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.

In a file called lib.c:

int addTwo(int x, int y) {
  return x + y;
}

Compiled on the Powerbook with:
gcc -dynamiclib -o lib.dylib lib.c

Then, in DrScheme v299:

(require (lib "foreign.ss"))
(define addTwo
  (get-ffi-obj
   "addTwo" "lib"
   (_fun _int _int -> _int)))

And, in the interactions window, I can now use:

> (addTwo 2 2)
4

That is so very sweet. Dynamic FFI. Thank you, Eli.

PS. The cool bit is the definition of ‘addTwo’ in Scheme; it’s a function name, a library name, and a type contract. How sweet is that?!? This makes it so much easier to solve a problem I’ve been having with native number types from PLT Scheme. So much goodness, it hurts.

This week was (is) busy. I had at least one seminar to attend every day, teaching Monday evening, a draft of an ITiCSE paper for Tuesday (due for submission this Monday), gave talk Thursday (with CSCS in the evening), and a trip to Wales today. I’ll return Monday, ship the paper, and teach from 6PM to 9PM.

I’m hoping that the submission of the ITiCSE paper will free up a bit of time in my schedule…

I have to admit, I’m getting kinda tired of syntax errors. I mean, analyzing real data generated by real students who are really learning to program is cool and all, but… geez. You can get sick of syntax errors.

I have never understood people who get two PhDs.

One of the CSCS guys dropped this link my way via IM:

To the Citizens of the United States of America

A brief taste:

Humour works best when there is a grain of truth to it. There are many grains here, and the author of this post (or whoever posted it after copying it from somewhere else on the web) has pounded on a number of these little truths. The most evident truth, however, is that The World sat up and paid attention to this election, and The World did not want to see Bush re-elected.

While wandering the streets of Prague this weekend, I saw a number of these signs all over the city. Prague is a very long way from Washinton, D.C., but the people there have opinions, and strong ones. During dinner Saturday night, one of the waiters (after discovering that I was from the States, and even more importantly, from Ohio!) continuously came by our table to express how he felt about the state of the world, and in particular why he felt that Bush had no right to lead America the way he has.

Not a politician, not a diplomat, not even another American–just a Czech trying to make his way through the world as a waiter in Prague who had no love for Bush and the Bush Administration’s policies, but at the same time could distinguish between that Administration and the people of the United States. Granted, I don’t know what would have happened if I was pro-Bush, but we’ll leave that to your imagination.

The World noticed. It’s too bad that most of the time we don’t notice the World.

It looks like ICAAN, the regulating body for domain names and whatnot on the internet, just made an evil policy change; hopefully, Netcraft is reporting this incorrectly–but most likely, they’re on top of things.

Update: I reacted to an internet scare; there was a policy change, but it wasn’t as evil as was originally thought. However, locking your domains is still a good idea.

Another CSCS weblog has come online; this one belongs to Jon Simpson, a first-year in the CS department. He’s also taking a poke at getting the Zaurus working with the Brainstem–meaning, he’s getting our handheld computer of choice talking to the motor and sensor controller that we’ll be using on our larger atomic death robots!

Unfortunately, we slowed Jon down for a while because a critical cable had gone wandering; fortunately, the cable has been found, everything is now organized in our office, and he’s free to run as far and as fast as possible.

Welcome, Jon!

The American people have spoken.

There is no rational explanation for why Bush should have been re-elected. His administration has tanked the economy, demolished America’s image on the global stage, started a war–unprovoked–without international support, and with no clear plan for the aftermath.

“It made America safer.” If I hear this again, I’ll be sick. We invaded a sovereign nation, and murdered 100,000 people, most of whom are innocent casualties of war. When the people of Iraq seek their own retribution for acts of terror, where will the violence take place? On Americans abroad? Or will the attacks take place on our native soil.

And who will the voting public blame? I’m sure they’ll find someone, when the time comes.

But today, I blame the voting public.

Upcoming jingle from the B&M Music Movement Machine.

Tomorrow is election day in the USA.

I was looking at the current electoral vote predictions, and I’m worried. I look at all those States in the middle, and I can’t help but think of the “Ugly American” tourists and short-stay students I’ve met since I’ve been here. People who rarely get out of their own county, let alone State or country. People “proud to be American” without even knowing what that means in the world today.

I went looking for passport ownership figures, and found Phil Gyford’s own efforts in this area; I’ll take his 20% as a reasonable number; one in five. While reading through the comments on his post, one comment in particular made me think of those vast expanses of land in the Midwest:

Perhaps your Typical American thinks traveling from one country to another in Europe is like going from Illinois to Iowa. If so, the Typical American is seriously confused, and needs to start getting their news from a source that isn’t owned by Rupert Murdoch. Perhaps this is why your Typical European can’t understand how so many Americans can have their heads lodged firmly up their asses when it comes to international politics and current affairs in the world today.

George W. Bush and his regime started a war with a sovereign nation on false pretenses, using the US media machine to their own ends to great effect. We have killed almost thirty Iraqi innocents for every one lost in September 11th–people who had no more to do with Bin Laden and Al-Qaeda than you or me. Who will avenge their deaths–who will be held accountable for these atrocities? No doubt, we’ll learn the answer to that question soon enough, and very possibly on US soil. Again. It’s called “cause-and-effect.”

It is not that the people of the world “don’t understand what the US is about”–indeed, they understand all too well.

Go vote.