Распределение памяти в Лиспе

Question

> (cons 2 3) 
(2 . 3)

В среде Lisp необходимо выделить только одну конс-ячейку для соединения двух элементов.

Выше из книги Лисп "Земля Лисп". Я не понимаю, почему эта пара находится только в одной клетке. Как выглядит память для этих данных?

Answer 1

В ячейке cons всегда содержатся два значения, называемые car и cdr:

+-----+-----+
| car | cdr |
+-----+-----+

Чтобы представить ячейку cons, Lisp имеет «точечную нотацию»:

(car . cdr)

Функция cons создает такую ​​cons-ячейку из двух аргументов:

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

, которые можно представить так:

+-----+-----+
|  1  |  2  |
+-----+-----+

Значения cons-ячейки могуттакже быть "ссылки" или "указатели" на другие вещи.Такими другими вещами могут быть, например, другие cons-ячейки:

+-----+-----+     +-----+-----+
|  1  |   ------->|  2  | nil |
+-----+-----+     +-----+-----+

Это будет (1 . (2 . nil)) в точечной записи.Эта цепочка используется в Лиспе для представления списков.Поскольку списки используются для представления кода, они важны для Лисп.Поэтому для них есть более короткая запись: (1 2).

Answer 2

Ячейка CONS - это запись с двумя полями.

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

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

Тогда также обратите внимание на разницу между:

(cons 1 2)

и

(list 1 2)

(cons 1 2) создает одну ячейку минусов. (list 1 2) создает две противоборствующие ячейки. Первая cons-ячейка содержит 1 и указатель на вторую. Вторая cons-ячейка содержит 2 и NIL (маркер конца списка).

Таким образом, в качестве оптимизации, часто в парах ключ / значение, используется только ячейка cons, а не список.

((age . 22) (name . "Barbara))

против

((age 22) (name "Barbara"))

Последний использует еще две минусы.

Answer 3

Память это иллюзия:

(define (cons a d)
    (lambda (f) (f a d)))

(define (car x)
    (x (lambda (theCar theCdr) theCar)))

(define (cdr x)
    (x (lambda (theCar theCdr) theCdr)))

Смотри, Ма, памяти не требуется!

(шучу)

Answer 4

Я думаю, что минусы в lisp - это что-то вроде (просто для объяснения, а не в реальном коде)

typedef struct _cons
{
    void* car;
    void* cdr;
} cons;

Вот что означает "одиночные минусы".