用Lisp写一个解释器

  10 mins to read  

TL; DR

  • Scheme的特点
    • 语法简洁统一
    • 面向求值
    • 递归
    • 双范式
    • 语法并不是绝对统一
    • Metaprogramming & S-expression
    • Continuation
    • Hygienic Macro
  • Scheme不适合工程开发
    • 无拿得出手的开发工具
    • 生态差
    • 动态类型
    • 代码难以用肉眼parse
    • ChezScheme debug反人类
  • 如何写解释器
    • Lexer => Parser => Interpreter
    • Lexical scoping
    • immutable实现mutable的问题
    • 正则序和应用序

Scheme的特点

语法简洁统一

语法采用S-expression,所有语法元素都是广义表

数字运算使用前缀表达式,这样就可以把所有的运算符当作函数,也就可以消除运算符这个概念

整体的语法简洁统一,不举例了,详见rnrs

面向求值

语句都有返回值(语句而不是函数),函数返回值为最后一条语句计算的值

(define foo (if #t 1 2))

递归

for, while等循环语句,用递归替代循环。rnrs要求必需实现严格尾递归优化,所以只要代码写的没问题一般不会出现OOM

习惯用named-let实现循环

(let loop ((lst lst))
  (if (null? lst)
    'end
    (let ((ele (car lst)))
      (printf "~s\n" ele)
      (loop (cdr lst)))))

双范式

Scheme并不像传统函数式语言一样只有函数式数据结构,它还提供了set!

包括record类型可以声明可变字段

(define-record-type foo (fields (mutable x)))
(define f (make-foo 1))
(foo-x-set! f 2)

还有显得完全乱入的hashtable,list, vector等其它复合类型实现不了下面的例子

(define h (make-eq-hashtable))
(define lst `(,h))
(hashtable-set! (car lst) 'k 'v)
(eq? (hashtable-ref h 'k 'null)
     (hashtable-ref h 'k 'null))

语法并不是绝对统一

语法中有一个元素叫form

(case 1
  (1 '1))
  
(case 1
  ((1) '1))
  
(define fn (lambda () 1))

(case 1
  (fn '1))
  
(case 1
  ((fn) '1))
  
(case 1
  (((fn)) '1))

歧义出现了

又或者说cond的语法(我个人更愿意用cond代替if):

(if 1
  (begin
    (display 1)
    (display 2))
  (begin
    (display 3)
    (display 4)))
    
(cond
  ((= 1 1) (display 1)
           (display 2))
  (else (display 1)
        (display 2)))

看到了吗,因为if的语法限制导致多条语句中必须使用begin,而不能直接((display 1) (display 2)),如果这样写实际的求值顺序也是UB:

> (if #t ((display 1) (display 2)) 'F)
21

而在cond里,每一个condition的body中都可以添加随意数量的语句,所以在保持语法统一上,cond更优。但实际上某些Scheme实现里会用if来实现cond

Metaprogramming & S-expression

Scheme中代码与数据都是S-expression

(define code '(display 1))
(eval code)

得益于语法的统一,代码数据没有绝对的界限

Continuation

中文译为延续,解释为:

During the evaluation of a Scheme expression, the implementation must keep track of two things: (1) what to evaluate and (2) what to do with the value. … We call “what to do with the value” the continuation of a computation.

continuation涉及到CPS(Continuation-Passing-Style)风格,此处不详细介绍

说白了,就是将evaluation时的环境和后续计算打包保存下来

(* 3 (call/cc 
       (lambda (k)
         (k 2))))

continuation可以实现generator,也就是像Python中yield的语法,进而实现coroutine

假如说要用pure C实现,是不可能的。因为C语言中函数返回控制权只能是return后,也就意味着函数栈帧销毁了。所以想实现只能在汇编层面,将局部变量以及执行位置存入寄存器。ucontext.hlongjmp/setjmp就是这样实现的

在Scheme中,得益于continuation是个一级对象,可以利用它来实现coroutine

;; http://deathking.github.io/yast-cn/contents/chapter16.html
;; abbreviation
(define call/cc call-with-current-continuation)

;; queue
(define (make-queue)
  (cons '() '()))

(define (enqueue! queue obj)
  (let ((lobj (list obj)))
    (if (null? (car queue))
    (begin
      (set-car! queue lobj)
      (set-cdr! queue lobj))
    (begin
      (set-cdr! (cdr queue) lobj)
      (set-cdr! queue lobj)))
    (car queue)))

(define (dequeue! queue)
  (let ((obj (car (car queue))))
    (set-car! queue (cdr (car queue)))
    obj))


;; coroutine   
(define process-queue (make-queue))

(define (coroutine thunk)
  (enqueue! process-queue thunk))

(define (start)
   ((dequeue! process-queue)))
   
(define (pause)
  (call/cc
   (lambda (k)
     (coroutine (lambda () (k #f)))
     (start))))


;; example
(coroutine (lambda ()
         (let loop ((i 0)) 
           (if (< i 10)
           (begin
             (display (1+ i)) 
             (display " ") 
             (pause) 
             (loop (1+ i)))))))
           
(coroutine (lambda ()
         (let loop ((i 0)) 
           (if (< i 10)
           (begin
             (display (integer->char (+ i 97)))
             (display " ")
             (pause) 
             (loop (1+ i)))))))

(newline)
(start)

Hygienic Macro

译为卫生宏,与C中不卫生的宏不同,卫生宏展开时不会污染命名空间,即变量捕获是没有问题的;而不卫生宏就是一个简单的文本替换

#define MACRO(foo) do {       \
    int bar = 1;              \
    printf("%d", foo * bar);  \
} while(0)

int main() {
    int foo = 2;
    int bar = 3;

    MACRO((bar + 1));
}
(define-syntax macro
  (syntax-rules ()
    ((_ foo)
     (let ((bar 1))
       (display (* foo bar))))))

(define foo 2)
(define bar 3)
(macro (+ bar 1))

输出分别为2和4,虽然Scheme的宏也是在编译器展开,及展开时不涉及求值,但(macro (+ bar 1))中bar的定义来源于调用处的scope

Scheme不适合工程开发

无拿得出手的开发工具

我用vsc插件vscode-chez v0.1.2,功能基本只有一些常见结构的snippets,诸如格式化,定义跳转都没有,连高亮也是个残次品(字符串中的注释符都被识别为注释)

Scheme的S-expression解析起来很方便,但还是没有人做开发工具,也从侧面印证了生态不行

生态差

不说了,什么轮子都自己造。当然,调用C语言的链接库还是挺方便的,所以很多Scheme库都是仅用Scheme做上层接口

针对这一点,Lisp方言中Clojure应该是最好的选择,CL也会优于Scheme

动态类型

不多说,动态类型的通病

代码难以用肉眼parse

))))))))))))))))))))))))))))))))))))))

ChezScheme debug反人类

chezscheme是一个神一样的编译器,编译速度和编译生成的代码速度都很快,脚本语言中无压力吊打lua。王垠说能媲美C,这点当然用脚趾头想都知道真假

快是它的优点,但是,…,它编译后代码中所有的runtime exception都没有行号,也就意味着写完了代码,运行后报错,但它不告诉你是哪一行,又没有合适的debugger,所以就得在程序的执行流中print,

如何写解释器

吐槽完了,说说如何写解释器吧

目标是使用Scheme完成一个类C语言的解释器,特性是:

  • 动态语言
  • 强类型
  • lexical scoping
  • with class

repo地址是https://github.com/EddieIvan01/yakult

由于2020年新型肺炎,在家为消磨时间开了坑,之后发现工作量太大,写起来心累,于是👴果断决定暂弃坑

Lexer => Parser => Interpreter

Lexer其实很简单,就是一个简单的分词器,去掉空格注释换行之类的,将源码解析为token流即可,一个有限状态机即可搞定(或者用regexp来做也可以,但会做不必要的回溯损失性能)

我在解析时维护一个pointer来递归,这样就可以方便的任意移动。而如果用car/cdr来做递归的话,就比较麻烦了

yakult里的分词阶段把所有的特殊符号归类到token::symbol中了,其实这里可以做更细粒度的划分,比如划分token::paren-open / token::paren-close等等,但这里不做留到paser里判断也是可以的

它的输入输出是这样的:

(import (lexer))

(define code "let a = 2 * (1 + 3)")
(printf "~s" (scan code))

OUTPUT:

(#[#{token::keyword ettq95xxtz6ic726sbbnaqs44-7} let] #[#{token::ident ettq95xxtz6ic726sbbnaqs44-8} a] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} "="] #[#{token::number ettq95xxtz6ic726sbbnaqs44-10} 2] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} "*"] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} "("] #[#{token::number ettq95xxtz6ic726sbbnaqs44-10} 1] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} "+"] #[#{token::number ettq95xxtz6ic726sbbnaqs44-10} 3] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} ")"] #[#{token::endline ettq95xxtz6ic726sbbnaqs44-11}] #[#{token::eof ettq95xxtz6ic726sbbnaqs44-12}])

Parser负责解析Lexer的输出,也就是接受token流为输入,以endline为分割解析成AST,最后的输出是每条语句的AST

像这样:

(import (parse))
(import (lexer))
(import (ast))

(define code "let a = 2 * (1 + 3);")
(define t (scan code))
(define a (parse t))

(printf "~s" a)


OUTPUT:

(#[#{ast::define daqf9vsq5uvx5qezt929ps0q9-7} a (#[#{ast::* daqf9vsq5uvx5qezt929ps0q9-8} #[#{token::number daqf9vsq5uvx5qezt929ps0q9-9} 2] #[#{ast::+ daqf9vsq5uvx5qezt929ps0q9-10} #[#{token::number daqf9vsq5uvx5qezt929ps0q9-9} 1] #[#{token::number daqf9vsq5uvx5qezt929ps0q9-9} 3]]])])

这个其实也很简单,唯一的难点是需要设计好每一条分支,尽可能复用代码(前期我没有仔细斟酌,导致代码逻辑分支有冗余,不够完善)

Interpreter接受AST为输入,解释执行即可,解释执行的过程是重点,后面讲

Lexical scoping

lexical scoping相对于dynamic scoping,区别在于捕获自由变量时的行为

lexical scoping在函数调用时从函数定义处的scope获取变量,而dynamic scoping则从函数的调用栈往上捕获变量

A = 1

func foo() {
	print A
}

func bar() {
	A = 5
	foo()
}

当调用bar时,lexical scoping会输出1,而dynamic scoping会输出5

为了实现lexical scoping,需要将函数定义处的环境保存在函数对象里,也就是closure,而函数调用时的自由变量,应当从当前函数的闭包中获取

当扩展环境形成新作用域时只需要从旧作用域扩展即可,而一个环境只会扩展自一个环境,所以所有环境其实可以表示为一个树形结构

               GLOBAL-ENV
              /          \
             ENV-0      ENV-1
           /
         ENV-2

而针对这棵树的查询操作只会从叶向根,所以只需要用一个列表保存所有的节点,每个节点中保存父节点的索引即可

env.ss中定义了env的相关操作

(define-record-type env (fields vars ref))

(define-syntax new-env
  (syntax-rules ()
    ((_ all-env)
      (define env (make-env (make-eq-hashtable) 'null))
      (set! all-env (append all-env `(,env)))
      env)))

(define-syntax ext-env
  (syntax-rules ()
    ((_ ref-env all-env)
      (define env (make-env (make-eq-hashtable) ref))
      (set! all-env (append all-env `(,env))))))

(define-syntax env-set!
  (syntax-rules ()
    ((_ env-index name val all-env)
      (let ((value (hashtable-ref 
                    (env-vars 
                      (list-ref all-env env-index)) 
                    name 'null)))
        (cond
          ((eq? value 'null)
          (let ((ref (env-ref (list-ref all-env env-index))))
            (cond
              ((eq? 'null ref) (halt "Undefined"))
              (else (let loop ((env (list-ref all-env ref)))
                (define h (env-vars env))
                (define value (hashtable-ref h name 'null))
                (case value
                  ('null (loop (list-ref all-env (env-ref env))))
                  (else
                    (hashtable-set! h name val))))))))
          (else (hashtable-set! 
                  (env-vars 
                    (list-ref all-env env-index) 
                    name val))))))))

(define env-lookup
  (lambda (env-index name all-env)
    (define env (list-ref all-env env-index))
    (let ((value (hashtable-ref 
                    (env-vars env) 
                    name 'null)))
      (cond
        ((eq? value 'null)
          (let ((ref (env-ref env)))
            (cond
              ((eq? 'null ref) 'null)
              (else (env-lookup ref name all-env)))))
        (else value)))))

这里的new-env, ext-env, env-set!为什么我要用宏而不是函数,我猜你肯定明白

immutable实现mutable的问题

为什么会有这个问题?假如只需要实现函数式数据结构(比如用Scheme实现Scheme),那么就不需要上一条里的三个宏了

正则序和应用序

虽然Scheme是个解释型语言,但它的宏也不可以递归

实际等同于编译期替换,即先扩展后求值。更佳的解释是宏是正则序,而函数是应用序

你可以试下下面这段代码,会无限展开

(define-syntax foo
  (syntax-rules ()
    ((_ lst)
     (if (null? lst)
       'end
       (begin
         (printf "~s\n" (car lst))
         (foo (cdr lst)))))))


(define lst '(1 2 3 4 5))
(foo lst)