Dynamic Scope Interpreter

Dynamic scope is an old idea in programming languages, back to 60s the origin of Lisp. Simply put, dynamic scoping means that the scope of identifiers will be dynamically changed. From the view of interpreter, dynamical scope is there is only one environment when the program is running.

So what is an Environment? An Environment is a set of bindings.

And what is a binding? A binding is just a pair of an identifier and a value.

So we can think that an environment as a map which maps identifiers to values, and we can also lookup value given an identifier.

If a programming language is dynamic scoped, it uses the global environment when it needs to lookup some variable, also to update a variable with a value. The environment accumulates all bindings together as the program executes. As a result, whether an identifier is bounded depends on the history of program execution.

On the contrary, if a language is static scoped (lexical scope), every time when we create a new scope level (function, in purely functional programming), we will also remember the current environment, which includes all identifiers can be accessed by that function lexically. This environment will also contains definitions which are defined outside of the function, say free variables. We name the function along with that environment as closure (because it closes the free variables).

A little bit history is some languages, such as the very early Lisp, Emacs Lisp, and Bash are both dynamic scoped languages. Acutally the early Lisp and Emcas Lisp is designed to be dynamically scope. According to its creator Richard Stallman, programs to be static scoped is too slow to run on 60s or 70s computers. In 70s, Scheme is the first dialect of Lisp with static scope.

The following code shows a simple implementation of dynamic scoping interpreter in Typed Racket. It’s a simple language, but shows the core idea of dynamic scope that environment accumulates all bindings along the program runs.

#lang typed/racket

; A simple dynamically scope interpreter.

(define-type Expr
  (U Void
     Number 
     String 
     Boolean 
     Id
     App
     Plus
     Mult
     Fun
     Begin))

(struct: Id ([s : Symbol]))
(struct: App ([fun : (U Symbol Fun)] [arg : Expr]))
(struct: Plus ([l : Expr] [r : Expr]))
(struct: Mult ([l : Expr] [r : Expr]))
(struct: Fun ([arg : Symbol] [body : Expr]))
(struct: Begin ([exprs : (Listof Expr)]))

(struct: Binding ([name : Symbol] [val : Expr]))

(define-type-alias Env (Listof Binding))
(define extend-env cons)

(: Any? (-> Any Boolean))
(define (Any? anything) #t)

(: lookup (-> Symbol Env Expr))
(define lookup
  (lambda (s env)
    (cond
      [(empty? env) (error 'lookup "name not found")]
      [else (cond [(symbol=? s (Binding-name (first env)))
                   (Binding-val (first env))]
                  [else (lookup s (rest env))])])))

(: dyn-interp (-> Expr Env Expr))
(define dyn-interp
  (lambda (expr env)
    (match expr
      [(? number? expr) expr]
      [(? string? expr) expr]
      [(? boolean? expr) expr]
      [(Id x) (lookup x env)]
      [(Plus x y)
       (cond [(and (number? x) (number? y)) (+ x y)]
             [else (dyn-interp (Plus (dyn-interp x env)
                                     (dyn-interp y env)) env)])]
      [(Mult x y)
       (cond [(and (number? x) (number? y)) (* x y)]
             [else (dyn-interp (Mult (dyn-interp x env)
                                     (dyn-interp y env)) env)])]
      [(App fun arg)
       (cond [(symbol? fun)
              (let ([fn (lookup fun env)])
                (cond [(Fun? fn) (dyn-interp (App fn arg) env)]
                      [else (error 'dyn-interp 
                                   (string-append "can not apply " (symbol->string fun)))]))]
             [(Fun? fun)
              (dyn-interp (Fun-body fun)
                          (extend-env (Binding (Fun-arg fun) (dyn-interp arg env)) env))])]
      [(Begin exprs)
       (foldl (lambda ([x : Expr] [y : Expr])
                (dyn-interp x env)) (void) exprs)]
      [(? Any? x) x])))

; test

(define t1 (Plus (Id 'x) (Id 'y)))
(define t2 (Mult 3 t1))
(define add1 (Fun 'x (Plus (Id 'x) 1)))
(define env0
  (list (Binding 'x 1)
        (Binding 'y 2)
        (Binding 'add1 add1)))

(define f1 (App (Fun 'x (App (Fun 'y (Plus (Id 'x) (Id 'y))) 3)) 4))
(dyn-interp f1 env0)

(define b1
  (Begin (list
          (App 'add1 3)
          (App 'add1 4))))