Б. Л. Файфель - Очень краткое введение в язык Лисп

точечная пара. Скобки должны
быть сбалансированы.

(name . "Анатолий")

Это снова правильная точечная
пара.

Следует обратить внимание на то, что образование точечной пары это бинарная операция. Запись вида:

( A . B . C)
бессмысленна (по крайней мере, в HomeLisp). Однако, две следующие записи
представляют собой корректные точечные пары:

(A . (B . C))
((A . B) . C)
В первой из приведенных выше точечных пар, пара (B . C) является составной частью
пары (A . (B . C)). Будем говорить, что пара (B . C) вложена в пару (A . (B . C)).
Введем важное определение: часть точечной пары, расположенную между левой скобкой
и точкой будем называть A-частью или А-компонентой. Соответственно, часть пары,
расположенную между точкой и правой скобкой будем называть D-частью или Dкомпонентой.
Что можно сказать о конструкции (1.2)? Здесь точка не отделена пробелами от
окружения, а является частью атома 1.2 . Несмотря на внешнее сходство с точечной
парой, эта конструкция не соответствует данному выше формальному определению. Мы
еще вернемся к этой конструкции при рассмотрении списков, и вскроем ее истиную
природу!

S-выражения.
Атом или точечная пара называются S-выражением. В "мире Лиспа" нет ничего,
кроме S-выражений; S-выражениями являются и программы и данные. В памяти

компьютера все конструкции, кроме атомов, хранятся и обрабатываются в виде точечных
пар.

Cписки.
Точечная пара - универсальный способ построения агрегатов из атомов. Однако, точечная
запись не очень удобна для человека: в ней слишком много скобок и точек. Было
предложено правило, позволяющее записывать S-выражения практически без точек и
с использованием значительно меньшего количества скобок.
Этих правил всего два:
Цепочки . Nil просто удаляем;
Цепочки . ( удаляем вместе с соответствующей закрывающей скобкой.
Рассмотрим применение этих правил к записи S-выражения:

(A . (B . (C . Nil)))
На приведенном ниже рисунке показана последовательность упрощений:

Использование описанных правил упрощения привело к тому, что большая часть Sвыражений в Лиспе записывается в чисто скобочной нотации и
называется списками.
Можно дать такое определение списка. Список - это такая точечная пара, в записи
которой после применения правил упрощения не остается точек.
Вот эквивалентное определение. Список - эта точечная пара (состоящая, возможно, из

атомов и других точечных пар), удовлетворяющая условию: D-частью всех вложенных
точечных пар может быть либо точечная пара, либо специальный атом Nil.
Можно сказать, что список - это конструкция следующего вида: левая скобка, ноль или
более пробелов, группа из нуля или болееатомов или списков, разделенная цепочками
из одного или более пробелов, ноль или более пробелов и правая скобка.
Это последнее определение обычно и приводится в курсах Лиспа. Оно, разумеется,
правильно, но не следует забывать, что все S-выражения хранятся в памяти компьютера в
виде точечных пар. Точечная запись "незримо присутствует" при работе Лисп-системы (а
иногда и неожиданно проявляется; такой пример будет приведен ниже).
Еще раз следует отметить, что всякий список может быть представлен в точечной записи,
но не всякая точечная пара является списком. В ряде случаев правила упрощения,
приведенные выше, могут сделать точечную запись даже менее наглядной. Вот пример
на эту тему: точечная пара ((a . b) . (c . d)) после применения правил упрощения
превращается в малонаглядную запись: ((a . b) c . d). Исходная запись этой точечной
пары нагляднее упрощенной. К счастью, такие конструкции в реальных программах почти
не встречаются.
Для представления списка в точечной записи существует достаточно простое правило. В
соответствии с последним определением, любой список может быть представлен в виде:

( Нечто-1

Нечто-2

Нечто-3

...)

где Нечто - атом или список, а многоточие означает повторение. Легко убедиться, что
эквивалентной точечной формой такого представления будет:

( Нечто-1

. ( Нечто-2

. ( Нечто-3

.

... . Nil) . Nil) . Nil )

Далее подобному преобразованию следует подвергнуть каждое "Нечто", при условии, что
это "Нечто" - список, а не атом. Ниже приводится последовательность преобразований
позволяющая получить для списка ((A B) (C D) E F) эквивалентную точечную форму. При
этом красным цветом выделены добавляемые точки и скобки на очередном --">