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

Поэтому в Лиспе ихрасполагают в общем списке. Карман кошелька может содержать карточку, накоторой написано, что делать с его содержимым - аргументами.Примеры:(fn arg1 arg2 ... argN)(Собрать портфель рюкзак)(+ 1 2 3 4 5 )(fn (gn arg1) arg2 ... argN)(Сложить (Найти портфель) (Подготовить Список_предметов))(+ 5 (* 2 3.14 R) X)При таком подходе список, представляющий вызов функции, внешне малоотличается от списка, представляющего данные, не требующие особой обработки.В таких случаях конверт можно заклеить, а в карман вставить карточку снадписью “QUOTE”, что соотвествует блокировке вычислений.

Увидев, чтоконверт заклеен, можно так его и оставить или расклеить. В последнем случае егосодержимое становится доступным для обработки в будущем. В записи это можноизобразить символом апострофа "'".Примеры:(СОБРАТЬ ‘(ШКАТУЛКА КОЛЬЦО СЕРЬГИ) СУМКА)(fn 'arg1 arg2 ...

argN)(cons '(+ 1 2 3 4 5) arg2 ... argN)При такой записи первые аргументы функций вычисляться не будут.(Расположены вторыми в списках.)Обычно подразумевают, что функция применяется к заранее вычисленнымзначениям ее аргументов. Но если в качестве данных допускать не толькозначения, но и символьные формы - записи программ для вычисления разныхзначений, то можно рассматривать и реализовывать специальные функции,способные обрабатывать аргументы нестандартно по любой схеме. Такиеваринаты нужны для реализации приcвоений и управления процессами.Конверты, кошельки и карточки могут быть разного цвета, они могут бытьпомечены перфорацией, марками, текстами и рисунками. Такие пометки можнопонимать как указания на схему обработки конвертов и их содержимого ("Передпрочтением - сжечь!"), что и позволяет моделировать функции и функциональныепрограммы, характерные для программирования на Лиспе.

Подобным образоморганизуют отображения – нечто вроде переноса рисунка вышивки с бумаги наткань.82. Идеальный Лисп-Основы символьной обработки.-Cписочная запись-Точечная нотация-Элементарные функции1. Основы символьной обработки.Идеальный (чистый, элементарный) Лисп – это свод принципиальныхособенностей программирования в функциональном стиле. Начинается он свыбора подходящей структуры данных и минимального набора функций надвыбранной структурой.

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

Программы строятся из рекурсивных функций над Sвыражениями. Определения и вызовы этих функций, как и любая информация,имеют вид S-выражений, то есть формально они могут обрабатываться какобычные данные, получаться в процессе вычислений и преобразовываться какзначения.3)Подобие машинным языкамСистема программирования на Лиспе допускает, что программа можетинтерпретировать и/или компилировать программы, представленные в виде Sвыражений. Это сближает программирование на Лиспе с методаминизкоуровневого программирования и отличает от традиционной методикиприменения языков высокого уровня.Cтруктуры данныхЛюбые структуры данных начинаются с элементарных значений. В Лиспе такиезначения называют атомами или символами. Внешне атом обычно выглядит какпоследовательность из букв и цифр, начинающаяся с буквы.9ANilATOMLISPЗанятие2Новый_годВотДлинныйАтомНуОченьДлинныйНоЕслиНадоАтомМожетБытьЕщеДлинннееФ4длш139к131бОдинаково выглядящие атомы не различимы по своим свойствам.

Термин“атом” выбран по аналогии с химическими атомами, строение которых –предмет другой науки. Согласно этой аналогии атом может иметь достаточносложное строение, но атом не предназначен для разбора на части базовымисредствами языка.Более сложные данные выстраиваются из одинаково устроенных блоковпамяти. В Лиспе это бинарные узлы, содержащие пары объектовпроизвольного вида. Каждый бинарный узел соответствует минимальномублоку памяти, выделяемому системой программирования при организации иобработке структур данных. Выделение блока памяти и размещение в немпары данных выполняет функция CONS (от слова consolidation), а извлечениелевой и правой частей из блока выполняют функции CAR и CDRсоответственно (“content of adress part of register” , “content of decrement part ofregister”).ФункцияАргументыРезультатConsАтом( Атом.X)XCar( Атом.X)Cdr( Атом.X)АтомXПо соглашению атом Nil выполняет роль пустого списка.

Бинарный узел,содержащий пару атомов ATOM и Nil, рассматривается как одноэлементный список(ATOM ) :АТОМNILили для наглядности:АТОМ10Если вместо атома “ATOM” подставлять произвольные атомы, а вместо “Nil” произвольные списки, затем вместо атомов - построенные списки и так далее, то мыполучим множество всех возможных списков. Можно сказать, что список - этозаключенная в скобки последовательность из разделенных пробелами атомовили списков.Примеры:(C )С(B C )ВС(C (A B))САВТакая форма записи S-выражений называется списочной записью (list-notation).Список – это перечень произвольного числа элементов, разделенныхпробелами, заключенный в круглые скобки.Элементы списка могут быть любой природы.Упражнения: Нарисуйте диаграммы для списков вида:((A B) C)11((A B) (D C))((A B)(D(C E)))Любой список может быть построен из пустого списка и атомов с помощьюCONS и любая его часть может быть выделена с помощью подходящейкомпозиции CAR-CDR.CONS - Функция, которая строит списки из бинарных узлов, заполняя их парамиобъектов, являющихся значениями пары ее аргументов.

Первый аргументпроизвольного вида размещается в левой части бинарного узла, а второй,являющийся списком, - в правой.CAR – Функция, обеспечивающая доступ к первому элементу списка - его“голове”.CDR – Функция, укорачивающая список на один элемент. Обеспечивает доступ к“хвосту” списка, т.е. к остатку списка после удаления его головы.ATOM - Функция, различающая составные и атомарные объекты. На атомахее значение “истина”, а на более сложных структурах данных – “ложь”.EQ – Функция, которая проверяет атомарные объекты на равенство.Таблица 2.1 Элементарные функции над спискамиПримеры соответствия между аргументами и результатами элементарныхфункций обработки списков .ФункцияАргументыРезультатКонструирование структур данныхCONSCONSCONSCONSCONSCARCARCARCARCDRCDRCDRCDRCDRA и Nil(A B) и NilA и (B)(Результат предыдущего CONS) и ( C )A и (B C)Доступ к компонентам структуры данных:Слева(A B C)(A (B C))((A B) C)AСправа(A )(A B C D)(A (B C))((A B) C)A(A )((A B) )(A B)((A B) C)(A B C)AA(A B)Не определенNil(B C D)((B C))(C)Не определен12Обработка данных:CDRCARCARCARCONSCAR(A B C)Результат предыдущего CDR(A C)Результат предыдущего CARA и (B)Результат предыдущего CONSCONSCDRA и (B)Результат предыдущего CONS(B C)BAНе определен(AB)A(AB)(B)Предикаты:Атомарность – неделимостьATOMATOMVeryLongStringOfLetters(A B)CDRATOMATOMATOM(A B)Результат предыдущего CDRNil()TNil - выполняетроль ложногозначения(B)NilTTРавенствоEQEQEQEQEQA AA BA (A B)(A B)(A B)Nil и ()TNilNilНе определенTРазличие истиностных значений в Лиспе принято отождествлять с разницеймежду пустым списком и остальными объектами, которым программист можетпридать в программе некоторый другой смысл.

Таким образом, значение “ложь”– это всегда Nil.Если требуется явно изобразить значение “истина”, то используется константа –атом T (true) как стандартное представление, но роль такого значения можетвыполнить любой, отличный от пустого списка, объект.Точечная нотацияИсторически при реализации Лиспа в качестве единой базовой структуры дляконструирования S-выражений использовалась так называемая “точечная13нотация” (dot-nоtation), согласно которой левая и правая части бинарного узларавноправны и могут хранить данные любой природы.Бинарный узел, содержащий пару атомов ATOM1 и ATOM2,ATOM1ATOM2можно представитьвида:в виде S-выражения( ATOM1 .

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