globalf5-240972240972 (850810), страница 20
Текст из файла (страница 20)
При ассемблировании на LAP непредусмотрено и не происходит никаких манипуляций с текстамипрограммы в файлах. Ассемблирование кода программы выполняется воперативной памяти во время второго просмотра, выполняющегосборку кода с установлением фактических адресов. LAP был включен вЛисп-систему как псевдо-функция от двух аргументов. Первый аргумент— листинг программы, представленный в виде списка, второй —исходная таблица символов. Результат — окончательная таблицасимволов, по формату напоминающая ассоциативный список.)(LAP листинг символы)Можно сказать, что первые Лисп-системы обеспечивали Лиспинтерфейс для доступа ко всем возможностям оборудования в стиле131Л.В.
ГородняяОсновы функционального программированияработы с ассемблером, но по форме как с обычными символьнымиданными.Началом листинга ассемблерной программы является строка,сообщающая ассемблеру, с какой позиции стартовать и предстоит липолученный в результате код программы встраивать в интерпретаторкак Лисп-функцию. По завершении работы ассемблера индикатор "Тип"будет размещен в списке свойств атома "Название" вместе соспециально сконструированной структурой данных, хранящей адреспостроенного кода, арность и команду для вызова этого кода какподпрограммы из Лисп-интерпретатора. Тип - это обычно SUBR илиFSUBR, отражает разницу в методах обработки параметров обычнымии специальными функциями.
При ассемблировании атомарных формсписок свойств атома проверяется на вхождение индикаторов SUBR,FSUBR.Формы вида ( QUOTE a ) рассматриваются как литеральная величина,содержащая a. Ее адрес - результат ассемблирования. Величиназащищена от выметания. Новый литерал не создается, если онсовпадает с ранее построенным.Определение операций ассемблера выполнялось OPDEFINE, псевдофункцией для введения новых команд для LAP. Она устанавливаетиндикатор SYM в списке свойств атома, который предстоит определитькак обозначение или символ команды. Ее аргумент - список пар.
Каждаяпара - символ и его численное значение. Здесь пара означает не"точечная" пара, а двухэлементный список.(OPDEFINE ( (CLA 500Q8)(TRA 2Q9)(LOAD 1000)(OVBGN 7432Q) ))Пример 7.1.Примеры применения ассемблераПредикат GREATER наводит некоторый канонический порядок средиатомов.132Л.В. ГородняяОсновы функционального программирования(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. Заплатка для кода программы.Абстрактная Лисп-машина. Система командВстраиваемыевядроинтерпретатораоперациидолжнысоответствовать стандартным правилам доступа к параметрам иразмещения выработанного результата. Таким же правилам долженподчиняться и компилируемый код. Это позволяет формально считатьравноправными встроенные и программируемые функции. Компиляторпо исходному тексту программы строит код программы, эквивалентныйтексту.
Особенности процесса компиляции достаточно сложны дажедля простых языков, поэтому характеристика результата компиляциичасто задается в терминах языково-ориентированных абстрактныхмашин. Такой подход полезен для решения ряда технологическихпроблем разработки программных систем (мобильность, надежность,независимость от архитектур и т.п.).При сравнении императивного и функционального подходов133кЛ.В. ГородняяОсновы функционального программированияпрограммированию, П.Лэндин (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 — первый элемент из активного значения стека ;134Л.В.
ГородняяОсновы функционального программирования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 d135Л.В. Городняя(a . s)e(ATOM . c)d(a b . s)e(EQ . c)dОсновы функционального программирования>> (t . s) e 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.Организация вызова процедур требует защиты контекста от локальныхизменений, происходящих при интерпретации тела определения.
Дляэтого при вводе определения функции в стек создается специальная136Л.В. ГородняяОсновы функционального программированияструктура, содержащая код определения функции и копию текущегосостояния контекста. До этого в стеке должны быть размещеныфактические параметры процедуры. Завершается процедура командой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,соответственно.)Ответ:137Л.В.
ГородняяОсновы функционального программирования( 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 l )(COND((EQ n 0 )(CONS e (CDR l )) )(T (CONS (CAR l )(ASS e (SUB1 n ) (CDR l ) ))) ) )Тогда можно описать команду SET следующим образом:(x .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
