globalf5-240972240972 (850810), страница 22
Текст из файла (страница 22)
Все необъявленные переменныерассматриваются как обычные.При трансляции функций в подпрограммы концепция переменныхотображается в распределение памяти, в которой размещаются значенияаргументов. Для обычных переменных распределение памяти — этостек. Другие функции не могут знать адреса таких переменных, что и непозволяет рассматривать их как свободные.SPECIAL -переменные размещаются в списке свойств. Это допускаетреализацию с заданием фиксированных адресов ячеек.
Когда такаяячейка связана, можно старое значение вытолкнуть в стек, а новоеразместить по старому адресу. При выходе из области действия текущейсвязи старое значение может быть восстановлено. При использованиитакой свободной переменной адрес SPECIAL -ячейки может быть147Л.В. ГородняяОсновы функционального программированиядоступен другим функциям.SPECIAL -переменные объявляются псевдо-функцией DECLARE синдикатором SPECIAL, вслед за которым расположен списокпеременных. Эта функция устанавливает индикатор SPECIAL в спискахсвойств перечисленных имен и создает ячейку для хранения значенияпеременной.
Эта псевдо-функция для компилятора весьма существенна.Она может действовать и при интерпретации, и при прогонекомпилированных программ.(DECLARE ... (SPECIAL v1 v2 ... ) ... )При повторном объявлении одной и той же SPECIAL -переменнойкомпилятор выделит другую ячейку, формально это будут различныепеременные.Специальные переменные удобны для коммуникации междукомпилируемыми программами, но не всегда могут четко служитькоммуникации между интерпретируемыми и компилируемымипрограммами.Еще один тонкий аспект — функциональные константы.Рассмотрим следующее определение, использующее S-выражение:(DEFUN YDOT(LAMBDA (X Y)(MAPLIST X(FUNCTION (LAMBDA (J) (CONS (CAR J) Y) ))) ) )(YDOT (A B C D) X);=((A .
X) (B . X) (C . X) (D . X))]За словом FUNCTION располагается функциональная константа. Еслиее вынести как самостоятельную функцию, то формально J — связаннаяпеременная, а Y — свободная. Не исключено, что свободная переменнаягде-то будет объявлена как специальная или общедоступная, хотя онадолжна быть связана внутри YDOT.148Л.В. ГородняяОсновы функционального программированияТеперь про функциональные аргументы.MAPLIST может быть определен следующим образом:(DEFUN MAPLIST(LAMBDA (L FN)(COND((NULL L) NIL)(T (CONS (FN L)(MAPLIST (CDR L) FN) ))) ) )Переменная FN — это связанный функциональный аргумент.
Дело втом, что его значение — определение функции.Трассировка скомпилированных программTRACE — работает с компилированными программами согласноследующим ограничениям:1. TRACE может быть объявлена после компиляции и не требуетповторной компиляции программы.2. TRACE не отслеживает прямые переходы на функции, созданныев обход атомов, т.е. выделенные на уровне ассемблера или кодабез встраивания в общую информационную систему Лиспа —таблицу символов, хранящую свойства атомов." В правильном выражении всегда достаточно скобок, чтобы избежатьсинтаксической неоднозначности"[3] Используя это утверждениеХендерсона как эпиграф, а в Лиспе со скобками все в порядке, можноуверенно приступить к определению собственно компилятора.Компиляция.
Венский метод. Операционная семантикаФункциональный подход к программированию наиболее убедительновыражен в Венской методике определения языков программирования.Эта методика разработана в конце 60-х годов [8]. Основная идея —использование абстрактного синтаксиса и абстрактной машины приопределении семантики языка программирования.
Конкретный149Л.В. ГородняяОсновы функционального программированиясинтаксис языка отображается в абстрактный — анализ, а абстрактнаямашина может быть реализована с помощью конкретной машины —кодогенерация, причем и то, и другое может иметь небольшой объем иневысокую сложность. Сущность определения языка концентрируется ввиде так называемой семантической функции языка, выполняющейпереход от абстрактного синтаксиса к абстрактной машине —трансляцию.При такой архитектуре компилятор можно рассматривать как трикомплекта функций, обеспечивающих анализ программы, еетрансляцию и кодогенерацию. Главная задача анализа — обнаружитьосновные понятия и выделить, вывести или вычислить по текступрограммы значения компонентов структуры, представляющей собойабстрактный синтаксис программы.
Эта работа сводится к наборураспознавателей и селекторов, названия которых могут быть выбраны взависимости от смысла понятий, составляющих программу, ареализация варьируется в зависимости от конкретного синтаксисаязыка. Тогда при любом конкретном синтаксисе разбор программывыполняется тем же самым определением, что и анализ ее абстрактногопредставления, которое играет роль спецификации. Любое определениеанализа выглядит как перебор распознавателей, передающихуправление композициям из селекторов, выбирающих существенныекомпоненты из анализируемой программы и заполняющих поляопределенной структуры или значениями, или программами ихвычисления.
Содержимое полей предназначено для генерации кодапрограммы, эквивалентной исходному тексту программы, а заодно и ееабстрактной структуре. Например, если форму PROG рассматривать какпредставление абстрактного синтаксиса для подмножества языкаПаскаль, содержащего переменные, константы, арифметическиеоперацииисравнения,пустойоператор,присваивание,последовательное исполнение операторов, условный оператор,безусловный переход GOTO и циклы, то необходим наборраспознавателей, выявляющих эти понятия, и селекторов, выделяющихих характеристики. Селекторы имеют смысл лишь при истинностисоответствующего распознавателя.Использование списочных форм в качестве абстрактного синтаксисапозволяет все распознаватели свести к анализу головы списка.Таблица 8.1. Абстрактный синтаксис операторов.150Л.В.
ГородняяОсновы функционального программированияТаблица 8.1. Абстрактный синтаксис операторов.(перем X )x(конст C )c(плюс А1 А2 ) (A1 + A2)(равно А1 А2 ) (A1 = A2)(пусто)(присвоить X A ) x := a(шаги S1 S2 ) S1; S2;(если P ST SF ) if p then ST else SF;(пока P S )while p do S;Все селекторы сводятся к композиции CAR-CDR, выполняемой послесоответствующего распознавателя. Так, в приведенных выше формахполя X, C, A1, S1, P можно выделить селектором, определенным как(LAMBDA (FM) (CAR(CDR FM))) — выделение второго элементасписка, а поля A2, S2, ST, S, расположенные третьими в списках — как(LAMBDA (FM) (CAR(CDR(CDR FM)))), поле SF — как(LAMBDA(FM)(CAR(CDR(CDR(CDRFM))))).
Такиеопределения практически не требуют отладки, работают с первогопредъявления.Определение семантической функции, обеспечивающей корректнуютрансляцию абстрактного синтаксиса программы в ее абстрактный код,требует реализации соответствия между именами и их значениями взависимости от контекста и предшествующих определений.При интерпретации такое соответствие представлялось ассоциативнымсписком, в котором хранятся связи вида Имя-Смысл, преобразуемые попринципу стека, естественно отражающего динамику вызова функций.При компиляции не принято сохранять имена на время исполненияпрограммы: их роль выполняют сопоставленные именам адреса.Поэтому вместо а-списка вида ((а . 1)(в .
2)(с . 3)...)применяется два списка (а в с ...) и (1 2 3 ...), хранящихимена и их значения на согласованных позициях. Обрабатываются этидва списка синхронно: оба удлиняются или сокращаются на одинаковоечисло элементов.151Л.В. ГородняяОсновы функционального программированияМожно переписать EVAL-APPLY с соответствующей коррекцией иопределить функцию подстановки, заменяющую имена их значениямииз синхронного списка.Определение EVAL-APPLY особенно компактно в стиле p-списка.Иерархию определений можно организовать с помощью блоков FLETсо списками определений для шаблонов (перем конст плюс равно) иотдельно для (пусто присвоить шаги если пока).Важно обратить внимание на учет изменения контекста припоследовательном выполнении шагов программы, а также нанесовпадение порядка в тексте с очередностью выполнениякомпозиций функций. Формально операторы могут рассматриваться какфункции, преобразующие полное состояние памяти V.
Пусть функция Eсписочному представлению оператора сопоставляет эквивалентнуюему Лисп-функцию, вызываемую в контексте (DECLARE (SPECIALN)) или (PARAMETER N).Таблица 8.2. Примеры функциональной реализации операторов ивыражений.c(конст C)(LAMBDA (v)c)x(LAMBDA (v) (assoc-i X N v))(перем X)N — свободная переменная, задающая списокимен, известных в программе(A1 + A2)(плюс А1 А2 )(LAMBDA (v) (+((Е А1)v) ((E А2)v)) )(A1 = A2)(равно А1 А2 )(пусто)x := a;(LAMBDA (v)(= ((Е А1)v) ((E А2)v)) )(LAMBDA (v)v)Состояние памяти V неизменноЗамена происходит по указанному адресу152Л.В.
Городняя(присвоить X A )Основы функционального программирования(LAMBDA (v)(replace N v X ((E A)v))S1; S2;(шаги S1 S2 )if P then STelse SF;(если P STSF)(LAMBDA (v) (E S2 (E S1 v)))(LAMBDA (v) (funcall(COND (((E P)v)((E ST)v)) (T((E SF)v)) )v)while e do S; Циклу соответствует безымянная функция,строящая внутренний контекст(пока P S )(LAMBDA (W) ((LAMBDA (v)(COND (((E P)v)(w ((E S)v)))(T v)))(LAMBDA (v)(COND ( ((E P)v)(w((E S)v)))(T v)))))Денотационная семантика ЯП (математическая) определяет семантикуязыка в терминах соотношений между множествами. При заданииоперационной семантики важно отследить корректность обработкипорождаемых структур данных, что может быть сформулировано каксвойство чистого результата.
Согласно этому свойству задана четкаядисциплина манипуляций со стеком при обработке данных: каждаяоперация берет из стека в точности все свои аргументы и обязательнорасполагает в нем свой единственный результат.При определении компилятора на уровне абстрактной машины должнобыть выделено описание реализационного минимума языка Лисп,послужившего базой для раскрутки Лиспа и основой дляфункционального программирования. Необходимо лишь ввестинекоторыеограничения,гарантирующиеприпереходекнизкоуровневому программированию сохранение важнейших свойствфункциональных программ. Эти ограничения формулируются какчистый результат правильного выражения:все аргументы убраны из стека;153Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
