На этом шаге мы приведем некоторые соображения по созданию интерпретатора.
Чистый LISP - это простое подмножество LISP, состоящее из:
- основных примитивов CAR, CDR, CONS, EQ и ATOM;
- управляющих структур, использующих COND, рекурсию и суперпозицию функций;
- списковых структур, содержащих только атомы и подсписки;
- примитива LAMBDA для определения новых функций.
С помощью такого подмножества может быть выполнена большая часть обычной обработки списков в LISP. Чистый LISP фактически является универсальным языком.
Чистый LISP послужил основой для многих теоретических исследований в программировании. Это подмножество языка LISP имеет очень простую, регулярную, рекурсивную структуру, что делает его удобным объектом для формального анализа [2, стр.479-480].
Руководство по LISP [1] относится к тем немногочисленным руководствам по языкам программирования, в которых дается совершенно четкое описание структур, существующих во время выполнения программы, - структур, на которых построена реализация языка. В центре внимания находится полное определение интерпретатора, выполняющего LISP-программы; это определение имеет форму LISP-программ для двух примитивов: EVAL и APPLY. Структура интерпретатора настолько прозрачна, что все определение занимает менее двух страниц.
Первоначально Маккарти определил интерпретатор в метанотации языка LISP [3, с.180], при использовании которой элегантность определения языка особенно заметна:
evalquote[fn;x] = apply[fn;x;NIL];
apply[fn;x;a] = [ atom[fn] -->
[ 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 [caddr[fn];pairlis[cadr[fn];x;a]];
eq [car[fn];LABEL] -->
apply[caddr[fn];x;cons
[cons[cadr[fn];caddr[fn]];a]];
eq [car[fn];FUNARG] -->
apply[cadr[fn];x;caddr[fn]]
];
eval [e;a] = [ atom[e] --> cdr[assoc[e;a]];
atom[car[e]] -->
[ eq[car[e];QUOTE] --> cadr[e];
eq[car[e];COND] -->
evcon[cdr[e];a];
eq[car[e];FUNCTION] -->
list[FUNARG;cadr[e];a];
T -->
apply [car[e];evlis[cdr[e];a];a]
];
T --> apply[car[e];evlis[cdr[e];a];a]
];
pairlis[x;y;a] = [ null[x] --> a;
T --> cons[cons[car[x];car[y]];
pairlis[cdr[x];cdr[y];a]]
];
assoc[x;a] = [ eq[caar[a];x] --> car[a];
T --> assoc[x;cdr[a]]
];
evcon[c;a] = [ eval[caar[c];a] --> eval[cadar[c];a];
T --> evcon[cdr[c];a]
];
evlis[m;a] = [ null[m] --> NIL;
T --> cons
[eval[car[m];a];evlis[cdr[m];a]]
];
Для сравнения: в (пересмотренном) сообщении об алголе-60 (1963 г.) используется 1109 синтаксических переменных и столько же правил Бэкуса, впрочем 73 из них - только для упрощения записи; из оставшихся 36 синтаксических переменных еще половину можно изъять за счет применения знака итерации. В сообщении о Паскале (1971 г.) фигурируют 197 синтаксических переменных с обобщенными правилами Бэкуса, в которых применяется знак итерации; многие из них опять введены для упрощения обозначений [4, т.2, с.545].
Более существенно в описании LISP определение структур, существующих во время выполнения программ. А-список как средство представления сред ссылок, использование списков свойств для ассоциации имен функций с их определениями, описания представлений атомов, списков, списков свойств и чисел во время выполнения программ - все это вместе позволяет легко понять структуру программы во время ее выполнения.
Ясность определения важна как для программиста, пишущего прграммы на языке LISP, так и для программиста, занимающегося реализацией языка LISP. Первому определение языка позволяет получить ответы на тонкие вопросы, касающиеся его семантики, второму оно необходимо как руководство по реализации, показывающее предполагаемый характер работы конкретных конструкций (хотя в деталях каждая реализация может существенно отличаться от описанной в определении). Данное определение LISP является, вероятно, наиболее широко известным определением виртуальной машины языка. К сожалению, лишь в немногих определениях других языков последовали этому примеру [2, стр.479-480].
Написание LISP на языке LISP имеет два важных преимущества. Во-первых, оно позволяет более строго определить семантику языка, исходя из немногих примитивных функций и, во-вторых, описание языка на нем самом делает его проще для понимания и позволяет одновременно описывать и основные функции языка, и применяемые им методы программирования. Последнее, как мы надеемся, позволит избежать ситуации, когда начинающий программист знает множество правил, основных и вспомогательных функций и процедур, но решительно не в состоянии воспользоваться своими знаниями, поскольку у него еще нет понятия о методах их применения.
Определение какого-нибудь языка на нем самом - это не такая очевидная задача. Хорошим пояснением к этому будет история зарождения подобной идеи [3, с.174-175].
Маккарти рассказывает, что во время его размышлений о семантике лисповской функции EVAL С.Рассел предложил запрограммировать ее тем же способом, что и другие функции LISPа: "... Этот EVAL был написан и опубликован в нашей статье, когда Стив Рассел сказал: "Послушайте, почему мне не запрограммировать этот EVAL и вы получите интерпретатор", на что я сказал ему: "Ну, ну, вы путаете теорию с практикой, наш EVAL предназначен для чтения, а не для вычислений." Но он на этом не остановился и сделал интерпретатор. Таким образом, С.Рассел оттранслировал EVAL из моей статьи в машинный код 704, отладил его и объявил результат в качестве интерпретатора LISPа, чем он, конечно, и являлся..."
После того, как идея была подана, ее осуществление не вызвало уже особых затруднений, так как в LISPе данные и программы представляются одинаково.
Рассмотрим ниже простой интерпретатор LISPа, запрограммированный на нем самом. Он, разумеется, отличается от интерпретаторов реальных систем. Тем не менее он дает довольно ясное представление о ядре интерпретатора и его работе, а также показывает, как легко и изящно семантика LISPа поддается определению и программированию и на других языках. В реализации интерепретатора будем использовать чисто функциональное программирование.
Определение того, как работает LISP, используя LISP как средство, в значительной степени аналогично тому, как в толковых словарях определяются слова в терминах других, предположительно более простых слов. Наш подход состоит в сведении языка LISP к некоторому числу основных функций, определения которых являются примитивами.
Пусть наш интерпретатор называется EVAL1 в отличие от интерпретирующего его системного интерпретатора EVAL. Соответственно назовем и интерпретируемые нами базовые функции: CAR1, CDR1, CONS1, EQUAL1 и ATOM1. Кроме того, будем использовать соответствующее предложению LAMBDA предложение LAMBDA1 и формы COND1 и QUOTE1.
T1, NIL1 и целые числа будут константами системы.
Во время вычисления предполагается, что вызываемые пользователем функции определены предложением LAMBDA1, которое является свойством FUN имени функции.
Предположим, что связи переменных хранятся в ассоциативном списке (A-списке) SWQZI.
Универсальную функцию EVAL1 можно определить следующим образом (учтите, что вначале SWQZI является пустым списком):
(DEFUN EVAL1 (LAMBDA (FORMA SWQZI)
(COND ( (ATOM FORMA) ; FORMA является атомом ;
(COND ( (EQ FORMA T1) T1 )
( (EQ FORMA NIL1) NIL1 )
( (NUMBERP FORMA) FORMA )
; Поиск в A-списке SWQZI значения ;
; атома FORMA ;
( (NULL (ASSOC FORMA SWQZI))
; Поиск в списке свойств ;
; значения свойства VALUE ;
; атома FORMA ;
(COND ( (NULL (GET FORMA VALUE))
FORMA )
( T (GET FORMA VALUE) ))
)
( T (CDR (ASSOC FORMA SWQZI)) )
)
)
; ---------------- ;
( (ATOM (CAR FORMA))
; Голова списка FORMA - атом ;
(COND ( (EQ (CAR FORMA) QUOTE1)
(CADR FORMA) )
; -------------------- ;
( (EQ (CAR FORMA) COND1)
(EVAL-COND (CDR FORMA) SWQZI) )
; --------------------------------- ;
( (EQ (CAR FORMA) SETQ1)
; Помещение значения атома ;
; (CAR FORMA) в список свойств ;
(PUT (CADR FORMA) VALUE
(CADDR FORMA)) )
; -------------------- ;
( (EQ (CAR FORMA) GETD1)
; Моделирование функции GETD ;
(GET (CADR FORMA) FUN)
)
; ---------------------------------- ;
; Вызов б а з и с н ы х функций: ;
; CAR1, CDR1, CONS1, ATOM1, EQUAL1, ;
; Вызов вспомогательных функций: ;
; PLUS1,DIFFERENCE1,TIMES1 ;
; GREATERP1,LESSP1 ;
; ---------------------------------- ;
( (MEMBER (CAR FORMA)
(QUOTE
(CAR1 CDR1 CONS1 ATOM1 EQUAL1
PLUS1 DIFFERENCE1 TIMES1
GREATERP1 LESSP1)
)
)
(APPLY1 (CAR FORMA)
(EVAL-SPISOK (CDR FORMA)
SWQZI)
SWQZI)
)
; --------------------- ;
( (EQ (CAR FORMA) DEFUN1)
; LAMBDA-определение помещается в ;
; список свойств ;
; в свойство FUN имени (CADR FORMA) ;
(PUT (CADR FORMA) FUN
(CADDR FORMA))
)
; ---------------- ;
; Создание макроса ;
( (EQ (CAR FORMA) DEFMACRO1)
; NLAMBDA-определение помещается в ;
; список свойств в свойство NFUN ;
; имени (CADR FORMA) ;
(PUT (CADR FORMA) NFUN
(LIST
NLAMBDA1
(CADR (CADDR FORMA))
(CADDR (CADDR FORMA))))
)
; -------------------------------- ;
; Вызов функции пользователя. ;
; Вызываемые пользователем функции ;
; определены предложением LAMBDA1, ;
; которое является свойством FUN ;
; имени функции ;
; -------------------------------- ;
( (GET (CAR FORMA) FUN)
; Функция GET возвращает значение ;
; свойства FUN имени (CAR FORMA) ;
; или NIL, если такого свойства нет ;
(APPLY1 (GET (CAR FORMA) FUN)
(EVAL-SPISOK (CDR FORMA)
SWQZI)
SWQZI)
)
; --------------------------------- ;
; Вызов функции пользователя. ;
; Вызываемые пользователем функции ;
; определены предложением NLAMBDA1, ;
; которое является свойством NFUN ;
; имени функции ;
; --------------------------------- ;
( (GET (CAR FORMA) NFUN)
(APPLY1
(GET (CAR FORMA) NFUN)
(NOT-EVAL-SPISOK (CDR FORMA))
SWQZI)
)
; ------------------------------ ;
( T (PRIN1 "Unknown function: ")
(PRINT (CAR FORMA)) )
)
)
; -------------------------------------------- ;
; FORMA - предложение вида: ;
; ((LAMBDA1 Формальные_параметры Тело_функции) ;
; Фактические_параметры) ;
; -------------------------------------------- ;
( (EQ (CAAR FORMA) LAMBDA1)
(APPLY1
(CAR FORMA)
(EVAL-SPISOK (CDR FORMA) SWQZI) SWQZI)
)
; --------------------------------------------- ;
; FORMA - предложение вида: ;
; ((NLAMBDA1 Формальные_параметры Тело_функции) ;
; Фактические_параметры ) ;
; --------------------------------------------- ;
( (EQ (CAAR FORMA) NLAMBDA1)
(APPLY1
(CAR FORMA)
(NOT-EVAL-SPISOK (CDR FORMA)) SWQZI)
)
; -------------------------- ;
( T (PRINT "Syntax error") )
)
))
Заметим, что при таком определении функции EVAL-COND, у предложений функции COND1 допускается лишь два элемента, т.е. COND1 допускает следующий синтаксис:
(COND1 ( (Условие1) (Предложение1) )
( (Условие2) (Предложение2) )
... ...
( (УсловиеN) (ПредложениеN) )
)
Далее, если FORMA - это список, первый элемент которого имя функции, то выражение можно вычислить, получив LAMBDA1-предложение, соответствующее имени функции, как свойство с именем FUN с помощью функции GET и применив его при помощи функции APPLY.
( (EQ (CAR FORMA) DEFUN1) ; Лямбда-определение помещается в список свойств ; (PUT (CADR FORMA) FUN (CADDR FORMA)) ) ; ---------------------------------------- ; ; Вызов функции пользователя. ; ; Вызываемые пользователем функции опреде- ; ; лены предложением LAMBDA1, которое явля- ; ; ется свойством FUN имени функции ; ; ---------------------------------------- ; ( (GET (CAR FORMA) FUN) ; Функция GET возвращает значение ; ; свойства FUN имени (CAR FORMA) ; ; или NIL, если такого свойства нет ; (APPLY1 (GET (CAR FORMA) FUN) (EVAL-SPISOK (CDR FORMA) SWQZI) SWQZI) )
До сих пор мы объясняли довольно поверхностно, почти неряшливо, что в действительности происходит, когда функция получает определение и используется. Было сказано, что описания функций каким-то образом запоминаются, каким-то образом извлекаются и каким-то образом применяются к аргументам. Теперь мы уточнили это описание, чтобы показать работу LISPа на более глубоком уровне.
Мы подробно рассмотрели, что делает LISP, когда сталкивается с функцией, определенной пользователем: интерпретатор обращается к списку свойств за лямбда-определением.
FORMA может быть непосредственно LAMBDA1-вызовом с фактическими параметрами
( (LAMBDA1 Формальные параметры Тело) Фактические параметры )
Эту ситуацию обрабатывает последняя ветвь EVAL1.
; ----------------------------------------------- ; ; FORMA - предложение вида: ; ; ( (LAMBDA1 Формальные_параметры Тело_функции) ; ; Фактические_параметры ) % ; ----------------------------------------------- ; ( (EQ (CAAR FORMA) LAMBDA1) (APPLY1 (CAR FORMA) (EVAL-SPISOK (CDR FORMA) SWQZI) SWQZI) )
Функция APPLY1 "применяет" функции к значениям аргументов. С ее помощью определены также базовые функции интерпретатора: CAR1, CDR1, CONS1, ATOM1, EQUAL1 и LAMBDA1-предложение.
(DEFUN APPLY1 (LAMBDA (FUNCT ARGUMENTS SWQZI) ; Функция возвращает результат применения функции ; ; FUNCT к аргументам ARGUMENTS ; (COND ( (ATOM FUNCT) ; FUNCT - атом ; (COND ( (EQ FUNCT CAR1) (COND ( (EQ (CAR ARGUMENTS) NIL1) NIL1 ) ( T (CAAR ARGUMENTS) )) ) ; ------------- ; ( (EQ FUNCT CDR1) (COND ( (EQ (CAR ARGUMENTS) NIL1) NIL1 ) ( (NULL (CDAR ARGUMENTS)) NIL1 ) ( T (CDAR ARGUMENTS) )) ) ; -------------- ; ( (EQ FUNCT CONS1) (COND ( (EQ (CADR ARGUMENTS) NIL1) (LIST (CAR ARGUMENTS)) ) ( T (CONS (CAR ARGUMENTS) (CADR ARGUMENTS))) ) ) ; -------------- ; ( (EQ FUNCT ATOM1) (COND ( (ATOM (CAR ARGUMENTS)) T1 ) ( T NIL1) ) ) ; --------------- ; ( (EQ FUNCT EQUAL1) (COND ( (EQUAL (CAR ARGUMENTS) (CADR ARGUMENTS)) Т1 ) ( T NIL1 )) ) ; -------------- ; ( (EQ FUNCT PLUS1) (+ (CAR ARGUMENTS) (CADR ARGUMENTS)) ) ; -------------------- ; ( (EQ FUNCT DIFFERENCE1) (- (CAR ARGUMENTS) (CADR ARGUMENTS)) ) ; --------------- ; ( (EQ FUNCT TIMES1) (* (CAR ARGUMENTS) (CADR ARGUMENTS)) ) ; ------------------ ; ( (EQ FUNCT GREATERP1) (COND ( (GREATERP (CAR ARGUMENTS) (CADR ARGUMENTS)) T1 ) ( T NIL1 )) ) ; --------------- ; ( (EQ FUNCT LESSP1) (COND ( (LESSP (CAR ARGUMENTS) (CADR ARGUMENTS)) T1 ) ( T NIL1 )) ) ; ----------------------------- ; ( T (APPLY1 (EVAL1 FUNCT SWQZI) ARGUMENTS SWQZI) ) ) ) ; ---------------------- ; ( (EQ (CAR FUNCT) LAMBDA1) (EVAL1 (CADDR FUNCT) (SOZDAI-SWQZI (CADR FUNCT) ARGUMENTS SWQZI)) ) ; ----------------------- ; ( (EQ (CAR FUNCT) NLAMBDA1) (EVAL1 (CADDR FUNCT) (SOZDAI-SWQZI (CADR FUNCT) ARGUMENTS SWQZI)) ) ; -------------------------- ; ( T (PRINT "Syntax error") ) ) ))
Функция FUNCT должна быть либо известной интерпретатору базовой функцией, либо более сложным вычислением, определенным через выражение LAMBDA1.
Функцией SOZDAI-SWQZI в окружение OKRUGENIE добавляются связи формальных параметров с фактическими:
(DEFUN SOZDAI-SWQZI (LAMBDA (FORMAL FACTICH OKRUGENIE)
; Заполнение ассоциативного списка A связей OKRUGENIE ;
(COND
( (NULL FORMAL) OKRUGENIE )
( (NULL FACTICH) OKRUGENIE )
( T (ACONS (CAR FORMAL) (CAR FACTICH)
(SOZDAI-SWQZI
(CDR FORMAL) (CDR FACTICH)
OKRUGENIE)) )
)
))
Вторым аргументом APPLY - ARGUMENTS - является список значений аргументов вызываемой функции, который вычисляется функцией EVAL-SPISOK:
(DEFUN EVAL-SPISOK (LAMBDA (NEWYCHISL SWQZI) ; Вычисление списка значений аргументов ; ; вызываемой функции ; (COND ( (NULL NEWYCHISL) NIL ) ( T (CONS (EVAL1 (CAR NEWYCHISL) SWQZI) (EVAL-SPISOK (CDR NEWYCHISL) SWQZI)) ) ) ))
Заметим, что интерпретатор языка LISP образуется в основном двумя взаимно рекурсивными функциями EVAL1 и APPLY1, через которые семантика языка получила формальное определение.
Теперь запрограммируем цикл диалога нашего интерпретатора LISP. В приведенном ниже определении в качестве приглашения интерпретатора будем использовать символ "<--". Кроме этого признаком выводимых результатов будет символ "-->".
(DEFUN muLISP (LAMBDA NIL
; Диалог с пользователем '
(PRINT "Учебный muLISP-92 1.01 (06/10/92)")
(PRINT
"Copyright (C) McCarthy & Hyvonen & Seppanen & RGPU")
(TERPRI) (PRIN1 " <-- ")
( LOOP
(SETQ EXPRESSION (READ))
( (EQUAL EXPRESSION (LIST SYSTEM1)) 'BYE-BYE )
(PRIN1 " --> ") (PRINT (EVAL1 EXPRESSION NIL))
(PRIN1 " <-- ")
)
))
(1) McCarthy J., Abrahams P.W., Edwards J., Hart T.P., Levin M.I. LISP 1.5 Programmer's Manual. - M.I.T. Press, Cambridge, Massachusetits, 1965.
(2) Пратт Т. Языки программирования. Разработка и реализация. - М.: Мир, 1979. - 574 с.
(3) Хювенен Э., Сеппянен Й. Мир Лиспа. В 2-х т. Т.2: Методы и системы программирования. - М.: Мир, 1990. - 319 с.
(4) Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2-х ч. Ч.1. пер. с нем. - М.: Мир, 1990. - 336 с.; Ч.2. пер. с нем. - М.: Мир, 1990. - 423 с.
На следующем шаге мы приведем текст учебного интерпретатора LISP на muLISPe.
