Структура LISP-программы
Как использовать список в качестве базовой структуры данных, понятно. Сложнее представить себе, как можно организовать программу или выражение программы в виде списка. Например, список: (+ X Y) представляет математическое выражение в форме:
(<функция> <1-й аргумент> <2-й аргумент>)
Которое обозначает сложение двух чисел. Такой метод обозначений (нотация) отличается от привычного нам обозначения функции n переменных в виде 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 не чувствительны к регистру символов, хотя и возможно так сконфигурировать исполнительную систему, что она станет по-разному воспринимать символы верхнего и нижнего регистров.
Функции, их вычисление и проблема цитирования в 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]).