Определение универсальной функции
Универсальная функция eval, которую предстоит определить, должна удовлетворять следующему условию: если представленная аргументом форма сводится к функции, имеющей значение на списке аргументов этой же формы, то это значение и является результатом функции eval.
(eval '(fn arg1 ... argK))
Результат применения "fn" к аргументам "arg1, ..., argK".
Предикаты и истинность в Лиспе
В Лиспе есть два атомных символа, которые представляют истину и ложь соответственно. Эти два атома - T и NIL. Эти символы - реальные значения всех предикатов в системе. Главная причина в удобстве кодирования. Во многих случаях достаточно отличать произвольное значение от пустого списка.
Не существует формального различия между функцией и предикатом в Лиспе. Предикат может быть определен как функция со значениями либо T либо NIL. Можно использовать форму, не являющуюся предикатом там, где требуется предикат: предикатная позиция условного выражения или аргумент логического предиката. Семантически любое S-выражение, только не NIL, будет рассматриватсья как истинное в таком случае. Предикат EQ ведет себя следующим образом:
Если его аргументы различны, значением EQ является NIL.Если оба его аргументы являются одним и тем же атомом, то значение - Т.Если значения одинаковы, но не атомы, то его значение T или NIL в зависимости от того, идентично ли представление аргументов в памяти.Значение EQ всегда T или NIL. Оно никогда не бывает неопределено, даже если аргументы плохие.
Выполнено достаточно строгое построение совершенно формальной математической системы, называемой "Элементарный ЛИСП". Составляющие этой формальной системы:
Множество символов, называемых S-выражениями.Система функциональных обозначений для основных понятий, трубемых при программировании обрботки S-выражений.Формальное представление функциональных обозначений в виде S-выражений.Универсальная функция (записанная в виде S-выражения), интерпретирующая обращение произвольной функции, записанной как S-выражение, к ее аргументам.Система базовых функций, обеспечивающих техническую поддержку обработки S-выражений, и специальных функций, обеспечивающих управление вычислениями.
Выполненное определение универсальной функции – макетный образец Лисп-системы, основные черты которой унаследованы многими системами программирования.
| (Apply Функция Список-ргументов ) | Применяет функцию к списку аргументов |
| ( Compile Название ) | Компилирует названную функцию, кроме того сообщает, успешна ли компиляция |
| (Eval Форма ) | Вычисление формы |
| (Funcall Функция Аргумент … ) | Применяет функцию к аргументам |
| (The Тип Форма) | Приводит значение Формы к заданному Типу |
| (Type-of Данное ) | Выдает тип данного |
| (Quote Форма ) | Форма без вычсления выдается как результат |
Синтаксическая сводка программ на языке
|
<форма> ::= <переменная> | (QOUTE <S-выражение>) | (COND (<форма> <форма>) ... (<форма> <форма>)) | (<функция> <аргумент> ... <аргумент>) <аргумент> ::= <форма> <переменная> ::= <идентификатор> <функция> ::= <название> | (LAMBDA <список_переменных> <форма>) | (DEFUN <название> <функция>) <список_переменных> ::= (<переменная> ... ) <название> = <идентификатор> <идентификатор> ::= <атом> |
| Пример 6.1. Синтаксическая сводка программ на языке Лисп |
| Закрыть окно |
Пример <форма> ::= <переменная>
<форма> ::= <переменная>
| (QOUTE )
| (COND (<форма> <форма>) ... (<форма> <форма>))
| (<функция> <аргумент> ... <аргумент>)
<аргумент> ::= <форма>
<переменная> ::= <идентификатор>
<функция> ::= <название>
| (LAMBDA <список_переменных> <форма>)
| (DEFUN <название> <функция>)
<список_переменных> ::= (<переменная> ... )
<название> = <идентификатор>
<идентификатор> ::= <атом>
Вычисление
Явное определение такой функции позволяет достичь четкости механизмов обработки Лисп-программ.
(eval '((LAMBDA (x y) (CONS (CAR x) y)) '(A B) '(C D) )) = (A C D)
Вводим две основные функции eval и apply для обработки форм и обращения к функциям соответственно. Каждая из этих функций использует ассоциативный список для хранения связанных имен - значений переменных и определений функций. Сначала этот список пуст.
Вернемся к синтаксической сводке вычислимых форм.
<форма> ::= <переменная> | (QOUTE <S-выражение>) | (COND (<форма> <форма>) ... (<форма> <форма>)) | (<функция> <аргумент> ... <аргумент>)
<аргумент> ::= <форма>
<переменная> ::= <идентификатор>
<функция> ::= <название> | (LAMBDA <список_переменных> <форма>) | (DEFUN <название> <функция>)
<список_переменных> ::= (<переменная> ... )
<название> = <идентификатор>
<идентификатор> ::= <атом>
Пример 6.1. Синтаксическая сводка программ на языке Лисп (html, txt)
Каждой ветви этой сводки соответствует ветвь универсальной функции:
(DEFUN eval (e) (ev e '((Nil . Nil))))
Вспомогательная функция ev понадобилась, чтобы ввести накапливающий параметр – ассоциативный список, в котором будут храниться связи между переменными и их значениями и названиями функций и их определениями.
(defun ev (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) )) )
Поясним ряд пунктов этого определения.
Первый аргумент ev - форма. Если она - атом, то этот атом может быть только именем переменной, а значение переменной должно бы уже находиться в ассоциативном списке.
Если CAR от формы - QUOTE, то она представляет собой константу, значение которой вычисляется как CADR от нее самой.
Если CAR от формы - COND, то форма - условное выражение. Вводим вспомогательную функцию EVCON, (определение ее будет дано ниже), которая обеспечивает вычисление предикатов (пропозициональных термов) по порядку и выбор формы, соответствующей первому предикату, принимающему значение "истина".
Эта форма передается EV для дальнейших вычислений.
Все остальные случаи рассматриваются как список из функции с последующими аргументами.
Вспомогательная функция EVLIS обеспечивает вычисление аргументов, затем представление функции и список вычисленных значений аргументов передаются функции APPLY.
(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)) ) ((QUOTE T) (apply (ev fn a) x a)) ) ) ) ((eq(car fn)'LAMBDA) (ev (caddr fn) (pairlis (cadr fn) x a) )) ((eq (car fn) 'DEFUN) (apply (cadddr fn) x (cons (cons (cadr fn) (cons 'LAMBDA (caddr fn) ) ) a) ))))
Первый аргумент apply - функция. Если она - атом, то существует две возможности: атом представляет одну из элементарных функций (car cdr cons atom eq). В таком случае соответствующая ветвь вычисляет значение этой функции на заданных аргументах. В противном случае, этот атом - имя ранее заданного определения, которое можно найти в ассоциативном списке.
Если функция начинается с LAMBDA, то ее аргументы попарно соединяются со связанными переменными, а тело определения (форма из лямбда-выражения) передается как аргумент функции EV для дальнейшей обработки.
Если функция начинается с DEFUN, то ее название и определение соединяются в пару и полученная пара размещается в ассоциативном списке, чтобы имя функции стало определенным при дальнейших вычислениях. Они произойдут как рекурсивный вызов apply, которая вместо имени функции теперь работает с ее определением при более полном ассоциативном списке - в нем теперь размещено определение названия функции. Поскольку определение размещается на "верху" стека, оно становится доступным для всех последующих переопределений, то есть работает как локальный объект. Глобальные объекты, такие как обеспечивает псевдо-функция DEFUN в системе Clisp, устроены немного иначе, что будет рассмотрено в следующей лекции.
assoc и pairlis уже определены ранее.
(DEFUN evcon (c a) (COND ((ev (caar c) a) (ev (cadar c) a) ) ( T (evcon (cdr c) a) ) ))
*) Примечание. В идеальном Лиспе не допускается отсутствие истинного предиката, т.е. пустого C.
(DEFUN evlis (m a) (COND ((null m) Nil ) ( T (cons(ev (car m) a) (evlis(cdr m) a) )) )
При
(DEFUN eval (e) (ev e ObList ))
определения функций могут накапливаться в системной переменной ObList, тогда они могут работать как глобальные определения. ObList обязательно должна содержать глобальное определение встроенной константы Nil, можно разместить в ней и представление истины - T.
Определение универсальной функции является важным шагом, показывающим одновременно и механизмы реализации языков программирования, и технику функционального программирования на любом языке. Пока еще не описаны многие другие особенности языка Лисп, которые будут рассмотрены позднее. Но все они будут увязаны в единую картину, основа которой согласуется с этим определением.
В строгой теории идеального Лиспа все функции следует определять всякий раз, как они используются. На практике это неудобно. Реальные системы имеют большой запас встроенных функций (более тысячи в Clisp-е), известных языку, и возможность присоединения такого количества новых функций, какое понадобится.В идеальном языке Лисп базисные функции CAR и CDR не определены для атомарных аргументов. Такие функции, имеющие осмысленный результат не на всех значениях естественной области определения, называют частичными. Отладка и применение частичных функций требует большего контроля, чем работа с тотальными, всюду определенными функциями.
Во многих Лисп-системах все элементарные функции вырабатывают результат и на списках, и на атомах, но его смысл зависит от системных решений, что может создавать трудности при переносе программ на другие системы. Базисный предикат EQ всегда имеет значение, но смысл его на неатомарных аргументах будет более понятен после знакомства со структурами данных, используемыми для представления списков в машине.
Для расширений и диалектов языка Лисп характерно большое разнообразие условных форм, конструкций выбора, ветвлений и циклов, практически без ограничений на их комбинирование. Форма COND выбрана для начального знакомства как наиболее общая. За редким исключением в Лисп-системе нет необходимости писать в условных выражениях (QUOTE T) или (QUOTE NIL). Вместо них используются встроенные константы T и Nil соответственно.В реальных системах функционального программирования обычно поддерживается работа с целыми, дробными и вещественными числами в предельно широком диапазоне, а также работа с кодами и строками. Такие данные, как и атомы, являются минимальными объектами при организации обработки нформации, но отличаются от атомов тем, что их смысл задан их собственным представлением непосредственно. Их понимание не требует ассоциаций или связывания. Поэтому и константы такого вида не требуют префикса в виде апострофа.
Универсальная функция – это функция, которая может вычислять значение любой формы и представляет собой инетрпретатор в миниатюре.При реализации универсальной функции необходимо учитывать способ представления контекста и виды вычисляемых форм.Контекст удобно представлять с помощью ассоциативных списков.Универсальная функция должна предусматривать основные виды вычисляемых форм, задающих значения аргументов, а также представления функций, в соответствии со сводом вышеприведенных правил языка.
