globalf5-240972240972 (850810), страница 21
Текст из файла (страница 21)
s) e (SET n . c) d >> s xne c dгде xne = (ASS x n e) — новое состояние контекста.ФункциональнаямашинымодельпроцессораабстрактнойНа этом можно было бы завершить описание реализационногоминимума языка Лисп, послужившего основой для функциональногопрограммирования. Но мы рассмотрим более детально еще рядтехническихаспектов,иллюстрирующихвозможностифункционального подхода к задачам системного программирования,включая конструирование компиляторов и моделирование парадигмпрограммирования.Здесь же определим общий цикл выполнения программ на SECD, чтодаст возможность поэкспериментировать с абстрактной машиной.Вышеописанная система команд способна выполнять результаты138Л.В. ГородняяОсновы функционального программированиякомпиляции функциональных программ, написанных на элементарномЛисп.
В следующей лекции более подробно будет описан компилятор. Апока можно поупражняться с расширениями SECD.Объявление системы команд машины и их определения:(DEFUN put (at ind def) (setf (get at ind) def))(put 'a 'SYM '(LAMBDA () (setq st (CONS (caar st)(CDR st)))))(put 'd 'SYM '(LAMBDA () (setq st (CONS (cadar st)(CDR st)))))(put 'at 'SYM '(LAMBDA () (setq st (CONS(ATOM (CAR st))(CDR st)))))(put 'co 'SYM'(LAMBDA () (setq st (CONS(CONS (CAR st) (cadr st))(cddr st)))))(put 'equ 'SYM '(LAMBDA () (setq st (CONS(EQ (CAR st) (cadr st))(cddr st)))))(put 'sum 'SYM '(LAMBDA () (setq st (CONS(+ (CAR st) (cadr st))(cddr st)))))(put 'def 'SYM '(LAMBDA () (setq st (CONS(- (CAR st) (cadr st))(cddr st)))))(put 'mlt 'SYM '(LAMBDA () (setq st (CONS(* (CAR st) (cadr st))(cddr st)))))(put 'ldc 'SYM '(LAMBDA ()139Л.В.
ГородняяОсновы функционального программирования; CP — продолжение программы вслед за LDC(setq st (CONS (CAR cp)st))(setq cp (CDR cp)); CP — без константы, переданной в стек)); Определение интерпретатора машины(DEFUN secd (LAMBDA ()(cond ((null cp)(print "?end-of-program!"))((EQ (CAR cp) 'STOP)(print "!normal-finish!"))((get (CAR cp)'SYM)(command (CAR cp) (CDR cp))(secd))(T (print "?error-command!")(setq cp (CDR cp))(secd)))))(DEFUN command (LAMBDA (acp dcp) (setq cp dcp)(print acp)(apply (get acp 'SYM)'())(prsecd)(read))); Вывод на экран состояния машины(DEFUN prsecd (LAMBDA()(prst)(prcp)))(DEFUN prst (LAMBDA ()(print (list "stack:=" st))))(DEFUN prcp (LAMBDA ()(print (list "control:=" cp)))); Задание состояния машины :; ST — стек; CP — управляющая программа; ENV — контекст; DM — память для восстановления состояния140Л.В.
ГородняяОсновы функционального программирования(setq st '())(setq cp '(ldc 1 ldc 2 ldc 3 mlt def ldc 4 equstop ))(secd)(prsecd)(read)(system)(setq st '(a ((1 2) (4 5)) 3 6 7 8 9 11 13 12 1421 25 9 1 0))(setq cp '(at de co at equ stop sum def mlt stop))(prsecd)(secd)(prsecd)(setq st (cddr st))(setq cp (CDR cp))(prsecd)(secd)(prsecd)(system)(apply (get 'a 'SYM)'())(prst)(setq st (CDR st))(apply (get 'd 'SYM)'())(prst)(setq st (CDR st))(apply (get 'at 'SYM)'())(prst)(setq st (CDR st))(apply (get 'co 'SYM)'())(prst)(apply (get 'at 'SYM)'())(prst)(setq st (CDR st))(setq st (CDR st))(apply (get 'equ 'SYM)'())(prst)(setq st (CDR st))(apply (get 'sum 'SYM)'())141Л.В.
ГородняяОсновы функционального программирования(prst)(setq st (CDR st))(apply (get 'def 'SYM)'())(prst)(setq st (CDR st))(apply (get 'mlt 'SYM)'())(prst)(setq st '(12 12 12) )(prst)(setq st (CDR st))(apply (get 'equ'SYM)'())(prst)(system)142Л.В. ГородняяОсновы функционального программированияКомпиляция функциональных программВ данной лекции изучаются требования к компиляции функциональныхпрограмм и строится определение компилятора. Для Лиспа такоеопределение написано на Лиспе, как и определение интерпретатора.РассматриваютсяВенскаяметодикаопределенияязыковпрограммирования, а именно отображение абстрактного синтаксисаязыка на язык абстрактной машины, и приемы оптимизационногопрограммирования. Разложение программы на функции с разнымуровнем отладки является отправной точкой при выбореоптимизационных решений.
Компиляция программ рассматриваетсякак один из методов оптимизации процессов, осуществляемый каксимвольное преобразование — трансляция с исходного языка высокогоуровня на язык низкого уровня, допускающий оптимизирующуюкодогенерацию.Компилятор и требования к коду программыОписанная в предыдущей лекции специальная абстрактная машинаSECD удобна для спецификации машинно-зависимых аспектовсемантики Лиспа. Такой подход позволяет не загромождать определениекомпилятора, добиться его прозрачности, но главное, такое определениеможет быть машинно-независимым и переносимым [3].Для функционального стиля в программировании характерностремление снять непринципиальные ограничения на применение ипостроение функций.
Для этого приходится сдерживать привычные длямногих областей применения разграничения, а также смягчатьстандартные границы при организации процессов в системахпрограммирования. В этом отношении следует отметить:1. единое пространство функций, их аргументов и всех обозначений,роль которых определяется по контексту при интерпретацииформ;2. разрешение функциональных переменных, значение которыхконструируется (вычисляется) в процессе их интерпретации. Этопозволяет вводить частичные определения, уточняемые по меренеобходимости;143Л.В. ГородняяОсновы функционального программирования3.
самоопределение основных механизмов символьной обработки и,следовательно, открытый характер системы программирования,поддерживающей функциональное программирование;4. мягкость пространственно-временных ограничений, без точныхчисленных оценок по отдельным параметрам;5. поощрение рекурсивных определений;6. предельная уточняемость и детализируемость определений,управление временем их существования и выполнения.Лисп-компилятор — это программа, написанная на Лисп, котораятранслирует S-выражения, определяющие функции, в машинныеподпрограммы. Это средство оптимизации, позволяющее ускоритьработу программ от двух до ста раз, чем было бы при простойинтерпретации.Когда компилятор вызывается для компиляции функций, он находитопределение функции в списке свойств названия функции.
Компилятортранслирует найденное исходное S-выражение в объектное Sвыражение, которое представляет подпрограмму на языке ассемблера.Ассемблер после этого ассемблирует код программы. Затем в спискесвойств функции размещается ссылка на код программы.Опыт показывает, что скомпилированная программа может работатьнамного раз быстрее, чем интерпретируемая программа, в зависимостиот ее природы. Скомпилированные программы могут быть иэкономичнее с точки зрения расхода памяти, требуя 50–80% от полногообъема.Основная часть компилятора — транслятор или функция,отображающая S-выражения, которые обозначают функции, на языкассемблера.
Единственное основание для того, чтобы рассматриватькомпилятор как псевдо-функцию, состоит в том, что он изменяетсвойства названий функций по завершении компиляции.Лисп-компилятор имеет уникальную историю.пошаговым образом ( метод раскрутки )[1].Онразвивался1. Компилятор был написан и отлажен как Лисп-программа,состоящая из набора определений функций в виде S-выражений.144Л.В. Городняя2.3.4.5.Основы функционального программированияЭто позволило компилировать любые Лисп-программы и строитьспециализированные расширения Лисп-интерпретатора.Компилятору была дана команда скомпилировать себя самого.Данная операция называется раскруткой ( bootstrapping ).
На этопотребовалось более 5 минут на IBM 7090, посколькузначительная часть компилятора в основном интерпретировалась.В результате было создано эффективное расширение Лиспсистемы, способное компилировать Лисп-программы и строитьрасширения Лисп-интерпретатора.Чтобы исключить повторение медленной раскрутки придальнейших шагах установки системы, весь код компиляторазаново был введен на языке ассемблера.Была создана системная лента, и компилятор стал загружаемым науровне ассемблера.Процесс раскрутки был повторен до полного формирования кодаЛисп-системы.Компилятор вызывается псевдо-функцией COMPILE.
АргументCOMPILE — список названий функций, которые следуеткомпилировать. Каждый атом в списке должен иметь определениефункции в своем списке свойств до компиляции.Обработка каждой функции происходит в три шага. Во-первых, Sвыражение, задающее функцию, транслируется в текст на уровеньассемблера. При отсутствии S-выражения, компилятор сообщает обэтом и переходит к другой функции. Во-вторых, текст программы науровне ассемблера транслируется в код программы.
И, наконец, еслиникаких ошибок не обнаружено, то S-выражение функции может бытьудалено из списка свойств. Когда некоторые ошибки указывают напоявление необъявленной переменной, компилятор предупреждает обэтом и продолжает работу. Такая диагностика будет дополнительноуточнена при анализе значений переменной.При написании большой Лисп-программы лучше отлаживатьотдельные функции, используя интерпретатор, а компилировать толькоте из них, которые уже хорошо изучены.Программист, планирующий применять компилятор, должен обратитьвнимание на следующие моменты.145Л.В. ГородняяОсновы функционального программирования1. Нет необходимости компилировать все функции, которыеиспользуются лишь эпизодически.
Интерпретатору доступныскомпилированные функции. Компилированные функции,использующие интерпретируемые функции, могут вычислять ихнепосредственно при счете.2. Порядок выполнения компиляции не имеет значения. Даже нетнеобходимости определять все функции до тех пор, пока они непонадобятся при счете. (Исключение из этого правила —специальные формы.
Они должны быть определены до того, каккомпилируется их вызов.)3. При динамическом использовании LABEL результирующаяфункция не может быть скомпилирована полностью.4. Свободные переменные в компилируемых функциях должныобъявляться до компиляции функций (См. лекцию 7).Последнее требование проясняет роль типового контроля встандартных, ориентированных на компиляцию без интерпретации,системах программирования.Компиляция всех объектов осуществляетсябез анализа фактических данных, а это и означает, что на моменткомпиляции переменные, как правило, являются свободными.Интерпретация располагает более полной информацией, связывающейнеобходимые для вычислений переменные с конкретными значениями,тип которых определен.Компилятор и ассемблер могут быть удалены из комплекта Лиспсистемы.
В целом существует механизм пакетов, позволяющийуправлять составом функций и объектов, включаемых в комплект. Приудалении части системы освободившаяся память может бытьприсоединена к списку свободной памяти. Имеются реализации, вкоторых выделено минимальное ядро системы, все остальные функциизагружаются по мере необходимости, а мусорщик может рассматриватьпамять от неиспользуемых функций как свободную.Требования к компиляции Лисп-программРассмотрим особенности Лисп-программ, которые необходимо учестьпри определении компилятора и подготовке программ к компиляции.Прежде всего — свободные переменные. Переменная связана, если она146Л.В.
ГородняяОсновы функционального программированиявстречается в списке LAMBDA или PROG, а также LET, DO, LOOP и т.п.Все несвязанные переменные свободны.(LAMBDA (A) (PROG (B)S(SETQ B A)(COND ((NULL B) (RETURN C)))(SETQ C (CONS (CAR A) C))(GO S)))Пример 8.1.A и B — связанные переменные, C — свободная переменная.Когда переменная используется как свободная, это значит, что онадолжна быть связана в другой функции на более высоком уровне. Приинтерпретации функций может быть обнаружена переменная, несвязанная вообще, о чем система известит пользователясоответствующим диагностическим сообщением об ошибке.При компиляции новые диагностические сообщения не появляются, апеременная получает значение NIL.Существуют разные типы переменных в компилируемых функциях:обычные и специальные — SPECIAL. Тип SPECIAL необходимообъявить до компиляции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
