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
go macro to start new
> (go (begin (write 1) (write 2) (write 3)) (begin (write 'a) (write 'b) (write 'c))) 1a2b3c > ;; this is one possible output
fibers can communicate with each other using
(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-...
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.
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)))))
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!