Свойства атомов и категории функций

Списки свойств атомов и структура списков

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

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

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

В списке свойств атома NIL было два индикатора, PNAME и APVAL, со значением NIL.

Более детально диаграммы списков свойств приведены в описании Lisp 1.5. .

Здесь достаточно принять к сведению, что реализация атомарных объектов — это сложная структура данных, в свою очередь представленная списками.

С помощью функции GET в форме (GET x i) можно найти для атома x свойство, индикатор которого равен i .

Значением (GET 'FF 'EXPR) будет (LAMBDA (X) (COND ... )), если определение FF было предварительно задано с помощью (DEFUN FF (X)( COND ... )).

Свойство с его индикатором может быть вычеркнуто - удалено из списка функцией REMPROP в форме (REMPROP x i).

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

Согласно стандарту Common Lisp, глобальные значения переменных и определения функций хранятся в фиксированных полях структуры атома. Они доступны с помощью специальных функций, SYMBOL-FUNCTION и SYMBOL-VALUE. Список произвольных свойств можно получить с использованием функции SYMBOL-PLIST. Функция REMPROP в Clisp удаляет лишь первое вхождение заданного свойства. Новое свойство можно ввести формой вида:

(SETF (GET atom indicator ) property )

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

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

Представление структуры списка

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

Каждая из частей занимает фиксированное число разрядов, представляющее тэг и адрес. Если декремент слова "x" указывает на слово "y", то это можно выразить стрелками на схеме:

Теперь можно дать правило представления S-выражений в машине. Представление атомов будет пояснено ниже. В тех случаях, когда машинное слово в адресе или декременте содержит указатель на атом, данный атом отобразится как запись в соответствующем прямоугольнике:

Правило представления неатомных S-выражений — начало со слова, содержащего указатель на car выражения в адресе и указатель на cdr в декременте. Ниже нарисовано несколько схем S-выражений. По соглашению NIL обозначается как перечеркнутый по диагонали прямоугольник.

вместо (A . B).

Непосредственная польза от сопоставления графического вида с представлением списков в памяти поясняется при рассмотрении функций, работающих со списками, на следующем примере из [1]:

((M . N) X (M . N))

Возможное для списков использование общих фрагментов ((M . N) X (M . N)) может быть представлено графически:

В точности такую структуру непосредственно текстом представить невозможно, но ее можно построить с помощью одного из выражений выражений:

(LET ((a '(M . N))) (SETQ b (LIST a 'X a)) )
((LAMBDA (a) (LIST a 'X a) )'(M . N))

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

может распечатываться как ( A B C A B C ... ).

Преимущества структур списков для хранения S-выражений в памяти:

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

Предполагается, что дан список вида

L1 = ((A B C)(D E F ) ... (X Y Z))

представленный как

и нужно построить список вида

L2 = ((A (B C))(D (E F)) ... (X (Y Z)))

представленный как

Рассмотрим типичную подструктуру (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)

Первый шаг в получении L2 из L1 — это определение функции GRP, строящей (X (Y Z)) из списка вида (X Y Z).

(GRP x) = (LIST (CAR x) (LIST (CADR x) (CADDR x)))

Здесь GRP применяется к списку L1 в предположении, что L1 заданного вида.

Для достижения цели новая функция MLTGRP определяется как

(MLTGRP L) = (COND ((NULL L) NIL)
      (T (CONS (GRP (CAR L)) (MLTGRP (CDR L)) )))

Итак, MLTGRP, применяемая к списку L1, перебирает (X Y Z) по очереди и применяет к ним GRP, чтобы установить их новую форму (X (Y Z)) до тех пор, пока не завершится список L1 и не построится новый список L2.

Деструктивные (разрушающие) преобразования структуры списков

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

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

Элементарный Лисп работает как расширяемая система, в которой информация как бы никогда не пропадает. SET внутри PROG лишь формально смягчает это свойство, сохраняя ассоциативный список и моделируя присваивания теми же CONS.

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

(RPLACA x y) заменяет адрес из x на y, эквивалент (CAR x) := y. Ее значение — x, но x, несколько отличающийся от того, что было раньше. На языке значений RPLACA можно описать равенством

(RPLACA x y) = (CONS y (CDR x))

Но действие различное: никакие CONS не вызываются и новые слова не создаются.

(RPLACD x y) заменяет декремент x на y, эквивалент (CDR x) := y.

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

Деструктивные функции используются при реализации списков свойств атома и ряда эффективных, но небезопасных, функций Clisp-а, таких как NCONC, MAPC и т.п.

Для примера рассмотрим функцию MLTGRP. Это преобразующая список функция, которая преобразует копию своего аргумента. Подфункция GRP реорганизует подструктуру

в структуру из тех же атомов:

Исходная функция делает это, создавая новую структуру и используя четыре CONS. Из-за того, что в оригинале только три слова, по крайней мере, один CONS необходим, а GRP можно переписать с помощью RPLACA и RPLACD. Изменение состоит в следующем:

Пусть новое машинное слово строит (CONS (CADR x) (CDDR x)). Тогда указатель на него встраивается в x при вычислении формы:

(RPLACA (CDR x) (CONS (CADR x) (CDDR x)))

Другое изменение сводится к удалению из второго слова указателя на третье слово.

Это выполняется как вычисление формы (RPLACA (CDR x) NIL).

Функция PGRP теперь определяется как соотношение:

(PGRP x) = (RPLACD (RPLACA (CDR x) (CONS (CADR x)
   (CDDR )x))) NIL)

Функция PGRP используется, в сущности, ради ее действия. Ее значением, неиспользуемым, является подструктура ((B C)). Поэтому для MLTGRP необходимо, чтобы PGRP выполнялось, а ее значение игнорировалось. Поскольку верхний уровень не должен копироваться, MLTGRP не обязана основываться на CONS.

(PMLTGRP L) =(COND ((NULL L) NIL)
                             (T (PROG2 (PGRP (CDR L))
                                      (PMLTGRP (CDR L)) )))

PROG2 — функция, вычисляющая свои аргументы. Ее значение — второй аргумент.

Значение PMLTGRP — NIL, PGRP и PMLTGRP — псевдо-функции.

Список свободной памяти и сборщик мусора

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

Первые реализации действовали по следующей схеме .

Определенный регистр FREE содержит информацию о первой ячейке этого списка. Когда требуется слово для формирования дополнительной структуры списка, берется первое слово списка свободной памяти, а код в регистре FREE заменяется на информацию о втором слове списка свободной памяти. Не требуется никаких программных средств для того, чтобы пользователь программировал возврат ячеек в список свободной памяти. Этот возврат происходит автоматически при пропуске программы, где бы ни исчерпался список свободной памяти. Программа, восстанавливающая память, называется "мусорщик" . Любая часть структуры списка, доступная программе, рассматривается как активный список и не затрагивается мусорщиком. Активные списки доступны программе через некоторые фиксированные наборы базисных ячеек, таких как ячейки списка атомов и ячейки, вмещающие частичные результаты Лисп-выражений. Сложные структуры списков могут быть произвольной длины, но каждое активное слово должно быть подведено к базисной ячейке цепью CAR-CDR.

Любая ячейка, не достижимая таким образом, недоступна для программы и не активна, поэтому ее содержимое не представляет интереса. Неактивные, то есть недоступные программе ячейки восстанавливаются мусорщиком в списке свободной памяти следующим образом. Во-первых, каждая ячейка, к которой можно получить доступ через цепь CAR-CDR, метится установлением отрицательного знака. Где бы ни выявилось отрицательное слово в цепи во время процесса пометки, мусорщик знает, что остаток раскручиваемого списка содержит уже помеченные ячейки. Затем мусорщик предпринимает линейное выметание осовободившегося пространства, собирая ячейки с положительным знаком в новый список свободной памяти и восстанавливая исходный знак активных ячеек.

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

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

Такая реализация экономична в отношении памяти, но она имеет ряд неприятных следствий: непредсказуемые длинноты (время работы) при поиске очередной порции ячеек и "перегрев системы", если такие порции слишком малы для продолжения счета. По мере роста производительности оборудования разработаны простые и не столь обременительные алгоритмы повторного использования памяти на базе параллельных процессов и профилактического копирования активных структур данных в дополнительные блоки памяти. Такие методы не требуют сложной разметки и анализа достижимости. Содержательная аналогия с мастерским мытьем посуды, то есть не допуская переполнения раковины, вполне отражает метод stopcopy; принятый в современных реализациях.

Гибкий интерпретатор

В качестве примера повышения гибкости определений приведено упрощенное определение Лисп-интерпретатора на Лиспе, полученное из М-выражения, приведенного Дж. Маккарти в описании Lisp 1.5 .

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

"(ASSOC e al )".

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

Функция SUBR — вызывает примитивы, реализованные другими, обычно низкоуровневыми, средствами. ERROR — выдает сообщения об ошибках и сведения о контексте вычислений, способствующие поиску источника ошибки. Уточнена работа с функциональными аргументами:

(DEFUN EVAL (e al )
   (COND 
 
   ((EQ e NIL ) NIL ) 
   ((ATOM e )((LAMBDA (v )
         (COND (v (CDR v ) )
            (T (ERROR 'undefvalue )) )
      ) (ASSOC e al ) )
   )
   ((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) )
   ((EQ (CAR e) 'FUNCTION )
      (LIST 'FUNARG (CADR fn ) al ) )
   ((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) ) 
   (T (apply (CAR e)(evlis (CDR e) al ) al ) )
) ) 
 
(DEFUN APPLY (fn args al )
   (COND
      ((EQ e NIL ) NIL ) 
      ((ATOM fn )
         (COND 
            ((MEMBER fn '(CAR CDR CONS ATOM EQ ))
               (SUBR fn agrs al ))
            (T (APPLY (EVAL fn al ) args al ))
) )

        ((EQ (CAR fn ) 'LABEL )
   (APPLY (CADDR fn )
         args
         (CONS (CONS (CADR fn )(CADDR fn )) 
            al ) ) )
 
((EQ (CAR fn ) 'FUNARG )
      (APPLY (CDR fn ) args (CADDR fn)) )

((EQ (CAR fn ) 'LAMBDA )
      (EVAL (CADDR fn )
         (APPEND (PAIR (CADR fn ) args ) al ))
(T (APPLY (EVAL fn al ) args al ))
) )

Определения ASSOC, APPEND, PAIR, LIST — стандартны.

Примерно то же самое обеспечивают EVAL-P и APPLY-P, рассчитанные на использование списков свойств атома для хранения постоянных значений и функциональных определений. Индикатор CATEGORY указывает в списке свойств атома на правило интерпретации функций, относящихся к отдельной категории, MACRO — на частный метод построения представления функции. Функция VALUE реализует методы поиска текущего значения переменной в зависимости от контекста и свойств атомов.

(DEFUN EVAL-P (E C)
(COND ((ATOM E) (VALUE E C))
   ((ATOM (CAR E))(COND ((GET (CAR E) 'CATEGORY)
         ((GET (CAR E) 'CATEGORY) (CDR E) C) )
         (T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))
   ) )
   (T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))
))
 
 
(DEFUN APPLY-P (F ARGS C)
(COND ((ATOM F)(APPLY-P (FUNCTION F C) ARGS C))
   ((ATOM (CAR F))(COND ((GET (CAR F) 'MACRO)
         (APPLY-P ((GET (CAR F) 'MACRO)
            (CDR F) C) ARGS C))
         (T (APPLY-P (EVAL F E) ARGS C))
   ) )
   (T (APPLY-P (EVAL F E) ARGS C))
))

Или то же самое с вынесением общих подвыражений во вспомогательные параметры:

(DEFUN EVAL-P (E C)
   (COND ((ATOM E) (VALUE E C))
      ((ATOM (CAR E))
         ((LAMBDA (V) (COND (V (V(CDR E) C) )
            (T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))
         )) (GET (CAR E) 'CATEGORY) ) )
      (T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))
))

 
(DEFUN APPLY-P (F ARGS C)
   (COND ((ATOM F)(APPLY-P (FUNCTION F C) ARGS C))
      ((ATOM (CAR F))
         ((LAMBDA (V) (COND (V (APPLY-P (V (CDR F)
            C) ARGS C))
               (T (APPLY-P (EVAL F E) ARGS C))
         ))(GET (CAR F) 'MACRO) ))
      (T (APPLY-P (EVAL F E) ARGS C))
))

Расширение системы программирования при таком определении интерпретации осуществляется простым введением/удалением соответствующих свойств атомов и функций.

Полученная схема интерпретации допускает разнообразные категории функций и макросредства конструирования функций, позволяет задавать различные механизмы передачи параметров функциям. Так, в языке Clisp различают, кроме обычных, обязательных и позиционных, — необязательные (факультативные), ключевые и серийные(многократные, с переменным числом значений) параметры . Виды параметров обозначаются пометкой OPTIONAL, KEY и REST соответственно, размещаемой перед параметрами в LAMBDA списке формальных аргументов. При этом серийный параметр должен быть последним в списке.

(DEFUN FUNCALL (FN REST AGRS) (APPLY FN ARGS))

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

(DEFUN EX-OPT (space OPTIONAL dot (line 'x))
   (LIST space 'of dot 'and- line))
(EX-OPT 'picture)
(EX-OPT 'picture 'circle)
(EX-OPT 'picture 'circle 'bars)

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

(DEFUN KEYLIST (A KEY X Y Z) (LIST A X Y Z))

(KEYLIST 1 :Y 2) ;= (1 NIL 2 NIL)

(DEFUN LENGTH (L OPTIONAL (V 0))
   (COND ((NULL L) V)
            (T (+ 1 (LENGTH (CDR L)))) 
)  )
 
((LENGTH '(1 2) 3)      ; = 5
 
(DEFUN REVERSE (L OPTIONAL (M NIL))
   (COND ((NULL L) M)
            (T (REVERSE (CDR L) (CONS (CAR L) M) )) 
)  )
 
(REVERSE '(1 2 3))            ; = (3 2 1)
(REVERSE '(1 2 3) '(5 6))   ;= (3 2 1 5 6)

Такой подход к работе параметрами часто освобождает от необходимости во вспомогательных функциях, что упрощает и определение EVAL от обязательности упоминания а-списка. Если воспользоваться сводимостью ( COND ) к NIL при отсутствии истиного предиката и кое-где использовать отображения, то определение становится совсем компактным.