Расширение Pure Lisp и SECD средствами обработки чисел

	Новая конструкция	Значение	Примечание
Лексика	Number = digit {digit}	целое	Новая область данных
Синтаксис	атом = Number		Встраивание новой обла- сти в систему понятий ЯП
Семантика	(SUM x y)	(x + y)	Добавление операций над новыми данными
	(DIF x y)	(x – y)
	(MUL x y)	(x * y)
	(DIV x y)	(x / y)
	(ADD1 x y)	(x + 1)
	(MIN1 x y)	(x – 1)
	(NUMBER x)	NIL или T	Предикат, выделяющий числа

При разработке и реализации компиляторов для своих ЯП Pascal, Oberon, Modula и других Николас Вирт создал АМ, названную Пи-код, содержащую сле- дующие команды (выше названа SECM для сопоставления с SECD):

LD – ввод данного из контекста в стек промежуточных значений; LDC – ввод константы из программы в стек;

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

STW – сохранение значения в глобальной памяти; STE – сохранение значения в локальном контексте;

RET – возврат из процедуры к вызвавшей ее программе;

IF – ветвление в зависимости от активного (верхнего) значения стека; EQ – равенство двух верхних значений стека;

LT – верхнее значение в стеке меньше, чем второе; INC – увеличение числа на 1;

DEC – уменьшение числа на 1;

SUB – вычитание из верхнего элемента стека; ADD – прибавление к верхнему элементу стека; MUL – произведение двух чисел;

DIV – частное от деления верхнего элемента стека на второй элемент; BR – безусловная передача управления по абсолютному адресу;

AP – применение процедуры к аргументам, расположенным в стеке; STOP – останов.

Для реализации компилятора АМ расширена добавлением экстракодов ввода-вывода:

WR – вывод значения из памяти на внешнее устройство; RD – ввод значения в память из внешнего устройства.

 

 

При таком расширении система программирования становится системой с обратной связью, что делает ее более пригодной для отладки. СП создается не просто над процессором, а над комплексом из процессора и операционной системы. Следует отметить, что в первых ЯП, таких как Fortran, Lisp, APL, Setl и других, средства ввода-выводы представлялись как неотъемлемая кон- струкция языка, а в более поздних, таких как Algol, Pascal, C, - включаются как библиотечные модули.

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

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

Теперь мы можем методично описать эффекты всех перечисленных выше команд.

s e (LDC q. c) m p                                       → (q. s) e c m p

(a. s) e (INC. c) m p                                   → (a+1. s) e c m p

(a. s) e (DEC. c) m p                                  → (a-1. s) e c m p

(a b. s) e (ADD. c) m p                              → (a+b. s) e c m p

(a b. s) e (SUB. c) m p                               → (a-b. s) e c m p

(a b. s) e (MUL. c) m p                               → (a*b. s) e c m p

(a b. s) e (DIV. c) m p                                → (a/b. s) e c m p

(a a. s) e (EQ. c) m p                                  → (TRUE. s) e c m p

(a b. s) e (EQ. c) m p                                  → (FALSE. s) e c m p

(a b. s) e (LT. c)m p                                    → (t. s) e c m p⁸

(TRUE. s) e (IF ct cf. c) m p                       → s e (ct. c) m p

(FALSE. s) e (IF ct cf. c) m p                    → s e (cf. c) m p

Далее используем дополнительные обозначения:

[x] – содержимое памяти по адресу x;

e[n] – содержимое n-го элемента контекста; A(Pr) – число аргументов процедуры Pr;

L(Pr) – число локальных переменных процедуры Pr; @c – адрес позиции «c» в программе;

8 t имеет значение «TRUE» или «FALSE».

 

 

_ – произвольное значение (_ подчерк).

s e (LDW x. c) m                                       → ([x]. s) e c m

s e (LD n. c) m                                           → (e[n]. s) e c m

(a. s) e (STW x. c) m                                → s e c (m[x]=a)

(a. s) e (STE x. c) m                                 → s (e[x]=a) c m

s e (LDP @Pr. c) m                                     → (@f L(Pr) A(Pr). s) e c m

(@Pr KL N a1... aN. s) e (AP. c) m         → s ((KL+N) _... _ a1... aN @c. e) Pr m

s (K e1... eK p. e) (RET. c) m                  → () e p m

s e(BR @Pr. c) m                                       → s e Pr m

Разница между SECD и SECM в основном сводится к операциям над дан- ными. Кроме того, SECM имеет дополнительные команды по непосредствен- ной работе с памятью для реализации присваиваний и передаче управления для реализации итераторов.

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

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

Дальнейшее развитие СП заключается в пошаговом расширении спектра обрабатываемых данных и присоединении ВС до полного покрытия ЯП его реализацией в СП. Каждую новую область данных подключают к АМ как ком- плект подпрограмм, реализующий предикат для выяснения принадлежности данного новой области и операции обработки данных. ВС, как правило, могут быть определены в терминах самого ЯП с помощью средств его ядра.

Интеграция вспомогательной семантики новых компонент ЯП в ранее реализованную версию СП осуществляется комплексным включением ряда согласованных определений на всех уровнях определения ЯП:

– дописывание БНФ;

– добавление ветвей в определение интерпретатора;

– дополнение АМ новыми командами.

В случае SECM кроме образа БС фактически реализована работа с векто- рами и указателями (адреса в памяти). Поэтому реализационное замыка-

 

 

ние учебного концентра языка Pascal естественно будет включать в себя об- работку структур данных. Соответствующие, фактически поддержанные на уровне АМ, правила языка:

Данные = array of

AM: x[i]:= y

X:= y [i]

*x:= @y доступ по указателю к адресу.

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

Таблица 9