Интерпретирующая система. Реализационное уточнение интерпретации
Эта глава предназначена для реализационного уточнения уже известных теоретических рассуждений. Ряд уточнений показан на примере, представляющем программу, которая определяет три функции union, intersection и member, а затем применяет эти функции к нескольким тестам [1]. На этом примере будут рассмотрены средства и методы, обеспечивающие удобочитаемость функциональных программ и удобство их развития при отладке. Как правило, удобство достигается включением в систему дополнительных функций для решения проблем, принципиальное решение которых уже обеспечено на уровне теории.
Функции union и intersection применяют к множествам, каждое множество представлено в виде списка атомов. Заметим, что все функции рекурсивны, а union и intersection используют member. Схематично работу этих функций можно выразить следующим образом:
member = lambda [a;x] [ null[x] ==>> Nil ] [ eq[a;car[x]] ==>> T ] [ T ==>> member[a;cdr[x]] ]
union = lambda[x;y] [ null[x] ==>> y ] [ member[car[x];y] ==>> union[cdr[x];y] ] [ T ==>> cons[car[x];union[cdr[x];y]] ]
intersection = lambda [x;y] [ null[x] ==>> NIL ] [ member[car[x];y] ==>> cons[car[x];intersection[cdr[x];y]] ] [ T ==>> intersection[cdr[x];y] ]
Определяя эти функции на Лиспе, мы используем дополнительную псевдо-функцию DEFUN, объединяющую эффекты lambda и label. Программа выглядит так:
(DEFUN MEMBER (A X) (COND ((NULL X) Nil) ((EQ A (CAR X)) T) (T (MEMBER A (CDR X)) ) ) )
(DEFUN UNION (X Y) (COND ((NULL X) Y) ((MEMBER (CAR X) Y) (UNION (CDR X) Y) ) (T (CONS (CAR X) (UNION (CDR X) Y))) )) ) ) )
(DEFUN INTERSECTION (X Y) (COND ((NULL X) NIL) ((MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECTION (CDR X) Y)) ) (T (INTERSECTION (CDR X) Y)) ) )
(INTERSECTION '(A1 A2 A3) '(A1 A3 A5)) (UNION '(X Y Z) '(U V W X))
Эта программа предлагает вычислить пять различных форм.
Первые три формы сводятся к применению псевдо-функции DEFUN.
Псевдо-функция — это функция, которая выполняется ради ее воздействия на систему, тогда как обычная функция — ради ее значения.
DEFUN заставляет функции стать определенными и допустимыми в системе равноправно со встроенными функциями. Ее значение — имя определяемой функции, в данном случае — member, union, intersection. Более точно можно сказать, что полная область значения псевдо-функции DEFUN включает в себя некоторые доступные ей части системы, обеспечивающие хранение информации о функциональных объектах, а формальное ее значение — атом, символизирующий определение функции.
Значение четвертой формы — (A1 A3). Значение пятой формы — (Y Z C B D X). Анализ пути, по которому выполняется рекурсия, показывает, почему элементы множества появляются именно в таком порядке.
В этом примере продемонстрировано несколько элементарных правил написания функциональных
программ, сложившихся при реализации интерпретатора Лисп 1.5 в дополнение к идеализированным правилам, сформулированным в строгой теории Лиспа. (С точностью до разницы между EVALQUOTE — EVAL.)
Программа состоит из последовательности вычисляемых форм. Если форма список, то ее первый элемент интерпретируется как функция. Остальные элементы списка — аргументы для этой функции. Они вычисляются с помощью EVAL, а функция применяется к ним с помощью APPLY, и полученное значение выводится как результат программы.- Особого формата для записи программ не существует. Границы строк игнорируются. Формат программы, включая идентификацию, выбран просто для удобства чтения.
- Любое число пробелов и концов строк можно разместить в любой точке программы, но не внутри атома.
- Не используются (QUOTE T), (QUOTE NIL). Вместо них применяется T, NIL, что влечет за собой соответствующее изменение определения EVAL.
- Атомы должны начинаться с букв, чтобы их можно было легко отличать от чисел.
- Может использоваться точечная нотация. Любое число пробелов перед или после точки, свыше одного, будет игнорироваться (один пробел нужен обязательно при соседстве с атомом).
- Точечные пары могут появляться как элементы списка, и списки могут быть элементами точечных пар.
((A . B) X (C . (E F D))) — есть допустимое S-выражение. Оно может быть записано как
((A . B) . ( X . ((C . (E . ( F . (D . Nil)))) . Nil)))
или
((A . B) X (C E F D)) - Форма типа (A B C . D) есть сокращение для (A . ( B . ( C . D) )). Любая другая расстановка точек на одном уровне есть ошибка, например (A. B C).
- Набор основных функций предоставляется системой. Другие функции могут быть введены программистом. Порядок введения функций не имеет значения. Любая функция может использоваться в определении другой функции.
Вывод S-выражений на печать и в файлы выполняет псевдо-функция print, чтение данных обеспечивает псевдо-функция read. Программа из файла может быть загружена
псевдо-функцией load.
(PRINT (INTERSECTION '(A1 A2 A3) '(Al A3 A5)) ) (PRINT (UNION '(X Y Z) '(U V W X)) ) (PRINT (UNION (READ) '(1 2 3 4)) ) ; объединение вводимого списка со списком ; '(1 2 3 4)
