WWW.DISSERS.RU

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

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


Pages:     | 1 | 2 || 4 | 5 |   ...   | 9 |

((DEFUN Левейший (LAMBDA (x)(COND ((ATOM x) x) (T (Левейший (CAR x))) ))) (QUOTE ((A. B). C) ) ) DEFUN дает имена обычным функциям, поэтому фактический параметр функции “Левейший” будет вычислен до того как начнет работать ее определение и переменная “x” получит значение “((A. B). C))”.

x = ((A. B). C)) Таблица. Схема вывода результата формы с рекурсивной функцией.

Вычисляемая форма Очередной шаг Результат и комментарии Вход в рекурсию (Левейший (QUOTE ((A Выбор определения функции (COND ((ATOM x) x). B). C))) и (T (Левейший (CAR x))) ) Первый шаг рекурсии Выделение параметров (QUOTE ((A. B). C)) функции (QUOTE ((A. B). C)) Вычисление аргумента X = ((A. B). C) функции (COND ((ATOM x) x) Перебор предикатов: выбор (ATOM x) (T (Левейший первого (CAR x))) ) (ATOM x) Вычисление первого Nil = “ложь”, предиката т.к. X – не атом.

Переход ко второму предикату T Вычисление второго T = “истина” – константа.

предиката Переход к выделенной ветви Второй шаг рекурсии (Левейший (CAR x)) выделение параметров (CAR x) функции (CAR x) Вычисление аргумента X = (A. B) функции Рекурсивный переход к редуцированному аргументу (COND ((ATOM x) x) Перебор предикатов: выбор (ATOM x) (T (Левейший первого (CAR x))) ) (ATOM x) Вычисление первого Nil = “ложь”, предиката т.к. X – не атом.

Переход ко второму предикату T Вычисление второго T = “истина” – константа.

предиката Переход ко второй ветви Третий шаг рекурсии (Левейший (CAR x)) выделение параметров (CAR x) функции (CAR x) Вычисление аргумента X = A функции Рекурсивный переход к редуцированному аргументу (COND ((ATOM x) x) Перебор предикатов: выбор (ATOM x) (T (Левейший первого (CAR x))) ) (ATOM x) Вычисление первого T – т.к. X теперь атом предиката Преход к первой ветви Вычисление значений A X переменной Значение функции получено и вычисление завершено Выход из рекурсии Некоторые определения функций могут быть хорошо определены на одних аргументах, но зацикливаться на других, подобно традиционному определению факториала при попытке его применить к отрицательным числам. Результат может выглядеть как исчезновение свободной памяти или слишком долгий счет без видимого прогресса. Такие функции называют частичными. Их определения должны включать в себя ветвления для проверки аргументов на принадлежность фактической области определения функции - динамический контроль. Условные выражения не менее удобны и для численных расчетов.

Пример 1. Абсолютное значение числа.

(Запись на алгоритмической нотации) алг АБС( цел x) арг x нач если (x < 0) то знач := - x иначе знач := x кон (Лисп-программа) (DEFUN Абс (LAMBDA (x)(COND ((< x 0 ) (- x)) (T x) ))) Пример 2. Факториал неотрицательного числа.

(Запись на алгоритмической нотации) алг ФАКТОРИАЛ ( цел N) арг N нач если (N = 0) то знач := иначе знач := N * ФАКТОРИАЛ (N - 1) кон (Лисп-программа) (DEFUN Факториал (LAMBDA (N)(COND ((= N 0 ) 1 ) (T ( * N (Факториал (- N 1 ))) ) ))) Это определение не завершается на отрицательных аргументах.

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

(+ 1 2 3 4) = Функция, которая определена лишь для некоторых значений аргументов естественной области определения, называется частичной функцией.

Пример 3. Алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел при условии, что определена функция “Остаток”.

(Запись на алгоритмической нотации) алг НОД ( цел x, y) арг x нач если (x < y) то знач := НОД ( y, x) инес Остаток (y, x) = то знач := x иначе знач := НОД (Остаток (y, x), x) кон остаток [x, y] - функция, вычисляющая остаток отделения x на y.

(Лисп-программа) (DEFUN НОД (LAMBDA (x y)(COND ((< x y) (НОД y x)) ((= (остаток y x ) 0 ) x ) (T (НОД (остаток y x) x )) )) ) Как и любое S-выражение, символьные представления функций могут быть значениями аргументов - функциональные аргументы.

Базис элементарного Лиспа образуют пять функций над S-выражениями CAR, CDR, CONS, ATOM, EQ и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA, DEFUN.

Далее мы построим определение универсальной функции EVAL, позволяющей вычислять значения выражений, представленных в виде списков, - правило интерпретации выражений.

Формально для перехода к практике нужна несколько большая определенность по механизмам исполнения программ, представленных S-выражениями:

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

Выводы:

- Основные понятия, возникающие при написании программ – это переменные, константы, выражения, ветвления, вызовов функций и определения. Все они представимы с помощью S-выражений.

- Связанную переменную можно объявить специальной функцией Lambda, а значение она получит при вызове функции.



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

- Специальные функции не требуют предварительной обработки параметров.

- Базис элементарного Лиспа образуют пять функций над S-выражениями CAR, CDR, CONS, ATOM, EQ и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA.

- И данные, и программа в Лиспе представляются с помощью S-выражений.

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

- Определение и имя новой функции можно задать с помощью специальной функции DEFUN.

4. Определение языка Теперь можем дать более точное определение Лиспа как языка программирования.

- Синтаксис Лиспа - Семантика Лиспа - Накопительные параметры - Вспомогательные функции Начнем с синтаксического обобщения.

Определение языка программирования обычно начинают с синтаксических формул, называемых БНФ (формулы Бекуса-Наура). Определение таких формул сводится к следующим положениям:

• Язык характеризуется набором определяемых понятий.

• Каждому понятию соответствует набор вариантов синтаксических формул.

• Каждый вариант – это последовательность элементов.

• Элемент – это или терминальный символ или синтаксическое понятие – нетерминальный символ.

Синтаксис данных в Лиспе сводится к правилам представления атомов и Sвыражений.

<атом> ::= <БУКВА> <конец_атома> <конец_атома> ::= <пусто> | <БУКВА> <конец_атома> | <число> <конец_атома> В Лиспе атомы - это мельчайшие частицы. Их разложение по литерам не имеет смысла.

::= <атом> | (. ) | (... ) По этому правилу S-выражения - это или атомы, или узлы из пары S-выражений, или списки из S-выражений.

/Три точки означают, что допустимо любое число вхождений предшествующего вида объектов, включая ни одного./ Символ «;» - начало комментария до конца строки.

Т.о. “()” есть допустимое S-выражение. Оно в языке Лисп по соглашению эквивалентно атому Nil.

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

() = Nil (a. Nil) = (a) - - - (a1. (... (aK. Nil)... )) = (a1... aK) Такая единая структура данных оказалась вполне достаточной для представления сколь угодно сложных программ. Дальнейшее определение языка Лиспа можно рассматривать как восходящий процесс генерации семантического каркаса, по ключевым позициям которого распределены семантические действия по обработке программ.

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

Синтаксис программ в Лиспе внешне на отличается от синтаксиса данных.

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

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

<идентификатор> ::= <атом> Идентификатор - это атомы, используемые при именовании неоднократно используемых объектов программы - функций и переменных. Предполагается, что объекты размещаются в памяти так, что по идентификатору их можно найти.

<форма> ::= <константа> | <переменная> | (<функция> <аргумент>... >) | (COND (<форма> <форма>) (<форма> <форма>)... ) <константа> ::= (QOUTE ) | ' <переменная> ::= <идентификатор> Переменная - это идентификатор, имеющий многократно используемое значение, ранее вычисленное в подходящем контексте. Подразумевается, что одна и та же переменная в разных контекстах может иметь разные значения.

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

<аргумент> ::= <форма> Если форма представляет собой константу, то нет необходимости в вычислениях, независимо от вида константы. Константные значения, могут быть любой сложности, включая вычислимые выражения. Константы изображаются с помощью специальной функции QUOTE, блокирующей вычисление.

Представление констант с помощью QOUTE устанавливает границу, далее которой вычисление не идет. Использование апострофа (') - просто сокращенное обозначение для удобства набора внешних форм. Константные значения аргументов характерны при тестировании и демонстрации программ.

Если форма представляет собой переменную, то ее значением должно быть Sвыражение, связанное с этой переменной до момента вычисления формы.

Следовательно где-то должна храниться некая таблица, по которой, зная имя переменной, можно найти ее значение.

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

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





Последнее правило задает формат условного выражения. Согласно этому формату условное выражение строится из размещенных в двухэлементном списке синтаксически различимых позиций для условий и обычных форм.

Двухэлементные списки из определения условного выражения рассматриваются как представление предиката и соответствующего ему S-выражения. Значение условного выражения определяется перебором предикатов по порядку, пока не найдется форма, значение которой отлично от Nil, что означает логическое значение "истина". Строго говоря, такая форма должна найтись непременно.

Тогда вычисляется S-выражение, размещенное вторым элементом этого же двухэлементного списка. Остальные предикаты и формы условного выражения не вычисляют (логика Мак-Карти), их формальная корректность или определенность не влияют на существование результата.

Разница между предикатами и обычными формами заключается лишь в трактовке их результатов. Любая форма может выполнить роль предиката.

<функция> ::= <название> | (LAMBDA <список_переменных> <форма>) | (DEFUN <название> <функция>) <список_переменных> ::= (<переменная>... ) <название> = <идентификатор> Название - это идентификатор, определение которого хранится в памяти, но оно может не подвергаться влиянию контекста вычислений.

Таким образом, функция - это или название, или трехэлементный список, начинающийся с LAMBDA или DEFUN.

Функция может быть представлена просто именем. В таком случае ее смысл должен быть заранее известен. Например, встроенные функции CAR, CDR и т.д.

Функция может быть введена с помощью лямбда-выражения, станавливающего соответствие между аргументами функции и связанными переменными, упоминаемыми в теле ее определения (в определяющей ее форме). Форма из определения функции может включать переменные, не включенные в лямбдасписок, - так называемые свободные переменные. Их значения должны устанавливаться на более внешнем уровне. Если функция рекурсивна, то следует объявить ее имя с помощью специальной функции DEFUN.

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

Начнем с общих методов обработки S-выражений.

AMONG – проверка входит ли заданный атом в данное S-выражение.

(DEFUN among (x y) (COND ((ATOM y) (EQ x y)) ((among x (CAR y)) (QUOTE T)) ((QUOTE T) (among x (CDR y) )) ) ) EQUAL - предикат, проверяющий равенство двух S-выражений. Его значение "истина" для идентичных аргументов и "ложь" для различных. (Элементарный предикат EQ определен только для атомов.) Определение EQUAL иллюстрирует условное выражение внутри условного выражения (двухуровневое условное выражение и двунаправленная рекурсия) (DEFUN equal (x y) (COND ((ATOM x) (COND ((ATOM y) (EQ x y)) ((QUOTE T) (QUOTE NIL)) ) ) ((equal (CAR x)(CAR y)) (equal (CDR x)(CDR y))) ((QUOTE T) (QUOTE NIL)) ) ) При желании можно дать название этой функции по-русски:

(DEFUN равно_ли (x y) (equal x y)) SUBST - функция трех аргументов x, y, z, строящая результат замены Sвыражением x всех вхождений атома y в S-выражение z.

(DEFUN subst (x y z) (COND ((equal y z) x) ((ATOM z) z) ((QUOTE T)(CONS (subst x y (CAR z)) (subst x y (CDR z)) ) ) ) ) (subst '(x. A) 'B '((A. B). C)) ; = ((A. (x. A)). C) (subst 'x '(B C D) '((A B C D)(E B C D)(F B C D))) ;= ((A. x)(E. x)(F. x)) Символ «;» - начало комментария.

Использование equal в этом определении позволяет подстановку осуществлять и в более сложных случаях. Например, для редукции совпадающих хвостов подсписков:

(DEFUN Подстановка (x y z) (subst x y z)) (Подстановка '(x. A) 'B '((A. B). C)) ;= ((A. (x. A)). C) NULL - предикат, отличающий пустой список от всех остальных S-выражений.

Используется, чтобы выяснять, когда список исчерпан. Принимает значение "истина" тогда и только тогда, когда его аргумент - Nil.

(DEFUN null (x) (COND ((EQ x (QUOTE Nil)) (QUOTE T)) ((QUOTE T) (QUOTE Nil)) ) ) При необходимости можно компоненты точечной пары разместить в двухэлементном списке и наоборот, из первых двух элементов списка построить в точечную пару.

(DEFUN pair_to_list (x) (CONS (CAR x) (CONS (CDR x) Nil)) ) (DEFUN list_to_pair (x) (CONS (CAR x) (CADR x)) ) По этим определениям видно, что списочная запись строится большим числом CONS, т.е. на нее расходуется больше памяти.

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

APPEND - функция двух аргументов x и y, сцепляющая два списка в один.

(DEFUN append (x y) (COND ((null x) y) ((QUOTE T) (CONS (CAR x) (append (CDR x) y) ) ) ) ) (append '(A B) '(C D E)) ;= (A B C D E) MEMBER - функция двух аргументов x и y, выясняющая встречается ли Sвыражение x среди элементов списка y.

(DEFUN member (x y) (COND ((null x) (QUOTE Nil)) ((equal x (CAR y)) (QUOTE T)) ((QUOTE T) (member x (CDR y)) ) ) PAIRLIS - функция трех аргументов x, y, al, строит список пар соотвествующих элементов из списков x и y - связывает и присоединяет их к списку al.

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

Pages:     | 1 | 2 || 4 | 5 |   ...   | 9 |










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

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