ЯП с общим АС семантически эквивалентны, они сравнимы по тру- доемкости отладки программ.

Различают два стиля задания семантики ЯП – семантика вычисления зна- чений и семантика изменения состояний памяти. Основой определения ин- терпретатора для семантики вычисления значений языка Lisp является функ- ция EVAL (evaluation), вычисляющая произвольные выражения языка с уче- том контекста – таблицы атомов ТА, устроенной как стек (более точно будет определена при описании семантики ФП). Для семантики изменения состоя- ний памяти функция языка Pascal EXEC (execution) выполняет ту же работу на базе контекста из двух устроенных как векторы таблиц TA и TF, раздельно хранящих значения переменных и определения процедур, соответственно (более точно будет определена при описании семантики ЯП).

 

 

Универсальная функция, или интерпретация – это функция, которая мо- жет вычислять значение любой формы, включая формы, сводимые к вычис- лению любой заданной функции, применяемой к аргументам, представлен- ным в этой же форме, по доступному описанию данной функции. (Конечно, если функция, которой предстоит интерпретироваться, имеет бесконечную рекурсию, интерпретация будет повторяться бесконечно.)

Рассмотрим универсальную функцию EVAL от аргумента expr. Это вы- ражение, являющееся произвольной вычислимой формой языка Lisp. Такая универсальная функция должна предусматривать основные виды вычисляе- мых форм, задающих значения аргументов, а также представления функций в соответствии со сводом правил языка. При интерпретации выражений учи- тываются следующие решения, представленные при определении АС:

– атом обычно понимается как переменная. Для него следует найти зна- чение, связанное с ним в ТА. Например, могут быть переменные вида x, elem, смысл которых зависит от контекста, в котором они вычисляются;

– константы, представленные как аргументы функции QUOTE, можно просто извлечь из списка ее аргументов. Например, значением константы (QUOTE T) является атом T, обычно символизирующий значение «истина»;

– условное выражение требует специального алгоритма для перебора пре- дикатов и выбора нужной ветви;

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

– если функция представлена своим названием, то среди названий разли- чаются имена встроенных элементарных функций, такие как CAR, CDR, CONS и т. п., и имена функций, введенных в программе;

– для встроенных функций интерпретация сама «знает», как найти их зна- чение по заданным аргументам, а для функций, введенных в программе, ис- пользует их определение, которое находит подобно переменной по имени в таблице атомов ТА – в контексте⁷;

– если функция построена с помощью λ-конструктора, то, прежде чем ее применять, понадобится связывать переменные из λ-списка параметров со значениями аргументов;

– если представление функции начинается с DEFUN, то понадобится со- хранить имя функции с соответствующим ее определением в ТА так, чтобы корректно выполнялись рекурсивные вызовы функции. Определения функ-

 

7 Похоже на резервированные слова, но в реальных СП все функции (более тысячи) равноправно являются встроенными функциями.

 

 

ций накапливаются в «хвосте» стека – контекста, представленного системной переменной ТА, т. е. работают как глобальные определения.

Таким образом, интерпретация выражений осуществляется как взаимо- действие четырех прикладных семантик:

– обработка структур данных (cons, car, cdr, atom, eq);

– конструирование функциональных объектов (lambda);

– идентификация объектов (список параметров, таблица атомов, defun);

– управление логикой вычислений и частичными вычислениями (компо- зиции, quote, cond, eval).

Идентификация и управление отчасти привязаны к синтаксическим пози- циям без специальной лексики («синтаксический сахар»). В большинстве ЯП аналоги первых двух подсистем нацелены на обработку элементарных дан- ных и конструирование составных значений, кроме того, иначе установлены границы между подсистемами.

Явное определение универсальной функции позволяет достичь четкости механизмов обработки Lisp-программ.

При написании на демонстрационном подмножестве языка Lisp опреде- ления функции EVAL, согласно приведенной выше спецификации, задается переход от данного списочного представления выражения E к его значению с учетом заданной таблицы атомов ТА, хранящей значения атомов.

Универсальная функция EXEC для минимального подмножества языка Pascal немного отличается от EVAL:

– атом понимается как переменная или константа;

– константы строятся из так называемых литералов и могут быть поиме- нованы;

– условное выражение состоит из предиката и двух позиций для выбора нужной ветви;

– существуют специальные формы для циклов, определения и вызова процедур и функций и другие схемы управления вычислениями;

– выражения обрабатываются с учетом таблицы приоритетов операций и расстановки скобок;

– определения переменных и функций или процедур хранятся раздельно.

Основные различия:

– EXEC не поддерживает безымянные функции;

– EVAL не поддерживает присваивания глобальным переменным, пред- почитает локальное связывание имен и значений;

– EXEC поддерживает раздельное хранение значений и определений функций/процедур;

– EVAL допускает конструирование определений функций подробно лю- бым данным в процессе вычислений.

 

 

Абстрактная машина

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

АМ различает обычно следующие категории команд:

– засылка значений из памяти в стек;

– вычисления над безымянными операндами в стеке при обработке выра- жений;

– пересылка значений из стека в память с учетом локализации;

– организация ветвлений и циклов;

– организация вызовов процедур и функций с сохранением/восстановле- нием контекста.

Могут быть и другие категории команд.

При сравнении императивного и функционального подходов к програм- мированию с цель создания Lisp-процессора, П. Лэндин (P. J. Landin) пред- ложил специальную абстрактную машину SECD, удобную для специфика- ции машинно-зависимых аспектов семантики Lispа. Подробное описание этой машины можно найти в книге Хендерсона по функциональному про- граммированию [15].

Машина SECD работает над четырьмя независимыми регистрами произ- вольного объема: стек для промежуточных результатов, контекст для разме- щения именованных значений, управляющая вычислениями программа, ре- зервная память (Stack, Environment, Control list, Dump). Регистры приспособ- лены для хранения выражений в форме атомов или списков. Состояние машины полностью определяется содержимым этих регистров. Поэтому функционирование машины можно описать достаточно точно в терминах из- менения содержимого регистров при выполнении команд, что выражается следующим образом:

s e c d → s' e' c' d' – переход от старого состояния к новому.

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

 

 

мируемые функции. Компилятор по исходному тексту программы строит код программы, эквивалентный тексту.

Для характеристики встроенных команд интерпретатора и результата компиляции программ БС языка Lisp понадобятся следующие команды:

LD – ввод данного из контекста в стек;

LDC – ввод константы из программы в стек; LDF – ввод определения функции в стек;

AP – применение функции, определение которой уже в стеке;

RTN – возврат из определения функции к вызвавшей ее программе; RAP – применение рекурсивной функции;

DUM – резервирование памяти для хранения состояний при ветвлениях и вызовах функции;

SEL – ветвление в зависимости от активного (верхнего) значения стека; JOIN – переход к общей точке после ветвления;

CAR – первый элемент из активного значения стека; CDR – без первого элемента активное значение стека;

CONS – формирование узла по двум верхним значениям стека; ATOM – неделимость (атомарность) верхнего элемента стека; EQ – равенство двух верхних значений стека;

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 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. b). s) e (ATOM. c) d     → (NIL. s) e c d

(A. s) e (ATOM. c) d     → (T. s) e c d

Для неатомарных значений – NIL,., т. е. ложь, истина «Т» – для атомов. (a a. s) e (EQ. c) d       → (T. s) e c d

(a b. s) e (EQ. c) d     → (NIL. s) e c d

Истина «Т» – для совпадающих указателей, для несовпадающих – NIL, т. е. ложь.

Для доступа к значениям, расположенным в контексте, можно определить специальную функцию N-th, выделяющую из списка элемент с заданным но- мером N в предположении, что длина списка превосходит заданный адрес:

s e (LD n. c) d → (x. s) e c d

x – это значение (N-th n e).

При реализации ветвлений управляющая программа соответствует следу- ющему шаблону:

(... SEL (... JOIN) (... JOIN)...)

Ветви размещены в подсписках с завершителем JOIN, после которых сле- дует общая часть вычислений. Для большей надежности на время выполне- ния ветви общая часть сохраняется в дампе – резервной памяти, а по завер- шении ветви – восстанавливается в регистре управляющей программы:

(NIL. s) e (SEL c1 c0. c) d → s e c0 (c. d) (T. s) e (SEL c1 c0. c) d → s e c1 (c. d)

s e (JOIN) (c. d) → s e c d

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

Завершается процедура командой 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 – результат функции.

Рекурсивные вызовы функций требуют резервирования памяти для уни- кальных ссылок на разные поколения фактических аргументов, что достига- ется путем размещения фиктивного объекта «ω», который функция rplaca, в порядке исключения, замещает на реальные данные:

s e (DUM. c) d → s (ω. e) c d

((f. ef) vf. s) e (RAP. c) d → NIL (rplaca vf ef) f (s e c. d)

Поэтому для SECD реализационное замыкание ядра языка Lisp включает в себя структуро-разрушающие функции rplaca и rplacd, размещающие свой результат непосредственно в памяти второго аргумента. Это требует соответ- ствующих ветвей в определениях синтаксиса и интерпретатора, что можно рассматривать как шаг раскрутки СП.

Таблица 7