diff options
Diffstat (limited to 'doc')
-rw-r--r-- | doc/guile.1 | 2 | ||||
-rw-r--r-- | doc/ref/Makefile.am | 4 | ||||
-rw-r--r-- | doc/ref/api-control.texi | 9 | ||||
-rw-r--r-- | doc/ref/api-coverage.texi | 12 | ||||
-rw-r--r-- | doc/ref/api-data.texi | 17 | ||||
-rw-r--r-- | doc/ref/api-debug.texi | 285 | ||||
-rw-r--r-- | doc/ref/api-evaluation.texi | 28 | ||||
-rw-r--r-- | doc/ref/api-io.texi | 24 | ||||
-rw-r--r-- | doc/ref/api-macros.texi | 178 | ||||
-rw-r--r-- | doc/ref/api-memory.texi | 2 | ||||
-rw-r--r-- | doc/ref/api-options.texi | 12 | ||||
-rw-r--r-- | doc/ref/api-peg.texi | 1036 | ||||
-rw-r--r-- | doc/ref/api-procedures.texi | 48 | ||||
-rw-r--r-- | doc/ref/compiler.texi | 1073 | ||||
-rw-r--r-- | doc/ref/guile-invoke.texi | 10 | ||||
-rw-r--r-- | doc/ref/guile.texi | 2 | ||||
-rw-r--r-- | doc/ref/history.texi | 53 | ||||
-rw-r--r-- | doc/ref/libguile-concepts.texi | 26 | ||||
-rw-r--r-- | doc/ref/libguile-parallel.texi | 10 | ||||
-rw-r--r-- | doc/ref/posix.texi | 41 | ||||
-rw-r--r-- | doc/ref/srfi-modules.texi | 23 | ||||
-rw-r--r-- | doc/ref/vm.texi | 2045 |
22 files changed, 3223 insertions, 1717 deletions
diff --git a/doc/guile.1 b/doc/guile.1 index e36c2aac7..5d8b4e158 100644 --- a/doc/guile.1 +++ b/doc/guile.1 @@ -4,7 +4,7 @@ .\" groff -man -Tascii foo.1 .\" .\" title section date source manual -.TH GUILE 1 "2011-03-04" GNU "GNU Guile 2.0" +.TH GUILE 1 "2011-03-04" GNU "GNU Guile 2.2" . .SH NAME guile \- The GNU Project Extension Language diff --git a/doc/ref/Makefile.am b/doc/ref/Makefile.am index 31c26a7ad..83c6e5ee0 100644 --- a/doc/ref/Makefile.am +++ b/doc/ref/Makefile.am @@ -45,6 +45,7 @@ guile_TEXINFOS = preface.texi \ api-foreign.texi \ api-regex.texi \ api-lalr.texi \ + api-peg.texi \ api-languages.texi \ api-evaluation.texi \ api-memory.texi \ @@ -119,8 +120,7 @@ EXTRA_DIST = ChangeLog-2008 $(PICTURES) libguile-autoconf.texi: autoconf-macros.texi autoconf-macros.texi: $(top_srcdir)/meta/guile.m4 - GUILE_INSTALL_LOCALE=1 GUILE_AUTO_COMPILE=0 \ - $(top_builddir)/meta/uninstalled-env guild \ + GUILE_AUTO_COMPILE=0 $(top_builddir)/meta/uninstalled-env guild \ snarf-guile-m4-docs $(top_srcdir)/meta/guile.m4 \ > $(srcdir)/$@ diff --git a/doc/ref/api-control.texi b/doc/ref/api-control.texi index 0b08dced1..4253a206a 100644 --- a/doc/ref/api-control.texi +++ b/doc/ref/api-control.texi @@ -494,14 +494,17 @@ those passed to @code{abort-to-prompt}. @end deffn @deffn {Scheme Procedure} make-prompt-tag [stem] -Make a new prompt tag. Currently prompt tags are generated symbols. -This may change in some future Guile version. +Make a new prompt tag. A prompt tag is simply a unique object. +Currently, a prompt tag is a fresh pair. This may change in some future +Guile version. @end deffn @deffn {Scheme Procedure} default-prompt-tag Return the default prompt tag. Having a distinguished default prompt tag allows some useful prompt and abort idioms, discussed in the next -section. +section. Note that @code{default-prompt-tag} is actually a parameter, +and so may be dynamically rebound using @code{parameterize}. +@xref{Parameters}. @end deffn @deffn {Scheme Procedure} abort-to-prompt tag val1 val2 @dots{} diff --git a/doc/ref/api-coverage.texi b/doc/ref/api-coverage.texi index 680997711..5081d343b 100644 --- a/doc/ref/api-coverage.texi +++ b/doc/ref/api-coverage.texi @@ -1,6 +1,6 @@ @c -*-texinfo-*- @c This is part of the GNU Guile Reference Manual. -@c Copyright (C) 2010 Free Software Foundation, Inc. +@c Copyright (C) 2010, 2013 Free Software Foundation, Inc. @c See the file guile.texi for copying conditions. @@ -14,10 +14,10 @@ part of the code is @dfn{covered} by the test suite. The @code{(system vm coverage)} module provides tools to gather code coverage data and to present them, as detailed below. -@deffn {Scheme Procedure} with-code-coverage vm thunk -Run @var{thunk}, a zero-argument procedure, using @var{vm}; instrument @var{vm} -to collect code coverage data. Return code coverage data and the values -returned by @var{thunk}. +@deffn {Scheme Procedure} with-code-coverage thunk +Run @var{thunk}, a zero-argument procedure, while instrumenting Guile's +virtual machine to collect code coverage data. Return code coverage +data and the values returned by @var{thunk}. @end deffn @deffn {Scheme Procedure} coverage-data? obj @@ -43,7 +43,7 @@ Here's an example use: (system vm vm)) (call-with-values (lambda () - (with-code-coverage (the-vm) + (with-code-coverage (lambda () (do-something-tricky)))) (lambda (data result) diff --git a/doc/ref/api-data.texi b/doc/ref/api-data.texi index acdf9ca2b..96f9fd017 100644 --- a/doc/ref/api-data.texi +++ b/doc/ref/api-data.texi @@ -445,6 +445,8 @@ function will always succeed and will always return an exact number. @deftypefnx {C Function} scm_t_uint64 scm_to_uint64 (SCM x) @deftypefnx {C Function} scm_t_intmax scm_to_intmax (SCM x) @deftypefnx {C Function} scm_t_uintmax scm_to_uintmax (SCM x) +@deftypefnx {C Function} scm_t_intptr scm_to_intptr_t (SCM x) +@deftypefnx {C Function} scm_t_uintptr scm_to_uintptr_t (SCM x) When @var{x} represents an exact integer that fits into the indicated C type, return that integer. Else signal an error, either a `wrong-type' error when @var{x} is not an exact integer, or an @@ -479,6 +481,8 @@ the corresponding types are. @deftypefnx {C Function} SCM scm_from_uint64 (scm_t_uint64 x) @deftypefnx {C Function} SCM scm_from_intmax (scm_t_intmax x) @deftypefnx {C Function} SCM scm_from_uintmax (scm_t_uintmax x) +@deftypefnx {C Function} SCM scm_from_intptr_t (scm_t_intptr x) +@deftypefnx {C Function} SCM scm_from_uintptr_t (scm_t_uintptr x) Return the @code{SCM} value that represents the integer @var{x}. These functions will always succeed and will always return an exact number. @@ -4475,6 +4479,19 @@ returned is the number of bytes for @code{scm_to_latin1_stringn} and for @code{scm_to_utf32_stringn}. @end deftypefn +It is not often the case, but sometimes when you are dealing with the +implementation details of a port, you need to encode and decode strings +according to the encoding and conversion strategy of the port. There +are some convenience functions for that purpose as well. + +@deftypefn {C Function} SCM scm_from_port_string (const char *str, SCM port) +@deftypefnx {C Function} SCM scm_from_port_stringn (const char *str, size_t len, SCM port) +@deftypefnx {C Function} char* scm_to_port_string (SCM str, SCM port) +@deftypefnx {C Function} char* scm_to_port_stringn (SCM str, size_t *lenp, SCM port) +Like @code{scm_from_stringn} and friends, except they take their +encoding and conversion strategy from a given port object. +@end deftypefn + @node String Internals @subsubsection String Internals diff --git a/doc/ref/api-debug.texi b/doc/ref/api-debug.texi index 619629b56..9b0e56448 100644 --- a/doc/ref/api-debug.texi +++ b/doc/ref/api-debug.texi @@ -342,6 +342,7 @@ library, or from Guile itself. * Catching Exceptions:: Handling errors after the stack is unwound. * Capturing Stacks:: Capturing the stack at the time of error. * Pre-Unwind Debugging:: Debugging before the exception is thrown. +* Stack Overflow:: Detecting and handling runaway recursion. * Debug Options:: A historical interface to debugging. @end menu @@ -600,10 +601,12 @@ These procedures are available for use by user programs, in the @deffn {Scheme Procedure} call-with-error-handling thunk @ [#:on-error on-error='debug] [#:post-error post-error='catch] @ - [#:pass-keys pass-keys='(quit)] [#:trap-handler trap-handler='debug] + [#:pass-keys pass-keys='(quit)] @ + [#:report-keys report-keys='(stack-overflow)] @ + [#:trap-handler trap-handler='debug] Call a thunk in a context in which errors are handled. -There are four keyword arguments: +There are five keyword arguments: @table @var @item on-error @@ -630,9 +633,185 @@ traps entirely. @xref{Traps}, for more information. @item pass-keys A set of keys to ignore, as a list. + +@item report-keys +A set of keys to always report even if the post-error handler is +@code{catch}, as a list. @end table @end deffn +@node Stack Overflow +@subsubsection Stack Overflow + +@cindex overflow, stack +@cindex stack overflow +Every time a Scheme program makes a call that is not in tail position, +it pushes a new frame onto the stack. Returning a value from a function +pops the top frame off the stack. Stack frames take up memory, and as +nobody has an infinite amount of memory, deep recursion could cause +Guile to run out of memory. Running out of stack memory is called +@dfn{stack overflow}. + +@subsubheading Stack Limits + +Most languages have a terrible stack overflow story. For example, in C, +if you use too much stack, your program will exhibit ``undefined +behavior'', which if you are lucky means that it will crash. It's +especially bad in C, as you neither know ahead of time how much stack +your functions use, nor the stack limit imposed by the user's system, +and the stack limit is often quite small relative to the total memory +size. + +Managed languages like Python have a better error story, as they are +defined to raise an exception on stack overflow -- but like C, Python +and most dynamic languages still have a fixed stack size limit that is +usually much smaller than the heap. + +Arbitrary stack limits would have an unfortunate effect on Guile +programs. For example, the following implementation of the inner loop +of @code{map} is clean and elegant: + +@example +(define (map f l) + (if (pair? l) + (cons (f (car l)) + (map f (cdr l))) + '())) +@end example + +However, if there were a stack limit, that would limit the size of lists +that can be processed with this @code{map}. Eventually, you would have +to rewrite it to use iteration with an accumulator: + +@example +(define (map f l) + (let lp ((l l) (out '())) + (if (pair? l) + (lp (cdr l) (cons (f (car l)) out)) + (reverse out)))) +@end example + +This second version is sadly not as clear, and it also allocates more +heap memory (once to build the list in reverse, and then again to +reverse the list). You would be tempted to use the destructive +@code{reverse!} to save memory and time, but then your code would not be +continuation-safe -- if @var{f} returned again after the map had +finished, it would see an @var{out} list that had already been +reversed. The recursive @code{map} has none of these problems. + +Guile has no stack limit for Scheme code. When a thread makes its first +Guile call, a small stack is allocated -- just one page of memory. +Whenever that memory limit would be reached, Guile arranges to grow the +stack by a factor of two. When garbage collection happens, Guile +arranges to return the unused part of the stack to the operating system, +but without causing the stack to shrink. In this way, the stack can +grow to consume up to all memory available to the Guile process, and +when the recursive computation eventually finishes, that stack memory is +returned to the system. + +@subsubheading Exceptional Situations + +Of course, it's still possible to run out of stack memory. The most +common cause of this is program bugs that cause unbounded recursion, as +in: + +@example +(define (faulty-map f l) + (if (pair? l) + (cons (f (car l)) (faulty-map f l)) + '())) +@end example + +Did you spot the bug? The recursive call to @code{faulty-map} recursed +on @var{l}, not @code{(cdr @var{l})}. Running this program would cause +Guile to use up all memory in your system, and eventually Guile would +fail to grow the stack. At that point you have a problem: Guile needs +to raise an exception to unwind the stack and return memory to the +system, but the user might have throw handlers in place (@pxref{Throw +Handlers}) that want to run before the stack is unwound, and we don't +have any stack in which to run them. + +Therefore in this case, Guile throws an unwind-only exception that does +not run pre-unwind handlers. Because this is such an odd case, Guile +prints out a message on the console, in case the user was expecting to +be able to get a backtrace from any pre-unwind handler. + +@subsubheading Runaway Recursion + +Still, this failure mode is not so nice. If you are running an +environment in which you are interactively building a program while it +is running, such as at a REPL, you might want to impose an artificial +stack limit on the part of your program that you are building to detect +accidental runaway recursion. For that purpose, there is +@code{call-with-stack-overflow-handler}, from @code{(system vm vm)}. + +@example +(use-module (system vm vm)) +@end example + +@deffn {Scheme Procedure} call-with-stack-overflow-handler limit thunk handler +Call @var{thunk} in an environment in which the stack limit has been +reduced to @var{limit} additional words. If the limit is reached, +@var{handler} (a thunk) will be invoked in the dynamic environment of +the error. For the extent of the call to @var{handler}, the stack limit +and handler are restored to the values that were in place when +@code{call-with-stack-overflow-handler} was called. + +Usually, @var{handler} should raise an exception or abort to an outer +prompt. However if @var{handler} does return, it should return a number +of additional words of stack space to allow to the inner environment. +@end deffn + +A stack overflow handler may only ever ``credit'' the inner thunk with +stack space that was available when the handler was instated. When +Guile first starts, there is no stack limit in place, so the outer +handler may allow the inner thunk an arbitrary amount of space, but any +nested stack overflow handler will not be able to consume more than its +limit. + +Unlike the unwind-only exception that is thrown if Guile is unable to +grow its stack, any exception thrown by a stack overflow handler might +invoke pre-unwind handlers. Indeed, the stack overflow handler is +itself a pre-unwind handler of sorts. If the code imposing the stack +limit wants to protect itself against malicious pre-unwind handlers from +the inner thunk, it should abort to a prompt of its own making instead +of throwing an exception that might be caught by the inner thunk. + +@subsubheading C Stack Usage + +It is also possible for Guile to run out of space on the C stack. If +you call a primitive procedure which then calls a Scheme procedure in a +loop, you will consume C stack space. Guile tries to detect excessive +consumption of C stack space, throwing an error when you have hit 80% of +the process' available stack (as allocated by the operating system), or +160 kilowords in the absence of a strict limit. + +For example, looping through @code{call-with-vm}, a primitive that calls +a thunk, gives us the following: + +@lisp +scheme@@(guile-user)> (use-modules (system vm vm)) +scheme@@(guile-user)> (let lp () (call-with-vm lp)) +ERROR: Stack overflow +@end lisp + +Unfortunately, that's all the information we get. Overrunning the C +stack will throw an unwind-only exception, because it's not safe to +do very much when you are close to the C stack limit. + +If you get an error like this, you can either try rewriting your code to +use less stack space, or increase the maximum stack size. To increase +the maximum stack size, use @code{debug-set!}, for example: + +@lisp +(debug-set! stack 200000) +@end lisp + +The next section describes @code{debug-set!} more thoroughly. Of course +the best thing is to have your code operate without so much resource +consumption by avoiding loops through C trampolines. + + @node Debug Options @subsubsection Debug options @@ -666,8 +845,8 @@ warn-deprecated no Warn when deprecated features are used. @end smallexample The boolean options may be toggled with @code{debug-enable} and -@code{debug-disable}. The non-boolean @code{keywords} option must be set -using @code{debug-set!}. +@code{debug-disable}. The non-boolean options must be set using +@code{debug-set!}. @deffn {Scheme Procedure} debug-enable option-name @deffnx {Scheme Procedure} debug-disable option-name @@ -680,59 +859,6 @@ to historical oddities, it is a macro that expects an unquoted option name. @end deffn -@subsubheading Stack overflow - -@cindex overflow, stack -@cindex stack overflow -Stack overflow errors are caused by a computation trying to use more -stack space than has been enabled by the @code{stack} option. There are -actually two kinds of stack that can overflow, the C stack and the -Scheme stack. - -Scheme stack overflows can occur if Scheme procedures recurse too far -deeply. An example would be the following recursive loop: - -@lisp -scheme@@(guile-user)> (let lp () (+ 1 (lp))) -<unnamed port>:8:17: In procedure vm-run: -<unnamed port>:8:17: VM: Stack overflow -@end lisp - -The default stack size should allow for about 10000 frames or so, so one -usually doesn't hit this level of recursion. Unfortunately there is no -way currently to make a VM with a bigger stack. If you are in this -unfortunate situation, please file a bug, and in the meantime, rewrite -your code to be tail-recursive (@pxref{Tail Calls}). - -The other limit you might hit would be C stack overflows. If you call a -primitive procedure which then calls a Scheme procedure in a loop, you -will consume C stack space. Guile tries to detect excessive consumption -of C stack space, throwing an error when you have hit 80% of the -process' available stack (as allocated by the operating system), or 160 -kilowords in the absence of a strict limit. - -For example, looping through @code{call-with-vm}, a primitive that calls -a thunk, gives us the following: - -@lisp -scheme@@(guile-user)> (use-modules (system vm vm)) -scheme@@(guile-user)> (debug-set! stack 10000) -scheme@@(guile-user)> (let lp () (call-with-vm (the-vm) lp)) -ERROR: In procedure call-with-vm: -ERROR: Stack overflow -@end lisp - -If you get an error like this, you can either try rewriting your code to -use less stack space, or increase the maximum stack size. To increase -the maximum stack size, use @code{debug-set!}, for example: - -@lisp -(debug-set! stack 200000) -@end lisp - -But of course it's better to have your code operate without so much -resource consumption, avoiding loops through C trampolines. - @node Traps @subsection Traps @@ -800,10 +926,11 @@ To digress, Guile's VM has 6 different hooks (@pxref{Hooks}) that can be fired at different times, which may be accessed with the following procedures. -All hooks are called with one argument, the frame in -question. @xref{Frames}. Since these hooks may be fired very -frequently, Guile does a terrible thing: it allocates the frames on the -C stack instead of the garbage-collected heap. +The first argument of calls to these hooks is the frame in question. +@xref{Frames}. Some hooks may call their procedures with more +arguments. Since these hooks may be fired very frequently, Guile does a +terrible thing: it allocates the frames on the C stack instead of the +garbage-collected heap. The upshot here is that the frames are only valid within the dynamic extent of the call to the hook. If a hook procedure keeps a reference to @@ -816,31 +943,28 @@ The interface to hooks is provided by the @code{(system vm vm)} module: @end example @noindent -The result of calling @code{the-vm} is usually passed as the @var{vm} -argument to all of these procedures. +All of these functions implicitly act on the VM for the current thread +only. -@deffn {Scheme Procedure} vm-next-hook vm +@deffn {Scheme Procedure} vm-next-hook The hook that will be fired before an instruction is retired (and executed). @end deffn -@deffn {Scheme Procedure} vm-push-continuation-hook vm +@deffn {Scheme Procedure} vm-push-continuation-hook The hook that will be fired after preparing a new frame. Fires just before applying a procedure in a non-tail context, just before the corresponding apply-hook. @end deffn -@deffn {Scheme Procedure} vm-pop-continuation-hook vm +@deffn {Scheme Procedure} vm-pop-continuation-hook The hook that will be fired before returning from a frame. -This hook is a bit trickier than the rest, in that there is a particular -interpretation of the values on the stack. Specifically, the top value -on the stack is the number of values being returned, and the next -@var{n} values are the actual values being returned, with the last value -highest on the stack. +This hook fires with a variable number of arguments, corresponding to +the values that the frame returns to its continuation. @end deffn -@deffn {Scheme Procedure} vm-apply-hook vm +@deffn {Scheme Procedure} vm-apply-hook The hook that will be fired before a procedure is applied. The frame's procedure will have already been set to the new procedure. @@ -851,13 +975,16 @@ whereas a tail call will run without having fired a push-continuation hook. @end deffn -@deffn {Scheme Procedure} vm-abort-continuation-hook vm +@deffn {Scheme Procedure} vm-abort-continuation-hook The hook that will be called after aborting to a -prompt. @xref{Prompts}. The stack will be in the same state as for -@code{vm-pop-continuation-hook}. +prompt. @xref{Prompts}. + +Like the pop-continuation hook, this hook fires with a variable number +of arguments, corresponding to the values that returned to the +continuation. @end deffn -@deffn {Scheme Procedure} vm-restore-continuation-hook vm +@deffn {Scheme Procedure} vm-restore-continuation-hook The hook that will be called after restoring an undelimited continuation. Unfortunately it's not currently possible to introspect on the values that were given to the continuation. @@ -875,12 +1002,12 @@ level temporarily set to 0. That way the hooks don't fire while you're handling a hook. The trace level is restored to whatever it was once the hook procedure finishes. -@deffn {Scheme Procedure} vm-trace-level vm +@deffn {Scheme Procedure} vm-trace-level Retrieve the ``trace level'' of the VM. If positive, the trace hooks associated with @var{vm} will be run. The initial trace level is 0. @end deffn -@deffn {Scheme Procedure} set-vm-trace-level! vm level +@deffn {Scheme Procedure} set-vm-trace-level! level Set the ``trace level'' of the VM. @end deffn @@ -1178,7 +1305,7 @@ procedure calls and returns within the thunk. @deffn {Scheme Procedure} call-with-trace thunk [#:calls?=#t] @ [#:instructions?=#f] @ - [#:width=80] [#:vm=(the-vm)] + [#:width=80] Call @var{thunk}, tracing all execution within its dynamic extent. If @var{calls?} is true, Guile will print a brief report at each diff --git a/doc/ref/api-evaluation.texi b/doc/ref/api-evaluation.texi index c441dffee..a23cf1ae4 100644 --- a/doc/ref/api-evaluation.texi +++ b/doc/ref/api-evaluation.texi @@ -580,18 +580,6 @@ Call @var{proc} with the array of arguments @var{argv}, as a @var{nargs}, as a @code{size_t}. @end deffn -@deffn {Scheme Procedure} apply:nconc2last lst -@deffnx {C Function} scm_nconc2last (lst) -@var{lst} should be a list (@var{arg1} @dots{} @var{argN} -@var{arglst}), with @var{arglst} being a list. This function returns -a list comprising @var{arg1} to @var{argN} plus the elements of -@var{arglst}. @var{lst} is modified to form the return. @var{arglst} -is not modified, though the return does share structure with it. - -This operation collects up the arguments from a list which is -@code{apply} style parameters. -@end deffn - @deffn {Scheme Procedure} primitive-eval exp @deffnx {C Function} scm_primitive_eval (exp) Evaluate @var{exp} in the top-level environment specified by @@ -683,13 +671,13 @@ Use @var{lang} as the source language of @var{file}. If this option is omitted, @item -t @var{lang} @itemx --to=@var{lang} Use @var{lang} as the target language of @var{file}. If this option is omitted, -@code{objcode} is assumed. +@code{rtl} is assumed. @item -T @var{target} @itemx --target=@var{target} -Produce bytecode for @var{target} instead of @var{%host-type} -(@pxref{Build Config, %host-type}). Target must be a valid GNU triplet, -such as @code{armv5tel-unknown-linux-gnueabi} (@pxref{Specifying Target +Produce code for @var{target} instead of @var{%host-type} (@pxref{Build +Config, %host-type}). Target must be a valid GNU triplet, such as +@code{armv5tel-unknown-linux-gnueabi} (@pxref{Specifying Target Triplets,,, autoconf, GNU Autoconf Manual}). @end table @@ -714,7 +702,7 @@ the Virtual Machine}. @end deffn @deffn {Scheme Procedure} compile-file file [#:output-file=#f] @ - [#:from=(current-language)] [#:to='objcode] @ + [#:from=(current-language)] [#:to='rtl] @ [#:env=(default-environment from)] @ [#:opts='()] @ [#:canonicalization='relative] @@ -943,8 +931,8 @@ When @code{primitive-load-path} searches the @code{%load-compiled-path} for a corresponding compiled file for a relative path it does so by appending @code{.go} to the relative path. For example, searching for @code{ice-9/popen} could find -@code{/usr/lib/guile/2.0/ccache/ice-9/popen.go}, and use it instead of -@code{/usr/share/guile/2.0/ice-9/popen.scm}. +@code{/usr/lib/guile/2.2/ccache/ice-9/popen.go}, and use it instead of +@code{/usr/share/guile/2.2/ice-9/popen.scm}. If @code{primitive-load-path} does not find a corresponding @code{.go} file in the @code{%load-compiled-path}, or the @code{.go} file is out of @@ -1186,7 +1174,7 @@ it contains, splicing them into the location of the @code{include}, within a @code{begin}. If @var{file-name} is a relative path, it is searched for relative to -the path that contains the file that the @code{include} for appears in. +the path that contains the file that the @code{include} form appears in. @end deffn If you are a C programmer, if @code{load} in Scheme is like diff --git a/doc/ref/api-io.texi b/doc/ref/api-io.texi index 02d92a2d7..8b44224dc 100644 --- a/doc/ref/api-io.texi +++ b/doc/ref/api-io.texi @@ -1066,28 +1066,6 @@ away from its default. Calls the one-argument procedure @var{proc} with a newly created output port. When the function returns, the string composed of the characters written into the port is returned. @var{proc} should not close the port. - -Note that which characters can be written to a string port depend on the port's -encoding. The default encoding of string ports is specified by the -@code{%default-port-encoding} fluid (@pxref{Ports, -@code{%default-port-encoding}}). For instance, it is an error to write Greek -letter alpha to an ISO-8859-1-encoded string port since this character cannot be -represented with ISO-8859-1: - -@example -(define alpha (integer->char #x03b1)) ; GREEK SMALL LETTER ALPHA - -(with-fluids ((%default-port-encoding "ISO-8859-1")) - (call-with-output-string - (lambda (p) - (display alpha p)))) - -@result{} -Throw to key `encoding-error' -@end example - -Changing the string port's encoding to a Unicode-capable encoding such as UTF-8 -solves the problem. @end deffn @deffn {Scheme Procedure} call-with-input-string string proc @@ -1101,8 +1079,6 @@ read. The value yielded by the @var{proc} is returned. Calls the zero-argument procedure @var{thunk} with the current output port set temporarily to a new string port. It returns a string composed of the characters written to the current output. - -See @code{call-with-output-string} above for character encoding considerations. @end deffn @deffn {Scheme Procedure} with-input-from-string string thunk diff --git a/doc/ref/api-macros.texi b/doc/ref/api-macros.texi index c2910a44e..9964e6b06 100644 --- a/doc/ref/api-macros.texi +++ b/doc/ref/api-macros.texi @@ -43,6 +43,8 @@ languages}, or EDSLs.}. * Identifier Macros:: Identifier macros. * Syntax Parameters:: Syntax Parameters. * Eval When:: Affecting the expand-time environment. +* Macro Expansion:: Procedurally expanding macros. +* Hygiene and the Top-Level:: A hack you might want to know about. * Internal Macros:: Macros as first-class values. @end menu @@ -806,7 +808,7 @@ Return the name of the module whose source contains the identifier @var{id}. @end deffn -@deffn {Scheme Procedure} syntax-local-binding id +@deffn {Scheme Procedure} syntax-local-binding id [#:resolve-syntax-parameters?=#t] Resolve the identifer @var{id}, a syntax object, within the current lexical environment, and return two values, the binding type and a binding value. The binding type is a symbol, which may be one of the @@ -819,6 +821,12 @@ of @code{eq?}) identifying this binding. @item macro A syntax transformer, either local or global. The value is the transformer procedure. +@item syntax-parameter +A syntax parameter (@pxref{Syntax Parameters}). By default, +@code{syntax-local-binding} will resolve syntax parameters, so that this +value will not be returned. Pass @code{#:resolve-syntax-parameters? #f} +to indicate that you are interested in syntax parameters. The value is +the default transformer procedure, as in @code{macro}. @item pattern-variable A pattern variable, bound via @code{syntax-case}. The value is an opaque object, internal to the expander. @@ -1224,6 +1232,174 @@ the example above. Other uses of @code{eval-when} may void your warranty or poison your cat. @end deffn +@node Macro Expansion +@subsection Macro Expansion + +Usually, macros are expanded on behalf of the user as needed. Macro +expansion is an integral part of @code{eval} and @code{compile}. Users +can also expand macros at the REPL prompt via the @code{expand} REPL +command; @xref{Compile Commands}. + +Macros can also be expanded programmatically, via @code{macroexpand}, +but the details get a bit hairy for two reasons. + +The first complication is that the result of macro-expansion isn't +Scheme: it's Tree-IL, Guile's high-level intermediate language. +@xref{Tree-IL}. As ``hygienic macros'' can produce identifiers that are +distinct but have the same name, the output format needs to be able to +represent distinctions between variable identities and names. Again, +@xref{Tree-IL}, for all the details. The easiest thing is to just run +@code{tree-il->scheme} on the result of macro-expansion: + +@lisp +(macroexpand '(+ 1 2)) +@result{} +#<tree-il (call (toplevel +) (const 1) (const 2))> + +(use-modules (language tree-il)) +(tree-il->scheme (macroexpand '(+ 1 2))) +@result{} +(+ 1 2) +@end lisp + +The second complication involves @code{eval-when}. As an example, what +would it mean to macro-expand the definition of a macro? + +@lisp +(macroexpand '(define-syntax qux (identifier-syntax 'bar))) +@result{} +? +@end lisp + +The answer is that it depends who is macro-expanding, and why. Do you +define the macro in the current environment? Residualize a macro +definition? Both? Neither? The default is to expand in ``eval'' mode, +which means an @code{eval-when} clauses will only proceed when +@code{eval} (or @code{expand}) is in its condition set. Top-level +macros will be @code{eval}'d in the top-level environment. + +In this way @code{(macroexpand @var{foo})} is equivalent to +@code{(macroexpand @var{foo} 'e '(eval))}. The second argument is the +mode (@code{'e} for ``eval'') and the second is the +eval-syntax-expanders-when parameter (only @code{eval} in this default +setting). + +But if you are compiling the macro definition, probably you want to +reify the macro definition itself. In that case you pass @code{'c} as +the second argument to @code{macroexpand}. But probably you want the +macro definition to be present at compile time as well, so you pass +@code{'(compile load eval)} as the @var{esew} parameter. In fact +@code{(compile @var{foo} #:to 'tree-il)} is entirely equivalent to +@code{(macroexpand @var{foo} 'c '(compile load eval))}; @xref{The Scheme +Compiler}. + +It's a terrible interface; we know. The macroexpander is somewhat +tricksy regarding modes, so unless you are building a macro-expanding +tool, we suggest to avoid invoking it directly. + + +@node Hygiene and the Top-Level +@subsection Hygiene and the Top-Level + +Consider the following macro. + +@lisp +(define-syntax-rule (defconst name val) + (begin + (define t val) + (define-syntax-rule (name) t))) +@end lisp + +If we use it to make a couple of bindings: + +@lisp +(defconst foo 42) +(defconst bar 37) +@end lisp + +The expansion would look something like this: + +@lisp +(begin + (define t 42) + (define-syntax-rule (foo) t)) +(begin + (define t 37) + (define-syntax-rule (bar) t)) +@end lisp + +As the two @code{t} bindings were introduced by the macro, they should +be introduced hygienically -- and indeed they are, inside a lexical +contour (a @code{let} or some other lexical scope). The @code{t} +reference in @code{foo} is distinct to the reference in @code{bar}. + +At the top-level things are more complicated. Before Guile 2.2, a use +of @code{defconst} at the top-level would not introduce a fresh binding +for @code{t}. This was consistent with a weaselly interpretation of the +Scheme standard, in which all possible bindings may be assumed to exist, +at the top-level, and in which we merely take advantage of toplevel +@code{define} of an existing binding being equivalent to @code{set!}. +But it's not a good reason. + +The solution is to create fresh names for all bindings introduced by +macros -- not just bindings in lexical contours, but also bindings +introduced at the top-level. + +However, the obvious strategy of just giving random names to introduced +toplevel identifiers poses a problem for separate compilation. Consider +without loss of generality a @code{defconst} of @code{foo} in module +@code{a} that introduces the fresh top-level name @code{t-1}. If we +then compile a module @code{b} that uses @code{foo}, there is now a +reference to @code{t-1} in module @code{b}. If module @code{a} is then +expanded again, for whatever reason, for example in a simple +recompilation, the introduced @code{t} gets a fresh name; say, +@code{t-2}. Now module @code{b} has broken because module @code{a} no +longer has a binding for @code{t-1}. + +If introduced top-level identifiers ``escape'' a module, in whatever +way, they then form part of the binary interface (ABI) of a module. It +is unacceptable from an engineering point of view to allow the ABI to +change randomly. (It also poses practical problems in meeting the +recompilation conditions of the Lesser GPL license, for such modules.) +For this reason many people prefer to never use identifier-introducing +macros at the top-level, instead making those macros receive the names +for their introduced identifiers as part of their arguments, or to +construct them programmatically and use @code{datum->syntax}. But this +approach requires omniscience as to the implementation of all macros one +might use, and also limits the expressive power of Scheme macros. + +There is no perfect solution to this issue. Guile does a terrible thing +here. When it goes to introduce a top-level identifier, Guile gives the +identifier a pseudo-fresh name: a name that depends on the hash of the +source expression in which the name occurs. The result in this case is +that the introduced definitions expand as: + +@lisp +(begin + (define t-1dc5e42de7c1050c 42) + (define-syntax-rule (foo) t-1dc5e42de7c1050c)) +(begin + (define t-10cb8ce9fdddd6e9 37) + (define-syntax-rule (bar) t-10cb8ce9fdddd6e9)) +@end lisp + +However, note that as the hash depends solely on the expression +introducing the definition, we also have: + +@lisp +(defconst baz 42) +@result{} (begin + (define t-1dc5e42de7c1050c 42) + (define-syntax-rule (baz) t-1dc5e42de7c1050c)) +@end lisp + +Note that the introduced binding has the same name! This is because the +source expression, @code{(define t 42)}, was the same. Probably you +will never see an error in this area, but it is important to understand +the components of the interface of a module, and that interface may +include macro-introduced identifiers. + + @node Internal Macros @subsection Internal Macros diff --git a/doc/ref/api-memory.texi b/doc/ref/api-memory.texi index 099d80678..0e37d16fc 100644 --- a/doc/ref/api-memory.texi +++ b/doc/ref/api-memory.texi @@ -1,6 +1,6 @@ @c -*-texinfo-*- @c This is part of the GNU Guile Reference Manual. -@c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2009, 2010, 2012, 2014 +@c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2009, 2010, 2012, 2013, 2014 @c Free Software Foundation, Inc. @c See the file guile.texi for copying conditions. diff --git a/doc/ref/api-options.texi b/doc/ref/api-options.texi index 8fa4f98a5..b09ae8952 100644 --- a/doc/ref/api-options.texi +++ b/doc/ref/api-options.texi @@ -60,14 +60,14 @@ The @code{effective-version} function returns the version name that should remain unchanged during a stable series. Currently that means that it omits the micro version. The effective version should be used for items like the versioned share directory name -i.e.@: @file{/usr/share/guile/2.0/} +i.e.@: @file{/usr/share/guile/2.2/} @lisp -(version) @result{} "2.0.4" -(effective-version) @result{} "2.0" +(version) @result{} "2.2.0" +(effective-version) @result{} "2.2" (major-version) @result{} "2" -(minor-version) @result{} "0" -(micro-version) @result{} "4" +(minor-version) @result{} "2" +(micro-version) @result{} "0" @end lisp @end deffn @@ -87,7 +87,7 @@ party package) are installed. On Unix-like systems this is usually @file{/usr/share/guile/@var{GUILE_EFFECTIVE_VERSION}}; @noindent -for example @file{/usr/local/share/guile/2.0}. +for example @file{/usr/local/share/guile/2.2}. @end deffn @deffn {Scheme Procedure} %site-dir diff --git a/doc/ref/api-peg.texi b/doc/ref/api-peg.texi new file mode 100644 index 000000000..0e16aab7e --- /dev/null +++ b/doc/ref/api-peg.texi @@ -0,0 +1,1036 @@ +@c -*-texinfo-*- +@c This is part of the GNU Guile Reference Manual. +@c Copyright (C) 2006, 2010, 2011 +@c Free Software Foundation, Inc. +@c See the file guile.texi for copying conditions. + +@node PEG Parsing +@section PEG Parsing + +Parsing Expression Grammars (PEGs) are a way of specifying formal +languages for text processing. They can be used either for matching +(like regular expressions) or for building recursive descent parsers +(like lex/yacc). Guile uses a superset of PEG syntax that allows more +control over what information is preserved during parsing. + +Wikipedia has a clear and concise introduction to PEGs if you want to +familiarize yourself with the syntax: +@url{http://en.wikipedia.org/wiki/Parsing_expression_grammar}. + +The module works by compiling PEGs down to lambda expressions. These +can either be stored in variables at compile-time by the define macros +(@code{define-peg-pattern} and @code{define-peg-string-patterns}) or calculated +explicitly at runtime with the compile functions +(@code{compile-peg-pattern} and @code{peg-string-compile}). + +They can then be used for either parsing (@code{match-pattern}) or searching +(@code{search-for-pattern}). For convenience, @code{search-for-pattern} +also takes pattern literals in case you want to inline a simple search +(people often use regular expressions this way). + +The rest of this documentation consists of a syntax reference, an API +reference, and a tutorial. + +@menu +* PEG Syntax Reference:: +* PEG API Reference:: +* PEG Tutorial:: +* PEG Internals:: +@end menu + +@node PEG Syntax Reference +@subsection PEG Syntax Reference + +@subsubheading Normal PEG Syntax: + +@deftp {PEG Pattern} sequence a b +Parses @var{a}. If this succeeds, continues to parse @var{b} from the +end of the text parsed as @var{a}. Succeeds if both @var{a} and +@var{b} succeed. + +@code{"a b"} + +@code{(and a b)} +@end deftp + +@deftp {PEG Pattern} {ordered choice} a b +Parses @var{a}. If this fails, backtracks and parses @var{b}. +Succeeds if either @var{a} or @var{b} succeeds. + +@code{"a/b"} + +@code{(or a b)} +@end deftp + +@deftp {PEG Pattern} {zero or more} a +Parses @var{a} as many times in a row as it can, starting each @var{a} +at the end of the text parsed by the previous @var{a}. Always +succeeds. + +@code{"a*"} + +@code{(* a)} +@end deftp + +@deftp {PEG Pattern} {one or more} a +Parses @var{a} as many times in a row as it can, starting each @var{a} +at the end of the text parsed by the previous @var{a}. Succeeds if at +least one @var{a} was parsed. + +@code{"a+"} + +@code{(+ a)} +@end deftp + +@deftp {PEG Pattern} optional a +Tries to parse @var{a}. Succeeds if @var{a} succeeds. + +@code{"a?"} + +@code{(? a)} +@end deftp + +@deftp {PEG Pattern} {followed by} a +Makes sure it is possible to parse @var{a}, but does not actually parse +it. Succeeds if @var{a} would succeed. + +@code{"&a"} + +@code{(followed-by a)} +@end deftp + +@deftp {PEG Pattern} {not followed by} a +Makes sure it is impossible to parse @var{a}, but does not actually +parse it. Succeeds if @var{a} would fail. + +@code{"!a"} + +@code{(not-followed-by a)} +@end deftp + +@deftp {PEG Pattern} {string literal} ``abc'' +Parses the string @var{"abc"}. Succeeds if that parsing succeeds. + +@code{"'abc'"} + +@code{"abc"} +@end deftp + +@deftp {PEG Pattern} {any character} +Parses any single character. Succeeds unless there is no more text to +be parsed. + +@code{"."} + +@code{peg-any} +@end deftp + +@deftp {PEG Pattern} {character class} a b +Alternative syntax for ``Ordered Choice @var{a} @var{b}'' if @var{a} and +@var{b} are characters. + +@code{"[ab]"} + +@code{(or "a" "b")} +@end deftp + +@deftp {PEG Pattern} {range of characters} a z +Parses any character falling between @var{a} and @var{z}. + +@code{"[a-z]"} + +@code{(range #\a #\z)} +@end deftp + +Example: + +@example +"(a !b / c &d*) 'e'+" +@end example + +Would be: + +@lisp +(and + (or + (and a (not-followed-by b)) + (and c (followed-by (* d)))) + (+ "e")) +@end lisp + +@subsubheading Extended Syntax + +There is some extra syntax for S-expressions. + +@deftp {PEG Pattern} ignore a +Ignore the text matching @var{a} +@end deftp + +@deftp {PEG Pattern} capture a +Capture the text matching @var{a}. +@end deftp + +@deftp {PEG Pattern} peg a +Embed the PEG pattern @var{a} using string syntax. +@end deftp + +Example: + +@example +"!a / 'b'" +@end example + +Is equivalent to + +@lisp +(or (peg "!a") "b") +@end lisp + +and + +@lisp +(or (not-followed-by a) "b") +@end lisp + +@node PEG API Reference +@subsection PEG API Reference + +@subsubheading Define Macros + +The most straightforward way to define a PEG is by using one of the +define macros (both of these macroexpand into @code{define} +expressions). These macros bind parsing functions to variables. These +parsing functions may be invoked by @code{match-pattern} or +@code{search-for-pattern}, which return a PEG match record. Raw data can be +retrieved from this record with the PEG match deconstructor functions. +More complicated (and perhaps enlightening) examples can be found in the +tutorial. + +@deffn {Scheme Macro} define-peg-string-patterns peg-string +Defines all the nonterminals in the PEG @var{peg-string}. More +precisely, @code{define-peg-string-patterns} takes a superset of PEGs. A normal PEG +has a @code{<-} between the nonterminal and the pattern. +@code{define-peg-string-patterns} uses this symbol to determine what information it +should propagate up the parse tree. The normal @code{<-} propagates the +matched text up the parse tree, @code{<--} propagates the matched text +up the parse tree tagged with the name of the nonterminal, and @code{<} +discards that matched text and propagates nothing up the parse tree. +Also, nonterminals may consist of any alphanumeric character or a ``-'' +character (in normal PEGs nonterminals can only be alphabetic). + +For example, if we: +@lisp +(define-peg-string-patterns + "as <- 'a'+ +bs <- 'b'+ +as-or-bs <- as/bs") +(define-peg-string-patterns + "as-tag <-- 'a'+ +bs-tag <-- 'b'+ +as-or-bs-tag <-- as-tag/bs-tag") +@end lisp +Then: +@lisp +(match-pattern as-or-bs "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> +(match-pattern as-or-bs-tag "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: (as-or-bs-tag (as-tag aa))> +@end lisp + +Note that in doing this, we have bound 6 variables at the toplevel +(@var{as}, @var{bs}, @var{as-or-bs}, @var{as-tag}, @var{bs-tag}, and +@var{as-or-bs-tag}). +@end deffn + +@deffn {Scheme Macro} define-peg-pattern name capture-type peg-sexp +Defines a single nonterminal @var{name}. @var{capture-type} determines +how much information is passed up the parse tree. @var{peg-sexp} is a +PEG in S-expression form. + +Possible values for capture-type: + +@table @code +@item all +passes the matched text up the parse tree tagged with the name of the +nonterminal. +@item body +passes the matched text up the parse tree. +@item none +passes nothing up the parse tree. +@end table + +For Example, if we: +@lisp +(define-peg-pattern as body (+ "a")) +(define-peg-pattern bs body (+ "b")) +(define-peg-pattern as-or-bs body (or as bs)) +(define-peg-pattern as-tag all (+ "a")) +(define-peg-pattern bs-tag all (+ "b")) +(define-peg-pattern as-or-bs-tag all (or as-tag bs-tag)) +@end lisp +Then: +@lisp +(match-pattern as-or-bs "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> +(match-pattern as-or-bs-tag "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: (as-or-bs-tag (as-tag aa))> +@end lisp + +Note that in doing this, we have bound 6 variables at the toplevel +(@var{as}, @var{bs}, @var{as-or-bs}, @var{as-tag}, @var{bs-tag}, and +@var{as-or-bs-tag}). +@end deffn + +@subsubheading Compile Functions +It is sometimes useful to be able to compile anonymous PEG patterns at +runtime. These functions let you do that using either syntax. + +@deffn {Scheme Procedure} peg-string-compile peg-string capture-type +Compiles the PEG pattern in @var{peg-string} propagating according to +@var{capture-type} (capture-type can be any of the values from +@code{define-peg-pattern}). +@end deffn + + +@deffn {Scheme Procedure} compile-peg-pattern peg-sexp capture-type +Compiles the PEG pattern in @var{peg-sexp} propagating according to +@var{capture-type} (capture-type can be any of the values from +@code{define-peg-pattern}). +@end deffn + +The functions return syntax objects, which can be useful if you want to +use them in macros. If all you want is to define a new nonterminal, you +can do the following: + +@lisp +(define exp '(+ "a")) +(define as (compile (compile-peg-pattern exp 'body))) +@end lisp + +You can use this nonterminal with all of the regular PEG functions: + +@lisp +(match-pattern as "aaaaa") @result{} +#<peg start: 0 end: 5 string: bbbbb tree: bbbbb> +@end lisp + +@subsubheading Parsing & Matching Functions + +For our purposes, ``parsing'' means parsing a string into a tree +starting from the first character, while ``matching'' means searching +through the string for a substring. In practice, the only difference +between the two functions is that @code{match-pattern} gives up if it can't +find a valid substring starting at index 0 and @code{search-for-pattern} keeps +looking. They are both equally capable of ``parsing'' and ``matching'' +given those constraints. + +@deffn {Scheme Procedure} match-pattern nonterm string +Parses @var{string} using the PEG stored in @var{nonterm}. If no match +was found, @code{match-pattern} returns false. If a match was found, a PEG +match record is returned. + +The @code{capture-type} argument to @code{define-peg-pattern} allows you to +choose what information to hold on to while parsing. The options are: + +@table @code +@item all +tag the matched text with the nonterminal +@item body +just the matched text +@item none +nothing +@end table + +@lisp +(define-peg-pattern as all (+ "a")) +(match-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: (as aa)> + +(define-peg-pattern as body (+ "a")) +(match-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> + +(define-peg-pattern as none (+ "a")) +(match-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: ()> + +(define-peg-pattern bs body (+ "b")) +(match-pattern bs "aabbcc") @result{} +#f +@end lisp +@end deffn + +@deffn {Scheme Macro} search-for-pattern nonterm-or-peg string +Searches through @var{string} looking for a matching subexpression. +@var{nonterm-or-peg} can either be a nonterminal or a literal PEG +pattern. When a literal PEG pattern is provided, @code{search-for-pattern} works +very similarly to the regular expression searches many hackers are used +to. If no match was found, @code{search-for-pattern} returns false. If a match +was found, a PEG match record is returned. + +@lisp +(define-peg-pattern as body (+ "a")) +(search-for-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> +(search-for-pattern (+ "a") "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> +(search-for-pattern "'a'+" "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> + +(define-peg-pattern as all (+ "a")) +(search-for-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: (as aa)> + +(define-peg-pattern bs body (+ "b")) +(search-for-pattern bs "aabbcc") @result{} +#<peg start: 2 end: 4 string: aabbcc tree: bb> +(search-for-pattern (+ "b") "aabbcc") @result{} +#<peg start: 2 end: 4 string: aabbcc tree: bb> +(search-for-pattern "'b'+" "aabbcc") @result{} +#<peg start: 2 end: 4 string: aabbcc tree: bb> + +(define-peg-pattern zs body (+ "z")) +(search-for-pattern zs "aabbcc") @result{} +#f +(search-for-pattern (+ "z") "aabbcc") @result{} +#f +(search-for-pattern "'z'+" "aabbcc") @result{} +#f +@end lisp +@end deffn + +@subsubheading PEG Match Records +The @code{match-pattern} and @code{search-for-pattern} functions both return PEG +match records. Actual information can be extracted from these with the +following functions. + +@deffn {Scheme Procedure} peg:string match-record +Returns the original string that was parsed in the creation of +@code{match-record}. +@end deffn + +@deffn {Scheme Procedure} peg:start match-record +Returns the index of the first parsed character in the original string +(from @code{peg:string}). If this is the same as @code{peg:end}, +nothing was parsed. +@end deffn + +@deffn {Scheme Procedure} peg:end match-record +Returns one more than the index of the last parsed character in the +original string (from @code{peg:string}). If this is the same as +@code{peg:start}, nothing was parsed. +@end deffn + +@deffn {Scheme Procedure} peg:substring match-record +Returns the substring parsed by @code{match-record}. This is equivalent to +@code{(substring (peg:string match-record) (peg:start match-record) (peg:end +match-record))}. +@end deffn + +@deffn {Scheme Procedure} peg:tree match-record +Returns the tree parsed by @code{match-record}. +@end deffn + +@deffn {Scheme Procedure} peg-record? match-record +Returns true if @code{match-record} is a PEG match record, or false +otherwise. +@end deffn + +Example: +@lisp +(define-peg-pattern bs all (peg "'b'+")) + +(search-for-pattern bs "aabbcc") @result{} +#<peg start: 2 end: 4 string: aabbcc tree: (bs bb)> + +(let ((pm (search-for-pattern bs "aabbcc"))) + `((string ,(peg:string pm)) + (start ,(peg:start pm)) + (end ,(peg:end pm)) + (substring ,(peg:substring pm)) + (tree ,(peg:tree pm)) + (record? ,(peg-record? pm)))) @result{} +((string "aabbcc") + (start 2) + (end 4) + (substring "bb") + (tree (bs "bb")) + (record? #t)) +@end lisp + +@subsubheading Miscellaneous + +@deffn {Scheme Procedure} context-flatten tst lst +Takes a predicate @var{tst} and a list @var{lst}. Flattens @var{lst} +until all elements are either atoms or satisfy @var{tst}. If @var{lst} +itself satisfies @var{tst}, @code{(list lst)} is returned (this is a +flat list whose only element satisfies @var{tst}). + +@lisp +(context-flatten (lambda (x) (and (number? (car x)) (= (car x) 1))) '(2 2 (1 1 (2 2)) (2 2 (1 1)))) @result{} +(2 2 (1 1 (2 2)) 2 2 (1 1)) +(context-flatten (lambda (x) (and (number? (car x)) (= (car x) 1))) '(1 1 (1 1 (2 2)) (2 2 (1 1)))) @result{} +((1 1 (1 1 (2 2)) (2 2 (1 1)))) +@end lisp + +If you're wondering why this is here, take a look at the tutorial. +@end deffn + +@deffn {Scheme Procedure} keyword-flatten terms lst +A less general form of @code{context-flatten}. Takes a list of terminal +atoms @code{terms} and flattens @var{lst} until all elements are either +atoms, or lists which have an atom from @code{terms} as their first +element. +@lisp +(keyword-flatten '(a b) '(c a b (a c) (b c) (c (b a) (c a)))) @result{} +(c a b (a c) (b c) c (b a) c a) +@end lisp + +If you're wondering why this is here, take a look at the tutorial. +@end deffn + +@node PEG Tutorial +@subsection PEG Tutorial + +@subsubheading Parsing /etc/passwd +This example will show how to parse /etc/passwd using PEGs. + +First we define an example /etc/passwd file: + +@lisp +(define *etc-passwd* + "root:x:0:0:root:/root:/bin/bash +daemon:x:1:1:daemon:/usr/sbin:/bin/sh +bin:x:2:2:bin:/bin:/bin/sh +sys:x:3:3:sys:/dev:/bin/sh +nobody:x:65534:65534:nobody:/nonexistent:/bin/sh +messagebus:x:103:107::/var/run/dbus:/bin/false +") +@end lisp + +As a first pass at this, we might want to have all the entries in +/etc/passwd in a list. + +Doing this with string-based PEG syntax would look like this: +@lisp +(define-peg-string-patterns + "passwd <- entry* !. +entry <-- (! NL .)* NL* +NL < '\n'") +@end lisp + +A @code{passwd} file is 0 or more entries (@code{entry*}) until the end +of the file (@code{!.} (@code{.} is any character, so @code{!.} means +``not anything'')). We want to capture the data in the nonterminal +@code{passwd}, but not tag it with the name, so we use @code{<-}. + +An entry is a series of 0 or more characters that aren't newlines +(@code{(! NL .)*}) followed by 0 or more newlines (@code{NL*}). We want +to tag all the entries with @code{entry}, so we use @code{<--}. + +A newline is just a literal newline (@code{'\n'}). We don't want a +bunch of newlines cluttering up the output, so we use @code{<} to throw +away the captured data. + +Here is the same PEG defined using S-expressions: +@lisp +(define-peg-pattern passwd body (and (* entry) (not-followed-by peg-any))) +(define-peg-pattern entry all (and (* (and (not-followed-by NL) peg-any)) + (* NL))) +(define-peg-pattern NL none "\n") +@end lisp + +Obviously this is much more verbose. On the other hand, it's more +explicit, and thus easier to build automatically. However, there are +some tricks that make S-expressions easier to use in some cases. One is +the @code{ignore} keyword; the string syntax has no way to say ``throw +away this text'' except breaking it out into a separate nonterminal. +For instance, to throw away the newlines we had to define @code{NL}. In +the S-expression syntax, we could have simply written @code{(ignore +"\n")}. Also, for the cases where string syntax is really much cleaner, +the @code{peg} keyword can be used to embed string syntax in +S-expression syntax. For instance, we could have written: + +@lisp +(define-peg-pattern passwd body (peg "entry* !.")) +@end lisp + +However we define it, parsing @code{*etc-passwd*} with the @code{passwd} +nonterminal yields the same results: + +@lisp +(peg:tree (match-pattern passwd *etc-passwd*)) @result{} +((entry "root:x:0:0:root:/root:/bin/bash") + (entry "daemon:x:1:1:daemon:/usr/sbin:/bin/sh") + (entry "bin:x:2:2:bin:/bin:/bin/sh") + (entry "sys:x:3:3:sys:/dev:/bin/sh") + (entry "nobody:x:65534:65534:nobody:/nonexistent:/bin/sh") + (entry "messagebus:x:103:107::/var/run/dbus:/bin/false")) +@end lisp + +However, here is something to be wary of: + +@lisp +(peg:tree (match-pattern passwd "one entry")) @result{} +(entry "one entry") +@end lisp + +By default, the parse trees generated by PEGs are compressed as much as +possible without losing information. It may not look like this is what +you want at first, but uncompressed parse trees are an enormous headache +(there's no easy way to predict how deep particular lists will nest, +there are empty lists littered everywhere, etc. etc.). One side-effect +of this, however, is that sometimes the compressor is too aggressive. +No information is discarded when @code{((entry "one entry"))} is +compressed to @code{(entry "one entry")}, but in this particular case it +probably isn't what we want. + +There are two functions for easily dealing with this: +@code{keyword-flatten} and @code{context-flatten}. The +@code{keyword-flatten} function takes a list of keywords and a list to +flatten, then tries to coerce the list such that the first element of +all sublists is one of the keywords. The @code{context-flatten} +function is similar, but instead of a list of keywords it takes a +predicate that should indicate whether a given sublist is good enough +(refer to the API reference for more details). + +What we want here is @code{keyword-flatten}. +@lisp +(keyword-flatten '(entry) (peg:tree (match-pattern passwd *etc-passwd*))) @result{} +((entry "root:x:0:0:root:/root:/bin/bash") + (entry "daemon:x:1:1:daemon:/usr/sbin:/bin/sh") + (entry "bin:x:2:2:bin:/bin:/bin/sh") + (entry "sys:x:3:3:sys:/dev:/bin/sh") + (entry "nobody:x:65534:65534:nobody:/nonexistent:/bin/sh") + (entry "messagebus:x:103:107::/var/run/dbus:/bin/false")) +(keyword-flatten '(entry) (peg:tree (match-pattern passwd "one entry"))) @result{} +((entry "one entry")) +@end lisp + +Of course, this is a somewhat contrived example. In practice we would +probably just tag the @code{passwd} nonterminal to remove the ambiguity +(using either the @code{all} keyword for S-expressions or the @code{<--} +symbol for strings).. + +@lisp +(define-peg-pattern tag-passwd all (peg "entry* !.")) +(peg:tree (match-pattern tag-passwd *etc-passwd*)) @result{} +(tag-passwd + (entry "root:x:0:0:root:/root:/bin/bash") + (entry "daemon:x:1:1:daemon:/usr/sbin:/bin/sh") + (entry "bin:x:2:2:bin:/bin:/bin/sh") + (entry "sys:x:3:3:sys:/dev:/bin/sh") + (entry "nobody:x:65534:65534:nobody:/nonexistent:/bin/sh") + (entry "messagebus:x:103:107::/var/run/dbus:/bin/false")) +(peg:tree (match-pattern tag-passwd "one entry")) +(tag-passwd + (entry "one entry")) +@end lisp + +If you're ever uncertain about the potential results of parsing +something, remember the two absolute rules: +@enumerate +@item +No parsing information will ever be discarded. +@item +There will never be any lists with fewer than 2 elements. +@end enumerate + +For the purposes of (1), "parsing information" means things tagged with +the @code{any} keyword or the @code{<--} symbol. Plain strings will be +concatenated. + +Let's extend this example a bit more and actually pull some useful +information out of the passwd file: + +@lisp +(define-peg-string-patterns + "passwd <-- entry* !. +entry <-- login C pass C uid C gid C nameORcomment C homedir C shell NL* +login <-- text +pass <-- text +uid <-- [0-9]* +gid <-- [0-9]* +nameORcomment <-- text +homedir <-- path +shell <-- path +path <-- (SLASH pathELEMENT)* +pathELEMENT <-- (!NL !C !'/' .)* +text <- (!NL !C .)* +C < ':' +NL < '\n' +SLASH < '/'") +@end lisp + +This produces rather pretty parse trees: +@lisp +(passwd + (entry (login "root") + (pass "x") + (uid "0") + (gid "0") + (nameORcomment "root") + (homedir (path (pathELEMENT "root"))) + (shell (path (pathELEMENT "bin") (pathELEMENT "bash")))) + (entry (login "daemon") + (pass "x") + (uid "1") + (gid "1") + (nameORcomment "daemon") + (homedir + (path (pathELEMENT "usr") (pathELEMENT "sbin"))) + (shell (path (pathELEMENT "bin") (pathELEMENT "sh")))) + (entry (login "bin") + (pass "x") + (uid "2") + (gid "2") + (nameORcomment "bin") + (homedir (path (pathELEMENT "bin"))) + (shell (path (pathELEMENT "bin") (pathELEMENT "sh")))) + (entry (login "sys") + (pass "x") + (uid "3") + (gid "3") + (nameORcomment "sys") + (homedir (path (pathELEMENT "dev"))) + (shell (path (pathELEMENT "bin") (pathELEMENT "sh")))) + (entry (login "nobody") + (pass "x") + (uid "65534") + (gid "65534") + (nameORcomment "nobody") + (homedir (path (pathELEMENT "nonexistent"))) + (shell (path (pathELEMENT "bin") (pathELEMENT "sh")))) + (entry (login "messagebus") + (pass "x") + (uid "103") + (gid "107") + nameORcomment + (homedir + (path (pathELEMENT "var") + (pathELEMENT "run") + (pathELEMENT "dbus"))) + (shell (path (pathELEMENT "bin") (pathELEMENT "false"))))) +@end lisp + +Notice that when there's no entry in a field (e.g. @code{nameORcomment} +for messagebus) the symbol is inserted. This is the ``don't throw away +any information'' rule---we succesfully matched a @code{nameORcomment} +of 0 characters (since we used @code{*} when defining it). This is +usually what you want, because it allows you to e.g. use @code{list-ref} +to pull out elements (since they all have known offsets). + +If you'd prefer not to have symbols for empty matches, you can replace +the @code{*} with a @code{+} and add a @code{?} after the +@code{nameORcomment} in @code{entry}. Then it will try to parse 1 or +more characters, fail (inserting nothing into the parse tree), but +continue because it didn't have to match the nameORcomment to continue. + + +@subsubheading Embedding Arithmetic Expressions + +We can parse simple mathematical expressions with the following PEG: + +@lisp +(define-peg-string-patterns + "expr <- sum +sum <-- (product ('+' / '-') sum) / product +product <-- (value ('*' / '/') product) / value +value <-- number / '(' expr ')' +number <-- [0-9]+") +@end lisp + +Then: +@lisp +(peg:tree (match-pattern expr "1+1/2*3+(1+1)/2")) @result{} +(sum (product (value (number "1"))) + "+" + (sum (product + (value (number "1")) + "/" + (product + (value (number "2")) + "*" + (product (value (number "3"))))) + "+" + (sum (product + (value "(" + (sum (product (value (number "1"))) + "+" + (sum (product (value (number "1"))))) + ")") + "/" + (product (value (number "2"))))))) +@end lisp + +There is very little wasted effort in this PEG. The @code{number} +nonterminal has to be tagged because otherwise the numbers might run +together with the arithmetic expressions during the string concatenation +stage of parse-tree compression (the parser will see ``1'' followed by +``/'' and decide to call it ``1/''). When in doubt, tag. + +It is very easy to turn these parse trees into lisp expressions: + +@lisp +(define (parse-sum sum left . rest) + (if (null? rest) + (apply parse-product left) + (list (string->symbol (car rest)) + (apply parse-product left) + (apply parse-sum (cadr rest))))) + +(define (parse-product product left . rest) + (if (null? rest) + (apply parse-value left) + (list (string->symbol (car rest)) + (apply parse-value left) + (apply parse-product (cadr rest))))) + +(define (parse-value value first . rest) + (if (null? rest) + (string->number (cadr first)) + (apply parse-sum (car rest)))) + +(define parse-expr parse-sum) +@end lisp + +(Notice all these functions look very similar; for a more complicated +PEG, it would be worth abstracting.) + +Then: +@lisp +(apply parse-expr (peg:tree (match-pattern expr "1+1/2*3+(1+1)/2"))) @result{} +(+ 1 (+ (/ 1 (* 2 3)) (/ (+ 1 1) 2))) +@end lisp + +But wait! The associativity is wrong! Where it says @code{(/ 1 (* 2 +3))}, it should say @code{(* (/ 1 2) 3)}. + +It's tempting to try replacing e.g. @code{"sum <-- (product ('+' / '-') +sum) / product"} with @code{"sum <-- (sum ('+' / '-') product) / +product"}, but this is a Bad Idea. PEGs don't support left recursion. +To see why, imagine what the parser will do here. When it tries to +parse @code{sum}, it first has to try and parse @code{sum}. But to do +that, it first has to try and parse @code{sum}. This will continue +until the stack gets blown off. + +So how does one parse left-associative binary operators with PEGs? +Honestly, this is one of their major shortcomings. There's no +general-purpose way of doing this, but here the repetition operators are +a good choice: + +@lisp +(use-modules (srfi srfi-1)) + +(define-peg-string-patterns + "expr <- sum +sum <-- (product ('+' / '-'))* product +product <-- (value ('*' / '/'))* value +value <-- number / '(' expr ')' +number <-- [0-9]+") + +;; take a deep breath... +(define (make-left-parser next-func) + (lambda (sum first . rest) ;; general form, comments below assume + ;; that we're dealing with a sum expression + (if (null? rest) ;; form (sum (product ...)) + (apply next-func first) + (if (string? (cadr first));; form (sum ((product ...) "+") (product ...)) + (list (string->symbol (cadr first)) + (apply next-func (car first)) + (apply next-func (car rest))) + ;; form (sum (((product ...) "+") ((product ...) "+")) (product ...)) + (car + (reduce ;; walk through the list and build a left-associative tree + (lambda (l r) + (list (list (cadr r) (car r) (apply next-func (car l))) + (string->symbol (cadr l)))) + 'ignore + (append ;; make a list of all the products + ;; the first one should be pre-parsed + (list (list (apply next-func (caar first)) + (string->symbol (cadar first)))) + (cdr first) + ;; the last one has to be added in + (list (append rest '("done")))))))))) + +(define (parse-value value first . rest) + (if (null? rest) + (string->number (cadr first)) + (apply parse-sum (car rest)))) +(define parse-product (make-left-parser parse-value)) +(define parse-sum (make-left-parser parse-product)) +(define parse-expr parse-sum) +@end lisp + +Then: +@lisp +(apply parse-expr (peg:tree (match-pattern expr "1+1/2*3+(1+1)/2"))) @result{} +(+ (+ 1 (* (/ 1 2) 3)) (/ (+ 1 1) 2)) +@end lisp + +As you can see, this is much uglier (it could be made prettier by using +@code{context-flatten}, but the way it's written above makes it clear +how we deal with the three ways the zero-or-more @code{*} expression can +parse). Fortunately, most of the time we can get away with only using +right-associativity. + +@subsubheading Simplified Functions + +For a more tantalizing example, consider the following grammar that +parses (highly) simplified C functions: + +@lisp +(define-peg-string-patterns + "cfunc <-- cSP ctype cSP cname cSP cargs cLB cSP cbody cRB +ctype <-- cidentifier +cname <-- cidentifier +cargs <-- cLP (! (cSP cRP) carg cSP (cCOMMA / cRP) cSP)* cSP +carg <-- cSP ctype cSP cname +cbody <-- cstatement * +cidentifier <- [a-zA-z][a-zA-Z0-9_]* +cstatement <-- (!';'.)*cSC cSP +cSC < ';' +cCOMMA < ',' +cLP < '(' +cRP < ')' +cLB < '@{' +cRB < '@}' +cSP < [ \t\n]*") +@end lisp + +Then: +@lisp +(match-pattern cfunc "int square(int a) @{ return a*a;@}") @result{} +(32 + (cfunc (ctype "int") + (cname "square") + (cargs (carg (ctype "int") (cname "a"))) + (cbody (cstatement "return a*a")))) +@end lisp + +And: +@lisp +(match-pattern cfunc "int mod(int a, int b) @{ int c = a/b;return a-b*c; @}") @result{} +(52 + (cfunc (ctype "int") + (cname "mod") + (cargs (carg (ctype "int") (cname "a")) + (carg (ctype "int") (cname "b"))) + (cbody (cstatement "int c = a/b") + (cstatement "return a- b*c")))) +@end lisp + +By wrapping all the @code{carg} nonterminals in a @code{cargs} +nonterminal, we were able to remove any ambiguity in the parsing +structure and avoid having to call @code{context-flatten} on the output +of @code{match-pattern}. We used the same trick with the @code{cstatement} +nonterminals, wrapping them in a @code{cbody} nonterminal. + +The whitespace nonterminal @code{cSP} used here is a (very) useful +instantiation of a common pattern for matching syntactically irrelevant +information. Since it's tagged with @code{<} and ends with @code{*} it +won't clutter up the parse trees (all the empty lists will be discarded +during the compression step) and it will never cause parsing to fail. + +@node PEG Internals +@subsection PEG Internals + +A PEG parser takes a string as input and attempts to parse it as a given +nonterminal. The key idea of the PEG implementation is that every +nonterminal is just a function that takes a string as an argument and +attempts to parse that string as its nonterminal. The functions always +start from the beginning, but a parse is considered successful if there +is material left over at the end. + +This makes it easy to model different PEG parsing operations. For +instance, consider the PEG grammar @code{"ab"}, which could also be +written @code{(and "a" "b")}. It matches the string ``ab''. Here's how +that might be implemented in the PEG style: + +@lisp +(define (match-and-a-b str) + (match-a str) + (match-b str)) +@end lisp + +As you can see, the use of functions provides an easy way to model +sequencing. In a similar way, one could model @code{(or a b)} with +something like the following: + +@lisp +(define (match-or-a-b str) + (or (match-a str) (match-b str))) +@end lisp + +Here the semantics of a PEG @code{or} expression map naturally onto +Scheme's @code{or} operator. This function will attempt to run +@code{(match-a str)}, and return its result if it succeeds. Otherwise it +will run @code{(match-b str)}. + +Of course, the code above wouldn't quite work. We need some way for the +parsing functions to communicate. The actual interface used is below. + +@subsubheading Parsing Function Interface + +A parsing function takes three arguments - a string, the length of that +string, and the position in that string it should start parsing at. In +effect, the parsing functions pass around substrings in pieces - the +first argument is a buffer of characters, and the second two give a +range within that buffer that the parsing function should look at. + +Parsing functions return either #f, if they failed to match their +nonterminal, or a list whose first element must be an integer +representing the final position in the string they matched and whose cdr +can be any other data the function wishes to return, or '() if it +doesn't have any more data. + +The one caveat is that if the extra data it returns is a list, any +adjacent strings in that list will be appended by @code{match-pattern}. For +instance, if a parsing function returns @code{(13 ("a" "b" "c"))}, +@code{match-pattern} will take @code{(13 ("abc"))} as its value. + +For example, here is a function to match ``ab'' using the actual +interface. + +@lisp +(define (match-a-b str len pos) + (and (<= (+ pos 2) len) + (string= str "ab" pos (+ pos 2)) + (list (+ pos 2) '()))) ; we return no extra information +@end lisp + +The above function can be used to match a string by running +@code{(match-pattern match-a-b "ab")}. + +@subsubheading Code Generators and Extensible Syntax + +PEG expressions, such as those in a @code{define-peg-pattern} form, are +interpreted internally in two steps. + +First, any string PEG is expanded into an s-expression PEG by the code +in the @code{(ice-9 peg string-peg)} module. + +Then, then s-expression PEG that results is compiled into a parsing +function by the @code{(ice-9 peg codegen)} module. In particular, the +function @code{compile-peg-pattern} is called on the s-expression. It then +decides what to do based on the form it is passed. + +The PEG syntax can be expanded by providing @code{compile-peg-pattern} more +options for what to do with its forms. The extended syntax will be +associated with a symbol, for instance @code{my-parsing-form}, and will +be called on all PEG expressions of the form +@lisp +(my-parsing-form ...) +@end lisp + +The parsing function should take two arguments. The first will be a +syntax object containing a list with all of the arguments to the form +(but not the form's name), and the second will be the +@code{capture-type} argument that is passed to @code{define-peg-pattern}. + +New functions can be registered by calling @code{(add-peg-compiler! +symbol function)}, where @code{symbol} is the symbol that will indicate +a form of this type and @code{function} is the code generating function +described above. The function @code{add-peg-compiler!} is exported from +the @code{(ice-9 peg codegen)} module. diff --git a/doc/ref/api-procedures.texi b/doc/ref/api-procedures.texi index 7fedadffd..02bf6822a 100644 --- a/doc/ref/api-procedures.texi +++ b/doc/ref/api-procedures.texi @@ -161,48 +161,30 @@ Returns @code{#t} if @var{obj} is a compiled procedure, or @code{#f} otherwise. @end deffn -@deffn {Scheme Procedure} program-objcode program -@deffnx {C Function} scm_program_objcode (program) -Returns the object code associated with this program. @xref{Bytecode -and Objcode}, for more information. +@deffn {Scheme Procedure} program-code program +@deffnx {C Function} scm_program_code (program) +Returns the address of the program's entry, as an integer. This address +is mostly useful to procedures in @code{(system vm debug)}. @end deffn -@deffn {Scheme Procedure} program-objects program -@deffnx {C Function} scm_program_objects (program) -Returns the ``object table'' associated with this program, as a -vector. @xref{VM Programs}, for more information. +@deffn {Scheme Procedure} program-num-free-variable program +@deffnx {C Function} scm_program_num_free_variables (program) +Return the number of free variables captured by this program. @end deffn -@deffn {Scheme Procedure} program-module program -@deffnx {C Function} scm_program_module (program) -Returns the module that was current when this program was created. Can -return @code{#f} if the compiler could determine that this information -was unnecessary. -@end deffn - -@deffn {Scheme Procedure} program-free-variables program -@deffnx {C Function} scm_program_free_variables (program) -Returns the set of free variables that this program captures in its -closure, as a vector. If a closure is code with data, you can get the -code from @code{program-objcode}, and the data via -@code{program-free-variables}. - -Some of the values captured are actually in variable ``boxes''. -@xref{Variables and the VM}, for more information. +@deffn {Scheme Procedure} program-free-variable-ref program n +@deffnx {C Function} scm_program_free_variable-ref (program, n) +@deffnx {Scheme Procedure} program-free-variable-set! program n val +@deffnx {C Function} scm_program_free_variable_set_x (program, n, val) +Accessors for a program's free variables. Some of the values captured +are actually in variable ``boxes''. @xref{Variables and the VM}, for +more information. Users must not modify the returned value unless they think they're really clever. @end deffn -@deffn {Scheme Procedure} program-meta program -@deffnx {C Function} scm_program_meta (program) -Return the metadata thunk of @var{program}, or @code{#f} if it has no -metadata. - -When called, a metadata thunk returns a list of the following form: -@code{(@var{bindings} @var{sources} @var{arities} . @var{properties})}. The format -of each of these elements is discussed below. -@end deffn +@c FIXME @deffn {Scheme Procedure} program-bindings program @deffnx {Scheme Procedure} make-binding name boxed? index start end diff --git a/doc/ref/compiler.texi b/doc/ref/compiler.texi index bfc633e57..640733838 100644 --- a/doc/ref/compiler.texi +++ b/doc/ref/compiler.texi @@ -1,20 +1,17 @@ @c -*-texinfo-*- @c This is part of the GNU Guile Reference Manual. -@c Copyright (C) 2008, 2009, 2010, 2013 +@c Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013, 2014 @c Free Software Foundation, Inc. @c See the file guile.texi for copying conditions. @node Compiling to the Virtual Machine @section Compiling to the Virtual Machine -Compilers have a mystique about them that is attractive and -off-putting at the same time. They are attractive because they are -magical -- they transform inert text into live results, like throwing -the switch on Frankenstein's monster. However, this magic is perceived -by many to be impenetrable. - -This section aims to pay attention to the small man behind the -curtain. +Compilers! The word itself inspires excitement and awe, even among +experienced practitioners. But a compiler is just a program: an +eminently hackable thing. This section aims to to describe Guile's +compiler in such a way that interested Scheme hackers can feel +comfortable reading and extending it. @xref{Read/Load/Eval/Compile}, if you're lost and you just wanted to know how to compile your @code{.scm} file. @@ -23,9 +20,8 @@ know how to compile your @code{.scm} file. * Compiler Tower:: * The Scheme Compiler:: * Tree-IL:: -* GLIL:: -* Assembly:: -* Bytecode and Objcode:: +* Continuation-Passing Style:: +* Bytecode:: * Writing New High-Level Languages:: * Extending the Compiler:: @end menu @@ -33,16 +29,15 @@ know how to compile your @code{.scm} file. @node Compiler Tower @subsection Compiler Tower -Guile's compiler is quite simple, actually -- its @emph{compilers}, to -put it more accurately. Guile defines a tower of languages, starting -at Scheme and progressively simplifying down to languages that -resemble the VM instruction set (@pxref{Instruction Set}). +Guile's compiler is quite simple -- its @emph{compilers}, to put it more +accurately. Guile defines a tower of languages, starting at Scheme and +progressively simplifying down to languages that resemble the VM +instruction set (@pxref{Instruction Set}). Each language knows how to compile to the next, so each step is simple -and understandable. Furthermore, this set of languages is not -hardcoded into Guile, so it is possible for the user to add new -high-level languages, new passes, or even different compilation -targets. +and understandable. Furthermore, this set of languages is not hardcoded +into Guile, so it is possible for the user to add new high-level +languages, new passes, or even different compilation targets. Languages are registered in the module, @code{(system base language)}: @@ -60,10 +55,10 @@ They are registered with the @code{define-language} form. [#:make-default-environment=make-fresh-user-module] Define a language. -This syntax defines a @code{#<language>} object, bound to @var{name} -in the current environment. In addition, the language will be added to -the global language set. For example, this is the language definition -for Scheme: +This syntax defines a @code{<language>} object, bound to @var{name} in +the current environment. In addition, the language will be added to the +global language set. For example, this is the language definition for +Scheme: @example (define-language scheme @@ -78,7 +73,7 @@ for Scheme: @end deffn The interesting thing about having languages defined this way is that -they present a uniform interface to the read-eval-print loop. This +they present a uniform interface to the read-eval-print loop. This allows the user to change the current language of the REPL: @example @@ -116,8 +111,8 @@ fast. There is a notion of a ``current language'', which is maintained in the @code{current-language} parameter, defined in the core @code{(guile)} -module. This language is normally Scheme, and may be rebound by the -user. The run-time compilation interfaces +module. This language is normally Scheme, and may be rebound by the +user. The run-time compilation interfaces (@pxref{Read/Load/Eval/Compile}) also allow you to choose other source and target languages. @@ -126,30 +121,31 @@ The normal tower of languages when compiling Scheme goes like this: @itemize @item Scheme @item Tree Intermediate Language (Tree-IL) -@item Guile Lowlevel Intermediate Language (GLIL) -@item Assembly +@item Continuation-Passing Style (CPS) @item Bytecode -@item Objcode @end itemize -Object code may be serialized to disk directly, though it has a cookie -and version prepended to the front. But when compiling Scheme at run -time, you want a Scheme value: for example, a compiled procedure. For -this reason, so as not to break the abstraction, Guile defines a fake -language at the bottom of the tower: +As discussed before (@pxref{Object File Format}), bytecode is in ELF +format, ready to be serialized to disk. But when compiling Scheme at +run time, you want a Scheme value: for example, a compiled procedure. +For this reason, so as not to break the abstraction, Guile defines a +fake language at the bottom of the tower: @itemize @item Value @end itemize -Compiling to @code{value} loads the object code into a procedure, and -wakes the sleeping giant. +Compiling to @code{value} loads the bytecode into a procedure, turning +cold bytes into warm code. Perhaps this strangeness can be explained by example: -@code{compile-file} defaults to compiling to object code, because it +@code{compile-file} defaults to compiling to bytecode, because it produces object code that has to live in the barren world outside the -Guile runtime; but @code{compile} defaults to compiling to -@code{value}, as its product re-enters the Guile world. +Guile runtime; but @code{compile} defaults to compiling to @code{value}, +as its product re-enters the Guile world. + +@c FIXME: This doesn't work anymore :( Should we add some kind of +@c special GC pass, or disclaim this kind of code, or what? Indeed, the process of compilation can circulate through these different worlds indefinitely, as shown by the following quine: @@ -161,22 +157,21 @@ different worlds indefinitely, as shown by the following quine: @node The Scheme Compiler @subsection The Scheme Compiler -The job of the Scheme compiler is to expand all macros and all of -Scheme to its most primitive expressions. The definition of -``primitive'' is given by the inventory of constructs provided by -Tree-IL, the target language of the Scheme compiler: procedure -applications, conditionals, lexical references, etc. This is described -more fully in the next section. +The job of the Scheme compiler is to expand all macros and all of Scheme +to its most primitive expressions. The definition of ``primitive +expression'' is given by the inventory of constructs provided by +Tree-IL, the target language of the Scheme compiler: procedure calls, +conditionals, lexical references, and so on. This is described more +fully in the next section. The tricky and amusing thing about the Scheme-to-Tree-IL compiler is -that it is completely implemented by the macro expander. Since the +that it is completely implemented by the macro expander. Since the macro expander has to run over all of the source code already in order to expand macros, it might as well do the analysis at the same time, producing Tree-IL expressions directly. -Because this compiler is actually the macro expander, it is -extensible. Any macro which the user writes becomes part of the -compiler. +Because this compiler is actually the macro expander, it is extensible. +Any macro which the user writes becomes part of the compiler. The Scheme-to-Tree-IL expander may be invoked using the generic @code{compile} procedure: @@ -184,38 +179,16 @@ The Scheme-to-Tree-IL expander may be invoked using the generic @lisp (compile '(+ 1 2) #:from 'scheme #:to 'tree-il) @result{} - #<<application> src: #f - proc: #<<toplevel-ref> src: #f name: +> - args: (#<<const> src: #f exp: 1> - #<<const> src: #f exp: 2>)> -@end lisp - -Or, since Tree-IL is so close to Scheme, it is often useful to expand -Scheme to Tree-IL, then translate back to Scheme. For that reason the -expander provides two interfaces. The former is equivalent to calling -@code{(macroexpand '(+ 1 2) 'c)}, where the @code{'c} is for -``compile''. With @code{'e} (the default), the result is translated -back to Scheme: - -@lisp -(macroexpand '(+ 1 2)) -@result{} (+ 1 2) -(macroexpand '(let ((x 10)) (* x x))) -@result{} (let ((x84 10)) (* x84 x84)) +#<tree-il (call (toplevel +) (const 1) (const 2))> @end lisp -The second example shows that as part of its job, the macro expander -renames lexically-bound variables. The original names are preserved -when compiling to Tree-IL, but can't be represented in Scheme: a -lexical binding only has one name. It is for this reason that the -@emph{native} output of the expander is @emph{not} Scheme. There's too -much information we would lose if we translated to Scheme directly: -lexical variable names, source locations, and module hygiene. - -Note however that @code{macroexpand} does not have the same signature -as @code{compile-tree-il}. @code{compile-tree-il} is a small wrapper -around @code{macroexpand}, to make it conform to the general form of -compiler procedures in Guile's language tower. +@code{(compile @var{foo} #:from 'scheme #:to 'tree-il)} is entirely +equivalent to calling the macro expander as @code{(macroexpand @var{foo} +'c '(compile load eval))}. @xref{Macro Expansion}. +@code{compile-tree-il}, the procedure dispatched by @code{compile} to +@code{'tree-il}, is a small wrapper around @code{macroexpand}, to make +it conform to the general form of compiler procedures in Guile's +language tower. Compiler procedures take three arguments: an expression, an environment, and a keyword list of options. They return three values: @@ -310,7 +283,7 @@ Users may program with this format directly at the REPL: @example scheme@@(guile-user)> ,language tree-il Happy hacking with Tree Intermediate Language! To switch back, type `,L scheme'. -tree-il@@(guile-user)> (apply (primitive +) (const 32) (const 10)) +tree-il@@(guile-user)> (call (primitive +) (const 32) (const 10)) @result{} 42 @end example @@ -326,36 +299,41 @@ take care of the rest. @deftp {Scheme Variable} <void> src @deftpx {External Representation} (void) -An empty expression. In practice, equivalent to Scheme's @code{(if #f +An empty expression. In practice, equivalent to Scheme's @code{(if #f #f)}. @end deftp + @deftp {Scheme Variable} <const> src exp @deftpx {External Representation} (const @var{exp}) A constant. @end deftp + @deftp {Scheme Variable} <primitive-ref> src name @deftpx {External Representation} (primitive @var{name}) -A reference to a ``primitive''. A primitive is a procedure that, when -compiled, may be open-coded. For example, @code{cons} is usually +A reference to a ``primitive''. A primitive is a procedure that, when +compiled, may be open-coded. For example, @code{cons} is usually recognized as a primitive, so that it compiles down to a single instruction. Compilation of Tree-IL usually begins with a pass that resolves some @code{<module-ref>} and @code{<toplevel-ref>} expressions to -@code{<primitive-ref>} expressions. The actual compilation pass -has special cases for applications of certain primitives, like -@code{apply} or @code{cons}. +@code{<primitive-ref>} expressions. The actual compilation pass has +special cases for calls to certain primitives, like @code{apply} or +@code{cons}. @end deftp + @deftp {Scheme Variable} <lexical-ref> src name gensym @deftpx {External Representation} (lexical @var{name} @var{gensym}) -A reference to a lexically-bound variable. The @var{name} is the +A reference to a lexically-bound variable. The @var{name} is the original name of the variable in the source program. @var{gensym} is a unique identifier for this variable. @end deftp + @deftp {Scheme Variable} <lexical-set> src name gensym exp @deftpx {External Representation} (set! (lexical @var{name} @var{gensym}) @var{exp}) Sets a lexically-bound variable. @end deftp + @deftp {Scheme Variable} <module-ref> src mod name public? @deftpx {External Representation} (@@ @var{mod} @var{name}) @deftpx {External Representation} (@@@@ @var{mod} @var{name}) @@ -367,49 +345,70 @@ up in @var{mod}'s public interface, and serialized with @code{@@}; otherwise it will be looked up among the module's private bindings, and is serialized with @code{@@@@}. @end deftp + @deftp {Scheme Variable} <module-set> src mod name public? exp @deftpx {External Representation} (set! (@@ @var{mod} @var{name}) @var{exp}) @deftpx {External Representation} (set! (@@@@ @var{mod} @var{name}) @var{exp}) Sets a variable in a specific module. @end deftp + @deftp {Scheme Variable} <toplevel-ref> src name @deftpx {External Representation} (toplevel @var{name}) References a variable from the current procedure's module. @end deftp + @deftp {Scheme Variable} <toplevel-set> src name exp @deftpx {External Representation} (set! (toplevel @var{name}) @var{exp}) Sets a variable in the current procedure's module. @end deftp + @deftp {Scheme Variable} <toplevel-define> src name exp @deftpx {External Representation} (define (toplevel @var{name}) @var{exp}) Defines a new top-level variable in the current procedure's module. @end deftp + @deftp {Scheme Variable} <conditional> src test then else @deftpx {External Representation} (if @var{test} @var{then} @var{else}) A conditional. Note that @var{else} is not optional. @end deftp -@deftp {Scheme Variable} <application> src proc args -@deftpx {External Representation} (apply @var{proc} . @var{args}) + +@deftp {Scheme Variable} <call> src proc args +@deftpx {External Representation} (call @var{proc} . @var{args}) A procedure call. @end deftp -@deftp {Scheme Variable} <sequence> src exps -@deftpx {External Representation} (begin . @var{exps}) -Like Scheme's @code{begin}. + +@deftp {Scheme Variable} <primcall> src name args +@deftpx {External Representation} (primcall @var{name} . @var{args}) +A call to a primitive. Equivalent to @code{(call (primitive @var{name}) +. @var{args})}. This construct is often more convenient to generate and +analyze than @code{<call>}. + +As part of the compilation process, instances of @code{(call (primitive +@var{name}) . @var{args})} are transformed into primcalls. +@end deftp + +@deftp {Scheme Variable} <seq> src head tail +@deftpx {External Representation} (seq @var{head} @var{tail}) +A sequence. The semantics is that @var{head} is evaluated first, and +any resulting values are ignored. Then @var{tail} is evaluated, in tail +position. @end deftp + @deftp {Scheme Variable} <lambda> src meta body @deftpx {External Representation} (lambda @var{meta} @var{body}) -A closure. @var{meta} is an association list of properties for the -procedure. @var{body} is a single Tree-IL expression of type -@code{<lambda-case>}. As the @code{<lambda-case>} clause can chain to +A closure. @var{meta} is an association list of properties for the +procedure. @var{body} is a single Tree-IL expression of type +@code{<lambda-case>}. As the @code{<lambda-case>} clause can chain to an alternate clause, this makes Tree-IL's @code{<lambda>} have the expressiveness of Scheme's @code{case-lambda}. @end deftp + @deftp {Scheme Variable} <lambda-case> req opt rest kw inits gensyms body alternate @deftpx {External Representation} @ (lambda-case ((@var{req} @var{opt} @var{rest} @var{kw} @var{inits} @var{gensyms})@ @var{body})@ [@var{alternate}]) -One clause of a @code{case-lambda}. A @code{lambda} expression in +One clause of a @code{case-lambda}. A @code{lambda} expression in Scheme is treated as a @code{case-lambda} with one clause. @var{req} is a list of the procedure's required arguments, as symbols. @@ -420,9 +419,9 @@ argument, or @code{#f}. @var{kw} is a list of the form, @code{(@var{allow-other-keys?} (@var{keyword} @var{name} @var{var}) ...)}, where @var{keyword} is the keyword corresponding to the argument named @var{name}, and whose -corresponding gensym is @var{var}. @var{inits} are tree-il expressions -corresponding to all of the optional and keyword arguments, evaluated -to bind variables whose value is not supplied by the procedure caller. +corresponding gensym is @var{var}. @var{inits} are tree-il expressions +corresponding to all of the optional and keyword arguments, evaluated to +bind variables whose value is not supplied by the procedure caller. Each @var{init} expression is evaluated in the lexical context of previously bound variables, from left to right. @@ -430,68 +429,49 @@ previously bound variables, from left to right. first all of the required arguments, then the optional arguments if any, then the rest argument if any, then all of the keyword arguments. -@var{body} is the body of the clause. If the procedure is called with +@var{body} is the body of the clause. If the procedure is called with an appropriate number of arguments, @var{body} is evaluated in tail -position. Otherwise, if there is an @var{alternate}, it should be a +position. Otherwise, if there is an @var{alternate}, it should be a @code{<lambda-case>} expression, representing the next clause to try. If there is no @var{alternate}, a wrong-number-of-arguments error is signaled. @end deftp + @deftp {Scheme Variable} <let> src names gensyms vals exp @deftpx {External Representation} (let @var{names} @var{gensyms} @var{vals} @var{exp}) -Lexical binding, like Scheme's @code{let}. @var{names} are the -original binding names, @var{gensyms} are gensyms corresponding to the +Lexical binding, like Scheme's @code{let}. @var{names} are the original +binding names, @var{gensyms} are gensyms corresponding to the @var{names}, and @var{vals} are Tree-IL expressions for the values. @var{exp} is a single Tree-IL expression. @end deftp + @deftp {Scheme Variable} <letrec> in-order? src names gensyms vals exp @deftpx {External Representation} (letrec @var{names} @var{gensyms} @var{vals} @var{exp}) @deftpx {External Representation} (letrec* @var{names} @var{gensyms} @var{vals} @var{exp}) A version of @code{<let>} that creates recursive bindings, like Scheme's @code{letrec}, or @code{letrec*} if @var{in-order?} is true. @end deftp -@deftp {Scheme Variable} <dynlet> fluids vals body -@deftpx {External Representation} (dynlet @var{fluids} @var{vals} @var{body}) -Dynamic binding; the equivalent of Scheme's @code{with-fluids}. -@var{fluids} should be a list of Tree-IL expressions that will -evaluate to fluids, and @var{vals} a corresponding list of expressions -to bind to the fluids during the dynamic extent of the evaluation of -@var{body}. -@end deftp -@deftp {Scheme Variable} <dynref> fluid -@deftpx {External Representation} (dynref @var{fluid}) -A dynamic variable reference. @var{fluid} should be a Tree-IL -expression evaluating to a fluid. -@end deftp -@deftp {Scheme Variable} <dynset> fluid exp -@deftpx {External Representation} (dynset @var{fluid} @var{exp}) -A dynamic variable set. @var{fluid}, a Tree-IL expression evaluating -to a fluid, will be set to the result of evaluating @var{exp}. -@end deftp -@deftp {Scheme Variable} <dynwind> winder body unwinder -@deftpx {External Representation} (dynwind @var{winder} @var{body} @var{unwinder}) -A @code{dynamic-wind}. @var{winder} and @var{unwinder} should both -evaluate to thunks. Ensure that the winder and the unwinder are called -before entering and after leaving @var{body}. Note that @var{body} is -an expression, without a thunk wrapper. -@end deftp -@deftp {Scheme Variable} <prompt> tag body handler -@deftpx {External Representation} (prompt @var{tag} @var{body} @var{handler}) -A dynamic prompt. Instates a prompt named @var{tag}, an expression, + +@deftp {Scheme Variable} <prompt> escape-only? tag body handler +@deftpx {External Representation} (prompt @var{escape-only?} @var{tag} @var{body} @var{handler}) +A dynamic prompt. Instates a prompt named @var{tag}, an expression, during the dynamic extent of the execution of @var{body}, also an -expression. If an abort occurs to this prompt, control will be passed -to @var{handler}, a @code{<lambda-case>} expression with no optional -or keyword arguments, and no alternate. The first argument to the -@code{<lambda-case>} will be the captured continuation, and then all -of the values passed to the abort. @xref{Prompts}, for more -information. +expression. If an abort occurs to this prompt, control will be passed +to @var{handler}, also an expression, which should be a procedure. The +first argument to the handler procedure will be the captured +continuation, followed by all of the values passed to the abort. If +@var{escape-only?} is true, the handler should be a @code{<lambda>} with +a single @code{<lambda-case>} body expression with no optional or +keyword arguments, and no alternate, and whose first argument is +unreferenced. @xref{Prompts}, for more information. @end deftp + @deftp {Scheme Variable} <abort> tag args tail @deftpx {External Representation} (abort @var{tag} @var{args} @var{tail}) An abort to the nearest prompt with the name @var{tag}, an expression. @var{args} should be a list of expressions to pass to the prompt's handler, and @var{tail} should be an expression that will evaluate to -a list of additional arguments. An abort will save the partial +a list of additional arguments. An abort will save the partial continuation, which may later be reinstated, resulting in the @code{<abort>} expression evaluating to some number of values. @end deftp @@ -499,19 +479,20 @@ continuation, which may later be reinstated, resulting in the There are two Tree-IL constructs that are not normally produced by higher-level compilers, but instead are generated during the source-to-source optimization and analysis passes that the Tree-IL -compiler does. Users should not generate these expressions directly, -unless they feel very clever, as the default analysis pass will -generate them as necessary. +compiler does. Users should not generate these expressions directly, +unless they feel very clever, as the default analysis pass will generate +them as necessary. @deftp {Scheme Variable} <let-values> src names gensyms exp body @deftpx {External Representation} (let-values @var{names} @var{gensyms} @var{exp} @var{body}) Like Scheme's @code{receive} -- binds the values returned by evaluating @code{exp} to the @code{lambda}-like bindings described by -@var{gensyms}. That is to say, @var{gensyms} may be an improper list. +@var{gensyms}. That is to say, @var{gensyms} may be an improper list. -@code{<let-values>} is an optimization of @code{<application>} of the +@code{<let-values>} is an optimization of a @code{<call>} to the primitive, @code{call-with-values}. @end deftp + @deftp {Scheme Variable} <fix> src names gensyms vals body @deftpx {External Representation} (fix @var{names} @var{gensyms} @var{vals} @var{body}) Like @code{<letrec>}, but only for @var{vals} that are unset @@ -520,323 +501,581 @@ Like @code{<letrec>}, but only for @var{vals} that are unset @code{fix} is an optimization of @code{letrec} (and @code{let}). @end deftp -Tree-IL implements a compiler to GLIL that recursively traverses -Tree-IL expressions, writing out GLIL expressions into a linear list. -The compiler also keeps some state as to whether the current -expression is in tail context, and whether its value will be used in -future computations. This state allows the compiler not to emit code -for constant expressions that will not be used (e.g.@: docstrings), and -to perform tail calls when in tail position. +Tree-IL is a convenient compilation target from source languages. It +can be convenient as a medium for optimization, though CPS is usually +better. The strength of Tree-IL is that it does not fix order of +evaluation, so it makes some code motion a bit easier. -Most optimization, such as it currently is, is performed on Tree-IL -expressions as source-to-source transformations. There will be more -optimizations added in the future. +Optimization passes performed on Tree-IL currently include: -Interested readers are encouraged to read the implementation in -@code{(language tree-il compile-glil)} for more details. +@itemize +@item Open-coding (turning toplevel-refs into primitive-refs, +and calls to primitives to primcalls) +@item Partial evaluation (comprising inlining, copy propagation, and +constant folding) +@item Common subexpression elimination (CSE) +@end itemize + +In the future, we will move the CSE pass to operate over the lower-level +CPS language. + +@node Continuation-Passing Style +@subsection Continuation-Passing Style -@node GLIL -@subsection GLIL +@cindex CPS +Continuation-passing style (CPS) is Guile's principal intermediate +language, bridging the gap between languages for people and languages +for machines. CPS gives a name to every part of a program: every +control point, and every intermediate value. This makes it an excellent +medium for reasoning about programs, which is the principal job of a +compiler. + +@menu +* An Introduction to CPS:: +* CPS in Guile:: +* Building CPS:: +* Compiling CPS:: +@end menu -Guile Lowlevel Intermediate Language (GLIL) is a structured intermediate -language whose expressions more closely approximate Guile's VM -instruction set. Its expression types are defined in @code{(language -glil)}. +@node An Introduction to CPS +@subsubsection An Introduction to CPS -@deftp {Scheme Variable} <glil-program> meta . body -A unit of code that at run-time will correspond to a compiled -procedure. @var{meta} should be an alist of properties, as in -Tree-IL's @code{<lambda>}. @var{body} is an ordered list of GLIL +Consider the following Scheme expression: + +@lisp +(begin + (display "The sum of 32 and 10 is: ") + (display 42) + (newline)) +@end lisp + +Let us identify all of the sub-expressions in this expression, +annotating them with unique labels: + +@lisp +(begin + (display "The sum of 32 and 10 is: ") + |k1 k2 + k0 + (display 42) + |k4 k5 + k3 + (newline)) + |k7 + k6 +@end lisp + +Each of these labels identifies a point in a program. One label may be +the continuation of another label. For example, the continuation of +@code{k7} is @code{k6}. This is because after evaluating the value of +@code{newline}, performed by the expression labelled @code{k7}, we +continue to apply it in @code{k6}. + +Which expression has @code{k0} as its continuation? It is either the +expression labelled @code{k1} or the expression labelled @code{k2}. +Scheme does not have a fixed order of evaluation of arguments, though it +does guarantee that they are evaluated in some order. Unlike general +Scheme, continuation-passing style makes evaluation order explicit. In +Guile, this choice is made by the higher-level language compilers. + +Let us assume a left-to-right evaluation order. In that case the +continuation of @code{k1} is @code{k2}, and the continuation of +@code{k2} is @code{k0}. + +With this example established, we are ready to give an example of CPS in +Scheme: + +@smalllisp +(lambda (ktail) + (let ((k1 (lambda () + (let ((k2 (lambda (proc) + (let ((k0 (lambda (arg0) + (proc k4 arg0)))) + (k0 "The sum of 32 and 10 is: "))))) + (k2 display)))) + (k4 (lambda _ + (let ((k5 (lambda (proc) + (let ((k3 (lambda (arg0) + (proc k7 arg0)))) + (k3 42))))) + (k5 display)))) + (k7 (lambda _ + (let ((k6 (lambda (proc) + (proc ktail)))) + (k6 newline))))) + (k1)) +@end smalllisp + +Holy code explosion, Batman! What's with all the lambdas? Indeed, CPS +is by nature much more verbose than ``direct-style'' intermediate +languages like Tree-IL. At the same time, CPS is simpler than full +Scheme, because it makes things more explicit. + +In the original program, the expression labelled @code{k0} is in effect +context. Any values it returns are ignored. In Scheme, this fact is +implicit. In CPS, we can see it explicitly by noting that its +continuation, @code{k4}, takes any number of values and ignores them. +Compare this to @code{k2}, which takes a single value; in this way we +can say that @code{k1} is in a ``value'' context. Likewise @code{k6} is +in tail context with respect to the expression as a whole, because its +continuation is the tail continuation, @code{ktail}. CPS makes these +details manifest, and gives them names. + +@node CPS in Guile +@subsubsection CPS in Guile + +Guile's CPS language is composed of @dfn{terms}, @dfn{expressions}, +and @dfn{continuations}. + +A term can either evaluate an expression and pass the resulting values +to some continuation, or it can declare local continuations and contain +a sub-term in the scope of those continuations. + +@deftp {CPS Term} $continue k src exp +Evaluate the expression @var{exp} and pass the resulting values (if any) +to the continuation labelled @var{k}. The source information associated +with the expression may be found in @var{src}, which is either an alist +as in @code{source-properties} or is @code{#f} if there is no associated +source. +@end deftp + +@deftp {CPS Term} $letk conts body +Bind @var{conts}, a list of continuations (@code{$cont} instances), in +the scope of the sub-term @var{body}. The continuations are mutually +recursive. +@end deftp + +Additionally, the early stages of CPS allow for a set of mutually +recursive functions to be declared as a term. This @code{$letrec} type +is like Tree-IL's @code{<fix>}. The contification pass will attempt to +transform the functions declared in a @code{$letrec} into local +continuations. Any remaining functions are later lowered to @code{$fun} expressions. + +@deftp {CPS Term} $letrec names syms funs body +Declare the mutually recursive set of functions denoted by @var{names}, +@var{syms}, and @var{funs} within the sub-term @var{body}. @var{names} +and @var{syms} are lists of symbols, and @var{funs} is a list of +@code{$fun} values. @var{syms} are globally unique. @end deftp -@deftp {Scheme Variable} <glil-std-prelude> nreq nlocs else-label -A prologue for a function with no optional, keyword, or rest -arguments. @var{nreq} is the number of required arguments. @var{nlocs} -the total number of local variables, including the arguments. If the -procedure was not given exactly @var{nreq} arguments, control will -jump to @var{else-label}, if given, or otherwise signal an error. -@end deftp -@deftp {Scheme Variable} <glil-opt-prelude> nreq nopt rest nlocs else-label -A prologue for a function with optional or rest arguments. Like -@code{<glil-std-prelude>}, with the addition that @var{nopt} is the -number of optional arguments (possibly zero) and @var{rest} is an -index of a local variable at which to bind a rest argument, or -@code{#f} if there is no rest argument. -@end deftp -@deftp {Scheme Variable} <glil-kw-prelude> nreq nopt rest kw allow-other-keys? nlocs else-label -A prologue for a function with keyword arguments. Like -@code{<glil-opt-prelude>}, with the addition that @var{kw} is a list -of keyword arguments, and @var{allow-other-keys?} is a flag indicating -whether to allow unknown keys. @xref{Function Prologue Instructions, -@code{bind-kwargs}}, for details on the format of @var{kw}. -@end deftp -@deftp {Scheme Variable} <glil-bind> . vars -An advisory expression that notes a liveness extent for a set of -variables. @var{vars} is a list of @code{(@var{name} @var{type} -@var{index})}, where @var{type} should be either @code{argument}, -@code{local}, or @code{external}. - -@code{<glil-bind>} expressions end up being serialized as part of a -program's metadata and do not form part of a program's code path. -@end deftp -@deftp {Scheme Variable} <glil-mv-bind> vars rest -A multiple-value binding of the values on the stack to @var{vars}. If -@var{rest} is true, the last element of @var{vars} will be treated as a -rest argument. - -In addition to pushing a binding annotation on the stack, like -@code{<glil-bind>}, an expression is emitted at compilation time to -make sure that there are enough values available to bind. See the -notes on @code{truncate-values} in @ref{Procedure Call and Return -Instructions}, for more information. -@end deftp -@deftp {Scheme Variable} <glil-unbind> -Closes the liveness extent of the most recently encountered -@code{<glil-bind>} or @code{<glil-mv-bind>} expression. As GLIL -expressions are compiled, a parallel stack of live bindings is -maintained; this expression pops off the top element from that stack. - -Bindings are written into the program's metadata so that debuggers and -other tools can determine the set of live local variables at a given -offset within a VM program. -@end deftp -@deftp {Scheme Variable} <glil-source> loc -Records source information for the preceding expression. @var{loc} -should be an association list of containing @code{line} @code{column}, -and @code{filename} keys, e.g.@: as returned by -@code{source-properties}. -@end deftp -@deftp {Scheme Variable} <glil-void> -Pushes ``the unspecified value'' on the stack. -@end deftp -@deftp {Scheme Variable} <glil-const> obj -Pushes a constant value onto the stack. @var{obj} must be a number, -string, symbol, keyword, boolean, character, uniform array, the empty -list, or a pair or vector of constants. -@end deftp -@deftp {Scheme Variable} <glil-lexical> local? boxed? op index -Accesses a lexically bound variable. If the variable is not -@var{local?} it is free. All variables may have @code{ref}, -@code{set}, and @code{bound?} as their @var{op}. Boxed variables may -also have the @var{op}s @code{box}, @code{empty-box}, and @code{fix}, -which correspond in semantics to the VM instructions @code{box}, -@code{empty-box}, and @code{fix-closure}. @xref{Stack Layout}, for -more information. -@end deftp -@deftp {Scheme Variable} <glil-toplevel> op name -Accesses a toplevel variable. @var{op} may be @code{ref}, @code{set}, -or @code{define}. -@end deftp -@deftp {Scheme Variable} <glil-module> op mod name public? -Accesses a variable within a specific module. See Tree-IL's -@code{<module-ref>}, for more information. -@end deftp -@deftp {Scheme Variable} <glil-label> label -Creates a new label. @var{label} can be any Scheme value, and should -be unique. -@end deftp -@deftp {Scheme Variable} <glil-branch> inst label -Branch to a label. @var{label} should be a @code{<ghil-label>}. -@code{inst} is a branching instruction: @code{br-if}, @code{br}, etc. -@end deftp -@deftp {Scheme Variable} <glil-call> inst nargs -This expression is probably misnamed, as it does not correspond to -function calls. @code{<glil-call>} invokes the VM instruction named -@var{inst}, noting that it is called with @var{nargs} stack arguments. -The arguments should be pushed on the stack already. What happens to -the stack afterwards depends on the instruction. -@end deftp -@deftp {Scheme Variable} <glil-mv-call> nargs ra -Performs a multiple-value call. @var{ra} is a @code{<glil-label>} -corresponding to the multiple-value return address for the call. See -the notes on @code{mv-call} in @ref{Procedure Call and Return -Instructions}, for more information. -@end deftp -@deftp {Scheme Variable} <glil-prompt> label escape-only? -Push a dynamic prompt into the stack, with a handler at @var{label}. -@var{escape-only?} is a flag that is propagated to the prompt, -allowing an abort to avoid capturing a continuation in some cases. -@xref{Prompts}, for more information. -@end deftp - -Users may enter in GLIL at the REPL as well, though there is a bit -more bookkeeping to do: -@example -scheme@@(guile-user)> ,language glil -Happy hacking with Guile Lowlevel Intermediate Language (GLIL)! -To switch back, type `,L scheme'. -glil@@(guile-user)> (program () (std-prelude 0 0 #f) - (const 3) (call return 1)) -@result{} 3 -@end example +Here is an inventory of the kinds of expressions in Guile's CPS +language. Recall that all expressions are wrapped in a @code{$continue} +term which specifies their continuation. -Just as in all of Guile's compilers, an environment is passed to the -GLIL-to-object code compiler, and one is returned as well, along with -the object code. +@deftp {CPS Expression} $void +Continue with the unspecified value. +@end deftp -@node Assembly -@subsection Assembly +@deftp {CPS Expression} $const val +Continue with the constant value @var{val}. +@end deftp -Assembly is an S-expression-based, human-readable representation of -the actual bytecodes that will be emitted for the VM. As such, it is a -useful intermediate language both for compilation and for -decompilation. +@deftp {CPS Expression} $prim name +Continue with the procedure that implements the primitive operation +named by @var{name}. +@end deftp -Besides the fact that it is not a record-based language, assembly -differs from GLIL in four main ways: +@deftp {CPS Expression} $fun src meta free body +Continue with a procedure. @var{src} identifies the source information +for the procedure declaration, and @var{meta} is the metadata alist as +described above in Tree-IL's @code{<lambda>}. @var{free} is a list of +free variables accessed by the procedure. Early CPS uses an empty list +for @var{free}; only after closure conversion is it correctly populated. +Finally, @var{body} is the @code{$kentry} @code{$cont} of the procedure +entry. +@end deftp -@itemize -@item Labels have been resolved to byte offsets in the program. -@item Constants inside procedures have either been expressed as inline -instructions or cached in object arrays. -@item Procedures with metadata (source location information, liveness -extents, procedure names, generic properties, etc) have had their -metadata serialized out to thunks. -@item All expressions correspond directly to VM instructions -- i.e., -there is no @code{<glil-lexical>} which can be a ref or a set. -@end itemize +@deftp {CPS Expression} $call proc args +@deftpx {CPS Expression} $callk label proc args +Call @var{proc} with the arguments @var{args}, and pass all values to +the continuation. @var{proc} and the elements of the @var{args} list +should all be variable names. The continuation identified by the term's +@var{k} should be a @code{$kreceive} or a @code{$ktail} instance. + +@code{$callk} is for the case where the call target is known to be in +the same compilation unit. @var{label} should be some continuation +label, though it need not be in scope. In this case the @var{proc} is +simply an additional argument, since it is not used to determine the +call target at run-time. +@end deftp -Assembly is isomorphic to the bytecode that it compiles to. You can -compile to bytecode, then decompile back to assembly, and you have the -same assembly code. +@deftp {CPS Expression} $primcall name args +Perform the primitive operation identified by @code{name}, a well-known +symbol, passing it the arguments @var{args}, and pass all resulting +values to the continuation. The set of available primitives includes +all primitives known to Tree-IL and then some more; see the source code +for details. +@end deftp -The general form of assembly instructions is the following: +@deftp {CPS Expression} $values args +Pass the values named by the list @var{args} to the continuation. +@end deftp -@lisp -(@var{inst} @var{arg} ...) -@end lisp +@deftp {CPS Expression} $prompt escape? tag handler +Push a prompt on the stack identified by the variable name @var{tag}, +which may be escape-only if @var{escape?} is true, and continue with +zero values. If the body aborts to this prompt, control will proceed at +the continuation labelled @var{handler}, which should be a +@code{$kreceive} continuation. Prompts are later popped by +@code{pop-prompt} primcalls. +@end deftp -The @var{inst} names a VM instruction, and its @var{arg}s will be -embedded in the instruction stream. The easiest way to see assembly is -to play around with it at the REPL, as can be seen in this annotated -example: +The remaining element of the CPS language in Guile is the continuation. +In CPS, all continuations have unique labels. Since this aspect is +common to all continuation types, all continuations are contained in a +@code{$cont} instance: -@example -scheme@@(guile-user)> ,pp (compile '(+ 32 10) #:to 'assembly) -(load-program - ((:LCASE16 . 2)) ; Labels, unused in this case. - 8 ; Length of the thunk that was compiled. - (load-program ; Metadata thunk. - () - 17 - #f ; No metadata thunk for the metadata thunk. - (make-eol) - (make-eol) - (make-int8 2) ; Liveness extents, source info, and arities, - (make-int8 8) ; in a format that Guile knows how to parse. - (make-int8:0) - (list 0 3) - (list 0 1) - (list 0 3) - (return)) - (assert-nargs-ee/locals 0) ; Prologue. - (make-int8 32) ; Actual code starts here. - (make-int8 10) - (add) - (return)) -@end example +@deftp {CPS Continuation Wrapper} $cont k cont +Declare a continuation labelled @var{k}. All references to the +continuation will use this label. +@end deftp -Of course you can switch the REPL to assembly and enter in assembly -S-expressions directly, like with other languages, though it is more -difficult, given that the length fields have to be correct. +The most common kind of continuation binds some number of values, and +then evaluates a sub-term. @code{$kargs} is this kind of simple +@code{lambda}. -@node Bytecode and Objcode -@subsection Bytecode and Objcode +@deftp {CPS Continuation} $kargs names syms body +Bind the incoming values to the variables @var{syms}, with original +names @var{names}, and then evaluate the sub-term @var{body}. +@end deftp -Finally, the raw bytes. There are actually two different ``languages'' -here, corresponding to two different ways to represent the bytes. +Variable names (the names in the @var{syms} of a @code{$kargs}) should +be globally unique, and also disjoint from continuation labels. To bind +a value to a variable and then evaluate some term, you would continue +with the value to a @code{$kargs} that declares one variable. The bound +value would then be available for use within the body of the +@code{$kargs}. + +@deftp {CPS Continuation} $kif kt kf +Receive one value. If it is true for the purposes of Scheme, branch to +the continuation labelled @var{kt}, passing no values; otherwise, branch +to @var{kf}. +@end deftp -``Bytecode'' represents code as uniform byte vectors, useful for -structuring and destructuring code on the Scheme level. Bytecode is -the next step down from assembly: +For internal reasons, only certain terms may continue to a @code{$kif}. +Compiling @code{$kif} avoids allocating space for the test variable, so +it needs to be preceded by expressions that can test-and-branch without +temporary values. In practice this condition is true for +@code{$primcall}s to @code{null?}, @code{=}, and similar primitives that +have corresponding @code{br-if-@var{foo}} VM operations; see the source +code for full details. When in doubt, bind the test expression to a +variable, and continue to the @code{$kif} with a @code{$values} +expression. The optimizer should elide the @code{$values} if it is not +needed. + +Calls out to other functions need to be wrapped in a @code{$kreceive} +continuation in order to adapt the returned values to their uses in the +calling function, if any. + +@deftp {CPS Continuation} $kreceive arity k +Receive values on the stack. Parse them according to @var{arity}, and +then proceed with the parsed values to the @code{$kargs} continuation +labelled @var{k}. As a limitation specific to @code{$kreceive}, +@var{arity} may only contain required and rest arguments. +@end deftp -@example -scheme@@(guile-user)> (compile '(+ 32 10) #:to 'bytecode) -@result{} #vu8(8 0 0 0 25 0 0 0 ; Header. - 95 0 ; Prologue. - 10 32 10 10 148 66 17 ; Actual code. - 0 0 0 0 0 0 0 9 ; Metadata thunk. - 9 10 2 10 8 11 18 0 3 18 0 1 18 0 3 66) -@end example +@code{$arity} is a helper data structure used by @code{$kreceive} and +also by @code{$kclause}, described below. -``Objcode'' is bytecode, but mapped directly to a C structure, -@code{struct scm_objcode}: +@deftp {CPS Data} $arity req opt rest kw allow-other-keys? +A data type declaring an arity. @var{req} and @var{opt} are lists of +source names of required and optional arguments, respectively. +@var{rest} is either the source name of the rest variable, or @code{#f} +if this arity does not accept additional values. @var{kw} is a list of +the form @code{((@var{keyword} @var{name} @var{var}) ...)}, describing +the keyword arguments. @var{allow-other-keys?} is true if other keyword +arguments are allowed and false otherwise. -@example -struct scm_objcode @{ - scm_t_uint32 len; - scm_t_uint32 metalen; - scm_t_uint8 base[0]; -@}; -@end example +Note that all of these names with the exception of the @var{var}s in the +@var{kw} list are source names, not unique variable names. +@end deftp + +Additionally, there are three specific kinds of continuations that can +only be declared at function entries. + +@deftp {CPS Continuation} $kentry self tail clauses +Declare a function entry. @var{self} is a variable bound to the +procedure being called, and which may be used for self-references. +@var{tail} declares the @code{$cont} wrapping the @code{$ktail} for this +function, corresponding to the function's tail continuation. +@var{clauses} is a list of @code{$kclause} @code{$cont} instances. +@end deftp + +@deftp {CPS Continuation} $ktail +A tail continuation. +@end deftp -As one might imagine, objcode imposes a minimum length on the -bytecode. Also, the @code{len} and @code{metalen} fields are in native -endianness, which makes objcode (and bytecode) system-dependent. - -Objcode also has a couple of important efficiency hacks. First, -objcode may be mapped directly from disk, allowing compiled code to be -loaded quickly, often from the system's disk cache, and shared among -multiple processes. Secondly, objcode may be embedded in other -objcode, allowing procedures to have the text of other procedures -inlined into their bodies, without the need for separate allocation of -the code. Of course, the objcode object itself does need to be -allocated. - -Procedures related to objcode are defined in the @code{(system vm -objcode)} module. - -@deffn {Scheme Procedure} objcode? obj -@deffnx {C Function} scm_objcode_p (obj) -Returns @code{#f} if @var{obj} is object code, @code{#f} otherwise. +@deftp {CPS Continuation} $kclause arity cont +A clause of a function with a given arity. Applications of a function +with a compatible set of actual arguments will continue to @var{cont}, a +@code{$kargs} @code{$cont} instance representing the clause body. +@end deftp + + +@node Building CPS +@subsubsection Building CPS + +Unlike Tree-IL, the CPS language is built to be constructed and +deconstructed with abstract macros instead of via procedural +constructors or accessors, or instead of S-expression matching. + +Deconstruction and matching is handled adequately by the @code{match} +form from @code{(ice-9 match)}. @xref{Pattern Matching}. Construction +is handled by a set of mutually recursive builder macros: +@code{build-cps-term}, @code{build-cps-cont}, and @code{build-cps-exp}. + +In the following interface definitions, consider variables containing +@code{cont} to be recursively build by @code{build-cps-cont}, and +likewise for @code{term} and @code{exp}. Consider any other name to be +evaluated as a Scheme expression. Many of these forms recognize +@code{unquote} in some contexts, to splice in a previously-built value; +see the specifications below for full details. + +@deffn {Scheme Syntax} build-cps-term ,val +@deffnx {Scheme Syntax} build-cps-term ($letk (cont ...) term) +@deffnx {Scheme Syntax} build-cps-term ($letrec names syms funs term) +@deffnx {Scheme Syntax} build-cps-term ($continue k src exp) +@deffnx {Scheme Syntax} build-cps-exp ,val +@deffnx {Scheme Syntax} build-cps-exp ($void) +@deffnx {Scheme Syntax} build-cps-exp ($const val) +@deffnx {Scheme Syntax} build-cps-exp ($prim name) +@deffnx {Scheme Syntax} build-cps-exp ($fun src meta free body) +@deffnx {Scheme Syntax} build-cps-exp ($call proc (arg ...)) +@deffnx {Scheme Syntax} build-cps-exp ($call proc args) +@deffnx {Scheme Syntax} build-cps-exp ($primcall name (arg ...)) +@deffnx {Scheme Syntax} build-cps-exp ($primcall name args) +@deffnx {Scheme Syntax} build-cps-exp ($values (arg ...)) +@deffnx {Scheme Syntax} build-cps-exp ($values args) +@deffnx {Scheme Syntax} build-cps-exp ($prompt escape? tag handler) +@deffnx {Scheme Syntax} build-cps-cont ,val +@deffnx {Scheme Syntax} build-cps-cont (k ($kargs (name ...) (sym ...) term)) +@deffnx {Scheme Syntax} build-cps-cont (k ($kargs names syms term)) +@deffnx {Scheme Syntax} build-cps-cont (k ($kif kt kf)) +@deffnx {Scheme Syntax} build-cps-cont (k ($kreceive req rest kargs)) +@deffnx {Scheme Syntax} build-cps-cont (k ($kentry self tail-cont ,clauses)) +@deffnx {Scheme Syntax} build-cps-cont (k ($kentry self tail-cont (cont ...))) +@deffnx {Scheme Syntax} build-cps-cont (k ($kclause ,arity cont)) +@deffnx {Scheme Syntax} build-cps-cont (k ($kclause (req opt rest kw aok?) cont)) +Construct a CPS term, expression, or continuation. @end deffn -@deffn {Scheme Procedure} bytecode->objcode bytecode -@deffnx {C Function} scm_bytecode_to_objcode (bytecode) -Makes a bytecode object from @var{bytecode}, which should be a -bytevector. @xref{Bytevectors}. +There are a few more miscellaneous interfaces as well. + +@deffn {Scheme Procedure} make-arity req opt rest kw allow-other-keywords? +A procedural constructor for @code{$arity} objects. @end deffn -@deffn {Scheme Variable} load-objcode file -@deffnx {C Function} scm_load_objcode (file) -Load object code from a file named @var{file}. The file will be mapped -into memory via @code{mmap}, so this is a very fast operation. +@deffn {Scheme Syntax} let-gensyms (sym ...) body ... +Bind @var{sym...} to fresh names, and evaluate @var{body...}. +@end deffn -On disk, object code has an sixteen-byte cookie prepended to it, to -prevent accidental loading of arbitrary garbage. +@deffn {Scheme Syntax} rewrite-cps-term val (pat term) ... +@deffnx {Scheme Syntax} rewrite-cps-exp val (pat exp) ... +@deffnx {Scheme Syntax} rewrite-cps-cont val (pat cont) ... +Match @var{val} against the series of patterns @var{pat...}, using +@code{match}. The body of the matching clause should be a template in +the syntax of @code{build-cps-term}, @code{build-cps-exp}, or +@code{build-cps-cont}, respectively. @end deffn -@deffn {Scheme Variable} write-objcode objcode file -@deffnx {C Function} scm_write_objcode (objcode) -Write object code out to a file, prepending the sixteen-byte cookie. +@node Compiling CPS +@subsubsection Compiling CPS + +Compiling CPS in Guile has three phases: conversion, optimization, and +code generation. + +CPS conversion is the process of taking a higher-level language and +compiling it to CPS. Source languages can do this directly, or they can +convert to Tree-IL (which is probably easier) and let Tree-IL convert to +CPS later. Going through Tree-IL has the advantage of running Tree-IL +optimization passes, like partial evaluation. Also, the compiler from +Tree-IL to CPS handles assignment conversion, in which assigned local +variables (in Tree-IL, locals that are @code{<lexical-set>}) are +converted to being boxed values on the heap. @xref{Variables and the +VM}. + +After CPS conversion, Guile runs some optimization passes. The major +optimization performed on CPS is contification, in which functions that +are always called with the same continuation are incorporated directly +into a function's body. This opens up space for more optimizations, and +turns procedure calls into @code{goto}. It can also make loops out of +recursive function nests. + +At the time of this writing (2014), most high-level optimization in +Guile is done on Tree-IL. We would like to rewrite many of these passes +to operate on CPS instead, as it is easier to reason about CPS. + +The rest of the optimization passes are really cleanups and +canonicalizations. CPS spans the gap between high-level languages and +low-level bytecodes, which allows much of the compilation process to be +expressed as source-to-source transformations. Such is the case for +closure conversion, in which references to variables that are free in a +function are converted to closure references, and in which functions are +converted to closures. There are a few more passes to ensure that the +only primcalls left in the term are those that have a corresponding +instruction in the virtual machine, and that their continuations expect +the right number of values. + +Finally, the backend of the CPS compiler emits bytecode for each +function, one by one. To do so, it determines the set of live variables +at all points in the function. Using this liveness information, it +allocates stack slots to each variable, such that a variable can live in +one slot for the duration of its lifetime, without shuffling. (Of +course, variables with disjoint lifetimes can share a slot.) Finally +the backend emits code, typically just one VM instruction, for each +continuation in the function. + + +@node Bytecode +@subsection Bytecode + +As mentioned before, Guile compiles all code to bytecode, and that +bytecode is contained in ELF images. @xref{Object File Format}, for +more on Guile's use of ELF. + +To produce a bytecode image, Guile provides an assembler and a linker. + +The assembler, defined in the @code{(system vm assembler)} module, has a +relatively straightforward imperative interface. It provides a +@code{make-assembler} function to instantiate an assembler and a set of +@code{emit-@var{inst}} procedures to emit instructions of each kind. + +The @code{emit-@var{inst}} procedures are actually generated at +compile-time from a machine-readable description of the VM. With a few +exceptions for certain operand types, each operand of an emit procedure +corresponds to an operand of the corresponding instruction. + +Consider @code{vector-length}, from @pxref{Miscellaneous Instructions}. +It is documented as: + +@deftypefn Instruction {} vector-length u12:@var{dst} u12:@var{src} +@end deftypefn + +Therefore the emit procedure has the form: + +@deffn {Scheme Procedure} emit-vector-length asm dst src @end deffn -@deffn {Scheme Variable} objcode->bytecode objcode -@deffnx {C Function} scm_objcode_to_bytecode (objcode) -Copy object code out to a bytevector for analysis by Scheme. +All emit procedure take the assembler as their first argument, and +return no useful values. + +The argument types depend on the operand types. @xref{Instruction Set}. +Most are integers within a restricted range, though labels are generally +expressed as opaque symbols. + +There are a few macro-instructions as well. + +@deffn {Scheme Procedure} emit-label asm label +Define a label at the current program point. +@end deffn + +@deffn {Scheme Procedure} emit-source asm source +Associate @var{source} with the current program point. +@end deffn + +@deffn {Scheme Procedure} emit-cache-current-module! asm module scope +@deffnx {Scheme Procedure} emit-cached-toplevel-box asm dst scope sym bound? +@deffnx {Scheme Procedure} emit-cached-module-box asm dst module-name sym public? bound? +Macro-instructions to implement caching of top-level variables. The +first takes the current module, in the slot @var{module}, and associates +it with a cache location identified by @var{scope}. The second takes a +@var{scope}, and resolves the variable. @xref{Top-Level Environment +Instructions}. The last does not need a cached module, rather taking +the module name directly. +@end deffn + +@deffn {Scheme Procedure} emit-load-constant asm dst constant +Load the Scheme datum @var{constant} into @var{dst}. @end deffn -The following procedure is actually in @code{(system vm program)}, but -we'll mention it here: +@deffn {Scheme Procedure} emit-begin-program asm label properties +@deffnx {Scheme Procedure} emit-end-program asm +Delimit the bounds of a procedure, with the given @var{label} and the +metadata @var{properties}. +@end deffn + +@deffn {Scheme Procedure} emit-load-static-procedure asm dst label +Load a procedure with the given @var{label} into local @var{dst}. This +macro-instruction should only be used with procedures without free +variables -- procedures that are not closures. +@end deffn + +@deffn {Scheme Procedure} emit-begin-standard-arity asm req nlocals alternate +@deffnx {Scheme Procedure} emit-begin-opt-arity asm req opt rest nlocals alternate +@deffnx {Scheme Procedure} emit-begin-kw-arity asm req opt rest kw-indices allow-other-keys? nlocals alternate +@deffnx {Scheme Procedure} emit-end-arity asm +Delimit a clause of a procedure. +@end deffn + +@deffn {Scheme Procedure} emit-br-if-symbol asm slot invert? label +@deffnx {Scheme Procedure} emit-br-if-variable asm slot invert? label +@deffnx {Scheme Procedure} emit-br-if-vector asm slot invert? label +@deffnx {Scheme Procedure} emit-br-if-string asm slot invert? label +@deffnx {Scheme Procedure} emit-br-if-bytevector asm slot invert? label +@deffnx {Scheme Procedure} emit-br-if-bitvector asm slot invert? label +TC7-specific test-and-branch instructions. The TC7 is a 7-bit code that +is part of a heap object's type. @xref{The SCM Type in Guile}. Also, +@xref{Branch Instructions}. +@end deffn -@deffn {Scheme Variable} make-program objcode objtable [free-vars=#f] -@deffnx {C Function} scm_make_program (objcode, objtable, free_vars) -Load up object code into a Scheme program. The resulting program will -have @var{objtable} as its object table, which should be a vector or -@code{#f}, and will capture the free variables from @var{free-vars}. +The linker is a complicated beast. Hackers interested in how it works +would do well do read Ian Lance Taylor's series of articles on linkers. +Searching the internet should find them easily. From the user's +perspective, there is only one knob to control: whether the resulting +image will be written out to a file or not. If the user passes +@code{#:to-file? #t} as part of the compiler options (@pxref{The Scheme +Compiler}), the linker will align the resulting segments on page +boundaries, and otherwise not. + +@deffn {Scheme Procedure} link-assembly asm #:page-aligned?=#t +Link an ELF image, and return the bytevector. If @var{page-aligned?} is +true, Guile will align the segments with different permissions on +page-sized boundaries, in order to maximize code sharing between +different processes. Otherwise, padding is minimized, to minimize +address space consumption. @end deffn -Object code from a file may be disassembled at the REPL via the -meta-command @code{,disassemble-file}, abbreviated as @code{,xx}. -Programs may be disassembled via @code{,disassemble}, abbreviated as -@code{,x}. +To write an image to disk, just use @code{put-bytevector} from +@code{(ice-9 binary-ports)}. Compiling object code to the fake language, @code{value}, is performed via loading objcode into a program, then executing that thunk with respect to the compilation environment. Normally the environment -propagates through the compiler transparently, but users may specify -the compilation environment manually as well, as a module. +propagates through the compiler transparently, but users may specify the +compilation environment manually as well, as a module. Procedures to +load images can be found in the @code{(system vm loader)} module: + +@lisp +(use-modules (system vm loader)) +@end lisp + +@deffn {Scheme Variable} load-thunk-from-file file +@deffnx {C Function} scm_load_thunk_from_file (file) +Load object code from a file named @var{file}. The file will be mapped +into memory via @code{mmap}, so this is a very fast operation. +@end deffn + +@deffn {Scheme Variable} load-thunk-from-memory bv +@deffnx {C Function} scm_load_thunk_from_memory (bv) +Load object code from a bytevector. The data will be copied out of the +bytevector in order to ensure proper alignment of embedded Scheme +values. +@end deffn + +Additionally there are procedures to find the ELF image for a given +pointer, or to list all mapped ELF images: + +@deffn {Scheme Variable} find-mapped-elf-image ptr +Given the integer value @var{ptr}, find and return the ELF image that +contains that pointer, as a bytevector. If no image is found, return +@code{#f}. This routine is mostly used by debuggers and other +introspective tools. +@end deffn + +@deffn {Scheme Variable} all-mapped-elf-images +Return all mapped ELF images, as a list of bytevectors. +@end deffn @node Writing New High-Level Languages diff --git a/doc/ref/guile-invoke.texi b/doc/ref/guile-invoke.texi index 95493dd00..d233ce653 100644 --- a/doc/ref/guile-invoke.texi +++ b/doc/ref/guile-invoke.texi @@ -335,9 +335,7 @@ explicitly enable it by setting the variable to @code{1}. Usually, installing the current locale is the right thing to do. It allows Guile to correctly parse and print strings with non-ASCII -characters. However, for compatibility with previous Guile 2.0 -releases, this option is off by default. The next stable release series -of Guile (the 2.2 series) will install locales by default. +characters. Therefore, this option is on by default. @item GUILE_STACK_SIZE @vindex GUILE_STACK_SIZE @@ -367,7 +365,7 @@ Here is an example using the Bash shell that adds the current directory, @example $ export GUILE_LOAD_COMPILED_PATH=".:../my-library" $ guile -c '(display %load-compiled-path) (newline)' -(. ../my-library /usr/local/lib/guile/2.0/ccache) +(. ../my-library /usr/local/lib/guile/2.2/ccache) @end example @item GUILE_LOAD_PATH @@ -386,8 +384,8 @@ directory to @code{%load-path}, and adds the relative directory @example $ env GUILE_LOAD_PATH=".:...:../srfi" \ guile -c '(display %load-path) (newline)' -(. /usr/local/share/guile/2.0 \ -/usr/local/share/guile/site/2.0 \ +(. /usr/local/share/guile/2.2 \ +/usr/local/share/guile/site/2.2 \ /usr/local/share/guile/site \ /usr/local/share/guile \ ../srfi) diff --git a/doc/ref/guile.texi b/doc/ref/guile.texi index 5b368df83..5f21188fa 100644 --- a/doc/ref/guile.texi +++ b/doc/ref/guile.texi @@ -309,6 +309,7 @@ available through both Scheme and C interfaces. * Input and Output:: Ports, reading and writing. * Regular Expressions:: Pattern matching and substitution. * LALR(1) Parsing:: Generating LALR(1) parsers. +* PEG Parsing:: Parsing Expression Grammars. * Read/Load/Eval/Compile:: Reading and evaluating Scheme code. * Memory Management:: Memory management and garbage collection. * Modules:: Designing reusable code libraries. @@ -338,6 +339,7 @@ available through both Scheme and C interfaces. @include api-io.texi @include api-regex.texi @include api-lalr.texi +@include api-peg.texi @include api-evaluation.texi @include api-memory.texi @include api-modules.texi diff --git a/doc/ref/history.texi b/doc/ref/history.texi index a617cf7f8..f7fc4cbf2 100644 --- a/doc/ref/history.texi +++ b/doc/ref/history.texi @@ -1,6 +1,6 @@ @c -*-texinfo-*- @c This is part of the GNU Guile Reference Manual. -@c Copyright (C) 2008, 2010, 2011 +@c Copyright (C) 2008, 2010, 2011, 2013 @c Free Software Foundation, Inc. @c See the file guile.texi for copying conditions. @@ -211,6 +211,13 @@ via Geiser. Guile caught up to features found in a number of other Schemes: SRFI-18 threads, module-hygienic macros, a profiler, tracer, and debugger, SSAX XML integration, bytevectors, a dynamic FFI, delimited continuations, module versions, and partial support for R6RS. + +@item 2.2 --- mid-2014 +The virtual machine and introduced in 2.0 was completely rewritten, +along with much of the compiler and toolchain. This speeds up many +Guile programs as well as reducing startup time and memory usage. A PEG +parser toolkit was added, making it easier to write other language +frontends. @end table @node Status @@ -250,19 +257,13 @@ than in other languages. These days it is possible to write extensible applications almost entirely from high-level languages, through byte-code and native compilation, speed gains in the underlying hardware, and foreign call -interfaces in the high-level language. Smalltalk systems are like -this, as are Common Lisp-based systems. While there already are a -number of pure-Guile applications out there, users still need to drop -down to C for some tasks: interfacing to system libraries that don't -have prebuilt Guile interfaces, and for some tasks requiring high -performance. - -The addition of the virtual machine in Guile 2.0, together with the -compiler infrastructure, should go a long way to addressing the speed -issues. But there is much optimization to be done. Interested -contributors will find lots of delightful low-hanging fruit, from -simple profile-driven optimization to hacking a just-in-time compiler -from VM bytecode to native code. +interfaces in the high-level language. Smalltalk systems are like this, +as are Common Lisp-based systems. While there already are a number of +pure-Guile applications out there, users still need to drop down to C +for some tasks: interfacing to system libraries that don't have prebuilt +Guile interfaces, and for some tasks requiring high performance. Native +ahead-of-time compilation, planned for Guile 3.0, should help with +this. Still, even with an all-Guile application, sometimes you want to provide an opportunity for users to extend your program from a @@ -270,19 +271,17 @@ language with a syntax that is closer to C, or to Python. Another interesting idea to consider is compiling e.g.@: Python to Guile. It's not that far-fetched of an idea: see for example IronPython or JRuby. -And then there's Emacs itself. Though there is a somewhat-working Emacs -Lisp language frontend for Guile, it cannot yet execute all of Emacs -Lisp. A serious integration of Guile with Emacs would replace the Elisp -virtual machine with Guile, and provide the necessary C shims so that -Guile could emulate Emacs' C API. This would give lots of exciting -things to Emacs: native threads, a real object system, more -sophisticated types, cleaner syntax, and access to all of the Guile -extensions. +And then there's Emacs itself. Guile's Emacs Lisp support has reached +an excellent level of correctness, robustness, and speed. However there +is still work to do to finish its integration into Emacs itself. This +will give lots of exciting things to Emacs: native threads, a real +object system, more sophisticated types, cleaner syntax, and access to +all of the Guile extensions. Finally, there is another axis of crystallization, the axis between -different Scheme implementations. Guile does not yet support the -latest Scheme standard, R6RS, and should do so. Like all standards, -R6RS is imperfect, but supporting it will allow more code to run on -Guile without modification, and will allow Guile hackers to produce -code compatible with other schemes. Help in this regard would be much +different Scheme implementations. Guile does not yet support the latest +Scheme standard, R7RS, and should do so. Like all standards, R7RS is +imperfect, but supporting it will allow more code to run on Guile +without modification, and will allow Guile hackers to produce code +compatible with other schemes. Help in this regard would be much appreciated. diff --git a/doc/ref/libguile-concepts.texi b/doc/ref/libguile-concepts.texi index ea2bdbe9f..9e2eb7503 100644 --- a/doc/ref/libguile-concepts.texi +++ b/doc/ref/libguile-concepts.texi @@ -1,7 +1,7 @@ @c -*-texinfo-*- @c This is part of the GNU Guile Reference Manual. -@c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2010, 2013, 2014 -@c Free Software Foundation, Inc. +@c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2010, +@c 2011, 2013, 2014 Free Software Foundation, Inc. @c See the file guile.texi for copying conditions. @node General Libguile Concepts @@ -445,16 +445,18 @@ that are stored in local variables. When a thread puts itself into guile mode for the first time, it gets a Scheme representation and is listed by @code{all-threads}, for example. -Threads in guile mode can block (e.g., do blocking I/O) without causing any -problems@footnote{In Guile 1.8, a thread blocking in guile mode would prevent -garbage collection to occur. Thus, threads had to leave guile mode whenever -they could block. This is no longer needed with Guile 2.0.}; temporarily -leaving guile mode with @code{scm_without_guile} before blocking slightly -improves GC performance, though. For some common blocking operations, Guile -provides convenience functions. For example, if you want to lock a pthread -mutex while in guile mode, you might want to use @code{scm_pthread_mutex_lock} -which is just like @code{pthread_mutex_lock} except that it leaves guile mode -while blocking. +Threads in guile mode can block (e.g., do blocking I/O) without causing +any problems@footnote{In Guile 1.8, a thread blocking in guile mode +would prevent garbage collection to occur. Thus, threads had to leave +guile mode whenever they could block. This is no longer needed with +Guile 2.@var{x}.}; temporarily leaving guile mode with +@code{scm_without_guile} before blocking slightly improves GC +performance, though. For some common blocking operations, Guile +provides convenience functions. For example, if you want to lock a +pthread mutex while in guile mode, you might want to use +@code{scm_pthread_mutex_lock} which is just like +@code{pthread_mutex_lock} except that it leaves guile mode while +blocking. All libguile functions are (intended to be) robust in the face of diff --git a/doc/ref/libguile-parallel.texi b/doc/ref/libguile-parallel.texi index 37a713929..a0e1ea978 100644 --- a/doc/ref/libguile-parallel.texi +++ b/doc/ref/libguile-parallel.texi @@ -1,6 +1,6 @@ @c -*-texinfo-*- @c This is part of the GNU Guile Reference Manual. -@c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2010, 2011 +@c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2010, 2011, 2013 @c Free Software Foundation, Inc. @c See the file guile.texi for copying conditions. @@ -11,10 +11,10 @@ @cindex effective version Guile provides strong API and ABI stability guarantees during stable -series, so that if a user writes a program against Guile version 2.0.3, -it will be compatible with some future version 2.0.7. We say in this -case that 2.0 is the @dfn{effective version}, composed of the major and -minor versions, in this case 2 and 0. +series, so that if a user writes a program against Guile version 2.2.3, +it will be compatible with some future version 2.2.7. We say in this +case that 2.2 is the @dfn{effective version}, composed of the major and +minor versions, in this case 2 and 2. Users may install multiple effective versions of Guile, with each version's headers, libraries, and Scheme files under their own diff --git a/doc/ref/posix.texi b/doc/ref/posix.texi index 7ca2fb01b..570102c27 100644 --- a/doc/ref/posix.texi +++ b/doc/ref/posix.texi @@ -1870,10 +1870,11 @@ the integer process ID of the child. Note that it is unsafe to fork a process that has multiple threads running, as only the thread that calls @code{primitive-fork} will persist in the child. Any resources that other threads held, such as -locked mutexes or open file descriptors, are lost. Indeed, @acronym{POSIX} -specifies that only async-signal-safe procedures are safe to call after -a multithreaded fork, which is a very limited set. Guile issues a -warning if it detects a fork from a multi-threaded program. +locked mutexes or open file descriptors, are lost. Indeed, +@acronym{POSIX} specifies that only async-signal-safe procedures are +safe to call after a multithreaded fork, which is a very limited set. +Guile issues a warning if it detects a fork from a multi-threaded +program. If you are going to @code{exec} soon after forking, the procedures in @code{(ice-9 popen)} may be useful to you, as they fork and exec within @@ -2129,14 +2130,17 @@ the C level (@pxref{Blocking}). @end deffn @deffn {Scheme Procedure} getitimer which_timer -@deffnx {Scheme Procedure} setitimer which_timer interval_seconds interval_microseconds periodic_seconds periodic_microseconds +@deffnx {Scheme Procedure} setitimer which_timer interval_seconds interval_microseconds value_seconds value_microseconds @deffnx {C Function} scm_getitimer (which_timer) -@deffnx {C Function} scm_setitimer (which_timer, interval_seconds, interval_microseconds, periodic_seconds, periodic_microseconds) -Get or set the periods programmed in certain system timers. These -timers have a current interval value which counts down and on reaching -zero raises a signal. An optional periodic value can be set to -restart from there each time, for periodic operation. -@var{which_timer} is one of the following values +@deffnx {C Function} scm_setitimer (which_timer, interval_seconds, interval_microseconds, value_seconds, value_microseconds) +Get or set the periods programmed in certain system timers. + +These timers have two settings. The first setting, the interval, is the +value at which the timer will be reset when the current timer expires. +The second is the current value of the timer, indicating when the next +expiry will be signalled. + +@var{which_timer} is one of the following values: @defvar ITIMER_REAL A real-time timer, counting down elapsed real time. At zero it raises @@ -2158,21 +2162,20 @@ This timer is intended for profiling where a program is spending its time (by looking where it is when the timer goes off). @end defvar -@code{getitimer} returns the current timer value and its programmed -restart value, as a list containing two pairs. Each pair is a time in -seconds and microseconds: @code{((@var{interval_secs} -. @var{interval_usecs}) (@var{periodic_secs} -. @var{periodic_usecs}))}. +@code{getitimer} returns the restart timer value and its current value, +as a list containing two pairs. Each pair is a time in seconds and +microseconds: @code{((@var{interval_secs} . @var{interval_usecs}) +(@var{value_secs} . @var{value_usecs}))}. @code{setitimer} sets the timer values similarly, in seconds and -microseconds (which must be integers). The periodic value can be zero +microseconds (which must be integers). The interval value can be zero to have the timer run down just once. The return value is the timer's previous setting, in the same form as @code{getitimer} returns. @example (setitimer ITIMER_REAL - 5 500000 ;; first SIGALRM in 5.5 seconds time - 2 0) ;; then repeat every 2 seconds + 5 500000 ;; Raise SIGALRM every 5.5 seconds + 2 0) ;; with the first SIGALRM in 2 seconds @end example Although the timers are programmed in microseconds, the actual diff --git a/doc/ref/srfi-modules.texi b/doc/ref/srfi-modules.texi index b1776c6a0..882b7d371 100644 --- a/doc/ref/srfi-modules.texi +++ b/doc/ref/srfi-modules.texi @@ -152,6 +152,7 @@ guile-2 ;; starting from Guile 2.x r5rs srfi-0 srfi-4 +srfi-6 srfi-13 srfi-14 srfi-16 @@ -188,8 +189,8 @@ how to load it with the Guile mechanism. @cindex @code{guile-2} SRFI-0 feature @cindex portability between 2.0 and older versions Likewise, testing the @code{guile-2} feature allows code to be portable -between Guile 2.0 and previous versions of Guile. For instance, it -makes it possible to write code that accounts for Guile 2.0's compiler, +between Guile 2.@var{x} and previous versions of Guile. For instance, it +makes it possible to write code that accounts for Guile 2.@var{x}'s compiler, yet be correctly interpreted on 1.8 and earlier versions: @example @@ -1802,19 +1803,11 @@ uniform numeric vector, it is returned unchanged. @cindex SRFI-6 SRFI-6 defines the procedures @code{open-input-string}, -@code{open-output-string} and @code{get-output-string}. - -Note that although versions of these procedures are included in the -Guile core, the core versions are not fully conformant with SRFI-6: -attempts to read or write characters that are not supported by the -current @code{%default-port-encoding} will fail. - -We therefore recommend that you import this module, which supports all -characters: - -@example -(use-modules (srfi srfi-6)) -@end example +@code{open-output-string} and @code{get-output-string}. These +procedures are included in the Guile core, so using this module does not +make any difference at the moment. But it is possible that support for +SRFI-6 will be factored out of the core library in the future, so using +this module does not hurt, after all. @node SRFI-8 @subsection SRFI-8 - receive diff --git a/doc/ref/vm.texi b/doc/ref/vm.texi index 9936ad97d..468ac65e3 100644 --- a/doc/ref/vm.texi +++ b/doc/ref/vm.texi @@ -1,6 +1,6 @@ @c -*-texinfo-*- @c This is part of the GNU Guile Reference Manual. -@c Copyright (C) 2008,2009,2010,2013 +@c Copyright (C) 2008,2009,2010,2011,2013 @c Free Software Foundation, Inc. @c See the file guile.texi for copying conditions. @@ -26,6 +26,7 @@ machine. * Stack Layout:: * Variables and the VM:: * VM Programs:: +* Object File Format:: * Instruction Set:: @end menu @@ -38,7 +39,7 @@ 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 +performed 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 -- @@ -79,9 +80,11 @@ 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! +code. The downside is that the interpreter in Guile 2.2 is still slower +than the interpreter in 1.8. We hope the that the compiler's speed makes +up for the loss. In any case, once we have native compilation for +Scheme code, we expect the new self-hosted interpreter to beat the old +hand-tuned C implementation. Also note that this decision to implement a bytecode compiler does not preclude native compilation. We can compile from bytecode to native @@ -91,23 +94,24 @@ possibilities are discussed in @ref{Extending the Compiler}. @node VM Concepts @subsection 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. +Compiled code is run by a virtual machine (VM). Each thread has its own +VM. The virtual machine executes the sequence of instructions in a +procedure. -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. +Each VM instruction starts by indicating which operation it is, and then +follows by encoding its source and destination operands. Each procedure +declares that it has some number of local variables, including the +function arguments. These local variables form the available operands +of the procedure, and are accessed by index. -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. +The local variables for a procedure are stored on a stack. Calling a +procedure typically enlarges the stack, and returning from a procedure +shrinks it. Stack memory is exclusive to the virtual machine that owns +it. -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 @code{cons}, etc. +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. The registers that a VM has are as follows: @@ -117,110 +121,59 @@ The registers that a VM has are as follows: @item fp - Frame pointer @end itemize -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. - -@c wingo: The following is true, but I don't know in what context to -@c describe it. A documentation FIXME. - -@c A VM may have one of three engines: reckless, regular, or debugging. -@c Reckless engine is fastest but dangerous. Regular engine is normally -@c fail-safe and reasonably fast. Debugging engine is safest and -@c functional but very slow. - -@c (Actually we have just a regular and a debugging engine; normally -@c we use the latter, it's almost as fast as the ``regular'' engine.) +In other architectures, the instruction pointer is sometimes called the +``program counter'' (pc). This set of registers is pretty typical for +virtual machines; their exact meanings in the context of Guile's VM are +described in the next section. @node Stack Layout @subsection 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). +The stack of Guile's virtual machine is composed of @dfn{frames}. Each +frame corresponds to the application of one compiled procedure, and +contains storage space for arguments, local variables, and some +bookkeeping information (such as what to do after the frame is +finished). 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, @pxref{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: +The structure of the top stack frame is as follows: @example - Stack + /------------------\ <- top of stack + | Local N-1 | <- sp | ... | - | Intermed. val. 0 | <- fp + bp->nargs + bp->nlocs = SCM_FRAME_UPPER_ADDRESS (fp) + | Local 1 | + | Local 0 | <- fp = SCM_FRAME_LOCALS_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) + | Dynamic link | <- fp - 2 = SCM_FRAME_LOWER_ADDRESS (fp) +==================+ - | | + | | <- fp - 3 = SCM_FRAME_PREVIOUS_SP (fp) @end example -In the above drawing, the stack grows upward. The intermediate values -stored in the application of this frame are stored above -@code{SCM_FRAME_UPPER_ADDRESS (fp)}. @code{bp} refers to the -@code{struct scm_objcode} data associated with the program at -@code{fp - 1}. @code{nargs} and @code{nlocs} are properties of the -compiled procedure, which will be discussed later. - -The individual fields of the frame are as follows: - -@table @asis -@item Return address -The @code{ip} that was in effect before this program was applied. When -we return from this activation frame, we will jump back to this -@code{ip}. - -@item MV return address -The @code{ip} to return to if this application returns multiple -values. For continuations that only accept one value, this value will -be @code{NULL}; for others, it will be an @code{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. - -@item Dynamic link -This is the @code{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. - -@item Local variable @var{n} -Lambda-local variables that are all allocated as part of the frame. -This makes access to variables very cheap. - -@item Argument @var{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. - -@item Program -This is the program being applied. For more information on how -programs are implemented, @xref{VM Programs}. -@end table +In the above drawing, the stack grows upward. Usually the procedure +being applied is in local 0, followed by the arguments from local 1. +After that are enough slots to store the various lexically-bound and +temporary values that are needed in the function's application. + +The @dfn{return address} is the @code{ip} that was in effect before this +program was applied. When we return from this activation frame, we will +jump back to this @code{ip}. Likewise, the @dfn{dynamic link} is the +@code{fp} in effect before this program was applied. + +To prepare for a non-tail application, Guile's VM will emit code that +shuffles the function to apply and its arguments into appropriate stack +slots, with two free slots below them. The call then initializes those +free slots with the current @code{ip} and @code{fp}, and updates +@code{ip} to point to the function entry, and @code{fp} to point to the +new call frame. + +In this way, the dynamic link links the current frame to the previous +frame. Computing a stack trace involves traversing these frames. @node Variables and the VM @subsection Variables and the VM @@ -232,16 +185,18 @@ Consider the following Scheme code as an example: (lambda (b) (list foo a b))) @end example -Within the lambda expression, @code{foo} is a top-level variable, @code{a} is a -lexically captured variable, and @code{b} is a local variable. +Within the lambda expression, @code{foo} is a top-level variable, +@code{a} is a lexically captured variable, and @code{b} is a local +variable. -Another way to refer to @code{a} and @code{b} is to say that @code{a} -is a ``free'' variable, since it is not defined within the lambda, and +Another way to refer to @code{a} and @code{b} is to say that @code{a} is +a ``free'' variable, since it is not defined within the lambda, and @code{b} is a ``bound'' variable. These are the terms used in the -@dfn{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. +@dfn{lambda calculus}, a mathematical notation for describing functions. +The lambda calculus is useful because it is a language in which to +reason precisely about functions and variables. 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 @dfn{closure}---is created, it copies @@ -275,33 +230,30 @@ lexically bound in this example. @subsection 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 @code{(system vm -program)}. @xref{Compiled Procedures}, for a full API reference. - -@cindex object table -@cindex object array -The object array of a compiled procedure, also known as the -@dfn{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 @code{load-program}. -@xref{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 @code{toplevel-ref} -instruction, which uses the object vector, and are almost as fast as -local variable references. +first compiled to bytecode. Then that bytecode 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 and +a reference to any captured lexical variables. In addition, when a +procedure is compiled, it has associated metadata written to side +tables, for instance a line number mapping, or its docstring. You can +pick apart these pieces with the accessors in @code{(system vm +program)}. @xref{Compiled Procedures}, for a full API reference. + +A procedure may reference data that was statically allocated when the +procedure was compiled. For example, a pair of immediate objects +(@pxref{Immediate objects}) can be allocated directly in the memory +segment that contains the compiled bytecode, and accessed directly by +the bytecode. + +Another use for statically allocated data is to serve as a cache for a +bytecode. Top-level variable lookups are handled in this way. If the +@code{toplevel-box} instruction finds that it does not have a cached +variable for a top-level reference, it accesses other static data to +resolve the reference, and fills in the cache slot. Thereafter all +access to the variable goes through the cache cell. The variable's +value may change in the future, but the variable itself will not. We can see how these concepts tie together by disassembling the @code{foo} function we defined earlier to see what is going on: @@ -309,53 +261,229 @@ We can see how these concepts tie together by disassembling the @smallexample 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 foo (a)> at #x203be34: + + 0 (assert-nargs-ee/locals 2 1) ;; 1 arg, 1 local at (unknown file):1:0 + 1 (make-closure 2 6 1) ;; anonymous procedure at #x203be50 (1 free var) + 4 (free-set! 2 1 0) ;; free var 0 + 6 (return 2) ---------------------------------------- -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) +Disassembly of anonymous procedure at #x203be50: + + 0 (assert-nargs-ee/locals 2 3) ;; 1 arg, 3 locals at (unknown file):1:0 + 1 (toplevel-box 2 73 57 71 #t) ;; `foo' + 6 (box-ref 2 2) + 7 (make-short-immediate 3 772) ;; () + 8 (cons 3 1 3) + 9 (free-ref 4 0 0) ;; free var 0 + 11 (cons 3 4 3) + 12 (cons 2 2 3) + 13 (return 2) @end smallexample -First there's some prelude, where @code{foo} checks that it was called with only -1 argument. Then at @code{ip} 2, we load up the compiled lambda. @code{Ip} 4 -loads up `a', so that it can be captured into a closure by at @code{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. @xref{Top-Level Environment Instructions}, -for more details. - -Then we see a reference to a free variable, corresponding to @code{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 @code{b}, then the @code{list} opcode, an inline implementation of the -@code{list} scheme routine. +First there's some prelude, where @code{foo} checks that it was called +with only 1 argument. Then at @code{ip} 1, we allocate a new closure +and store it in slot 2. The `6' in the @code{(make-closure 2 6 1)} is a +relative offset from the instruction pointer of the code for the +closure. + +A closure is code with data. We already have the code part initialized; +what remains is to set the data. @code{Ip} 4 initializes free variable +0 in the new closure with the value from local variable 1, which +corresponds to the first argument of @code{foo}: `a'. Finally we return +the closure. + +The second stanza disassembles the code for the closure. After the +prelude, we load the variable for the toplevel variable @code{foo} into +local variable 2. This lookup occurs lazily, the first time the +variable is actually referenced, and the location of the lookup is +cached so that future references are very cheap. @xref{Top-Level +Environment Instructions}, for more details. The @code{box-ref} +dereferences the variable cell, replacing the contents of local 2. + +What follows is a sequence of conses to build up the result list. +@code{Ip} 7 makes the tail of the list. @code{Ip} 8 conses on the value +in local 1, corresponding to the first argument to the closure: `b'. +@code{Ip} 9 loads free variable 0 of local 0 -- the procedure being +called -- into slot 4, then @code{ip} 11 conses it onto the list. +Finally we cons local 2, containing the @code{foo} toplevel, onto the +front of the list, and we return it. + + +@node Object File Format +@subsection Object File Format + +To compile a file to disk, we need a format in which to write the +compiled code to disk, and later load it into Guile. A good @dfn{object +file format} has a number of characteristics: + +@itemize +@item Above all else, it should be very cheap to load a compiled file. +@item It should be possible to statically allocate constants in the +file. For example, a bytevector literal in source code can be emitted +directly into the object file. +@item The compiled file should enable maximum code and data sharing +between different processes. +@item The compiled file should contain debugging information, such as +line numbers, but that information should be separated from the code +itself. It should be possible to strip debugging information if space +is tight. +@end itemize + +These characteristics are not specific to Scheme. Indeed, mainstream +languages like C and C++ have solved this issue many times in the past. +Guile builds on their work by adopting ELF, the object file format of +GNU and other Unix-like systems, as its object file format. Although +Guile uses ELF on all platforms, we do not use platform support for ELF. +Guile implements its own linker and loader. The advantage of using ELF +is not sharing code, but sharing ideas. ELF is simply a well-designed +object file format. + +An ELF file has two meta-tables describing its contents. The first +meta-table is for the loader, and is called the @dfn{program table} or +sometimes the @dfn{segment table}. The program table divides the file +into big chunks that should be treated differently by the loader. +Mostly the difference between these @dfn{segments} is their +permissions. + +Typically all segments of an ELF file are marked as read-only, except +that part that represents modifiable static data or static data that +needs load-time initialization. Loading an ELF file is as simple as +mmapping the thing into memory with read-only permissions, then using +the segment table to mark a small sub-region of the file as writable. +This writable section is typically added to the root set of the garbage +collector as well. + +One ELF segment is marked as ``dynamic'', meaning that it has data of +interest to the loader. Guile uses this segment to record the Guile +version corresponding to this file. There is also an entry in the +dynamic segment that points to the address of an initialization thunk +that is run to perform any needed link-time initialization. (This is +like dynamic relocations for normal ELF shared objects, except that we +compile the relocations as a procedure instead of having the loader +interpret a table of relocations.) Finally, the dynamic segment marks +the location of the ``entry thunk'' of the object file. This thunk is +returned to the caller of @code{load-thunk-from-memory} or +@code{load-thunk-from-file}. When called, it will execute the ``body'' +of the compiled expression. + +The other meta-table in an ELF file is the @dfn{section table}. Whereas +the program table divides an ELF file into big chunks for the loader, +the section table specifies small sections for use by introspective +tools like debuggers or the like. One segment (program table entry) +typically contains many sections. There may be sections outside of any +segment, as well. + +Typical sections in a Guile @code{.go} file include: + +@table @code +@item .rtl-text +Bytecode. +@item .data +Data that needs initialization, or which may be modified at runtime. +@item .rodata +Statically allocated data that needs no run-time initialization, and +which therefore can be shared between processes. +@item .dynamic +The dynamic section, discussed above. +@item .symtab +@itemx .strtab +A table mapping addresses in the @code{.rtl-text} to procedure names. +@code{.strtab} is used by @code{.symtab}. +@item .guile.procprops +@itemx .guile.arities +@itemx .guile.arities.strtab +@itemx .guile.docstrs +@itemx .guile.docstrs.strtab +Side tables of procedure properties, arities, and docstrings. +@item .debug_info +@itemx .debug_abbrev +@itemx .debug_str +@itemx .debug_loc +@itemx .debug_line +Debugging information, in DWARF format. See the DWARF specification, +for more information. +@item .shstrtab +Section name string table. +@end table + +For more information, see @uref{http://linux.die.net/man/5/elf,,the +elf(5) man page}. See @uref{http://dwarfstd.org/,the DWARF +specification} for more on the DWARF debugging format. Or if you are an +adventurous explorer, try running @code{readelf} or @code{objdump} on +compiled @code{.go} files. It's good times! + @node Instruction Set @subsection 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. +There are currently about 130 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 composed of 1 or more 32-bit units. The low +8 bits of the first word indicate the opcode, and the rest of +instruction describe the operands. There are a number of different ways +operands can be encoded. + +@table @code +@item u@var{n} +An unsigned @var{n}-bit integer. Usually indicates the index of a local +variable, but some instructions interpret these operands as immediate +values. +@item l24 +An offset from the current @code{ip}, in 32-bit units, as a signed +24-bit value. Indicates a bytecode address, for a relative jump. +@item i16 +@itemx i32 +An immediate Scheme value (@pxref{Immediate objects}), encoded directly +in 16 or 32 bits. +@item a32 +@itemx b32 +An immediate Scheme value, encoded as a pair of 32-bit words. +@code{a32} and @code{b32} values always go together on the same opcode, +and indicate the high and low bits, respectively. Normally only used on +64-bit systems. +@item n32 +A statically allocated non-immediate. The address of the non-immediate +is encoded as a signed 32-bit integer, and indicates a relative offset +in 32-bit units. Think of it as @code{SCM x = ip + offset}. +@item s32 +Indirect scheme value, like @code{n32} but indirected. Think of it as +@code{SCM *x = ip + offset}. +@item l32 +@item lo32 +An ip-relative address, as a signed 32-bit integer. Could indicate a +bytecode address, as in @code{make-closure}, or a non-immediate address, +as with @code{static-patch!}. + +@code{l32} and @code{lo32} are the same from the perspective of the +virtual machine. The difference is that an assembler might want to +allow an @code{lo32} address to be specified as a label and then some +number of words offset from that label, for example when patching a +field of a statically allocated object. +@item b1 +A boolean value: 1 for true, otherwise 0. +@item x@var{n} +An ignored sequence of @var{n} bits. +@end table + +An instruction is specified by giving its name, then describing its +operands. The operands are packed by 32-bit words, with earlier +operands occupying the lower bits. -Instructions themselves are one byte long. Some instructions take -parameters, which follow the instruction byte in the instruction -stream. +For example, consider the following instruction specification: + +@deftypefn Instruction {} free-set! u12:@var{dst} u12:@var{src} x8:@var{_} u24:@var{idx} +Set free variable @var{idx} from the closure @var{dst} to @var{src}. +@end deftypefn + +The first word in the instruction will start with the 8-bit value +corresponding to the @var{free-set!} opcode in the low bits, followed by +@var{dst} and @var{src} as 12-bit values. The second word starts with 8 +dead bits, followed by the index as a 24-bit immediate value. Sometimes the compiler can figure out that it is compiling a special case that can be run more efficiently. So, for example, while Guile @@ -371,28 +499,27 @@ their own test-and-branch instructions: @end example In addition, some Scheme primitives have their own inline -implementations, e.g.@: @code{cons}, and @code{list}, as we saw in the -previous section. +implementations. For example, in the previous section we saw +@code{cons}. -So Guile's instruction set is a @emph{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. +Guile's instruction set is a @emph{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. @menu -* Lexical Environment Instructions:: -* Top-Level Environment Instructions:: -* Procedure Call and Return Instructions:: -* Function Prologue Instructions:: -* Trampoline Instructions:: -* Branch Instructions:: -* Data Constructor Instructions:: -* Loading Instructions:: -* Dynamic Environment Instructions:: -* Miscellaneous Instructions:: -* Inlined Scheme Instructions:: -* Inlined Mathematical Instructions:: -* Inlined Bytevector Instructions:: +* Lexical Environment Instructions:: +* Top-Level Environment Instructions:: +* Procedure Call and Return Instructions:: +* Function Prologue Instructions:: +* Trampoline Instructions:: +* Branch Instructions:: +* Constant Instructions:: +* Dynamic Environment Instructions:: +* Miscellaneous Instructions:: +* Inlined Scheme Instructions:: +* Inlined Mathematical Instructions:: +* Inlined Bytevector Instructions:: @end menu @@ -400,101 +527,61 @@ instructions. More instructions may be added over time. @subsubsection 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 @code{long-} variants, the difference -being that they take 16-bit arguments, encoded in big-endianness, -instead of the normal 8-bit range. - -@xref{Stack Layout}, for more information on the format of stack frames. - -@deffn Instruction local-ref index -@deffnx Instruction long-local-ref index -Push onto the stack the value of the local variable located at -@var{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. -@end deffn - -@deffn Instruction local-set index -@deffnx 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 @var{index} within the current -stack frame. -@end deffn - -@deffn Instruction box index -Pop a value off the stack, and set the @var{index}nth local variable -to a box containing that value. A shortcut for @code{make-variable} -then @code{local-set}, used when binding boxed variables. -@end deffn - -@deffn Instruction empty-box index -Set the @var{index}th local variable to a box containing a variable -whose value is unbound. Used when compiling some @code{letrec} -expressions. -@end deffn - -@deffn Instruction local-boxed-ref index -@deffnx Instruction local-boxed-set index -Get or set the value of the variable located at @var{index} within the -current stack frame. A shortcut for @code{local-ref} then -@code{variable-ref} or @code{variable-set}, respectively. -@end deffn - -@deffn Instruction free-ref index -Push the value of the captured variable located at position -@var{index} within the program's vector of captured variables. -@end deffn - -@deffn Instruction free-boxed-ref index -@deffnx Instruction free-boxed-set index -Get or set a boxed free variable. A shortcut for @code{free-ref} then -@code{variable-ref} or @code{variable-set}, respectively. - -Note that there is no @code{free-set} instruction, as variables that are -@code{set!} must be boxed. -@end deffn - -@deffn Instruction make-closure num-free-vars -Pop @var{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. @var{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. -@end deffn - -@deffn Instruction fix-closure index -Fix up the free variables array of the closure stored in the -@var{index}th local variable. @var{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. - -@code{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 -@code{letrec}-bound procedures to be allocated unboxed on the stack. -@end deffn - -@deffn Instruction local-bound? index -@deffnx Instruction long-local-bound? index -Push @code{#t} on the stack if the @code{index}th local variable has -been assigned, or @code{#f} otherwise. Mostly useful for handling -optional arguments in procedure prologues. -@end deffn +compiled procedure---its free and bound variables. @xref{Stack Layout}, +for more information on the format of stack frames. + +@deftypefn Instruction {} mov u12:@var{dst} u12:@var{src} +@deftypefnx Instruction {} long-mov u24:@var{dst} x8:@var{_} u24:@var{src} +Copy a value from one local slot to another. + +As discussed previously, procedure arguments and local variables are +allocated to local slots. Guile's compiler tries to avoid shuffling +variables around to different slots, which often makes @code{mov} +instructions redundant. However there are some cases in which shuffling +is necessary, and in those cases, @code{mov} is the thing to use. +@end deftypefn + +@deftypefn Instruction {} make-closure u24:@var{dst} l32:@var{offset} x8:@var{_} u24:@var{nfree} +Make a new closure, and write it to @var{dst}. The code for the closure +will be found at @var{offset} words from the current @code{ip}. +@var{offset} is a signed 32-bit integer. Space for @var{nfree} free +variables will be allocated. + +The size of a closure is currently two words, plus one word per free +variable. +@end deftypefn + +@deftypefn Instruction {} free-ref u12:@var{dst} u12:@var{src} x8:@var{_} u24:@var{idx} +Load free variable @var{idx} from the closure @var{src} into local slot +@var{dst}. +@end deftypefn + +@deftypefn Instruction {} free-set! u12:@var{dst} u12:@var{src} x8:@var{_} u24:@var{idx} +Set free variable @var{idx} from the closure @var{dst} to @var{src}. + +This instruction is usually used when initializing a closure's free +variables, but not to mutate free variables, as variables that are +assigned are boxed. +@end deftypefn + +Recall that variables that are assigned are usually allocated in boxes, +so that continuations and closures can capture their identity and not +their value at one point in time. Variables are also used in the +implementation of top-level bindings; see the next section for more +information. + +@deftypefn Instruction {} box u12:@var{dst} u12:@var{src} +Create a new variable holding @var{src}, and place it in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} box-ref u12:@var{dst} u12:@var{src} +Unpack the variable at @var{src} into @var{dst}, asserting that the +variable is actually bound. +@end deftypefn + +@deftypefn Instruction {} box-set! u12:@var{dst} u12:@var{src} +Set the contents of the variable at @var{dst} to @var{set}. +@end deftypefn @node Top-Level Environment Instructions @@ -508,210 +595,133 @@ 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. - -@deffn Instruction toplevel-ref index -@deffnx Instruction long-toplevel-ref index -Push the value of the toplevel binding whose location is stored in at -position @var{index} in the current procedure's object table. The -@code{long-} variant encodes the index over two bytes. - -Initially, a cell in a procedure's object table that is used by -@code{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 @code{@@} or -@code{@@@@}). In that case, the cell in the object table holds a list: -@code{(@var{modname} @var{sym} @var{public?})}. The symbol @var{sym} -will be looked up in the module named @var{modname} (a list of -symbols). The lookup will be performed against the module's public -interface, unless @var{public?} is @code{#f}, which it is for example -when compiling @code{@@@@}. - -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. -@end deffn - -@deffn Instruction toplevel-set index -@deffnx Instruction long-toplevel-set index -Pop a value off the stack, and set it as the value of the toplevel -variable stored at @var{index} in the object table. If the variable -has not yet been looked up, we do the lookup as in -@code{toplevel-ref}. -@end deffn - -@deffn 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. -@end deffn - -@deffn Instruction link-now -Pop a value, @var{x}, from the stack. Look up the binding for @var{x}, -according to the rules for @code{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. -@end deffn - -@deffn 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. -@end deffn - -@deffn Instruction variable-set -Pop off two objects from the stack, a variable and a value, and set -the variable to the value. -@end deffn - -@deffn Instruction variable-bound? -Pop off the variable object from top of the stack and push @code{#t} if -it is bound, or @code{#f} otherwise. Mostly useful in procedure -prologues for defining default values for boxed optional variables. -@end deffn - -@deffn Instruction make-variable -Replace the top object on the stack with a variable containing it. -Used in some circumstances when compiling @code{letrec} expressions. -@end deffn +@deftypefn Instruction {} current-module u24:@var{dst} +Store the current module in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} resolve u24:@var{dst} b1:@var{bound?} x7:@var{_} u24:@var{sym} +Resolve @var{sym} in the current module, and place the resulting +variable in @var{dst}. An error will be signalled if no variable is +found. If @var{bound?} is true, an error will be signalled if the +variable is unbound. +@end deftypefn + +@deftypefn Instruction {} define! u12:@var{sym} u12:@var{val} +Look up a binding for @var{sym} in the current module, creating it if +necessary. Set its value to @var{val}. +@end deftypefn + +@deftypefn Instruction {} toplevel-box u24:@var{dst} s32:@var{var-offset} s32:@var{mod-offset} n32:@var{sym-offset} b1:@var{bound?} x31:@var{_} +Load a value. The value will be fetched from memory, @var{var-offset} +32-bit words away from the current instruction pointer. +@var{var-offset} is a signed value. Up to here, @code{toplevel-box} is +like @code{static-ref}. + +Then, if the loaded value is a variable, it is placed in @var{dst}, and +control flow continues. + +Otherwise, we have to resolve the variable. In that case we load the +module from @var{mod-offset}, just as we loaded the variable. Usually +the module gets set when the closure is created. @var{sym-offset} +specifies the name, as an offset to a symbol. + +We use the module and the symbol to resolve the variable, placing it in +@var{dst}, and caching the resolved variable so that we will hit the +cache next time. If @var{bound?} is true, an error will be signalled if +the variable is unbound. +@end deftypefn + +@deftypefn Instruction {} module-box u24:@var{dst} s32:@var{var-offset} n32:@var{mod-offset} n32:@var{sym-offset} b1:@var{bound?} x31:@var{_} +Like @code{toplevel-box}, except @var{mod-offset} points at a module +identifier instead of the module itself. A module identifier is a +module name, as a list, prefixed by a boolean. If the prefix is true, +then the variable is resolved relative to the module's public interface +instead of its private interface. +@end deftypefn @node Procedure Call and Return Instructions @subsubsection Procedure Call and Return Instructions -@c something about the calling convention here? - -@deffn 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 @code{call} instruction to get the return -address. -@end deffn - -@deffn Instruction call nargs -Call the procedure located at @code{sp[-nargs]} with the @var{nargs} -arguments located from @code{sp[-nargs + 1]} to @code{sp[0]}. - -This instruction requires that a new frame be pushed on the stack before -the procedure, via @code{new-frame}. @xref{Stack Layout}, for more -information. It patches up that frame with the current @code{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 -@code{sp[-nargs + 1]}, the arguments don't have to be shuffled around -- -they are already in place. -@end deffn - -@deffn Instruction tail-call nargs -Transfer control to the procedure located at @code{sp[-nargs]} with the -@var{nargs} arguments located from @code{sp[-nargs + 1]} to -@code{sp[0]}. - -Unlike @code{call}, which requires a new frame to be pushed onto the -stack, @code{tail-call} simply shuffles down the procedure and arguments -to the current stack frame. This instruction implements tail calls as -required by RnRS. -@end deffn - -@deffn Instruction apply nargs -@deffnx Instruction tail-apply nargs -Like @code{call} and @code{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. -@end deffn - -@deffn Instruction call/nargs -@deffnx Instruction tail-call/nargs -These are like @code{call} and @code{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. -@end deffn - -@deffn Instruction mv-call nargs offset -Like @code{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 (@pxref{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. -@end deffn - -@deffn 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 @code{sp} is decremented to one below the current -@code{fp}, the @code{ip} is reset to the current return address, the -@code{fp} is reset to the value of the current dynamic link, and then -the returned value is pushed on the stack. -@end deffn - -@deffn Instruction return/values nvalues -@deffnx Instruction return/nvalues -Return the top @var{nvalues} to the current continuation. In the case of -@code{return/nvalues}, @var{nvalues} itself is first popped from the top -of the stack. - -If the current continuation is a multiple-value continuation, -@code{return/values} pushes the number of values on the stack, then -returns as in @code{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 @code{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. -@end deffn - -@deffn Instruction return/values* nvalues -Like a combination of @code{apply} and @code{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 @code{(apply values -...)} case. -@end deffn - -@deffn 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 @code{(receive (x y . z) (foo) ...)} would, -logically speaking, pop off the values returned from @code{(foo)} and -push them as three values, corresponding to @code{x}, @code{y}, and -@code{z}. In that case, @var{nbinds} would be 3, and @var{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. -@end deffn - -@deffn Instruction call/cc -@deffnx 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. - -@code{call/cc} does not require a @code{new-frame} to be pushed on the -stack, as @code{call} does, because it needs to capture the stack -before the frame is pushed. - -Both the VM continuation and the C continuation are captured. -@end deffn +As described earlier (@pxref{Stack Layout}), Guile's calling convention +is that arguments are passed and values returned on the stack. + +For calls, both in tail position and in non-tail position, we require +that the procedure and the arguments already be shuffled into place +befor the call instruction. ``Into place'' for a tail call means that +the procedure should be in slot 0, and the arguments should follow. For +a non-tail call, if the procedure is in slot @var{n}, the arguments +should follow from slot @var{n}+1, and there should be two free slots at +@var{n}-1 and @var{n}-2 in which to save the @code{ip} and @code{fp}. + +Returning values is similar. Multiple-value returns should have values +already shuffled down to start from slot 1 before emitting +@code{return-values}. There is a short-cut in the single-value case, in +that @code{return} handles the trivial shuffling itself. We start from +slot 1 instead of slot 0 to make tail calls to @code{values} trivial. + +In both calls and returns, the @code{sp} is used to indicate to the +callee or caller the number of arguments or return values, respectively. +After receiving return values, it is the caller's responsibility to +@dfn{restore the frame} by resetting the @code{sp} to its former value. + +@deftypefn Instruction {} call u24:@var{proc} x8:@var{_} u24:@var{nlocals} +Call a procedure. @var{proc} is the local corresponding to a procedure. +The two values below @var{proc} will be overwritten by the saved call +frame data. The new frame will have space for @var{nlocals} locals: one +for the procedure, and the rest for the arguments which should already +have been pushed on. + +When the call returns, execution proceeds with the next instruction. +There may be any number of values on the return stack; the precise +number can be had by subtracting the address of @var{proc} from the +post-call @code{sp}. +@end deftypefn + +@deftypefn Instruction {} tail-call u24:@var{nlocals} +Tail-call a procedure. Requires that the procedure and all of the +arguments have already been shuffled into position. Will reset the +frame to @var{nlocals}. +@end deftypefn + +@deftypefn Instruction {} tail-call/shuffle u24:@var{from} +Tail-call a procedure. The procedure should already be set to slot 0. +The rest of the args are taken from the frame, starting at @var{from}, +shuffled down to start at slot 0. This is part of the implementation of +the @code{call-with-values} builtin. +@end deftypefn + +@deftypefn Instruction {} receive u12:@var{dst} u12:@var{proc} x8:@var{_} u24:@var{nlocals} +Receive a single return value from a call whose procedure was in +@var{proc}, asserting that the call actually returned at least one +value. Afterwards, resets the frame to @var{nlocals} locals. +@end deftypefn + +@deftypefn Instruction {} receive-values u24:@var{proc} b1:@var{allow-extra?} x7:@var{_} u24:@var{nvalues} +Receive a return of multiple values from a call whose procedure was in +@var{proc}. If fewer than @var{nvalues} values were returned, signal an +error. Unless @var{allow-extra?} is true, require that the number of +return values equals @var{nvalues} exactly. After @code{receive-values} +has run, the values can be copied down via @code{mov}, or used in place. +@end deftypefn + +@deftypefn Instruction {} return u24:@var{src} +Return a value. +@end deftypefn + +@deftypefn Instruction {} return-values x24:@var{_} +Return a number of values from a call frame. This opcode corresponds to +an application of @code{values} in tail position. As with tail calls, +we expect that the values have already been shuffled down to a +contiguous array starting at slot 1. We also expect the frame has +already been reset. +@end deftypefn + +@deftypefn Instruction {} call/cc x24:@var{_} +Capture the current continuation, and tail-apply the procedure in local +slot 1 to it. This instruction is part of the implementation of +@code{call/cc}, and is not generated by the compiler. +@end deftypefn @node Function Prologue Instructions @@ -728,374 +738,297 @@ 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.) -@deffn Instruction assert-nargs-ee n -@deffnx Instruction assert-nargs-ge n -Assert that the current procedure has been passed exactly @var{n} -arguments, for the @code{-ee} case, or @var{n} or more arguments, for -the @code{-ge} case. @var{n} is encoded over two bytes. +@deftypefn Instruction {} assert-nargs-ee u24:@var{expected} +@deftypefnx Instruction {} assert-nargs-ge u24:@var{expected} +@deftypefnx Instruction {} assert-nargs-le u24:@var{expected} +If the number of actual arguments is not @code{==}, @code{>=}, or +@code{<=} @var{expected}, respectively, signal an error. The number of arguments is determined by subtracting the frame pointer -from the stack pointer (@code{sp - (fp -1)}). @xref{Stack Layout}, for -more details on stack frames. -@end deffn - -@deffn Instruction br-if-nargs-ne n offset -@deffnx Instruction br-if-nargs-gt n offset -@deffnx Instruction br-if-nargs-lt n offset -Jump to @var{offset} if the number of arguments is not equal to, greater -than, or less than @var{n}. @var{n} is encoded over two bytes, and -@var{offset} has the normal three-byte encoding. +from the stack pointer (@code{sp + 1 - fp}). @xref{Stack Layout}, for +more details on stack frames. Note that @var{expected} includes the +procedure itself. +@end deftypefn + +@deftypefn Instruction {} br-if-nargs-ne u24:@var{expected} x8:@var{_} l24:@var{offset} +@deftypefnx Instruction {} br-if-nargs-lt u24:@var{expected} x8:@var{_} l24:@var{offset} +@deftypefnx Instruction {} br-if-nargs-gt u24:@var{expected} x8:@var{_} l24:@var{offset} +If the number of actual arguments is not equal, less than, or greater +than @var{expected}, respectively, add @var{offset}, a signed 24-bit +number, to the current instruction pointer. Note that @var{expected} +includes the procedure itself. These instructions are used to implement multiple arities, as in @code{case-lambda}. @xref{Case-lambda}, for more information. -@end deffn - -@deffn Instruction bind-optionals n -If the procedure has been called with fewer than @var{n} arguments, fill -in the remaining arguments with an unbound value (@code{SCM_UNDEFINED}). -@var{n} is encoded over two bytes. - -The optionals can be later initialized conditionally via the -@code{local-bound?} instruction. -@end deffn - -@deffn Instruction push-rest n -Pop off excess arguments (more than @var{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 -@code{bind-rest} instead. -@end deffn - -@deffn Instruction bind-rest n idx -Pop off excess arguments (more than @var{n}), collecting them into a -list. The list is then assigned to the @var{idx}th local variable. -@end deffn - -@deffn Instruction bind-optionals/shuffle nreq nreq-and-opt ntotal -@deffnx 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 @code{SCM_UNDEFINED}. Each argument is encoded over two bytes. - -This instruction is used by procedures with keyword arguments. -@var{nreq} is the number of required arguments to the procedure, and -@var{nreq-and-opt} is the total number of positional arguments (required -plus optional). @code{bind-optionals/shuffle} will scan the stack from -the @var{nreq}th argument up to the @var{nreq-and-opt}th, and start -shuffling when it sees the first keyword argument or runs out of -positional arguments. - -@code{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 @var{offset}, encoded using the normal three-byte -encoding. - -Shuffling simply moves the keyword arguments past the total number of -arguments, @var{ntotal}, which includes keyword and rest arguments. The -free slots created by the shuffle are filled in with -@code{SCM_UNDEFINED}, so they may be conditionally initialized later in -the function's prologue. -@end deffn - -@deffn 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 @var{ntotal}th stack slot by @code{bind-optionals/shuffle}. +@end deftypefn + +@deftypefn Instruction {} alloc-frame u24:@var{nlocals} +Ensure that there is space on the stack for @var{nlocals} local +variables, setting them all to @code{SCM_UNDEFINED}, except those values +that are already on the stack. +@end deftypefn + +@deftypefn Instruction {} reset-frame u24:@var{nlocals} +Like @code{alloc-frame}, but doesn't check that the stack is big enough, +and doesn't initialize values to @code{SCM_UNDEFINED}. Used to reset +the frame size to something less than the size that was previously set +via alloc-frame. +@end deftypefn + +@deftypefn Instruction {} assert-nargs-ee/locals u12:@var{expected} u12:@var{nlocals} +Equivalent to a sequence of @code{assert-nargs-ee} and +@code{reserve-locals}. The number of locals reserved is @var{expected} ++ @var{nlocals}. +@end deftypefn + +@deftypefn Instruction {} br-if-npos-gt u24:@var{nreq} x8:@var{_} u24:@var{npos} x8:@var{_} l24:@var{offset} +Find the first positional argument after @var{nreq}. If it is greater +than @var{npos}, jump to @var{offset}. + +This instruction is only emitted for functions with multiple clauses, +and an earlier clause has keywords and no rest arguments. +@xref{Case-lambda}, for more on how @code{case-lambda} chooses the +clause to apply. +@end deftypefn + +@deftypefn Instruction {} bind-kwargs u24:@var{nreq} u8:@var{flags} u24:@var{nreq-and-opt} x8:@var{_} u24:@var{ntotal} n32:@var{kw-offset} +@var{flags} is a bitfield, whose lowest bit is @var{allow-other-keys}, +second bit is @var{has-rest}, and whose following six bits are unused. + +Find the last positional argument, and shuffle all the rest above +@var{ntotal}. Initialize the intervening locals to +@code{SCM_UNDEFINED}. Then load the constant at @var{kw-offset} words +from the current @var{ip}, and use it and the @var{allow-other-keys} +flag to bind keyword arguments. If @var{has-rest}, collect all shuffled +arguments into a list, and store it in @var{nreq-and-opt}. Finally, +clear the arguments that we shuffled up. The parsing is driven by a keyword arguments association list, looked up -from the @var{idx}th element of the procedures object array. The alist -is a list of pairs of the form @code{(@var{kw} . @var{index})}, mapping -keyword arguments to their local variable indices. - -There are two bitflags that affect the parser, @code{allow-other-keys?} -(@code{0x1}) and @code{rest?} (@code{0x2}). Unless -@code{allow-other-keys?} is set, the parser will signal an error if an -unknown key is found. If @code{rest?} is set, errors parsing the -keyword arguments will be ignored, as a later @code{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. - -@var{idx} and @var{ntotal} are encoded over two bytes each, and -@var{flags} is encoded over one byte. -@end deffn - -@deffn Instruction reserve-locals n -Resets the stack pointer to have space for @var{n} local variables, -including the arguments. If this operation increments the stack pointer, -as in a push, the new slots are filled with @code{SCM_UNBOUND}. If this -operation decrements the stack pointer, any excess values are dropped. - -@code{reserve-locals} is typically used after argument parsing to -reserve space for local variables. -@end deffn - -@deffn Instruction assert-nargs-ee/locals n -@deffnx Instruction assert-nargs-ge/locals n -A combination of @code{assert-nargs-ee} and @code{reserve-locals}. The -number of arguments is encoded in the lower three bits of @var{n}, a -one-byte value. The number of additional local variables is take from -the upper 5 bits of @var{n}. -@end deffn +using @var{kw-offset}. The alist is a list of pairs of the form +@code{(@var{kw} . @var{index})}, mapping keyword arguments to their +local slot indices. Unless @code{allow-other-keys} is set, the parser +will signal an error if an unknown key is found. + +A macro-mega-instruction. +@end deftypefn + +@deftypefn Instruction {} bind-rest u24:@var{dst} +Collect any arguments at or above @var{dst} into a list, and store that +list at @var{dst}. +@end deftypefn @node Trampoline Instructions @subsubsection 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 +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 @code{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 @code{scm_c_make_gsubr}. As such, a -compiler probably shouldn't emit code with these instructions. However, +example in response to a call to @code{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. -@deffn Instruction subr-call nargs -Pop off a foreign pointer (which should have been pushed on by the -trampoline), and call it directly, with the @var{nargs} arguments from -the stack. Return the resulting value or values to the calling -procedure. -@end deffn - -@deffn 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 @var{nargs} -arguments from the stack. Return the resulting value to the calling -procedure. -@end deffn - -@deffn 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. -@end deffn - -@deffn 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. -@end deffn +@deftypefn Instruction {} subr-call u24:@var{ptr-idx} +Call a subr, passing all locals in this frame as arguments. Fetch the +foreign pointer from @var{ptr-idx}, a free variable. Return from the +calling frame. +@end deftypefn + +@deftypefn Instruction {} foreign-call u12:@var{cif-idx} u12:@var{ptr-idx} +Call a foreign function. Fetch the @var{cif} and foreign pointer from +@var{cif-idx} and @var{ptr-idx}, both free variables. Return from the calling +frame. Arguments are taken from the stack. +@end deftypefn + +@deftypefn Instruction {} continuation-call u24:@var{contregs} +Return to a continuation, nonlocally. The arguments to the continuation +are taken from the stack. @var{contregs} is a free variable containing +the reified continuation. +@end deftypefn + +@deftypefn Instruction {} compose-continuation u24:@var{cont} +Compose a partial continution with the current continuation. The +arguments to the continuation are taken from the stack. @var{cont} is a +free variable containing the reified continuation. +@end deftypefn + +@deftypefn Instruction {} tail-apply x24:@var{_} +Tail-apply the procedure in local slot 0 to the rest of the arguments. +This instruction is part of the implementation of @code{apply}, and is +not generated by the compiler. +@end deftypefn + +@deftypefn Instruction {} builtin-ref u12:@var{dst} u12:@var{idx} +Load a builtin stub by index into @var{dst}. +@end deftypefn @node Branch Instructions @subsubsection Branch Instructions -All the conditional branch instructions described below work in the -same way: +All offsets to branch instructions are 24-bit signed numbers, which +count 32-bit units. This gives Guile effectively a 26-bit address range +for relative jumps. + +@deftypefn Instruction {} br l24:@var{offset} +Add @var{offset} to the current instruction pointer. +@end deftypefn + +All the conditional branch instructions described below have an +@var{invert} parameter, which if true reverses the test: +@code{br-if-true} becomes @code{br-if-false}, and so on. + +@deftypefn Instruction {} br-if-true u24:@var{test} b1:@var{invert} x7:@var{_} l24:@var{offset} +If the value in @var{test} is true for the purposes of Scheme, add +@var{offset} to the current instruction pointer. +@end deftypefn + +@deftypefn Instruction {} br-if-null u24:@var{test} b1:@var{invert} x7:@var{_} l24:@var{offset} +If the value in @var{test} is the end-of-list or Lisp nil, add +@var{offset} to the current instruction pointer. +@end deftypefn + +@deftypefn Instruction {} br-if-nil u24:@var{test} b1:@var{invert} x7:@var{_} l24:@var{offset} +If the value in @var{test} is false to Lisp, add @var{offset} to the +current instruction pointer. +@end deftypefn + +@deftypefn Instruction {} br-if-pair u24:@var{test} b1:@var{invert} x7:@var{_} l24:@var{offset} +If the value in @var{test} is a pair, add @var{offset} to the current +instruction pointer. +@end deftypefn + +@deftypefn Instruction {} br-if-struct u24:@var{test} b1:@var{invert} x7:@var{_} l24:@var{offset} +If the value in @var{test} is a struct, add @var{offset} number to the +current instruction pointer. +@end deftypefn + +@deftypefn Instruction {} br-if-char u24:@var{test} b1:@var{invert} x7:@var{_} l24:@var{offset} +If the value in @var{test} is a char, add @var{offset} to the current +instruction pointer. +@end deftypefn + +@deftypefn Instruction {} br-if-tc7 u24:@var{test} b1:@var{invert} u7:@var{tc7} l24:@var{offset} +If the value in @var{test} has the TC7 given in the second word, add +@var{offset} to the current instruction pointer. TC7 codes are part of +the way Guile represents non-immediate objects, and are deep wizardry. +See @code{libguile/tags.h} for all the details. +@end deftypefn + +@deftypefn Instruction {} br-if-eq u12:@var{a} u12:@var{b} b1:@var{invert} x7:@var{_} l24:@var{offset} +@deftypefnx Instruction {} br-if-eqv u12:@var{a} u12:@var{b} b1:@var{invert} x7:@var{_} l24:@var{offset} +@deftypefnx Instruction {} br-if-equal u12:@var{a} u12:@var{b} b1:@var{invert} x7:@var{_} l24:@var{offset} +If the value in @var{a} is @code{eq?}, @code{eqv?}, or @code{equal?} to +the value in @var{b}, respectively, add @var{offset} to the current +instruction pointer. +@end deftypefn + +@deftypefn Instruction {} br-if-= u12:@var{a} u12:@var{b} b1:@var{invert} x7:@var{_} l24:@var{offset} +@deftypefnx Instruction {} br-if-< u12:@var{a} u12:@var{b} b1:@var{invert} x7:@var{_} l24:@var{offset} +@deftypefnx Instruction {} br-if-<= u12:@var{a} u12:@var{b} b1:@var{invert} x7:@var{_} l24:@var{offset} +If the value in @var{a} is @code{=}, @code{<}, or @code{<=} to the value +in @var{b}, respectively, add @var{offset} to the current instruction +pointer. +@end deftypefn + + +@node Constant Instructions +@subsubsection Constant Instructions + +The following instructions load literal data into a program. There are +two kinds. + +The first set of instructions loads immediate values. These +instructions encode the immediate directly into the instruction stream. + +@deftypefn Instruction {} make-short-immediate u8:@var{dst} i16:@var{low-bits} +Make an immediate whose low bits are @var{low-bits}, and whose top bits are +0. +@end deftypefn + +@deftypefn Instruction {} make-long-immediate u24:@var{dst} i32:@var{low-bits} +Make an immediate whose low bits are @var{low-bits}, and whose top bits are +0. +@end deftypefn + +@deftypefn Instruction {} make-long-long-immediate u24:@var{dst} a32:@var{high-bits} b32:@var{low-bits} +Make an immediate with @var{high-bits} and @var{low-bits}. +@end deftypefn + +Non-immediate constant literals are referenced either directly or +indirectly. For example, Guile knows at compile-time what the layout of +a string will be like, and arranges to embed that object directly in the +compiled image. A reference to a string will use +@code{make-non-immediate} to treat a pointer into the compilation unit +as a @code{SCM} value directly. + +@deftypefn Instruction {} make-non-immediate u24:@var{dst} n32:@var{offset} +Load a pointer to statically allocated memory into @var{dst}. The +object's memory is will be found @var{offset} 32-bit words away from the +current instruction pointer. Whether the object is mutable or immutable +depends on where it was allocated by the compiler, and loaded by the +loader. +@end deftypefn + +Some objects must be unique across the whole system. This is the case +for symbols and keywords. For these objects, Guile arranges to +initialize them when the compilation unit is loaded, storing them into a +slot in the image. References go indirectly through that slot. +@code{static-ref} is used in this case. + +@deftypefn Instruction {} static-ref u24:@var{dst} s32:@var{offset} +Load a @var{scm} value into @var{dst}. The @var{scm} value will be fetched from +memory, @var{offset} 32-bit words away from the current instruction +pointer. @var{offset} is a signed value. +@end deftypefn + +Fields of non-immediates may need to be fixed up at load time, because +we do not know in advance at what address they will be loaded. This is +the case, for example, for a pair containing a non-immediate in one of +its fields. @code{static-ref} and @code{static-patch!} are used in +these situations. + +@deftypefn Instruction {} static-set! u24:@var{src} lo32:@var{offset} +Store a @var{scm} value into memory, @var{offset} 32-bit words away from the +current instruction pointer. @var{offset} is a signed value. +@end deftypefn + +@deftypefn Instruction {} static-patch! x24:@var{_} lo32:@var{dst-offset} l32:@var{src-offset} +Patch a pointer at @var{dst-offset} to point to @var{src-offset}. Both offsets +are signed 32-bit values, indicating a memory address as a number +of 32-bit words away from the current instruction pointer. +@end deftypefn + +Many kinds of literals can be loaded with the above instructions, once +the compiler has prepared the statically allocated data. This is the +case for vectors, strings, uniform vectors, pairs, and procedures with +no free variables. Other kinds of data might need special initializers; +those instructions follow. + +@deftypefn Instruction {} string->number u12:@var{dst} u12:@var{src} +Parse a string in @var{src} to a number, and store in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} string->symbol u12:@var{dst} u12:@var{src} +Parse a string in @var{src} to a symbol, and store in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} symbol->keyword u12:@var{dst} u12:@var{src} +Make a keyword from the symbol in @var{src}, and store it in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} load-typed-array u8:@var{dst} u8:@var{type} u8:@var{shape} n32:@var{offset} u32:@var{len} +Load the contiguous typed array located at @var{offset} 32-bit words away +from the instruction pointer, and store into @var{dst}. @var{len} is a byte +length. @var{offset} is signed. +@end deftypefn -@itemize -@item They pop off Scheme object(s) located on the stack for use in the -branch condition -@item If the condition is true, then the instruction pointer is -increased by the offset passed as an argument to the branch -instruction; -@item Program execution proceeds with the next instruction (that is, -the one to which the instruction pointer points). -@end itemize - -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. - -@deffn Instruction br offset -Jump to @var{offset}. No values are popped. -@end deffn - -@deffn Instruction br-if offset -Jump to @var{offset} if the object on the stack is not false. -@end deffn - -@deffn Instruction br-if-not offset -Jump to @var{offset} if the object on the stack is false. -@end deffn - -@deffn Instruction br-if-eq offset -Jump to @var{offset} if the two objects located on the stack are -equal in the sense of @code{eq?}. Note that, for this instruction, the -stack pointer is decremented by two Scheme objects instead of only -one. -@end deffn - -@deffn Instruction br-if-not-eq offset -Same as @code{br-if-eq} for non-@code{eq?} objects. -@end deffn - -@deffn Instruction br-if-null offset -Jump to @var{offset} if the object on the stack is @code{'()}. -@end deffn - -@deffn Instruction br-if-not-null offset -Jump to @var{offset} if the object on the stack is not @code{'()}. -@end deffn - - -@node Data Constructor Instructions -@subsubsection Data Constructor Instructions - -These instructions push simple immediate values onto the stack, -or construct compound data structures from values on the stack. - -@deffn Instruction make-int8 value -Push @var{value}, an 8-bit integer, onto the stack. -@end deffn - -@deffn Instruction make-int8:0 -Push the immediate value @code{0} onto the stack. -@end deffn - -@deffn Instruction make-int8:1 -Push the immediate value @code{1} onto the stack. -@end deffn - -@deffn Instruction make-int16 value -Push @var{value}, a 16-bit integer, onto the stack. -@end deffn - -@deffn Instruction make-uint64 value -Push @var{value}, an unsigned 64-bit integer, onto the stack. The -value is encoded in 8 bytes, most significant byte first (big-endian). -@end deffn - -@deffn Instruction make-int64 value -Push @var{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. -@end deffn - -@deffn Instruction make-false -Push @code{#f} onto the stack. -@end deffn - -@deffn Instruction make-true -Push @code{#t} onto the stack. -@end deffn - -@deffn Instruction make-nil -Push @code{#nil} onto the stack. -@end deffn - -@deffn Instruction make-eol -Push @code{'()} onto the stack. -@end deffn - -@deffn Instruction make-char8 value -Push @var{value}, an 8-bit character, onto the stack. -@end deffn - -@deffn Instruction make-char32 value -Push @var{value}, an 32-bit character, onto the stack. The value is -encoded in big-endian order. -@end deffn - -@deffn Instruction make-symbol -Pops a string off the stack, and pushes a symbol. -@end deffn - -@deffn Instruction make-keyword value -Pops a symbol off the stack, and pushes a keyword. -@end deffn - -@deffn Instruction list n -Pops off the top @var{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. @var{n} is a two-byte value, -most significant byte first. -@end deffn - -@deffn Instruction vector n -Create and fill a vector with the top @var{n} values from the stack, -popping off those values and pushing on the resulting vector. @var{n} -is a two-byte value, like in @code{vector}. -@end deffn - -@deffn Instruction make-struct n -Make a new struct from the top @var{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. -@end deffn - -@deffn Instruction make-array n -Pop an array shape from the stack, then pop the remaining @var{n} -values, pushing a new array. @var{n} is encoded over three bytes. - -The array shape should be appropriate to store @var{n} values. -@xref{Array Procedures}, for more information on array shapes. -@end deffn - -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. @xref{Variables -and the VM}, for more information on the object table. - -@deffn Instruction object-ref n -@deffnx Instruction long-object-ref n -Push @var{n}th value from the current program's object vector. The -``long'' variant has a 16-bit index instead of an 8-bit index. -@end deffn - - -@node Loading Instructions -@subsubsection 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 @code{length} parameter, -indicating the size of the embedded data, in bytes. The length itself -is encoded in 3 bytes. - -@deffn Instruction load-number length -Load an arbitrary number from the instruction stream. The number is -embedded in the stream as a string. -@end deffn -@deffn Instruction load-string length -Load a string from the instruction stream. The string is assumed to be -encoded in the ``latin1'' locale. -@end deffn -@deffn Instruction load-wide-string length -Load a UTF-32 string from the instruction stream. @var{length} is the -length in bytes, not in codepoints. -@end deffn -@deffn 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 @code{load-wide-string} then @code{make-symbol}. -@end deffn -@deffn 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. -@end deffn - -@deffn 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 @code{#f} in the case that the program has no -object table. A program that does not reference toplevel bindings and -does not use @code{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, @code{struct scm_objcode}. @xref{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. -@end deffn @node Dynamic Environment Instructions @subsubsection Dynamic Environment Instructions @@ -1103,169 +1036,185 @@ closures. Guile's virtual machine has low-level support for @code{dynamic-wind}, dynamic binding, and composable prompts and aborts. -@deffn 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 -@code{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. -@xref{Dynamic Wind}. -@end deffn - -@deffn Instruction unwind -Pop off the top entry from the ``dynamic stack'', for example, a -wind/unwind thunk pair. @code{unwind} instructions should be properly -paired with their winding instructions, like @code{wind}. -@end deffn - -@deffn Instruction wind-fluids n -Pop off @var{n} values and @var{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. @xref{Fluids and Dynamic -States}. -@end deffn - -@deffn 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 -@code{wind-fluids} instruction was processed. -@end deffn - -@deffn Instruction fluid-ref -Pop a fluid from the stack, and push its current value. -@end deffn - -@deffn Instruction fluid-set -Pop a value and a fluid from the stack, in that order, and set the fluid -to the value. -@end deffn - -@deffn Instruction prompt escape-only? offset -Establish a dynamic prompt. @xref{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 -@code{unwind}. - -If an abort is made to this prompt, control will jump to @var{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 @code{prompt} implements Felleisen's @dfn{--F--} operator.) +@deftypefn Instruction {} abort x24:@var{_} +Abort to a prompt handler. The tag is expected in slot 1, and the rest +of the values in the frame are returned to the prompt handler. This +corresponds to a tail application of abort-to-prompt. + +If no prompt can be found in the dynamic environment with the given tag, +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 from slot 1, as if from a multiple-value +return, and control resumes in the caller. Thus to the calling +function, a call to @code{abort-to-prompt} looks like any other function +call. +@end deftypefn + +@deftypefn Instruction {} prompt u24:@var{tag} b1:@var{escape-only?} x7:@var{_} u24:@var{proc-slot} x8:@var{_} l24:@var{handler-offset} +Push a new prompt on the dynamic stack, with a tag from @var{tag} and a +handler at @var{handler-offset} words from the current @var{ip}. + +If an abort is made to this prompt, control will jump to the handler. +The handler will expect a multiple-value return as if from a call with +the procedure at @var{proc-slot}, with the reified partial continuation +as the first argument, followed by the values returned to the handler. +If control returns to the handler, the prompt is already popped off by +the abort mechanism. (Guile's @code{prompt} implements Felleisen's +@dfn{--F--} operator.) If @var{escape-only?} is nonzero, the prompt will be marked as escape-only, which allows an abort to this prompt to avoid reifying the continuation. -@end deffn -@deffn Instruction abort n -Abort to a dynamic prompt. +@xref{Prompts}, for more information on prompts. +@end deftypefn -This instruction pops one tail argument list, @var{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. +@deftypefn Instruction {} wind u12:@var{winder} u12:@var{unwinder} +Push wind and unwind procedures onto the dynamic stack. Note that +neither are actually called; the compiler should emit calls to wind and +unwind for the normal dynamic-wind control flow. Also note that the +compiler should have inserted checks that they wind and unwind procs are +thunks, if it could not prove that to be the case. @xref{Dynamic Wind}. +@end deftypefn -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 @code{abort} -instruction should be followed by code ready to handle the equivalent of -a multiply-valued return. -@end deffn +@deftypefn Instruction {} unwind x24:@var{_} +@var{a} normal exit from the dynamic extent of an expression. Pop the top +entry off of the dynamic stack. +@end deftypefn -@node Miscellaneous Instructions -@subsubsection Miscellaneous Instructions +@deftypefn Instruction {} push-fluid u12:@var{fluid} u12:@var{value} +Dynamically bind @var{value} to @var{fluid} by creating a with-fluids +object and pushing that object on the dynamic stack. @xref{Fluids and +Dynamic States}. +@end deftypefn -@deffn Instruction nop -Does nothing! Used for padding other instructions to certain -alignments. -@end deffn +@deftypefn Instruction {} pop-fluid x24:@var{_} +Leave the dynamic extent of a @code{with-fluid*} expression, restoring +the fluid to its previous value. @code{push-fluid} should always be +balanced with @code{pop-fluid}. +@end deftypefn -@deffn 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. +@deftypefn Instruction {} fluid-ref u12:@var{dst} u12:@var{src} +Reference the fluid in @var{src}, and place the value in @var{dst}. +@end deftypefn -If multiple values have been returned, the SCM value will be a -multiple-values object (@pxref{Multiple Values}). -@end deffn +@deftypefn Instruction {} fluid-set u12:@var{fluid} u12:@var{val} +Set the value of the fluid in @var{dst} to the value in @var{src}. +@end deftypefn -@deffn Instruction break -Does nothing, but invokes the break hook. -@end deffn -@deffn Instruction drop -Pops off the top value from the stack, throwing it away. -@end deffn +@node Miscellaneous Instructions +@subsubsection Miscellaneous Instructions -@deffn Instruction dup -Re-pushes the top value onto the stack. -@end deffn +@deftypefn Instruction {} halt x24:@var{_} +Bring the VM to a halt, returning all the values from the stack. Used +in the ``boot continuation'', which is used when entering the VM from C. +@end deftypefn -@deffn Instruction void -Pushes ``the unspecified value'' onto the stack. -@end deffn @node Inlined Scheme Instructions @subsubsection 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. - -@deffn Instruction not x -@deffnx Instruction not-not x -@deffnx Instruction eq? x y -@deffnx Instruction not-eq? x y -@deffnx Instruction null? -@deffnx Instruction not-null? -@deffnx Instruction eqv? x y -@deffnx Instruction equal? x y -@deffnx Instruction pair? x y -@deffnx Instruction list? x -@deffnx Instruction set-car! pair x -@deffnx Instruction set-cdr! pair x -@deffnx Instruction cons x y -@deffnx Instruction car x -@deffnx Instruction cdr x -@deffnx Instruction vector-ref x y -@deffnx Instruction vector-set x n y -@deffnx Instruction struct? x -@deffnx Instruction struct-ref x n -@deffnx Instruction struct-set x n v -@deffnx Instruction struct-vtable x -@deffnx Instruction class-of x -@deffnx Instruction slot-ref struct n -@deffnx Instruction slot-set struct n x -Inlined implementations of their Scheme equivalents. -@end deffn +procedures. It tries to inline these small operations to avoid the +overhead of creating new stack frames. This allows the compiler to +optimize better. + +@deftypefn Instruction {} make-vector/immediate u8:@var{dst} u8:@var{length} u8:@var{init} +Make a short vector of known size and write it to @var{dst}. The vector +will have space for @var{length} slots, an immediate value. They will +be filled with the value in slot @var{init}. +@end deftypefn + +@deftypefn Instruction {} vector-length u12:@var{dst} u12:@var{src} +Store the length of the vector in @var{src} in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} vector-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +Fetch the item at position @var{idx} in the vector in @var{src}, and +store it in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} vector-ref/immediate u8:@var{dst} u8:@var{src} u8:@var{idx} +Fill @var{dst} with the item @var{idx} elements into the vector at +@var{src}. Useful for building data types using vectors. +@end deftypefn + +@deftypefn Instruction {} vector-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +Store @var{src} into the vector @var{dst} at index @var{idx}. +@end deftypefn + +@deftypefn Instruction {} vector-set!/immediate u8:@var{dst} u8:@var{idx} u8:@var{src} +Store @var{src} into the vector @var{dst} at index @var{idx}. Here +@var{idx} is an immediate value. +@end deftypefn + +@deftypefn Instruction {} struct-vtable u12:@var{dst} u12:@var{src} +Store the vtable of @var{src} into @var{dst}. +@end deftypefn + +@deftypefn Instruction {} allocate-struct/immediate u8:@var{dst} u8:@var{vtable} u8:@var{nfields} +Allocate a new struct with @var{vtable}, and place it in @var{dst}. The +struct will be constructed with space for @var{nfields} fields, which +should correspond to the field count of the @var{vtable}. +@end deftypefn + +@deftypefn Instruction {} struct-ref/immediate u8:@var{dst} u8:@var{src} u8:@var{idx} +Fetch the item at slot @var{idx} in the struct in @var{src}, and store +it in @var{dst}. @var{idx} is an immediate unsigned 8-bit value. +@end deftypefn + +@deftypefn Instruction {} struct-set!/immediate u8:@var{dst} u8:@var{idx} u8:@var{src} +Store @var{src} into the struct @var{dst} at slot @var{idx}. @var{idx} +is an immediate unsigned 8-bit value. +@end deftypefn + +@deftypefn Instruction {} class-of u12:@var{dst} u12:@var{type} +Store the vtable of @var{src} into @var{dst}. +@end deftypefn + +@deftypefn Instruction {} make-array u12:@var{dst} u12:@var{type} x8:@var{_} u12:@var{fill} u12:@var{bounds} +Make a new array with @var{type}, @var{fill}, and @var{bounds}, storing it in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} string-length u12:@var{dst} u12:@var{src} +Store the length of the string in @var{src} in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} string-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +Fetch the character at position @var{idx} in the string in @var{src}, and store +it in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} cons u8:@var{dst} u8:@var{car} u8:@var{cdr} +Cons @var{car} and @var{cdr}, and store the result in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} car u12:@var{dst} u12:@var{src} +Place the car of @var{src} in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} cdr u12:@var{dst} u12:@var{src} +Place the cdr of @var{src} in @var{dst}. +@end deftypefn + +@deftypefn Instruction {} set-car! u12:@var{pair} u12:@var{car} +Set the car of @var{dst} to @var{src}. +@end deftypefn + +@deftypefn Instruction {} set-cdr! u12:@var{pair} u12:@var{cdr} +Set the cdr of @var{dst} to @var{src}. +@end deftypefn Note that @code{caddr} and friends compile to a series of @code{car} and @code{cdr} instructions. + @node Inlined Mathematical Instructions @subsubsection Inlined Mathematical Instructions @@ -1276,29 +1225,61 @@ 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. - -@deffn Instruction add x y -@deffnx Instruction add1 x -@deffnx Instruction sub x y -@deffnx Instruction sub1 x -@deffnx Instruction mul x y -@deffnx Instruction div x y -@deffnx Instruction quo x y -@deffnx Instruction rem x y -@deffnx Instruction mod x y -@deffnx Instruction ee? x y -@deffnx Instruction lt? x y -@deffnx Instruction gt? x y -@deffnx Instruction le? x y -@deffnx Instruction ge? x y -@deffnx Instruction ash x n -@deffnx Instruction logand x y -@deffnx Instruction logior x y -@deffnx Instruction logxor x y -Inlined implementations of the corresponding mathematical operations. -@end deffn +All of these operations place their result in their first operand, +@var{dst}. + +@deftypefn Instruction {} add u8:@var{dst} u8:@var{a} u8:@var{b} +Add @var{a} to @var{b}. +@end deftypefn + +@deftypefn Instruction {} add1 u12:@var{dst} u12:@var{src} +Add 1 to the value in @var{src}. +@end deftypefn + +@deftypefn Instruction {} sub u8:@var{dst} u8:@var{a} u8:@var{b} +Subtract @var{b} from @var{a}. +@end deftypefn + +@deftypefn Instruction {} sub1 u12:@var{dst} u12:@var{src} +Subtract 1 from @var{src}. +@end deftypefn + +@deftypefn Instruction {} mul u8:@var{dst} u8:@var{a} u8:@var{b} +Multiply @var{a} and @var{b}. +@end deftypefn + +@deftypefn Instruction {} div u8:@var{dst} u8:@var{a} u8:@var{b} +Divide @var{a} by @var{b}. +@end deftypefn + +@deftypefn Instruction {} quo u8:@var{dst} u8:@var{a} u8:@var{b} +Divide @var{a} by @var{b}. +@end deftypefn + +@deftypefn Instruction {} rem u8:@var{dst} u8:@var{a} u8:@var{b} +Divide @var{a} by @var{b}. +@end deftypefn + +@deftypefn Instruction {} mod u8:@var{dst} u8:@var{a} u8:@var{b} +Compute the modulo of @var{a} by @var{b}. +@end deftypefn + +@deftypefn Instruction {} ash u8:@var{dst} u8:@var{a} u8:@var{b} +Shift @var{a} arithmetically by @var{b} bits. +@end deftypefn + +@deftypefn Instruction {} logand u8:@var{dst} u8:@var{a} u8:@var{b} +Compute the bitwise @code{and} of @var{a} and @var{b}. +@end deftypefn + +@deftypefn Instruction {} logior u8:@var{dst} u8:@var{a} u8:@var{b} +Compute the bitwise inclusive @code{or} of @var{a} with @var{b}. +@end deftypefn + +@deftypefn Instruction {} logxor u8:@var{dst} u8:@var{a} u8:@var{b} +Compute the bitwise exclusive @code{or} of @var{a} with @var{b}. +@end deftypefn + @node Inlined Bytevector Instructions @subsubsection Inlined Bytevector Instructions @@ -1309,48 +1290,32 @@ 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 (@code{u16}, @code{f64}, etc) take an extra -endianness argument. Only aligned native accesses are currently -fast-pathed in Guile's VM. - -@deffn Instruction bv-u8-ref bv n -@deffnx Instruction bv-s8-ref bv n -@deffnx Instruction bv-u16-native-ref bv n -@deffnx Instruction bv-s16-native-ref bv n -@deffnx Instruction bv-u32-native-ref bv n -@deffnx Instruction bv-s32-native-ref bv n -@deffnx Instruction bv-u64-native-ref bv n -@deffnx Instruction bv-s64-native-ref bv n -@deffnx Instruction bv-f32-native-ref bv n -@deffnx Instruction bv-f64-native-ref bv n -@deffnx Instruction bv-u16-ref bv n endianness -@deffnx Instruction bv-s16-ref bv n endianness -@deffnx Instruction bv-u32-ref bv n endianness -@deffnx Instruction bv-s32-ref bv n endianness -@deffnx Instruction bv-u64-ref bv n endianness -@deffnx Instruction bv-s64-ref bv n endianness -@deffnx Instruction bv-f32-ref bv n endianness -@deffnx Instruction bv-f64-ref bv n endianness -@deffnx Instruction bv-u8-set bv n val -@deffnx Instruction bv-s8-set bv n val -@deffnx Instruction bv-u16-native-set bv n val -@deffnx Instruction bv-s16-native-set bv n val -@deffnx Instruction bv-u32-native-set bv n val -@deffnx Instruction bv-s32-native-set bv n val -@deffnx Instruction bv-u64-native-set bv n val -@deffnx Instruction bv-s64-native-set bv n val -@deffnx Instruction bv-f32-native-set bv n val -@deffnx Instruction bv-f64-native-set bv n val -@deffnx Instruction bv-u16-set bv n val endianness -@deffnx Instruction bv-s16-set bv n val endianness -@deffnx Instruction bv-u32-set bv n val endianness -@deffnx Instruction bv-s32-set bv n val endianness -@deffnx Instruction bv-u64-set bv n val endianness -@deffnx Instruction bv-s64-set bv n val endianness -@deffnx Instruction bv-f32-set bv n val endianness -@deffnx Instruction bv-f64-set bv n val endianness -Inlined implementations of the corresponding bytevector operations. -@end deffn +@deftypefn Instruction {} bv-u8-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-s8-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-u16-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-s16-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-u32-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-s32-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-u64-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-s64-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-f32-ref u8:@var{dst} u8:@var{src} u8:@var{idx} +@deftypefnx Instruction {} bv-f64-ref u8:@var{dst} u8:@var{src} u8:@var{idx} + +Fetch the item at byte offset @var{idx} in the bytevector @var{src}, and +store it in @var{dst}. All accesses use native endianness. +@end deftypefn + +@deftypefn Instruction {} bv-u8-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-s8-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-u16-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-s16-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-u32-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-s32-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-u64-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-s64-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-f32-set! u8:@var{dst} u8:@var{idx} u8:@var{src} +@deftypefnx Instruction {} bv-f64-set! u8:@var{dst} u8:@var{idx} u8:@var{src} + +Store @var{src} into the bytevector @var{dst} at byte offset @var{idx}. +Multibyte values are written using native endianness. +@end deftypefn |