Concepts, Techniques and Models of Computer Programming / Концепции, Техники и Модели Компьютерного Программирования: Глава 3 - Техники Декларативного Программирования

“S’il vous plaˆıt... dessine-moi un arbre!”
"Пожалуйста, нарисуй мне дерево!"
- Свободная адаптация "Маленького принца" Антуана де Сент-Экзюпери
(1900 - 1944)

Charlz_Klug 24.10.15 в 03:35

"Приятная черта в декларативном программировании в том, что вы можете написать описание и запустить его как программу. Противная черта в декларативном программировании заключается в том, что некоторые хорошие описания дают невероятно плохие программы. На декларативное программирование возлагается надежда на то, что вы можете перейти от описания к полезной программе не покидая сам язык."
- The Craft of Prolog, Richard O'Keefe (? - )

Charlz_Klug 19.11.15 в 19:41

Рассмотрим любую вычислительную операцию, то есть, фрагмент программы с входами и выходами. Мы говорим, что операция декларативна если,она возвращает один и тот же результат на одних и тех же аргументах вне зависимости от места вызова и любых состояний вычисления. Рисунок 3.1 иллюстрирует эту концепцию. Декларативная операция независима (не зависит от любых состояний исполнения внешней среды), не обладает состоянием 1 (не имеет внутреннего состояния исполнения, сохраняемого между вызовами) и детерминирована (всегда возвращает один и тот же результат на одних и тех же аргументах). Мы покажем, что все программы, написанные с применением модели этой главы являются декларативными.

Charlz_Klug 19.11.15 в 19:52

1 Концепцию "без состояний" иногда называют "иммутабельностью".

Charlz_Klug 19.11.15 в 19:53

Почему декларативное программирование является важным

Charlz_Klug 19.11.15 в 20:04

Декларативное программирование является важным из-за двух его свойств:

Charlz_Klug 19.11.15 в 20:05

Декларативные программы композиционны. Декларативные программы состоят из компонентов, каждый из которых может быть написан, протестирован и доказана его корректность независимо от других компонентов и его собственной прошедшей истории (предыдущих вызовов).

Charlz_Klug 19.11.15 в 20:08

Аргументы

Charlz_Klug 23.11.15 в 01:58

Декларативная операция

Charlz_Klug 23.11.15 в 01:58

Результаты

Charlz_Klug 23.11.15 в 01:58

Остальное вычисление

Charlz_Klug 23.11.15 в 01:59

Рисунок 3.1: Декларативная операция внутри общего вычисления.

Charlz_Klug 23.11.15 в 01:59

Рассуждения о декларативных программах просты. Программы написанные в декларативной модели более просты в рассуждениях чем программы написанные в более выразительных моделях. Поскольку декларативные программы вычисляют только значения, то к ним можно применять простые алгебраические и логические техники рассуждений.

Charlz_Klug 23.11.15 в 01:34

Эти два свойства важны для программирования как в целом, так и в частности. Было бы хорошо, если бы все программы можно было бы написать в декларативной модели. К сожалению, это не тот случай. Декларативная модель хорошо подходит к некоторым видам программ и плохо подходит для других программ. Эта и следующая главы посвящены техникам программирования декларативной модели и объясняют какие разновидности программ можно, а какие нельзя легко писать в этой модели.

Charlz_Klug 23.11.15 в 01:41

Начнём с того, что более внимательно рассмотрим первое свойство. Определим компонент как точно очерченный фрагмент программы с чётко обозначенными входами и выходами. Компонент может быть определён в терминах набора более простых компонентов. Например, в декларативной модели, процедура - это одна из разновидностей компонента. Прикладная программа - это наивысший компонент в иерархии компонентов. Низ иерархии состоит из примитивных компонентов, предоставленных системой.

Charlz_Klug 23.11.15 в 01:49

В декларативной программе взаимодействие между компонентами определяется исключительно входами и выходами компонентов. Рассмотрим программу с декларативным компонентом. Этот компонент можно понять основываясь только на нём самом и не понимая остальную программу. Усилия, затраченные на понимание всей программы равны сумме усилий затраченных на понимание этого и оставшихся других декларативных компонентов.

Charlz_Klug 23.11.15 в 01:56

Определение

Charlz_Klug 23.11.15 в 21:34

Программирование с рекурсией

Charlz_Klug 23.11.15 в 21:34

Абстракция

Charlz_Klug 23.11.15 в 21:34

Реальный мир

Charlz_Klug 23.11.15 в 21:35

Модель

Charlz_Klug 23.11.15 в 21:35

Процедурная

Charlz_Klug 23.11.15 в 21:36

На данных

Charlz_Klug 23.11.15 в 21:36

Что такое декларативность?

Charlz_Klug 23.11.15 в 21:37

Итеративное и рекурсивное вычисление
Программирование со списками и деревьями

Charlz_Klug 23.11.15 в 21:38

Управляющие абстракции
Высокоуровневое программирование

Charlz_Klug 23.11.15 в 21:38

Абстрактные типы данных
Безопасные абстрактные типы данных

Charlz_Klug 23.11.15 в 21:39

Эффективность по памяти и по времени
Структура программ с большой масштабируемостью
Недекларативные нужды

Charlz_Klug 23.11.15 в 21:41

Ограничения и расширения
Отношения к остальным декларативным моделям

Charlz_Klug 23.11.15 в 21:42

Рисунок 3.2: Структура главы

Charlz_Klug 23.11.15 в 21:42

Если между компонентом и остальной программой существует более тесная связь, то компоненты нельзя понять независимо. Их нужно изучать вместе, и усилия, затраченные на понимание будут большими. Они могут быть (примерно) пропорциональными произведению усилий, затраченных на каждую часть. Для программ с большим числом тесно взаимодействующих компонентов сложность понимания растёт лавинообразно, делая понимание трудным или невозможным. Примером подобного тесного взаимодействия является многопоточная программа с разделяемым состоянием, как это показано в Главе 8.

Charlz_Klug 23.11.15 в 21:52

Часто тесные взаимодействия оказываются необходимыми. Их нельзя "запретить законодательно" программируя в модели прямо не поддерживающей их (подробно освещено в Разделе 4.7). Но важный принцип в том, что они должны использоваться только при необходимости и никак иначе. Для соблюдения этого принципа необходимо чтобы компоненты были по возможности декларативными.

Charlz_Klug 23.11.15 в 22:00

Написание декларативных программ

Charlz_Klug 23.11.15 в 22:06

Простой способ писать декларативные программы - это использовать декларативную модель последней главы. Базовые операции над типами данных декларативны, то есть, арифметические операции, списковые операции и операции над записями. Если следовать определённым правилам, то возможно создание новых декларативных операций, путём комбинирования других декларативных операций. Комбинирование декларативных операций относится к операциям декларативной модели и результатом является декларативная операция. Этой теме посвящён Раздел 3.1.3.

Charlz_Klug 23.11.15 в 22:17

Другой пример декларативной комбинации - стандартное правило алгебры "равенство может быть замещено равенством". В языках программирования это свойство называется ссылочной прозрачностью. Оно очень сильно упрощает рассуждения о программах. Например, если мы знаем, что f(a) = a^2, то мы можем заменить f(a) выражением a^2 вне зависимости от того, где встречается f(a). Тогда равенство b = 7f(a)^2 преобразуется в b = 7a^4. Такое возможно из-за декларативности f(a); f(a) зависит только от его аргументов и не зависит от другого состояния вычисления.

Charlz_Klug 23.11.15 в 22:27

Базовой техникой для написания декларативных программ является рассмотрение программ как набора определений рекурсивных функций и использование высокоуровневости для упрощения структуры программы. Рекурсивная функция - это функция, тело описания которой прямо, либо косвенно ссылается на саму функцию. Прямая рекурсия обозначает, что функция применяется непосредственно в своём теле. Косвенная рекурсия обозначает что функция ссылается на другую функцию, которая прямо или косвенно ссылается на исходную функцию. Высокоуровневость означает, что функции могут работать с другими функциями как с аргументами и результатами. Эта способность лежит в основе всех техник построения абстракций, которые мы покажем в книге. Высокоуровневость может частично компенсировать малую выразительность декларативной модели, например, она позволяет реализовать ограниченные формы параллелизма и состояния в декларативной модели.

Charlz_Klug 24.11.15 в 22:51

Декларативное программирование

Charlz_Klug 24.11.15 в 22:52

Описательно

Charlz_Klug 24.11.15 в 22:52

Программируемо

Charlz_Klug 24.11.15 в 22:52

Наблюдательно

Charlz_Klug 24.11.15 в 22:53

Определительно

Charlz_Klug 24.11.15 в 22:53

Декларативная модель

Charlz_Klug 24.11.15 в 22:53

Функциональное программирование

Charlz_Klug 24.11.15 в 22:54

Логическое программирование

Charlz_Klug 24.11.15 в 22:54

Рисунок 3.3: Классификация декларативного программирования

Charlz_Klug 24.11.15 в 22:55

Структура главы

Charlz_Klug 24.11.15 в 22:58

Эта глава описывает как писать практичные декларативные программы. Глава условно разделена на шесть частей, показанных на Рисунке 3.2. Первая часть определяет "декларативность". Вторая часть даёт обзор техник программирования. Третья и четвёртая части описывают процедурные абстракции и абстракции на данных. Пятая часть показывает как декларативное программирование взаимодействует с остальной средой вычисления. Шестая часть делает отступление для того, чтобы показать пользу декларативной модели и расположение декларативной модели по отношению к остальным моделям.

Charlz_Klug 24.11.15 в 23:06

Пустой оператор

Charlz_Klug 25.11.15 в 12:49

Последовательность операторов

Charlz_Klug 25.11.15 в 12:49

Создание переменной

Charlz_Klug 25.11.15 в 12:49