Лексический и динамический интерпретатор на языке схем

Question

Я до сих пор не понимаю, чем динамический интерпретатор отличается от лексического.

Я работаю над схемой, и мне очень трудно понять, как такой простой код, как этот, работает динамически и лексически.

      (define mystery
  (let ((x 2018))
    (lambda (y)
      (let ((result (cons x y)))
         (set! x (+ x 1))
         result))))

какие-нибудь указания?

Answer 1

Лексические привязки имеют ограниченную видимость и неограниченный срок жизни. Все функции «запоминают» среду, в которой они были созданы - такой вид функций называется лексическим замыканием .

В вашем примере эта часть:

      (let ((x 2018))
    (lambda (y) (let ((result (cons x y)))
                  (set! x (+ x 1)) result))))

возвращает функцию, которая запоминает среду с x = 2018. Эта функция привязана к символу, и когда вы ее вызываете, она изменяет значение x в этой среде.

      > (mystery 1)
'(2018 . 1)
> (mystery 1)
'(2019 . 1)

В Scheme с динамическими привязками (неограниченная видимость, ограниченный срок жизни) функции не запоминают среду, в которой они были созданы. Итак, функция mystery не запомнит среду с x = 2018 и вызовет (mystery 1) заканчивается ошибкой во время оценки (cons x y), потому что символ x не имеет значения.

Answer 2

Давайте просто создадим программу с вашим кодом:

      ;; a global binding
(define x 100)

;; your function
(define mystery
  (let ((x 2018))
    (lambda (y)
      (let ((result (cons x y)))
         (set! x (+ x 1))
         result))))

;; just to add newlines in prints
(define displayln
  (lambda (v) 
    (display v)
    (newline)))

;; a indirect call
(define local-test 
  (lambda (x)
    (displayln x)
    (displayln (mystery 'local))
    (displayln (mystery 'local))
    (displayln x)))

(define global-test
  (lambda ()
    (displayln x)
    (displayln (mystery 'global))
    (displayln (mystery 'global))
    (displayln x)))

;; program
(local-test 1)
(local-test 11)
(global-test 1)
(global-test 11)

Результаты обычной схемы зависят только от замыканий, а не от переменных, связанных со стеком вызовов:

      1
(2018 local)
(2019 local)
1
11
(2020 local)
(2021 local)
11
1
(2022 global)
(2023 global)
1
11
(2024 global)
(2025 global)
11

Результаты динамической «схемы» остаются загадкой как мертвый код. Он ничего не делает, поскольку привязки не сохраняются с объектом функции. Таким образом, только переменные в активном let и звонки совпадают:

      1
(1 local)
(2 local)
3
11
(11 local)
(12 local)
13
100
(100 global)
(101 global)
102
102
(102 global)
(103 global)
104

Answer 3

      (define mystery
  (let ((x 2018))
    (lambda (y)
      (let ((result (cons x y)))
         (set! x (+ x 1))
         result))))

Это не очень хороший пример для понимания разницы между динамической и статической привязкой. Это просто угловой случай.

Идея состоит в том, что при статическом связывании свободные переменные связаны со статической областью видимости (лексический код, который виден при записи), а при динамическом связывании они связаны с динамическим кодом (который хранится в стеке выполнения).

Ваш код оценивается как это лямбда-выражение:

      (lambda (y)
  (let ((result (cons x y)))
    (set! x (+ x 1))
    result))

В этом результате единственная свободная переменная - это X.

Каково значение X, когда вы применяете результат к значению для Y?

В статической области видимости будет 2018 год, при динамической привязке значение X будет храниться в стеке - например,

      (define X 100)
(define F (result 200)))

будет применяться result с привязкой X=100(X будут храниться в стеке). Конечно, значение X физически не хранится в стеке, а просто указатель на фрейм среды, в котором оно находится, или, возможно, в ячейке значения, если в среде выполняется повторное рутирование, и т. Д.

Чтобы понять ваше недоразумение, вы можете пройти курс лямбда-исчисления. И, конечно же, то, что я сказал здесь, предполагает, что вы используете общую интерпретацию, многие другие интерпретации могут быть связаны с тем же синтаксисом, что и ваш пример ввода, и т. Д.