Организация памяти Lisp-машины

Как уже было сказано, каждый атом является переменной, если только не было определено обратное. Иными словами, если мы пишем список (+ 2 3) мы складываем то, что и пишем, т.е. 1+2, в то время как при записи (+ A B) вы пытаемся сложить значение A со значением B. Понимание механизма обработки данных при вычислении функции очень важно для избежания ошибок. в целях достижения этого понимания мы рассмотрим вопрос, как представляются данные в памяти интерпретатора Lisp.

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

Например, если у нас имеется список (a b c) то первый указатель будет указывать на элемент A, а второй на список (B C). Соответственно, список (B C) также может быть представлен в виде подобной ячейки, где головой будет являться b, а хвостом (c). Наконец, список из одного элемента (C) может быть представлен как голова C и хвост NIL. Поясним это на рисунке:

Таким образом, мы видим, что переменные A, B и C хранятся в памяти в некоторых ячейках, в то время как списковая структура использует не сами переменные, а ссылки на них. Важно понимать, что при создании другого списка, использующего переменные A, B или C, новые экземпляры этих переменных не создаются, а ссылки направляются в те же самые ячейки памяти, что и для первого списка. Это справедливо только для атомов – при создании нового списка (a b c) вся его структура будет продублирована заново.

Возникает естественный вопрос, как быть со списками со сложной структурой. В этом случае используется та же структура, в которой однако голова списка может указывать не только на переменную, но также и на список, обладающий в свою очередь сложной структурой. В качестве примера приведём список (a (a (c) b) b):

Как становится понятно из рисунка, значения элементов списка являются указателями на те ячейки памяти, в которых хранятся реальные данные. Несмотря на то, что наш список хранил в себе два элемента А и два элемента B, они в памяти имеют по одному экземпляру, а два экземпляра имеют указатели на них. Таким образом, переменные в языке Lisp хранятся в некоторых ячейках памяти, доступ в которые осуществляется через указатели. В дальнейшем будет показано, каким именно образом функции Lisp обрабатывают списки на основе их представления в памяти, здесь же мы подробнее остановимся на переменных.

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

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

setq	То же, что и set, однако подавляет вычисление первого аргумента

setqq

То же, что и set, однако подавляет вычисление обоих аргументов. Эта функция определена не во всех версиях Lisp (например, существует в Interlisp).

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

> (SET A B) Error: Attempt to take the value of the unbound variable `A'.

Ошибка возникает в виду того, что символ A вычисляется, однако значение ему не было присвоено. Если же мы используем функцию setq, то получим

> (SETQ A B) Error: Attempt to take the value of the unbound variable `B'.

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

> (SETQQ A B) B

Таким образом, мы присвоили A значение B, и теперь при вызове A мы получим значение B:

>A B

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

>(SET 'A 'B) B >(SETQ A 'B) B >(SETQQ A B) B

Также для пояснения механизма работы и отличий SET, SETQ и SETQQ приведём следующий пример:

> (SETQ A 'B) B > (SET A 'C) C > A B > B C >(EVAL A) C > (setq a 5) > (setq b 'a) A > (eval b)

Таким образом, мы видим, что оператор (SET A 'C) сперва преобразовал свой первый аргумент в его значение (т.е. B) и уже после этого присвоил B значение своего второго аргумента. Любопытно также отметить, что хотя A имеет значение B, а B имеет значение C, при попытке вычислить A мы получаем B, а вовсе не C. Однако при попытке вычисления уже вычисленного значения A мы получим С. Это связано с организацией памяти Lisp-машины, так как фактическим значением является указатель, и даже если в ячейку памяти занесено некоторое значение, второй раз по этому значению аргумент не вычисляется.

Рассмотрим ещё одну функцию, которая позволяет присваивать значение непосредственно ячейке памяти, на которую ссылается её первый аргумент (смысл этого действия будет объяснён при описании памяти lisp-машины)

setf	Функция записывает значение непосредственно в ячейку памяти, на которую указывает первый аргумент, и является обобщённым вариантом присвоения символу значения.

Вообще пока что можно полагать, что (SETF a b) эквивалентно (SETQ a b), однако в дальнейшем будет показано, как эта функция используется для обновления значений в объектах различных типов языка Lisp.