2.12.2. Машинное представление и оценивание выражений
Для интерпретатора программ на языке Лисп ячейки памяти ЭВМ сгруппированы попарно, и каждая из них содержит указатель, который на рисунках изображается стрелкой.
Рис. 2.22.
Рис. 2.23. Пример графа.
Рис. 2.24.
На рис. 2.22, а показана некоторая ситуация, а на рис. 2.22, б соответствующая ей физическая реализация. Два указателя на схеме играют роль первого указателя-“сына” и первого указателя-“брата”. Например, команда (SETQ LI (АВ)) создает структуру, показанную на рис. 2.23. При этом используются следующие соглашения: отсутствие указателя обозначается символом 
атомы обрабатываются отдельно (для указания на них используется специальный маркер).
Рис. 2.25.
Рис. 2.26.
Рис. 2.27.
Рис. 2.28.
CAR некоторого 
-выражения есть то, на что указывает первый “сын”.
CDR некоторого 
-выражения есть то, на что указывает первый “брат”, взятый из внутренней части выражения и заключенный в скобки.
Чтобы определить выражение по его схематическому представлению, нужно просмотреть представление, следуя указателям, расположенным слева, на наибольшую глубину и затем по правым указателям (внешний просмотр). При записи выражения каждой стрелке, не заканчивающейся на атоме, соответствует открывающая скобка, а каждому символу 
закрывающая скобка и каждому атому — сам атом. Таким образом, приведенная на рис. 2.24 схема соответствует списку 
Кроме того, интерпретатор постоянно ведет список свободных ячеек, предназначенных для заполнения. На рис. 2.25 это представлено схематически, где головная ячейка обозначена символом 
Так, например, задание списка 
соответствует перемещению указателя 
от предыдущей заданной отметки, если атом С не существует, и его образованию либо помещению указателя “брата” в голову списка 2 (рис. 2.26).
Схема образования списка 
представлена на рис. 2.27, где 
— это 
Другой пример представления списка показан на схеме, соответствующей списку 
включающему списки 
(рис. 2.28).
Вычисление значения списка
Ниже приведен пример вычисления значения в языке Лисп с помощью функции 
когда используется внутреннее представление в Лиспе, в котором скобки не применяются. В языке Лисп выполнение какой-либо команды (которая сама является выражением) означает просто вычисление значения соответствующего входного выражения. Оно просматривается программой в последовательности, задаваемой указателями - “сыновьями”, а затем учитывается последний из встреченных указателей - “братьев”. После этого учитываются указатели-“сыновья”, связанные с этим последним, и так далее, пока не получается окончательное значение выражения. Затем вычисление повторяется снова, охватывая выражения более высокого уровня, и так до тех пор, пока не будет определено значение всего исходного выражения. Те части всего выражения, которые ожидают (в процессе всего оценивания) вычисления значений их аргументов, называются иногда “квазарами”.
Процедура 
где 
-выражение языка Лисп во внутреннем представлении.
(см. скан)
(см. скан)
Здесь учитывается, что 
эквивалентно выражению 
означает первого “сына” для выражения 
, а 
элементы выражения 
представляющие собой множество “братьев” выражения 
Необходимо отметить, что в языке Лисп любая программа сама по себе является 
-выражением. В частности, в Лиспе данные имеют ту же структуру, что и программы, и также являются выражениями. Результат выполнения программы в Лиспе также является программой. Соответственно этому 
-выражение в Лиспе является программой. Это свойство языка Лисп позволяет создавать программы, которые могут перестраивать сами себя.
Так как для функции 
целые (например, —4) и вещественные (например, 3.1416) числа, а также пустой список 
и символ Т (истина) являются одновременно их собственными значениями, то перед ними апостроф не ставится.
Примеры вычисления значений выражений:
(см. скан)
Функция 
может быть применена дважды:
(см. скан)
Сдвигая апостроф еще на позицию, имеем
