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

Эта функция сканирует список ивычисляет число элементов на верхнем уровне списка. Значение функции Length - целоечисло. Алгоритм можно описать следующими словами:"Это функция одного аргумента L.Она реализуется программой с двумя рабочими переменными z и v.Записать число 0 в v.Записать аргумент L в z.A: Если z содержит NIL, то программа выполнена и значениемявляется то,что сейчас записано в v.Записать в z cdr от того, что сейчас в z.Записать в v на единицу больше того, что сейчас записано в v.Перейти к A"28Эту программу можно записать в виде Паскаль-программы с несколькими подходящимитипами данных и функциями.

Строкам вышеописанной программы соответствуют строкиопределения функции LENGTH, в предположении, что существует библиотека Лиспфункций на Паскале:function LENGTH (L: list) : integer;var Z: list;V: integer;beginV := 0;Z := l;A: if null (Z) then LENGTH := V;Z := cdr (Z);V := V+1;goto A;end;Переписывая в виде С-выражения, получаем программу:(defunLENGTH (lambda (L)(prog (Z V)(setq V 0)(setq Z L)A(cond ((null Z)(return V)))(setq Z (cdr Z))(setq V (+ 1 V))(go A) ))) ));;=======================ТЕСТЫ=============(LENGTH '(A B C D))(LENGTH ‘((X . Y) A CAR (N B) (X Y Z)))Последние две строки содержат тесты. Их значения 4 и 5 соответственно.Форма Prog имеет структуру, подобную определениям функций и процедур в Паскале:(PROG, список рабочих переменных, последовательность операторов и атомов ...

) Атом впоследовательности выполняет роль метки, локализующей оператор, расположенный вследза ним. В вышеприведенном примере метка A локализует оператор, начинающийся с"COND".Первый список после символа PROG называется списком рабочих переменных. Приотсутствии таковых должно быть написано NIL или (). С рабочими переменными29обращаются примерно как со связанными переменными, но они не могут быть связаны ни скакими значениями через lambda.

Значение каждой рабочей переменной есть NIL, до тех пор,пока ей не будет присвоено что-нибудь другое.Для присваивания переменной применяется форма SET. Чтобы присвоить переменной piзначение 3.14 пишется:(SET (QUOTE PI)3.14)SETQ подобна SET, но она еще и блокирует вычисление первого аргумента. Поэтому(SETQ PI 3.14)запись того же присваивания. SETQ обычно удобнее. SET и SETQ могут изменятьзначения любых переменных из ассоциативного списка более внешних функций.Значением SET и SETQ является значение их второго аргумента.GO-форма, используемая для указания перехода (GO A) указывает, что программапродолжается оператором, помеченным атомом A, причем это A может быть и из болеевнешнего prog.Условные выражения в качестве операторов программы обладают полезнымиособенностями. Если ни один из предикатов не истинен, то программа продолжаетсяоператором, следующим за условным выражением.RETURN - нормальное завершение программы.

Аргумент return вычисляется, что иявляется значением программы. Никакие последующие операторы не вычисляются.Если программа прошла все свои операторы, не встретив Return, она завершается созначением NIL.Prog-форма может быть рекурсивной.Пример: Функция REV, обращающая список и все подсписки, столь же естественно пишетсяс помощью рекурсивной Prog-формы.ЛиспПаскаль(DEFUN rev (x)(prog (y z)function rev (x: list) :Listvar y, z: list;beginA: if null (x) Then rev := y;z := cdr (x);A (COND ((null x)(return y)))(setq z (CDR x))(COND ((ATOM z)(goto B)))if atom (z) then goto B;30(setq z (rev z))B(setq y (CONS z y))(setq x (CDR x))(goto A)))z := rev (z);B: y := cons (z, y);x := cdr (x);goto Aend;Функция rev обращает все уровни списка, так что rev от (A ((B C) D)) даст ((D (C B))A) .Для того, чтобы форма prog была полностью законна, необходима возможность дополнятьассоциативный список рабочими переменными.

Кроме того операторы этой формы требуютспециального расширения языка - в него включаются формы go, set и return, не известные внеprog. (Формы Go, Set, Return возникли как операторы лишь на верхнем уровне PROG иливнутри COND, находящегося на верхнем уровне PROG. Но в современных версиях Лиспа ихможно встретить и в других позициях.)Атомы, выполняющие роль меток, работают как указатели помеченного блока.Кроме того произошло уточнение механизма условных выражений, - отсутствие истинногопредиката не препятствует формированию значения cond-оператора, т.к. все операторыигнорируют выработанное значение.

Это позволяет считать, что значением является Nil.Такое доопределение условного выражения давно перекочевало и в области обычныхфункций, где часто дает компактные формулы для рекурсии по списку. Исчезаетнеобходимость в ветви вида “(T NIL)” .В принципе SET и SETQ могут быть реализованы с помощью a-списка примерно также как идоступ к значению аргумента, только с копированием связей, расположенных ранееизменяемой переменной (см. функцию assign из параграфа 4). Более эффективнаяреализация, на основе списков свойств, будет описана ниже.(DEFUN set (x y) (assign x y Alist))Обратите внимание, что введенное таким образом присваивание работает разнообразнее, чемтрадиционное присваивание: допущена вычисляемость левой части присваивания, т.е.можно в программе вычислять имена переменных, значение которых предстоит поменять.Пример:(setq x 'y)(set x 'NEW)(print x)(print y)31Напечатается Y и NEW.Списки свойств атомовДо сих пор атом рассматривался только как уникальный указатель, обеспечивающий быстроевыяснение различимости имен, названий или символов.

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

Каждое свойство помечаетсяатомом, называемым индикатором, или расположено в фиксированном поле структуры.Согласно стандарту Common Lisp глобальные значения переменных и определения функцийхранятся в фиксированных полях структуры атома. Они доступны с помощью специальныхфункций symbol-function и symbol-value соответственно. Список произвольных свойствможно получить функцией symbol-plist. Функция remprop в Clisp удаляет лишь первоевхождение заданного свойства. Новое свойство можно ввести формой вида:(setf (get Индикатор ) Свойство)Числа представляются в Лиспе как специальный тип атома. Атом такого типа состоит изуказателя с тэгом, специфицирующим слово как число, тип числа (целые, дробные,вещественные), и адрес собственно числа, код которого может быть произвольной длины.

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

Адреса в таких записях сопровождаются так называемымитегами, специфицирующими тип данного, расположенного по указателю. При схематичномизображении структуры списка в виде диаграммы машинное слово рисуется какпрямоугольник, разделенный на две части: адрес и декремент.Теперь можно дать правило представления С-выражений в машине. Представление атомовбудет пояснено ниже.32Преимущества структур списков для хранения С-выражений в памяти:1) Размер и даже число выражений, с которыми программа будет иметь дело, можно непредсказывать. Кроме того, трудно организовать для размещения выражений блоки памятификсированной длины.2) Ячейки можно переносить в список свободной памяти, как только исчезнет необходимостьв них. Даже возврат одной ячейки в список имеет значение, но если выражения хранятсялинейно, то трудно организовать использование лишнего или освободившегося пространстваиз блоков ячеек.3) Выражения, являющиеся продолжением нескольких выражений, могут быть представленытолько в одном экземпляре.Для примера рассмотрим типичную двухуровневую структуру (A (B C)).Она может быть построена из A, B и C с помощью(cons ‘A (cons (cons ‘B (cons ‘C NIL)) NIL))или, используя функцию list, можно то же самое записать как(list ‘A (list ‘B ‘C))Если дан список x из трех атомов x = (A B C), то аргументы A, B и C, используемые впредыдущем построении, можно найти какA = (car x)B = (cadr x)C = (caddr x)Исходную структуру из такого списка можно получить функцией grp, строящей (X (YZ)) из списка вида (X Y Z).(grp x) = (list (car x) (list (cadr x) (caddr x)))Здесь grp применяется к списку X в предположении, что он заданного вида.Деструктивные (разрушающие) операции33Элементарный Лисп универсален в смысле теории вычислительных функций отсимвольных выражений.

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

Функции, описанные в чистом Лиспе,такие как subst, в действительности не модифицируют свои аргументы, но делаютмодифицированную копию оригинала.Элементарный Лисп работает как расширяемая система, в которой информация как быникогда не пропадает. Set внутри Prog лишь формально смягчает это свойство, сохраняяассоциативный список и моделируя присваивания теми же CONS.Теперь же Лисп обобщается с точки зрения структуры списка добавлениемразрушающих средств - деструктивных базисных операций над списками rplaca иrplacd.

Эти операции могут применяться для замены адреса или декремента любого узлав списке подобно стандартным присваиваниям. Они используются ради их воздействияна память и относятся к категории псевдо-функций.(rplaca x y) заменяет адресную часть x на y. Ее значение - x, но x, отличное от того, чтобыло раньше. На языке значений rplaca можно описать равенством(rplaca x y) = (cons y (cdr x))Но действие совершенно различно: никакие cons не вызываются и новые слова несоздаются.(rplacd x y) заменяет декремент x на y.Деструктивные операции должно применять с осторожностью! Они могут совершеннопреобразить существующие определения и основную память. Их применение можетпородить циклические списки, возможно, влекущие бесконечную печать иливыглядящие бесконечными для таких функций как equal и subst.Такие функции используются при реализации списков свойств атома и рядаэффективных, но небезопасных, функций Clisp-а, таких как nconc, mapc и т.п.Для примера вернемся к функции grp.