Учебник по Lisp (Материалы к экзамену и коллоквиумам 2013-го года), страница 7

argK))Результат применения "fn" к аргументам "arg1, ..., argK".ВычислениеЯвное определение такой функции позволяет достичь четкости механизмовобработки Лисп-программ.(eval '((LAMBDA (x y) (CONS (CAR x) y)) '(A B) ‘(C D) ))= (A C D)Вводим две основные функции eval и apply для обработки форм и обращения кфункциям соответственно. Каждая из этих функций использует ассоциативныйсписок для хранения связанных имен - значений переменных и определенийфункций.

Сначала этот список пуст.Вернемся к синтаксической сводке вычислимых форм.42Таблица. Синтаксическая сводка программ на языке Лисп.<форма> ::= <переменная>| (QOUTE <S-выражение>)| (COND (<форма> <форма>) ... (<форма> <форма>))| (<функция> <аргумент> ... <аргумент>)<аргумент> ::= <форма><переменная> ::= <идентификатор><функция> ::= <название>| (LAMBDA <список_переменных> <форма>)| (DEFUN <название> <функция>)<список_переменных> ::= (<переменная> ... )<название> = <идентификатор><идентификатор> ::= <атом>Каждой ветви этой сводки соответствует ветвь универсальной функции:(DEFUN eval0 (e) (eval e '((Nil .

Nil))))Вспомогательная функция eval0 понадобилась, чтобы в eval ввестинакапливающий параметр – ассоциативный список, в котором будут хранитьсясвязи между переменными и их значениями и названиями функций и ихопределениями.(defun eval(e a) (COND( (atom e) (cdr(assoc e a)) )( (eq (car e) 'QUOTE) (cadr e))((eq(car e) 'COND) (evcon(cdr e) a))( T (apply (car e) (evlis(cdr e) a) a) )) )(defun apply (fn x a) (COND((atom fn)(cond((eq fn 'CAR)(caar x))((eq fn 'CDR)(cdar x))((eq fn 'CONS) (cons (car x)(cadr x)) )((eq fn 'ATOM)(atom (car x)) )((eq fn 'EQ) (eq (car x)(cadr x)) )((QUOTE T) (apply (eval fn a) x a)) ) ))((eq(car fn)'LAMBDA) (eval (caddr fn) (pairlis (cadr fn) x a) ))((eq (car fn) 'DEFUN) (apply (caddr fn) x (cons (cons (cadr fn)(caddr fn)) a)))))43Упражнение: Это определение можно немого уточнить, если а-список присвязывании названий функций поплнять не в начале, а в конце.assoc и pairlis уже определены ранее.(DEFUN evcon (c a) (COND((eval (caar c) a) (eval (cadar c) a) )(T(evcon (cdr c) a)) ))*) Примечание.

Не допускается отсутствие истиного предиката, т.е. пустого C.(DEFUN evlis (m a) (COND((null m) Nil )(T(cons(eval (car m) a)(evlis(cdr m) a))) )При(DEFUN eval0 (e) (eval e ObList ))определения функций могут накапливаться в системной переменной ObList, тоесть работать как глобальные определения. ObList обязательно должна содержатьглобальное определение встроенной константы Nil, можно и сразу разместить вней T.Поясним ряд пунктов этих определений.Первый аргумент eval - форма. Если она - атом, то этот атом может быть толькоименем переменной, а значение переменной должно бы уже находиться вассоциативном списке.Если CAR от формы - QUOTE, то она представляет собой константу, значениекоторой вычисляется как CADR от нее самой.Если CAR от формы - COND, то форма - условное выражение.

Вводимвспомогательную функцию EVCON, (определение ее будет дано ниже),которая обеспечивает вычисление предикатов (пропозициональных термов) попорядку и выбор формы, соответствующей первому предикату, принимающемузначение "истина". Эта форма передается EVAL для дальнейших вычислений.Все остальные случаи рассматриваются как список из функции споследующими аргументами.44Вспомогательная функция EVLIS обеспечивает вычисление аргументов,затем представление функции и список вычисленных значений аргументовпередаются функции APPLY.Первый аргумент apply - функция.

Если она - атом, то существует двевозможности: атом представляет одну из элементарных функций (car cdr consatom eq). В таком случае соответствующая ветвь вычисляет значение этойфункции на заданных аргументах. В противном случае, этот атом - имя ранеезаданного определения, которое можно найти в ассоциативном списке.Если функция начинается с LAMBDA, то ее аргументы попарно соединяютсясо связанными переменными, а тело определения (форма из лямбдавыражения) передается как аргумент функции eval для дальнейшей обработки.Если функция начинается с DEFUN, то ее название и определение соединяютсяв пару и полученная пара размещается в ассоциативном списке, чтобы имяфункции стало определенным при дальнейших вычислениях.

Они произойдут какрекурсивный вызов apply, которая вместо имени функции теперь работает с ееопределением при более полном ассоциативном списке - в нем теперь размещеноопределение имени функции. Поскольку определение размещается на "верху"стека, оно становится доступным для всех последующих переопределений, тоесть работает как локальный объект. Глобальные объекты, такие какобеспечивает псевдо-функция DEFUN, устроены немного иначе, что будетрассмотрено в следующей лекции.Определение универсальной функции является важным шагом, показывающимодновременно и механизмы реализации языков программирования, итехнику функционального программирования на любом языке.

Пока еще неописаны многие другие особенности языка Лисп, которые будут рассмотреныпозднее. Но все они будут увязаны в единую картину, основа которой согласуетсяс этим определением.1) В строгой теории элементарного Лиспа все функции следует определятьвсякий раз, как они используются. На практике это неудобно.

Реальные системыимеют большой запас встроенных функций (более тысячи в Clisp-е), известныхязыку, и возможность присоединения такого количества новых функций, какоепонадобится.2) В чистом языке Лисп базисные функции CAR и CDR не определены дляатомарных аргументов.

Такие функции, имеющие осмысленный результат не навсех значениях естественной области определения, называют частичными.Отладка и применение частичных функций требует большего контроля, чемработа с тотальными, всюду определенными функциями.Во многих Лисп-системах все элементарные функции вырабатывают результат ина списках, и на атомах, но его смысл зависит от системных решений, что можетсоздавать трудности при переносе программ на другие системы. Базисныйпредикат EQ всегда имеет значение, но смысл его на неатомарных аргументах45будет более понятен после знакомства со структурами данных, используемымидля представления списков в машине.3) Для расширений и диалектов языка Лисп характерно большое разнообразиеусловных форм, конструкций выбора, ветвлений и циклов, практически безограничений на их комбинирование.

Форма COND выбрана для начальногознакомства как наиболее общая. За редким исключением в Лисп-системе нетнеобходимости писать в условных выражениях (QUOTE T) или (QUOTE NIL).Вместо них используются встроенные константы T и Nil соответственно.4) В реальных системах функционального программирования обычноподдерживается работа с целыми, дробными и вещественными числами впредельно широком диапазоне, а также работа с кодами и строками. Такиеданные, как и атомы, являются минимальными объектами при организацииобработки нформации, но отличаются от атомов тем, что их смысл задан ихсобственным представлением непосредственно. Их понимание не требуетассоциаций или связывания.

Поэтому и константы такого вида не требуютпрефикса в виде апострофа.Предикаты и истинность в ЛиспеВ Лиспе есть два атомных символа, которые представляют истину и ложьсоответственно. Эти два атома - T и NIL. Эти символы - действительныезначения всех предикатов в системе. Главная причина в удобстве кодирования.Во многих случаях достаточно отличать произвольное значение от пустогосписка.Не существует формального различия между функцией и предикатом в Лиспе.Предикат может быть определен как функция со значениями либо T либо NIL.Можно использовать форму, не являющуюся предикатом там, где требуетсяпредикат: предикатная позиция условного выражения или аргумент логическогопредиката.

Семантически любое S-выражение, только не NIL, будетрассматриватсья как истинное в таком случае. Предикат EQ ведет себяследующим образом:1) Если его аргументы различны, значением EQ является NIL.2)Если оба его аргументы являются одним и тем же атомом, то значение - Т.3) Если значения одинаковы, но не атомы, то его значение T или NIL взависимости от того, идентично ли представление аргументов в памяти.4) Значение EQ всегда T или NIL. Оно никогда не бывает неопределено, дажеесли аргументы плохие.Выполнено достаточно строгое построение совершенно формальнойматематической системы, называемой “Элементарный ЛИСП”.Составляющие этой формальной системы:461) Множество символов, называемых S-выражениями.2) Система функциональных обозначений для основных понятий, трубемых припрограммировании обрботки S-выражений.3) Формальное представление функциональных обозначений в виде Sвыражений.4) Универсальная функция (записанная в виде S-выражения), интерпретирующаяобращение произвольной функции, записанной как S-выражение, к ееаргументам.5) Система базовых функций, обеспечивающих техническую поддержкуобработки S-выражений, и специальных функций, обеспечивающих управлениевычислениями.Выполненное определение универсальной функции – макетный образец Лиспсистемы, основные черты которой унаследованы многими системамипрограммирования.Выводы:-Универсальная функция – это функция, которая может вычислять значениелюбой формы и представляет собой инетрпретатор в миниатюре.-При реализации универсальной функции необходимо учитывать способпредставления контекста и виды вычисляемых форм.-Контекст удобно представлять с помощью ассоциативных списков.-Универсальная функция должна предусматривать основные видывычисляемых форм, задающих значения аргументов, а также представленияфункций, в соответствии со сводом вышеприведенных правил языка.476.

Отображения и функционалыВ этом параграфе мы рассмотрим следующие механизмы:- отображения,- числа и строки,- безымянные определения функций,- фильтры и свертки (редукции).Отображения обычно используются при анализе и обработке данных, представляющихинформацию разной природы. Нумерация, кодирование, идентификация, шифрование каждый их этих процессов использует исходное множество номеров, текстов,идентификаторов, сообщений, по которым конкретная отображающая функция находитзанумерованный объект, строит закодированный текст, выделяет идентифицированныйфрагмент, получает зашифрованное сообщение. Таким же образом работает любое введениеобозначений - от знака происходит переход к его смыслу.

Перевод с одного языка на другой,фотография, киносъемка, спортивный репортаж - все это можно рассматривать как примерыотображений.Отображения - ключевой механизм информатики. Построение любой информационнойсистемы сопровождается определением и реализацией большого числа отображений. Вопервых, выбираются данные, с помощью которых представляется информация. В результате,по данным можно восстановить представленную ими информацию - извлечь информацию изданных. Например, по символам записи числа можно восстановить его величину. Во-вторых,конструируется набор структур, достаточный для размещения и обработки данных в памятикомпьютера.