Общий подход к обработке символьных выражений и представлению программ
Приведенные ранее описания и правила записи функций и выражений в этой лекции получат более строгое определение. Начнем с синтаксического обобщения. Представим результаты предыдущей лекции в виде простых БНФ (Формул Бекуса-Наура), позволяющих задать грамматику представления функций и значений в виде системы правил. Каждое правило отдельному понятию сопоставляет ( : : = ) варианты ( | ) его изображения:
Синтаксис данных в Лиспе сводится к правилам представления атомов и S-выражений, включая списки.
атом ::= БУКВА конец_атома
Это правило констатирует, что атомы начинаются с буквы.
конец_атома ::= пусто | БУКВА конец_атома | цифра конец_атома
Это правило констатирует, что после первой литеры в изображении атома могут быть как буквы, так и цифры.
В Лиспе атомы — это мельчайшие частицы. Их разложение по литерам не имеет смысла.
S-выражение ::= атом | (S-выражение . S-выражение) | (S-выражение ... )
Данное правило констатирует, что S-выражения — это или атомы, или узлы из пары S-выражений, или списки из S-выражений. (Три точки означают, что допустимо любое число вхождений предшествующего вида объектов, включая ни одного.)
Согласно такому правилу "()" есть допустимое S-выражение. Оно в языке Лисп по соглашению эквивалентно атому Nil.
Базовая система представления данных — точечная нотация, хотя на практике запись в виде списков удобнее. Любой список можно представить точечной нотацией:
() = Nil (a . Nil) = (a) - - - (a1 . ( ... (aK . Nil) ... )) = (a1 ... aK)
Такая единая структура данных оказалась вполне достаточной для представления сколь угодно сложных программ. Дальнейшее определение языка Лисп можно рассматривать как восходящий процесс генерации семантического каркаса, по ключевым позициям которого распределены семантические действия по обработке программ.
Другие правила представления данных нужны лишь при расширении и специализации лексики языка (числа, строки, имена особого вида и т.п.). Они не влияют ни на общий синтаксис языка, ни на строй его понятий, а лишь характеризуют разнообразие сферы его конкретных приложений.
Синтаксис программ является конкретизацией синтаксиса данных, а именно — выделением из класса S-выражений подкласса вычислимых выражений (форм), т.е. данных, имеющих смысл как выражения языка и приспособленных к вычислению. Внешне это выглядит как объявление объектов, заранее известных в языке, и представление разных форм, вычисление которых обладает определенной спецификой.
Выполнение программы устроено как интерпретация данных, представляющих выражения, имеющие значение. Ниже приведены синтаксические правила для обычных конструкций, к которым относятся идентификаторы, переменные, константы, аргументы, формы и функции. (Правила упорядочены по сложности взаимосвязи формул.)
идентификатор ::= атом
Идентификатор — это подкласс атомов, используемых при именовании неоднократно используемых объектов программы — функций и переменных. Предполагается, что идентифицируемые объекты размещаются в памяти так, что по идентификатору их можно найти.
Понятие "идентификатор" выделено для того, чтобы по мере развития определения атома не требовалось на все виды атомов искусственно распространять семантику вычислений. (Например, у Бекуса в его знаменитой статье про "бутылочное горлышко" рассматриваются числа как представление операций доступа [20].)
форма ::= константа | переменная | (функция аргумент ... ) | (COND (форма форма) (форма форма) ... )
константа ::= (QUOTE S-выражение) | 'S-выражение
переменная ::= идентификатор
Переменная — это подкласс идентификаторов, которым сопоставлено многократно используемое значение, ранее вычисленное в подходящем контексте. Подразумевается, что одна и та же переменная в разных контекстах может иметь разные значения.
Таким образом, класс форм — это объединение класса переменных и подкласса списков, начинающихся с QUOTE, COND или с представления некоторой функции.
аргумент ::= форма
Форма — это выражение, которое может быть вычислено. Форма, представляющая собой константу, выдает эту константу как свое значение.
В таком случае нет необходимости в вычислениях, независимо от вида константы. Константные значения могут быть любой сложности, включая вычислимые выражения. Чтобы избежать двусмысленности, предлагается константы изображать как результат специальной функции QUOTE, блокирующей вычисление. Представление констант с помощью QUOTE устанавливает границу, далее которой вычисление не идет. Использование апострофа "'" — просто сокращенное обозначение для удобства набора внешних форм. Константные значения аргументов характерны при тестировании и демонстрации программ.
Если форма представляет собой переменную, то ее значением должно быть S-выражение, связанное с этой переменной до момента вычисления формы. (Динамическое связывание, в отличие от традиционного правила, требующего связывания к моменту описания формы, т.е. статическое связывание.)
Третья ветвь определения гласит, что можно написать функцию, затем перечислить ее аргументы, и все это как общий список заключить в скобки.
Аргументы представляются формами. Это означает, что допустимы композиции функций. Обычно аргументы вычисляются в порядке вхождения в список аргументов. Позиция "аргумент" выделена для того, чтобы было удобно в дальнейшем локализовывать разные схемы обработки аргументов в зависимости от категории функций. Аргументом может быть любая форма, но метод вычисления аргументов может варьироваться. Функция может не только учитывать тип обрабатываемого данного, но и управлять временем обработки данных, принимать решения по глубине и полноте анализа данных, обеспечивать продолжение счета при исключительных ситуациях и т.п.
Последняя ветвь определяет формат условного выражения. Согласно этому формату условное выражение строится из размещенных в двухэлементном списке синтаксически различимых позиций для пропозициональных термов и обычных форм. Двухэлементные списки из определения условного выражения рассматриваются как представление предиката и соответствующего ему S-выражения. Значение условного выражения определяется перебором предикатов по порядку, пока не найдется форма, значение которой отлично от Nil, что означает логическое значение "истина".
Строго говоря, такая форма должна быть найдена непременно. Тогда вычисляется S-выражение, размещенное вторым элементом этого же двухэлементного списка. Остальные предикаты и формы условного выражения не вычисляют (логика Мак-Карти), их формальная корректность или определенность не влияют на существование результата.
Разница между пропозициональными и обычными формами заключается лишь в трактовке их результатов. Любая форма может играть роль предиката.
функция ::= название | (LAMBDA список_переменных форма) | (LABEL название функция)
список_переменных ::= (переменная ... )
название ::= идентификатор
Название — это подкласс идентификаторов, определение которых хранится в памяти, но оно может не подвергаться влиянию контекста вычислений.
Таким образом, класс функций — это объединение класса назва-ний и подкласса трехэлементных списков, начинающихся с LAMBDA или LABEL.
Функция может быть представлена просто именем. В таком случае ее смысл должен быть заранее известен. Функция может быть введена с помощью лямбда-выражения, устанавливающего соответствие между аргументами функции и связанными переменными, упоминаемыми в теле ее определения (в определяющей ее форме). Форма из определения функции может включать переменные, не включенные в лямбда-список, — так называемые свободные переменные. Их значения должны устанавливаться на более внешнем уровне. Если функция рекурсивна, то следует объявить ее имя с помощью специальной функции
LABEL. (Используемая в примерах DEFUN, по существу, совмещает эффекты LABEL и LAMBDA.)
форма ::= переменная | (QUOTE S-выражение) | (COND (форма форма) ... (форма форма)) | (функция аргумент ... )
аргумент ::= форма
переменная ::= идентификатор
функция ::= название | (LAMBDA список_переменных форма) | (LABEL название функция)
список_переменных ::= (переменная ... ) название ::= идентификатор
идентификатор ::= атом S-выражение ::= атом | (S-выражение . S-выражение) | (S-выражение ...)
атом ::= БУКВА конец_атома
конец_атома ::= пусто | БУКВА конец_атома | цифра конец_атома
