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

[ext_44906]

I have yet to digest this fully and I'm going on holiday for 2 weeks very soon. I very much look forward to munching on the more delicate textures and flavours.

I'm sure this has some bearing on the way Curly Logo is evaluated and can definitely improve the way I think about it.

In Haskell, like Fix, literal numbers don't denote numbers they denote some sort of function. As far as I can tell. I guess it's some sort of lazy number.

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

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,