This file documents Guile VM.

Copyright © 2000 Keisuke Nishida Copyright © 2005 Ludovic Court`es

Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies.

Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one.

Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by the Free Software Foundation.

Guile VM Specification
**********************

This document would like to correspond to Guile VM 0.6. However, be warned that important parts still correspond to version 0.0 and are not valid anymore.

What is Guile VM?
*****************

A Guile VM has a set of registers and its own stack memory.  Guile may have more than one VM's.  Each VM may execute at most one program at a time.  Guile VM is a CISC system so designed as to execute Scheme and other languages efficiently.

Registers
---------

  * pc - Program counter    ;; ip (instruction poiner) is better?

  * sp - Stack pointer

  * bp - Base pointer

  * ac - Accumulator

Engine
------

A VM may have one of three engines: reckless, regular, or debugging. Reckless engine is fastest but dangerous.  Regular engine is normally fail-safe and reasonably fast.  Debugging engine is safest and functional but very slow.

Memory
------

Stack is the only memory that each VM owns.  The other memory is shared memory that is shared among every VM and other part of Guile.

Program
-------

A VM program consists of a bytecode that is executed and an environment in which execution is done.  Each program is allocated in the shared memory and may be executed by any VM.  A program may call other programs within a VM.

Instruction
-----------

Guile VM has dozens of system instructions and (possibly) hundreds of functional instructions.  Some Scheme procedures such as cons and car are implemented as VM's builtin functions, which are very efficient. Other procedures defined outside of the VM are also considered as VM's functional features, since they do not change the state of VM. Procedures defined within the VM are called subprograms.

Most instructions deal with the accumulator (ac).  The VM stores all results from functions in ac, instead of pushing them into the stack. I'm not sure whether this is a good thing or not.

Variable Management
*******************

A program may have access to local variables, external variables, and top-level variables.

Local/external variables
========================

A stack is logically divided into several blocks during execution.  A "block" is such a unit that maintains local variables and dynamic chain. A "frame" is an upper level unit that maintains subprogram calls.

                  Stack
       dynamic |          |  |        |
         chain +==========+  -        =
             | |local vars|  |        |
             `-|block data|  | block  |
              /|frame data|  |        |
             | +----------+  -        |
             | |local vars|  |        | frame
             `-|block data|  |        |
              /+----------+  -        |
             | |local vars|  |        |
             `-|block data|  |        |
              /+==========+  -        =
             | |local vars|  |        |
             `-|block data|  |        |
              /|frame data|  |        |
             | +----------+  -        |
             | |          |  |        |

The first block of each frame may look like this:

            Address  Data
            -------  ----
            xxx0028  Local variable 2
            xxx0024  Local variable 1
       bp ->xxx0020  Local variable 0
            xxx001c  Local link       (block data)
            xxx0018  External link    (block data)
            xxx0014  Stack pointer    (block data)
            xxx0010  Return address   (frame data)
            xxx000c  Parent program   (frame data)

The base pointer (bp) always points to the lowest address of local variables of the recent block.  Local variables are referred as "bp[n]". The local link field has a pointer to the dynamic parent of the block. The parent's variables are referred as "bp[-1][n]", and grandparent's are "bp[-1][-1][n]".  Thus, any local variable is represented by its depth and offset from the current bp.

A variable may be "external", which is allocated in the shared memory. The external link field of a block has a pointer to such a variable set, which I call "fragment" (what should I call?).  A fragment has a set of variables and its own chain.

         local                    external
         chain|     |              chain
            | +-----+     .--------, |
            `-|block|--+->|external|-'
             /+-----+  |  `--------'\,
            `-|block|--'             |
             /+-----+     .--------, |
            `-|block|---->|external|-'
              +-----+     `--------'
              |     |

An external variable is referred as "bp[-2]->variables[n]" or "bp[-2]->link->...->variables[n]".  This is also represented by a pair of depth and offset.  At any point of execution, the value of bp determines the current local link and external link, and thus the current environment of a program.

Other data fields are described later.

Top-level variables
===================

Guile VM uses the same top-level variables as the regular Guile.  A program may have direct access to vcells.  Currently this is done by calling scm_intern0, but a program is possible to have any top-level environment defined by the current module.

Scheme and VM variable
======================

Let's think about the following Scheme code as an example:

       (define (foo a)
         (lambda (b) (list foo a b)))

In the lambda expression, "foo" is a top-level variable, "a" is an external variable, and "b" is a local variable.

When a VM executes foo, it allocates a block for "a".  Since "a" may be externally referred from the closure, the VM creates a fragment with a copy of "a" in it.  When the VM evaluates the lambda expression, it creates a subprogram (closure), associating the fragment with the subprogram as its external environment.  When the closure is executed, its environment will look like this:

           block          Top-level: foo
       +-------------+
       |local var: b |       fragment
       +-------------+     .-----------,
       |external link|---->|variable: a|
       +-------------+     `-----------'

The fragment remains as long as the closure exists.

Addressing mode
===============

Guile VM has five addressing modes:

  * Real address

  * Local position

  * External position

  * Top-level location

  * Constant object

Real address points to the address in the real program and is only used with the program counter (pc).

Local position and external position are represented as a pair of depth and offset from bp, as described above.  These are base relative addresses, and the real address may vary during execution.

Top-level location is represented as a Guile's vcell.  This location is determined at loading time, so the use of this address is efficient.

Constant object is not an address but gives an instruction an Scheme object directly.

[ We'll also need dynamic scope addressing to support Emacs Lisp? ]

At a Glance
-----------

Guile VM has a set of instructions for each instruction family.  `%load' is, for example, a family to load an object from memory and set the accumulator (ac).  There are four basic `%load' instructions:

       %loadl - Local addressing
       %loade - External addressing
       %loadt - Top-level addressing
       %loadi - Immediate addressing

A possible program code may look like this:

       %loadl (0 . 1)                ; ac = local[0][1]
       %loade (2 . 3)                ; ac = external[2][3]
       %loadt (foo . #<undefined>)   ; ac = #<undefined>
       %loadi "hello"                ; ac = "hello"

One instruction that uses real addressing is `%jump', which changes the value of the program counter:

       %jump  0x80234ab8             ; pc = 0x80234ab8

Program Execution
*****************

Overall procedure:

 1. A source program is compiled into a bytecode.

 2. A bytecode is given an environment and becomes a program.

 3. A VM starts execution, creating a frame for it.

 4. Whenever a program calls a subprogram, a new frame is created for it.

 5. When a program finishes execution, it returns a value, and the VM continues execution of the parent program.

 6. When all programs terminated, the VM returns the final value and stops.

Environment
===========

Local variable:

      (let ((a 1) (b 2) (c 3)) (+ a b c)) ->

        %pushi 1       ; a
        %pushi 2       ; b
        %pushi 3       ; c
        %bind  3       ; create local bindings
        %pushl (0 . 0) ; local variable a
        %pushl (0 . 1) ; local variable b
        %pushl (0 . 2) ; local variable c
        add    3       ; ac = a + b + c
        %unbind        ; remove local bindings

External variable:

      (define foo (let ((n 0)) (lambda () n)))

        %pushi 0                      ; n
        %bind  1                      ; create local bindings
        %export [0]                   ; make it an external variable
        %make-program #<bytecode xxx> ; create a program in this environment
        %unbind                       ; remove local bindings
        %savet (foo . #<undefined>)   ; save the program in foo

      (foo) ->

        %loadt (foo . #<program xxx>) ; program has an external link
        %call  0                      ; change the current external link
        %loade (0 . 0)                ; external variable n
        %return                       ; recover the external link

Top-level variable:

      foo ->

        %loadt (foo . #<program xxx>) ; top-level variable foo

Flow control
============

      (if #t 1 0) ->

           %loadi      #t
           %br-if-not  L1
           %loadi      1
           %jump       L2
       L1: %loadi      0
       L2:

Function call
=============

Builtin function:

      (1+ 2) ->

        %loadi 2  ; ac = 2
        1+        ; one argument

      (+ 1 2) ->

        %pushi 1  ; 1 -> stack
        %loadi 2  ; ac = 2
        add2      ; two argument

      (+ 1 2 3) ->

        %pushi 1  ; 1 -> stack
        %pushi 2  ; 2 -> stack
        %pushi 3  ; 3 -> stack
        add    3  ; many argument

External function:

      (version) ->

        %func0 (version . #<primitive-procedure version>) ; no argument

      (display "hello") ->

        %loadi "hello"
        %func1 (display . #<primitive-procedure display>) ; one argument

      (open-file "file" "w") ->

        %pushi "file"
        %loadi "w"
        %func2 (open-file . #<primitive-procedure open-file>) ; two arguments

      (equal 1 2 3)

        %pushi 1
        %pushi 2
        %pushi 3
        %loadi 3                                      ; the number of arguments
        %func  (equal . #<primitive-procedure equal>) ; many arguments

Subprogram call
===============

Instruction Set
***************

The Guile VM instruction set is roughly divided two groups: system instructions and functional instructions.  System instructions control the execution of programs, while functional instructions provide many useful calculations.

Environment Control Instructions
================================

 -- Instruction: link binding-name
     Look up BINDING-NAME (a string) in the current environment and push the corresponding variable object onto the stack.  If BINDING-NAME is not bound yet, then create a new binding and push its variable object.

 -- Instruction: variable-ref
     Dereference the variable object which is on top of the stack and replace it by the value of the variable it represents.

 -- Instruction: variable-set
     Set the value of the variable on top of the stack (at sp[0]) to the object located immediately before (at sp[-1]).

As an example, let us look at what a simple function call looks like:

     (+ 2 3)

This call yields the following sequence of instructions:

     (link "+")      ;; lookup binding "+"
     (variable-ref)  ;; dereference it
     (make-int8 2)   ;; push immediate value `2'
     (make-int8 3)   ;; push immediate value `3'
     (tail-call 2)   ;; call the proc at sp[-3] with two args

 -- Instruction: local-ref offset
     Push onto the stack the value of the local variable located at OFFSET within the current stack frame.

 -- Instruction: local-set offset
     Pop the Scheme object located on top of the stack and make it the new value of the local variable located at OFFSET within the current stack frame.

 -- Instruction: external-ref offset
     Push the value of the closure variable located at position OFFSET within the program's list of external variables.

 -- Instruction: external-set offset
     Pop the Scheme object located on top of the stack and make it the new value of the closure variable located at OFFSET within the program's list of external variables.

 -- Instruction: make-closure
     Pop the program object from the stack and assign it the current closure variable list as its closure.  Push the result program object.

Let's illustrate this:

     (let ((x 2))
       (lambda ()
         (let ((x++ (+ 1 x)))
           (set! x x++)
           x++)))

The resulting program has one external (closure) variable, i.e. its NEXTS is set to 1 (see Subprogram Control Instructions). This yields the following code:

        ;; the traditional program prologue with NLOCS = 0 and NEXTS = 1

        0    (make-int8 2)
        2    (external-set 0)
        4    (make-int8 4)
        6    (link "+")     ;; lookup `+'
        9    (vector 1)     ;; create the external variable vector for
                            ;; later use by `object-ref' and `object-set'
             ...
       40    (load-program ##34#)
       59    (make-closure) ;; assign the current closure to the program
                            ;; just pushed by `load-program'
       60    (return)

The program loaded here by LOAD-PROGRAM contains the following sequence of instructions:

        0    (object-ref 0)     ;; push the variable for `+'
        2    (variable-ref)     ;; dereference `+'
        3    (make-int8:1)      ;; push 1
        4    (external-ref 0)   ;; push the value of `x'
        6    (call 2)           ;; call `+' and push the result
        8    (local-set 0)      ;; make it the new value of `x++'
       10    (local-ref 0)      ;; push the value of `x++'
       12    (external-set 0)   ;; make it the new value of `x'
       14    (local-ref 0)      ;; push the value of `x++'
       16    (return)           ;; return it

At this point, you should know pretty much everything about the three types of variables a program may need to access.

Branch Instructions
===================

All the conditional branch instructions described below work in the same way:

  * They take the Scheme object located on the stack and use it as the branch condition;

  * If the condition if false, then program execution continues with the next instruction;

  * If the condition is true, then the instruction pointer is increased by the offset passed as an argument to the branch instruction;

  * Finally, when the instruction finished, the condition object is removed from the stack.

Note that the offset passed to the instruction is encoded on two 8-bit integers which are then combined by the VM as one 16-bit integer.

 -- Instruction: br offset
     Jump to OFFSET.

 -- Instruction: br-if offset
     Jump to OFFSET if the condition on the stack is not false.

 -- Instruction: br-if-not offset
     Jump to OFFSET if the condition on the stack is false.

 -- Instruction: br-if-eq offset
     Jump to OFFSET if the two objects located on the stack are equal in the sense of EQ?.  Note that, for this instruction, the stack pointer is decremented by two Scheme objects instead of only one.

 -- Instruction: br-if-not-eq offset
     Same as BR-IF-EQ for non-equal objects.

 -- Instruction: br-if-null offset
     Jump to OFFSET if the object on the stack is '().

 -- Instruction: br-if-not-null offset
     Jump to OFFSET if the object on the stack is not '().

Subprogram Control Instructions
===============================

Programs (read: ``compiled procedure'') may refer to external bindings, like variables or functions defined outside the program itself, in the environment in which it will evaluate at run-time.  In a sense, a program's environment and its bindings are an implicit parameter of every program.

In order to handle such bindings, each program has an object table associated to it.  This table (actually a Scheme vector) contains all constant objects referenced by the program.  The object table of a program is initialized right before a program is loaded with LOAD-PROGRAM.

Variable objects are one such type of constant object: when a global binding is defined, a variable object is associated to it and that object will remain constant over time, even if the value bound to it changes.  Therefore, external bindings only need to be looked up once when the program is loaded.  References to the corresponding external variables from within the program are then performed via the OBJECT-REF instruction and are almost as fast as local variable references.

Let us consider the following program (procedure) which references external bindings frob and %MAGIC:

     (lambda (x)
       (frob x %magic))

This yields the following assembly code:

     (make-int8 64)   ;; number of args, vars, etc. (see below)
     (link "frob")
     (link "%magic")
     (vector 2)       ;; object table (external bindings)
     ...
     (load-program #u8(20 0 23 21 0 20 1 23 36 2))
     (return)

All the instructions occurring before LOAD-PROGRAM (some were omitted for simplicity) form a prologue which, among other things, pushed an object table (a vector) that contains the variable objects for the variables bound to FROB and %MAGIC.  This vector and other data pushed onto the stack are then popped by the LOAD-PROGRAM instruction.

Besides, the LOAD-PROGRAM instruction takes one explicit argument which is the bytecode of the program itself.  Disassembled, this bytecode looks like:

     (object-ref 0)  ;; push the variable object of `frob'
     (variable-ref)  ;; dereference it
     (local-ref 0)   ;; push the value of `x'
     (object-ref 1)  ;; push the variable object of `%magic'
     (variable-ref)  ;; dereference it
     (tail-call 2)   ;; call `frob' with two parameters

This clearly shows that there is little difference between references to local variables and references to externally bound variables since lookup of externally bound variables if performed only once before the program is run.

 -- Instruction: load-program bytecode
     Load the program whose bytecode is BYTECODE (a u8vector), pop its meta-information from the stack, and push a corresponding program object onto the stack.  The program's meta-information may consist of (in the order in which it should be pushed onto the stack):

       * optionally, a pair representing meta-data (see the PROGRAM-META procedure); [FIXME: explain their meaning]

       * optionally, a vector which is the program's object table (a program that does not reference external bindings does not need an object table);

       * either one immediate integer or four immediate integers representing respectively the number of arguments taken by the function (NARGS), the number of rest arguments (NREST, 0 or 1), the number of local variables (NLOCS) and the number of external variables (NEXTS) (see Environment Control Instructions).

 -- Instruction: object-ref offset
     Push the variable object for the external variable located at OFFSET within the program's object table.

 -- Instruction: return
     Free the program's frame.

 -- Instruction: call nargs
     Call the procedure, continuation or program located at sp[-nargs] with the NARGS arguments located from sp[0] to sp[-nargs + 1].  The procedure/continuation/program and its arguments are dropped from the stack and the result is pushed.  When calling a program, the call instruction reserves room for its local variables on the stack, and initializes its list of closure variables and its vector of externally bound variables.

 -- Instruction: tail-call nargs
     Same as call except that, for tail-recursive calls to a program, the current stack frame is re-used, as required by RnRS. This instruction is otherwise similar to call.

Data Control Instructions
=========================

 -- Instruction: make-int8 value
     Push VALUE, an 8-bit integer, onto the stack.

 -- Instruction: make-int8:0
     Push the immediate value 0 onto the stack.

 -- Instruction: make-int8:1
     Push the immediate value 1 onto the stack.

 -- Instruction: make-false
     Push #f onto the stack.

 -- Instruction: make-true
     Push #t onto the stack.

  * %push

  * %pushi

  * %pushl, %pushl:0:0, %pushl:0:1, %pushl:0:2, %pushl:0:3

  * %pushe, %pushe:0:0, %pushe:0:1, %pushe:0:2, %pushe:0:3

  * %pusht

  * %loadi

  * %loadl, %loadl:0:0, %loadl:0:1, %loadl:0:2, %loadl:0:3

  * %loade, %loade:0:0, %loade:0:1, %loade:0:2, %loade:0:3

  * %loadt

  * %savei

  * %savel, %savel:0:0, %savel:0:1, %savel:0:2, %savel:0:3

  * %savee, %savee:0:0, %savee:0:1, %savee:0:2, %savee:0:3

  * %savet

Flow control instructions
=========================

  * %br-if

  * %br-if-not

  * %jump

Function call instructions
==========================

  * %func, %func0, %func1, %func2

Scheme built-in functions
=========================

  * cons

  * car

  * cdr

Mathematical buitin functions
=============================

  * 1+

  * 1-

  * add, add2

  * sub, sub2, minus

  * mul2

  * div2

  * lt2

  * gt2

  * le2

  * ge2

  * num-eq2