diff options
Diffstat (limited to 'hobbit.info')
| -rw-r--r-- | hobbit.info | 1952 |
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 |