Fix

[chard]

I recently had occasion to write a Forth interpreter in Linden Scripting Language (in Second Life). I've done it before (more than twice) and it only took me an hour or two. I've written the odd Scheme interpreter (and compiler) too. Forth and Scheme are both elegant little things, and I've always wanted to think of a way of combining them, but

Comments

Update

[chard]

So I have a practical compiler and VM running in Linden Scripting Language. It's pretty small and fast, and has just six core words:

; defines a word, binding a string to an entry address
{ start a block
} end a block, leaving the entry point on the stack
! call the entry point on the stack
recursive fixed point operator
if select and calls one of two entry points depending on a third value

In addition, any call just before a "}" is converted to a jump, so tail recursion works. Here's a recursive factorial program.

"fact" {
over 0 =
{ drop drop 1 }
{ over 1 - swap ! * }
if
} recursive ;

The "recursive" word is the witty thing here. It compiles a little bit of code which pops an address from the stack, then pushes its own address and jumps to that address. So when "fact" is bound above, it's actually bound to one of those chunks, which then jumps to the main body. When the body does a "!" it's actually calling itself, recursive, or "Y f" if you prefer.

Here's an iterative version which doesn't consume O(n) stack levels.

"fact-loop" {
over 0 =
{ drop drop }
{
rot 2 pick *
rot 1 -
rot !
}
if
} recursive ;

"ifact" {
1 swap fact-loop
} ;

Re: Update

[chard]

Incidentally, I'm toying with a CPS version of the language. The current version has two stacks: the operand stack (with the data on it) and an operator stack (with return addresses). This actually causes a problem with the VM being re-entrant when it calls other language code, and it prevents me doing nice things with coroutines. I think it can work quite well with just one stack.

Just two changes are needed.

1. When an address is called, the VM will push the return address onto the operand stack (the only stack in this case).
2. When the end of a block is reached, pop and jump to the address at the top of the operand stack.

These are trivial changes. What they mean is that the entire state of computation is now on the operand stack. The recursive factorial program now looks like this:

"fact" {
2 pick 0 =
{ drop swap drop 1 swap }
{ 2 pick 1 - swap ! rot * swap }
if
} recursive ;

At the start of the first line, "2 pick 0 =", there are three things on the stack: the recursion address, then the return address, then the number. "2 pick" gets a copy of the number to check if it's zero. In the zero case, we drop the recursion, replace the number with 1, and then jump to the return address. In the non-zero case, we copy the number, decrement it, call the recursion (which jumps back here later), multiply by the number we first thought of, then jump to the return address.

Simple!