Дополнительные команды АМ для эффективной поддержки отложенных выражений

Команда	Пояснение
LDE	Загрузка отложенного выражения с созданием рецепта
RPL	Замена рецепта его результатом
APN	Возобновление отложенного выражения

Вычисляться такими командами рецепт может не более чем один раз, и то если его результат действительно нужен.

Таблица 29

Дополнение АМ для эффективного выполнения отложенных действий

Команда	Результат
s e (LDE f. c) d	→ ([F (f. e)]. s) e c d
(x) e (RPL) ([F (F. e)] ee c. d)	→ (x. s) ee c d при этом ([F (F. e)] → [T x] 17
([T x]. s) e (APN. c) d	→ (x.s) e c d
([F (f. e)]. s) ee (APN. c) d	→ Nil e f ([F (F. e)] ee c. d)

Эффект отложенных вычислений можно продемонстрировать на обра- ботке бесконечных структур данных, в которых продолжение структуры представлено как вычисление следующих элементов. Включение в квадрат- ные скобки «[ ]» здесь символизирует размещение по тому же адресу.

 

Фрагмент	Примечание
(def beg (LAMBDA (k lst) (cond ((EQ k Nil)()) (T (cons (car lst) (beg (cdr k) (eval (cons (cdr lst) Nil)) ))) ))) (def endless (LAMBDA (m) (cons m (lambda () (endless (cons m m)))) )      ) (beg '(a b c) (endless 'A)) ; = (A (A. A) ((A. A) A. A))	Вырезка начального отрезка

Пример 25. Конструирование последовательности произвольной длины из бесконечного списка

Все это выполнимо уже на базе интерпретатора языка Pure Lisp.

 

 

Свойства атомов

Методы расширения функциональных построений могут быть приме- нены для моделирования привычного императивно-процедурного стиля про- граммирования и техники работы с глобальными определениями. Здесь де- монстрируется расширение базовой схемы обработки символьных выраже- ний и представленных с их помощью функциональных форм на примере механизма списков свойств атомов. В результате можно собирать функцио- нально полное определение гибкой и расширяемой реализации языка про- граммирования, что и показано на примере Lisp-интерпретатора, написанном на Lisp-е.

До сих пор атом рассматривался только как уникальный указатель, обес- печивающий быстрое выяснение различимости имен, названий или симво- лов. Теперь описываются списки свойств, которые начинаются или нахо- дятся в указанных ячейках. Каждый атом имеет список свойств. Когда атом читается (вводится) впервые, тогда для него создается пустой список свойств, который потом можно заполнять. Список свойств устроен как специальная структура, подобная записям в Паскале или структурам в Си, но указатели в такой записи сопровождаются тэгами, символизирующими тип хранимой информации. Первый элемент этой структуры расположен по адресу, кото- рый задан в указателе. Остальные элементы доступны по этому же указателю с помощью ряда специальных функций. Элементы структуры содержат раз- личные свойства атома. Каждое свойство помечается атомом, называемым индикатором, или расположено в фиксированном поле структуры. Свойства могут быть системными или программируемыми.

Здесь достаточно принять к сведению, что реализация атомарных объек- тов – это сложная структура данных, в свою очередь представленная спис- ками – встроенная база данных.

С помощью функции GET в форме (GET x i) можно найти для атома x свойство, индикатор которого равен i.

Значением

(GET 'FF 'EXPR)

будет

(LAMBDA  (X) (COND  …)),

если определение FF было предварительно задано с помощью (DEFUN FF (X)(COND...)).

Свойство с его индикатором может быть вычеркнуто – удалено из списка функцией REMPROP в форме (REMPROP x i).

С середины 1970-х годов возникла тенденция повышать эффективность разработкой специальных структур, отличающихся в разных реализациях.

 

 

Существуют реализации, например, muLisp, допускающие работу с представ- лениями атома как с обычными списками посредством функций CAR, CDR.

 

Гибкий интерпретатор

В качестве примера повышения гибкости определений приведено упро- щенное определение Lisp-интерпретатора на Lisp-е, полученное из М-выра- жения²², приведенного Дж. Маккарти в описании Lisp 1.5 [22].

 

Определение	Примечание
(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 (caddr fn) (pairlis (cadr fn) x a))) ((eq (car fn) 'LABEL) (apply (caddr fn) x (cons (cons (cadr fn)(caddr fn)) a)))))	Элементарные функции.     Программируемые функции. Безымянная функция. Именованная функция.
(DEFUN evcon (c a) (COND ((eval (car c) a) (eval (cadr c) a)) (T (eval (caddr c) a))))	Выбор ветви.
(DEFUN evlis (m a) (COND ((null m) Nil) (T    (cons(eval (car m) a) (evlis(cdr m) a))) )	Вычисление параметров

Пример 26. Самоописание Lisp-интерпретатора, предложенное Дж. Маккарти в начале 1960-х годов

22 Предварительный синтаксис языка Lisp, выглядящий как обычной язык программи- рования, отображаемый в круглоскобочное представление списков.

 

 

Ради удобочитаемости здесь уменьшена диагностичность, нет пост-вы- числений и формы PROG. Lisp хорошо приспособлен к оптимизации про- грамм. Любые совпадающие подвыражения можно локализовать и вынести за скобки, как можно заметить по передаче значения.

Определения функций хранятся в ассоциативном списке, как и значения переменных.

Функция SUBR – вызывает примитивы, реализованные другими, обычно низкоуровневыми, средствами.

ERROR – выдает сообщения об ошибках и сведения о контексте вычис- лений, способствующие поиску источника ошибки. Уточнена работа с функ- циональными аргументами.

 

Определение	Примечание
(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 'CLOSURE (CADR fn) al)) ((EQ (CAR e) 'COND) (EVCON (CDR e) al)) (T (apply (CAR e)(evlis (CDR e) al) al)) ))	Диагностика. Однократность вычисления значения.     Замыкание функциональ- ного аргумента

Пример 27. Диагностика отсутствия определений при вычислении форм

 

Определения функций могут содержать свободные переменные, порож- дающие так называемую FunArg-проблему при вызове в разных контекстах. Решение строится с помощью замыканий, фиксирующих выбор значений пе- ременных.

 

 

Определение	Примечание
(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) ' CLOSURE) (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)) ))	Применение функцио- нального аргумента с помомщью замыка- ния

Пример 28. Применение подпрограмм и функциональных параметров

 

Определения ASSOC, APPEND, PAIR, LIST, MEMBER – стандартны.

 

Определение	Примечание
(DEFUN evcon (c a) (COND ((evel (car c) a) (evel (cadr c) a)) (с (evcon (caddr c) a))))	Возможно отсутствие ветви – пока c не пуст

Пример 29. Выбор ветви, допускающий отсутствие истинного предиката

 

Определение	Примечание
(DEFUN evlis (m a) (COND (m (cons(evel (car m) a)   (evlis(cdr m) a) )) ))	Пока «M» не пуст, присоединяем значение его первого элемента к списку значений остальных элементов

Пример 30. Вычисление параметров в стиле Clisp