Lisp with mult-threaded extension in Haskell

FOPL

简介

这是一个用Haskell写的Lisp解释器。按照课程要求，加入了对多线程的扩展。

编译

需要有ghc
可能要安装parsec(用来解析lisp源文件)

sudo apt-get install cabal-install
cabal update
cabal install parsec

可能要安装libghc6-mtl-dev

apt-get install libghc6-mtl-dev

编译

make

执行

bin/clisp

实现Lisp

简介

作为一个解释器，它要能够读取源文件、通过REPL和用户交互，所以必然会产生不纯的情况。这里用到了几个Monad: Parser, IO, Error
具体实现比较繁琐，由于Haskell的类型系统非常严格，以及通过Monad严格区分纯和不纯的世界，所以写起来相当麻烦。

各部分功能

Main段：读取命令行，判断是启动REPL还是直接执行某个Lisp文件。
Var段：通过IO实现赋值(define set!)
REPL段：读取指令，调用Eval段的函数计算并输出。
Parser段：Lisp的数据类型有标志符、字符串、数字、列表、原始函数（在解释器中定义的函数）、自定义函数、IO函数、IO端口、线程通信口（即MVar)。通过Parsec模块解析代码，每个数据类型对应了一个函数，返回类型都是Parser LispVal。
Print段：定义了如何输出各数据类型。
Eval段：定义了如何求一个Lisp函数值
Primitive段：定义了所有的原始函数(primitive function)。

实现

首先读入的指令类型都是IO String，要通过Parsec解析。各个parse函数从输入的字符串中提取出数据结构，实际上形成了一个语法树。这棵语法树保存为一个LispVal类型的列表。
然后解释器会调用eval对它求值，普通的原子直接输出，如果碰到了define，要在当前环境（environment或context）中定义函数、变量。如果碰到了函数调用，还要对它求值。另外还有一些特殊函数，它们要和环境交互，所以也定义在这儿。
在求值的过程中，可能会发生错误，这时就要抛出异常。于是引进了Error Monad。针对它有一系列函数，如catchError、throwError以及各种Monad的操作。另外由于Haskell是一个纯的语言，不能直接改变变量状态；而如果想实现Lisp中define、set!指令必须要改变某个变量的状态，因此要用IO Monad中的IORef。由于所有的数据基本上都要涉及这两个Monad，干脆将它们合并为一个Monad IOThrowsError，于是代码中开始充斥着各种Monad的操作。

实现多线程

创建线程：使用forkIO，每次fork后都会创建一个新线程，然后主线程会不阻塞地执行下去。
线程间通信：使用MVar

data MVar a
newEmptyMVar :: IO (MVar a)
newMVar      :: a -> IO (Mvar a)
takeMVar     :: MVar a -> IO a
putMVar      :: MVar a -> a -> IO ()

newEmptyMVar和newMVar会创建线程盒子
putMVar会将一个值放入MVar盒子中，如果盒子满会阻塞。
takeMVar可以从一个MVar盒子中取出值，如果盒子为空会阻塞。

在Haskell中写多线程非常方便，但是如果想让Lisp解释器支持多线程，需要付出较大的努力。要和各种Monad搏斗。

在我的解释器中，包含了这些相关的函数：

(fork func args) ;创建一个新线程
                 ;将线程的通信口作为func的第一个参数
                 ;args为剩余的参数
(take mvar)      ;从mvar中读取一个数
(put mvar val)   ;向mvar中写一个数

这样fork出的func可以通过第一个参数获取通信口，而主线程可以通过通信口直接和该线程通信，也可以将通信口传给其它线程（具体见demo）

缓冲通道

通过MVar通信有一个缺陷，一个MVar只能保存一个值，如果对MVar读写失败后会阻塞。这导致多个线程间通信时效率大大降低。比如我想写一个Map-Reduce程序，可能多个线程不能按序规约，如果主线程按序收集则会阻塞。所以需要一个缓冲通道，从线程可以向它写任意多的数据；只要通道中有数据，主线程就能直接读出来。
下面是相关的代码：

(define (newStream)
  (define hole (newMVar))
  (cons (newMVar hole) (newMVar hole)))
(define (readStream s)
  (define item (take (take (car s))))
  (put (car s) (cdr item))
  (car item))
(define (writeStream s val)
  (define hole (newMVar))
  (put (take (cdr s)) (cons val hole))
  (put (cdr s) hole))

一个缓冲通道的入口由两个MVar构成：读端口、写端口。读端口直接连着第一个有效数据，而写端口指向了一个空结点。
下面是两个例子：
空：[readport]->[hole]<-[writeport]
有两个元素：[readport]->[MVar]->[val1|next]->[MVar]->[val2|next]->[MVar]->[hole]->[writeport]
每次写数据时，先生成一个新的空结点hole，然后生成一个pair：(数据 . hole)，再将这个pair存入原来的空结点中。然后更新写端口。
每次读数据时，先从读端口读出第一个MVar，然后再读出其中的数据，然后令读端口指向它的后继。相当于删掉了这个数据。
注意到对MVar读写时，不仅是阻塞的，而且还是互斥的，所以有多个线程一起读写时，不会出错。

demo

首先在shell中输入

bin/clisp

会启动Lisp的REPL，接下来输入

(load "stdlib.scm")

会载入一些标准函数以及demo函数

test1 主线程和创建的线程通信

(test1)

主线程会创建一个从线程，该线程会等待1秒，然后将数据放入通信口，主线程一直在读通信口。于是在阻塞了1秒后会读出该数据。

test2 多个线程间通信

(test2)

首先主线程启动3个从线程（编号为1、2、3），然后将2的通信口传给1，3的通信口传给2，1的通信口传给3。从而3个线程构成了一个环，接着向1写一个数。
每个线程接收到下个线程的通信口后等待1秒，然后从自己的通信口读一个数，输出后加1再传给下个通信口。于是效果就是输出了1、2、3
注：由于主线程在从线程之前就结束了，所以先输出了Prompt："Lisp>>"，然后才输出从线程的结果。这时直接输入下一条指令即可。

test3 Map-Reduce

(test3)

利用缓冲通道。
目的是计算$\sum_{i=1}^{100}i^{2}$，最终结果为338350。
通过test_map生成100个线程，每个线程计算一个数的平方，算完后写入缓冲通道。
主线程生成完100个线程后就启动test_reduce，开始从缓冲通道中读取数据，然后累加起来。
为了表现出缓冲通道的作用，我在计算每个平方之前都delay一段时间。使得看上去好像是乱序完成的。

全部执行完后输入quit退出REPL。

参考

Write Yourself a Scheme in 48 Hours
Haskell并行与并发编程
Learn You a Haskell