Неожиданный вывод с cons()

Я нахожусь на императивном фоне, но в эти дни пробовал свои руки LISP (Common LISP)

Я прочитал здесь о cons, который

(cons x L):

Учитывая объект LISP x и список L, оценка (cons x L) создает список, содержащий x, за которым следуют элементы в L.

Когда я намеренно не использовал список в качестве второго аргумента, то есть когда я использовал

(cons 'a 'a) Я ожидал ошибки, но whoa! Я получил (A . A).

Что я пропустил, а что (A . A)?

Ответ 1

Cons строит "cons cell". Сначала это не относится к спискам. Ячейка cons - это пара двух значений. Ячейка cons представлена в письменной форме "пунктирной парой", например. (A . B), который содержит два значения 'A и 'B.

Два места в ячейке cons называются "автомобиль" и "cdr". Вы можете визуализировать такую ячейку cons как биссеральный блок:

  car   cdr
+-----+-----+
|  A  |  B  |
+-----+-----+

В Lisp значение также может быть ссылкой на что-то другое, например, другая ячейка cons:

+-----+-----+       +-----+-----+
|  A  |   --------> |  B  |  C  |
+-----+-----+       +-----+-----+

Это будет представлено в форме "пунктирной пары" как (A . (B . C)). Вы можете продолжить:

+-----+-----+       +-----+-----+       +-----+-----+
|  A  |   --------> |  B  |   --------> |  C  |  D  |
+-----+-----+       +-----+-----+       +-----+-----+

Это (A . (B . (C . D))). Как вы можете видеть, в такой структуре значения всегда находятся в car ячейки cons, а cdr указывает на остальную часть структуры. Исключением является последнее значение, которое находится в последнем cdr. Мы не нуждаемся в этом исключении: в Lisp есть специальное значение NIL, которое обозначает "ничего". Помещая NIL в последний cdr, у вас есть удобное контрольное значение, и все ваши значения находятся в car s:

+-----+-----+       +-----+-----+       +-----+-----+       +-----+-----+
|  A  |   --------> |  B  |   --------> |  C  |   --------> |  D  | NIL |
+-----+-----+       +-----+-----+       +-----+-----+       +-----+-----+

Так создается список в Lisp. Поскольку (A . (B . (C . (D . NIL)))) является немного громоздким, его также можно представить просто как (A B C D). NIL также называется пустым списком (); это обменные обозначения для одного и того же.

Теперь вы можете видеть, почему (cons x list) возвращает другой список. Cons просто конструирует другую ячейку cons с x в car и ссылку на list в cdr:

+-----+-----+
|  X  |   --------> list
+-----+-----+

и если list (A B), он работает как:

+-----+-----+       +-----+-----+       +-----+-----+
|  X  |   --------> |  A  |   --------> |  B  | NIL |
+-----+-----+       +-----+-----+       +-----+-----+

Итак, (cons x '(a b)) оценивается как (x a b).

Списки - это одно очень распространенное использование cons-ячеек. Вы также можете построить произвольные деревья из cons-ячеек или круговых списков или любого направленного графа.

Ответ 2

'a - атом lisp, а (A . A) - вырожденный список, называемый cons cell или "пунктирная пара". Поскольку вы не передали список аргументов L в (cons x L), вы вернули ячейку.

Ответ 3

(CONS x L)

Учитывая x и L, CONS возвращает новую cons-ячейку с x как CAR этой ячейки и L как CDR этой ячейки.

Списки связаны целыми ячейками cons.

CL-USER 141 > (sdraw '(a b c))

[*|*]--->[*|*]--->[*|*]---> NIL
  |        |        |
  v        v        v
  A        B        C

CL-USER 142 > (sdraw (cons 'foo '(a b c)))

[*|*]--->[*|*]--->[*|*]--->[*|*]---> NIL
  |        |        |        |
  v        v        v        v
 FOO       A        B        C

Если CONS получает два символа в качестве аргумента, он выглядит так:

CL-USER 143 > (sdraw (cons 'foo 'bar))

[*|*]---> BAR
  |
  v
 FOO