Учебник Common Lisp и Scheme для начинающих

Программа курса

1. 1 Введение в Lisp

   1. Что такое Lisp и почему он вечен

      Краткая история Lisp с 1958 года, его уникальная идея «код — это данные» и причины, по которым язык остаётся актуальным шесть десятилетий подряд.

   2. Гомоиконность: когда программа — это структура данных

      Что такое гомоиконность в Lisp, почему код является списком, как читатель превращает текст в данные и как макросы используют это, чтобы программы писали программы.

   3. REPL и интерактивная разработка

      Что такое REPL в Lisp, как устроен цикл read-eval-print, чем интерактивная разработка отличается от цикла «правка-сборка-запуск» и почему это изменило индустрию.

   4. Диалекты Lisp: Common Lisp, Scheme, Clojure

      Чем отличаются главные диалекты Lisp: Common Lisp (SBCL), Scheme (R7RS, Racket) и Clojure. Философия, Lisp-1 против Lisp-2, реализации и что выбрать.

2. 2 S-выражения и основы

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

      Что такое S-выражения в Lisp: атомы и списки, как читается префиксная нотация, почему оператор стоит первым и как правило «оператор-аргументы» заменяет всю грамматику.

   2. quote, eval и читатель: данные против кода

      Зачем в Lisp нужна кавычка quote, как работает eval, что делает читатель и почему символы и списки нужно цитировать, чтобы получить данные, а не вычислять их.

   3. Числовая башня: целые, дроби, комплексные

      Числовая башня Common Lisp: целые без ограничения разрядности, точные рациональные дроби, числа с плавающей точкой и комплексные. Почему 1/3 в Lisp остаётся точным.

   4. Символы, строки, t и nil

      Природа символов в Lisp и их интернирование, отличие от строк, операции со строками и особая роль t и nil, где nil — это и пустой список, и ложь одновременно.

3. 3 Списки и cons-ячейки

   1. Cons-ячейки: из чего на самом деле сделаны списки

      Cons-ячейка — кирпичик списков Lisp. Что такое car и cdr, как из пар строятся списки, что такое точечная пара и почему список — это цепочка ячеек, оканчивающаяся nil.

   2. Построение списков: list, cons, append

      Как строить списки в Lisp: list для готового списка, cons для добавления в начало, append для склейки. Разделяемая структура, копирование и точечные пары.

   3. Обход и доступ: first, rest, nth и списки как стек

      Как обходить списки в Lisp: рекурсия по car/cdr, dolist и loop, доступ через first/rest/nth, length и поиск. Почему список — естественный стек через push и pop.

   4. Деструктивные и недеструктивные операции

      Разница между недеструктивными и деструктивными операциями над списками в Lisp: remove против delete, append против nconc, reverse против nreverse, ловушки изменения общих ячеек.

4. 4 Функции

   1. Функции: defun и lambda

      Как определять функции в Lisp: defun для именованных, lambda для анонимных. Тело функции, неявный progn, возврат значения последним выражением и контраст со Scheme.

   2. Параметры функций: optional, rest, key, aux

      Богатая система параметров Common Lisp: обязательные, необязательные &optional со значениями по умолчанию, переменное число &rest, именованные &key и вспомогательные &aux.

   3. Замыкания и функции высшего порядка

      Что такое замыкания в Lisp и как функция захватывает окружение, функции высшего порядка mapcar, reduce, remove-if, функции, возвращающие функции, и функциональный стиль.

   4. funcall, apply и пространства имён: Lisp-2 против Lisp-1

      Глубокий разбор Lisp-2: зачем в Common Lisp нужны funcall и apply, что значит #', почему функции и переменные в раздельных пространствах имён и как это иначе в Scheme.

5. 5 Связывание и области видимости

   1. Локальные переменные: let и let*

      Как связывать локальные переменные в Lisp: let создаёт параллельные привязки, let* — последовательные. Область видимости, тело как progn и типичные ошибки.

   2. Множественные значения: values и multiple-value-bind

      Как функция в Lisp возвращает несколько значений сразу через values, как их принять с multiple-value-bind и почему это не то же самое, что вернуть список.

   3. Специальные переменные: defparameter и defvar

      Глобальные специальные переменные в Common Lisp: разница defparameter и defvar, соглашение об ушах *имя*, динамическое связывание и временное переопределение через let.

   4. Лексическое и динамическое связывание

      Главное различие в семантике переменных: лексическое связывание (по тексту программы) против динамического (по времени выполнения). Почему Lisp выбрал лексику и роль Scheme.

6. 6 Управление и рекурсия

   1. Ветвление: if, when, unless, cond и case

      Управляющие конструкции Common Lisp: if как выражение, when/unless, лестница cond и диспетчер case. Почему единственная ложь — nil, и как всё строится поверх if.

   2. Последовательность вычислений: progn, prog1 и неявные тела

      progn, prog1, prog2 и неявный progn в телах defun/let/when/lambda. Возврат значения последовательности, top-level-ness для макросов и аналог begin в Scheme.

   3. Рекурсия и хвостовая рекурсия: TCO в Scheme и его отсутствие в CL

      Рекурсия как естественный стиль Lisp, накопители, хвостовая позиция и TCO. Scheme гарантирует оптимизацию хвостовых вызовов, ANSI Common Lisp — нет; named let и стек под капотом.

   4. Итерация: dolist, dotimes, do и named let

      Итеративные конструкции Common Lisp: dolist по списку, dotimes по индексам, общий do с параллельным обновлением и do*. Контраст с named let в Scheme и tagbody/go под капотом.

7. 7 Макросы — суперсила Lisp

   1. Макросы: код как данные и defmacro

      Главная суперсила Lisp: гомоиконность, две фазы (compile time/run time), defmacro и отличие макроса от функции. Когда нужен макрос, а когда хватит функции.

   2. Квазицитирование: backquote, запятая, ,@ и macroexpand

      Шаблоны кода через backquote: запятая подставляет значение, запятая-собака вклеивает список. Переписываем макросы наглядно и отлаживаем через macroexpand-1.

   3. Гигиена и захват переменных: gensym и syntax-rules

      Захват переменных и двойное вычисление в макросах. Как gensym обеспечивает гигиену в Common Lisp вручную и почему syntax-rules в Scheme гигиеничен по умолчанию.

   4. Собственный DSL: макрос как проектирование языка

      Пишем предметный язык на макросах: от своей управляющей конструкции до декларативного DSL конечного автомата. Дисциплина проектирования и почему DSL компилируется без потери скорости.

8. 8 Структуры данных

   1. Символы и пакеты: пространства имён Lisp

      Символ как первоклассный тип: интернирование, eq, пять ячеек, Lisp-2 против Lisp-1, ключевые слова. Пакеты как пространства имён: defpackage, export, одно и два двоеточия.

   2. Ассоциативные списки (alist) и списки свойств (plist)

      Словари из списков: alist с assoc/rassoc и plist с getf. Идиомы обновления, выбор :test, граница применимости и переход на хеш-таблицы. Контраст с assq/assv в Scheme.

   3. Хеш-таблицы: быстрый словарь Common Lisp

      make-hash-table и четыре теста (eq/eql/equal/equalp), gethash с двумя значениями и setf, идиома подсчёта, обход maphash/loop, множества. Под капотом корзины и рехеширование.

   4. Структуры, массивы, векторы и строки

      defstruct как лёгкий ООП-записи, массивы и векторы с O(1)-доступом, растущий вектор, и строки как векторы символов в едином протоколе последовательностей. Что хранится под капотом.

9. 9 CLOS — объектная система

   1. CLOS: классы и слоты через defclass

      Объектная система Common Lisp: defclass, слоты и их опции (:initarg/:initform/:accessor/:reader/:allocation), make-instance, slot-value и with-slots. Почему данные отдельно от поведения.

   2. Обобщённые функции и методы: defgeneric/defmethod

      Полиморфизм CLOS: обобщённая функция как набор методов, специализация по классу и eql, call-next-method. Почему диспетчеризация снаружи класса мощнее методов «внутри объекта».

   3. Мультиметоды и множественное наследование

      Мультидиспетчеризация по нескольким аргументам решает симметричные задачи без «посетителя». Множественное наследование и его линеаризация (CPL), миксины как безопасная идиома.

   4. Комбинирование методов: :before, :after, :around

      Стандартное комбинирование собирает поведение слоями: primary, :before/:after для эффектов и :around-обёртка, меняющая результат. Порядок выполнения и define-method-combination.

10. 10 Продвинутое

    1. Система условий и рестарты: мощнее исключений

       Условия и рестарты Common Lisp: handler-case vs handler-bind, restart-case и invoke-restart. Почему обработка до раскрутки стека разделяет восстановление и политику и даёт интерактивную отладку.

    2. Пакеты вглубь и форматирование (format)

       Модульность через пакеты: use/import-from/local-nicknames, разрешение конфликтов shadow. Язык вывода format: директивы ~a/~s/~d/~f/~%, циклы ~{~}, ветвления ~[~] и множественное число ~p.

    3. Цикл loop во всю мощь и обзор MOP

       Декларативная итерация loop: источники for in/across/from, накопление collect/sum/maximize, into и finally. Обзор метаобъектного протокола: классы и методы как объекты, метаклассы, зачем нужен MOP.

    4. Экосистема и итог: ASDF, Quicklisp и сравнение диалектов

       Инфраструктура Common Lisp: ASDF (сборка) и Quicklisp (библиотеки), карта экосистемы и реализации. Финальное сравнение Common Lisp, Scheme и Racket и общее ядро всего семейства Lisp.