globalf5-240972240972 (850810), страница 8
Текст из файла (страница 8)
Их разложение по литерам44Л.В. ГородняяОсновы функционального программированияне имеет смысла.S-выражение ::= атом| (S-выражение . S-выражение)| (S-выражение ... )Данное правило констатирует, что S-выражения — это или атомы, илиузлы из пары S-выражений, или списки из S-выражений. (Три точкиозначают, что допустимо любое число вхождений предшествующеговида объектов, включая ни одного.)Согласно такому правилу "()" есть допустимое S-выражение. Оно вязыке Лисп по соглашению эквивалентно атому NIL.Базовая система представления данных — точечная нотация, хотя напрактике запись в виде списков удобнее. Любой список можнопредставить точечной нотацией:() = NIL(a . NIL) = (a)--(a1 . ( ... (aK .
NIL) ... )) = (a1 ... aK)Такая единая структура данных оказалась вполне достаточной дляпредставления сколь угодно сложных программ. Дальнейшееопределение языка Лисп можно рассматривать как восходящий процессгенерации семантического каркаса, по ключевым позициям которогораспределены семантические действия по обработке программ.Другие правила представления данных нужны лишь при расширении испециализации лексики языка (числа, строки, имена особого вида ит.п.).
Они не влияют ни на общий синтаксис языка, ни на строй егопонятий, а лишь характеризуют разнообразие сферы его конкретныхприложений.Синтаксис программ является конкретизацией синтаксиса данных, аименно — выделением из класса S-выражений подкласса вычислимыхвыражений (форм), т.е. данных, имеющих смысл как выражения языка иприспособленных к вычислению.
Внешне это выглядит как объявлениеобъектов, заранее известных в языке, и представление разных форм,45Л.В. ГородняяОсновы функционального программированиявычисление которых обладает определенной спецификой.Выполнение программы устроено как интерпретация данных,представляющих выражения, имеющие значение. Ниже приведенысинтаксические правила для обычных конструкций, к которымотносятся идентификаторы, переменные, константы, аргументы, формыи функции. (Правила упорядочены по сложности взаимосвязи формул.)идентификатор ::= атомИдентификатор — это подкласс атомов, используемых при именованиинеоднократно используемых объектов программы — функций ипеременных.
Предполагается, что идентифицируемые объектыразмещаются в памяти так, что по идентификатору их можно найти.Понятие "идентификатор" выделено для того, чтобы по мере развитияопределения атома не требовалось на все виды атомов искусственнораспространять семантику вычислений. (Например, у Бекуса в егознаменитой статье про "бутылочное горлышко" рассматриваются числакак представление операций доступа [20].)форма ::= константа| переменная| (функция аргумент ...
)| (COND (форма форма) (форма форма) ... )константа ::= (QUOTE S-выражение)| 'S-выражениепеременная ::= идентификаторПеременная — это подкласс идентификаторов, которым сопоставленомногократно используемое значение, ранее вычисленное в подходящемконтексте. Подразумевается, что одна и та же переменная в разныхконтекстах может иметь разные значения.Таким образом, класс форм — это объединение класса переменных иподкласса списков, начинающихся с QUOTE,COND или спредставления некоторой функции.46Л.В.
ГородняяОсновы функционального программированияаргумент ::= формаФорма — это выражение, которое может быть вычислено. Форма,представляющая собой константу, выдает эту константу как своезначение. В таком случае нет необходимости в вычислениях,независимо от вида константы.
Константные значения могут бытьлюбой сложности, включая вычислимые выражения. Чтобы избежатьдвусмысленности, предлагается константы изображать как результатспециальнойфункцииQUOTE,блокирующейвычисление.Представление констант с помощью QUOTE устанавливает границу,далее которой вычисление не идет. Использование апострофа "'" —просто сокращенное обозначение для удобства набора внешних форм.Константные значения аргументов характерны при тестировании идемонстрации программ.Если форма представляет собой переменную, то ее значением должнобыть S-выражение, связанное с этой переменной до моментавычисления формы. ( Динамическое связывание, в отличие оттрадиционного правила, требующего связывания к моменту описанияформы, т.е.
статическое связывание.)Третья ветвь определения гласит, что можно написать функцию, затемперечислить ее аргументы, и все это как общий список заключить вскобки.Аргументы представляются формами. Это означает, что допустимыкомпозиции функций. Обычно аргументы вычисляются в порядкевхождения в список аргументов. Позиция "аргумент" выделена для того,чтобы было удобно в дальнейшем локализовывать разные схемыобработки аргументов в зависимости от категории функций.Аргументом может быть любая форма, но метод вычисления аргументовможет варьироваться.
Функция может не только учитывать типобрабатываемого данного, но и управлять временем обработки данных,принимать решения по глубине и полноте анализа данных,обеспечивать продолжение счета при исключительных ситуациях и т.п.Последняя ветвь определяет формат условного выражения. Согласноэтому формату условное выражение строится из размещенных вдвухэлементном списке синтаксически различимых позиций для47Л.В. ГородняяОсновы функционального программированияпропозициональных термов и обычных форм.
Двухэлементные спискииз определения условного выражения рассматриваются какпредставление предиката и соответствующего ему S-выражения.Значение условного выражения определяется перебором предикатов попорядку, пока не найдется форма, значение которой отлично от NIL,что означает логическое значение "истина".
Строго говоря, такая формадолжна быть найдена непременно. Тогда вычисляется S-выражение,размещенное вторым элементом этого же двухэлементного списка.Остальные предикаты и формы условного выражения не вычисляют(логика Маккарти), их формальная корректность или определенность невлияют на существование результата.Разница между пропозициональными и обычными формамизаключается лишь в трактовке их результатов.
Любая форма можетиграть роль предиката.функция ::= название| (LAMBDA список_переменных форма)| (LABEL название функция)список_переменных ::= (переменная ... )название ::= идентификаторНазвание — это подкласс идентификаторов, определение которыххранится в памяти, но оно может не подвергаться влиянию контекставычислений.Таким образом, класс функций — это объединение класса назва-ний иподкласса трехэлементных списков, начинающихся с LAMBDA илиLABEL.Функция может быть представлена просто именем. В таком случае еесмысл должен быть заранее известен. Функция может быть введена спомощью лямбда-выражения, устанавливающего соответствие междуаргументами функции и связанными переменными, упоминаемыми втеле ее определения (в определяющей ее форме).
Форма из определенияфункции может включать переменные, не включенные в лямбда-список,— так называемые свободные переменные. Их значения должны48Л.В. ГородняяОсновы функционального программированияустанавливаться на более внешнем уровне. Если функция рекурсивна,то следует объявить ее имя с помощью специальной функции LABEL.(Используемая в примерах DEFUN, по существу, совмещает эффектыLABEL и LAMBDA.)форма ::= переменная| (QUOTE S-выражение)| (COND (форма форма) ...
(форма форма))| (функция аргумент ... )аргумент ::= формапеременная ::= идентификаторфункция ::= название| (LAMBDA список_переменных форма)| (LABEL название функция)список_переменных ::= (переменная ... )название ::= идентификаторидентификатор ::= атомS-выражение ::= атом| (S-выражение . S-выражение)| (S-выражение ...)атом ::= БУКВА конец_атомаконец_атома ::= пусто| БУКВА конец_атома| цифра конец_атомаУниверсальная функцияИнтерпретация или универсальная функция — это функция, котораяможет вычислять значение любой формы, включая формы, сводимые квычислению произвольной заданной функции, применяемой каргументам, представленным в этой же форме, по доступному49Л.В.
ГородняяОсновы функционального программированияописанию данной функции. (Конечно, если функция, которой предстоитинтерпретироваться, имеет бесконечную рекурсию, интерпретациябудет повторяться бесконечно.)Определим универсальную функцию eval от аргумента expr —выражения, являющегося произвольной вычислимой формой языкаЛисп.Универсальная функция должна предусматривать основные видывычисляемых форм, задающих значения аргументов, а такжепредставления функций, в соответствии со сводом приведенных вышеправил языка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
