What I\’m playing with at home

This is an email I sent out to a few friends, talking about what we\’re doing with our time, and I realized that it\’s exactly the sort of thing I should be posting.

There are a number of models of computation, the most famous being the Turing machine and the λ-calculus (which are equivalent, but λ-calculus is prettier). They\’re both pretty old, dating from the 40s and 50s respectively. Of course, they\’ve pretty well stood the test of time. Two of the more modern ones that have held my interest are the ρ-calculus and the π-calculus. Both of these encode the λ-calculus very easily (meaning anything you can do with λ-calculus you can do with them).

The ρ-calculus adds the idea of patterns, like that found in ML, Haskell, and Erlang. It allows for a more natural expression of a lot of ideas than a traditional language would offer. For example, you might write an average function like this in the λ-calculus:

     (defun average (list &optional (count 0) (sum 0))
       (if (null list)
           (/ sum count)
           (average (cdr list) (1+ count) (+ (car list) sum))))

whereas, it would look like this in Haskell:

     average [x:xs] count sum = average xs (count + 1) (sum + x)
     average []     count sum = sum / count

Rather than using an if structure, the left side of the equal sign shows different patterns to match. The first pattern matches if you
call the function \”average\” with a list containing at least one element and works its way through the list. (\”x\” is the first element of the list \”[x:xs]\”. That notation means \”take a list, store the first element in \’x\’ and put the rest of it in \’xs\’.\” \”x\” and \”xs\” being conventional Haskell shorthand for parts of a list.) If you call it with an empty list it calculates the average from the values that have been collected. Now, just because we\’ve got pattern matching doesn\’t mean we have to give up parens. You could implement a DEFPFUN that works like this:

     (defpfun average
       (((h . t) count sum) (average t (1+ count) (+ h sum)))
       ((() count sum) (/ sum count)))

and maybe even add some strict typing

    (defpfun average (list integer number number)
      (((h . t) count sum) (average t (1+ count) (+ h sum)))
      ((() count sum) (/ sum count)))

Hrmm, yeah, maybe I\’ll try to implement that (looks like Fare beat me to it). So, that\’s ρ-calculus.

The π-calculus is all about concurrency. Threads are nasty and slow, however, given the approach used in many current systems, we don\’t have much flexibility. There are a number of models of concurrency that replace the state-sharing of threads with message-passing. This is much safer, as multiple processes can\’t step on each other\’s toes. Two of the really cool ideas that make the π-calculus stand out are

  1. sending processes as values, which can then continue running from
    some other location and
  2. representing data structures as processes.

I\’m still just really getting into this one, but the theory has been developed by Robin Milner who also developed the idea of type inference (letting the compiler figure out the types, so you don\’t have to type them everywhere like you do in C++). His writing is lucid and makes the theory seem so simple.

Anyway, it\’s past my bedtime now. I\’ll ramble on some more later. To wrap up, I\’m thinking of how I can combine these two models to come up with what I guess is a somewhat cleaner version of Erlang with the metaprogramming abilities of Lisp.

Comments are closed.