Введение в программирование на Лиспе



             

Точечная нотация


При реализации Лиспа в качестве единой универсальной базовой структуры для конструирования символьных выражений использовалась так называемая "точечная нотация" (dot-nоtation), согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.

Бинарный узел, содержащий пару атомов ATOM1 и ATOM2,


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

( ATOM1 . ATOM2 )

Если вместо атомов "ATOM1", "ATOM2" рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то мы получим множество всех возможных составных символьных выражений – S-выражений.

S-выражение - это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой.

Все сложные данные создаются из одинаково устроенных блоков - бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.

Списки – это подмножество S-выражений, движение вправо по которым завершается атомом Nil.

(A . B)


(C . (A . B))


Пример 3.3.

(html, txt)

Любое S-выражение может быть построено из атомов с помощью CONS и любая его часть может быть выделена с помощью CAR-CDR.

Упражнение 3.3. Нарисуйте диаграммы для следующих S-выражений:

((A . B) . C) ((A . B) . (D . C)) ((A . B) . (D . (C . E)))




Содержание  Назад  Вперед