Drinkable Chicken

If I finish my Scheme interpreter (written in Python), and it comes out halfway decent, it would technically be possible to use Google App Engine with Scheme…

*ponders*

For what it’s worth, I’ve been tinkering a bit with Google App Engine. So far I like it… I especially appreciate that I can focus on writing Python code, rather than having to work around a traditional database’s rigidity. (You know… creating a database schema, and a model in an ORM to mimick it, then keeping them in sync, all the while pretending that you’re storing and retrieving objects rather than rows in tables.)

Of course, for all I know GAE does exactly that behind the scenes, but it *feels* different. So far, I find it much more pleasant to work with than “regular” web application frameworks. Maybe this statement reveals my inexperience with web programming, but still, that’s what it feels like right now. :-)

World of Goo is an “indie” game, available for Windows, Mac, and Wii, that has had some good reviews. So I figured I’d download the demo for Mac OS X and see what all the fuss is about.

At first, it seems simple enough. You build a contraption using balls of “goo” in order to reach a sort of faucet (which functions as the level exit). In the first screen(s), this is laughably easy, and you might wonder what the big deal is. But naturally, higher levels crank up the difficulty; for example, you have a cross a chasm without hitting the spikes at the bottom, or build a huge tower without it collapsing. To spice things up, new types of goo are introduced regularly; some function as balloons, while others are reusable, etc.

In spite of, or maybe because of, its simple premise, this game is strangely addicting. I found myself going back several times this evening… maybe because it’s so easy to just fire it up and start building. And if you fail, experimenting comes naturally (“what happens if I build it this way instead?”).

Probably the most entertaining game I’ve played on a PC/Mac in a *long* time. (It reminds me a bit of Gish, which plays very differently, though.)

Another year went by. Much has happened. Here’s an overview.

Personal

• Not off to a good start: In January my wife was diagnosed with lung cancer. Over the course of the year she had chemo treatment and, more recently, radiation.

Professional

Technical

• I didn’t use Chicken Scheme quite as much as I hoped (life interfered, after all), but I did learn a lot about the language, and wrote a project or two using Chicken. I also wrote a Scheme interpreter or two in Python, to get a better idea of what makes the language tick.

• Although I’m old enough to know better, I did get two more iBook clamshells, even though they don’t run Leopard. ^_^’  But they’re so kawaii…

• In an attempt to stay connected, I got myself a Helio Ocean, just to find that it doesn’t get much service around here. Suck.

• Blogging-wise, it wasn’t a remarkable year, although a few of my posts did garner some attention… like this one. :-)

Recreational

• We had a few remarkable outings this year, like Disney, Silver Springs, New Smyrna Beach, and a psychic fair.

• I got to play a lot of good and interesting games this year: Patapon (PSP), Phoenix Wright 3 (DS), Yggdra Union (GBA), Professor Layton (DS), Okami (Wii), The Lurking Horror (Z-machine — I didn’t say these were *new* games :-), Touch Detective 2½ (DS), Civilization (DS), Odin Sphere (PS2), La Pucelle Tactics (PS2), Spore Creatures (DS)

• It was the second time I got to watch a European Championship while in the US… the Netherlands initially did well, then choked on Guus Hiddink’s Russia. >_<

All in all, this year saw some serious ups and downs… some of the downs are not mentioned, as there’s no point in dwelling on them. In spite of the negative events, there was significant progress in some areas as well.

Onwards…

Almost four years ago I took a look at Subtext, an unusual programming “language”. Today I stumbled upon it again. Development has continued, and while I don’t see this appearing on worker bee’s desktops anytime soon, it’s definitely worth another look.

As you can tell from the updated video, programming is done by creating and manipulating “schematic tables”… sort of a crossover between a flowchart and a spreadsheet. (Do watch that video… it’s hard to explain the essence of Subtext in just a few words. You have to *see* it.)

It moves away from the assumption that “a program == text”. Or, as the author puts it, “Much of the design of our programming language is an artifact of the linear nature of text.”

While the new approach is interesting and makes for a whole new way of writing programs, I’m not sure how well it would hold up when dealing with more complex programming problems. (The examples mentioned in the video are fairly simple… fibonacci and an algorithm to calculate damage in an RPG-like game.) Also, it seems to rely heavily on the mouse, while the general trend in programming editors and IDEs seems to be, to use the keyboard as much as possible.

Subtext is capable of doing some pretty nifty things… like pointing out gaps or contradictions in your logic. (Again, see the video.)

I’m also curious how easy it is to define custom abstractions with Subtext, as is common in more expressive programming languages.

I haven’t made up my mind yet if this way of programming is easier or harder than the “conventional” way… The difference in layout (a table with different columns rather than a class hierarchy, for instance) makes some things easier to see and grasp. But again, I don’t know how well this scales to more complex algorithms. In any case, it’s different.

Now, when will this be available for download? I want to play with it. :-)

Where in the world do I find this Rockers from London album?!

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… ;-)

So, this language with the working title llizard… I’m going to change its name to Manta.

I’ve been tinkering with various incarnations of this language/idea for a *long* time. I believe the oldest versions were called Manta. This was back in, say, 1992, when I was still using Turbo Pascal. :-)

Anyway, the OCaml sources are now available. Get them here: [manta-20081222.tar.gz].

Big fat disclaimers apply. This code is not so recent (written in 2006), and it was my first non-trivial project in OCaml, so I’m sure I’m doing a lot of clumsy things… like writing my own version of functions and data structures that are probably available in some library, among other things. It matters not. This is only an experimental version, and I am making the code available for masochistic adventurous souls.

There’s currently no documentation included. Build it using the build script (Unixoid systems only). Obviously you’ll need a recent version of OCaml (3.x), and Python if you want to run build.py (which generates a makefile of some sort). More info will be available when I get around to giving this thing a separate project page. :-/

A newer version, if any, will probably be written in Python 3.0 or Clojure or something. I have no concrete plans right now, but this project has a tendency to resurface every few years or so.

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. :-)

After yesterday’s post, I figured I might as well explain how stack-based languages work. After all, they’re not that common, so maybe some clarification would be in order.

As the name indicates, a stack-based (or “concatenative”) language relies heavily on a stack. Functions are not called with parameters; rather, they may take a number of items off the stack, do something with them, maybe push a result back onto the stack, etc.

To illustrate this, let’s write a tiny interpreter for a stack-based language. I’ll use Python, but it should be trivial to translate to other higher-level languages.

First, let’s describe the language. A program consists of a number of words separated by whitespace. Words can be numbers, actual words, operators, pretty much anything…  For now, we’ll stick to integers and a small number of built-in words.

The interpreter starts with an empty stack. When it encounters a number, it will push that number onto the stack. For example, “1 2 3″ is a valid program, that pushes the numbers 1, 2 and 3, in that order, on the stack. At this point, the topmost element of the stack is 3. This is important, because words take elements from the top.

Our language will then support the following words:

• +, which takes the two topmost elements off the stack, adds them, and pushes the result back.
• dup, which duplicates the topmost element.
• drop, which takes the topmost element off (and does not do anything with it).
• swap, which takes the two topmost elements off the stack, and pushes them back in reverse order. Or, in other words, it swaps the two topmost elements.
• print, which takes the topmost element and displays it.

(“Real” stack-based languages have many, many more words, but this small subset is enough for our purposes.)

Now, let’s write the interpreter. First, we define a Stack class.

class Stack:
    def __init__(self):
        self.data = []
    def push(self, x):
        self.data.append(x)
    def pop(self):
        return self.data.pop()

All we really need right now is two methods: push(x) to push an item onto the stack, and pop() to take an item off.

Now let’s define a rudimentary interpreter. The process() method takes a word and tries to do something with it… if it’s a number, it will push it, if it’s a built-in word, it will execute it, otherwise it’s an error.

class Interpreter:

    def __init__(self):
        self.stack = Stack()

    def process(self, word):
        if is_int(word):
            n = int(word)
            self.stack.push(n)
        else:
            try:
                f = words[word]
            except KeyError:
                raise SyntaxError, "Unknown word: %s" % word

            # determine number of arguments
            n = num_args(f)

            # pop that number of args from stack
            args = reversed([self.stack.pop() for i in range(n)])

            # call f with that list
            result = f(*args)

            # take return value (a list)
            # push elements on stack
            for x in result or []:
                self.stack.push(x)

    def process_line(self, line):
        words = line.split()
        for word in words:
            self.process(word)

Now let’s define a few built-in words. The idea is that we can define these words as Python functions. The number of arguments these functions take, is the number of items that will be taken from the stack. They should return a list containing the items that should be pushed, or None, in which case nothing will be pushed.

def _print(x):
    print x

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

(Lambdas are especially useful here to add simple functions as one-liners, but of course we can use named functions as well.)

Now all we need is a few helper functions, and we’re good to go:

def num_args(f):
    """ Return the number of arguments that function <f> takes. """
    return f.func_code.co_argcount

def is_int(s):
    try:
        int(s)
    except ValueError:
        return False
    else:
        return True

(These are clumsy and incomplete; for example, num_args doesn’t work correctly for methods; but for now they will do.)

Throw all the code above in a file, and add this __main__ block:

if __name__ == "__main__":

    e = Interpreter()

    while 1:
        line = raw_input("> ")
        e.process_line(line)
        print "stack:", e.stack.data

…and run that file through Python.  You should now have a very small but working interpreter. Let’s test it.

> 1
stack: [1]

Aha! This pushes the number 1 on the stack. Let’s try a few more numbers…

> 2 3
stack: [1, 2, 3]

We now have three numbers on the stack. Remember that 3 is the topmost one… so in this representation, the right represents the top of the stack.

> dup
stack: [1, 2, 3, 3]

dup duplicates the topmost element… so now we have an extra 3.

> +
stack: [1, 2, 6]

+ takes the two top elements, add them, and pushes the result back. So it takes 3 and 3, adds them, and pushes 6 back, which is what we see. The other items on the stack (1 and 2) are unaffected by this.

What if we want to add, say, 1 and 6, and we aren’t interested in the 2? Use some of the other words:

> swap
stack: [1, 6, 2]
> drop
stack: [1, 6]
> +
stack: [7]
> print
7
stack: []

Well. This is basically how a stack-based language works. Of course, languages like Forth, Joy and Factor have much more than this small subset; they have pretty much everything that mainstream languages have, and possibly more. Even my small llizard interpreter has more: you get to define functions, variables, macros, use strings and lists, manipulate the stack in other ways, etc. The nice thing is that in the end, almost everything is just a word.

In the next posts I will talk about the way these built-in words are defined here, and probably release the OCaml code for my latest toy interpreter.