Another tiny interpreter for a stack-based language… this time in OCaml
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… ;-)