common-lisp
Консоли и списки

Списки как конвенция

Некоторые языки включают структуру данных списка. Common Lisp и другие языки семейства Lisp широко используют списки (а имя Lisp основано на идее LISt-процессора). Однако Common Lisp фактически не содержит примитивный тип данных списка. Вместо этого списки существуют по соглашению. Конвенция зависит от двух принципов:

1. Символ nil - пустой список.
2. Непустым списком является ячейка cons, чей автомобиль является первым элементом списка и чей cdr является остальной частью списка.

Это все, что есть в списках. Если вы прочитали пример, называемый What is cons cell? , то вы знаете, что ячейка cons, автомобиль которой X, а cdr - Y, может быть записана как (X, Y) . Это означает, что мы можем написать несколько списков на основе вышеизложенных принципов. Список элементов 1, 2 и 3 просто:

(1 . (2 . (3 . nil)))

Однако, поскольку списки настолько распространены в семействе языков Lisp, существуют специальные соглашения о печати за пределами простой пунктирной пары для cons-ячеек.

1. Символ nil также может быть записан как () .
2. Когда cdr одной cons-ячейки является другим списком (либо (), либо ячейкой cons), вместо того, чтобы писать одну cons-ячейку с точечной парной нотацией, используется «запись списка».

Обозначение списка показано наиболее четко несколькими примерами:

(x . (y . z))   === (x y . z)
(x . NIL)       === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ())        === (1)

Идея состоит в том, что элементы списка записываются в последовательном порядке в круглых скобках до тех пор, пока не будет достигнут окончательный cdr в списке. Если конечный cdr равен nil (пустой список), тогда записывается окончательная скобка. Если конечный cdr не равен nil (в этом случае список называется неправильным списком ), то записывается точка, а затем записывается окончательный cdr.

Что такое ячейка cons?

Ячейка cons, также известная как пунктирная пара (из-за ее напечатанного представления), представляет собой просто пару из двух объектов. Ячейка cons создается функцией cons , а элементы в паре извлекаются с помощью функций car и cdr .

(cons "a" 4)

Например, это возвращает пару, чей первый элемент (который может быть извлечен car ) является "a" , а второй элемент (который может быть извлечен cdr ) равен 4 .

(car (cons "a" 4))
;;=> "a"

(cdr (cons "a" 4))
;;=> 3

Символьные ячейки могут быть напечатаны в виде точечной пары :

(cons 1 2)
;;=> (1 . 2)

Консервные ячейки также могут быть прочитаны в виде точечных парных обозначений, так что

(car '(x . 5))
;;=> x

(cdr '(x . 5))
;;=> 5

(Печатная форма cons-ячеек также может быть немного сложнее. Подробнее об этом см. В примере о cons-ячейках в виде списков.)

Это оно; cons cells - это только пары элементов, созданных функцией cons , и элементы могут быть извлечены car и cdr . Из-за их простоты ячейки cons могут быть полезным строительным блоком для более сложных структур данных.

Эскизные экраны

Для лучшего понимания семантики conses и списков часто используется графическое представление таких структур. Ячейка cons обычно представлена ​​двумя контактами, содержащими две стрелки, указывающие на значения car и cdr , или непосредственно значения. Например, результат:

(cons 1 2)   
;; -> (1 . 2)

могут быть представлены одним из этих чертежей:

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

Так, например:

(cons 1 (cons 2 (cons 3 4)))   ; improper “dotted” list
;; -> (1 2 3 . 4)

представлен как:

в то время как:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))  ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)

представлен как:

Вот древовидная структура:

(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4)         ; note the printing as an improper list

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

(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)

которые могут быть представлены обычным образом:

Затем мы пишем другое выражение, которое, по-видимому, эквивалентно предыдущему, и это подтверждается печатным представлением результата:

(let ((cell-a (cons 1 2)))
  (cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)

Но, если мы рисуем диаграмму, мы можем видеть, что семантика выражения различна, поскольку cell-a та же ячейка является значением как части car части cdr внешних cons (это - cell-a является общей ) :

и тот факт, что семантика двух результатов на самом деле отличается на уровне языка, может быть проверена следующими тестами:

(let ((c1 (cons (cons 1 2) (cons 1 2)))
      (c2 (let ((cell-a (cons 1 2)))
            (cons cell-a cell-a))))
  (list (eq (car c1) (cdr c1))
        (eq (car c2) (cdr c2)))
;; -> (NIL T)

Первый eq является ложным, так как car и cdr c1 структурно равны (это верно equal ), но не являются «идентичными» (т. Е. «Одна и та же общая структура»), а во втором тесте результат верен, поскольку car и cdr c2 идентичны , то есть они имеют одинаковую структуру .