A while ago I was recommended to watch this talk about Lisp, where a Lisp interpreter is presented with only several lines of Lisp code, as copied from here:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define eval-expr
(lambda (expr env)
(pmatch expr
[`,x (guard (symbol? x))
(env x)]
[`(lambda (,x) ,body)
(lambda (arg)
(eval-expr body (lambda (y)
(if (eq? x y)
arg
(env y)))))]
[`(,rator ,rand)
((eval-expr rator env)
(eval-expr rand env))])))
pmatch is a pattern match function that evaluates the symbolic input expr, and determines whether it is a symbolic variable, a function or an function application, and env stores arguments that should be parsed to the function. E.g., ((eval-expr '(lambda (x) (+ 1 x))) 5) should return 6, because (eval-expr '(lambda (x) (+ 1 x))) should return a function, which takes argument 5 and return 6. If without env, the incorrect eval-expr would return (lambda (arg) (eval-expr '(+ 1 x))), here, lambda is no more symbolic, but x is still symbolic, and eval-expr does not know how to evaluate x.
With env, it does. The (eq? x y) checks if the symbol given in the body is equal to the lambda argument provided in expr, e.g., it is in the case (eval-expr '(lambda (x) (+ 1 x))) but not in (eval-expr '(lambda (x) (+ 1 y))'). Now when evaluating x with eval-expr 'x, the new env is also passed and eval-expr returns (env x) = arg, which means it is able to evaluate (lambda (arg) (eval-expr '(+ 1 x))) as (lambda (arg) (+ 1 arg)), which is now a normal function without any symbolic expression, hence it can accepts argument 5 and returns 6.
The initialization of env does not matter, e.g., it can be (eval-expr '(lambda (x) (+ 1 x)) (lambda (y) (error "unbounded symbol"))).