S-выражения: атомы, списки и префиксная нотация

Изучаем единственное синтаксическое правило Lisp, из которого строится всё остальное.

S-выражение (symbolic expression) — базовая синтаксическая единица Lisp: это либо атом (неделимое значение вроде числа или символа), либо список — последовательность S-выражений в круглых скобках. Вся программа на Lisp — это вложенные S-выражения.

У большинства языков грамматика занимает десятки страниц: отдельные правила для объявлений, выражений, операторов, приоритетов, блоков. У Lisp грамматика умещается в одно предложение: «всё есть либо атом, либо список атомов и списков». Эта радикальная простота — не бедность, а сила, и именно она делает возможной гомоиконность, которую мы разбирали раньше. В этом уроке мы детально освоим, что такое атомы и списки и как читать префиксную нотацию, чтобы дальнейший код перестал выглядеть как нагромождение скобок.

Атомы: неделимые значения

Атом — это S-выражение, которое нельзя разбить на части средствами чтения. К атомам относятся числа (42, 3.14, 1/3), символы (имена вроде x, +, defun), строки ("привет"), а также особые значения t и nil. Слово «атом» здесь употреблено в исходном древнегреческом смысле — «неделимый». Когда читатель встречает атом, он создаёт соответствующий объект: для 42 — целое число, для x — символ, для "привет" — строку.

Важнее всего понять природу символов, потому что это самый «лисповый» тип атома, у которого нет прямого аналога в большинстве языков. Символ — это объект-имя. Когда вы пишете foo, читатель создаёт символ с именем FOO (по умолчанию имена приводятся к верхнему регистру). Этот символ может играть роль имени переменной, имени функции, ключа или просто данных-метки. Символ существует сам по себе, независимо от того, связан ли он с каким-либо значением. Это ключевое отличие от строк: строка — это последовательность символов-литер (текст), а символ — это уникальный именованный объект, который к тому же интернируется (одинаковые имена дают один и тот же объект).

;; Примеры атомов:
42            ; целое число
3.14          ; число с плавающей точкой
1/3           ; рациональное число (дробь!)
"привет"      ; строка
foo           ; символ (имя)
+             ; тоже символ (имя операции сложения)
t             ; логическая истина
nil           ; пустой список и логическая ложь одновременно

Списки: всё в скобках

Список — это упорядоченная последовательность S-выражений, заключённая в круглые скобки. Элементами списка могут быть как атомы, так и другие списки — отсюда вложенность. Список (1 2 3) состоит из трёх атомов; список (1 (2 3) 4) состоит из атома, вложенного списка и ещё одного атома. Пустой список записывается как () и совпадает с атомом nil — это особый случай, к которому мы вернёмся в уроке про t и nil.

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

()              ; пустой список (он же nil)
(1 2 3)         ; список из трёх чисел
(a b c)         ; список из трёх символов
(1 (2 3) 4)     ; вложенный список
(+ 1 2)         ; список — и одновременно вызов сложения
(defun sq (x) (* x x))   ; список — и одновременно определение функции

Префиксная нотация: оператор стоит первым

Самое непривычное для новичка — это префиксная нотация: в Lisp оператор (а точнее, имя функции) ставится первым элементом списка, перед всеми аргументами. Мы пишем не 2 + 3, а (+ 2 3); не max(a, b), а (max a b). Правило чтения любого вычисляемого списка простое и единообразное: первый элемент — что делаем, остальные — над чем делаем.

На первый взгляд это кажется неудобством, но у префиксной нотации есть весомые преимущества. Во-первых, исчезает понятие приоритета операций. В привычной записи 2 + 3 * 4 нужно помнить, что умножение «сильнее» сложения; ошибёшься в приоритете — получишь неверный результат. В Lisp структура задаётся скобками явно: (+ 2 (* 3 4)) не оставляет никакой двусмысленности. Во-вторых, операторы естественно принимают любое число аргументов. Сложить пять чисел — это просто (+ 1 2 3 4 5); не нужно писать 1 + 2 + 3 + 4 + 5 с повторением знака. В-третьих, вызов функции и применение оператора — это одно и то же: нет искусственного разделения на «встроенные операторы» и «обычные функции», всё записывается единообразно.

;; Префиксная запись против привычной инфиксной:
(+ 2 3)              ; 2 + 3        = 5
(* 3 4)              ; 3 * 4        = 12
(+ 2 (* 3 4))        ; 2 + 3*4      = 14  (скобки заменяют приоритет)
(* (+ 2 3) 4)        ; (2+3) * 4    = 20
(+ 1 2 3 4 5)        ; 1+2+3+4+5    = 15  (любое число аргументов!)
(max 7 2 9 4)        ; максимум из четырёх  = 9

Как читать вложенные скобки

Главный навык начинающего — научиться читать вложенные S-выражения, не пугаясь скобок. Секрет в том, чтобы читать изнутри наружу: находите самое глубоко вложенное выражение, мысленно вычисляете его, заменяете результатом — и поднимаетесь на уровень выше. Возьмём (* (+ 1 2) (- 10 4)). Самое внутреннее слева — (+ 1 2), это 3. Справа — (- 10 4), это 6. Остаётся (* 3 6) — это 18. Так любое, сколь угодно громоздкое выражение распадается на простые шаги.

Важно понять, что отступы и переносы строк в Lisp не меняют смысла — структуру задают исключительно скобки. Поэтому редакторы автоматически выравнивают код по уровням вложенности, и опытный программист читает не отдельные скобки, а форму отступов, как читают структуру по абзацам. Подсветка парных скобок в редакторе и автоотступ снимают всю мнимую сложность: вы почти никогда не считаете скобки вручную.

;; Те же скобки, выровненные отступами для читаемости:
(defun discriminant (a b c)
  (- (* b b)
     (* 4 a c)))

;; читается изнутри: b*b, потом 4*a*c, потом их разность

Комментарии и оформление

Раз уж мы говорим о синтаксисе, отметим, как в Lisp пишутся комментарии, — это часто удивляет новичков. Однострочный комментарий начинается с точки с запятой ; и тянется до конца строки. Это и есть причина, по которой точка с запятой не может служить разделителем выражений, как в C: она занята под комментарии. По принятому стилю количество точек с запятой кодирует уровень комментария: ; — комментарий в конце строки кода, ;; — отдельная строка-пояснение внутри функции, ;;; — комментарий уровня всего определения. Кроме того, есть блочный комментарий #| ... |#, который может занимать несколько строк и вкладываться сам в себя.

; комментарий уровня строки кода
;; пояснение к блоку внутри функции
;;; комментарий ко всему определению ниже

#| Это блочный комментарий.
   Он может занимать
   несколько строк. |#

(+ 1 2)   ; складываем — комментарий справа от кода

Ещё одна полезная конструкция читателя — «немедленный комментарий выражения» #;, который выбрасывает не строку, а следующее целое S-выражение. Это удобно при отладке: можно «выключить» подвыражение, поставив перед ним #;, не стирая его. Такие мелочи показывают, насколько читатель Lisp гибок: он не просто разбирает скобки, а предоставляет набор инструментов для управления тем, что попадёт в структуру данных, а что будет отброшено ещё на стадии чтения.

Как это работает под капотом

Когда читатель встречает открывающую скобку, он начинает собирать список, читая S-выражения одно за другим, пока не встретит закрывающую скобку. Каждый элемент рекурсивно читается тем же механизмом — поэтому вложенность обрабатывается естественно. Результат — структура из cons-ячеек в памяти (их мы детально разберём в следующем разделе), где первый элемент списка доступен через car, а остаток — через cdr. Атомы же читаются по своим правилам: последовательность цифр становится числом, последовательность букв — символом, текст в кавычках — строкой.

Когда затем вычислитель получает список, он применяет простое правило: смотрит на первый элемент. Если это имя функции — вычисляет остальные элементы как аргументы и вызывает функцию. Если это имя специального оператора (например, if или quote) — обрабатывает его особым образом. Атом-число вычисляется сам в себя, атом-символ — в значение связанной с ним переменной. Вся семантика вычисления Lisp умещается в этот короткий свод правил, что мы детально разберём в следующем уроке про quote и eval.

Частые ошибки

Самая частая ошибка новичка — писать инфиксно по привычке: (2 + 3) вместо (+ 2 3). Запись (2 + 3) Lisp воспримет как попытку вызвать «функцию» с именем 2 и аргументами + и 3, что приведёт к ошибке, потому что число не является функцией. Помните железное правило: первый элемент списка — это всегда «что делаем».

Вторая ошибка — лишние или недостающие скобки. В Lisp каждая пара скобок значима: (f x) вызывает функцию f с аргументом x, а ((f x)) вызовет то, что вернул (f x), как функцию — это разные вещи. Привычка из других языков ставить «скобки для группировки на всякий случай» здесь вредна: каждая скобка добавляет уровень вызова.

Третья ошибка — путать символ и строку. foo — это символ (имя-объект), а "foo" — это строка (текст). Они ведут себя по-разному: символы интернируются и сравниваются как объекты, строки — как последовательности литер. Использовать строку там, где нужен символ (или наоборот), — источник тонких ошибок, особенно при работе с ключами и метками.

Итоги

• S-выражение — это либо атом (число, символ, строка, t, nil), либо список S-выражений в скобках; вся программа на Lisp устроена так.
• Список — одновременно структура данных и форма записи кода; различает их только контекст вычисления, что и лежит в основе гомоиконности.
• Префиксная нотация ставит оператор первым: правило «первый элемент — что делаем, остальные — над чем» убирает приоритеты операций и допускает любое число аргументов.
• Вложенные выражения читаются изнутри наружу; отступы не влияют на смысл — структуру задают только скобки.
• Символ — это именованный объект (не текст), а строка — последовательность литер; путать их нельзя.