CONS создает ячейку и возвращает на нее указатель

Допустим, что у нас есть два списка:

 

_(setq голова '(b с))

(B C)

_(setq хвост '(a b c))

(А В С)

 

Вызов функции

 

_(cons голова хвост)

((В С) АВС)

строит новый список из ранее построенных списков ГOЛОBА и ХВОСТ так, как это показано на рис.3.

(cons голова хвост)

хвост

голова

Рис.3.

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

Заметим, что применение функции CONS не изменило структуры списков, являющихся аргументами, и не изменило значений переменных ГОЛОВА и ХВОСТ.

 

У списков могут быть общие части

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

(кто-то приходит кто-то уходит)

символ КТO-ТО является общим подвыражением, на которое ссылаются указатели из поля CAR из первой н из третьей ячейки списка.

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

_(setq список '((b c) a b c)

((В С) А В С)

структура изображена на рис.4.

Рис.4.

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

_(саr список)

(B C)

и

 

_(cddr список1)

(В С)

 

являются логически одинаковым списком (B C), хотя они и представлены различными списочными ячейка­ми:

 

_(equal (car список1) (cddr список1))

T

Однако список (B C), как видно из рис.5, может состоять и из тех же ячеек. Эту структуру можно создать с помощью следую­щей последовательности вызовов:

_(setq bc '(b c))

(В С)

_(setq abc (cons 'а bc))

(А В С)

_(setq список2 (cons bc abc))

((В C) A B C)

_список2

((В С) А В С)

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

Рис.5.

Логическое и физическое равенство не одно и то же.

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

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

Вызовы функции EQ из следующего примера возвращают в качестве значения NIL, так как логически одинаковые аргументы в данном случае представле­ны в памяти физически различными ячейками:

 

_(eq '((b с) a b с) '((b c) a b с))

NIL

_(eq список1 список2)

NIL; pис.4 и 5

_(eq (саr список1) (cddr список1))

NIL; риc.4

 

Поскольку части CAR н CDR списка СПИСОК2 предста­влены при помощи одних и тех же списочных ячеек, то получим следующий результат:

 

_(eq (саr список2) (cddr список2))

T

⇐ Предыдущая123

Поделиться: