a tiny interpreter

lil-interpreter.rkt

#lang racket

; 来源：http://www.yinwang.org/blog-cn/2012/08/01/interpreter

;;; 以下三个定义 global-env, ext-env, lookup 是对环境（environment）的基本操作：

;; 空环境
(define global-env '())

;; 扩展：对环境 env 进行扩展，把 x 映射到 v，得到一个新的环境
(define ext-env (lambda (x v env) (cons `(,x . ,v) env)))

;; 查找：在环境中 env 中查找 x 的值。如果没找到就返回 #f
(define lookup
  (lambda (x env)
    (let ([p (assq x env)])
      (cond
        [(not p) #f]
        [else (cdr p)]))))

;; 闭包的数据结构定义，包含一个函数定义和它定义时所在的环境
(struct Closure (procedure env))

;; 解释器的递归定义（接受两个参数，表达式 expression 和环境 env）
;; 共 5 种情况（变量，函数，绑定，调用，数字，算术表达式）
(define interpret
  (lambda (expression env)
    ; 对 expression 进行模式匹配
    (match expression
      ; 变量
      [(? symbol? variable-name)
       (let ([value (lookup variable-name env)])
         (cond
           [(not value) (error "undefined variable" variable-name)]
           [else value]))]
      ; 数字
      [(? number? num) num]
      ; 函数定义
      [`(lambda (,parameter) ,body) (Closure expression env)]
      ; let 绑定
      [`(let ([,variable-name ,exp]) ,body)
       (let ([value (interpret exp env)]) (interpret body (ext-env variable-name value env)))]
      ; 调用
      [`(,exp1 ,exp2)
       (let ([procedure (interpret exp1 env)] [argument (interpret exp2 env)])
         ;  拆解 procedure
         (match procedure
           [(Closure `(lambda (,parameter) ,body) env-save)
            (interpret body (ext-env parameter argument env-save))]))]
      ; 算术表达式
      [`(,op ,exp1 ,exp2)
       (let ([value1 (interpret exp1 env)] [value2 (interpret exp2 env)])
         (match op
           ['+ (+ value1 value2)]
           ['- (- value1 value2)]
           ['* (* value1 value2)]
           ['/ (/ value1 value2)]))])))

;; 解释器的“用户界面”函数。它把 interpret 包装起来，掩盖第二个参数，初始值为 global-env
(define my-interpreter (lambda (expression) (interpret expression global-env)))



(my-interpreter '((lambda (x) (* 2 x)) 3))