Памятка, переводчики и замыкания

Question

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

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

РЕДАКТИРОВАТЬ: я сейчас использую ракетку, эквивалентную этому, так что если там легче, вы должны дать мне предложения.

(define-struct var (string)) ;; a variable, e.g., (make-var "foo")
(define-struct int (num)) ;; a constant number, e.g., (make-int 17)
(define-struct add (e1 e2)) ;; add two expressions
(define-struct fun (name formal body)) ;; a recursive 1-argument function
(define-struct closure (fun env)) ;; closures (made at run-time)

(define (envlookup env str)
    (cond [(null? env) (error "unbound variable during evaluation" str)]
        [(equal? (caar env) str) (cdar env)]
        [#t (envlookup (cdr env) str)]))

(define (eval-prog p)
    (letrec
        ([f (lambda (env p)
            (cond [(var? p) (envlookup env (var-string p))]
                    [(int? p) p]
                    [(add? p) (let ([v1 (f env (add-e1 p))]
                                    [v2 (f env (add-e2 p))])
                                        (if (and (int? v1) (int? v2))
                                            (make-int (+ (int-num v1) (int-num v2)))
                                            (error "TTPL addition applied to non-number")))]
                    [(fun? p) (make-closure p env)]
                    [(closure? p) p]
                    [#t (error "bad TTPL expression")]))])
    (f () p)))

Answer 1

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

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

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

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

Answer 2

Похоже, вы хотите создать что-то вроде плоского замыкания или того, что Дибвиг назвал "закрытием экрана". То есть вы должны рекурсивно найти свободные переменные в вашей лямбде, а затем создать представление замыкания, содержащее только эти свободные переменные.

Например,

((lambda (x) (lambda (f) (f x))) a)

создаст замыкание, которое выглядит как [code, a].

Взгляните на Три модели реализации Dybvig для схемы , стр. 88.

Answer 3

Если вы не возражаете прочесть какой-нибудь Haskell, Напишите себе схему за 48 часов демонстрирует, как создаются замыкания: когда встречается выражение (lambda ...), его замыкание просто устанавливается в текущей среде (список привязок от имен к значениям). Когда вычисляется лямбда, ее тело оценивается в контексте этого замыкания плюс привязки аргументов - конечно, не в текущей среде.

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