next up previous contents
Next: 4 Ignore this Up: QScheme Documentation Previous: 2 Introduction   Contents

Subsections

3 How it works

This section gives some technical informations about QScheme.

3.1 The Read/Eval/Print Loop

A classical Scheme interpreter works in a loop, the famous REPL, which stands for ``Read, Eval, Print Loop''. My Scheme largely conforms to this. In order to achieve speed and flexibility, the REPL has been slightly changed.


Table 1: The Read/Eval/Print Loop
\begin{table}{\par\centering\includegraphics{repl.eps}\par }
\par\end{table}


The simple eval procedure has been split in 4 parts, namely compile optimize assemble execute.

The compile phase transforms the list given by the read procedure into an intermediate code (icode) representation. This code is stored in a standard array and can be manipulated with the standard Scheme procedures.The icode is describe hereafter.

The optimizer transforms the icode generated by the compiler, mainly to implement tail recursion.

The assembler transforms the icode to a code which can be executed by the virtual machine. The vmcode is an internal code. It cannot be changed from the Scheme interpreter. It only can be printed for debugging purpose, see the disasm function.

With this design, the compiler and the optimizer can be written in Scheme itself.

3.1.1 The compiler

The compiler takes a list as input and generates an icode array. The input list is typically delivered by the read function.

When the compiler encounters a symbol which is bound to a macro, the macro code is evaluated and the result of this evaluation replaces the original form.

After compilation, the icode array contains assembly instructions. See table 2.


Table 2: Assembly instructions
Instruction Argument Description
nop - no operation
end - terminate
dolet - start of a let
dolet* nvars start of a let*
end-letjump - tail optimization
endlet-return - tail optimization
drop - forget top of stack value
pushq lit push lit
pushv sym push value of symbol
pushl var# depth push local variable
store - store to symbol
store-evar evar store to extern variable
setl varnum depth set local variable
getvar - get value of a variable
setvar - set value of a variable
mark - push a partial continuation
mkclosure - pack a closure
mkproc varlist #args #local optarg? code create a procedure
mkcode - unused yet
endlet - terminate let clause
return - terminate procedure
callp prim call primitive
callc cfunc call c function
call - general call
jump - general jump
br-and #label branch for and
br-or #label branch for or
bra #label branch always
brf #label branch if false
brt #label branch if true
catch #label catch
uncatch - uncatch
label #label generate lab for branching


3.1.2 The optimizer

The optimizer transforms the icode. The main optimizations are:

The optimization process is not really very optimized. It just iterates through the icode until no further optimization can be done.

3.1.3 The assembler

The assembler transforms the intermediate code to real virtual machine code. During this transformation, the ``nop'' icodes generated during optimization are ignored and the labels are mapped to actual addresses.

3.2 Where in the source ?

The compiler/assembler is implemented in the asm.c source file. There you can find the complete list of opcodes.

The execute and read functions are located in the s.c file. I'm not totally happy with this and may move these functions elsewhere.


next up previous contents
Next: 4 Ignore this Up: QScheme Documentation Previous: 2 Introduction   Contents
Daniel Crettol 2000-06-12