Данные и программы
Рассмотрим на примере языка Лисп подход к представлению данных и программ в языках функционального программирования.
Любые структуры данных начинаются с элементарных значений. Следуя Лиспу, в функциональном программировании такие значения называют атомами или символами. Одинаково выглядящие атомы не различимы по своим свойствам, хотя проявления этих свойств могут быть обусловлены контекстом использования атомов. Каждый атом имеет список свойств. Когда атом читается (вводится) впервые, тогда для него и создается список свойств. Список свойств характеризуется специальной структурой, подобной записям в Паскале, но указатели в такой записи сопровождаются тэгами, символизирующими тип хранимой информации. Первый элемент этой структуры расположен по адресу, который задан в указателе. Остальные элементы доступны по этому же указателю с помощью ряда специальных функций. Элементы структуры содержат различные свойства атома. Каждое свойство помечается атомом, называемым индикатором, или расположено в фиксированном поле структуры.
Функция CONS строит структуры данных из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, - в правой.
Функция CAR обеспечивает доступ к первому элементу списка - его "голове", а функция CDR - к укороченному на один элемент списку - его "хвосту", т.е. к тому, что остается после удаления головы.
Функция ATOM позволяет различать составные и атомарные объекты: на атомах ее значение "истина", а на структурированных объектах - "ложь".
Функция EQ выполняет проверку атомарных объектов на равенство.
Различие истинностных значений в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение "ложь" - это всегда Nil.
Любая структура данных может быть построено из атомов с помощью CONS, и любая его часть может быть выделена с помощью CAR-CDR.
Атом Nil, рассматриваемый как представление пустого списка (), играет роль ограничителя в любом списке.
Гипотезу об универсальности символьных данных, прежде всего, следует проверить при выборе представления форм, возникающих при написании программы и ее основного конструктива - переменных, констант, выражений, определений, ветвлений, вызовов функций:
- Самая простая форма выражения - это переменная. Она может быть представлена как атом.
- Все более сложные формы понимаются как применение функции к ее аргументам (вызов функции). Аргументом функции может быть любая форма. Вызов функции можно строить как список, первый элемент которого - представление функции, остальные элементы - аргументы функции. (функция аргумент1 аргумент2 ... )
- Имена функций, как и переменные, изображаются с помощью атомов.
Соответствие между именем функции и ее определением можно задать с помощью специального конструктора функций. Вместо конструктора LABEL, описанного в лекции 1, в реальные системы программирования включают ряд средств с разными особенностями подготовки, реализации и применения определений функций. Common Lisp включает в себя конструктор функций DEFUN, первый аргумент которого - имя функции, второй - список аргументов функции, а третий - тело определения функции. Формальным результатом DEFUN является ее первый аргумент, который меняет свой статус - теперь это имя новой функции. Определение функции строится с помощью неявного LAMBDA-конструктора, объединяющего список аргументов функции и тело ее определения.
Пример 7.1. Новая функция "третий".
Именование функций работает подобно присваиванию значений переменным, но идентификатору присваивается объект другой категории - структура, символизирующая функциональный объект, содержащая список формальных параметров функции и тело ее определения.Определение функцииКомментарии
(DEFUN третий (x) (CAR (CDR (CDR x))) ) ; Атом "третий" связан ;с выражением " ( LAMBDA (x ) (CAR (CDR (CDR x ))) ) "
имя новой функции параметры функции тело функции
Представления функции могут вычисляться и передаваться как параметры или результаты других функций. Соответствие между именем и определением функции может быть изменено, подобно тому, как меняется соответствие между именем переменной и ее значением.
- Композиции функций можно строить с помощью вложенных скобок.
(функция1 (функция2 аргумент21 аргумент22 ... ) аргумент2 ... )
Приведенные правила ничего не говорят ни о природе данных и функций, ни о порядке вычисления аргументов и композиций функций. Речь идет исключительно о форме - внешнем виде списков, используемых для записи программы. Такая синтаксическая оболочка, в которой еще не конкретизированы операции над данными, является общей спецификацией реализационной основы для определения аппликативных систем, допускающих специализацию практически в любом направлении. Можно сказать, что Лисп является аппликативной системой, специализированной для обработки списков.
Если объект играет роль константы, то для объявления константы достаточно заблокировать его вычисление, как бы взять его в кавычки (quotation), отмечающие буквально используемые фразы, не требующие обработки. Для такой блокировки вводится специальная функция QUOTE, предохраняющая свой единственный аргумент от вычисления.
(QUOTE (A B C) ) - константа (A B C) объявлена
Можно сказать, что функция QUOTE выполняет в древовидной структуре программы роль помеченного контейнера. С ее помощью любое выражение может быть заключено в контейнер, а контейнер помечен указанием, что вычислять его содержимое не следует.
Ветвление (условное выражение) обеспечивает специальная функция COND (condition), аргументами которой являются двухэлементные списки, содержащие предикаты и соответствующие им выражения. Аргументов может быть сколько угодно, а обрабатываются они по особой схеме: сначала вычисляются первые элементы аргументов по порядку, пока не найдется предикат со значением "истина". Затем выбирается второй элемент этого аргумента, и вычисляется его значение, которое и считается значением всего условного выражения.
(COND (p1 e1) (p2 e2) ... (pk ek) ) | |_______|__________|_______ ветви условного выражения |_______|___________|__________ предикаты для выбора ветви
Каждый предикат pi или ветвь ei может быть любой формы: переменная, константа, вызов функции, композиция функций, условное выражение.
Специальные функции QUOTE, COND, LAMBDA и DEFUN существенно отличаются от обычных функций CAR, CDR, CONS, ATOM, EQ правилом обработки аргументов. Обычно функции получают значения аргументов, предварительно вычисленные системой программирования по формулам фактических параметров функции. Специальные функции не требуют такой предварительной обработки параметров. Они сами могут выполнять все необходимое, используя представление фактических параметров в виде списков.
- Определения могут быть рекурсивными.
(DEFUN премьер (x)(COND ((ATOM x) x) (T (премьер (CAR x ))) ))
Пример 7.2. Новая функция "премьер" выбирает первый атом из любого данного
- Собственно механизм связывания пока определен не был.
Точные границы применимости функций определяются в виде определения универсальной функции EVAL, позволяющей вычислять значения выражений, представленных в виде списков, - правило интерпретации выражений.
Такая единая структура данных оказалась вполне достаточной для представления сколь угодно сложных программ.
Выполнение программы устроено как интерпретация данных, представляющих выражения, имеющие значение.
- Возможно достаточно свободное программирование функционалов, использующих функции в качестве аргументов или результатов.
Пример 7.7. Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn:
(defun map-comp (fn al vl); fn покомпонентно применить ; к соотвественным элементам AL и VL (cond (xl (cons (funcall fn (car al) (car vl)) ; Вызов данного FN как функции от элементов двух списков (map-comp (cdr al) (cdr vl)) ) ) ) )
Теперь покомпонентные действия над векторами, представленными с помощью списков, полностью в наших руках. Вот списки и сумм, и произведений, и пар, и результатов проверки на совпадение:
(map-comp #'+ '(1 2 3) '(4 6 9)) ; = (5 8 12 ) Суммы (map-comp #'* '(1 2 3) '(4 6 9)) ; = (4 12 27 ) Произведения (map-comp #'cons '(1 2 3) '(4 6 9)) ; = ((1 . 4)(2 . 6)(3 . 9)) Пары (map-comp #'eq '(4 2 3 ) '(4 6 9)) ; = (T NIL NIL ) Сравнения
Достаточно уяснить, что надо делать с элементами списка, остальное довершит функционал map-comp, отображающий этот список в список результатов заданной функции.
Пример 7.8. Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого.
(defun mapf (fl el) (cond ; Пока первый аргумент не пуст, (fl (cons (funcall (car fl) el ) ; применяем очередную функцию ; ко второму аргументу
(mapf (cdr fl) el) ; и переходим к остальным функциям, ) ) ) ) ; собирая их результаты в общий список
(mapf '(length car cdr) '(a b c d )) ; = (4 a (b c d ))
Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов. Естественно, и серии, и последовательности представляются списками. - Возможны средства управления областями действия имен и их определений.
На практике сложилась традиция в систему функционального программирования включать специальные функции, обеспечивающие иерархию контекстов, в которых переменные обладают определенным значением. Для Clisp это LET и LET* [[73]].
Let сопоставляет локальным переменным независимые выражения. С ее помощью можно вынести из сложного определения любые совпадающие подвыражения. Пример:
(defun UNION- (x y) (let ( (a-x (CAR x)) (d-x (CDR x)) )
(COND ((NULL x) y) ((MEMBER a-x y) (UNION d-x y) ) (T (CONS a-x (UNION d-x y)) ) ) ))
Let -1) сопоставляет локальным переменным взаимосвязанные выражения. Она позволяет дозировать сложность именуемых подвыражений. Пример:
(defun ( (member (a x) (let* ( (n-x (null x)) (a-x (car x)) (d-x (cdr x)) (e-car (eq a a-x)) )
(COND (N-X Nil) (E-CAR T) (T (MEMBER A D-X))) ) ))
Labels - позволяет из списка определений функций формировать контекст, в котором вычисляются выражения.
Flet - специальная функция, позволяющая вводить локальные нерекурсивные функции.
defun - позволяет вводить новые определения на текущем уровне.
Лисп хорошо приспособлен к оптимизации программ. Любые совпадающие подвыражения можно локализовать и вынести за скобки, как можно заметить по передаче значения "(ASSOC e al )" в нижеприведенном определении интерпретатора с явным выделением зависимости от набора встроенных функций. Определения функций хранятся в ассоциативном списке подобно значениям переменных.
В качестве примера повышения гибкости определений приведено упрощенное определение Лисп-интерпретатора на Лиспе, полученное из М-выражения, приведенного Дж. Мак-Карти в описании Lisp 1.5 [[75]]. Уменьшена диагностичность, нет предвычислений и формы Prog.
В сравнении с определением в лекции 1 уточнена работа с функциональными аргументами:
(DEFUN EVAL (e al ) (COND ((EQ e NIL ) NIL ) ((ATOM e ) ((LAMBDA (v ) (COND (v (CDR v ) ) (T (ERROR 'undefvalue )) ) ) (ASSOC e al ) ) )
((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) ) ((EQ (CAR e) 'FUNCTION ) (LIST 'FUNARG (CADR fn ) al ) ) ((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) ) (T (apply (CAR e) (evlis (CDR e) al ) al ) ) ) ) (DEFUN APPLY (fn args al ) (COND
((EQ e NIL ) NIL ) ((ATOM fn ) (COND
((MEMBER fn '(CAR CDR CONS ATOM EQ )) (SUBR fn agrs al )) (T (APPLY (EVAL fn al ) args al )) ) )
((EQ (CAR fn ) 'LABEL ) (APPLY (CADDR fn ) args (CONS (CONS (CADR fn ) (CADDR fn )) al ) ) )
((EQ (CAR fn ) 'FUNARG ) (APPLY (CDR fn ) args (CADDR fn)) ) ((EQ (CAR fn ) 'LAMBDA ) (EVAL (CADDR fn ) (APPEND (PAIR (CADR fn ) args ) al )) (T (APPLY (EVAL fn al ) args al )) ) )
Пример 7.1.
Определения assoc, append, pair, list - стандартны.
SUBR - Функция, вызывающая примитивы, реализованные другими, обычно низкоуровневыми, средствами.
ERROR - Функция, выдающая сообщения об ошибках и сведения о контексте вычислений, способствующие поиску источника ошибки.
С другими расширениями и вариантами Лисп-интерпретатора можно ознакомиться в курсах Интернет-Университета ИТ, посвященных функциональному программированию и языку Лисп [[8]].
Расширение системы функционального программирования осуществляется простым введением/удалением соответствующих свойств атомов и функций.
Многие реализационные находки Лиспа, такие как ссылочная организация памяти, сборка мусора для повторного использования памяти, частичная компиляция программ с интерпретацией промежуточного кода, полиморфизм, длительное хранение атрибутов объектов в период их использования и т.д. перекочевали из области исследований и экспериментов на базе Лиспа в практику реализации операционных систем и систем программирования.
В нашей стране программирование мало соприкоснулось функциональным программированием, хотя знакомство с Лиспом состоялось из первых рук. Джон Мак-Карти в конце 1968 года познакомил Москву и Новосибирск с Лиспом, что побудило к реализации отечественных версий языка.
К середине семидесятых годов именно на Лиспе решались наиболее сложные в практике программирования задачи из области дискретной и вычислительной математики, системного, экспериментального и теоретического программирования, лингвистики, химии, биологии, медицины и инженерного проектирования. Пример - AutoCAD - система автоматизации инженерных расчетов, дизайна и комплектации изделий из доступного конструктива. Приверженцы Лиспа ценят его за элегантность, гибкость, а, главное, за способность к точному представлению программистских идей, удобной отладке и быстрому прототипированию.
Функциональные языки программирования достаточно разнообразны. Существует и активно применяется более трехсот диалектов Лиспа и родственных ему языков: Interlisp, muLisp, Clisp, Sheame, ML, Cmucl, Logo, Hope, Sisal, Haskell, Miranda и др. При сравнении языков и парадигм программирования часто классифицируют функциональные языки по следующим критериям: "ленивый" или аппликативный, последовательный и параллельный. Например, ML является аппликативным и последовательным, Erlang - аппликативным и параллельным, Haskell - "ленивым" и последовательным, а Clean - параллельным и "ленивым".
CMUCL - свободно- распространяемая реализация стандарта common lisp с эффективной компиляцией, осуществляемой как в объектный код, так и в байт-код[[34]]. По сравнению с CLISP CMUCL работает на меньшем количестве платформ и более требователен к памяти. CLISP обладает более мощной поддержкой многоязыковости. Поддерживает Unicode. Так как CMUCL компилируется в объектный код, то программы исполняются быстрее по сравнению с программами на CLISP. Несмотря на это математические примитивы в CLISP очень хорошо реализованы, кроме того, CLISP поддерживает вещественную арифметику с произвольной точностью [[79]].
Рефал. В отличие от ЛИСПа, основу РЕФАЛа составляет сопоставление с образцом. Благодаря этому типовая программа на РЕФАЛе вдвое-втрое короче по объему, чем аналогичная программа на языке ЛИСП, и гораздо более читаема. От ПРОЛОГа РЕФАЛ отличает концептуальная простота. Его сопоставление с образцом работает в прямом направлении, а не в обратном (начиная от цели), как в ПРОЛОГе. Это более естественный подход к написанию алгоритмов, что делает их более легкими для тестирования и отладки.
ML (Meta Language, изначальное предназначение - метаязык для представления систем автоматизации доказательств) имеет важную особенность: полиморфную систему типов данных, разработанную Робином Милнером. Подобная система была раньше предложена Роджером Хиндли и сейчас часто называется системой типов Хиндли-Милнера. Наличие механизма вывода типов позволило избавить программиста от необходимости явно описывать типы функций и в то же время производить строгий контроль типов. ML не чисто функциональный язык, он включает и императивные инструкции. ML развивался и включил в себя многие особенности других функциональных языков. Появилось несколько диалектов, наиболее известные из которых StandardML, CAML и чисто функциональный LazyML.
Haskell. В конце 80-х не было стандарта на чисто функциональный, ленивый язык. Haskell был создан с целью занять эту нишу. Haskell "ленивый", чисто функциональный язык.
Основан на лямбда-исчислении [[78]]. В функциональном стиле выражен ввод и вывод, для реализации которого использована концепция монад. В языке широко используется сопоставление с образцом, что приближает его к декларативным языкам.
Dylan. Dylan является попыткой компромисса между функциональным и ОО-подходом. Вследствие чего центральным объектом являются обобщенные функции (generic functions). Язык обладает предопределенной библиотекой, включающей в себя систему исключений, набор функций высшего порядка, средства самоанализа и др [[81]].
Erlang. Создан отделением компании Erricson, однако, является продуктом с открытым кодом. Этот функциональный язык специально создан для поддержки распределенной обработки, параллельности и обработки ошибок. Язык предназначен для систем реального времени и активно используется Erricson при создании телекоммуникационных систем [[80]].
В рамках проекта .Net выполнено большое число реализаций весьма различных функциональных языков программирования, в их числе Haskell, Sml, Scheme, Mondrian, Mercury, Perl, Oberon, Component Pascal, разрабатывается F# - новый язык ФП [[22]]. Еще большее разнообразие предлагает проект DotGNU, пытающийся отстоять приоритет в области разработки переносимого ПО. Развиваются линии учебного и любительского программирования и методично осваивается техника выстраивания иерархии абстрактных машин при определении языков программирования [[82]].
Разработка ЯФП и приспособленность средств ФП к быстрой отладке, верификации, их лаконизм, гибкость, конструктивность и моделирующая сила позволяют рассматривать ФП как основу информационной среды обучения современного программирования на всех уровнях проблематики от алгоритмизации до включения в социальный контекст приложений разрабатываемых ИС. Документация по GNU Clisp, xLisp, CMUCL и другим реализациям языка Lisp доступна на сайтах любителей ФП, а также на многих сайтах [[78],[79],[80],[81],[82]].
Примечание. Эквивалентность с точностью до побочного эффекта
