Drinkable Chicken

This post is a followup on:

• llizard teaser
• A tiny interpreter for a stack-based language

Let’s take another look at the way the built-in words were defined, in the interpreter. This may look straightforward, but I used to do this differently, even in Python.

In the OCaml code (which will be made available soon), all built-in words are functions with the same signature. They all take two parameters, an environment (basically an object that holds the stack and other interpreter state) and a namespace. These functions then use the environment to pop elements off the stack, etc., resulting in code that looks like this:

(* dup  ( x -- x x ) *)
let dup env ns =
  let obj = Env.top env in
  Env.push env obj;;

(* swap  ( a b -- b a ) *)
let swap env ns =
  let a, b = Env.pop2 env in
  Env.push env a;
  Env.push env b;;

(* -  ( n1 n2 -- n3 )
*)
let minus env ns =
  let top_stack = Env.top_stack env in
  let x1 = Stack.pop top_stack in
  let x2 = Stack.pop top_stack in
  match x1.obj, x2.obj with
    LzInt i1, LzInt i2 ->
      let result = i2 - i1 in
      let newobj = Env.create_object env (LzInt result) in
      Stack.push top_stack newobj
  | _ -> raise Invalid_arguments "-: requires two integers"
;;

(Note: This was my first non-trivial project in OCaml, written about two years ago… I’m sure the code can be improved, but bear with me.)

For a long time I thought this was a fairly straightforward way to do it… until I saw the source code of this Joy interpreter (by John Cowan). Written in Scheme, it puts macros to good use in order to make word definitions simpler and clearer. The words mentioned above can be defined like this:

(joy-prim-list (dup x) (list x x))
(joy-prim-list (swap x y) (list y x))
(joy-prim (- i j) (- i j))

Definitions like (dup x) and (swap x y) tell us how many items are popped off the stack, *and* they get named automatically, to be used in the following expression.

Python doesn’t have macros, but it has other ways to do something similar. The tiny interpreter I wrote about yesterday uses a form of introspection to determine the number of arguments a function has. Using this, we can then write built-in words like this:

words = {
    '+': lambda x, y: [x+y],
    'dup': lambda x: [x, x],
    'drop': lambda x: [],
    'swap': lambda x, y: [y, x],
    'print': _print,
}

In other words, the function associated with +, takes two items off the stack, adds them, and puts them back. The function associated with dup takes one item, pushes back two, etc. This allows for definitions that are much more concise and straightforward… at least in these cases.

I wonder if the same can be done in statically typed languages like OCaml (or Haskell)? I don’t see an obvious way to do it, but I’d love to be enlightened. :-)