summaryrefslogtreecommitdiffstats
path: root/hobbit.info
diff options
context:
space:
mode:
authorBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:26 -0800
committerBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:26 -0800
commitdeda2c0fd8689349fea2a900199a76ff7ecb319e (patch)
treec9726d54a0806a9b0c75e6c82db8692aea0053cf /hobbit.info
parent3278b75942bdbe706f7a0fba87729bb1e935b68b (diff)
downloadscm-deda2c0fd8689349fea2a900199a76ff7ecb319e.tar.gz
scm-deda2c0fd8689349fea2a900199a76ff7ecb319e.zip
Import Upstream version 5d6upstream/5d6
Diffstat (limited to 'hobbit.info')
-rw-r--r--hobbit.info1952
1 files changed, 1952 insertions, 0 deletions
diff --git a/hobbit.info b/hobbit.info
new file mode 100644
index 0000000..9e0c0a9
--- /dev/null
+++ b/hobbit.info
@@ -0,0 +1,1952 @@
+This is hobbit.info, produced by makeinfo version 4.0 from hobbit.texi.
+
+INFO-DIR-SECTION The Algorithmic Language Scheme
+START-INFO-DIR-ENTRY
+* hobbit: (hobbit). SCM Compiler.
+END-INFO-DIR-ENTRY
+
+
+File: hobbit.info, Node: Top, Next: Introduction, Prev: (dir), Up: (dir)
+
+Hobbit is an optimizing R4RS-Scheme to C compiler written by Tanel
+Tammet.
+
+* Menu:
+
+* Introduction::
+* Compiling with Hobbit::
+* The Language Compiled::
+* Performance of Compiled Code::
+* Principles of Compilation::
+* About Hobbit::
+
+Copyright (C) 1990-1999, 2002 Free Software Foundation
+
+Permission is granted to make and distribute verbatim copies of this
+manual provided the copyright notice and this permission notice are
+preserved on all copies.
+
+Permission is granted to copy and distribute modified versions of this
+manual under the conditions for verbatim copying, provided that the
+entire resulting derived work is distributed under the terms of a
+permission notice identical to this one.
+
+Permission is granted to copy and distribute translations of this manual
+into another language, under the above conditions for modified versions,
+except that this permission notice may be stated in a translation
+approved by the author.
+
+
+File: hobbit.info, Node: Introduction, Next: Compiling with Hobbit, Prev: Top, Up: Top
+
+Introduction
+************
+
+Hobbit is a small optimizing scheme-to-C compiler written in Report 4
+scheme and intended for use together with the SCM scheme interpreter of
+A. Jaffer. Hobbit compiles full Report 4 scheme, except that:
+
+ * It does not fully conform to the requirement of being properly
+ tail-recursive: non-mutual tailrecursion is detected, but mutual
+ tailrecursion is not.
+
+ * Macros from the Report 4 appendix are not supported (yet): only
+ the common-lisp-like defmacro is supported.
+
+Hobbit treats SCM files as a C library and provides integration of
+compiled procedures and variables with the SCM interpreter as new
+primitives.
+
+Hobbit compiles scheme files to C files and does not provide anything
+else by itself (eg. calling the C compiler, dynamic loading). Such
+niceties are described in the next chapter *Note Compiling And
+Linking::.
+
+Hobbit (derived from hobbit5x) is now part of the SCM Scheme
+implementation. The most recent information about SCM can be found on
+SCM's "WWW" home page:
+
+ <http://swissnet.ai.mit.edu/~jaffer/SCM.html>
+
+Hobbit4d has also been ported to the Guile Scheme implementation:
+
+ <http://www.gnu.org/software/guile/anon-cvs.html>
+
+
+File: hobbit.info, Node: Compiling with Hobbit, Next: The Language Compiled, Prev: Introduction, Up: Top
+
+Compiling with Hobbit
+*********************
+
+* Menu:
+
+* Compiling And Linking::
+* Error Detection::
+* Hobbit Options::
+* CC Optimizations::
+
+
+File: hobbit.info, Node: Compiling And Linking, Next: Error Detection, Prev: Compiling with Hobbit, Up: Compiling with Hobbit
+
+Compiling And Linking
+=====================
+
+`(require 'compile)'
+
+ - Function: hobbit name1.scm name2.scm ...
+ Invokes the HOBBIT compiler to translate Scheme files `NAME1.scm',
+ `NAME2.scm', ... to C files `NAME1.c' and `NAME1.h'.
+
+ - Function: compile-file name1.scm name2.scm ...
+ Compiles the HOBBIT translation of NAME1.scm, NAME2.scm, ... to a
+ dynamically linkable object file NAME1<object-suffix>, where
+ <object-suffix> is the object file suffix for your computer (for
+ instance, `.so'). NAME1.scm must be in the current directory;
+ NAME2.scm, ... may be in other directories.
+
+ cd ~/scm/
+ scm -rcompile -e'(compile-file "example.scm")'
+
+ Starting to read example.scm
+
+ Generic (slow) arithmetic assumed: 1.0e-3 found.
+
+ ** Pass 1 completed **
+ ** Pass 2 completed **
+ ** Pass 3 completed **
+ ** Pass 4 completed **
+ ** Pass 5 completed **
+ ** Pass 6 completed **
+
+ C source file example.c is built.
+ C header file example.h is built.
+
+ These top level higher order procedures are not clonable (slow):
+ (nonkeyword_make-promise map-streams generate-vector runge-kutta-4)
+ These top level procedures create non-liftable closures (slow):
+ (nonkeyword_make-promise damped-oscillator map-streams scale-vector elementwise runge-kutta-4 integrate-system)
+
+ ; Scheme (linux) script created by SLIB/batch Sun Apr 7 22:49:49 2002
+ ; ================ Write file with C defines
+ (delete-file "scmflags.h")
+ (call-with-output-file
+ "scmflags.h"
+ (lambda (fp)
+ (for-each
+ (lambda (string) (write-line string fp))
+ '("#define IMPLINIT \"Init5d6.scm\""
+ "#define BIGNUMS"
+ "#define FLOATS"
+ "#define ARRAYS"
+ "#define DLL"))))
+ ; ================ Compile C source files
+ (system "gcc -O2 -fpic -c -I/usr/local/lib/scm/ example.c")
+ (system "gcc -shared -o example.so example.o -lm -lc")
+ (delete-file "example.o")
+ ; ================ Link C object files
+ (delete-file "slibcat")
+
+ Compilation finished at Sun Apr 7 22:49:50
+
+ - Function: compile->executable exename name1.scm name2.scm ...
+ Compiles and links the HOBBIT translation of NAME1.scm, NAME2.scm,
+ ... to a SCM executable named EXENAME. NAME1.scm must be in the
+ current directory; NAME2.scm, ... may be in other directories.
+
+ cd ~/scm/
+ scm -rcompile -e'(compile->executable "exscm" "example.scm")'
+
+ Starting to read example.scm
+
+ Generic (slow) arithmetic assumed: 1.0e-3 found.
+
+ ** Pass 1 completed **
+ ** Pass 2 completed **
+ ** Pass 3 completed **
+ ** Pass 4 completed **
+ ** Pass 5 completed **
+ ** Pass 6 completed **
+
+ C source file example.c is built.
+ C header file example.h is built.
+
+ These top level higher order procedures are not clonable (slow):
+ (nonkeyword_make-promise map-streams generate-vector runge-kutta-4)
+ These top level procedures create non-liftable closures (slow):
+ (nonkeyword_make-promise damped-oscillator map-streams scale-vector elementwise runge-kutta-4 integrate-system)
+
+ ; Scheme (linux) script created by SLIB/batch Sun Apr 7 22:46:31 2002
+ ; ================ Write file with C defines
+ (delete-file "scmflags.h")
+ (call-with-output-file
+ "scmflags.h"
+ (lambda (fp)
+ (for-each
+ (lambda (string) (write-line string fp))
+ '("#define IMPLINIT \"Init5d6.scm\""
+ "#define COMPILED_INITS init_example();"
+ "#define CCLO"
+ "#define FLOATS"))))
+ ; ================ Compile C source files
+ (system "gcc -O2 -c continue.c scmmain.c findexec.c script.c time.c repl.c scl.c eval.c sys.c subr.c debug.c unif.c rope.c example.c scm.c")
+ ; ================ Link C object files
+ (system "gcc -rdynamic -o exscm continue.o scmmain.o findexec.o script.o time.o repl.o scl.o eval.o sys.o subr.o debug.o unif.o rope.o example.o scm.o -L/usr/local/lib/scm/ -lm -lc")
+
+ Compilation finished at Sun Apr 7 22:46:44
+
+_Note Bene:_ `#define CCLO' must be present in `scmfig.h'.
+
+In order to see calls to the C compiler and linker, do
+
+ (verbose 3)
+
+before calling these functions.
+
+
+File: hobbit.info, Node: Error Detection, Next: Hobbit Options, Prev: Compiling And Linking, Up: Compiling with Hobbit
+
+Error Detection
+===============
+
+Error detection during compilation is minimal. In case your scheme code
+is syntactically incorrect, hobbit may crash with no sensible error
+messages or it may produce incorrect C code.
+
+Hobbit does not insert any type-checking code into the C output it
+produces. Eg, if a hobbit-compiled program applies `car' to a number,
+the program will probably crash with no sensible error messages.
+
+Thus it is strongly suggested to compile only throughly debugged scheme
+code.
+
+Alternatively, it is possible to compile all the primitives into calls
+to the SCM procedures doing type-checking. Hobbit will do this if you
+tell it to assume that all the primitives may be redefined. Put
+
+ (define compile-all-proc-redefined #t)
+
+anywhere in top level of your scheme code to achieve this.
+
+_Note Bene:_ The compiled code using
+
+ (define compile-all-proc-redefined #t)
+
+will typically be much slower than one produced without using
+
+ (define compile-all-proc-redefined #t).
+
+All errors caught by hobbit will generate an error message
+
+ COMPILATION ERROR:
+ <description of the error>
+
+and hobbit will immediately halt compilation.
+
+
+File: hobbit.info, Node: Hobbit Options, Next: CC Optimizations, Prev: Error Detection, Up: Compiling with Hobbit
+
+Hobbit Options
+==============
+
+ 1. Selecting the type of arithmetics.
+
+ By default hobbit assumes that only immediate (ie small, up to 30
+ bits) integers are used. It will automatically assume general
+ arithmetics in case it finds any non-immediate numbers like 1.2 or
+ 10000000000000 or real-only procedures like $sin anywhere in the
+ source.
+
+ Another way to make Hobbit assume that generic arithmetic supported
+ by SCM (ie exact and/or inexact reals, bignums) is also used, is to
+ put the following line somewhere in your scheme source file:
+
+ (define compile-allnumbers T)
+
+ where T is arbitrary.
+
+ In that case all the arithmetic primitives in all the given source
+ files will be assumed to be generic. This will make operations
+ with immediate integers much slower. You can use the special
+ immediate-integer-only forms of arithmetic procedures to recover:
+
+ %negative? %number? %> %>= %= %<= %<
+ %positive? %zero? %eqv? %+ %- %* %/
+
+ See *Note The Language Compiled::.
+
+ 2. Redefinition of procedures.
+
+ By default hobbit assumes that neither primitives nor compiled
+ procedures are redefined, neither before the compiled program is
+ initialized, during its work or later via the interpreter.
+
+ Hobbit checks the compiled source and whenever some variable bar is
+ defined as a procedure, but is later redefined, or set! is applied
+ to bar, then hobbit assumes thas this particular variable bar is
+ redefinable. bar may be a primitive (eg `car') or a name of a
+ compiled procedure.
+
+ _Note Bene:_ According to the Report 4 it is NOT allowed to use
+ scheme keywords as variables (you may redefine these as macros
+ defined by defmacro, though):
+
+ => and begin case cond define delay do else if lambda
+ let let letrec or quasiquote quote set! unquote unquote-splicing
+
+ If you want to be able to redefine some procedures, eg. `+' and
+ `baz', then put both
+
+ (set! + +)
+ (set! baz baz)
+
+ somewhere into your file.
+
+ As a consequence hobbit will generate code for `+' and `baz' using
+ the run-time values of these variables. This is generally much
+ slower than using non-redefined `+' and `baz' (especially for `+').
+
+ If you want to be able to redefine all the procedures, both
+ primitives (eg `car') and the compiled procedures, then put the
+ following into the compiled file:
+
+ (define compile-all-proc-redefined T)
+
+ where T is arbitrary.
+
+ If you want to be able to redefine all the compiled procedures,
+ but not the scheme primitives, then put the following into the
+ compiled file:
+
+ (define compile-new-proc-redefined T)
+
+ where T is arbitrary.
+
+ Again, remember that redefinable procedures will be typically much
+ slower than non-redefinable procedures.
+
+ 3. Inlined variables and procedures.
+
+ You may inline top-level-defined variables and procedures. Notice
+ that inlining is DIFFERENT for variables and procedures!
+
+ NEVER inline variables or procedures which are set! or redefined
+ anywhere in you program: this will produce wrong code.
+
+ * You may declare certain top-level defined variables to be
+ inlined. For example, if the following variable foo is
+ declared to be inlined
+
+ (define foo 100)
+
+ then `foo' will be everywhere replaced by `100'.
+
+ To declare some variables foo and bar to be inlined, put a
+ following definition anywhere into your file:
+
+ (define compile-inline-vars '(foo bar))
+
+ Usually it makes sense to inline only these variables whose value
+ is either a small integer, character or a boolean.
+
+ _Note Bene:_ Do not use this kind of inlining for inlining
+ procedures! Use the following for procedures:
+
+ * You may declare certain procedures to be inlined. For
+ example, if the following foo is declared to be inlined
+
+ (define (foo x) (+ x 2))
+
+ then any call
+
+ (foo SOMETHING)
+
+ will be replaced by
+
+ (+ SOMETHING 2)
+
+ Inlining is NOT safe for variable clashes - in other words, it is
+ not "hygienic".
+
+ Inlining is NOT safe for recursive procedures - if the set of
+ inlined procedures contains either immediate or mutual (foo calling
+ bar, bar calling foo) recursion, the compiler will not terminate.
+ To turn off full inlining (harmful for recursive funs), change the
+ definition of the *full-inlining-flag* in the section "compiler
+ options" to the value #f instead of #t.
+
+ To declare some procedures foo and bar to be inlined, put a
+ following definition anywhere into your file:
+
+ (define compile-inline '(foo bar))
+
+ 4. Speeding up vectors:
+
+ Put
+
+ (define compile-stable-vectors '(baz foo))
+
+ into your file to declare that baz and foo are vector names
+ defined once on the top level, and set! is never applied to them
+ (vector-set! is, of course, allowed). This speeds up vector
+ reference to those vectors by precomputing their location.
+
+ 5. Speeding up and hiding certain global variables:
+
+ Put
+
+ (define compile-uninterned-variables '(bazvar foovar))
+
+ into your file to declare that bazvar and foovar are defined on
+ the top level and they do always have an immediate value, ie a
+ boolean, immediate (30-bit) integer or a character. Then bazvar
+ and foovar will NOT be accessible from the interpreter. They'll
+ be compiled directly into static C vars and used without an extra
+ C *-operation prefixed to other global scheme variables.
+
+ 6. Intermediate files
+
+ To see the output of compiler passes, change the following
+ definition in `hobbit.scm'.
+
+ (define *build-intermediate-files* #f)
+
+ to:
+
+ (define *build-intermediate-files* #t)
+
+ 7. Name clashes
+
+ It may happen that several originally different scheme variable
+ names are represented by one and the same C variable. This will
+ happen, for example, if you have separate variables a-1 and a_1.
+
+ If such (or any other) name clashes occur you may need to change
+ some control variables in the first sections of `hobbit.scm' (up
+ to the section "global variable defs") or just rename some
+ variables in your scheme program.
+
+ 8. Other options
+
+ See various control variables in the first sections of `hobbit.scm'
+ (up to section "global variable defs").
+
+
+File: hobbit.info, Node: CC Optimizations, Prev: Hobbit Options, Up: Compiling with Hobbit
+
+CC Optimizations
+================
+
+When using the C compiler to compile the C code output by hobbit, always
+use strong optimizations (eg. `cc -xO3' for cc on Sun, `gcc -O2' or
+`gcc -O3' for gcc). Hobbit does not attempt to do optimizations of the
+kind we anticipate from the C compiler, therefore it often makes a
+serious difference whether the C compiler is run with a strong
+optimization flag or not.
+
+For the final and fast version of your program you may want to first
+recompile the whole scm (scmlit for the version scm4e2) using the
+`-DRECKLESS' flag suppressing error checking: the hobbit-compiled code
+uses some SCM primitives in the compiled files with the suffix .o, and
+a number of these primitives become faster when error checking is
+disabled by `-DRECKLESS'. Notice that hobbit never inserts error
+checking into the code it produces.
+
+
+File: hobbit.info, Node: The Language Compiled, Next: Performance of Compiled Code, Prev: Compiling with Hobbit, Up: Top
+
+The Language Compiled
+*********************
+
+Calls to `load' or `require' occurring at the top level of a file being
+compiled are ignored. Calls to `load' or `require' within a procedure
+are compiled to call (interpreted) `load' or `require' as appropriate.
+
+Several SCM and SLIB extensions to the Scheme report are recognized by
+hobbit as Scheme primitives.
+
+* Menu:
+
+* Macros::
+* SCM Primitive Procedures::
+* SLIB Logical Procedures::
+* Fast Integer Calculations::
+* Force and Delay::
+* Suggestions for writing fast code::
+
+
+File: hobbit.info, Node: Macros, Next: SCM Primitive Procedures, Prev: The Language Compiled, Up: The Language Compiled
+
+Macros
+======
+
+The Common-lisp style defmacro implemented in SCM is recognized and
+procedures defined by defmacro are expanded during compilation.
+
+_Note Bene:_ any macro used in a compiled file must be also defined in
+one of the compiled files.
+
+`#.<EXPRESSION>' is read as the object resulting from the evaluation of
+<EXPRESSION>. The calculation is performed during compile time. Thus
+<EXPRESSION> must not contain variables defined or set! in the compiled
+file.
+
+
+File: hobbit.info, Node: SCM Primitive Procedures, Next: SLIB Logical Procedures, Prev: Macros, Up: The Language Compiled
+
+SCM Primitive Procedures
+========================
+
+Real-only versions of transcedental procedures (warning: these
+procedures are not compiled directly into the corresponding C library
+procedures, but a combination of internal SCM procedures, guaranteeing
+exact correspondence with the SCM interpreter while hindering the
+speed):
+
+ $sqrt $abs $exp $log $sin $cos $tan $asin $acos
+ $atan $sinh $cosh $tanh $asinh $acosh $atanh $expt
+
+_Note Bene:_ These procedures are compiled to faster code than the
+corresponding generic versions sqrt, abs, ... expt.
+
+A selection of other extra primitives in SCM is also recognized as
+primitives. eg. get-internal-run-time, quit, abort, restart, chdir,
+delete-file, rename-file.
+
+
+File: hobbit.info, Node: SLIB Logical Procedures, Next: Fast Integer Calculations, Prev: SCM Primitive Procedures, Up: The Language Compiled
+
+SLIB Logical Procedures
+=======================
+
+The following bitwise procedures in the scheme library file
+`logical.scm' are compiled directly to fast C operations on immediate
+integers (small 30-bit integers) (Scheme library funs in the upper row,
+C ops below):
+
+ logand logior logxor lognot logsleft logsright
+ & | ^ ~ << >>
+
+The following alternative names logical:logand, logical:logior,
+logical:logxor, logical:lognot, ash, logical:ash are compiled for the
+generic case, not immediate-integers-only and are thus much slower.
+
+Notice that the procedures logsleft, logsright are NOT in the the
+library file `logical.scm:' the universal procedure ash is instead.
+Procedures ash, logcount, integer-length, integer-expt, bit-extract,
+ipow-by-squaring, logical:ash, logical:logcount, logical:integer-length,
+logical:integer-expt, logical:bit-extract, logical:ipow-by-squaring, in
+`logical.scm' are not primtives and they are all compiled into calls to
+interpreted code.
+
+logsleft and logsright are defined for non-compiled use in the file
+`scmhob.scm' included in the SCM distribution.
+
+
+File: hobbit.info, Node: Fast Integer Calculations, Next: Force and Delay, Prev: SLIB Logical Procedures, Up: The Language Compiled
+
+Fast Integer Calculations
+=========================
+
+The following primitives are for immediate (30-bit) integer-only
+arithmetics. The are compiled directly into the corresponding C
+operations plus some bitshifts if necessary. They are good for speed in
+case the compiled program uses BOTH generic arithmetics (reals, bignums)
+and immediate (30-bit) integer arithmetics. These procedures are much
+faster than corresponding generic procedures taking also reals and
+bignums. There is no point in using these unless the program as a whole
+is compiled using generic arithmetics, since otherwise all the
+arithmetics procedures are compiled directly into corresponding C
+operations anyway.
+
+_Note Bene:_ These primitives are NOT defined in SCM or its libraries.
+For non-compiled use they are defined in the file `scmhob.scm' included
+in the SCM distribution.
+
+ %negative? %number? %> %>= %= %<= %<
+ %positive? %zero? %eqv? %+ %- %* %/
+
+
+File: hobbit.info, Node: Force and Delay, Next: Suggestions for writing fast code, Prev: Fast Integer Calculations, Up: The Language Compiled
+
+Force and Delay
+===============
+
+The nonessential procedure `force' and syntax `delay' are implemented
+exactly as suggested in the report 4. This implementation deviates
+internally from the implementation of `force' and `delay' in the SCM
+interpeter, thus it is incorrect to pass a promise created by `delay'
+in the compiled code to the `force' used by interpreter, and vice-versa
+for the promises created by the interpreter.
+
+
+File: hobbit.info, Node: Suggestions for writing fast code, Prev: Force and Delay, Up: The Language Compiled
+
+Suggestions for writing fast code
+=================================
+
+The following suggestions may help you to write well-optimizable and
+fast code for the hobbit-scm combination. Roughly speaking, the main
+points are:
+
+ * minimizing consing and creation of new vectors and strings in
+ speed-critical parts,
+
+ * minimizing the use of generic (non-integer) arithmetics in
+ speed-critical parts,
+
+ * minimizing the usage of procedures as first-class objects (very
+ roughly speaking, explicit lambda-terms and call/cc) in
+ speed-critical parts,
+
+ * using special options and fast-compiled primitives of the compiler.
+
+Here come the details.
+
+ 1. Immediate arithmetics (ie using small, up to 30 bits integers) is
+ much faster than generic (reals and bignums) arithmetics. If you
+ have to use generic arithmetic in your program, then try to use
+ special immediate arithmetics operations `%=', `%<=', `%+', `%*',
+ ... for speed-critical parts of the program whenever possible.
+
+ Also, if you use bitwise logical operations, try to use the
+ immediate-integer-only versions
+
+ logand logior logxor lognot logsleft logsright
+
+ and not `logical:logand' or `ash', for example.
+
+ 2. Due to its inner stack-based architecture, the generic (not
+ escape-only) continuations are very slow in SCM. Thus they are
+ also slow in compiled code. Try to avoid continuations (calls to
+ the procedure call-with-current-continuation and calls to the
+ continuations it produces) in speed-critical parts.
+
+ 3. In speed-critical parts of your program try to avoid using
+ procedures which are redefined or defined by set!:
+
+ (set! bar +)
+ (set! f (lambda (x) (if (zero? x) 1 (* x (f (- x 1))))))
+
+ anywhere in the compiled program. Avoid using compiler flags
+ (*note Hobbit Options::):
+
+ (define compile-all-proc-redefined T)
+ (define compile-new-proc-redefined T)
+
+ 4. Do not use complicated higher-order procedures in speed-critical
+ parts. By "complicated" we mean "not clonable", where clonability
+ is defined in the following way (_Note Bene:_ the primitives `map'
+ and `for-each' are considered clonable and do not inflict a speed
+ penalty).
+
+ A higher-order procedure (HOP for short) is defined as a procedure
+ with some of its formal arguments occuring in the procedure body in
+ a function position, that is, as a first element of a list. Such
+ an argument is called a "higher-order argument".
+
+ A HOP `bar' is clonable iff it satisfies the following four
+ conditions:
+
+ 1. `bar' is defined as
+
+ (define bar (lambda ...))
+
+ or
+
+ (define (bar ...) ...)
+
+ on top level and bar is not redefined anywhere.
+
+ 2. the name `bar' occurs inside the body of bar only in a
+ function position and not inside an internal lambda-term.
+
+ 3. Let f be a higher-order argument of bar. Any occurrence of f
+ in bar has one of the following two forms:
+
+ * f occurs in a function position,
+
+ * f is passed as an argument to bar and in the call it
+ occurs in the same position as in the argument list.
+
+ 4. Let f be a higher-order argument of bar. f does not occur
+ inside a lambda-term occurring in bar.
+
+ Examples:
+
+ If `member-if' is defined on top level and is not redefined
+ anywhere, then `member-if' is a clonable HOP:
+
+ (define (member-if fn lst)
+ (if (fn (car lst))
+ lst
+ (member-if fn (cdr lst)) ))
+
+ member-if-not is not a clonable HOP (fn occurs in a
+ lambdaterm):
+
+ (define (member-if-not fn lst)
+ (member (lambda (x) (not (fn x))) lst) )
+
+ show-f is not a clonable HOP (fn occurs in a non-function
+ position in (display fn)):
+
+ (define (show-f fn x)
+ (set! x (fn x))
+ (display fn)
+ x)
+
+ 5. In speed-critical parts avoid using procedures which return
+ procedures.
+
+ Eg, a procedure
+
+ (define plus
+ (lambda (x)
+ (lambda (y) (+ y x)) ))
+
+ returns a procedure.
+
+ 6. A generalisation of the previous case 5:
+
+ In speed-critical parts avoid using lambda-terms except in
+ non-set! function definitions like
+
+ (define foo (lambda ...)),
+ (let ((x 1) (f (lambda ...))) ...)
+ (let* ((x 1) (f (lambda ...))) ...)
+ (let name ((x 1) (f (lambda ...))) ...)
+ (letrec ((f (lambda ...)) (g (lambda ...))) ...)
+
+ or as arguments to clonable HOP-s or primitives map and
+ for-each, like
+
+ (let ((x 0)) (map (lambda (y) (set! x (+ 1 x)) (cons x y)) LIST))
+ (member-if (lambda (x) (< x 0)) LIST)
+
+ where member-if is a clonable HOP.
+
+ Also, avoid using variables with a procedural value anywhere
+ except in a function position (first element of a list) or as
+ an argument to a clonable HOP, map or for-each.
+
+ Lambda-terms conforming to the current point are said to be
+ liftable.
+
+ Examples:
+
+ (define (bar x) (let ((f car)) (f (f x))))
+
+ has `car' in a non-function and non-HOP-argument position in
+ `(f car)', thus it is slower than
+
+ (define (bar x) (let ((f 1)) (car (car x))))
+
+ Similarly,
+
+ (define (bar y z w)
+ (let ((f (lambda (x) (+ x y))))
+ (set! w f)
+ (cons (f (car z))
+ (map f z) )))
+
+ has `f' occurring in a non-function position in `(set! w f)',
+ thus the lambda-term `(lambda (x) (+ x y))' is not liftable
+ and the upper `bar' is thus slower than the following
+ equivalent `bar' with a liftable inner lambda-term:
+
+ (define (bar y z w)
+ (let ((f (lambda (x) (+ x y))))
+ (set! w 0)
+ (cons (f (car z))
+ (map f z) )))
+
+ Using a procedure bar defined as
+
+ (define bar (let ((x 1)) (lambda (y) (set! x y) (+ x y))))
+
+ is slower than using a procedure bar defined as
+
+ (define *bar-x* 1)
+ (define bar (lambda (y) (set! *bar-x* y) (+ *bar-x* y)))
+
+ since the former definition contains a non-liftable
+ lambda-term.
+
+ 7. Try to minimize the amount of consing in the speed-critical
+ program fragments, that is, a number of applications of cons,
+ list, map, quasiquote (`) and vector->list during the time
+ program is running. `cons' (called also by `list', `map' and
+ `quasiquote') is translated into a C call to an internal cons
+ procedure of the SCM interpreter. Excessive consing also
+ means that the garbage collection happens more often. Do
+ `(verbose 3)' to see the amount of time used by garbage
+ collection while your program is running.
+
+ Try to minimize the amount of creating new vectors, strings
+ and symbols in the speed-critical program frgaments, that is,
+ a number of applications of make-vector, vector, list->vector,
+ make-string, string-append, *->string, string->symbol.
+ Creating such objects takes typically much more time than
+ consing.
+
+ 8. The Scheme iteration construction `do' is compiled directly
+ into the C iteration construction `for'. We can expect that
+ the C compiler has some knowledge about `for' in the
+ optimization stage, thus it is probably faster to use `do'
+ for iteration than non-mutual tailrecursion (which is
+ recognized by hobbit as such and is compiled into a jump to a
+ beginning of a procedure) and certainly much faster than
+ non-tail-recursion or mutual tailrecursion (the latter is not
+ recognized by hobbit as such).
+
+ 9. Declare small nonrecursive programs which do not contain
+ let-s or lambdaterms as being inlinable.
+
+ Declare globally defined variables which are never set! or
+ redefined and whose value is a small integer, character or a
+ boolean, as being inlinable. *Note Hobbit Options::.
+
+ 10. If possible, declare vectors as being stable. *Note Speeding
+ up vectors: Hobbit Options. This gives a minor improvement
+ in speed.
+
+ 11. If possible, declare critical global vars as being uninterned.
+ *Note Speeding up and hiding certain global variables: Hobbit
+ Options. This gives a minor improvement in speed. Declare
+ the global variables which are never set! and have an
+ (unchanged) numeric or boolean value as being inlined. *Note
+ Hobbit Options::.
+
+ In addition, take the following into account:
+
+ * When using the C compiler to compile the C code output by
+ hobbit, always use strong optimizations (eg. `cc -xO3' for cc
+ on Sun, `gcc -O2' or `gcc -O3' for gcc). Hobbit does not
+ attempt to do optimizations of the kind we anticipate from
+ the C compiler, therefore it often makes a big difference if
+ the C compiler is run with a strong optimization flag or not.
+
+ * hobbit does not give proper tailrecursion behaviour for mutual
+ tailrecursion (foo calling bar, bar calling foo
+ tailrecursively).
+
+ Hobbit guarantees proper tailrecursive behaviour for
+ non-mutual tailrecursion (foo calling foo tailrecursively),
+ provided that foo is not redefined anywhere and that foo is
+ not a local function which occurs also in a non-function and
+ non-clonable-HOP-argument position (i.e. cases 3 and 6 above).
+
+
+File: hobbit.info, Node: Performance of Compiled Code, Next: Principles of Compilation, Prev: The Language Compiled, Up: Top
+
+Performance of Compiled Code
+****************************
+
+* Menu:
+
+* Gain in Speed::
+* Benchmarks::
+* Benchmark Sources::
+
+
+File: hobbit.info, Node: Gain in Speed, Next: Benchmarks, Prev: Performance of Compiled Code, Up: Performance of Compiled Code
+
+Gain in Speed
+=============
+
+The author has so far compiled and tested a number of large programs
+(theorem provers for various logics and hobbit itself).
+
+The speedup for the provers was between 25 and 40 times for various
+provable formulas. Comparison was made between the provers being
+interpreted and compiled with `gcc -O2 -DRECKLESS' on Sparcstation ELC
+in both cases.
+
+The provers were written with care to make the compiled version run
+fast. They do not perform excessive consing and they perform very
+little arithmetic.
+
+According to experiments made by A. Jaffer, the compiled form of the
+example program `pi.scm' was approximately 11 times faster than the
+interpreted form.
+
+As a comparison, his hand-coded C program for the same algorithm of
+computing pi was about 12 times faster than the interpreted form.
+`pi.scm' spends most of of its time in immediate arithmetics,
+vector-ref and vector-set!.
+
+P. Kelloma"ki has reported a 20-fold speedup for his generic scheme
+debugger. T. Moore has reported a 16-fold speedup for a large
+gate-level IC optimizer.
+
+Self-compilation speeds Hobbit up only ca 10 times.
+
+However, there are examples where the code compiled by hobbit runs
+actually slower than the same code running under interpreter: this may
+happen in case the speed of the code relies on non-liftable closures
+and proper mutual tailrecursion. See for example the closure-intensive
+benchmark CPSTAK in the following table.
+
+
+File: hobbit.info, Node: Benchmarks, Next: Benchmark Sources, Prev: Gain in Speed, Up: Performance of Compiled Code
+
+Benchmarks
+==========
+
+We will present a table with the performance of three scheme systems on
+a number of benchmarks: interpreted SCM, byte-compiled VSCM and
+hobbit-compiled code. The upper 13 benchmarks of the table are the
+famous Gabriel benchmarks (originally written for lisp) modified for
+scheme by Will Clinger. The lower five benchmarks of the table are
+proposed by other people. "Selfcompile" is the self-compile time of
+Hobbit.
+
+Hobbit performs well on most of the benchmarks except CPSTAK and CTAK:
+CPSTAK is a closure-intensive tailrecursive benchmark and CTAK is a
+continuations-intensive benchmark. Hobbit performs extremely well on
+these benchmarks which essentially satisfy the criterias for
+well-optimizable code outlined in the section 6 above.
+
+FFT is real-arithmetic-intensive.
+
+All times are in seconds.
+
+SCM 4c0(U) and 1.1.5*(U) (the latter is the newest version of VSCM) are
+compiled and run by Matthias Blume on a DecStation 5000 (Ultrix). VSCM
+is a bytecode-compiler using continuation-passing style, and is well
+optimized for continuations and closures.
+
+SCM 4e2(S) and Hobbit4b(S) compiled (with `cc -xO3') and run by Tanel
+Tammet on a Sun SS10 (lips.cs.chalmers.se). Hobbit is a Scheme-to-C
+compiler for SCM, the code it produces does not do any checking. SCM
+and hobbit are not optimized for continuations. Hobbit is not
+optimized for closures and proper mutual tailrecursion.
+
+SCM and Hobbit benchmarks were run giving ca 8 MB of free heap space
+before each test.
+
+ Benchmark |SCM 4c0(U) 1.1.5*(U)| SCM 4e2(S) Hobbit4b(S)
+ ----------------|------------------------------------------------
+ Deriv | 3.40 3.86 | 2.9 0.18
+ Div-iter | 3.45 2.12 | 2.6 0.083
+ Div-rec | 3.45 2.55 | 3.5 0.42
+ TAK | 1.81 1.71 | 1.4 0.018
+ TAKL |14.50 11.32 | 13.8(1.8 in gc) 0.13
+ TAKR | 2.20 1.64 | 1.7 1.5 0.018
+ Destruct | ? ? | 7.4(1.8 in gc) 0.18
+ Boyer | ? ? | 27.(3.8 in gc) 1.9
+ CPSTAK | 2.72 2.64 | 2.0 1.92 3.46(2.83 in gc)
+ CTAK |31.0 4.11 | memory memory
+ CTAK(7 6 1) | ? ? | 0.83 0.74
+ FFT |12.45 15.7 | 11.4 10.8 1.0
+ Puzzle | 0.28 0.41 | 0.46(0.22 gc) 0.03
+ ----------------------------------------------------------------
+ (recfib 25) | ? ? | 4.1 0.079
+ (recfib 30) | ? ? | 55. (10.in gc) 0.87
+ (pi 300 3) | ? ? | 7.4 0.46
+ (hanoi 15) | ? ? | 0.68 0.007
+ (hanoi 20) | ? ? | 31. (9. in gc) 0.2
+ ----------------------------------------------------------------
+
+
+File: hobbit.info, Node: Benchmark Sources, Prev: Benchmarks, Up: Performance of Compiled Code
+
+Benchmark Sources
+=================
+
+A selection of (smaller) benchmark sources
+------------------------------------------
+
+* Menu:
+
+* Destruct::
+* Recfib::
+* div-iter and div-rec::
+* Hanoi::
+* Tak::
+* Ctak::
+* Takl::
+* Cpstak::
+* Pi::
+
+
+File: hobbit.info, Node: Destruct, Next: Recfib, Prev: Benchmark Sources, Up: Benchmark Sources
+
+Destruct
+--------
+
+ ;;;; Destructive operation benchmark
+ (define (destructive n m)
+ (let ((l (do ((i 10 (- i 1))
+ (a '() (cons '() a)))
+ ((= i 0) a))))
+ (do ((i n (- i 1)))
+ ((= i 0))
+ (if (null? (car l))
+ (do ((l l (cdr l)))
+ ((null? l))
+ (or (car l) (set-car! l (cons '() '())))
+ (append! (car l) (do ((j m (- j 1))
+ (a '() (cons '() a)))
+ ((= j 0) a))))
+ (do ((l1 l (cdr l1))
+ (l2 (cdr l) (cdr l2)))
+ ((null? l2))
+ (set-cdr! (do ((j (quotient (length (car l2)) 2) (- j 1))
+ (a (car l2) (cdr a)))
+ ((zero? j) a)
+ (set-car! a i))
+ (let ((n (quotient (length (car l1)) 2)))
+ (cond ((= n 0) (set-car! l1 '()) (car l1))
+ (else (do ((j n (- j 1))
+ (a (car l1) (cdr a)))
+ ((= j 1)
+ (let ((x (cdr a)))
+ (set-cdr! a '()) x))
+ (set-car! a i)))))))))))
+ ;; call: (destructive 600 50)
+
+
+File: hobbit.info, Node: Recfib, Next: div-iter and div-rec, Prev: Destruct, Up: Benchmark Sources
+
+Recfib
+------
+
+ (define (recfib x)
+ (if (< x 2)
+ x
+ (+ (recfib (- x 1))
+ (recfib (- x 2)))))
+
+
+File: hobbit.info, Node: div-iter and div-rec, Next: Hanoi, Prev: Recfib, Up: Benchmark Sources
+
+div-iter and div-rec
+--------------------
+
+ ;;;; Recursive and iterative benchmark divides by 2 using lists of ()'s.
+ (define (create-n n)
+ (do ((n n (- n 1))
+ (a '() (cons '() a)))
+ ((= n 0) a)))
+ (define *ll* (create-n 200))
+ (define (iterative-div2 l)
+ (do ((l l (cddr l))
+ (a '() (cons (car l) a)))
+ ((null? l) a)))
+ (define (recursive-div2 l)
+ (cond ((null? l) '())
+ (else (cons (car l) (recursive-div2 (cddr l))))))
+ (define (test-1 l)
+ (do ((i 300 (- i 1))) ((= i 0))
+ (iterative-div2 l)
+ (iterative-div2 l)
+ (iterative-div2 l)
+ (iterative-div2 l)))
+ (define (test-2 l)
+ (do ((i 300 (- i 1))) ((= i 0))
+ (recursive-div2 l)
+ (recursive-div2 l)
+ (recursive-div2 l)
+ (recursive-div2 l)))
+ ;; for the iterative test call: (test-1 *ll*)
+ ;; for the recursive test call: (test-2 *ll*)
+
+
+File: hobbit.info, Node: Hanoi, Next: Tak, Prev: div-iter and div-rec, Up: Benchmark Sources
+
+Hanoi
+-----
+
+ ;;; C optimiser should be able to remove the first recursive call to
+ ;;; move-them. But Solaris 2.4 cc, gcc 2.5.8, and hobbit don't.
+ (define (hanoi n)
+ (letrec ((move-them
+ (lambda (n from to helper)
+ (if (> n 1)
+ (begin
+ (move-them (- n 1) from helper to)
+ (move-them (- n 1) helper to from))))))
+ (move-them n 0 1 2)))
+
+
+File: hobbit.info, Node: Tak, Next: Ctak, Prev: Hanoi, Up: Benchmark Sources
+
+Tak
+---
+
+ ;;;; A vanilla version of the TAKeuchi function
+ (define (tak x y z)
+ (if (not (< y x))
+ z
+ (tak (tak (- x 1) y z)
+ (tak (- y 1) z x)
+ (tak (- z 1) x y))))
+ ;; call: (tak 18 12 6)
+
+
+File: hobbit.info, Node: Ctak, Next: Takl, Prev: Tak, Up: Benchmark Sources
+
+Ctak
+----
+
+ ;;;; A version of the TAK function that uses continuations
+ (define (ctak x y z)
+ (call-with-current-continuation
+ (lambda (k)
+ (ctak-aux k x y z))))
+
+ (define (ctak-aux k x y z)
+ (cond ((not (< y x)) (k z))
+ (else (call-with-current-continuation
+ (ctak-aux
+ k
+ (call-with-current-continuation
+ (lambda (k) (ctak-aux k (- x 1) y z)))
+ (call-with-current-continuation
+ (lambda (k) (ctak-aux k (- y 1) z x)))
+ (call-with-current-continuation
+ (lambda (k) (ctak-aux k (- z 1) x y))))))))
+
+ (define (id x) x)
+
+ (define (mb-test r x y z)
+ (if (zero? r)
+ (ctak x y z)
+ (id (mb-test (- r 1) x y z))))
+ ;;; call: (ctak 18 12 6)
+
+
+File: hobbit.info, Node: Takl, Next: Cpstak, Prev: Ctak, Up: Benchmark Sources
+
+Takl
+----
+
+ ;;;; The TAKeuchi function using lists as counters.
+ (define (listn n)
+ (if (not (= 0 n))
+ (cons n (listn (- n 1)))
+ '()))
+
+ (define l18 (listn 18))
+ (define l12 (listn 12))
+ (define l6 (listn 6))
+
+ (define (mas x y z)
+ (if (not (shorterp y x))
+ z
+ (mas (mas (cdr x) y z)
+ (mas (cdr y) z x)
+ (mas (cdr z) x y))))
+
+ (define (shorterp x y)
+ (and (pair? y) (or (null? x) (shorterp (cdr x) (cdr y)))))
+ ;; call: (mas l18 l12 l6)
+
+
+File: hobbit.info, Node: Cpstak, Next: Pi, Prev: Takl, Up: Benchmark Sources
+
+Cpstak
+------
+
+ ;;;; A continuation-passing version of the TAK benchmark.
+ (define (cpstak x y z)
+ (define (tak x y z k)
+ (if (not (< y x))
+ (k z)
+ (tak (- x 1)
+ y
+ z
+ (lambda (v1)
+ (tak (- y 1)
+ z
+ x
+ (lambda (v2)
+ (tak (- z 1)
+ x
+ y
+ (lambda (v3)
+ (tak v1 v2 v3 k)))))))))
+ (tak x y z (lambda (a) a)))
+ ;;; call: (cpstak 18 12 6)
+
+
+File: hobbit.info, Node: Pi, Prev: Cpstak, Up: Benchmark Sources
+
+Pi
+--
+
+ (define (pi n . args)
+ (let* ((d (car args))
+ (r (do ((s 1 (* 10 s))
+ (i 0 (+ 1 i)))
+ ((>= i d) s)))
+ (n (+ (quotient n d) 1))
+ (m (quotient (* n d 3322) 1000))
+ (a (make-vector (+ 1 m) 2)))
+ (vector-set! a m 4)
+ (do ((j 1 (+ 1 j))
+ (q 0 0)
+ (b 2 (remainder q r)))
+ ((> j n))
+ (do ((k m (- k 1)))
+ ((zero? k))
+ (set! q (+ q (* (vector-ref a k) r)))
+ (let ((t (+ 1 (* 2 k))))
+ (vector-set! a k (remainder q t))
+ (set! q (* k (quotient q t)))))
+ (let ((s (number->string (+ b (quotient q r)))))
+ (do ((l (string-length s) (+ 1 l)))
+ ((>= l d) (display s))
+ (display #\0)))
+ (if (zero? (modulo j 10)) (newline) (display #\ )))
+ (newline)))
+
+
+File: hobbit.info, Node: Principles of Compilation, Next: About Hobbit, Prev: Performance of Compiled Code, Up: Top
+
+Principles of Compilation
+*************************
+
+* Menu:
+
+* Macro-Expansion and Analysis:: Pass 1
+* Building Closures:: Pass 2
+* Lambda-lifting:: Pass 3
+* Statement-lifting:: Pass 4
+* Higher-order Arglists:: Pass 5
+* Typing and Constants:: Pass 6
+
+
+File: hobbit.info, Node: Macro-Expansion and Analysis, Next: Building Closures, Prev: Principles of Compilation, Up: Principles of Compilation
+
+Expansion and Analysis
+======================
+
+ 1. Macros defined by defmacro and all the quasiquotes are expanded
+ and compiled into equivalent form without macros and quasiquotes.
+
+ For example, `(a , x) will be converted to (cons 'a (cons x '())).
+
+ 2. Define-s with the nonessential syntax like
+
+ (define (foo x) ...)
+
+ are converted to defines with the essential syntax
+
+ (define foo (lambda (x) ...))
+
+ Non-top-level defines are converted into equivalent letrec-s.
+
+ 3. Variables are renamed to avoid name clashes, so that any local
+ variable may have a whole procedure as its scope. This renaming
+ also converts let-s to let*-s. Variables which do not introduce
+ potential name clashes are not renamed. For example,
+
+ (define (foo x y)
+ (let ((x y)
+ (z x))
+ (let* ((x (+ z x)))
+ x)))
+
+ is converted to
+
+ (define foo
+ (lambda (x y)
+ (let* ((x__1 y)
+ (z x)
+ (x__2 (+ z x__1)))
+ x__2)))
+
+ 4. In case the set of procedures defined in one letrec is actually not
+ wholly mutually recursive (eg, f1 calls f2, but f2 does not call
+ f1, or there are three procedures, f1, f2, f3 so that f1 and f2
+ are mutually recursive but f3 is not called from f1 or f2 and it
+ does not call them, etc), it is possible to minimize the number of
+ additional variables passed to procedures.
+
+ Thus letrec-s are split into ordered chunks using dependency
+ analysis and topological sorting, to reduce the number of mutually
+ passed variables. Wherever possible, letrec-s are replaced by
+ let*-s inside these chunks.
+
+ 5. Normalization is performed. This converts a majority of scheme
+ control procedures like cond, case, or, and into equivalent terms
+ using a small set of primitives. New variables may be introduced
+ in this phase.
+
+ In case a procedure like or or and occurs in the place where its
+ value is treated as a boolean (eg. first argument of if), it is
+ converted into an analogous boolean-returning procedure, which
+ will finally be represented by an analogous C procedure (eg. || or
+ &&).
+
+ Associative procedures are converted into structures of
+ corresponding nonassociative procedures. List is converted to a
+ structure of cons-s.
+
+ Map and for-each with more than two arguments are converted into an
+ equivalent do-cycle. map-s and for-each-s with two arguments are
+ treated as if they were defined in the compiled file - the
+ definitions map1 and for-each1 are automatically included, if
+ needed.
+
+ There is an option in `hobbit.scm' to make all map-s and
+ for-each-s be converted into equivalent do-loops, avoiding the use
+ of map1 and/or for-each1 altogether.
+
+ 6. Code is analysed for determining which primitive names and
+ compiled procedure names are assumed to be redefinable.
+
+ 7. Analysing HOP clonability: hobbit will find a list of clonable
+ HOP-s with information about higher-order arguments.
+
+ Criterias for HOP clonability are given in the section 6.4.
+
+ 8. Analysis of liftability: hobbit will determine which lambda-terms
+ have to be built as real closures (implemented as a vector where
+ the first element is a pointer to a function and the rest contain
+ values of environment variables or environment blocks of
+ surrounding code) and which lambda-terms are liftable.
+
+ Liftability analysis follows the criterias given in section 6.5 and
+ 6.6.
+
+
+File: hobbit.info, Node: Building Closures, Next: Lambda-lifting, Prev: Macro-Expansion and Analysis, Up: Principles of Compilation
+
+Building Closures
+=================
+
+Here Hobbit produces code for creating real closures for all the
+lambda-terms which are not marked as being liftable by the previous
+liftability analysis.
+
+Global variables (eg x-glob) are translated as pointers (locations) to
+SCM objects and used via a fetch: *x_glob (or a fetch macro
+GLOBAL(x-glob) which translates to *x_glob).
+
+While producing closures hobbit tries to minimize the indirection
+levels necessary. Generally a local variable x may have to be
+translated to an element of a vector of local variables built in the
+procedure creating x. If x occurs in a non-liftable closure, the whole
+vector of local variables is passed to a closure.
+
+Such a translation using a local vector will only take place if either x
+is set! inside a non-liftable lambda-term or x is a name of a
+recursively defined non-liftable function, and the definition of x is
+irregular. The definition of x is irregular if x is given the
+non-liftable recursive value T by extra computation, eg as
+
+ (set! x (let ((u 1)) (lambda (y) (display u) (x (+ u 1)))))
+
+and not as a simple lambdaterm:
+
+ (set! x (lambda (y) (display x) (x (+ y 1))))
+
+In all the other cases a local scheme variable x is translated directly
+to a local C variable x having the type SCM (a 32-bit integer). If
+such an x occurs in a non-liftable closure, then only its value is
+passed to a closure via the closure-vector. In case the
+directly-translated variable x is passed to a liftable lambda-term
+where it is set!, then x is passed indirectly by using its address &x.
+In the lifted lambda-term it is then accessed via *.
+
+If all the variables x1, ..., xn created in a procedure can be
+translated directly as C variables, then the procedure does not create a
+special vector for (a subset of) local variables.
+
+An application (foo ...) is generally translated to C by an internal
+apply of the SCM interpreter: apply(GLOBAL(foo), ...). Using an
+internal apply is much slower than using direct a C function call,
+since:
+
+ * there is an extra fetch by GLOBAL(foo),
+
+ * internal apply performs some computations,
+
+ * the arguments of foo are passed as a list constructed during
+ application: that is, there is a lot of expensive consing every
+ time foo is applied via an internal apply.
+
+However, in case foo is either a name of a non-redefined primitive or a
+name of a non-redefined liftable procedure, the application is
+translated to C directly without the extra layer of calling apply:
+foo(...).
+
+Sometimes lambda-lifting generates the case that some variable x is
+accessed not directly, but by *x. See the next section.
+
+Undefined procedures are assumed to be defined via interpreter and are
+called using an internal apply.
+
+
+File: hobbit.info, Node: Lambda-lifting, Next: Statement-lifting, Prev: Building Closures, Up: Principles of Compilation
+
+Lambda-lifting
+==============
+
+When this pass starts, all the real (nonliftable) closures have been
+translated to closure-creating code. The remaining lambda-terms are
+all liftable.
+
+Lambda-lifting is performed. That is, all procedures defined inside
+some other procedure (eg. in letrec) and unnamed lambda-terms are made
+top-level procedure definitions. Any N variables not bound in such
+procedures which were bound in the surrounding procedure are given as
+extra N first parameters of the procedure, and whenever the procedure is
+called, the values of these variables are given as extra N first
+arguments.
+
+For example:
+
+ (define foo
+ (lambda (x y)
+ (letrec ((bar (lambda (u) (+ u x))))
+ (bar y) )))
+
+is converted to
+
+ (define foo
+ (lambda (x y)
+ (foo-fn1 x y) ))
+
+ (define foo-fn1
+ (lambda (x u)
+ (+ u x) ))
+
+The case of mutually recursive definitions in letrec needs special
+treatment - all free variables in mutually recursive funs have, in
+general, to be passed to each of those funs. For example, in
+
+ (define (foo x y z i)
+ (letrec ((f1 (lambda (u) (if x (+ (f2 u) 1))))
+ (f2 (lambda (v) (if (zero? v) 1 (f1 z)))) )
+ (f2 i) ))
+
+the procedure f1 contains a free variable x and the procedure f2
+contains a free variable z. Lambda-lifted f1 and f2 must each get both
+of these variables:
+
+ (define (foo x y z i)
+ (foo-fn2 x z i) )
+
+ (define foo-fn1
+ (lambda (x z u) (if x (+ (foo-fn2 x z u) 1))) )
+
+ (define foo-fn2
+ (lambda (x z v) (if (zero? v) 1 (foo-fn1 x z z))) )
+
+Recall that hobbit has already done dependency analysis and has split
+the original letrec into smaller chunks according to this analysis: see
+pass 1.
+
+Whenever the value of some free variable is modified by set! in the
+procedure, this variable is passed by reference instead. This is not
+directly possible in scheme, but it is possible in C.
+
+ (define foo
+ (lambda (x y z)
+ (letrec ((bar (lambda (u) (set! z (+ u x z)))))
+ (bar y)
+ z)))
+
+is converted to incorrect scheme:
+
+ (define foo
+ (lambda (x y z)
+ (foo-fn1 x (**c-adr** z) y)
+ z))
+
+ (define foo-fn1
+ (lambda (x (**c-adr** z) u)
+ (set! (**c-fetch** z) (+ u x (**c-fetch** z))) ))
+
+The last two will finally be compiled into correct C as:
+
+ SCM foo(x, y, z)
+ SCM x, y, z;
+ {
+ foo_fn1(x, &z, y);
+ return z;
+ }
+
+ SCM foo_fn1(x, z, u)
+ SCM x, u;
+ SCM *z;
+ {
+ return (*z = (u + x) + *z);
+ }
+
+
+File: hobbit.info, Node: Statement-lifting, Next: Higher-order Arglists, Prev: Lambda-lifting, Up: Principles of Compilation
+
+Statement-lifting
+=================
+
+As the scheme do-construction is compiled into C for, but for cannot
+occur in all places in C (it is a statement), then if the do in a
+scheme procedure occurs in a place which will not be a statement in C,
+the whole do-term is lifted out into a new top-level procedure
+analogously to lambda-lifting. Any statement-lifted parts of some
+procedure foo are called foo_auxN, where N is a number.
+
+The special C-ish procedure **return** is pushed into a scheme term as
+far as possible to extend the scope of statements in the resulting C
+program. For example,
+
+ (define foo
+ (lambda (x y)
+ (if x (+ 1 y) (+ 2 y)) ))
+
+is converted to
+
+ (define foo
+ (lambda (x y)
+ (if x (**return** (+ 1 y)) (**return** (+ 2 y))) ))
+
+Immediate tailrecursion (foo calling foo tailrecursively) is recognized
+and converted into an assignment of new values to args and a jump to
+the beginning of the procedure body.
+
+
+File: hobbit.info, Node: Higher-order Arglists, Next: Typing and Constants, Prev: Statement-lifting, Up: Principles of Compilation
+
+Higher-order Arglists
+=====================
+
+All procedures taking a list argument are converted into ordinary
+non-list taking procedures and they are called with the list-making
+calls inserted. For example,
+
+ (define foo
+ (lambda (x . y)
+ (cons x (reverse y)) ))
+
+is converted to
+
+ (define foo
+ (lambda (x y)
+ (cons x (reverse y)) ))
+
+and any call to foo will make a list for a variable y. For example,
+
+ (foo 1 2 3)
+
+is converted to
+
+ (foo 1 (cons 2 (cons 3 '()))).
+
+All higher-order procedure calls where an argument-term contains
+unbound variables will generate a new instance (provided it has not
+been created already) of this higher-order procedure, carrying the
+right amount of free variables inside to right places.
+
+For example, if there is a following definition:
+
+ (define (member-if fn lst)
+ (if (fn (car lst))
+ lst
+ (member-if fn (cdr lst)) ))
+
+and a call
+
+ (member-if (lambda (x) (eq? x y)) lst),
+
+a new instance of member-if is created (if an analogous one has not
+been created before):
+
+ (define (member-if_inst1 tmp fn lst)
+ (if (fn tmp (car lst))
+ lst
+ (member-if_inst1 tmp fn (cdr lst)) ))
+
+and the call is converted to
+
+ (member-if_inst1 y foo lst)
+
+and a top-level define
+
+ (define (foo y x) (eq? x y))
+
+In addition, if the higher-order procedure is to be exported, an
+additional instance is created, which uses apply to call all
+argument-procedures, assuming they are defined via interpreter. The
+exportable higher-order procedure will have a name FUN_exporthof, where
+FUN is the name of the original procedure.
+
+
+File: hobbit.info, Node: Typing and Constants, Prev: Higher-order Arglists, Up: Principles of Compilation
+
+Typing and Constants
+====================
+
+All C<->Scheme conversions for immediate objects like numbers, booleans
+and characters are introduced. Internal apply is used for undefined
+procedures. Some optimizations are performed to decrease the amount of
+C<->Scheme object conversions.
+
+All vector, pair and string constants are replaced by new variables.
+These variables are instantiated to the right values by init_FOO*.
+
+Procedures foo which are to be exported (made accesible to the
+interpreter), and which have an arity different from one of the
+following five templates: x, (), (x), (x y), (x y z), are made
+accessible via an additional procedure foo_wrapper taking a single list
+argument.
+
+C Code Generation
+-----------------
+
+More or less straightforward.
+
+The type conversion between C objects and immediate Scheme objects of
+the type boolean, char and num is performed by macros. The scheme
+object '() is represented by the macro object EOL.
+
+Intermediate files
+------------------
+
+Experiment yourself by defining:
+
+ (define *build-intermediate-files* #t)
+
+instead of the default:
+
+ (define *build-intermediate-files* #f).
+
+
+File: hobbit.info, Node: About Hobbit, Prev: Principles of Compilation, Up: Top
+
+About Hobbit
+************
+
+* Menu:
+
+* The Aims of Developing Hobbit::
+* Manifest::
+* Author and Contributors::
+* Future Improvements::
+* Release History::
+
+
+File: hobbit.info, Node: The Aims of Developing Hobbit, Next: Manifest, Prev: About Hobbit, Up: About Hobbit
+
+The Aims of Developing Hobbit
+=============================
+
+ 1. Producing maximally fast C code from simple scheme code.
+
+ By "simple" we mean code which does not rely on procedures
+ returning procedures (closures) and nontrivial forms of
+ higher-order procedures. All the latter are also compiled, but
+ the optimizations specially target simple code fragments. Hobbit
+ performs global optimization in order to locate such fragments.
+
+ 2. Producing C code which would preserve as much original scheme code
+ structure as possible, to enable using the output C code by a
+ human programmer (eg. for introducing special optimizations
+ possible in C). Also, this will hopefully help the C compiler to
+ find better optimizations.
+
+
+File: hobbit.info, Node: Manifest, Next: Author and Contributors, Prev: The Aims of Developing Hobbit, Up: About Hobbit
+
+Manifest
+========
+
+`hobbit.scm' the hobbit compiler.
+`scmhob.scm' the file defining some additional procedures recognized
+ by hobbit as primitives. Use it with the interpreter
+ only.
+`scmhob.h' the common headerfile for hobbit-compiled C files.
+`hobbit.texi' documentation for hobbit.
+
+
+File: hobbit.info, Node: Author and Contributors, Next: Future Improvements, Prev: Manifest, Up: About Hobbit
+
+Author and Contributors
+=======================
+
+ Tanel Tammet
+ Department of Computing Science
+ Chalmers University of Technology
+ University of Go"teborg
+ S-41296 Go"teborg Sweden
+
+A. Jaffer (jaffer @ alum.mit.edu), the author of SCM, has been of major
+help with a number of suggestions and hacks, especially concerning the
+interface between compiled code and the SCM interpreter.
+
+Several people have helped with suggestions and detailed bug reports,
+e.g. David J. Fiander (davidf@mks.com), Gordon Oulsnam
+(STCS8004@IRUCCVAX.UCC.IE), Pertti Kelloma"ki (pk@cs.tut.fi), Dominique
+de Waleffe (ddw2@sunbim.be) Terry Moore (tmm@databook.com), Marshall
+Abrams (ab2r@midway.uchicago.edu). Georgy K. Bronnikov
+(goga@bronnikov.msk.su), Bernard Urban (Bernard.URBAN@meteo.fr),
+Charlie Xiaoli Huang, Tom Lord (lord@cygnus.com),
+NMICHAEL@us.oracle.com, Lee Iverson (leei@ai.sri.com), Burt Leavenworth
+(EDLSOFT@aol.com).
+
+
+File: hobbit.info, Node: Future Improvements, Next: Release History, Prev: Author and Contributors, Up: About Hobbit
+
+Future Improvements
+===================
+
+ 1. Optimisations:
+
+ * the calls to internal apply: we'd like to avoid the excessive
+ consing of always building the list of arguments.
+
+ * speeding up the creation of a vector for assignable
+ closure-variables
+
+ * several peephole optimisations.
+
+ 2. Improve Variable creation and naming to avoid C function name
+ clashes.
+
+ 3. Report 4 macros.
+
+ 4. Better error-checking.
+
+ 5. Better liftability analysis.
+
+ 6. More tailrecursion recognition.
+
+ 7. Better numeric optimizations.
+
+ 8. Fast real-only arithmetics: $eqv, $=, $>, $+, $*, etc.
+
+
+File: hobbit.info, Node: Release History, Prev: Future Improvements, Up: About Hobbit
+
+Release History
+===============
+
+ [In February 2002, hobbit5x was integrated into the SCM
+ distribution. Changes since then are recorded in `scm/ChangeLog'.]
+
+hobbit4d:
+ * the incorrect translation of char>?, char-ci>?, char>=?,
+ char-ci>=? string>?, string-ci>?, string-ci>=?, string>=?
+ reported by Burt Leavenworth (EDLSOFT@aol.com) was fixed.
+
+ * the name clash bug for new variables new_varN occurring in
+ non-liftable closures (reported by Lee Iverson
+ (leei@ai.sri.com)) was fixed.
+
+ * the major COPYRIGHT change: differently from all the previous
+ versions of Hobbit, hobbit4d is Free Software.
+
+hobbit4c:
+ * a liftability-analysis bug for for-each and map reported by
+ Lee Iverson (leei@ai.sri.com) has been fixed.
+
+ * The output C code does not contain the unnecessary ;-s on
+ separate lines any more.
+
+hobbit4b:
+ The following bugs have been fixed:
+ * Erroneous treatment of [ and ] inside symbols, reported by A.
+ Jaffer (jaffer @ alum.mit.edu).
+
+ * A bug in the liftability analysis, reported by A. Jaffer
+ (jaffer @ alum.mit.edu).
+
+ * A bug occurring in case arguments are evaluated right-to-left,
+ which happens with Hobbit compiled by gcc on Linux. Reported
+ and patched by George K. Bronnikov (goga@bronnikov.msk.su)
+
+ * A closure-building bug sometimes leading to a serious loss of
+ efficiency (liftability not recognized), reported by
+ NMICHAEL@us.oracle.com.
+
+ * A bug in the liftability analysis (non-liftable lambda-term
+ inside a liftable lambda-term) reported by Lee Iverson
+ (leei@ai.sri.com)
+
+hobbit4a:
+ Several bugs found in version4x are fixed.
+
+hobbit4x (not public):
+ * A major overhaul: Hobbit is now able to compile full scheme,
+ not just the fast liftable-clonable fragment.
+
+ The optimizations done by the earlier versions are preserved.
+
+ * Numerous bugs found in earlier versions have been fixed.
+
+hobbit3d:
+ bugs found in the version 3c are fixed.
+
+hobbit3c:
+ * the form
+
+ (define foo (let ((x1 <t1>) ... (xn <tn>)) (lambda ...)))
+
+ is now supported for all terms <ti> except procedures defined
+ in the compiled files.
+
+ * macros are partially supported by doing a preprocessing pass
+ using the procedures pprint-filter-file and defmacro:expand*
+ defined in slib.
+
+ * the file `scmhob.scm' defining hobbit-recognized nonstandard
+ procedures is created.
+
+ * the documentation is improved (thanks go to Aubrey for
+ suggestions).
+
+hobbit3b:
+ * Aubrey fixed some problems with the version 3.
+
+ * It is now OK to define procedures "by name" on top level.
+
+ * It is now OK to apply "apply", etc to procedures defined in
+ the compiled file. Compiled procedures may now be passed to
+ procedures not defined but still called in the compiled files.
+
+hobbit3:
+ * Generic arithmetic supported by SCM (exact and inexact reals,
+ bignums) is made available.
+
+ * The #. special syntactic form of SCM is made available.
+
+ * Procedures with chars are compiled open-coded, making them
+ faster.
+
+ * The bug concerning strings containing an embedded \nl char is
+ corrected (thanks to Terry Moore, (tmm@databook.com)).
+
+ * The special declaration compile-stable-vectors for optimizing
+ vector access is introduced.
+
+ * Source code may contain top-level computations, top-level
+ loads are ignored.
+
+ * The bug causing "or" to (sometimes) lose tailrecursiveness is
+ corrected.
+
+ * Hobbit now allows the following very special form:
+
+ (define foo (let ((bar bar)) (lambda ...)))
+
+ Notice `(bar bar)'. See the section 5 above. It will
+ produce wrong code if bar is redefined.
+
+ There were several versions of the 2-series, like 2.x, which
+ were not made public. The changes introduced are present in
+ the version 3.
+
+hobbit2:
+ * The following bitwise procedures in the scheme library file
+ `logical.scm' are compiled directly to C (Scheme library funs
+ in the upper row, C ops below):
+
+ logand logior logxor lognot logsleft logsright
+ & | ^ ~ << >>
+
+ Notice that the procedures logsleft, logsright are NOT in the
+ the library file `logical.scm': the universal procedure ash
+ is instead. Procedures ash, logcount, integer-length,
+ integer-expt, bit-extract in `logical.scm' are not recognized
+ by hobbit.
+
+hobbit1a3 (not public):
+ * the letrec-sorting bug often resulting in not recognizing
+ procedures defined in letrec (or local defines) has been
+ corrected.
+
+ * the primitives string and vector are now compiled correctly.
+
+hobbit1a2 (not public):
+ * any fixed arity procedure (including primitives) may be
+ passed to any higher-order procedure by name. Variable arity
+ procedures (eg primitives list, +, display and defined funs
+ like `(define (foo x . y) x)') must not be passed to new
+ defined higher-order funs.
+
+ * some optimizations have been introduced for calls to map and
+ for-each.
+
+ * (map list x y) bug has been corrected.
+
+ * Corrected self-compilation name clash between call_cc and
+ call-cc.
+
+hobbit1a1 (not public):
+ * named let is supported.
+
+ * the inlining bug is fixed: all procedures declared to be
+ inlined are fully inlined, except when the flag
+ *full-inlining-flag* is defined as #f.
+
+ * the letrec (or in-procedure define) bug where local procedure
+ names were not recognized, is fixed.
+
+ * documentation says explicitly that definitions like
+
+ (define foo (let ((x 0)) (lambda (y) ...)))
+
+ are assumed to be closure-returning procedures and are
+ prohibited.
+
+ * documentation allows more liberty with passing procedures to
+ higher-order funs by dropping the general requirement that
+ only unnamed lambda-terms may be passed. Still, primitives
+ and list-taking procedures may not be passed by name.
+
+ * documentation prohibits passing lambda-terms with free
+ variables to recursive calls of higher-order procedures in
+ the definition of a higher-order procedure.
+
+hobbit1:
+ the first release
+
+
+
+Tag Table:
+Node: Top199
+Node: Introduction1217
+Node: Compiling with Hobbit2533
+Node: Compiling And Linking2786
+Node: Error Detection7267
+Node: Hobbit Options8565
+Node: CC Optimizations15286
+Node: The Language Compiled16234
+Node: Macros16889
+Node: SCM Primitive Procedures17485
+Node: SLIB Logical Procedures18336
+Node: Fast Integer Calculations19616
+Node: Force and Delay20742
+Node: Suggestions for writing fast code21319
+Node: Performance of Compiled Code31510
+Node: Gain in Speed31766
+Node: Benchmarks33343
+Node: Benchmark Sources36435
+Node: Destruct36773
+Node: Recfib38348
+Node: div-iter and div-rec38591
+Node: Hanoi39665
+Node: Tak40234
+Node: Ctak40577
+Node: Takl41560
+Node: Cpstak42219
+Node: Pi42986
+Node: Principles of Compilation44103
+Node: Macro-Expansion and Analysis44525
+Node: Building Closures48308
+Node: Lambda-lifting51191
+Node: Statement-lifting53939
+Node: Higher-order Arglists55039
+Node: Typing and Constants56837
+Node: About Hobbit58093
+Node: The Aims of Developing Hobbit58335
+Node: Manifest59218
+Node: Author and Contributors59669
+Node: Future Improvements60719
+Node: Release History61476
+
+End Tag Table