Implementing ML like language

Simon Peyton Jones's book The Implementation of Functional Programming Languages is worth reading, it discusses implementing an ML-like programming language, compiling it to lambda calculus, then discusses optimizations. CAML Light realizes aspects of the book, compiling to the Categorical Abstract Machine (CAM). It might be worth while to look at this in greater detail.

Algebraic Data Types

• What is the preferable memory layout of Algebraic Data Types? SO thread
• Memory footprint of Haskell data types

How it seems to work under the hood is:

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)

Loosely speaking, this is "the same" as the following code:

typedef struct tree tree;

enum {Tree_Empty, Tree_Leaf, Tree_Node} Tree_constructor;

typedef struct {} Empty;
typedef struct { int leaf; } Leaf;
typedef struct { tree *t1; tree *t2; } Node;

struct Tree {
    enum Tree_constructor constructor;
    union {
        Empty *empty;
        Leaf *leaf;
        Node *node;
    }
};

int depth(struct Tree *tree) {
    switch(tree->constructor) {
        case Tree_Empty: return 0;
        case Tree_Leaf:  return 1;
        case Tree_Node:  return 1 + max(depth(tree->t1), depth(tree->t2));
    }
}

Or something like that. Also see:

• Diehl's Write you a Haskell, part 10: Custom Datatypes