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

Каждыйбинарный узел соответствует минимальному блоку памяти.Примеры:(A . B)AB(C . (A . B))CABЛюбое S-выражение может быть построено из атомов с помощью CONS илюбая его часть может быть выделена с помощью CAR-CDR.Упражнение. Нарисуйте диаграммы для следующих S-выражений:14((A . B) .

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

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

C)BCНеопределен(A . B)15CARCONSCDRРезультат предыдущегоCONSA и BРезультат предыдущегоCONSA(A . B)BТождества: (на произвольных объектах)CONSCARДва произвольныхобъекта x и yРезультатпредыдущего CONSCONSCDRДва произвольныхобъекта x и yРезультат предыдущегоCONSCARCDRCONSПроизвольныйсоставной объект x не атом.Тот же самый объект x.Результаты предыдущихCAR и CDRИсходныйобъект x(первыйаргументCONS )Исходныйобъект y(второйаргументCONS )Исходный объект xПредикаты:Атомарность –неделимостьATOMCDRATOM(A.B)Nil выполняетроль(A.B)Результат предыдущегоCDRложногозначенияBTРавенствоEQ(A . B)(A . B)Неопределен16Точечная нотация точно представляет логику хранения любых структур данных впамяти и доступа к компонентам структур данных.

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

( … . (Ak . Nil) … ))).В памяти это фактически одна и та же структура данных.Таблица 2.3. Соответствие списков и равнозначных им S-выраженийList-notation списочная записьобъекта(A B C )((A B) C )(A B (C E))(A)((A))(A (B . C))(())(A B . C)Dot-notation - точечнаязапись того же объекта(A . (B . (C . Nil)))((A . (B .

Nil)) . (C . Nil))(A . (B . ((C . (E . Nil)). Nil)))(A . Nil)((A . Nil) . Nil(A . ((B . C) . Nil))(Nil . Nil)(A . (B . C))Для многошагового доступа к отдельным элементам такой структуры удобнопользоваться мнемоничными обзначениями композиций из многократных CARCDR. Имена таких композиций устроены как цепочки из “a” или “d”, задающиемаршрут движения из шагов CAR и CDR соотвественно, расположенный между“c” и “r”. Указанные таким способом CAR-CDR исполняются с ближайшего каргументу шага, т.е. в порядки обратном записи.Таблица. Примеры многошагового доступа к элементам структуры.Композиции CAR-CDRCaarВычисляются впорядке, обратномзаписи:A((A) B C)CadrCaddr(A B C)(A B C)Cadadr(A (B C) D)B - CDR затем CARC - (дважды CDR)затем CARC - два раза (CDR17затем CAR)Выводы:-Список – это перечень произвольного числа элементов, разделенныхпробелами, заключенный в круглые скобки.-Элементы списка могут быть любой природы.- S-выражение - это или атом или заключенная в скобки пара из двух Sвыражений, разделенных точкой.

Список – частный случай S-выражения.- Любое S-выражение может быть построено из атомов с помощью CONS илюбая его часть может быть выделена с помощью CAR-CDR.-Для изображения S-выражений используют различные нотации:графическую, точечную и списочную.-Базис Лиспа содержит элементарные функции CAR, CDR, CONS, EQ,, ATOM.3. Запись Лисп-программТеперь рассмотрим правила записи программ на Лиспе.-Правила записи Лисп-программ-Специальные функции-Безымянные функции-Рекурсивные функцииОсновные понятия, возникающие при написании программ – это переменные, константы,выражения, ветвления, вызовы функций и определения.

Все они представимы с помощьюS-выражений.1) Самая простая форма выражения - это переменная. Она может бытьпредставлена как атом.Примеры:18XnVariable1Переменная2LongSongДолгаяПесня2) Имена функций, как и переменных, лучше всего изображать с помощьюатомов, для наглядности можно предпочитать заглавные буквы.Примеры:CONSCARCDRATOMEQ3) Все более сложные формыпонимают как применение функции к ее аргументам(вызов функции). Аргументом функции может быть любая форма. Список, первыйэлемент которого – представление функции, остальные элементы - аргументы функции,– это основная конструкция в Лисп-программе.Пример:(функция аргумент1 аргумент2 ...

)4) Композиции функций естественно строить с помощью вложенных скобок.Пример:(функция1 (функция2 аргумент21 аргумент22 ... ) аргумент2 ... )Этих правил достаточно, чтобы более ясно выписать основные тождестваЛиспа, формально характеризующие элементарные функции CAR, CDR, CONS,ATOM, EQ над S-выражениями:19(CAR (CONS x y)) = x(CDR (CONS x y)) = y(ATOM (CONS x y)) = Nil(CONS (CAR x) (CDR x)) = x(EQ x x) = T(EQ x y) = Nilдля неатомарных x.если x атомесли 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аргументом предиката являетсяатом “А”20(ATOM (QUOTE (A B C) )) = Nil(ATOM A)(третий (QUOTE (A B C)))аргументом предиката являетсясписок (A B C)значение не определено, т.к. онозависитотвхожденияпеременной A, аее значениезависит от контекста и должнобыть определено или задано допопытки выяснить атом ли это.применение новой функции кзначению,нетребующемувычисленияУпражнение.

Запишите выражения, соответствующие применению функций извышеприведенных таблиц.6) Построить функцию можно с помощью Lambda-конструктора:Пример:(LAMBDA (x)(CAR (CDR (CDR x))) )||_________________|_____определение|__________________________ параметр функциифункцииПри вызове такой безымянной функции заодно происходит задание значенийпараметров - связанных переменных:((LAMBDA (x) (atom x)) 123) ; = TX получит значение 123 на время применения построенной анонимной функции, действиекоторой заключается в выяснении, атом ли аргумент функции.Связанную переменную можно объявить специальной функцией Lambda, азначение она получит при вызове функции.7) Соответствие между именем функции и ее определением можно задать спомощью специального конструктора функций DEFUN, первый аргументкоторого - имя функции, второй – собственно именуемое определение функции.Формальным результатом DEFUN является ее первый аргумент, которыйстановится объектом другой категории.

Он меняет свой статус – теперь это имяновой функции.(DEFUN третий (x) (CAR (CDR (CDR x))) ))21||| |__________________|_____ определение функции|_____________________________ параметры функции|___________________________________________ имя новой функцииНовая функция “третий” действует так же как “Caddr” в таблице 2.4.Именование функций работает подобно заданию значений переменным.Идентификатор представляет структуру, символизирующую функциональныйобъект.

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