Lexical vs Dynamic interpreter in Scheme language

Question

I still do not understand how a dynamic interpreter differ from a lexical one.

I am working on scheme and i find it very difficult to know how a simple code like these one works dynamically and lexically.

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

any guidance?

Answer 1

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

This is a not a very good example to understand the difference between dynamic and static binding. It's merely a corner case.

The idea is, in static binding the free variables are associated with the static scope (the lexical code that is visible when writing) and in dynamic binding, they are associated with the dynamic code (what is stored on the execution stack).

Your code evaluates to a result that is this lambda expression:

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

In this result, the only free variable is X.

What is the value of X when you apply the result to a value for Y?

In static scoping, it will be 2018, in dynamic binding the value of X will be stored on the stack--for example,

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

will apply result with a bound X=100 (X's will be kept on the stack). Of course, X's value is not physically kept on the stack, just a pointer to the environment frame where it is, or maybe in a value cell if a rerooting is performed on the environment, etc.

To understand your misunderstanding you can take a course of lambda calculus. And, of course, what I said here supposes you use the common interpretation, many other interpretations can be associated to the same syntax as your input example, etc.

Answer 2

Lexical bindings have limited visibility and unlimited lifespan. All functions "remember" environment, where they were created- that kind of functions is called lexical closures.

In your example, this part:

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

returns function, which remembers environment with x = 2018. That function is bind to symbol mystery and when you call it, it changes value of x in that environment.

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

In Scheme with dynamic bindings (unlimited visibility, limited lifespan), functions don't remember environment, where they were created. So, function mystery won't remember environment with x = 2018 and call (mystery 1) ends with error during evaluation of (cons x y), because symbol x has no value.

Answer 3

Lets just make a program with your code:

;; 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)

Results from a normal Scheme relies only on closures and not about the call stack bound variables:

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

Results from a dynamic "Scheme" has the let in mystery as dead code. It does nothing since the bindings are not saved with the function object. Thus only the variables in active let and calls are matched:

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