A Virtual Machine for Guile
===========================

Guile has both an interpreter and a compiler. To a user, the difference is transparent---interpreted and compiled procedures can call each other as they please.

The difference is that the compiler creates and interprets bytecode for a custom virtual machine, instead of interpreting the S-expressions directly. Loading and running compiled code is faster than loading and running source code.

The virtual machine that does the bytecode interpretation is a part of Guile itself. This section describes the nature of Guile's virtual machine.

Why a VM?
---------

For a long time, Guile only had an interpreter. Guile's interpreter operated directly on the S-expression representation of Scheme source code.

But while the interpreter was highly optimized and hand-tuned, it still performs many needless computations during the course of evaluating an expression. For example, application of a function to arguments needlessly consed up the arguments in a list. Evaluation of an expression always had to figure out what the car of the expression is -- a procedure, a memoized form, or something else. All values have to be allocated on the heap. Et cetera.

The solution to this problem was to compile the higher-level language, Scheme, into a lower-level language for which all of the checks and dispatching have already been done---the code is instead stripped to the bare minimum needed to ``do the job''.

The question becomes then, what low-level language to choose? There are many options. We could compile to native code directly, but that poses portability problems for Guile, as it is a highly cross-platform project.

So we want the performance gains that compilation provides, but we also want to maintain the portability benefits of a single code path. The obvious solution is to compile to a virtual machine that is present on all Guile installations.

The easiest (and most fun) way to depend on a virtual machine is to implement the virtual machine within Guile itself. This way the virtual machine provides what Scheme needs (tail calls, multiple values, call/cc) and can provide optimized inline instructions for Guile (cons, struct-ref, etc.).

So this is what Guile does. The rest of this section describes that VM that Guile implements, and the compiled procedures that run on it.

Before moving on, though, we should note that though we spoke of the interpreter in the past tense, Guile still has an interpreter. The difference is that before, it was Guile's main evaluator, and so was implemented in highly optimized C; now, it is actually implemented in Scheme, and compiled down to VM bytecode, just like any other program. (There is still a C interpreter around, used to bootstrap the compiler, but it is not normally used at runtime.)

The upside of implementing the interpreter in Scheme is that we preserve tail calls and multiple-value handling between interpreted and compiled code. The downside is that the interpreter in Guile 2.0 is slower than the interpreter in 1.8. We hope the that the compiler's speed makes up for the loss!

Also note that this decision to implement a bytecode compiler does not preclude native compilation. We can compile from bytecode to native code at runtime, or even do ahead of time compilation. More possibilities are discussed in Extending the Compiler.

VM Concepts
-----------

Compiled code is run by a virtual machine (VM). Each thread has its own VM. When a compiled procedure is run, Guile looks up the virtual machine for the current thread and executes the procedure using that VM.

Guile's virtual machine is a stack machine---that is, it has few registers, and the instructions defined in the VM operate by pushing and popping values from a stack.

Stack memory is exclusive to the virtual machine that owns it. In addition to their stacks, virtual machines also have access to the global memory (modules, global bindings, etc) that is shared among other parts of Guile, including other VMs.

A VM has generic instructions, such as those to reference local variables, and instructions designed to support Guile's languages -- mathematical instructions that support the entire numerical tower, an inlined implementation of cons, etc.

The registers that a VM has are as follows:

  * ip - Instruction pointer

  * sp - Stack pointer

  * fp - Frame pointer

In other architectures, the instruction pointer is sometimes called the ``program counter'' (pc). This set of registers is pretty typical for stack machines; their exact meanings in the context of Guile's VM are described in the next section.

Stack Layout
------------

While not strictly necessary to understand how to work with the VM, it is instructive and sometimes entertaining to consider the structure of the VM stack.

Logically speaking, a VM stack is composed of ``frames''. Each frame corresponds to the application of one compiled procedure, and contains storage space for arguments, local variables, intermediate values, and some bookkeeping information (such as what to do after the frame computes its value).

While the compiler is free to do whatever it wants to, as long as the semantics of a computation are preserved, in practice every time you call a function, a new frame is created. (The notable exception of course is the tail call case, see Tail Calls.)

Within a frame, you have the data associated with the function application itself, which is of a fixed size, and the stack space for intermediate values. Sometimes only the former is referred to as the ``frame'', and the latter is the ``stack'', although all pending application frames can have some intermediate computations interleaved on the stack.

The structure of the fixed part of an application frame is as follows:

                  Stack
        | ...              |
        | Intermed. val. 0 | <- fp + bp->nargs + bp->nlocs = SCM_FRAME_UPPER_ADDRESS (fp)
        +==================+
        | Local variable 1 |
        | Local variable 0 | <- fp + bp->nargs
        | Argument 1       |
        | Argument 0       | <- fp
        | Program          | <- fp - 1
        +------------------+
        | Return address   |
        | MV return address|
        | Dynamic link     | <- fp - 4 = SCM_FRAME_DATA_ADDRESS (fp) = SCM_FRAME_LOWER_ADDRESS (fp)
        +==================+
        |                  |

In the above drawing, the stack grows upward. The intermediate values stored in the application of this frame are stored above SCM_FRAME_UPPER_ADDRESS (fp). bp refers to the struct scm_objcode data associated with the program at fp - 1. nargs and nlocs are properties of the compiled procedure, which will be discussed later.

The individual fields of the frame are as follows:

Return address
     The ip that was in effect before this program was applied. When we return from this activation frame, we will jump back to this ip.

MV return address
     The ip to return to if this application returns multiple values. For continuations that only accept one value, this value will be NULL; for others, it will be an ip that points to a multiple-value return address in the calling code. That code will expect the top value on the stack to be an integer---the number of values being returned---and that below that integer there are the values being returned.

Dynamic link
     This is the fp in effect before this program was applied. In effect, this and the return address are the registers that are always ``saved''. The dynamic link links the current frame to the previous frame; computing a stack trace involves traversing these frames.

Local variable N
     Lambda-local variables that are all allocated as part of the frame. This makes access to variables very cheap.

Argument N
     The calling convention of the VM requires arguments of a function application to be pushed on the stack, and here they are. References to arguments dispatch to these locations on the stack.

Program
     This is the program being applied. For more information on how programs are implemented, see VM Programs.

Variables and the VM
--------------------

Consider the following Scheme code as an example:

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

Within the lambda expression, foo is a top-level variable, a is a lexically captured variable, and b is a local variable.

Another way to refer to a and b is to say that a is a ``free'' variable, since it is not defined within the lambda, and b is a ``bound'' variable. These are the terms used in the lambda calculus, a mathematical notation for describing functions. The lambda calculus is useful because it allows one to prove statements about functions. It is especially good at describing scope relations, and it is for that reason that we mention it here.

Guile allocates all variables on the stack. When a lexically enclosed procedure with free variables---a closure---is created, it copies those variables into its free variable vector. References to free variables are then redirected through the free variable vector.

If a variable is ever set!, however, it will need to be heap-allocated instead of stack-allocated, so that different closures that capture the same variable can see the same value. Also, this allows continuations to capture a reference to the variable, instead of to its value at one point in time. For these reasons, set! variables are allocated in ``boxes''---actually, in variable cells. See Variables, for more information. References to set! variables are indirected through the boxes.

Thus perhaps counterintuitively, what would seem ``closer to the metal'', viz set!, actually forces an extra memory allocation and indirection.

Going back to our example, b may be allocated on the stack, as it is never mutated.

a may also be allocated on the stack, as it too is never mutated. Within the enclosed lambda, its value will be copied into (and referenced from) the free variables vector.

foo is a top-level variable, because foo is not lexically bound in this example.

Compiled Procedures are VM Programs
-----------------------------------

By default, when you enter in expressions at Guile's REPL, they are first compiled to VM object code, then that VM object code is executed to produce a value. If the expression evaluates to a procedure, the result of this process is a compiled procedure.

A compiled procedure is a compound object, consisting of its bytecode, a reference to any captured lexical variables, an object array, and some metadata such as the procedure's arity, name, and documentation. You can pick apart these pieces with the accessors in (system vm program). See Compiled Procedures, for a full API reference.

The object array of a compiled procedure, also known as the object table, holds all Scheme objects whose values are known not to change across invocations of the procedure: constant strings, symbols, etc. The object table of a program is initialized right before a program is loaded with load-program. See Loading Instructions, for more information.

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, toplevel bindings only need to be looked up once. Thereafter, references to the corresponding toplevel variables from within the program are then performed via the toplevel-ref instruction, which uses the object vector, and are almost as fast as local variable references.

We can see how these concepts tie together by disassembling the foo function we defined earlier to see what is going on:

     scheme@(guile-user)> (define (foo a) (lambda (b) (list foo a b)))
     scheme@(guile-user)> ,x foo
        0    (assert-nargs-ee/locals 1)
        2    (object-ref 1)                  ;; #<procedure 8ebec20 at <current input>:0:17 (b)>
        4    (local-ref 0)                   ;; `a'
        6    (make-closure 0 1)
        9    (return)

     ----------------------------------------
     Disassembly of #<procedure 8ebec20 at <current input>:0:17 (b)>:

        0    (assert-nargs-ee/locals 1)
        2    (toplevel-ref 1)                ;; `foo'
        4    (free-ref 0)                    ;; (closure variable)
        6    (local-ref 0)                   ;; `b'
        8    (list 0 3)                      ;; 3 elements         at (unknown file):0:29
       11    (return)

First there's some prelude, where foo checks that it was called with only 1 argument. Then at ip 2, we load up the compiled lambda. Ip 4 loads up `a', so that it can be captured into a closure by at ip 6---binding code (from the compiled lambda) with data (the free-variable vector). Finally we return the closure.

The second stanza disassembles the compiled lambda. After the prelude, we note that toplevel variables are resolved relative to the module that was current when the procedure was created. This lookup occurs lazily, at the first time the variable is actually referenced, and the location of the lookup is cached so that future references are very cheap. See Top-Level Environment Instructions, for more details.

Then we see a reference to a free variable, corresponding to a. The disassembler doesn't have enough information to give a name to that variable, so it just marks it as being a ``closure variable''. Finally we see the reference to b, then the list opcode, an inline implementation of the list scheme routine.

Instruction Set
---------------

There are about 180 instructions in Guile's virtual machine. These instructions represent atomic units of a program's execution. Ideally, they perform one task without conditional branches, then dispatch to the next instruction in the stream.

Instructions themselves are one byte long. Some instructions take parameters, which follow the instruction byte in the instruction stream.

Sometimes the compiler can figure out that it is compiling a special case that can be run more efficiently. So, for example, while Guile offers a generic test-and-branch instruction, it also offers specific instructions for special cases, so that the following cases all have their own test-and-branch instructions:

     (if pred then else)
     (if (not pred) then else)
     (if (null? l) then else)
     (if (not (null? l)) then else)

In addition, some Scheme primitives have their own inline implementations, e.g. cons, and list, as we saw in the previous section.

So Guile's instruction set is a complete instruction set, in that it provides the instructions that are suited to the problem, and is not concerned with making a minimal, orthogonal set of instructions. More instructions may be added over time.

Lexical Environment Instructions
................................

These instructions access and mutate the lexical environment of a compiled procedure---its free and bound variables.

Some of these instructions have long- variants, the difference being that they take 16-bit arguments, encoded in big-endianness, instead of the normal 8-bit range.

See Stack Layout, for more information on the format of stack frames.

 -- Instruction: local-ref index
 -- Instruction: long-local-ref index
     Push onto the stack the value of the local variable located at INDEX within the current stack frame.

     Note that arguments and local variables are all in one block. Thus the first argument, if any, is at index 0, and local bindings follow the arguments.

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

 -- Instruction: box index
     Pop a value off the stack, and set the INDEXnth local variable to a box containing that value. A shortcut for make-variable then local-set, used when binding boxed variables.

 -- Instruction: empty-box index
     Set the INDEXth local variable to a box containing a variable whose value is unbound. Used when compiling some letrec expressions.

 -- Instruction: local-boxed-ref index
 -- Instruction: local-boxed-set index
     Get or set the value of the variable located at INDEX within the current stack frame. A shortcut for local-ref then variable-ref or variable-set, respectively.

 -- Instruction: free-ref index
     Push the value of the captured variable located at position INDEX within the program's vector of captured variables.

 -- Instruction: free-boxed-ref index
 -- Instruction: free-boxed-set index
     Get or set a boxed free variable. A shortcut for free-ref then variable-ref or variable-set, respectively.

     Note that there is no free-set instruction, as variables that are set! must be boxed.

 -- Instruction: make-closure num-free-vars
     Pop NUM-FREE-VARS values and a program object off the stack in that order, and push a new program object closing over the given free variables. NUM-FREE-VARS is encoded as a two-byte big-endian value.

     The free variables are stored in an array, inline to the new program object, in the order that they were on the stack (not the order they are popped off). The new closure shares state with the original program. At the time of this writing, the space overhead of closures is 3 words, plus one word for each free variable.

 -- Instruction: fix-closure index
     Fix up the free variables array of the closure stored in the INDEXth local variable. INDEX is a two-byte big-endian integer.

     This instruction will pop as many values from the stack as are in the corresponding closure's free variables array. The topmost value on the stack will be stored as the closure's last free variable, with other values filling in free variable slots in order.

     fix-closure is part of a hack for allocating mutually recursive procedures. The hack is to store the procedures in their corresponding local variable slots, with space already allocated for free variables. Then once they are all in place, this instruction fixes up their procedures' free variable bindings in place. This allows most letrec-bound procedures to be allocated unboxed on the stack.

 -- Instruction: local-bound? index
 -- Instruction: long-local-bound? index
     Push #t on the stack if the indexth local variable has been assigned, or #f otherwise. Mostly useful for handling optional arguments in procedure prologues.

Top-Level Environment Instructions
..................................

These instructions access values in the top-level environment: bindings that were not lexically apparent at the time that the code in question was compiled.

The location in which a toplevel binding is stored can be looked up once and cached for later. The binding itself may change over time, but its location will stay constant.

Currently only toplevel references within procedures are cached, as only procedures have a place to cache them, in their object tables.

 -- Instruction: toplevel-ref index
 -- Instruction: long-toplevel-ref index
     Push the value of the toplevel binding whose location is stored in at position INDEX in the current procedure's object table. The long- variant encodes the index over two bytes.

     Initially, a cell in a procedure's object table that is used by toplevel-ref is initialized to one of two forms. The normal case is that the cell holds a symbol, whose binding will be looked up relative to the module that was current when the current program was created.

     Alternately, the lookup may be performed relative to a particular module, determined at compile-time (e.g. via @ or @@). In that case, the cell in the object table holds a list: (MODNAME SYM PUBLIC?). The symbol SYM will be looked up in the module named MODNAME (a list of symbols). The lookup will be performed against the module's public interface, unless PUBLIC? is #f, which it is for example when compiling @@.

     In any case, if the symbol is unbound, an error is signalled. Otherwise the initial form is replaced with the looked-up variable, an in-place mutation of the object table. This mechanism provides for lazy variable resolution, and an important cached fast-path once the variable has been successfully resolved.

     This instruction pushes the value of the variable onto the stack.

 -- Instruction: toplevel-set index
 -- Instruction: long-toplevel-set index
     Pop a value off the stack, and set it as the value of the toplevel variable stored at INDEX in the object table. If the variable has not yet been looked up, we do the lookup as in toplevel-ref.

 -- Instruction: define
     Pop a symbol and a value from the stack, in that order. Look up its binding in the current toplevel environment, creating the binding if necessary. Set the variable to the value.

 -- Instruction: link-now
     Pop a value, X, from the stack. Look up the binding for X, according to the rules for toplevel-ref, and push that variable on the stack. If the lookup fails, an error will be signalled.

     This instruction is mostly used when loading programs, because it can do toplevel variable lookups without an object table.

 -- 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
     Pop off two objects from the stack, a variable and a value, and set the variable to the value.

 -- Instruction: variable-bound?
     Pop off the variable object from top of the stack and push #t if it is bound, or #f otherwise. Mostly useful in procedure prologues for defining default values for boxed optional variables.

 -- Instruction: make-variable
     Replace the top object on the stack with a variable containing it. Used in some circumstances when compiling letrec expressions.

Procedure Call and Return Instructions
......................................

 -- Instruction: new-frame
     Push a new frame on the stack, reserving space for the dynamic link, return address, and the multiple-values return address. The frame pointer is not yet updated, because the frame is not yet active -- it has to be patched by a call instruction to get the return address.

 -- Instruction: call nargs
     Call the procedure located at sp[-nargs] with the NARGS arguments located from sp[-nargs + 1] to sp[0].

     This instruction requires that a new frame be pushed on the stack before the procedure, via new-frame. See Stack Layout, for more information. It patches up that frame with the current ip as the return address, then dispatches to the first instruction in the called procedure, relying on the called procedure to return one value to the newly-created continuation. Because the new frame pointer will point to sp[-nargs + 1], the arguments don't have to be shuffled around -- they are already in place.

 -- Instruction: tail-call nargs
     Transfer control to the procedure located at sp[-nargs] with the NARGS arguments located from sp[-nargs + 1] to sp[0].

     Unlike call, which requires a new frame to be pushed onto the stack, tail-call simply shuffles down the procedure and arguments to the current stack frame. This instruction implements tail calls as required by RnRS.

 -- Instruction: apply nargs
 -- Instruction: tail-apply nargs
     Like call and tail-call, except that the top item on the stack must be a list. The elements of that list are then pushed on the stack and treated as additional arguments, replacing the list itself, then the procedure is invoked as usual.

 -- Instruction: call/nargs
 -- Instruction: tail-call/nargs
     These are like call and tail-call, except they take the number of arguments from the stack instead of the instruction stream. These instructions are used in the implementation of multiple value returns, where the actual number of values is pushed on the stack.

 -- Instruction: mv-call nargs offset
     Like call, except that a multiple-value continuation is created in addition to a single-value continuation.

     The offset (a three-byte value) is an offset within the instruction stream; the multiple-value return address in the new frame (see Stack Layout) will be set to the normal return address plus this offset. Instructions at that offset will expect the top value of the stack to be the number of values, and below that values themselves, pushed separately.

 -- Instruction: return
     Free the program's frame, returning the top value from the stack to the current continuation. (The stack should have exactly one value on it.)

     Specifically, the sp is decremented to one below the current fp, the ip is reset to the current return address, the fp is reset to the value of the current dynamic link, and then the returned value is pushed on the stack.

 -- Instruction: return/values nvalues
 -- Instruction: return/nvalues
     Return the top NVALUES to the current continuation. In the case of return/nvalues, NVALUES itself is first popped from the top of the stack.

     If the current continuation is a multiple-value continuation, return/values pushes the number of values on the stack, then returns as in return, but to the multiple-value return address.

     Otherwise if the current continuation accepts only one value, i.e. the multiple-value return address is NULL, then we assume the user only wants one value, and we give them the first one. If there are no values, an error is signaled.

 -- Instruction: return/values* nvalues
     Like a combination of apply and return/values, in which the top value on the stack is interpreted as a list of additional values. This is an optimization for the common (apply values ...) case.

 -- Instruction: truncate-values nbinds nrest
     Used in multiple-value continuations, this instruction takes the values that are on the stack (including the number-of-values marker) and truncates them for a binding construct.

     For example, a call to (receive (x y . z) (foo) ...) would, logically speaking, pop off the values returned from (foo) and push them as three values, corresponding to x, y, and z. In that case, NBINDS would be 3, and NREST would be 1 (to indicate that one of the bindings was a rest argument).

     Signals an error if there is an insufficient number of values.

 -- Instruction: call/cc
 -- Instruction: tail-call/cc
     Capture the current continuation, and then call (or tail-call) the procedure on the top of the stack, with the continuation as the argument.

     call/cc does not require a new-frame to be pushed on the stack, as call does, because it needs to capture the stack before the frame is pushed.

     Both the VM continuation and the C continuation are captured.

Function Prologue Instructions
..............................

A function call in Guile is very cheap: the VM simply hands control to the procedure. The procedure itself is responsible for asserting that it has been passed an appropriate number of arguments. This strategy allows arbitrarily complex argument parsing idioms to be developed, without harming the common case.

For example, only calls to keyword-argument procedures ``pay'' for the cost of parsing keyword arguments. (At the time of this writing, calling procedures with keyword arguments is typically two to four times as costly as calling procedures with a fixed set of arguments.)

 -- Instruction: assert-nargs-ee n
 -- Instruction: assert-nargs-ge n
     Assert that the current procedure has been passed exactly N arguments, for the -ee case, or N or more arguments, for the -ge case. N is encoded over two bytes.

     The number of arguments is determined by subtracting the frame pointer from the stack pointer (sp - (fp -1)). See Stack Layout, for more details on stack frames.

 -- Instruction: br-if-nargs-ne n offset
 -- Instruction: br-if-nargs-gt n offset
 -- Instruction: br-if-nargs-lt n offset
     Jump to OFFSET if the number of arguments is not equal to, greater than, or less than N. N is encoded over two bytes, and OFFSET has the normal three-byte encoding.

     These instructions are used to implement multiple arities, as in case-lambda. See Case-lambda, for more information.

 -- Instruction: bind-optionals n
     If the procedure has been called with fewer than N arguments, fill in the remaining arguments with an unbound value (SCM_UNDEFINED). N is encoded over two bytes.

     The optionals can be later initialized conditionally via the local-bound? instruction.

 -- Instruction: push-rest n
     Pop off excess arguments (more than N), collecting them into a list, and push that list. Used to bind a rest argument, if the procedure has no keyword arguments. Procedures with keyword arguments use bind-rest instead.

 -- Instruction: bind-rest n idx
     Pop off excess arguments (more than N), collecting them into a list. The list is then assigned to the IDXth local variable.

 -- Instruction: bind-optionals/shuffle nreq nreq-and-opt ntotal
 -- Instruction: bind-optionals/shuffle-or-br nreq nreq-and-opt ntotal offset
     Shuffle keyword arguments to the top of the stack, filling in the holes with SCM_UNDEFINED. Each argument is encoded over two bytes.

     This instruction is used by procedures with keyword arguments. NREQ is the number of required arguments to the procedure, and NREQ-AND-OPT is the total number of positional arguments (required plus optional). bind-optionals/shuffle will scan the stack from the NREQth argument up to the NREQ-AND-OPTth, and start shuffling when it sees the first keyword argument or runs out of positional arguments.

     bind-optionals/shuffle-or-br does the same, except that it checks if there are too many positional arguments before shuffling.  If this is the case, it jumps to OFFSET, encoded using the normal three-byte encoding.

     Shuffling simply moves the keyword arguments past the total number of arguments, NTOTAL, which includes keyword and rest arguments. The free slots created by the shuffle are filled in with SCM_UNDEFINED, so they may be conditionally initialized later in the function's prologue.

 -- Instruction: bind-kwargs idx ntotal flags
     Parse keyword arguments, assigning their values to the corresponding local variables. The keyword arguments should already have been shuffled above the NTOTALth stack slot by bind-optionals/shuffle.

     The parsing is driven by a keyword arguments association list, looked up from the IDXth element of the procedures object array. The alist is a list of pairs of the form (KW . INDEX), mapping keyword arguments to their local variable indices.

     There are two bitflags that affect the parser, allow-other-keys? (0x1) and rest? (0x2). Unless allow-other-keys? is set, the parser will signal an error if an unknown key is found. If rest? is set, errors parsing the keyword arguments will be ignored, as a later bind-rest instruction will collect all of the tail arguments, including the keywords, into a list. Otherwise if the keyword arguments are invalid, an error is signalled.

     IDX and NTOTAL are encoded over two bytes each, and FLAGS is encoded over one byte.

 -- Instruction: reserve-locals n
     Resets the stack pointer to have space for N local variables, including the arguments. If this operation increments the stack pointer, as in a push, the new slots are filled with SCM_UNBOUND. If this operation decrements the stack pointer, any excess values are dropped.

     reserve-locals is typically used after argument parsing to reserve space for local variables.

 -- Instruction: assert-nargs-ee/locals n
 -- Instruction: assert-nargs-ge/locals n
     A combination of assert-nargs-ee and reserve-locals. The number of arguments is encoded in the lower three bits of N, a one-byte value. The number of additional local variables is take from the upper 5 bits of N.

Trampoline Instructions
.......................

Though most applicable objects in Guile are procedures implemented in bytecode, not all are. There are primitives, continuations, and other procedure-like objects that have their own calling convention. Instead of adding special cases to the call instruction, Guile wraps these other applicable objects in VM trampoline procedures, then provides special support for these objects in bytecode.

Trampoline procedures are typically generated by Guile at runtime, for example in response to a call to scm_c_make_gsubr. As such, a compiler probably shouldn't emit code with these instructions. However, it's still interesting to know how these things work, so we document these trampoline instructions here.

 -- Instruction: subr-call nargs
     Pop off a foreign pointer (which should have been pushed on by the trampoline), and call it directly, with the NARGS arguments from the stack. Return the resulting value or values to the calling procedure.

 -- Instruction: foreign-call nargs
     Pop off an internal foreign object (which should have been pushed on by the trampoline), and call that foreign function with the NARGS arguments from the stack. Return the resulting value to the calling procedure.

 -- Instruction: continuation-call
     Pop off an internal continuation object (which should have been pushed on by the trampoline), and reinstate that continuation. All of the procedure's arguments are passed to the continuation. Does not return.

 -- Instruction: partial-cont-call
     Pop off two objects from the stack: the dynamic winds associated with the partial continuation, and the VM continuation object. Unroll the continuation onto the stack, rewinding the dynamic environment and overwriting the current frame, and pass all arguments to the continuation. Control flow proceeds where the continuation was captured.

Branch Instructions
...................

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

  * They pop off Scheme object(s) located on the stack for use in the branch condition

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

  * Program execution proceeds with the next instruction (that is, the one to which the instruction pointer points).

Note that the offset passed to the instruction is encoded as three 8-bit integers, in big-endian order, effectively giving Guile a 24-bit relative address space.

 -- Instruction: br offset
     Jump to OFFSET. No values are popped.

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

 -- Instruction: br-if-not offset
     Jump to OFFSET if the object 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-eq? 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 '().

Data Constructor Instructions
.............................

These instructions push simple immediate values onto the stack, or construct compound data structures from values on the stack.

 -- 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-int16 value
     Push VALUE, a 16-bit integer, onto the stack.

 -- Instruction: make-uint64 value
     Push VALUE, an unsigned 64-bit integer, onto the stack. The value is encoded in 8 bytes, most significant byte first (big-endian).

 -- Instruction: make-int64 value
     Push VALUE, a signed 64-bit integer, onto the stack. The value is encoded in 8 bytes, most significant byte first (big-endian), in twos-complement arithmetic.

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

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

 -- Instruction: make-nil
     Push #nil onto the stack.

 -- Instruction: make-eol
     Push '() onto the stack.

 -- Instruction: make-char8 value
     Push VALUE, an 8-bit character, onto the stack.

 -- Instruction: make-char32 value
     Push VALUE, an 32-bit character, onto the stack. The value is encoded in big-endian order.

 -- Instruction: make-symbol
     Pops a string off the stack, and pushes a symbol.

 -- Instruction: make-keyword value
     Pops a symbol off the stack, and pushes a keyword.

 -- Instruction: list n
     Pops off the top N values off of the stack, consing them up into a list, then pushes that list on the stack. What was the topmost value will be the last element in the list. N is a two-byte value, most significant byte first.

 -- Instruction: vector n
     Create and fill a vector with the top N values from the stack, popping off those values and pushing on the resulting vector. N is a two-byte value, like in vector.

 -- Instruction: make-struct n
     Make a new struct from the top N values on the stack. The values are popped, and the new struct is pushed.

     The deepest value is used as the vtable for the struct, and the rest are used in order as the field initializers. Tail arrays are not supported by this instruction.

 -- Instruction: make-array n
     Pop an array shape from the stack, then pop the remaining N values, pushing a new array. N is encoded over three bytes.

     The array shape should be appropriate to store N values. See Array Procedures, for more information on array shapes.

Many of these data structures are constant, never changing over the course of the different invocations of the procedure. In that case it is often advantageous to make them once when the procedure is created, and just reference them from the object table thereafter. See Variables and the VM, for more information on the object table.

 -- Instruction: object-ref n
 -- Instruction: long-object-ref n
     Push Nth value from the current program's object vector. The ``long'' variant has a 16-bit index instead of an 8-bit index.

Loading Instructions
....................

In addition to VM instructions, an instruction stream may contain variable-length data embedded within it. This data is always preceded by special loading instructions, which interpret the data and advance the instruction pointer to the next VM instruction.

All of these loading instructions have a length parameter, indicating the size of the embedded data, in bytes. The length itself is encoded in 3 bytes.

 -- Instruction: load-number length
     Load an arbitrary number from the instruction stream. The number is embedded in the stream as a string.

 -- Instruction: load-string length
     Load a string from the instruction stream. The string is assumed to be encoded in the ``latin1'' locale.

 -- Instruction: load-wide-string length
     Load a UTF-32 string from the instruction stream. LENGTH is the length in bytes, not in codepoints.

 -- Instruction: load-symbol length
     Load a symbol from the instruction stream. The symbol is assumed to be encoded in the ``latin1'' locale. Symbols backed by wide strings may be loaded via load-wide-string then make-symbol.

 -- Instruction: load-array length
     Load a uniform array from the instruction stream. The shape and type of the array are popped off the stack, in that order.

 -- Instruction: load-program
     Load bytecode from the instruction stream, and push a compiled procedure.

     This instruction pops one value from the stack: the program's object table, as a vector, or #f in the case that the program has no object table. A program that does not reference toplevel bindings and does not use object-ref does not need an object table.

     This instruction is unlike the rest of the loading instructions, because instead of parsing its data, it directly maps the instruction stream onto a C structure, struct scm_objcode. See Bytecode and Objcode, for more information.

     The resulting compiled procedure will not have any free variables captured, so it may be loaded only once but used many times to create closures.

Dynamic Environment Instructions
................................

Guile's virtual machine has low-level support for dynamic-wind, dynamic binding, and composable prompts and aborts.

 -- Instruction: wind
     Pop an unwind thunk and a wind thunk from the stack, in that order, and push them onto the ``dynamic stack''. The unwind thunk will be called on nonlocal exits, and the wind thunk on reentries. Used to implement dynamic-wind.

     Note that neither thunk is actually called; the compiler should emit calls to wind and unwind for the normal dynamic-wind control flow. See Dynamic Wind.

 -- Instruction: unwind
     Pop off the top entry from the ``dynamic stack'', for example, a wind/unwind thunk pair. unwind instructions should be properly paired with their winding instructions, like wind.

 -- Instruction: wind-fluids n
     Pop off N values and N fluids from the stack, in that order. Set the fluids to the values by creating a with-fluids object and pushing that object on the dynamic stack. See Fluids and Dynamic States.

 -- Instruction: unwind-fluids
     Pop a with-fluids object from the dynamic stack, and swap the current values of its fluids with the saved values of its fluids. In this way, the dynamic environment is left as it was before the corresponding wind-fluids instruction was processed.

 -- Instruction: fluid-ref
     Pop a fluid from the stack, and push its current value.

 -- Instruction: fluid-set
     Pop a value and a fluid from the stack, in that order, and set the fluid to the value.

 -- Instruction: prompt escape-only? offset
     Establish a dynamic prompt. See Prompts, for more information on prompts.

     The prompt will be pushed on the dynamic stack. The normal control flow should ensure that the prompt is popped off at the end, via unwind.

     If an abort is made to this prompt, control will jump to OFFSET, a three-byte relative address. The continuation and all arguments to the abort will be pushed on the stack, along with the total number of arguments (including the continuation. If control returns to the handler, the prompt is already popped off by the abort mechanism. (Guile's prompt implements Felleisen's --F-- operator.)

     If ESCAPE-ONLY? is nonzero, the prompt will be marked as escape-only, which allows an abort to this prompt to avoid reifying the continuation.

 -- Instruction: abort n
     Abort to a dynamic prompt.

     This instruction pops one tail argument list, N arguments, and a prompt tag from the stack. The dynamic environment is then searched for a prompt having the given tag. If none is found, an error is signalled. Otherwise all arguments are passed to the prompt's handler, along with the captured continuation, if necessary.

     If the prompt's handler can be proven to not reference the captured continuation, no continuation is allocated. This decision happens dynamically, at run-time; the general case is that the continuation may be captured, and thus resumed. A reinstated continuation will have its arguments pushed on the stack, along with the number of arguments, as in the multiple-value return convention. Therefore an abort instruction should be followed by code ready to handle the equivalent of a multiply-valued return.

Miscellaneous Instructions
..........................

 -- Instruction: nop
     Does nothing! Used for padding other instructions to certain alignments.

 -- Instruction: halt
     Exits the VM, returning a SCM value. Normally, this instruction is only part of the ``bootstrap program'', a program run when a virtual machine is first entered; compiled Scheme procedures will not contain this instruction.

     If multiple values have been returned, the SCM value will be a multiple-values object (see Multiple Values).

 -- Instruction: break
     Does nothing, but invokes the break hook.

 -- Instruction: drop
     Pops off the top value from the stack, throwing it away.

 -- Instruction: dup
     Re-pushes the top value onto the stack.

 -- Instruction: void
     Pushes ``the unspecified value'' onto the stack.

Inlined Scheme Instructions
...........................

The Scheme compiler can recognize the application of standard Scheme procedures. It tries to inline these small operations to avoid the overhead of creating new stack frames.

Since most of these operations are historically implemented as C primitives, not inlining them would entail constantly calling out from the VM to the interpreter, which has some costs---registers must be saved, the interpreter has to dispatch, called procedures have to do much type checking, etc. It's much more efficient to inline these operations in the virtual machine itself.

All of these instructions pop their arguments from the stack and push their results, and take no parameters from the instruction stream. Thus, unlike in the previous sections, these instruction definitions show stack parameters instead of parameters from the instruction stream.

 -- Instruction: not x
 -- Instruction: not-not x
 -- Instruction: eq? x y
 -- Instruction: not-eq? x y
 -- Instruction: null?
 -- Instruction: not-null?
 -- Instruction: eqv? x y
 -- Instruction: equal? x y
 -- Instruction: pair? x y
 -- Instruction: list? x
 -- Instruction: set-car! pair x
 -- Instruction: set-cdr! pair x
 -- Instruction: cons x y
 -- Instruction: car x
 -- Instruction: cdr x
 -- Instruction: vector-ref x y
 -- Instruction: vector-set x n y
 -- Instruction: struct? x
 -- Instruction: struct-ref x n
 -- Instruction: struct-set x n v
 -- Instruction: struct-vtable x
 -- Instruction: class-of x
 -- Instruction: slot-ref struct n
 -- Instruction: slot-set struct n x
     Inlined implementations of their Scheme equivalents.

Note that caddr and friends compile to a series of car and cdr instructions.

Inlined Mathematical Instructions
.................................

Inlining mathematical operations has the obvious advantage of handling fixnums without function calls or allocations. The trick, of course, is knowing when the result of an operation will be a fixnum, and there might be a couple bugs here.

More instructions could be added here over time.

As in the previous section, the definitions below show stack parameters instead of instruction stream parameters.

 -- Instruction: add x y
 -- Instruction: add1 x
 -- Instruction: sub x y
 -- Instruction: sub1 x
 -- Instruction: mul x y
 -- Instruction: div x y
 -- Instruction: quo x y
 -- Instruction: rem x y
 -- Instruction: mod x y
 -- Instruction: ee? x y
 -- Instruction: lt? x y
 -- Instruction: gt? x y
 -- Instruction: le? x y
 -- Instruction: ge? x y
 -- Instruction: ash x n
 -- Instruction: logand x y
 -- Instruction: logior x y
 -- Instruction: logxor x y
     Inlined implementations of the corresponding mathematical operations.

Inlined Bytevector Instructions
...............................

Bytevector operations correspond closely to what the current hardware can do, so it makes sense to inline them to VM instructions, providing a clear path for eventual native compilation. Without this, Scheme programs would need other primitives for accessing raw bytes -- but these primitives are as good as any.

As in the previous section, the definitions below show stack parameters instead of instruction stream parameters.

The multibyte formats (u16, f64, etc) take an extra endianness argument. Only aligned native accesses are currently fast-pathed in Guile's VM.

 -- Instruction: bv-u8-ref bv n
 -- Instruction: bv-s8-ref bv n
 -- Instruction: bv-u16-native-ref bv n
 -- Instruction: bv-s16-native-ref bv n
 -- Instruction: bv-u32-native-ref bv n
 -- Instruction: bv-s32-native-ref bv n
 -- Instruction: bv-u64-native-ref bv n
 -- Instruction: bv-s64-native-ref bv n
 -- Instruction: bv-f32-native-ref bv n
 -- Instruction: bv-f64-native-ref bv n
 -- Instruction: bv-u16-ref bv n endianness
 -- Instruction: bv-s16-ref bv n endianness
 -- Instruction: bv-u32-ref bv n endianness
 -- Instruction: bv-s32-ref bv n endianness
 -- Instruction: bv-u64-ref bv n endianness
 -- Instruction: bv-s64-ref bv n endianness
 -- Instruction: bv-f32-ref bv n endianness
 -- Instruction: bv-f64-ref bv n endianness
 -- Instruction: bv-u8-set bv n val
 -- Instruction: bv-s8-set bv n val
 -- Instruction: bv-u16-native-set bv n val
 -- Instruction: bv-s16-native-set bv n val
 -- Instruction: bv-u32-native-set bv n val
 -- Instruction: bv-s32-native-set bv n val
 -- Instruction: bv-u64-native-set bv n val
 -- Instruction: bv-s64-native-set bv n val
 -- Instruction: bv-f32-native-set bv n val
 -- Instruction: bv-f64-native-set bv n val
 -- Instruction: bv-u16-set bv n val endianness
 -- Instruction: bv-s16-set bv n val endianness
 -- Instruction: bv-u32-set bv n val endianness
 -- Instruction: bv-s32-set bv n val endianness
 -- Instruction: bv-u64-set bv n val endianness
 -- Instruction: bv-s64-set bv n val endianness
 -- Instruction: bv-f32-set bv n val endianness
 -- Instruction: bv-f64-set bv n val endianness
     Inlined implementations of the corresponding bytevector operations.