QuakeScheme is yet another implementation of the algorithmic (programming) language Scheme. I decided to write a new implementation, instead of re-using other free implementations, to address the idiosyncrasies of modding for Quake 3:
  1. No malloc().
  2. Q3VM is based on a stack-only register-less machine.
  3. 1MB of machine stack available.

1. No malloc()

This means no heap-dynamic memory. In short, all memory to be used has to be declared compile-time. Although I could have written my own malloc() implementation, this would have presented two problems: debugging this malloc implementation, does not solve #2.

2. Q3VM architecture

The Quake 3 Virtual Machine is based on the bytecode machine described by lcc, the free retargetable C compiler. This bytecode machine is based entirely on a stack, with no use of registers. The end result is that bytecode forms of Quake 3 mods (.qvm files) can run on any platforms for which Q3 is available, albeit slower (as much as 25% slower compared to native code).

This very architecture prevented me from using many of the free Scheme implementations. Most of the free Schemes expect the kind of system epitomized by Sun Microsystem's Sparc machines: flat memory space, 32 or 64-bit address space, 32 or 64-bit word size, a variety of registers, virtual memory space, Unix-like Operative System. Some of the free Schemes used system-specific information and/or Unix-specific system calls (e.g. setjmp/longjmp) to implement call-with-current-continuation, and sometimes garbage collection by deducing pointer values based on bit patterns. Although these bits could conceivably be removed selectively, such removals would cripple functionality.

Q3VM bytecode form, however, does have its advantages. Cross-platform functionality (compile-once run-anywhere) and more restricted access to the host system are among them. Still, these very design issues prevented me from merely plopping in a free Scheme.

3. 1MB machine stack

The most frequent use of stack is to construct and execute a subroutine (function) call. A certain amount of space is take from the stack to store the pre-call state, then some more to accomodate local variables in a subroutine. Each subcall takes up more stack space. I have no idea how much stack space each call of a Q3VM subroutine takes, but I would peg the size at anywhere from 30 bytes to 100 bytes per call, then varying more for local variables. At this size, there would space for most of the common recursive C functions. Most Scheme functions, however, implement recursion for looping. Without true tail-recursion, 1MB would fill up in less than 100K calls.

Most of the free Scheme implementations assume a sane host system as outlined above (wrt Sparcs), i.e. they don't expect a hard limit of 1MB for stack, and expect virtual memory to compensate for excessive stack use.