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

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

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

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

Каждая функция возвращает некоторое значение в вызвавшую его функцию, вычисление которой после этого продолжается; этот процесс повторяется до тех пор, пока начавшая процесс вычислений функция не вернет конечный результат пользователю.

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

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

Функциональное программирование весьма красиво и иногда в качестве первого языка программирования, изучаемого студентами, выбирается Haskell или Lisp. Для успешного овладения данным стилем программирования, впрочем, необходимо весьма глубокое понимание многих разделов математики.

Пример

Хорошей иллюстрацией функционального стиля программирования является программа на языке Haskell для получения всех пифагоровых троек чисел, не превосходящих заданного числа (пифагоровой тройкой называют три целых числа, являющихся сторонами некоторого прямоугольного треугольника).

Создайте файл с именем triads.hs в который поместите следующий текст: triads n = [(x,y,z)|let ns=[1..n], x<-ns, y<-ns, z<-ns, x*x+y*y==z*z] (скачать файл triads.hs)

triads n = [(x,y,z) | let ns = [1 .. n], x <- ns, y <- ns, z <- ns, x*x+y*y == z*z]

Такую программу легко понять: получить все тройки целых чисел x, y и z, не превышающих заданного числа n и удовлетворяющих условию x2+y2=z2.

Для запуска интерпретатора языка Haskell в командной строке наберите hugs. После появления приглашения > введите команду :load triads.hs для загрузки содержимого файла в память. Теперь можно находить пифагоровы триады, например, при помощи следующего вызова функции triads 50. Для завершения работы интерпретатора наберите :quit и нажмите на клавишу Enter.

Следующая программа на языке Haskell уже не столь очевидна, но она поражает своей краткостью.

Пример

Создайте файл с именем primes.hs и поместите в него следующие строки:

-- primes :: Integral a => [a] primes = map head (iterate sieve [2..]) sieve (p:xs) = [ x | x<-xs, x `rem` p /= 0 ]

(скачать файл primes.hs)

primes = map head (iterate sieve [2 ..]) sieve (p:xs) = [ x | x <- xs, x `rem` p /= 0 ]

После старта интерпретатора hugs и загрузки в него этой программы достаточно вызвать функцию primes (без аргументов) и программа начнет печатать простые числа до тех пор, пока вы не прервете ее выполнение, нажав комбинацию клавиш Ctrl+C.

Еще одной реализацией декларативного стиля является логическое программирование, основанное на логике предикатов, которое подробно рассматривается в следующей главе.

Логика предикатов - это ветвь формальной логики, получившая развитие в XX веке. В логическом программировании основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру, что ему следует делать. Prolog (от французского PROgrammation LOGique, далее Пролог) - это наиболее известный язык логического программирования. Этот язык (наряду с функциональным языком Lisp) часто называют языком искусственного интеллекта - с его помощью решаются задачи создания экспертных систем и систем обработки естественных языков.

Пример

Для иллюстрации принципов логического программирования с использованием языка Пролог приведем программу, находящую решение известной головоломки "Ханойская башня", изобретенной французским математиком Люка в 1883 году и украшенной им же легендой.

"Где-то в непроходимых джунглях, недалеко от города Ханоя, есть монастырь бога Брамы. В начале времен, когда Брама создавал Мир, он воздвиг в этом монастыре три высоких алмазных стержня и на один из них возложил 64 диска, сделанных из чистого золота. Он приказал монахам перенести эту башню на другой стержень (в соответствии с правилами, разумеется). С этого времени монахи работают день и ночь. Когда они закончат свой труд, наступит конец света."

Правила перемещения дисков таковы: разрешается снимать со стержня только верхний диск, запрещается класть больший диск на меньший, при каждом ходе передвигается только один диск.

Поместите в файл с именем hanoi.pl следующий текст (символ % начинает комментарий, который не обязательно помещать в файл).

% move(число_дисков, откуда, куда, через) move(1,X,Y,_) :- write('Move top disk from '), %передвиньте верхний диск с write(X), write(' to '), write(Y), nl. move(N,X,Y,Z) :- N>1, M is N-1, move(M,X,Z,Y), move(1,X,Y,_), move(M,Z,Y,X).

(скачать файл hanoi.pl)

% move(число_дисков, откуда, куда, через) move(1,X,Y,_) :- write('Move top disk from '), write(X), write(' to '), write(Y), nl. move(N,X,Y,Z) :- N>1, M is N-1, move(M,X,Z,Y), move(1,X,Y,_), move(M,Z,Y,X).

Запустите интерпретатор языка Пролог при помощи команды pl. После появления приглашения к работе (?- ) загрузите содержимое файла командой [hanoi]. (расширение файла указывать не нужно, а вот точка после закрывающей квадратной скобки необходима). Теперь, чтобы заставить Пролог решить задачу о перемещении трех дисков, введите следующий запрос:

move(3,left,right,center).

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

Для завершения работы с интерпретатором наберите команду halt. и нажмите Enter.

Задания

Измените программу triads.hs так, чтобы не выводились одинаковые тройки чисел, такие как (3,4,5) и (4,3,5). Для этого введите дополнительное условие, например, x<y.
Получите решение головоломки "Ханойская башня" для четырех дисков.

Содержание раздела