|
4.3.2.
Структура LISP-программы
Как использовать
список в качестве базовой структуры данных, понятно. Сложнее представить себе,
как можно организовать программу или выражение программы в виде списка.
Например, список
(+ X Y) представляет
математическое выражение в форме
(<функция>
<1-й аргумент> <2-й аргумент>),
которое обозначает
сложение двух чисел. Такой метод обозначений (нотация) отличается от привычного
нам обозначения функции п переменных в виде f(x1, ... xn).
Но возникает вопрос, как компилятор или интерпретатор отличает данные от программы,
если и то и другое представлено списками.
- Необходимо иметь возможность
определить значение такого выражения— например, значение выражения
( + X Y). Для этого нужно отыскать определение функции (в данном случае —
функции +). В этом определении должна содержаться та последовательность элементарных
операций, которую нужно применить к аргументам, чтобы определить значение
функции.
- Нужно иметь средства
сформировать определение функции и применить это определение к аргументам,
т.е. к действительным, а не формальным параметрам. Механизм определения функции
и приложения функции базируется на логической системе, названной лямбда-исчислением
(см. [Church, 1941]). Лямбда-исчисление является скорее функциональным,
чем исчислением отношений, и в этом состоит различие между ним и исчислением
предикатов первого порядка. В функциональном исчислении первичным понятием
является отношение "многие-к-одному", а не "многие-ко-многим".
Так, отец — это функциональное отношение, а брат — более общее
отношение, поскольку каждый человек может иметь только одного отца, а братьев
может быть несколько. Ниже в этой главе мы более подробно остановимся на связях
между языком LISP и лямбда-исчислением.
- Нужно располагать средствами
доступа к текущим значениям переменных (или формальных параметров),
таких как X и Y. Вычисление каждого символического выражения выполняется в
контексте формирования переменных. Нужно располагать средствами сохранения
и восстановления этого контекста при вычислении значений сложных символических
выражений, т.е. вычисления и комбинирования значений содержащихся в них подвыражений.
- При вычислении сложных
символических выражений, когда необходимо вычислять значения его компонентов,
которые являются сложными выражениями, нужно располагать средствами сохранять
текущее выражение и промежуточные результаты. Необходимо также обладать
средствами копирования символических выражений.
- Нужно уметь подавлять
вычислительную обработку списков, которые не являются операторами программы,
а структурами данных. Например, не нужно пытаться вычислять выражение, подобное
следующему:
((1
2 3)(4 5 6)(7 8 9))
и пытаться
отыскать определение функции (1 2 3).
Для этого
существует специальная форма выражения (QUOTE X) для любых X, которая возвращает
X. Точно такое же действие выполняется и выражением (quote X).
Современные
версии LISP не чувствительны к регистру символов, хотя и возможно так сконфигурировать
исполнительную систему, что она станет по-разному воспринимать символы верхнего
и нижнего регистров.
4.3.
Функции, их вычисление и проблема цитирования в CLIPS
Существуют
два основных метода разрешения проблемы цитирования, т.е. предотвращения интерпретации
данных как функций или выражений. Один метод заключается в том, чтобы в число
системных функций ввести специальную функцию, которая рассматривается интерпретатором
как указание не обрабатывать последующий список. Такой системной функцией в
LISP является QUOTE. Другой метод состоит в том, чтобы по умолчанию
подавлять механизм оценивания значения (вычисления) до тех пор, пока специальная
синтаксическая конструкция его не запустит. В языке CLIPS использован именно
такой метод.
Например,
в CLIPS можно следующим образом определить функцию:
(deffunction
between(?lb ?value ?ub)
(or
(> lib ?value) (> ?value ?ub))))
Эта
функция определяет, попало ли заданное целочисленное значение в диапазон между
указанными нижним и верхним пределами. Знак вопроса, предшествующий именам,
говорит интерпретатору CLIPS, что выражения ?lb, ?value и ?ub являются переменными
и их не нужно оценивать.
Общепринятым
методом реализации функциональных языков типа LISP является использование четырехстековой
машины, за которой закрепилось наименование SECD-машины. В четырех стеках машины
отслеживаются промежуточные результаты, значения переменных, текущее выражение
и копии текущего состояния процесса вычислений сложного выражения, которые нужны,
чтобы восстановить состояние после завершения вычисления вложенного выражения
(подвыражения). Не вдаваясь в подробности, отметим, что процесс оценивания символического
выражения в такой машине — это не что иное, как реализация базовой операции
приложения функции, как это определено в лямбда-исчислении (см., например, [Henderson,
1980], [Glaser et al., 1984]).
|
