Определение универсальной функции
Универсальная функция EVAL, которую предстоит определить, должна удовлетворять следующему условию: если представленная аргументом форма сводится к функции, имеющей значение на списке аргументов этой же формы, то данное значение и является результатом функции
eval.
(eval '(fn arg1 ... argK)) ; = результат применения fn к аргументам arg1, ..., argK.
Явное определение такой функции позволяет достичь четкости механизмов обработки Лисп-программ.
(eval '((LAMBDA (x y) (CONS (CAR x) y)) '(A B) '(C D) )) ; = (A C D)
Вводим две важные функции
EVAL и
APPLY для обработки форм и обращения к функциям, соответственно. Каждая из этих функций использует ассоциативный список для хранения связанных имен — значений переменных и определений функций.
Сначала этот список пуст.
Вернемся к синтаксической сводке вычислимых форм.
форма ::= переменная | (QUOTE S-выражение) | (COND (форма форма) ... (форма форма)) | (функция аргумент ...)
аргумент ::= форма
переменная ::= идентификатор
функция ::= название | (LAMBDA список_переменных форма) | (LABEL название функция) список_переменных ::= (переменная ... )
название ::= идентификатор
идентификатор ::= атом
S-выражение ::= атом | (S-выражение . S-выражение) | (S-выражение ...)
Ветвям этой сводки будут соответствовать ветви универсальной функции:
Поэтому понадобится вспомогательная функция
APPLY для обработки обращений к функциям. Кроме того работа с идентификаторами использует ассоциативный список для хранения связанных имен - значений переменных и определений функций.
(DEFUN eval (e) (eval-a e '((Nil . Nil)(T . T))))
Вспомогательная функция EVAL-A понадобилась, чтобы для EVAL завести накапливающий параметр — ассоциативный список , в котором будут храниться связи между переменными с их значениями и названиями функций с их определениями. Здесь его значение ((Nil . Nil)(T . T)) обеспечивает, что атомы NIL и T обозначают сами себя.
(DEFUN eval(e a) (COND ((atom e) (cdr(assoc e a)) ) ((eq (car e) 'QUOTE) (cadr e)) ((eq(car e) 'COND) (evcon(cdr e) a)) ( T (apply (car e) (evlis(cdr e) a) a) ) ) )
(defun apply (fn x a) (COND ((atom fn)
(COND ((eq fn 'CAR) (caar x)) ((eq fn 'CDR) (cdar x)) ((eq fn 'CONS) (cons(car x)(cadr x)) ) ((eq fn 'ATOM) (atom(car x)) ) ((eq fn 'EQ) (eq(car x)(cadr x)) ) (T (apply (eval fn a) x a)) ) )
((eq(car fn)'LAMBDA) (eval-a (caddr fn) (pairlis (cadr fn) x a) )) ((eq (car fn) 'LABEL) (apply (caddr fn) x (cons (cons (cadr fn)(caddr fn)) a) ) ) ) )
ASSOC и PAIRLIS уже определены ранее.
(DEFUN evcon (c a) (COND ((eval (caar c) a) (eval (cadar c) a) ) ( T (evcon (cdr c) a) ) ) )
( Не допускается отсутствие истинного предиката, т.е. пустого C.)
(DEFUN evlis (m a) (COND ((null m) Nil ) ( T (cons (eval (car m) a) (evlis(cdr m) a) ) ) ) )
При
(DEFUN eval (e) (eval-a e ObList ))
определения функций могут накапливаться в системной переменной ObList, то есть работать как глобальные определения. ObList обязательно должна содержать глобальное определение встроенной константы "Nil", можно и сразу разместить в ней "T".
Поясним ряд пунктов этих определений.
Первый аргумент EVAL — форма. Если она — атом, то этот атом может быть только именем переменной, а значение переменной должно уже находиться в ассоциативном списке.
Если CAR от формы — QUOTE, то она представляет собой константу, значение которой выделяется как
CADR от нее самой.
Если CAR от формы — COND, то форма — условное выражение. Вводим вспомогательную функцию
EVCON (определение ее будет дано ниже), которая обеспечивает вычисление предикатов (пропозициональных термов) по порядку и выбор формы, соответствующей первому предикату, принимающему значение "истина". Эта форма передается EVAL для дальнейших вычислений.
Все остальные случаи рассматриваются как список из функции с аргументами.
Вспомогательная функция
EVLIS обеспечивает вычисление аргументов, затем представление функции и список вычисленных значений аргументов передаются функции APPLY.
Первый аргумент APPLY — функция. Если она — атом, то существует две возможности. Атом может представлять одну из элементарных функций
(CAR CDR CONS ATOM EQ). В таком случае соответствующая ветвь вычисляет значение этой функции на заданных аргументах. В противном случае, этот атом — имя функции или название ранее заданного определения, которое можно найти в ассоциативном списке , подобно вычислению переменной.
Если функция начинается с LAMBDA, то ее аргументы попарно соединяются со связанными переменными, а тело определения (форма из лямбда-выражения) передается как аргумент функции EVAL-A для дальнейшей обработки.
Если функция начинается с LABEL, то ее название и определение соединяются в пару, и полученная пара размещается в ассоциативном списке, чтобы имя функции стало определенным при дальнейших вычислениях. Они произойдут как рекурсивный вызов APPLY, которая вместо имени функции теперь работает с ее определением при более полном ассоциативном списке — в нем уже размещено определение имени функции. Поскольку определение размещается "наверху" стека, оно становится доступным для всех последующих переопределений, то есть работает как локальный объект. Глобальные объекты, которые обеспечиваются псевдо-функцией DEFUN, устроены немного иначе, что будет рассмотрено в следующей лекции.
Определение универсальной функции является важным шагом, показывающим одновременно и механизмы реализации функциональных языков, и технику функционального программирования на любом языке. Пока еще не описаны многие другие особенности языка Лисп и функционального программирования, которые будут рассмотрены позднее. Но все они будут увязаны в единую картину, основа которой согласуется с этим определением.
- В строгой теории аппликативного программирования все функции следует определять всякий раз, когда они используются. На практике это неудобно. Реальные системы имеют большой запас встроенных функций (более тысячи в Clisp-е), известных языку, и возможность присоединения такого количества новых функций, какое понадобится. Во многих реализациях Лиспа все элементарные функции вырабатывают результат и на списках, и на атомах, но его смысл зависит от системных решений, что может создавать трудности при переносе программ на другие системы.
Базисный предикат EQ всегда имеет значение, но смысл его на неатомарных аргументах будет более ясен после знакомства со структурами данных, используемыми для представления списков в машине. - В чистом языке Лисп базисные функции CAR и CDR не определены для атомарных аргументов. Такие функции, имеющие осмысленный результат не на всех значениях естественной области определения, называют частичными. Отладка и применение частичных функций требует большего контроля, чем работа с тотальными, всюду определенными функциями. Во многих реализациях функциональных языков программирования все функции всегда вырабатывают значение. При необходимости каждый существенный класс объектов пополняется значением класса ERROR, символизирующим исключительные ситуации.
- Для функциональных языков характерно большое разнообразие условных форм, конструкций выбора, ветвлений и циклов, практически без ограничений на их комбинирование. Форма COND выбрана для начального знакомства как наиболее общая. За редким исключением в Лиспе нет необходимости писать в условных выражениях (QUOTE T) или (QUOTE NIL). Вместо них используются встроенные константы
T и Nil, соответственно. - В реальных системах функционального программирования обычно поддерживается работа с целыми, дробными и вещественными числами в предельно широком диапазоне, а также работа с битовыми и текстовыми строками. Такие данные, как и атомы, являются минимальными объектами при обработке информации, но отличаются от атомов тем, что их смысл задан непосредственно их собственным представлением. Их понимание не требует ассоциаций или связывания. Поэтому и константы такого вида не нуждаются в префиксе в виде апострофа.
Приведенное выше самоопределение Лисп-интерпретации является концептуальным минимумом, обеспечивающим постепенность восприятия более сложных особенностей специфики функционального программирования, а также методов реализации языков и систем программирования, которые будут иллюстрироваться в дальнейшем. Они будут введены как расширения или уточнения чистого определения универсальной функции.
