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

 

Компиляция функциональных программ

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

  1. единое пространство функций, их аргументов и всех обозначений, роль которых определяется по контексту при интерпретации форм;
  2. разрешение функциональных переменных, значение которых конструируется (вычисляется) в процессе их интерпретации. Это позволяет вводить частичные определения, уточняемые по мере необходимости;
  3. самоопределение основных механизмов символьной обработки и, следовательно, открытый характер системы программирования, поддерживающей функциональное программирование;
  4. мягкость пространтственно-временных ограничений, без точных численных оценок по отдельным параметрам;
  5. поощрение рекурсивных определений;
  6. предельная уточняемость и детализируемость определений, управление временем их существования и выполнения.

Лисп-компилятор — это программа, написанная на Лисп, которая транслирует S-выражения, определяющие функции, в машинные подпрограммы. Это средство оптимизации, позволяющее программам работать от двух до ста раз быстрее, чем было бы при простой интерпретации.
Когда компилятор вызывается для компиляции функций, он находит определение функции в списке свойств названия функции. Компилятор транслирует найденное S-выражение в S-выражение, которое представляет подпрограмму на языке ассемблера. Ассемблер после этого ассемблирует код программы. Затем в списке свойств размещается ссылка на код программы.
Опыт показывает, что скомпилированная программа может работать в 2100 раз быстрее, чем интерпретируемая программа, в зависимости от ее природы. Скомпилированные программы могут быть и экономичнее с точки зрения расхода памяти, требуя 50–80% от полного объема.
Основная часть компилятора — транслятор или функция, отображающая S-выражения, которые обозначают функции, на язык ассемблера. Единственное основание для того, чтобы рассматривать компилятор как псевдо-функцию, состоит в том, что он изменяет свойства названий функций по завершении компиляции.
Лисп-компилятор имеет уникальную историю. Он развивался пошаговым образом (метод раскрутки).

  1. Компилятор был написан и отлажен как Лисп-программа, состоящая из набора определений функций в виде S-выражений. Это позволило компилировать любые Лисп-программы и строить специализированные расширения Лисп-интерпретатора.
  2. Компилятору была дана команда скомпилировать себя самого. Данная операция называется раскруткой (bootstrapping). На это потребовалось более 5 минут на IBM 7090, поскольку значительная часть компилятора в основном интерпретировалась. В результате было создано эффективное расширение Лисп-системы, способное компилировать Лисп-программы и строить расширения Лисп-интерпретатора.
  3. Чтобы исключить повторение медленной раскрутки при дальнейших шагах установки системы, весь код компилятора заново был введен на языке ассемблера.
  4. Была создана системная лента, и компилятор стал загружаемым на уровне ассемблера.
  5. Процесс раскрутки был повторен до полного формирования кода Лисп-системы.

Компилятор вызывается псевдо-функцией compile. Аргумент compile — список названий функций, которые следует компилировать. Каждый атом в списке должен иметь определение функции в своем списке свойств до компиляции.
Обработка каждой функции происходит в три шага. Во-первых, S-выражение, задающее функцию, транслируется в текст на уровень ассемблера. При отсутствии S-выражения, компилятор сообщает об этом и переходит к другой функции. Во-вторых, текст программы на уровне ассемблера транслируется в код программы. И, наконец, если никаких ошибок не обнаружено, то S-выражение функции может быть удалено из списков свойств. Когда некоторые ошибки указывают на появление необъявленной переменной, компилятор предупреждает об этом и продолжает работу. Такая диагностика будет дополнительно уточнена при анализе значений переменной.
При написании большой Лисп-программы лучше отлаживать отдельные функции, используя интерпретатор, а компилировать только те из них, которые уже хорошо изучены.
Программист, планирующий применять компилятор, должен обратить внимание на следующие моменты.

  1. Нет необходимости компилировать все функции, которые используются лишь эпизодически. Интерпретатору доступны скомпилированные функции. Компилированные функции, использующие интерпретируемые функции, могут вычислять их непосредственно при счете.
  2. Порядок выполнения компиляции не имеет значения. Даже нет необходимости определять все функции до тех пор, пока они не понадобятся при счете. (Исключение из этого правила — специальные формы. Они должны быть определены до того, как компилируется их вызов.)
  3. При динамическом использовании Label результирующая функция не может быть скомпилирована полностью.
  4. Свободные переменные в компилируемых функциях должны объявляться до компиляции функций (См. лекцию 7).

Последнее требование проясняет роль типового контроля в стандартных, ориентированных на компиляцию без интерпретации, системах программирования.Компиляция всех объектов осуществляется без анализа фактических данных, а это и означает, что на момент компиляции переменные, как правило, являются свободными. Интерпретация располагает более полной информацией, связывающей необходимые для вычислений переменные с конкретными значениями, тип которых определен.
Компилятор и ассемблер могут быть удалены из комплекта Лисп-системы. В целом существует механизм пакетов, позволяющий управлять составом функций и объектов, включаемых в комплект. При удалении части системы освободившаяся память может быть присоединена к списку свободной памяти. Имеются реализации, в которых выделено минимальное ядро системы, все остальные функции загружаются по мере необходимости, а мусорщик может рассматривать память от неиспользуемых функций как свободную.

Требования к компиляции Лисп-программ
Рассмотрим особенности Лисп-программ, которые необходимо учесть при определении компилятора и подготовке программ к компиляции.
Прежде всего — свободные переменные. Переменная связана, если она встречается в списке 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 необходимо объявить до компиляции. Все необъявленные переменные рассматриваются как обычные.
При трансляции функций в подпрограммы концепция переменных отображается в распределение памяти, в которой размещаются значения аргументов. Для обычных переменных распределение памяти — это стек. Другие функции не могут знать адреса таких переменных, что и не позволяет рассматривать их как свободные.
SPECIAL-переменные размещаются в списке свойств. Это допускает реализацию с заданием фиксированных адресов ячеек. Когда такая ячейка связана, можно старое значение вытолкнуть в стек, а новое разместить по старому адресу. При выходе из области действия текущей связи старое значение восстанавливается. При использовании такой свободной переменной адрес SPECIAL-ячейки может быть доступен другим функциям.
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.
Теперь про функциональные аргументы.
MAPLIST может быть определен следующим образом:
(DEFUN MAPLIST
(LAMBDA (L FN)
(COND
((NULL L) NIL)
(T (CONS (FN L)
(MAPLIST (CDR L) FN) ))
)   )    ) 
Переменная FN — это связанный функциональный аргумент. Дело в том, что его значение — определение функции.
Трассировка скомпилированных программ
Trace — работает с компилированными программами согласно следующим ограничениям:

  1. Trace может быть объявлена после компиляции и не требует повторной компиляции программы.
  2. Trace не отслеживает прямые переходы на функции, созданные в обход атомов, т.е. выделенные на уровне ассемблера или кода без встраивания в общую информационную систему Лиспа — таблицу символов, хранящую свойства атомов.

«В правильном выражении всегда достаточно скобок, чтобы избежать синтаксической неоднозначности» Используя это утверждение Хендерсона как эпиграф, а в Лиспе со скобками все в порядке, можно уверенно приступить к определению собственно компилятора.

Компиляция. Венский метод. Операционная семантика
Функциональный подход к программированию наиболее убедительно выражен в Венской методике определения языков программирования. Эта методика разработана в конце 60-х годов. Основная идея — использование абстрактного синтаксиса и абстрактной машины при определении семантики языка программирования. Конкретный синтаксис языка отображается в абстрактный — анализ, а абстрактная машина может быть реализована с помощью конкретной машины — кодогенерация, причем и то, и другое может иметь небольшой объем и невысокую сложность. Сущность определения языка концентрируется в виде так называемой семантической функции языка, выполняющей переход от абстрактного синтаксиса к абстрактной машинетрансляцию.
При такой архитектуре компилятор можно рассматривать как три комплекта функций, обеспечивающих анализ программы, ее трансляцию и кодогенерацию. Главная задача анализа — обнаружить основные понятия и выделить, вывести или вычислить по тексту программы значения компонентов структуры, представляющей собой абстрактный синтаксис программы. Эта работа сводится к набору распознавателей и селекторов, названия которых могут быть выбраны в зависимости от смысла понятий, составляющих программу, а реализация варьируется в зависимости от конкретного синтаксиса языка. Тогда при любом конкретном синтаксисе разбор программы выполняется тем же самым определением, что и анализ ее абстрактного представления, которое и грает роль спецификации. Любое определение анализа выглядит как перебор распознавателей, передающих управление композициям из селекторов, выбирающих существенные компоненты из анализируемой программы и заполняющих поля определенной структуры или значениями, или программами их вычисления. Содержимое полей предназначено для генерации кода программы, эквивалентной исходному тексту программы, а заодно и ее абстрактной структуре. Например, если форму PROG рассматривать как представление абстрактного синтаксиса для подмножества языка Паскаль, содержащего переменные, константы, арифметические операции и сравнения, пустой оператор, присваивание, последовательное исполнение операторов, условный оператор и безусловный переход goto, то необходим набор распознавателей, выявляющих эти понятия, и селекторов, выделяющих их характеристики. Селекторы имеют смысл лишь при истинности соответствующего распознавателя.
Использование списочных форм в качестве абстрактного синтаксиса позволяет все распознаватели свести к анализу головы списка.


Таблица 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(cdr fm))))). Такие определения практически не требуют отладки, работают с первого предъявления.
Определение семантической функции, обеспечивающей корректную трансляцию абстрактного синтаксиса программы в ее абстрактный код, требует реализации соответствия между именами и их значениями в зависимости от контекста и предшествующих определений.
При интерпретации такое соответствие представлялось ассоциативным списком, в котором хранятся связи вида Имя-Смысл, преобразуемые по принципу стека, естественно отражающего динамику вызова функций. При компиляции не принято сохранять имена на время исполнения программы: их роль выполняют сопоставленные именам адреса. Поэтому вместо а-списка вида ((а . 1)(в . 2)(с . 3)...) применяется два списка (а в с ...) и (1 2 3 ...), хранящих имена и их значения на согласованных позициях. Обрабатываются эти два списка синхронно: оба удлиняются или сокращаются на одинаковое число элементов.
Можно переписать Eval-Apply с соответствующей коррекцией и определить функцию подстановки, заменяющую имена их значениями из синхронного списка.
Определение Eval-Apply особенно компактно в стиле p-списка. Иерархию определений можно организовать с помощью блоков Flet со списками определений для шаблонов (перем конст плюс равно) и отдельно для (пусто присвоить шаги если пока).
Важно обратить внимание на учет изменения контекста при последовательном выполнении шагов программы, а также на несовпадение порядка в тексте с очередностью выполнения композиций функций. Формально операторы могут рассматриваться как функции, преобразующие полное состояние памяти V. Пусть функция E списочному представлению оператора сопоставляет эквивалентную ему Лисп-функцию, вызываемую в контексте (declare (special N)).


Таблица 8.2. Примеры функциональной реализации операторов и выражений.

c

(lambda (v)c)

(конст C)

x

(lambda (v) (assoc-i X N v))
N — свободная переменная, задающая список имен, известных в программе

(перем X)

(A1 + A2)

(lambda (v) (+(Е А1)(У А2)))

(плюс А1 А2)

(A1 = A2)

(lambda (v)(=(Е А1)(У А2)))

(равно А1 А2)

(пусто)

(lambda (v)v)
Состояние памяти неизменно

x := a;

Замена происходит по указанному адресу
(lambda (v)(replace N v X (E A)))

(присвоить X A)

S1; S2;

(lambda (v) (E S2 (E S1 v)))

(шаги S1 S2)

if e then ST else SF;

(lambda (v) (funcall
(cond (((E P)v)
(E S1))
(T(E S2)) ) v)

(если P ST SF)

while e do 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)))
))

(пока P S)

Денотационная семантика ЯП (математическая) определяет семантику языка в терминах соотношений между множествами. При задании операционной семантики важно отследить корректность обработки порождаемых структур данных, что может быть сформулировано как свойство чистого результата. Согласно этому свойству задана четкая дисциплина манипуляций со стеком при обработке данных: каждая операция берет из стека в точности все свои аргументы и обязательно располагает в нем свой единственный результат.
При определении компилятора на уровне абстрактной машины должно быть выделено описание реализационного минимума языка Лисп, послужившего базой для раскрутки Лиспа и основой для функционального программирования. Необходимо лишь ввести некоторые ограничения, гарантирующие при переходе к низкоуровневому программированию сохранение важнейших свойств функциональных программ. Эти ограничения формулируются как чистый результат правильного выражения:

  • все аргументы убраны из стека;
  • результат выражения записан в стек.

 

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