Основы языка Lisp

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Архитектору

Основы языка Lisp

Что такое Lisp?

Lisp — это язык программирования со следующими особенностями:

Типизация — динамическая; в Common Lisp и Scheme типы объявляют опционально (declare, declaim), но проверка в основном в runtime; автоматического вывода типов нет.
Парадигма — функциональный (функции первого класса, рекурсия, lambda); мультипарадигменный: Common Lisp — CLOS (ООП), императивные setf и loop; ключевая идея — метапрограммирование через макросы и гомоиконичность.
Уровень — высокоуровневый — S-выражения, абстракции над списками и символами, без ручной работы с памятью.
Выполнение — интерпретируемый и/или компилируемый: исторически интерпретатор; Common Lisp (SBCL, CCL) — AOT и JIT; Scheme — интерпретатор или компиляция; Clojure — компиляция в байткод JVM.
Память — автоматическая (GC); Lisp — один из первых языков со сборкой мусора; ручного управления, RAII и подсчёта ссылок в классическом Lisp нет.
Платформа — кроссплатформенный — Common Lisp — нативные реализации (SBCL, CCL, CLISP); Clojure — JVM; ClojureScript — транспиляция в JavaScript; Scheme — разные интерпретаторы и компиляторы.
Формат разработки — REPL-first: можно работать построчно без проекта; для продакшена — .lisp/.cl файлы, ASDF-системы (Common Lisp), Leiningen/deps.edn (Clojure).
Направление — ИИ и символьные вычисления, метапрограммирование, академия, DSL; универсальный (Common Lisp — промышленный код); не типичный веб- или мобильный стек.
REPL — да, изобретён в Lisp — sbcl, ccl, SLIME/Sly в Emacs, встроенный REPL в IDE; цикл read-eval-print — основной способ обучения и отладки.
Поколение — старый, классический (с 1958 г., Джон Маккарти); Common Lisp (ANSI 1994) и Clojure (2007) — живые современные диалекты.
Параллелизм и асинхронность — ограниченно нативно: Common Lisp — потоки зависят от реализации (SBCL, CCL); Clojure — STM (ref), atom, agent, core.async; встроенных async/await в классическом Lisp нет.
Безопасность — относительно безопасный по памяти (GC, нет указателей); риски — динамическая типизация, мутабельное состояние (setq, setf), ошибки типов в runtime.

Если какой-то пункт из списка непонятен — подробные определения и примеры в Язык программирования.

Диалект в примерах

Учебные фрагменты ниже — Common Lisp (SBCL, CCL, CLISP), если не указано иное.

История диалектов — в статье 1; архитектура eval и макросов — в статье 3.

Lisp (LISt Processing) строится вокруг S-выражений: программа и данные записываются одним синтаксисом списков. Это основа гомоиконичности и метапрограммирования.

Все данные и код — списки (S-выражения)

S-выражение (symbolic expression) — атом или список в скобках. В Common Lisp атом — всё, что не cons: числа и символы — атомы, строки и векторы — нет ((atom "x") → nil). Список — цепочка cons-ячеек или литерал (a b c). Например:

42
hello
"world"
(+ 1 2)
(define square (lambda (x) (* x x)))

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

Эта унификация данных и кода означает, что программы на Lisp могут свободно манипулировать другими программами как данными. Можно создавать, изменять, анализировать и генерировать код во время выполнения, используя те же самые инструменты, что применяются для работы со списками. Такой подход открывает путь к мощным техникам метапрограммирования, включая макросы, которые позволяют расширять сам язык без изменения его компилятора или интерпретатора.

Префиксная нотация

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

(+ 3 5)        ; сложение
(* 2 (+ 3 4))  ; умножение результата сложения
(> x 10)       ; сравнение

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

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

Homoiconicity — код = данные

Homoiconicity — одно из ключевых свойств Lisp. Этот термин означает, что внутреннее представление программы идентично её внешнему текстовому виду. Другими словами, код программы на Lisp записан в том же формате, в котором язык представляет данные. Это позволяет программе читать, изменять и генерировать другой код, используя стандартные средства обработки списков.

Рассмотрим пример. Предположим, у нас есть список:

'(+ 1 2)

Апостроф перед списком указывает, что он не должен вычисляться, а воспринимается как данные. Этот список можно передать в функцию, модифицировать, сохранить в переменной или использовать как шаблон для генерации нового кода. Позже, при необходимости, его можно вычислить с помощью специальной функции eval.

Quote и quasiquote — основа макросов:

Запись	Значение
`'(+ 1 2)`	данные: список `(+ 1 2)`, не вычисляется
`(list ,x)	шаблон: `x` подставляется при генерации кода
`(list ,@xs)	вставка элементов списка `xs`

Благодаря гомоиконичности, Lisp предоставляет уникальную возможность создания языков внутри языка. Макросы в Lisp — это не просто текстовые замены, как в некоторых других системах. Они работают на уровне структур данных — макрос принимает S-выражение, преобразует его по заданным правилам и возвращает новое S-выражение, которое затем компилируется или интерпретируется как обычный код. Это делает макросы мощным инструментом для адаптации языка под конкретную предметную область, создания DSL (Domain-Specific Languages) и повышения выразительности программ.

REPL — интерактивная среда

Lisp был одним из первых языков, который ввёл концепцию REPL — Read-Eval-Print Loop (цикл "чтение–вычисление–вывод"). Это интерактивная среда, в которой программист может вводить выражения, немедленно получать результат их вычисления и наблюдать за состоянием системы в реальном времени.

Цикл REPL работает следующим образом:

Read — система читает введённое пользователем S-выражение.
Eval — выражение вычисляется согласно правилам языка.
Print — результат вычисления выводится на экран.
Затем цикл повторяется.

Такой подход создаёт тесную обратную связь между разработчиком и программой. Вместо того чтобы писать большой блок кода, компилировать его и запускать, программист может постепенно строить решение, проверяя каждую часть по отдельности. REPL особенно полезен при исследовательском программировании, прототипировании, отладке и обучении.

Подробнее о цикле read → eval → print — в архитектуре Lisp; установка REPL — в первой программе.

Списки как основная структура данных

Список — центральная структура данных в Lisp. Он не просто используется для хранения последовательностей элементов, но и служит фундаментальной строительной единицей самого языка. Каждый список в Lisp реализован как цепочка cons-ячеек — пар указателей, где первый элемент (car) содержит значение, а второй (cdr) указывает на следующую cons-ячейку или на пустой список nil.

Например, список (a b c) представлен в памяти как:

[a | •] → [b | •] → [c | nil]

Эта структура называется связным списком, и она позволяет эффективно добавлять элементы в начало списка, разделять списки на части и рекурсивно обрабатывать их.

Пустой список обозначается как () или nil. В Lisp эти два обозначения эквивалентны и одновременно представляют логическое значение "ложь". Любое другое значение считается "истиной".

Cons, car и cdr — базовые операции

Три функции составляют ядро работы со списками:

cons создаёт новую cons-ячейку из двух элементов.
car возвращает первый элемент cons-ячейки.
cdr возвращает остаток списка (всё, кроме первого элемента).

Примеры:

(cons 'a '(b c))   ; → (a b c)
(car '(a b c))     ; → a
(cdr '(a b c))     ; → (b c)

Операции (связный список; "добавление" создаёт новый список):

Действие	Функция
Добавить в начало	`(cons elem list)`
Голова / хвост	`(car list)`, `(cdr list)`
n-й элемент (0-based в `nth`)	`(nth n list)`
Длина	`(length list)`
Объединить	`(append list1 list2)`
Проверить пустоту	`(null list)`

Изменяемые списки (редко): rplaca, rplacd — замена car/cdr ячейки на месте. Векторы (vector ...): aref, setf + (aref v i).

Из cons, car и cdr можно построить любую операцию над списками — объединение, реверс, фильтрация, поиск и другие. Например, функция для проверки принадлежности элемента списку может быть написана так:

(defun my-member (x lst)
  (cond
    ((null lst) nil)
    ((equal x (car lst)) t)
    (t (my-member x (cdr lst)))))

В стандартной библиотеке есть (member x lst :test #'equal). Рекурсивный обход выше иллюстрирует car/cdr.

Для преобразования списков в Common Lisp используют mapcar, reduce, remove-if-not (аналог "filter"). Понимание cons, car и cdr остаётся базой для чтения любого Lisp-кода.

;; REPL: атом и cons
(atom 42)        ; => T
(atom "hello")   ; => NIL
(consp '(1 2))   ; => T

Работа с вложенными списками

Lisp легко справляется со вложенными структурами. Список может содержать другие списки, которые, в свою очередь, могут содержать символы, числа или ещё более глубокие вложения. Это делает Lisp особенно подходящим для представления древовидных структур, таких как XML-документы, AST (абстрактные синтаксические деревья) или иерархические данные.

Пример вложенного списка:

'((apple red) (banana yellow) (grape (green purple)))

Для доступа к элементам вложенных списков используются комбинации car и cdr. Например:

(car (cdr '((apple red) (banana yellow))))  ; → (banana yellow)
(cadr '((apple red) (banana yellow)))       ; → (banana yellow)

Функция cadr — это сокращение от (car (cdr ...)). Lisp предоставляет множество подобных комбинаций (caddr, cadar и т.д.) для удобства навигации по структурам.

Рекурсия естественным образом расширяется на вложенные списки. Например, функция для подсчёта всех атомов в произвольно вложенном списке:

(defun count-atoms (lst)
  (cond
    ((null lst) 0)
    ((atom lst) 1)
    (t (+ (count-atoms (car lst))
          (count-atoms (cdr lst))))))

Здесь проверяется, является ли текущий элемент атомом. Если да — считается за один. Если нет — рекурсивно обрабатываются его голова и хвост.

Создание и модификация списков

Хотя Lisp исторически ассоциируется с неизменяемыми структурами, большинство реализаций позволяют изменять cons-ячейки с помощью деструктивных функций, таких как setf, rplaca, rplacd.

Пример:

(setq my-list '(a b c))
(setf (car my-list) 'x)  ; my-list теперь (x b c)

Однако в функциональном стиле предпочтение отдаётся созданию новых списков, а не изменению существующих. Это повышает предсказуемость кода и упрощает рассуждение о его поведении.

Функции вроде append, reverse, subseq возвращают новые списки, оставляя исходные без изменений. Такой подход согласуется с принципами чистого функционального программирования и широко используется в современных диалектах, таких как Clojure.

Выразительность через композицию

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

Рассмотрим пример: генерация всех подмножеств заданного множества (представленного списком). На Lisp это можно выразить элегантно:

(defun subsets (lst)
  (if (null lst)
      '(())
      (let ((rest (subsets (cdr lst))))
        (append rest
                (mapcar (lambda (s) (cons (car lst) s))
                        rest)))))

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

Подробнее о стиле и композиции — в функциональном программировании.

Диалекты и куда читать дальше

Диалект	Роль
Common Lisp	ANSI-стандарт, CLOS, промышленный код — база курса
Scheme	минимальное ядро, хвостовая рекурсия, SICP
Clojure	JVM, иммутабельные структуры, `atom` / `ref`

Хронология и влияние на другие языки — история. Типы и CLOS — статья 4. Справочник по API — Справочник по Lisp.

Типичные ошибки старта и как их обходить

Новички часто упираются не в "сложность Lisp", а в несколько повторяющихся ловушек:

Ошибка 1: читать код как арифметику, а не как дерево.
Решение: смотрите на каждое выражение как на список "операция + аргументы".
Ошибка 2: путать данные и вычисление.
Решение: если форма должна остаться данными, используйте quote ('...).
Ошибка 3: пытаться сразу писать большой файл без REPL.
Решение: сначала проверяйте форму по частям в интерактивной сессии.
Ошибка 4: бояться вложенности скобок.
Решение: форматируйте код маленькими блоками, где каждая закрывающая скобка видна.

Эти же принципы подробно раскрываются в архитектуре и первой программе.

Мини-практикум на 10 минут

Запустите REPL и выполните блоки по порядку:

;; 1) данные vs код
'(+ 1 2)
(+ 1 2)

;; 2) список как структура
(car '(a b c))
(cdr '(a b c))

;; 3) простая функция
(defun twice (x) (* 2 x))
(mapcar #'twice '(1 2 3 4))

После практикума проще читать управляющие конструкции и функции и рекурсию, потому что базовая модель "S-выражение -> вычисление -> результат" уже закреплена.

Основы языка Lisp