Основы функционального программирования

       

Требования к компиляции Лисп-программ


Рассмотрим особенности Лисп-программ, которые необходимо учесть при определении компилятора и подготовке программ к компиляции.

Прежде всего — свободные переменные. Переменная связана, если она встречается в списке 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 не отслеживает прямые переходы на функции, созданные в обход атомов, т.е. выделенные на уровне ассемблера или кода без встраивания в общую информационную систему Лиспа — таблицу символов, хранящую свойства атомов.


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


Содержание раздела







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий