учебники, программирование, основы, введение в,

 

Детализация базовых функций

Низкоуровневое программирование. Ассемблер
П.Лэндин (P.J.Landin) предложил специальную абстрактную машину SECD, удобную для спецификации машинно-зависимых аспектов семантики Лиспа, которая будет рассмотрена ниже. А в первых Лисп-системах для реализации ядра и встроенных операций использовался специальный Лисп-ассемблер LAP, описание которого приводим в качестве иллюстрации. (LAP проектировался специально для нужд компилятора, но он применялся и для низкоуровневых определений функций, а также для обработки заплат (patches). Это двухпроходной встроенный, исключительно внутренний ассемблер. Первый просмотр анализирует программу и выясняет взаимосвязи между ее частями и Лисп-системой. При ассемблировании на LAP не предусмотрено и не происходит никаких манипуляций с текстами программы в файлах. Ассемблирование кода программы выполняется в оперативной памяти во время второго просмотра, выполняющего сборку кода с установлением фактических адресов.
LAP был включен в Лисп-систему как псевдо-функция от двух аргументов. Первый аргумент — листинг программы, представленный в виде списка, второй — исходная таблица символов. Результат — окончательная таблица символов, по формату напоминающая ассоциативный список.)
Можно сказать, что первые Лисп-системы обеспечивали Лисп-интерфейс для доступа ко всем возможностям оборудования в стиле работы с ассемблером, но по форме как с обычными символьными данными.
Началом листинга ассемблерной программы является строка, сообщающая ассемблеру, с какой позиции стартовать и предстоит ли полученный в результате код программы встраивать в интерпретатор как Лисп-функцию.
По завершении работы ассемблера индикатор "Тип" будет размещен в списке свойств атома "Название" вместе со специально сконструированной структурой данных, хранящей адрес построенного кода, арность и команду для вызова этого кода как подпрограммы из Лисп-интерпретатора. Тип - это обычно SUBR или FSUBR, отражает разницу в методах обработки параметров обычными и специальными функциями.
При ассемблировании атомарных форм список свойств атома проверяется на вхождение индикаторов SUBR, FSUBR.
Формы вида (QUOTE a) рассматриваются как литеральная величина, содержащая a. Ее адрес - результат ассемблирования. Величина защищена от выметания. Новый литерал не создается, если он совпадает с ранее построенным.
Определение операций выполняется opdefine, псевдо-функцией для введения новых команд для LAP. Она устанавливает индикатор SYM в списке свойств атома, который предстоит определить как обозначение или символ команды. Ее аргумент - список пар. Каждая пара - символ и его численное значение. Обратите внимание, что здесь пара означает не "точечная" пара, а двухэлементный список.
    (OPDEFINE ( (CLA 500Q8)
(TRA 2Q9)
(LOAD 1000)
(OVBGN 7432Q) ))

Пример 7.1.
Примеры применения ассемблера
Предикат greater наводит некоторый канонический порядок среди атомов.
    (LAP ( (GREATER SUBR 2) (TLQ (* 3))
(PXA 0 0)
(TRA 1 4)
(CLA (QUOTE *T* ) )
(TRA 1 4) )
NIL)

Пример 7.2. Лисп-функция.
Команда TSX 6204Q должна быть вставлена после позиции 6217Q. Последняя содержит CLA 6243Q и эти команды должны быть перемещены для заплатки.
(LAP (6217Q (TRA NIL) )NIL)
(LAP (NIL (CLA A)
(TSX 6204Q)
(TRA B) )
( (A . 6243Q) (B . 6220Q) )
))

Пример 7.3. Заплатка для кода программы.

Абстрактная Лисп-машина. Система команд
Встраиваемые в ядро интерпретатора операции должны соответствовать стандартным правилам доступа к параметрам и размещения выработанного результата. Таким же правилам должен подчиняться и компилируемый код. Это позволяет формально считать равноправными встроенные и программируемые функции. Компилятор по исходному тексту программы строит код программы, эквивалентный тексту. Особенности процесса компиляции достаточно сложны даже для простых языков, поэтому характеристика результата компиляции часто задается в терминах языково-ориентированных абстрактных машин. Такой подход полезен для решения ряда технологических проблем разработки программных систем (мобильность, надежность, независимость от архитектур и т.п.).
При сравнении императивного и функционального подходов к программированию, П.Лэндин (P.J.Landin) предложил специальную абстрактную машину SECD, удобную для спецификации машинно-зависимых аспектов семантики Лиспа. Подробное описание этой машины можно найти в книгах Хендерсона и Филда-Харрисона по функциональному программированию .
Машина 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) — новое состояние контекста.

Функциональная модель процессора абстрактной машины

На этом можно было бы завершить описание реализационного минимума языка Лисп, послужившего основой для функционального программирования. Но мы рассмотрим более детально еще ряд технических аспектов, иллюстрирующих возможности функционального подхода к задачам системного программирования, включая конструирование компиляторов и моделирование парадигм программирования.
Здесь же определим общий цикл выполнения программ на SECD, что даст возможность поэкспериментировать с абстрактной машиной. Вышеописанная система команд способна выполнять результаты компиляции функциональных программ, написанных на элементарном Лисп. В следующей лекции более подробно будет описан компилятор. А пока можно поупражняться с расширениями SECD.
Объявление системы команд машины и их определения:

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика