諺
Racket实现计算器解释器
2018-06-22 / modified at 2022-04-04 / 1.7k words / 7 mins
️This article has been over 2 years since the last update.

本文是纯折腾兴趣，时间充裕的可以玩一玩。

面向读者

LISP是世界上第二古老语言，目前国内折腾LISP的人并不多。首先明确本文目标是扩大视野，掌握FP编程范式，而不是学习Racket(LISP的一种实现)本身语法以及各种库，对读者要求如下

  • 掌握Java或一门动态语言
  • 有足够多的时间去折腾LISP，看得懂英文文档
  • 预先看完SICP的前两章

优缺点对比

如果你打算花时间学习Lisp，要明确如下

不足

  • 学习曲线高，几乎全是英文文档，缺乏IDE，甚至StackoverFlow提问都不多
  • 没有丰富的库，而且各种GPL协议对商业不友好
  • 经济效益低，几乎没有公司招聘Lisp，实际项目LISP基本用不上

优点

  • 学会了更多的编程思想，比如模式匹配，高阶函数，S表达式
  • 类比学习设计模式/注解/JVM解释器时更加容易理解，比如Akka或者Erlang，直接上手是看不明白的
  • 对后面折腾大数据/AI等高级数据的解析有一定帮助

S-Expression

S表达式是编程语言中最简洁的描述结构了(S-Expressions are a text-based representation of tree-structured data.)，比如``(+ 1 2)`。不用去直接操作各种字符串，而是通过内置函数(比如car,cdr,match)就可以直接操作SExpr，总之用一句话表达就是“括号大法好”。

借助S表达式，相比于Java可以更直观地理解

  • 各种树的遍历(不需要自己折腾native datastructure与模式匹配)
  • 编译原理(直接操作AST)
  • eval

在Racket中，直接可以用read进行解析，源码基于C，有5000多行，用一堆表达式与Switch实现的。

在理解了S表达式后，后面才能实现计算器/Markdown等更难的解析

类比: AngularJS

在AngularJS中，有很多表达式也可类比为S表达式，比如<span ng-bind="x|json">，这里面在进行Direactive操作时，将会调用scope.$eval(attr.ngBind)对x|json进行解释执行，思想都是一样的。

λ表达式语法

λ表达式在js，以及各种JVM语言均有，Racket语法如下

1
2
3
4
5
6
#lang racket
(define sum
  ; 此处的(a b)括号不能省略
  (λ (a b)
    (+ a b)))
(sum 1 3)

用Groovy的写法是这样的

1
2
def sum = {a, b -> a + b}
sum.call(1,3)

用Java8的BiFunction接口进行模拟，可以看出是强类型，强参数的

1
2
3
4
5
6
7
BiFunction<Integer,Integer,Integer> sum = new BiFunction<Integer, Integer, Integer>() {
    @Override
    Integer apply(Integer a, Integer b) {
        return a+b;
    }
}
sum.apply(1,3)

我在后面所有的函数定义中，全部使用λ进行包装

在DrRacket中使用cmd+\进行输入λ，cmd+i可以格式化代码

模式匹配(PatternMatch)

模式匹配实际上就是一个有限状态机，看起来就是对Map<pattern, λ>执行的状态转移。在Racket中，连S表达式都可以匹配，而在C/Java中，只能匹配数字或者字符串。

计算Fib

计算f(x)=f(x-1)+f(x-2)

实现方法

1
2
3
4
5
6
7
8
9
#lang racket
(define fib
  (λ (exp)
    (match exp
      [0 0]
      [1 1]
      [_ (+ (fib (- exp 1)) (fib (- exp 2)))])))
(fib 10)
;; => 55

用Groovy的写法是这样的

1
2
3
4
5
6
7
8
9
def fib;
fib = {exp->
    switch (exp){
        case 0: return 0
        case 1: return 1
        default: return fib.call(exp-1) + fib.call(exp-2)
    }
}
fib.call(10)

打印BinaryTree

二叉树的深度遍历，方便进行直观理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
; racket draw Binary Tree
#lang racket
; 导入绘图工具类
(require pict pict/tree-layout)
; 判断Token是否是单个元素
(define (atom? x) (not (or (pair? x) (null? x))))
; 定义一个名为gen-ast,入参为exp的函数
(define gen-ast
  (λ (exp)
    (match exp
      [(? atom? leaf)   ;如果为叶子
       (tree-layout #:pict (text (~v leaf)))] 
      [`(,op,l,r)        ;对S表达式进行遍历
       (let ([v1 (gen-ast l)]
             [v2 (gen-ast r)])
         (tree-layout #:pict (text (~v op)) v1 v2))])))
; 将生成的 tree-layout 赋值到 tree 变量
(define tree (gen-ast `(+ 1 (+ (* 2 5) (/ 2 4)))))
; 执行绘图
(naive-layered tree)

生成的结果是这样的

ast.png

Racket与递归下降

递归下降(RDP, recursive-descent parser)也称为左递归，它涉及到一种叫做BNF的DSL，本文暂且不引入，主要是提一下这个概念。

Racket上实现计算器

实现一个计算器一般有如下几步

1
String-(Lex)->Tokens-(Parser)->AST->(interp)->RESULT

其中

  • Lex: 指Lexical Analyzer，词法分析。可以使用lex这款工具(内部是通过正则表达式实现分词)或者自己写递归下降来实现
  • Parser: 指语法分析，将Token转为AST，可以通过YACC(Yet Another Compiler Compiler)实现。

Lexical Analyzer

此部分实现将字符串解析为S表达式

1
"1+2*(5.5+3)" => `(1 + 2 * ( 5.5 + 3))

在Racket官方example中，使用了Lex工具搞定，本文结合多个demo，最终如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
; 引入工具库与前缀
(require parser-tools/lex)
(require (prefix-in : parser-tools/lex-sre))
; +-x/的正则表达式
(define-lex-abbrevs (op (:or #\+ #\- #\* #\/)))
; [a-z]|[A-Z]的正则表达式
(define-lex-abbrevs (word (:or (char-range #\a #\z) (char-range #\A #\Z))))
; \d 的正则表达式
(define-lex-abbrevs (digest (char-range #\0 #\9)))
; \d+\.?\d*
(define-lex-abbrevs (float (:: (:+ digest) (:? #\.) (:* digest))))
(define calc-lexer
  (lexer
   [(:+ word)
    (cons (string->symbol lexeme)
          (calc-lexer input-port))]
   [#\( 
    (cons 'L
          (calc-lexer input-port))]
   [#\)
    (cons 'R 
          (calc-lexer input-port))]
   [float
    ; =>
    (cons (string->number lexeme)
          (calc-lexer input-port))]
   [op
    (cons (string->symbol lexeme)
          (calc-lexer input-port))]
   [whitespace 
    (calc-lexer input-port)]
   [(eof)
    '()]))
(calc-lexer (open-input-string "-3*(88 + 12333.44444)-(4*5)"))

上面本质上还是一个正则表达式的递归匹配，其中 lexeme 是历史遗留的全局变量(这是一个反模式，设计的极其糟糕)，用于存储结果

Parser

此部分将括号转为前缀表达式

1
`(1 + 2 * ( 5.5 + 3)) => `(+ 1 (* (+ 5.5 3) 2))

Eval

此部分执行计算，入参是转换完成的前缀表达式，参考垠神写的怎样写一个解释器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#lang racket
; 定义一个名为 eval-ast,入参为exp的函数
(define eval-ast
  (λ (exp)
    (match exp
      [(? number? leaf) leaf] ;说明已经是叶子
      [`(,op,l,r)        ;对S表达式进行遍历
       (let ([v1 (eval-ast l)]
             [v2 (eval-ast r)])
         (match op
           [`+ (+ v1 v2)]
           [`- (- v1 v2)]
           [`* (* v1 v2)]
           [`/ (/ v1 v2)]))])))
; 执行计算
(eval-ast `(+ 1 (+ (* 2 5) (/ 2 4))))
;; => 11.5

相比Java中用String/枚举与t.left == null的实现，这里代码没有一行废话; 同时由于支持类型推导，避免了Java中各种int转换与小数点的问题

附录