Абстрактная Лисп-машина. Система команд
Встраиваемые в ядро интерпретатора операции должны соответствовать стандартным правилам доступа к параметрам и размещения выработанного результата. Таким же правилам должен подчиняться и компилируемый код. Это позволяет формально считать равноправными встроенные и программируемые функции. Компилятор по исходному тексту программы строит код программы, эквивалентный тексту. Особенности процесса компиляции достаточно сложны даже для простых языков, поэтому характеристика результата компиляции часто задается в терминах языково-ориентированных абстрактных машин. Такой подход полезен для решения ряда технологических проблем разработки программных систем (мобильность, надежность, независимость от архитектур и т.п.).
При сравнении императивного и функционального подходов к программированию, П.Лэндин (P.J.Landin) предложил специальную абстрактную машину SECD, удобную для спецификации машинно-зависимых аспектов семантики Лиспа. Подробное описание этой машины можно найти в книгах Хендерсона и Филда-Харрисона по функциональному программированию [3, 4].
Машина SECD работает над четырьмя регистрами: стек для промежуточных результатов, контекст для размещения именованных значений, управляющая вычислениями программа, резервная память (Stack, Environment, Control list, Dump). Регистры приспособлены для хранения выражений в форме атомов или списков. Состояние машины полностью определяется содержимым этих регистров. Поэтому функционирование машины можно описать достаточно точно в терминах изменения содержимого регистров при выполнении команд, что выражается следующим образом:
s e c d => s' e' c' d' — переход от старого состояния к новому.
Для характеристики встроенных команд Лисп-интепретатора и результата компиляции программ базового Лиспа понадобятся следующие команды:
LD — ввод данного из контекста в стек;
LDC — ввод константы из программы в стек;
LDF — ввод определения функции в стек;
AP — применение функции, определение которой уже в стеке;
RTN — возврат из определения функции к вызвавшей ее программе;
SEL — ветвление в зависимости от активного (верхнего) значения стека;
JOIN — переход к общей точке после ветвления;
CAR — первый элемент из активного значения стека;
CDR — без первого элемента активное значение стека;
CONS — формирование узла по двум верхним значениям стека;
ATOM — неделимость (атомарность) верхнего элемента стека;
EQ — равенство двух верхних значений стека;
SUB1 — вычитание 1 из верхнего элемента стека;
ADD1 — прибавление 1 к верхнему элементу стека;
STOP — останов.
Стек устроен традиционно по схеме "первый пришел, последний ушел". Каждая команда абстрактной машины "знает" число используемых при ее работе элементов стека, которые она удаляет из стека и вместо них размещает выработанный результат. Исполняются команды по очереди, начиная с первой в регистре управляющей программы. Машина прекращает работу при выполнении команды "останов", которая формально характеризуется отсутствием изменений в состоянии машины:
s e (STOP ) d -> s e (STOP ) d
Следуя Хендерсону, для четкого отделения обрабатываемых элементов от остальной части списка будем использовать следующие обозначения: (x . l ) — это значит, что первый элемент списка — x, а остальные находятся в списке l.
(x y . l ) — первый элемент списка — x, второй элемент списка — y, остальные находятся в списке l и т.д. Теперь мы можем методично описать эффекты всех перечисленных выше команд.
s e(LDC q . c)d -> (q . s) e c d (a . s)e(ADD1 . c)d -> (a+1 . s) e c d (a . s)e(SUB1 . c)d -> (a-1 . s) e c d (a b . s)e(CONS . c)d -> ((a . b) . s) e c d ((a . b) . s)e(CAR . c) -> (a . s) e c d ((a . b) . s)e(CDR . c) -> (b . s) e c d (a . s)e(ATOM . c)d -> (t . s) e c d (a b . s)e(EQ . c)d -> (t . s) e c d
где t — логическое значение.
Для доступа к значениям, расположенным в контексте, можно определить специальную функцию N-th, выделяющую из списка элемент с заданным номером N в предположении, что длина списка превосходит заданный адрес.
(DEFUN N-th (n list ) (COND ((EQ n 0 )(CAR list )) (T (N-th (SUB1 n ) (CDR list ) )) ))
Продолжаем описание команд Лисп-машины.
s e (LD n . c) d -> (x . s) e c d
где x — это значение (N-th n e )
При реализации ветвлений управляющая программа соответствует следующему шаблону:
( ... SEL ( ... JOIN ) ( ... JOIN ) ... )
Ветви размещены в подсписках с завершителем JOIN, после которых следует общая часть вычислений. Для большей надежности на время выполнения ветви общая часть сохраняется в дампе — резервной памяти, а по завершении ветви — восстанавливается в регистре управляющей памяти.
(t . s) e (SEL c1 c0 . c) d -> s e ct (c . d) s e (JOIN ) (c . d) -> s e c d
где ct — это c1 или c0 в зависимости от истинностного значения t.
Организация вызова процедур требует защиты контекста от локальных изменений, происходящих при интерпретации тела определения. Для этого при вводе определения функции в стек создается специальная структура, содержащая код определения функции и копию текущего состояния контекста. До этого в стеке должны быть размещены фактические параметры процедуры. Завершается процедура командой RTN, восстанавливающей регистры и размещающей в стеке результат процедуры.
s e (LDF f . c) d -> ((f . e) . s) e c d ((f . ef) vf . s) e (AP . c) d -> NIL (vf . ef) f (s e c . d) (x) e (RTN ) (s e c . d) -> (x . s) e c d
где f — тело определения, ef — контекст в момент вызова функции, vf — фактические параметры для вызова функции, x — результат функции.
Упражнение 7.1. Программа имеет вид:
(LD 3 ADD1 LDC 128 EQ STOP)
Напишите последовательность состояний стека при работе программы и сформулируйте, что она делает.
Ответ: Данная программа проверяет, меньше ли на 1 значение, хранящееся в контексте по адресу 3, чем заданная в программе константа 128. При ее работе стек проходит следующие состояния:
NIL (3 ) (4 ) (128 4 ) (NIL )
Упражнение 7.2. Напишите управляющую программу, дающую результат, эквивалентный следующим выражениям:
(CADR e ) (EQ (CAR e) 'QUOTE ) (COND ((EQ n 0 )(CAR l )) (T (CONS (SUB1 n ) (CDR l ))) )
(Адреса значений e, n, l можно обозначить как @e, @n, @l, соответственно.)
Ответ:
( LD @e CDR CAR ) ( LD @e CAR LDC QUOTE EQ ) ( LD @n LDc 0 EQ SEL (LD @l CAR JOIN) (LD @n SUB1 LD @l CDR CONS JOIN) )
Упражнение 7.3. Напишите спецификацию команды SET, сохраняющей активное значение стека в контексте по заданному в программе адресу в предположении, что длина списка превосходит заданный адрес.
Ответ: Нужна функция, заменяющая в списке указанный старый элемент новым.
(DEFUN ASS (e n list ) (COND ((EQ n 0 )(CONS e (CDR l )) ) (T (CONS (CAR l ) (ASS e (SUB1 n ) (CDR l ) ) ) ) ) )
Тогда можно описать команду SET следующим образом:
(x . s) e (SET n . c) d -> s xne c d ``
где xne = (ASS x n e) — новое состояние контекста.
