Sub Ubi

When time presents itself, I want to start exploring a question that has come up lately: if you were to write a compiler today, what language would you use? This has some pertinence to the Transterpreter project, although not for the immediately foreseeable future.

That said, I thought I’d play a bit with occam as an expression of the CSP algebra, and poke at embedding it in Scheme. Without too much effort, I could easily convert my first attempt (which took an hour-and-a-half) into a general set of macros; a little more effort, and I could make it a new ‘language’ in DrScheme.

For the moment, though, I have a set of 11 pattern matchers (mutually-recursive functions called Expression, Process, Declaration, Type, Communication, Cond, While, Seq, Par, Assignment, and Scheme) that expand a given piece of ‘occam’ into Scheme.

For example, Consumer/Producer (in occam) would look like

CHAN INT chan:
PAR
  INT a:
  SEQ
    a := 0
    WHILE TRUE
      SEQ
        a := a + 1
        chan ! a
  INT b:
  WHILE TRUE
    chan ? b

And in my Schemely implementation of “occam” (with a little extra so we can see what’s going on) Consumer/Producer looks like:

(let ([chan channel])
    (par
     (let ([A int])
       (while true
              (seq
               (:= A (+ A 1))
               (! chan A))))
     (let ([B int])
       (while true
              (seq
               (? chan B)
               (scheme (printf "~a~n" B)))))
     ))

(The ’scheme’ expression lets me insert arbitrary Scheme code into my “occam” program; this is just a cheap trick to let me do things like print values to the console, quickly and easily.)

When I push the above expression through my pattern matchers, I end up with a real Scheme program (go ahead–try it!) that mimics the behavior of a (roughly) equivalent occam program:

(let ((chan (make-channel)))
  (for-each
    (lambda (p) (thread p))
    (list
     (lambda ()
       (let ((A 0))
         (let while2030 ()
           (if #t
             (begin
               (begin
                 (set! A (+ A 1))
                 (channel-put chan A))
               (while2030))))))
     (lambda ()
       (let ((B 0))
         (let while2029 ()
           (if #t
             (begin
               (begin
                 (set! B (channel-get chan))
                 (begin
                   (printf "~a~n" B)))
               (while2029)))))))))

Obviously, none of the guarantees that should be provided by a well-formed expression in the CSP algebra are not present in this 100-line hack. However, because MzScheme is a very expressive implementation of the Scheme programming language, it is easy enough to get something approaching the semantics of occam without too much effort.

To do all the proof-checking (deadlock detection, etc.) would require, effectively, writing the front-end of an occam compiler. However, it is clear that an entire compiler does not need to be written to see if the “occam” program exhibits the correct semantics; I can test “occam” programs by letting MzScheme run an equivalent Scheme program. As long as I’m confident that my interpretation of constructs in occam and CSP are equivalent to the Scheme constructs that I’ve chosen.

But this is all silliness; that was an hour-and-a-half I could have used in other ways. My apologies.

Updated, 23:31: Adam pointed out my original example would never pass a respectable occam compiler; I suspected this, but wasn’t shure. The update reflects more reasonable occam expressions.