Матрёшка

Разборщик из прошлой главы превратил строку в дерево из кортежей, а пять строк рекурсии посчитали по нему одиннадцать. В формуле были только числа и знаки. В программе есть ещё имена, которые определены где-то выше; функции, которые вызывают сами себя; функции, которые рождаются внутри других функций и уносят с собой их переменные. Дерево такой программы тоже обходят рекурсией, только по дороге приходится решить, где лежат значения имён, что происходит при вызове и почему функция помнит место, где её создали. Программа, которая отвечает на эти вопросы и выполняет дерево, называется интерпретатором. Её мы и напишем.

Глава устроена как матрёшка. Снаружи — Python. В нём работает наш интерпретатор Лиспа. В Лиспе, в свою очередь, мы напишем интерпретатор Лиспа, а внутри него запустим маленькую программу — факториал. И Python — не самая большая кукла: его байт-код исполняет программа на C, как мы видели в главе 33, а её машинные команды — процессор из главы 32. Каждая кукла исполняет следующую и ничего не знает о той, что снаружи.

Интерпретировать будем Лисп, а не Python, и всё из-за скобок. В музее языков мы видели, что программа на Лиспе — уже готовое дерево: разбирать её почти не нужно, и всё внимание достанется смыслу. А начиналось всё со статьи, где интерпретатор вовсе не собирались запускать.

MIT, 1958–1960. Функция для чтения

Мы повторим путь Рассела, только на Python и не вручную. А потом сделаем то, с чего начал Маккарти: напишем eval на самом Лиспе.

Кукла первая: чтение

Программа на Лиспе — вложенные скобки, внутри которых слова и числа. Лексер для неё пишется в одну строку: отделить каждую скобку пробелами и разрезать текст по пробелам. Разборщик — рекурсией: если пришла открывающая скобка, читать выражения, пока не встретится закрывающая, и сложить их в список; иначе это одно слово — число или имя.

Нажмите «Шаги»: parse вызывает сама себя на каждой открывающей скобке и возвращается на закрывающей, так что стопка вызовов повторяет вложенность скобок. Дерево — обычные списки Python: ['+', 1, ['*', 2, 3]]. Числа стали числами, а имена — даже + и define — остались строками. Такую запись — атом или список из таких же записей — называют S-выражением, от английского symbolic expression; именно S-выражения стоят в названии статьи Маккарти.

Сравните с разборщиком из главы 50. Там грамматика была в несколько этажей, чтобы умножение оказалось сильнее сложения, а здесь одна функция в десяток с небольшим строк и никакого старшинства. Его нет, потому что всё старшинство уже расставлено скобками: (+ 1 (* 2 3)) нельзя прочесть двумя способами. Скобками Лисп и расплачивается за такой короткий разборщик.

Кукла вторая: вычислить дерево

Правило, по которому вычисляется такое дерево, умещается в три строки, и в нём весь Лисп без особых случаев. Имя — найти в таблице, что за ним стоит. Число — само себе значение. Список — вычислить все его элементы, а потом применить первый к остальным.

В evaluate нет ни слова о сложении. + для интерпретатора — такое же имя, как pi, и его значение — функция Python, которая складывает. Сам наш Лисп считать не умеет: арифметику он поручает внешней кукле, Python, а Python — процессору. Зато первым элементом списка может быть что угодно, лишь бы оно вычислялось в функцию: голова вызова вычисляется по тому же правилу, что и аргументы.

В evaluate всего два действия. Одно — вычислить выражение в окружении, по-английски eval. Другое — применить функцию к аргументам, apply. Вычисление списка требует применения, а применение функции, написанной на самом Лиспе, потребует вычислить её тело. Авторы учебника SICP (1985) рисуют эти два действия кольцом и подписывают: цикл eval — apply обнажает суть языка программирования. Дальше пойдут подробности: что именно вычислять и где искать имена.

Особые формы

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

Площадь круга радиусом 10, слово маленький, потом пара, ради которой нужен quote: (quote (+ 1 2)) — это список из трёх элементов, а (+ 1 2) — число 3. Программа и данные в Лиспе записаны одинаково, и quote — переключатель между ними. А последняя строка падает с ZeroDivisionError, хотя условие (= r 0) истинно и ответ должен был быть 0. Функция if-function получила уже вычисленные аргументы, а чтобы их получить, интерпретатор поделил единицу на ноль. Особая форма if до ветки «нет» не дошла.

Истиной здесь считается всё, кроме False, — так принято в языке Scheme, ближайшем родственнике нашего Лиспа. Python строже к пустым значениям: для него ложны и 0, и пустой список.

Кукла третья: где живут имена

С одной таблицей имён интерпретатор проживёт только до первой своей функции. Вот на чём он споткнётся:

Когда вызывается (square 3), имя x должно значить 3. Но в таблице уже лежит x = 10, и после вызова оно должно остаться десятью. В главе 5 мы видели, как с этим справляется Python: у каждого вызова свой верстак — кадр, где лежат его переменные. Сделаем так же. Кадр — это словарь своих имён и ссылка на внешний кадр. Чтобы найти имя, смотрим в своём кадре, потом во внешнем, потом во внешнем внешнего — до глобального. Цепочку кадров, в которой ищутся имена, называют окружением.

Теперь функции. Особая форма (lambda (x) (* x x)) ничего не вычисляет: она создаёт значение-функцию и запоминает три вещи — параметры, тело и кадр, в котором её вычислили. Мы уже встречали такую конструкцию в главе 10: функция вместе с местом, где она родилась, — это замыкание. Тогда мы пообещали интерпретатор, внутри которого функции — такие же данные, как числа. Вот он. Запись (define (square x) …) — сокращение для (define square (lambda (x) …)).

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

Первая строка вывода — 9 и 10: внутри вызова x было тройкой, снаружи осталось десятью. Вторая интереснее. make-adder вызвали дважды, и каждый вызов создал свой кадр: в одном k = 5, в другом k = 10. Вызовы давно закончились, но кадры живы: на них ссылаются замыкания add5 и add10, и когда (add5 100) ищет k, поиск идёт из нового кадра с n = 100 во внешний, где лежит пятёрка. Кадр живёт, пока на него кто-то ссылается, а не пока идёт вызов. На этом держалась и закваска из главы 10: у каждого счётчика был свой живой кадр.

Рекурсия досталась даром: define записал count в глобальный кадр, и тело, вычисляясь, находит там само себя. Последняя строка — долг, к которому мы вернёмся через два раздела. Пройдите несколько программ по шагам в диаграмме и последите, как растут кадры и куда смотрят их стрелки.

Лексическая или динамическая

Строчка Env(f.params, args, f.env) — главное решение во всём интерпретаторе. Её можно было написать иначе: Env(f.params, args, env), где env — кадр того, кто вызывает. Разница видна на программе из трёх строк:

Функция show не знает своего x и ищет его во внешнем кадре. Если внешний — место, где show определена, она найдёт глобальное значение. Если внешний — кадр того, кто её вызвал, она найдёт x из test. Первое правило называют лексической областью видимости: что увидит функция, ясно из текста программы, из того, где она написана. Второе — динамической: это зависит от того, кто и откуда её позовёт. В диаграмме окружений выше выберите программу «Чья x?» и переключите правило.

Сегодня почти все языки лексические — Python, JavaScript, C, Java. Динамическая область осталась в забавном месте: в командной оболочке из главы 36, где переменные, объявленные внутри функции словом local, видны всем функциям, которые она вызывает. Сделайте ставку, прежде чем запускать.

Динамическую область трудно читать: чтобы понять, что напечатает show, надо знать всех, кто может её вызвать. Лексическую можно понять, глядя на одну функцию. Из этого правила следует вещь, полезная каждый день: функция в Python видит переменные того места, где она написана, и видит их живыми. Замыкание хранит сам кадр, а не копию значений из него. Поэтому в задачке из главы 10 три лямбды, сделанные в цикле, напечатали одно и то же: все они держат один кадр, где i к концу цикла стало двойкой.

Рекурсия без дна

Вернём долг. (count 100) сработал, а (count 1000) упал с RecursionError. Наш evaluate рекурсивен: вызов функции Лиспа — это вызов evaluate для её тела, внутри него — для ветки if, внутри неё — снова для вызова. На каждый вызов Лиспа уходит два кадра Python, а Python, как мы видели в главе 9, останавливается на тысяче. Двоичный поиск по n показывает границу: (count 495) ещё проходит, (count 496) уже нет.

Но у count есть особенность. Вызвав себя, она больше ничего не делает: результат внутреннего вызова и есть её результат. Кадр, который ждёт, пока внутренний вызов вернётся, ждёт впустую — ему остаётся только передать ответ наверх. Вызов, после которого вызывающей функции ничего не нужно, называют хвостовым. А если кадр не нужен, его можно и не хранить. Вместо того чтобы вызывать evaluate рекурсивно для ветки if или для тела функции, можно подменить вычисляемое выражение и окружение и пойти на следующий круг цикла:

Условие (= n 0) и аргументы по-прежнему вычисляются рекурсией: после них ещё есть работа. А тело функции и выбранная ветка — уже нет, и для них стопка вызовов Python не растёт. (count 100000) пройдёт за долю секунды.

Scheme выполнял хвостовые вызовы без роста стека с самого начала, с 1975 года, а потом первым из Лиспов потребовал этого от каждой своей реализации, и программисты на Scheme пишут циклы рекурсией. Python этого не делает и не собирается. В 2009 году Гвидо ван Россум объяснил в блоге, почему: это «просто не в духе Python», а главное, от устранённых кадров не остаётся следа в трейсбеке, и найти ошибку становится труднее. Наш интерпретатор платит ту же цену: если ошибка случится в глубине (count 100000), никто не узнает, на каком по счёту вызове.

Интерпретатор целиком

Соберём всё в одну программу и добавим несколько удобств. Лексер теперь выбрасывает комментарии после ; и понимает кавычку: 'x — сокращение для (quote x). Атомы #t и #f становятся True и False. Появились ещё три особые формы: set! меняет значение имени в том кадре, где оно найдено; begin вычисляет выражения по очереди; cond — цепочка условий, как if … elif … else в Python. Тело функции может состоять из нескольких выражений, а значение — последнее из них. И замыкание научилось вызываться из Python, как обычная функция: так встроенные map и apply работают и с функциями, написанными на Лиспе.

Двести строк — и у нас язык, в котором есть числа, списки, функции, замыкания, рекурсия и изменяемое состояние. В выводе — факториал двадцати, count на сто тысяч вызовов без единого лишнего кадра, счётчик, который помнит своё n в кадре make-counter, и map, которому подали лямбду, написанную на Лиспе. Последнюю строку пока пропустим, она понадобится в самом конце главы.

Прочитать, вычислить, напечатать, повторить

У интерпретатора есть возможность, которой нет у программы, переведённой заранее: с ним можно разговаривать. Прочитать строку, вычислить, напечатать ответ и ждать следующую. По-английски это read — eval — print — loop, и сокращение REPL читается буквально как программа: print(to_str(evaluate(parse(tokenize(input())), env))) в цикле. Значок >>> Python, консоль браузера, тетрадки Jupyter — всё это REPL. Название пришло из Лиспа. Первым интерактивным Лиспом Маккарти называет тот, что Л. Питер Дойч сделал на машине PDP-1 в 1963 году, и в описании этой системы, вышедшем в 1964-м, цикл так и назван: READ-EVAL-PRINT.

Ниже — REPL вашего Лиспа. Каждое выражение уходит на сервер курса и вычисляется интерпретатором из ячейки «лисп.py». Сервер ничего не помнит между запусками, поэтому REPL каждый раз повторяет всю историю удачных определений — так ваш define доживает до следующей строки. Поправьте ячейку, и REPL начнёт работать по-новому: добавьте, например, в standard_env строку "sqrt": math.sqrt, и спросите (sqrt 2).

Попробуйте сломать его. (car '()) закончится ошибкой Python IndexError: наш Лисп не проверяет аргументы встроенных функций, и ошибка внешней куклы видна изнутри. (fact 1000) упадёт с RecursionError: умножение после вызова делает его не хвостовым. А (define (fact2 n acc) (if (= n 0) acc (fact2 (- n 1) (* acc n)))) и (fact2 1000 1) выдадут число из 2568 цифр.

Кукла в кукле: Лисп на Лиспе

Теперь сделаем то, с чего начал Маккарти. Напишем eval на самом Лиспе и запустим его внутри нашего интерпретатора. Программа внутренней куклы — S-выражение, то есть список, а списки Лисп разбирать умеет: car — первый элемент, cdr — все, кроме первого, cons приставляет элемент спереди. Окружение внутренней куклы — список пар ((имя значение) …), как список a в статье 1960 года. Замыкание — список (closure параметры тело окружение).

Прочтите m-eval сверху вниз — это наш evaluate, пересказанный на другом языке. Имя ищется в окружении, число возвращается само, quote отдаёт список нетронутым, if выбирает ветку, lambda собирает замыкание, а всё остальное — вызов: вычислить голову, вычислить аргументы через m-list и отдать в m-apply. Та, в свою очередь, либо вычисляет тело замыкания в окружении, где параметры привязаны к аргументам (bind), либо, если перед ней встроенная функция внешней куклы, сразу применяет её. Особая форма label — из того же 1960 года: Маккарти пишет, что её придумал Натаниэль Рочестер, чтобы безымянная лямбда могла вызвать сама себя. У нас label делает замыкание, которое знает своё имя, и home добавляет это имя в окружение при каждом вызове.

Загрузите eval.lisp в REPL кнопкой «eval.lisp» и спросите внутреннюю куклу о факториале:

Ответ 3628800 прошёл через три интерпретатора. CPython выполняет байт-код нашего evaluate. evaluate выполняет m-eval. m-eval выполняет факториал, который ни о Python, ни о нашем evaluate не знает ничего. Интерпретатор, написанный на том же языке, который он исполняет, называют метациклическим. «Цикл» здесь в том, что каждое свойство языка определено через то же свойство хозяина: if внутренней куклы — через if внешней, сложение — через сложение. Зато лексическую область видимости внутренняя кукла строит сама: замыкание несёт своё окружение, и это видно в m-apply. Поменяйте там (home f) на окружение вызова — его придётся передать в m-apply лишним аргументом, — и внутренний Лисп станет динамическим, как первый Лисп Маккарти.

Алан Кэй, создатель Smalltalk, рассказывал в интервью журналу ACM Queue в 2004 году, как ещё аспирантом понял, что полстраницы кода внизу тринадцатой страницы руководства по Лиспу 1.5 — это Лисп, определённый на самом себе. Он назвал их «уравнениями Максвелла для программ»: весь мир программирования в нескольких строках, которые можно накрыть ладонью. Как четыре уравнения Максвелла описывают всю классическую электродинамику, так eval и apply говорят, что значит любая программа на Лиспе.

Сколько стоит кукла

Каждая кукла выполняет следующую, и за каждую приходится платить. Один вызов fib в Python — несколько десятков наносекунд. В нашем Лиспе тот же вызов проходит через evaluate: сравнить голову с "quote", "if", "cond"…, найти имена, пройдя по цепочке кадров, создать словарь для нового кадра. Внутренней кукле ещё тяжелее: каждое её действие — несколько вызовов функций Лиспа, а каждый из них — десятки шагов evaluate. Измерим на сервере, во что обходится каждый слой.

На сервере курса, когда писалась глава, выходило так: вызов fib в Python — около 0,02 микросекунды, в нашем Лиспе — около двух, во внутренней кукле — около 160. Каждый слой интерпретации стоит почти два порядка: наш Лисп медленнее Python раз в восемьдесят–сто, а Лисп на Лиспе медленнее нашего Лиспа ещё примерно во столько же. Сам Python, как мы мерили в главе 33, в десятки раз медленнее C. Если бы внутренняя кукла умела выполнять сама себя, третья тратила бы на один вызов около десятка миллисекунд, и (fib 20), с которой Python справляется за полмиллисекунды, считалась бы несколько минут.

Уборка: пометить и вымести

Осталась ещё одна забота, о которой наш интерпретатор не думает вовсе. Каждое cons, каждый вызов, каждый кадр занимают память. Кадр make-adder с k = 5 нужен, пока жив add5; кадры count не нужны уже на следующем круге. Освобождает их у нас Python: счётчик ссылок и сборщик петель из главы 38. У Рассела на IBM 704 никакого Python не было.

Построим память Лиспа сами. Пусть она состоит из n ячеек, в каждой два поля, car и cdr; поле хранит число, имя, пустой список или ссылку на другую ячейку. Свободные ячейки лежат в списке, cons берёт оттуда одну. Когда свободных не осталось, начинается уборка из двух проходов. Пометить: от каждой переменной программы пройти по ссылкам и отметить всё, до чего можно дойти. Вымести: пройти всю память подряд и вернуть в свободный список каждую непомеченную ячейку. Такой сборщик называют «пометить и вымести», а места, откуда начинается пометка, — корнями.

В первой строке память почти полна: список a занял ячейки 0–2, петля из x и y — 3 и 4, список b — 5 и 6. Петлю мы собрали нарочно: ячейки ссылаются друг на друга, но ни одна переменная на них не смотрит. После (set! a (cdr a)) ячейка 2 с единицей стала никому не нужна. Списку c нужно три ячейки, а свободна одна, и на втором cons начинается уборка. Она возвращает ячейки 2, 3 и 4: единицу и всю петлю. Счётчик ссылок петлю бы не нашёл: у x и y по одной ссылке — друг от друга, — и счётчики никогда не упадут до нуля. Именно для таких петель в CPython к счётчику добавлен сборщик, который мы видели в главе 38.

Перед уборкой cons отдаёт в collect свои аргументы a и b. Без этого сборщик освободил бы половину списка c, который make_list как раз собирает: на него пока не смотрит ни одна переменная из roots, он держится только в локальной переменной x. Поэтому Маккарти и помечал всё достижимое не только из переменных, но и из стека: корни — это всё, что программа ещё может прочитать. Забыть корень — худшая ошибка сборщика: он освободит живые данные, и программа сломается в случайном месте.

У «пометить и вымести» своя цена. Пока идёт уборка, программа стоит, и чем больше памяти, тем дольше пауза; на показе Маккарти уборка вместе со своей статистикой съела весь остаток доклада. Поэтому промышленные сборщики хитрее. Они разбивают уборку на маленькие порции, перемешанные с работой программы, или делят объекты на поколения: большинство объектов умирает молодыми, и чаще всего достаточно прибраться среди новых. Сборщик петель CPython устроен как раз по поколениям. Но в основе любого из них та же идея 1959 года: живо то, до чего можно дойти от корней, остальное — мусор.

Задачи

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

Куда дальше

Матрёшка собрана. Всё, что Python делает с вашими программами, наш evaluate с его кадрами и замыканиями делает с программами на Лиспе, и вы видели каждую его строку.

Но вспомните последнюю строку ячейки «лисп.py»: (fib 20) в нашем Лиспе считается раз в сто дольше, чем в Python, а Python и сам в десятки раз медленнее C. Время уходит на одни и те же вопросы. На каждом из двадцати двух тысяч вызовов fib функция evaluate проверяет, строка ли перед ней, сравнивает голову с "quote", "if", "cond", "define", "set!", "lambda", "begin" и ищет fib, n, < и -, проходя по цепочке кадров. Дерево тела не меняется, ответы тоже, а интерпретатор спрашивает заново при каждом вызове. Так ведёт себя толмач из главы 33, который переводит одну и ту же фразу каждый раз, когда её произносят.

Ранние Лиспы, по словам Маккарти, считали числа в 10–100 раз медленнее FORTRAN — языка, который переводили в машинные команды заранее. Можно ли прочитать программу один раз, ответить на все вопросы о её строении заранее и перевести её в машинный код — чтобы потом она работала сама, без переводчика рядом? В следующей главе мы напишем такой переводчик — компилятор — для «Искры-8», компьютера, который вы собрали из вентилей в четвёртой части курса.