globalf5-240972240972 (850810), страница 23
Текст из файла (страница 23)
ГородняяОсновы функционального программированиярезультат выражения записан в стек.Определение Лисп-компилятора на Лиспе(DEFUNcompile-(s)(append (comp- s NIL)'(Ap Stop)))(DEFUN comp- (S N)(COND((ATOM S) (list 'LD (adr S N)))((EQ (car S)'QUOTE) (list 'LDC (cadr S)))((EQ (car S)'CONS) (append (comp-(caddr S)N)(comp-(cadr S)N) 'CONS))((EQ (car S)'CAR) (append (comp-(cadr S)N)'CAR))((EQ (car S)'+) (append (comp-(cadr S)N) (comp(caddr S)N) 'ADD))((EQ (car S)'IF) (let ( (then (list (comp-(caddrS)N) '(JOIN)))(else (list (comp-(cadddr S)N) '(JOIN)) ))(append (comp-(cadr S)N) (list 'SEL thenelse)) ))((EQ (car S)'LAMBDA) (list 'LDF (comp-(caddr S)(append (cadr S) N)) 'RTN))((EQ (car S)'LET) (let* ((args (value (cddr S)))(mem (cons (var (cddr S)) N))(body (append (comp-(cadr S)mem) 'RTN)))(append (map #'(lambda(x)(comp- x N))args)(list body 'AP)) ))((EQ (car S)'LABEL) (let* ((args (value (cddr S)))(mem (cons (var (cddr S)) N))(body (append (comp-(cadr S)mem) 'RTN)))(append '(DUM) (map #'(lambda(x)(comp- xmem)) args)154Л.В.
ГородняяОсновы функционального программирования(list 'LDF body 'RAP)))))(T (append (map #'(lambda(x)(comp- x N)) (cdrS))(list body 'AP)) )))155Л.В. ГородняяОсновы функционального программированияРеализационные решенияПриведены принципы реализации, описаны структуры данных,удобныедлядинамическойобработкиинформации.Проиллюстрированы методы "сборки мусора" и других реализационныхмеханизмов функциональных языков программирования, давшихэкспериментальное обоснование современным решениям в областиязыковых новинок по организации вычислений, ставших практичнымина современном оборудовании, которое обладает достаточно высокимиэксплуатационнымихарактеристиками.Рассмотренапоследовательность комплектации ядра системы программирования,технические детали организации ее рабочего цикла и функциональныесредства оперативного мониторинга фактического состава системы.Сборка системы и ее рабочий циклМоделирование Лиспа или другого языка программирования наидеальном базовом Лиспе вполне может послужить иллюстрациейопределения операционной семантики языков программирования [8].Традиционно система программирования для языка Лисп содержитпару интерпретатор-компилятор.
Между этими понятиями трудноустановить формальную границу. Любой интерпретатор содержитэлементы, реализация которых описывается в машинных терминах:структура памяти, реализация двоичных деревьев и т. п. Любаякомпилированная программа содержит интерпретируемые элементы:например, обращения к файловой системе и другим элементам ОС. Напрактике достоинства интерпретации проявляются при отладкепрограмм, а преимущества компиляции — при эксплуатации готовогопрограммного продукта. Более подробное обсуждение этой темызаслуживает отдельного разговора.Теория программирования утверждает, что определение компилятораможет быть выведено из определения интерпретатора методамисмешанных вычислений [9]. Это методы, допускающие частичнуюобработку программ при неполных или избыточных данных спостроением остаточной программы, которую можно применять помере уточнения данных.
Компилятор по такой методике получается как156Л.В. ГородняяОсновы функционального программированияостаточная программа при смешанном вычислении интерпретатора.Теоретически для определения языка программирования достаточнопостроить определение интерпретатора, хотя практичность реальнойсистемы программирования обычно обеспечивается оптимизирующейкомпиляцией и кодогенерацией программ [9].
Но здесь речь идет не обэффективном компиляторе, а лишь о понятном описании семантики.Ядро интерпретатора языка Лисп может быть реализовано следующимобразом:выбирается реализация списков в виде бинарных деревьев, листьякоторого рассматриваются как атомы, а узлы используются длявыстраивания списков (левые ветви — элементы списка, правые— продолжение списка или конец списка, т.е. пустой список);выбирается реализация атомов как объектов, внутренняяструктура которых при определении и исполнении функций невсегда существенна, но при необходимости доступнаспециальным операциям;встраивается специальный атом NIL, являющийся реализациейпустого списка () ;встраивается операция, связывающая различные данные сатомами, и ассоциируется с атомом LABEL ;определяются правила доступа к параметрам встроенныхопераций с размещением их результата и встраиваетсяспециальная операция (монитор), выполняющая применениеопераций к правильно размещенным аргументам ( SUBR );встраивается операция, строящая из атомов и списков болеесложные структуры (списки и узлы из любых элементов), иассоциируется с атомом CONS ;встраиваются операции, выполняющие разбор и анализ структур,и ассоциируются с атомами CAR, CDR, ATOM, EQ,представляющими эти операции;встраиваютсяспециальныеоперации(псевдо-функции),выполняющие блокировку вычислений, выбор ветви иконструирование определений функций, и ассоциируются сатомами QUOTE, COND и LAMBDA, соответственно;универсальная функция ассоциируется с EVAL ;определяется рабочий цикл передачи данных интерпретатору и157Л.В.
ГородняяОсновы функционального программированиявывода результата интерпретации.Такое ядро представляет собой машинно-зависимую часть Лиспинтерпретатора. Встраивание операции в ядро системы — этовключение в его реализацию исполнимого кода, который являетсяреализацией этой операции. Адрес такого кода ассоциируется с именематома, с помощью которого будет организовано выполнение операциипри интерпретации программ.При ассоциировании атомов с произвольной информацией можноиспользовать специально организованный ассоциативный список,построенный из пар, содержащих атомы и их определения. Например,ассоциативный список((T .
T )(NIL . NIL))обеспечивает значение T и NIL в соответствии с семантикой базовогоЛиспа, список((ОДИН . 1)(ДВА . 2))дает символьные имена числовым значениям, а список((ГОЛОВА . CAR)(ХВОСТ . CDR)(УЗЕЛ . CONS))— синонимы для обозначения базовых операций Лиспа.Ассоциативный список работает как стек: при многократныхопределениях доступно самое новое, т.е. расположенное ближе к началусписка. Если мы знаем адреса кода операций, встроенных в ядросистемы, то можем соответствие между именами операций и адресамиих кода хранить в ассоциативном списке.
Можно считать, что начальноесостояние ассоциативного списка содержит таблицу соответствиямежду именами и адресами операций.Основой определения интерпретатора является функция EVAL(evaluation), вычисляющая произвольные выражения языка с учетомсостояния ассоциативного списка AL. Спецификация такой функциидля базового Лиспа может быть проиллюстрирована следующимипримерами:158Л.В. ГородняяОсновы функционального программирования(EVAL NIL AL ) ; = NIL(EVAL T AL );=T(EVAL 'X AL ); = (CADR (ASSOC X AL))(EVAL '(QOUTE EXPR ) AL ); = EXPR(EVAL '(COND ((T YES) ...
)) AL ) ; = YES(EVAL '(SETQ X Y ) AL ); = (CDAR(CONS (CONS 'X (EVAL Y )) AL))(EVAL '(CAR A) '((A 1 2 3)(NIL NIL)) ) ; = 1В других случаях выражения получают значение в результатеприменения некоторой функции, стоящей в голове списка, к ееаргументам, что выполняется другой важной частью определенияинтерпретатора — функцией APPLY. Для ее работы необходимафункция, вычисляющая значения аргументов с учетом состоянияассоциативного списка.При написании на базовом Лиспе определения функции EVAL согласноприведенной выше спецификации, способной от данного списочногопредставления выражения E перейти к его значению с учетомзаданного ассоциативного списка AL, хранящего значения атомов, мынесколько отступаем от ранее данных определений, с тем чтобы болееявно выделить линии сборки системы.(DEFUN EVAL (e al )(COND((MEMBER e '(NIL T )) e )((ATOM e ) ((LAMBDA (v )(COND (v (CADR v ) )(T (ERROR ''undefined_value ))))(ASSOC e al )) )((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) )((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) )((EQ (CAR e) 'LET )(EVAL (CADDDR e )(CONS (CONS (CADR e )(CONS (EVAL (CADDR e ) al ) NIL) ) al )))159Л.В.
ГородняяОсновы функционального программирования(T (APPLY (CAR e) (EVLIS (CDR e) al ) al ) )))В этом функциональном значении используется имя функции APPLY,применяющей произвольную функцию к ее аргументам при заданномассоциативном списке. ERROR — псевдо-функция, выдающая заданныедиагностические сообщения.Определение функции APPLY работает при условии, что функцияSUBR осуществляет применение встроенных функций к их аргументам,заданным в виде списка значений.(DEFUN APPLY (fn args al )(COND((MEMBER fn '(CAR CDR CONS ATOM EQ ))(SUBR (CADR (ASSOC fn al)) args ))((EQ fn NIL) NIL)((ATOM fn ) (APPLY (EVAL fn al ) args al ))((EQ (CAR fn ) 'LAMBDA )(EVAL (CADDR fn )(APPEND (PAIR (CADR fn ) args ) al )) )((EQ (CAR fn) 'LABEL )(APPLY (CADDR fn) args(CONS (CDR fn ) al )) )(T (ERROR- 'undefined_function))) )Обратите внимание, что в EVAL при поиске атома в ассоциативномсписке мы допускаем отсутствие ассоциированного с атомом значенияи сообщаем об этом диагностикой с помощью функции ERROR.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
