WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 9 |

(DEFUN pairlis (x y al) (COND ((null x) al) ((QUOTE T) (CONS (CONS (CAR x) (CAR Y) ) (pairlis (CDR x) (CDR y) al) ) ) ) ) (pairlis '(A B C) '(u t v) '((D. y)(E. y))) ;= ((A. u)(B. t)(C. v)(D. y)(E. y)) ASSOC - функция двух аргументов x и al. Если al - ассоциативный список, подобный тому, что формирует функция pairlis, то assoc выбирает из него первую пару, начинающуюся с x. Таким образом, это функция поиска определения или значения по таблице, реализованной в форме ассоциативного списка.

(DEFUN assoc (x al) (COND ((equal x (CAAR al)) (CAR al)) ((QUOTE T) (assoc x (CDR al)) ) ) ) (assoc 'B '((A. (m n)) (B. (CAR x)) (C. w) (B. (QUOTE T)))) ;= (B. (CAR x)) Частичная функция - рассчитана на наличие ассоциации.

SUBLIS - функция двух аргументов al и y, предполагается, что первый из аргументов AL устроен как ассоциативный список вида ((u1. v1)... (uK. vK)), где u есть атомы, а второй аргумент Y - любое S-выражение. Действие sublis заключается в обработке Y, такой что вхождения переменных Ui, связанные в ассоциативном списке со значениями Vi, заменяются на эти значения. Другими словами в S-выражении Y вхождения переменных U заменяются на соответствующие им V из списка пар AL. Вводим вспомогательную функцию SUB2, обрабатывающую атомарные S-выражения, а затем - полное определение SUBLIS:

(DEFUN sub2 (al z) (COND ((null al) z) ((equal (CAAR al) z) (CDAR al)) ((QUOTE T) (sub2 (CDR al) z)) ) ) (DEFUN sublis (al y) (COND ((ATOM y) (sub2 al y)) ((QUOTE T)(CONS (sublis al (CAR y)) (sublis al (CDR y)) ) ))) Пример.

(sublis '((x. Шекспир)(y. (Ромео и Джульетта))) '(x написал трагедию y)) ;= (Шекспир написал трагедию (Ромео и Джульетта)) INSERT – вставка z перед вхождением ключа x в список al.

(DEFUN insert (al x z) (COND ((null al) Nil) ((equal (CAR al) x) (CONS z al)) ((QUOTE T) (CONS (CAR al) (insert (CDR al) x z)) ) ) (insert ‘(a b c) ‘b ‘s) ; = (a s b c) ASSIGN – модель присваивания переменным, хранящим значения в ассоциативном списке. Замена связанного с данной переменной в первой паре значения на новое заданное значение. Если не было пары вообще, то новую пару из переменной и ее значения размещаем в конец а-списка, чтобы она могла работать как глобальная.

(DEFUN assign (x v al) (COND ((Null al) (CONS (CONS x v) Nil )) ((equal x (CAAR al))(CONS (CONS x v) (CDR al))) ((QUOTE T) (CONS (CAR al) (assign x v (CDR al)) ) ) (assign ‘a 111 ‘((a. 1)(b. 2)(a. 3))) ;= ((a. 111)(b. 2)(a. 3)) (assign ‘a 111 ‘((c. 1)(b. 2)(a. 3))) ;= ((c. 1)(b. 2)(a. 111)) (assign ‘a 111 ‘((c. 1)(d. 3))) ;= ((c. 1)(d. 3) (a. 111)) Упражнение: Введите функции с именами – Пусто, Пара_в_список, Список_в_пару, входит_ли, Соединение, Элемент, Связывание, Ассоциация, Ряд_подстановок, Вставка, Присваивание, как аналоги вышеприведенных функций.

Задание: Напишите определение функции REVERSE – обращение списка Ответ:

(defun reverse (m) (cond ((null m) NIL)(T (append(reverse(cdr m)) (list(car m)) )) )) Теперь посмотрим ее вариант как пример использования накапливающих параметров и вспомогательных функций:.

(defun rev (m n) (cond ((null m) N)(T (rev(cdr m) (cons (car m) n))))) (defun reverse (m) (rev m Nil)) Выводы:

- Синтаксис Лиспа очень прост. В некотором смысле это сосредотачивает разработчиков на семантике, что породило большое количество диалектов.

- Форма - это выражение, которое может быть вычислено. Формами являются переменные и списки, начинающиеся с QUOTE, COND или с представления некоторой функции.

- Выполнение программы на Лиспе устроено как интерпретация данных, представляющих выражения, имеющие значение.

5. Интерпретатор Теперь рассмотрим определение операционной семантики Лиспа в виде универсальной функции, задающей правила вычисления форм и применения функций к аргументам.

- Требования к определению.

- Синтаксическая сводка.

- Определение универсальной функции - EVAL-APPLY.

- Предикаты и истинность.

Интерпретация или универсальная функция - это функция, которая умеет вычислять значение любой формы, включая формы, сводимые к вычислению произвольной заданной функции, применяемой к представленным в этой же форме аргументам, по доступному описанию данной функции. (Конечно, если функция, которой предстоит интерпретироваться, имеет бесконечную рекурсию, то интерпретация будет повторяться бесконечно.) Определим универсальную функцию eval от аргумента expr - выражения, являющегося произвольной вычислимой формой языка Лисп.

Универсальная функция должна предусматривать основные виды вычисляемых форм, задающих значения аргументов, а также представления функций, в соответствии со сводом вышеприведенных правил языка. При интерпретации выражений учитывается следующее:

- Атомарное выражение обычно понимается как переменная. Для него следует найти связанное с ним значение. Например, могут быть переменные вида “x”, “elem”, смысл которых зависит от контекста, в котором они вычисляются.

- Константы, представленные как аргументы функции QUOTE, можно просто извлечь из списка ее аргументов. Например, значением константы (QUOTE T) является атом T, обычно символизирующий значение "истина".

- Условное выражение требует специального алгоритма для поиска истинных предикатов и выбора нужной ветви. Например, интерпретация условного выражения (COND ((ATOM x) x) ((QUOTE T) (first (CAR x) )) ) должна обеспечивать выбор ветви в зависимости от атомарности значения аргумента. Семантика чистого Лиспа не определяет значение условного выражения при отсутствии предиката со значением "истина".



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

- Если функция представлена своим названием, то среди названий различаются имена встроенных функций, такие как CAR, CDR, CONS и т.п., и имена функций, введенных в программе, например, first. Для встроенных функций интерпретация сама знает как найти их значение по заданным аргументам, а для введенных в программе функций - использует их определение, которое находит по имени или по контексту.

- Если функция использует лямбда-конструктор, то прежде, чем ее применять, понадобится связывать переменные из лямбда-списка со значениями аргументов. Функция, использующая лямбда-выражение, (LAMBDA (x) (COND ((ATOM x) x) ((QUOTE T) (first (CAR x) )) )) зависит от одного аргумента, значение которого должно быть связано с переменной x. В определении используется свободная функциональная переменная first, которая должна быть определена в более внешнем контексте.

- Если представление функции начинается с DEFUN, то понадобится сохранить имя функции с соответствующим ее определением так, чтобы корректно выполнялись рекурсивные вызовы функции. Например, предыдущее LAMBDA-определение безымянной функции становится рекурсивным, если его сделать вторым аргументом специальной функции DEFUN, первый аргумент которой – fisrt, имя новой функции.

(DEFUN first (x) (COND ((ATOM x) x) ((QUOTE T) (first (CAR x) )) )) Можно сказать, что DEFUN замыкает выражение, содержащее функциональную переменную.

Таким образом, интерпретация функций осуществляется как взаимодействие четырех подсистем:

- обработка структур данных (cons, car, cdr, atom, eq), - конструирование функциональных объектов (lambda, defun), - идентификация объектов (имена переменных и названия функций), - управление порядком вычислений (композиции, quote, cond, eval).

Определение универсальной функции Универсальная функция eval, которую предстоит определить, должна удовлетворять следующему условию: если представленная аргументом форма сводится к функции, имеющей значение на списке аргументов этой же формы, то это значение и является результатом функции eval.

(eval '(fn arg1... argK)) Результат применения "fn" к аргументам "arg1,..., argK".

Вычисление Явное определение такой функции позволяет достичь четкости механизмов обработки Лисп-программ.

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

Вернемся к синтаксической сводке вычислимых форм.

Таблица. Синтаксическая сводка программ на языке Лисп.

<форма> ::= <переменная> | (QOUTE ) | (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))))) Упражнение: Это определение можно немого уточнить, если а-список при связывании названий функций поплнять не в начале, а в конце.

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 для дальнейших вычислений.

Все остальные случаи рассматриваются как список из функции с последующими аргументами.

Вспомогательная функция EVLIS обеспечивает вычисление аргументов, затем представление функции и список вычисленных значений аргументов передаются функции APPLY.

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

Если функция начинается с LAMBDA, то ее аргументы попарно соединяются со связанными переменными, а тело определения (форма из лямбдавыражения) передается как аргумент функции eval для дальнейшей обработки.

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

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

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

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

Отладка и применение частичных функций требует большего контроля, чем работа с тотальными, всюду определенными функциями.

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

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. Оно никогда не бывает неопределено, даже если аргументы плохие.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 9 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.