Обновление, Сборка мусора, Замыкания
В Части 1 я говорил о том, как выбор Little Schemer каким-то образом привел меня к написанию интерпретатора Scheme, который я буду использовать для выполнения упражнений внутри.
Все идет довольно хорошо — прошлой ночью я закончил главу 7 и начинаю главу 8 (Lambda the Ultimate). Видимо, именно здесь книга действительно начинает становиться дикой и сложной.
Оказывается, после реализации определений функций и лямбда-выражений для главы 2 у меня был интерпретатор, который был достаточно мощным, чтобы делать все, что описано в книге, вплоть до конца главы 7. Тем временем я сделал несколько настроек здесь и там, а также несколько качественных улучшений. -life (например, загрузка и разбор файлов функций Scheme), но я был доволен тем, что мне не пришлось исправлять какие-либо серьезные ошибки в работе интерпретатора.
Однако в какой-то момент, просматривая последующие главы, я понял, что мы будем рассматривать замыкания, а мой интерпретатор еще не справился с этой задачей. Я начал набрасывать идеи о том, как реализовать замыкания, но вскоре понял, что мне нужно реализовать сборку мусора, прежде чем приступать к замыканиям.
Я беспокоился об этом, потому что боялся, что сборка мусора будет сложной темой, но, черт возьми, как бы я хотел немного изучить это, когда впервые написал код для привязки имен к значениям! Я смутно подумал: Я мог бы просто вести список созданных объектов и просматривать список, но должно быть что-то большее…. Я сохранил эту статью Боба Нистрома, и когда я копался в ней, я узнал, что на самом деле не было большего, чем это, по крайней мере, не для простого сборщика мусора. Я думаю, что мне потребовалось всего час или два, чтобы добавить в интерпретатор сборщик мусора пометки и очистки. Фантастический бонус заключался в том, что я смог исключить миллионы мест, где я использовал free() для создаваемых мной s-выражений, и поэтому код интерпретатора выглядит *намного* лучше.
Для хранения связанных имен у моего интерпретатора просто есть хеш-таблица. Когда вы вызываете (define foo 14), он создает s-выражение для хранения числового значения и вставляет ссылку с именем foo в хеш-таблицу. Я не пытаюсь имитировать настоящий стек или кучу. При вызове функции интерпретатор создает временную область видимости/хэш-таблицу и загружает в них параметры функции. Локальные области имеют ссылки на свои родительские области, поэтому они могут пройти по цепочке к верхней области в поисках ссылок.
Когда моя процедура сборки мусора выполняется, я просматриваю все имена, связанные в хеш-таблице, и помечаю объекты, на которые они ссылаются, с помощью текущего поколения сборщика мусора. Затем я просматриваю свой связанный список созданных объектов, и любой, чей маркер меньше текущего поколения, может быть безопасно освобожден (free()).
В общем, писать было довольно весело.
Закрытия
Для меня это странная функция, потому что я довольно поверхностно понимаю замыкания. (Один недостаток реализации языковых функций в то же время, когда я их изучаю…) Я знаю, что замыкания в функциональных языках имеют математическую основу, но на данный момент я думаю о них как о функции, сохраняющей доступ к локальным переменным, которые технически недоступны. его масштаба. Итак по схеме:
(define (addn x y) (+ x y)) (define add-factory (lambda (x) (lambda (y) (addn x y)) )) (define add6 (add-factory 6)) (define add4 (add-factory 4))
Здесь мы делаем следующее: сначала определяем функцию с именем addn, которая складывает два числа вместе. Затем add-factory — это функция, которая генерирует функции, принимающие один параметр, и добавляет его к значению, переданному в add-factory.
So:
(add6 3) > 9 (add4 17) > 21 (+ (add6 3) (add4 -3)) > 10
Мое наивное решение, которое, вероятно, теоретически неверно и, возможно, действительно глупый способ сделать это, заключается в том, что когда я выполняю лямбда-метод и генерирую возвращаемую функцию, я ищу любые ссылочные имена в областях (кроме верхней/глобальной области) и замените их ссылку значением. Таким образом, add6 не хранит (+ x y) для тела своей функции и не ссылается на копию y. Он просто сохраняет (+ x 6). Я уверен, что с этим есть проблемы.
Еще одна моя идея реализации замыканий заключалась в том, чтобы создать объект области действия при создании функции, а не при ее вызове, и поддерживать его посредством образа жизни объекта функции. Затем переменную замыкания можно скопировать в int и ссылаться на нее по мере необходимости, и не имеет значения, переработан ли оригинал. Я думаю, что это лучше соответствует теоретической модели того, что такое замыкание, но мой вариант поиска и замены очень прост и не требует длительного хранения объекта области видимости.
Полагаю, мы еще посмотрим, выдержит ли мой первый удар всю 8-ю главу, и в любом случае, после того, как я закончу Маленького интригана, я хочу в какой-то момент взять Lisp In Small Pieces, чтобы увидеть, как на самом деле реализует неигрушечный интерпретатор схем. Я немного ломал голову над оптимизацией хвостовых вызовов.
Это все для этого обновления! Я хочу написать несколько постов о моем впечатлении от Scheme в целом, обсудить C и мои ошибки, связанные с ним. Но сейчас, когда «Маленький интриган» пройден на три четверти, я могу просто подождать, пока не закончу книгу.
Я называю свой интерпретатор notion и его код есть на github. Пожалуйста, не осуждайте мои попытки новичка в C.
