ImperialViolet

After a brief holiday, The Memory Hole is ticking again.

• "58% disagree with the statement that the government can be trusted to keep their personal data secure"
• EETimes: Engineer writes open-source register generation tool
• Zoë, an email interwingle client. (from the Ted Nelson/JWZ school of thought)
• Online Prolog tutorial
• IndyMedia's new publishing system
• Fragments of Foundations of Cryptography [thanks to TBL]

People keep talking about it and it's high time that I looked into it. O'Caml is an ML based language and has all the standard ML language stuff (curried functions etc). It uses inferred typing, which is very useful, despite the few drawbacks (more on that later).

It also has polymorphic typing:

# let f = function (a, b) -> a;;
val f : 'a * 'b -> 'a = <fun>

That function takes a 2-tuple of any type and returns the first element and polymorphically works within the type-system.

There is a translation of a French O'Reilly O'Caml book online, but I find it's a little heavy for a introductionary text. I find that this book it nicer to start with. Maybe move on the O'Reilly book afterwards.

This code snippet, which implements red-black binary tree insertion, should demonstrate the power of O'Caml even if you don't understand it. (This assumes you've seen what a mess a red-black insert looks like in C/C++. If not, see this, and I have reasonable reason to suspect there's an error in there since it was done partly from CLR).

let balance = function
  Black, Node (Red, Node (Red, a, x, b), y, c), z, d ->
    Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
  | Black, Node (Red, a, x, Node (Red, b, y, c)), z, d ->
    Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
  | Black, a, x, Node (Red, Node (Red, b, y, c), z, d) ->
    Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
  | Black, a, x, Node (Red, b, y, Node (Red, c, z, d)) ->
    Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
  | a, b, c, d ->
    Node (a, b, c, d)
    
let insert x s =
  let rec ins = function
    Leaf -> Node (Red, Leaf, x, Leaf)
  | Node (color, a, y, b) as s ->
      if x < y then balance (color, ins a, y, b)
      else if x > y then balance (color, a, y, ins b)
      else s
  in
    match ins s with    (* guaranteed to be non-empty *)
      Node (_, a, y, b) -> Node (Black, a, y, b)
    | Leaf -> raise (Invalid_argument "insert");;

However, there are a couple of silly bits on O'Caml. Firstly, the bitwise (not, logical) AND function is called land. Secondly, the namespace for record fields is flat within a module, so you can't have 2 record/struct types with the same named field in a single module. I'm pretty sure that there isn't a deep reason for that (the shallow reason has to do with type inference).

From one of Coderman's friends....

(Sung to the tune of Y.M.C.A by the Village People)

Net geeks
  There's no need to feel guilt
I said, net geeks
  For the software you built
I said, net geeks
  'Cause you're not in the wrong
There's no need to feel unhappy!

Net geeks
  You can burn a CD
I said, net geeks
  With your fave mp3s
You can play them
  In your home or your car
Many ways to take them real far!

It's fun to violate
  the D M C A !
It's fun to violate
  the D M C A-AY !
You have everything
  You need to enjoy
Your music with your toys!

It's fun to violate
  the D M C A !
It's fun to violate
  the D M C A-AY !

You can archive your tunes
  You can share over cable
You can annoy the
  Record Labels!