WWW.DISSERS.RU

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

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


Pages:     | 1 || 3 | 4 |   ...   | 9 |

CDR – Функция, укорачивающая список на один элемент. Обеспечивает доступ к “хвосту” списка, т.е. к остатку списка после удаления его головы.

ATOM - Функция, различающая составные и атомарные объекты. На атомах ее значение “истина”, а на более сложных структурах данных – “ложь”.

EQ – Функция, которая проверяет атомарные объекты на равенство.

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

Функция Аргументы Результат Конструирование структур данных CONS A и Nil (A ) CONS (A B) и Nil ((A B) ) CONS A и (B) (A B) CONS (Результат предыдущего CONS) и ( C ) ((A B) C) CONS A и (B C) (A B C) Доступ к компонентам структуры данных:

Слева CAR (A B C) A CAR (A (B C)) A CAR ((A B) C) (A B) CAR A Не определен Справа CDR (A ) Nil CDR (A B C D) (B C D) CDR (A (B C)) ((B C)) CDR ((A B) C) ( C ) CDR A Не определен Обработка данных:

CDR (A B C) (B C) CAR Результат предыдущего CDR B CAR (A C) A CAR Результат предыдущего CAR Не определен CONS A и (B) (A CAR Результат предыдущего CONS B) A CONS A и (B) (A CDR Результат предыдущего CONS B) (B) Предикаты:

Атомарность – неделимость ATOM VeryLongStringOfLetters T ATOM ( A B ) Nil - выполняет роль ложного значения CDR ( A B ) (B) ATOM Результат предыдущего CDR Nil ATOM Nil T ATOM ( ) T Равенство EQ A A T EQ A B Nil EQ A (A B) Nil EQ (A B) (A B) Не определен EQ Nil и () T Различие истиностных значений в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение “ложь” – это всегда Nil.

Если требуется явно изобразить значение “истина”, то используется константа – атом T (true) как стандартное представление, но роль такого значения может выполнить любой, отличный от пустого списка, объект.

Точечная нотация Исторически при реализации Лиспа в качестве единой базовой структуры для конструирования S-выражений использовалась так называемая “точечная нотация” (dot-nоtation), согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.

Бинарный узел, содержащий пару атомов ATOM1 и ATOM2, ATOM1 ATOMможно представить в виде S-выражения вида:

( ATOM1. ATOM2 ) Если вместо атомов “ATOM1”, “ATOM2” рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то мы получим множество всех возможных составных S-выражений.

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

Все сложные данные выстраиваются из одинаково устроенных блоков - бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.

Примеры:

(A. B) A B (C. (A. B)) C A B Любое S-выражение может быть построено из атомов с помощью CONS и любая его часть может быть выделена с помощью CAR-CDR.

Упражнение. Нарисуйте диаграммы для следующих S-выражений:

((A. B). C) ((A. B). (D. C)) ((A. B). (D. (C. E))) Расширение типа данных, допускаемых в качестве второго аргумента “CONS”, ни в малейшей степени не усложняет реализацию этой функции, равно как и реализацию функций “CAR” и “CDR”, зато их описания становятся проще:

CONS - Функция, которая строит бинарный узел и заполняет его парой объектов, являющихся значениями пары ее аргументов. Первый аргумент размещается в левой части бинарного узла, а второй - в правой.

CAR – Функция, обеспечивающая доступ к объектам, расположенным слева от точки в точечной нотации, т.е. в левой части бинарного узла.

CDR - Функция, обеспечивающая доступ к объектам, расположенным справа от точки в точечной нотации, т.е. в правой части бинарного узла.

Таблица Элементарные функции над произвольными S-выражениями Функция Аргументы Результат Конструирование структур данных CONS A и B (A. B) CONS (A. B) и C ((A. B). C) CONS A B (A. B) CONS (Результат предыдущего ((A. B). C) CONS) и C Доступ к компонентам структуры данных:

Слева CAR (A. B) A CAR ((A. B). C) (A. B) Справа CDR (A. B) B CDR (A. (B. C)) (B. C) Обработка данных:

CDR (A. (B. C)) (B. C) CAR Результат предыдущего B CDR CDR (A. C) C CAR Результат предыдущего Не CDR определен CONS A и B (A. B) CAR Результат предыдущего A CONS CONS A и B (A. B) CDR Результат предыдущего B CONS Тождества: (на произвольных объектах) CONS Два произвольных CAR объекта x и y Исходный Результат объект x предыдущего CONS (первый аргумент CONS ) CONS Два произвольных CDR объекта x и y Исходный Результат предыдущего объект y CONS (второй аргумент CONS ) CAR Произвольный CDR составной объект x - CONS не атом. Исходный объект x Тот же самый объект x.

Результаты предыдущих CAR и CDR Предикаты:

Атомарность – неделимость ATOM ( A. B ) Nil - выполняет роль ложного значения CDR ( A. B ) B ATOM Результат предыдущего T CDR Равенство EQ (A. B) (A. B) Не определен Точечная нотация точно представляет логику хранения любых структур данных в памяти и доступа к компонентам структур данных. В виде списков можно представить лишь те S-выражения, в которых при движении вправо в конце концов обнаруживается атом Nil, символизирующий завершение списка.

Атом Nil, рассматриваемый как представление пустого списка (), выполняет роль ограничителя в списках. Одноэлементный список (A) идентичен S-выражению (A. Nil). Список (A1 A2 … Ak) может быть представлен как S-выражение вида:



(A1. (A2. ( …. (Ak. Nil) … ))).

В памяти это фактически одна и та же структура данных.

Таблица 2.3. Соответствие списков и равнозначных им S-выражений List-notation - Dot-notation - точечная списочная запись запись того же объекта объекта (A B C ) (A. (B. (C. Nil))) ((A B) C ) ((A. (B. Nil)). (C. Nil)) (A B (C E)) (A. (B. ((C. (E. Nil)). Nil))) (A) (A. Nil) ((A)) ((A. Nil). Nil (A (B. C)) (A. ((B. C). Nil)) (()) (Nil. Nil) (A B. C) (A. (B. C)) Для многошагового доступа к отдельным элементам такой структуры удобно пользоваться мнемоничными обзначениями композиций из многократных CARCDR. Имена таких композиций устроены как цепочки из “a” или “d”, задающие маршрут движения из шагов CAR и CDR соотвественно, расположенный между “c” и “r”. Указанные таким способом CAR-CDR исполняются с ближайшего к аргументу шага, т.е. в порядки обратном записи.

Таблица. Примеры многошагового доступа к элементам структуры.

Композиции CAR-CDR Вычисляются в порядке, обратном записи:

A Caar ((A) B C) Cadr (A B C) B - CDR затем CAR Caddr (A B C) C - (дважды CDR) затем CAR Cadadr (A (B C) D) C - два раза (CDR затем CAR) Выводы:

- Список – это перечень произвольного числа элементов, разделенных пробелами, заключенный в круглые скобки.

- Элементы списка могут быть любой природы.

- S-выражение - это или атом или заключенная в скобки пара из двух Sвыражений, разделенных точкой. Список – частный случай S-выражения.

- Любое S-выражение может быть построено из атомов с помощью CONS и любая его часть может быть выделена с помощью CAR-CDR.

- Для изображения S-выражений используют различные нотации:

графическую, точечную и списочную.

- Базис Лиспа содержит элементарные функции CAR, CDR, CONS, EQ,, ATOM.

3. Запись Лисп-программ Теперь рассмотрим правила записи программ на Лиспе.

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

1) Самая простая форма выражения - это переменная. Она может быть представлена как атом.

Примеры:

X n VariableПеременнаяLongSong ДолгаяПесня 2) Имена функций, как и переменных, лучше всего изображать с помощью атомов, для наглядности можно предпочитать заглавные буквы.

Примеры:

CONS CAR CDR ATOM EQ 3) Все более сложные формы понимают как применение функции к ее аргументам (вызов функции). Аргументом функции может быть любая форма. Список, первый элемент которого – представление функции, остальные элементы - аргументы функции, – это основная конструкция в Лисп-программе.

Пример:

(функция аргумент1 аргумент2... ) 4) Композиции функций естественно строить с помощью вложенных скобок.

Пример:

(функция1 (функция2 аргумент21 аргумент22... ) аргумент2... ) Этих правил достаточно, чтобы более ясно выписать основные тождества Лиспа, формально характеризующие элементарные функции CAR, CDR, CONS, ATOM, EQ над S-выражениями:

(CAR (CONS x y)) = x (CDR (CONS x y)) = y (ATOM (CONS x y)) = Nil (CONS (CAR x) (CDR x)) = x для неатомарных x.

(EQ x x) = T если x атом (EQ x y) = Nil если x и y различимы Любые композиции заданного набора функций над конечным множеством произвольных объектов можно представить таким способом, но класс соответствующих им процессов весьма ограничен и мало интересен. Организация более сложного класса процессов требует более детального представления в программах соответствия между именами и их значениями или определениями, изображения ветвлений и объявления констант.

Специальные функции 5) Константа представляется как аргумент специальной функции QUOTE в виде списка:

Пример: Список из атомов объявлен константой.

(QUOTE (C O N S T )) Используется и сокращенная запись – апостроф перед произвольным данным.

Пример:

‘(C O N S T ) В зависимости от контекста одни и те же объекты могут выполнять роль переменных или констант, причем значения и того, и другого могут быть произвольной сложности. Если объект выполняет роль константы, то для объявления константы достаточно заблокировать его вычисление, то есть как бы взять его в кавычки (quotation), отмечающие буквально используемые фразы, не требующие обработки. Для такой блокировки вводится специальная функция QUOTE, предохраняющая свой единственный аргумент от вычисления.

Примеры:

(QUOTE A) константа A объявлена.

(QUOTE (A B C) ) константа (A B C) объявлена.

(ATOM (QUOTE A)) = T аргументом предиката является атом “А” (ATOM (QUOTE (A B C) )) = Nil аргументом предиката является список (A B C) (ATOM A) значение не определено, т.к. оно зависит от вхождения переменной A, а ее значение зависит от контекста и должно быть определено или задано до попытки выяснить атом ли это.

(третий (QUOTE (A B C))) применение новой функции к значению, не требующему вычисления Упражнение. Запишите выражения, соответствующие применению функций из вышеприведенных таблиц.

6) Построить функцию можно с помощью Lambda-конструктора:

Пример:

(LAMBDA (x) (CAR (CDR (CDR x))) ) | |_|_определение функции | параметр функции При вызове такой безымянной функции заодно происходит задание значений параметров - связанных переменных:





((LAMBDA (x) (atom x)) 123) ; = T X получит значение 123 на время применения построенной анонимной функции, действие которой заключается в выяснении, атом ли аргумент функции.

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

7) Соответствие между именем функции и ее определением можно задать с помощью специального конструктора функций DEFUN, первый аргумент которого - имя функции, второй – собственно именуемое определение функции.

Формальным результатом DEFUN является ее первый аргумент, который становится объектом другой категории. Он меняет свой статус – теперь это имя новой функции.

(DEFUN третий (x) (CAR (CDR (CDR x))) )) | | ||_ определение функции | |_ параметры функции |_ имя новой функции Новая функция “третий” действует так же как “Caddr” в таблице 2.4.

Именование функций работает подобно заданию значений переменным.

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

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

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

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

8) Ветвление (условное выражение) характеризуется тем, что ход процесса зависит от некоторых условий. Условия следует сгруппировать в общий комплект и соотнести с подходящими ветвями. Такую организацию процесса вычисления обеспечивает специальная функция COND (condition). Ее аргументами являются двухэлементные списки, содержащие предикаты и соответствующие им выражения. Аргументов может быть любое число. Обрабатываются они по особой схеме: сначала вычисляются первые элементы аргументов по порядку, пока не найдется предикат со значением “истина”. Затем выбирается второй элемент этого аргумента и вычисляется его значение, которое и считается значением всего условного выражения.

(COND (p1 e1) (p2 e2)... (pk ek) ) ||| предикаты для выбора ветви || _| ветви условного выражения Каждый предикат pi или ветвь ei может быть любой формы: переменная, константа, вызов функции, композиция функций, условное выражение.

Обычное условное выражение (if Predicate Then Else) или (если Predicate то Then иначе Else) может быть представлено с помощью функции COND следующим образом:

(COND (Predicate Then)(T Else)) Или более наглядно:

(COND (Predicate Then) (T Else ) ) Вычисление ряда форм в определении может быть обусловлено заранее заданными предикатами.

Пример:

(COND ((EQ (CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x))) (T x) ) Атом “T” представляет тождественную истину. Значение всего условного выражения получается заменой первого элемента из значения переменной x на B в том случае, если (CAR x) совпадает с A.

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

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

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

Рекурсивные функции: определение и исполнение 9) Определения могут быть рекурсивны.

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

Для примера рассмотрим функцию, выбирающую в списке самый левый атом:

алг Левейший ( список x) арг x нач если Atom (x) то знач := x иначе знач := Левейший (Car (x)) кон Новая функция “Левейший” выбирает первый атом из любого данного.

(DEFUN Левейший (x)(COND ((ATOM x) x) (T (Левейший (CAR x))) )) Если x является атомом, то он и является результатом, иначе функцию “Левейший” следует применить к первому элементу значения x, которое получается в результате вычисления формулы (CAR x). На составных x будет выполняться вторая ветвь, выбираемая по тождественно истинному значению встроенной константы T.

Определение функции “Левейший” рекурсивно. Эта функция действительно работает в терминах самой себя. Важно, что для любого S-выражения существует некоторое число применений функции CAR, после которого из этого Sвыражения выделится какой-нибудь атом, следовательно процесс вычисления функции всегда определен, детерминирован, завершится за конечное число шагов. Можно сказать, что для определенности рекурсивной функции следует формулировать условие ее завершения.

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

Рассмотрим вычисление формы:

Pages:     | 1 || 3 | 4 |   ...   | 9 |










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

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