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.

Manifest

Author and Contributors

Tanel Tammet
Department of Computing Science
Chalmers University of Technology
University of Go"teborg
S-41296 Go"teborg Sweden

A. Jaffer (agj @ 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).

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.

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 (agj @ alum.mit.edu).
• A bug in the liftability analysis, reported by A. Jaffer (agj @ alum.mit.edu).
• A bug occurring in case arguments are evaluated right-to-left, which happens with Hobbit compiled by gcc on GNU/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