Drinkable Chicken

So a few days ago I was wondering if simple stack functions could be implemented concisely in a statically typed language like OCaml… similar to the way it can be done in Scheme and Python, as discussed here. This prompted an interesting comment by Juri Pakaste.

However, one thing that does come to mind is that there’s a limited number of stack effects you need to support – maybe create higher order functions like one_two (for dup), two_two (for swap), etc, that would take a function as a parameter and return a function that takes in the env and ns parameters, pop the correct number of items, give them as args to the function received as a parameter, then push the return values?

So, using this idea, I wrote another proof-of-concept “interpreter” in OCaml. I’ve deliberately kept it as simple as possible; the stack only takes integers, and there’s only a few words, and no real parser; rather, you pass a list of words (as strings) to the process_words function. 

(Again, my OCaml is clunky, but then again I haven’t read ML for the Working Programmer yet.)

First of all, let’s define a simple stack:

type stack = { mutable items: int list };;

let push stk x =
    stk.items <- x :: stk.items;;

let pop stk =
    match stk.items with
      [] -> failwith "stack is empty"
    | hd::tl ->
      stk.items <- tl;
      hd;;

let stack_repr stk =
    let contents = List.map string_of_int (List.rev stk.items) in
    let s = String.concat " " contents in
    "[" ^ s ^ "]";;

let make_stack () =
    { items=[] };;

Next, let’s write a few common “stack transformers”.

let one_two f =
    let g stk =
        let n1 = pop stk in
        let (r1, r2) = f n1 in
        push stk r1; push stk r2
    in g;;

let two_one f =
    let g stk =
        let n2 = pop stk in
        let n1 = pop stk in
        let r1 = f n1 n2 in
        push stk r1
    in g;;

let two_two f =
    let g stk =
        let n2 = pop stk in
        let n1 = pop stk in
        let (r1, r2) = f n1 n2 in
        push stk r1; push stk r2
    in g;;

let one_zero f =
    let g stk =
        let n1 = pop stk in
        let _ = f n1 in
        ()
    in g;;  

The idea is to take functions with different signatures; e.g. one_two wants a function that takes one argument and returns a tuple of two items, two_one takes two arguments and returns one, etc. They are then “transformed” to (or rather, encapsulated in) functions that take one argument (a stack) and apply the wrapped function to it, popping and pushing the right number of items.

Using these transformers, we can now define our built-in words.

let words = [
    ("dup", one_two (fun x -> (x, x)));
    ("swap", two_two (fun a b -> (b, a)));
    ("drop", one_zero (fun x -> ()));
    ("+", two_one (fun x y -> x + y));
    ("-", two_one (fun x y -> x - y))
];;

It looks a bit odd, but the actual functions have different signatures, and OCaml won’t let us store them in the same list, unless we wrap them. (Python’s decorators come to mind…)

Next up is the “meat” of the interpreter… processing words, determining whether they are numbers, looking them up in our list of builtins.

let lookup_word word =
    let rec lookup_word_aux words_left =
        match words_left with
          [] -> failwith ("unknown word: " ^ word)
        | (name, f) :: tl ->
          if name = word
          then f
          else lookup_word_aux tl
    in
    lookup_word_aux words;;

let is_integer word =
    try
        let _ = int_of_string word in
        true
    with Failure e ->
        false;;

let process word stk =
    if is_integer word
    then push stk (int_of_string word)
    else
      let f = lookup_word word in
      let _ = f stk in
      ();;

let process_words words stk =
    let g word =
        print_string ("> " ^ word ^ "\n");
        process word stk;
        print_string ("stack: " ^ (stack_repr stk) ^ "\n")
    in
    List.iter g words;;

Test test…

process_words ["1"; "2"; "3"; "+"; "dup"; "drop"; "swap"; "-"]
    (make_stack ());;

…produces:

> 1
stack: [1]
> 2
stack: [1 2]
> 3
stack: [1 2 3]
> +
stack: [1 5]
> dup
stack: [1 5 5]
> drop
stack: [1 5]
> swap
stack: [5 1]
> -
stack: [4]

Fun! Now, let’s try this in Java… ;-)