View on GitHub

GoLio

Go! Lisp in OCaml

Download this project as a .zip file Download this project as a tar.gz file

GoLio is a Lisp dialect implemented in OCaml. The syntax, semantics and library procedures are a subset of R5RS, with one important addition: a Go-like concurrency model.

Yet another Lisp interpreter ...

> (define (curry func arg1) (lambda (arg) (apply func arg1 (list arg))))
> (map (curry + 2) '(1 2 3 4))
(3 4 5 6) ;; just plain old s-expressions

> (letrec ((even? (lambda (n) (if (= 0 n) #t (odd? (- n 1)))))
           (odd?  (lambda (n) (if (= 0 n) #f (even? (- n 1))))))
           (even? 9875321))
#f ;; proper tail recursion is implemented

> `(1 2 `(10 ,',(+ 2 3)))
(1 2 `(10 ,'5)) ;; nested quasiquote is not very easy to implement right

... with Fibers and Channels

Use the go macro to start new fibers:

> (go (begin (write 1) (write 2) (write 3))
      (begin (write 'a) (write 'b) (write 'c)))
1a2b3c > ;; this is one possible output

The fibers can communicate with each other using chans:

(define ping-chan (make-chan))
(define pong-chan (make-chan))

(define (ping)
  (write (receive ping-chan)) ;; receive and write "ping-"
  (send pong-chan 'pong-) ;; and pong back
  (ping))

(define (pong)
  (send ping-chan 'ping-) ;; send a ping
  (write (receive pong-chan)) ;; and write the received "pong-"
  (pong))

(go (ping)
    (pong))

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

Deadlock detection

If the pong function is written like this:

(define (pong)
  (write (receive pong-chan)) ;; write the received "pong-"
  (send ping-chan 'ping-) ;; and send a ping
  (pong))

The GoLio interpreter will detect the deadlock and raise exception:

$ ./golio deadlock-ping-pong.scm
Dead_lock
Fatal error: exception Type.Dead_lock
Raised at file "src/repl.ml", line 51, characters 17-26
Called from file "src/golio.ml", line 30, characters 10-215

Implemented in OCaml

GoLio is mainly for me to learn the beautiful programming language OCaml while exploring lisp interpreter implementation and concurrent programming.

The fibers are implemented using OCaml threads, and chans are implemented using Event.channel.

Deadlock detection is implemented by keep a record on how many threads are currently waiting/blocked, and how many threads are active/working. If all of the threads are blocked waiting for sending to or receiving from some channel, then we have a deadlock. For a certain channel, it is necessary to keep a record on how many threads are currently waiting for sending to or receiving from it. In that way, when a new send or receive request is issued, whether the calling thread will be blocked by this request can be known and counted.

Buffered channels like in those in Go is once implemented but eventually abandoned in the 0.1 version, since my implementation using Queue.t does not play well with the deadlock detection. But this feature will surely appear in version 0.2.

A Fully Working Example

Here is a prime sieve implemented in GoLio:

;; send 2..n to chan `ch`
(define (gen ch n)
  (let loop ((i 2))
    (if (<= i n)
      (begin
        (send ch i)
        (loop (+ i 1)))))
  (close-chan ch))

;; receive from chan `in` and filter out all multipliers of `m`, send the rest
;; to chan `out`.
(define (filter in out m)
  (let ((x (receive in)))
    (if (eof-object? x)
      (close-chan out)
      (begin
        (if (/= 0 (% x m))
          (send out x))
        (filter in out m)))))

;; filter out all the non-primes from chan `in` and send the primes to chan `out`
(define (sieve in out)
  (let ((x (receive in)))
    (if (eof-object? x)
      (close-chan out)
      (let ((ch (make-chan)))
        (send out x)
        (go (filter in ch x))
        (sieve ch out)))))

;; get the threads going
(define in (make-chan))
(define out (make-chan))
(go (gen in 1000)
    (sieve in out))

;; receive all the primes and print them
(let loop ()
  (let ((x (receive out)))
    (if (not (eof-object? x))
      (begin
        (write x)
        (newline)
        (loop)))))

Thanks

GoLio is my very first OCaml project. It is currently in a very alpha state and under heavy development. I learned so much from writing and polishing it and had so much fun.

If you have any comments, suggestions or questions, please feel free to get in touch. Thanks for viewing!