kedebug

非专业搬砖技术研究

LispEx - 让 Lisp 支持并发编程

| Comments

LispEx 是用 Go 语言编写的一款符合 R5RS 标准的 Lisp 解释器。有意思的地方是, 在设计之初我就考虑是否能为其添加一些并发编程的语言特性,让这门古老的编程语言充满生机起来。

于是便选择了 Go 语言来实现它,耗时近 2 个月。Go 里面的一些特性如: goroutine, channel, select 等语义都在 LispEx 中有了支持。

  • 遵守 KISS 原则,尽量把代码设计的简单,易懂。很多模块被很好的分离出来,想添加新的语义支持的话,只需要添加、修改个别文件的源代码。

  • 借鉴了王垠大神 yin 语言的代码设计思路:任何一个 Node 都会被解释成 Value;Parser 被拆分成了 2 个阶段:包括预处理生成语法单元, 然后 Parse 成语法树。顺着这个思路,代码会变得非常易读,当然在设计的时候针对这点是费了很多心思的,希望对一些后人能有借鉴意义。

  • 并发的词法分析器。这点 Rob Pike 在 Lexical Scanning in Go 提到过。 LispEx 把它实践了一遍。相关视频也可以在 Youtube 上面搜索到,感兴趣的同学可以去看看,应该会有所启发。

  • Go-liked 并发语义支持。下面一段代码演示了并发编程里面经典的 ping-pong 案例,并且借助 channel 实现了信号量:

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
35
36
37
; define channels
(define ping-chan (make-chan))
(define pong-chan (make-chan))
; define a buffered channel
(define sem (make-chan 2))

(define (ping n)
  (if (> n 0)
    (begin
      (display (<-chan ping-chan))
      (newline)
      (chan<- pong-chan 'pong)
      (ping (- n 1)))
    (chan<- sem 'exit-ping)))

(define (pong n)
  (if (> n 0)
    (begin
      (chan<- ping-chan 'ping)
      (display (<-chan pong-chan))
      (newline)
      (pong (- n 1)))
    (chan<- sem 'exit-pong)))

(go (ping 6))  ; start ping-routine
(go (pong 6))  ; start pong-routine

; implement semaphore with channel, waiting for ping-pong finishing
(<-chan sem) (newline)
(<-chan sem) (newline)

; should close channels if you don't need it
(close-chan sem)
(close-chan pong-chan)
(close-chan ping-chan)

; the output will be: ping pong ping pong ... exit-ping exit-pong

怎么样?到这里会不会觉得 LispEx 还有点意思?下面看看 select 语义在 LispEx 中是如何实现的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(define chan-1 (make-chan))
(define chan-2 (make-chan))

(go (chan<- chan-1 'hello-chan-1))
(go (chan<- chan-2 'hello-chan-2))

; sleep for 20 millisecond
(sleep 20)

(select
  ((<-chan chan-1))
  ((<-chan chan-2))
  (default 'hello-default))

(close-chan chan-1)
(close-chan chan-2)

; the output will be randomized: hello-chan-1 or hello-chan-2

到这里的代码是不是和 go 语言似曾相识?没错,上述代码都是可以通过 LispEx 直接解释执行的。 实际上,整个工程很大的精力是在基于 R5RS 文档标准在构建 Lisp 的基本语义框架,如闭包、柯里化、解引用等, 而 go, channel, select 等语义在这个框架上的实现是非常轻松自然的。

为什么这么说,下面来看看 go 关键字的语义在 LispEx 代码中是如何实现的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type Go struct {
  Expr Node
}

func NewGo(expr Node) *Go {
  return &Go{Expr: expr}
}

func (self *Go) Eval(env *scope.Scope) Value {
  // We need to recover the panic message of goroutine
  go func() {
    defer func() {
      if err := recover(); err != nil {
        fmt.Println(err)
      }
    }()
    self.Expr.Eval(scope.NewScope(env))
  }()
  return nil
}

func (self *Go) String() string {
  return fmt.Sprintf("(go %s)", self.Expr)
}

个人认为 LispEx 在设计上还算是扩展性良好,再加上 golang 中的 interface 神器, 基于连接/组合的编程范式可以让代码流程变得异常清晰,这也是我喜欢 golang 的一个原因。

最后附上 当初在 V2EX 上的讨论帖以及 GitHub 地址,have fun!

Comments