0x06.如何实现一个解释器 in Racket

发表于 更新于

前言

本文是6. From Substitution to Environments的实验记录。

计划

  • Define a environment
  • Implement lookup in environment

codes

  1. Define a environment as list.
1
2
3
(define-type Binding
  [bind (name : symbol) (val : number)])
(define-type-alias Env (listof Binding))
  1. Implement lookup in environment
1
2
3
4
5
6
7
8
; DONE : Define lookup
(define (lookup [for : symbol] [env : Env]) : number
  (cond
    [(empty? env) (error 'lookup "name not found")]
    [else (cond
            [(symbol=? for (bind-name (first env)))
             (bind-val (first env))]
            [else (lookup for (rest env))])]))
  1. Substitution VS Env(1st version)
1
2
3
4
5
6
7
8
9
10
11
; Error case in our implementation of Env 1st.
; Our test case equal to
; (define (f1 x) (f2 4))
; (define (f2 y) (+ x y))
; (f1 3)
; If we take a look, we will find error binding that x 
; is not binded in f2's definition.
(interp (appC 'f1 (numC 3))
                    mt-env
                    (list (fdC 'f1 'x (appC 'f2 (numC 4)))
                          (fdC 'f2 'y (plusC (idC 'x) (idC 'y)))))
  1. detect error occus
1
2
3
4
5
; env cross scope
<appC-interp-bind-in-env>
                         (extend-env (bind (fdC-arg fd)
                                           (interp a env fds))
                                     env)
  1. Corret last error binding
1
2
3
4
5
; change env to mt-env
<appC-interp-bind-in-env>
                         (extend-env (bind (fdC-arg fd)
                                           (interp a env fds))
                                     mt-env)
  1. Scope in 3 terms
    6.1. Is it bound?
    6.2. where?
    6.3. Does it has parent scope?

系列文章

本系列文章旨在从零实现一个完整的解释器：

  1. 0x06 - 环境实现 - 从代换到环境
  2. 0x07 - 闭包与可变量 - 支持赋值和闭包

查看完整系列 →