src/interpreter/README

   1 Files in this directory implement the :sb-fasteval feature.
   2 The implementation is by Douglas Katzman.
   3
   4 This file serves as guide to care-and-feeding of the new feature.
   5
   6 Enabling
   7 ========
   8
   9 To use the new sb-fasteval interpreter, it must be compiled-in at
  10 build-time.  This can be done either by adding '--with-sb-fasteval
  11 --without-sb-eval' to the "make.sh" invocation, or by adding
  12 :sb-fasteval and removing :sb-eval from the
  13 'customize-target-features.lisp' file.  If building worked right,
  14 there should be an SB-INTERPRETER package.  There are external symbols
  15 in it, but none for public consumption.
  16
  17 As with sb-eval, the SB-EXT:*EVALUATOR-MODE* variable can be
  18 set to :INTERPRET or :COMPILE.
  19
  20 The REPL defaults to :INTERPRET if :sb-fasteval is enabled.  This is a
  21 change relative to existing behavior in which the REPL defaulted to
  22 :COMPILE.  For technical reasons, :INTERPRET is to be preferred, in
  23 that (COMPILE F) expressly requests compilation, whereas there is no
  24 means to expressly request interpretation other than having it be the
  25 default.
  26
  27 Advantages
  28 ==========
  29
  30 Speed:
  31
  32  * Toplevel form dispatch is slightly quicker.  It is not a linear
  33    scan over all 25 standard special operators.
  34
  35  * Macroexpansions are aggressively cached to avoid consing.
  36
  37  * Repeated syntactic/semantic analysis of forms is avoided,
  38    to the extent possible (subject to cache invalidation).
  39
  40  * LOAD on a source file is at least as fast as it would be
  41    with sb-eval, and usually significantly faster.
  42
  43 Safety:
  44
  45  * Type declarations and THE forms are respected unless
  46    OPTIMIZE qualities contraindicate checking.
  47
  48 Convenience:
  49
  50  * Maximal laziness - as per the above points, semantic analysis is
  51    performed to avoid subsequent work, however it is performed only
  52    just-in-time to evaluate each subform.  Huge swaths of code which
  53    are never reached incur no penalty.
  54
  55  * Global declarations (macros, types, etc) may be made out-of-order
  56    with respect to their first "apparent" use, if such use is in a
  57    function that is not called, just as would be true with a plain
  58    recursive-descent evaluator.  While not strictly an improvement
  59    over what the sb-eval interpreter offers, it is indeed more
  60    friendly than an interpreter which bakes in all semantics in a
  61    pre-pass.
  62
  63 OPTIMIZE Settings
  64 =================
  65
  66 The interpreter pays heed to the SPEED and SAFETY qualities
  67 in each lexical environment as they affect type-checking.
  68
  69 Entrance to a new LET, LET*, or LAMBDA scope:
  70  - initial bindings are checked if (>= SAFETY 1)
  71
  72  - declarations pertaining to lexically visible variables
  73    in containing scopes are checked if (>= SAFETY 2).
  74    The rationale is that tightening a type restriction
  75    is rare and unlikely to be strictly necessary.
  76    Weakening a restriction is correctly deemed a no-op.
  77
  78 Variable assignment (SETQ, etc):
  79  - checked if (>= SAFETY 1)
  80
  81 Variable access:
  82  - not checked, unless (AND (= SAFETY 3) (SPEED 0))
  83    We normally assume that variables have their correct types and that
  84    structure slots have their correct types.  As such, reads should be
  85    inherently type-correct.
  86
  87 THE forms:
  88  - checked if (>= SAFETY SPEED)
  89
  90 The effect of the above is that raising SPEED to 2 will continue
  91 to respect type-safety for binding and assignment, but ignore THE
  92 forms that are typically introduced into code "for efficiency".
  93 In as much as interpreted code can not be made to execute faster
  94 by adding type-checks, THE forms can reasonably be disregarded
  95 for the most part, but not by default.
  96
  97 If maximally fast interpreted code is desired, it is necessary
  98 to change three things: (SPEED 3) (SAFETY 0) (DEBUG 0).
  99 The DEBUG setting does not affect debuggability per se, however
 100 the combination of the above effectively disables macro cache flushes.
 101 That is, the interpreter forgoes any checking that it would
 102 otherwise do to see if a macro definition has changed.
 103
 104 Note that it is virtually impossible to run truly unsafe code
 105 in the interpreter, as at no point does it produce machine code
 106 except through the compiler in one particular situation limited
 107 to structure slot access.
 108
 109 Note also that FTYPE proclamations are always disregarded.
 110 It is unlikely that an enhancement to check FTYPE would be
 111 implemented, though it is within the realm of what could be done.
 112
 113 Performance
 114 ===========
 115
 116 Having been tested extensively on the CL-bench suite of tests,
 117 the performance can be characterized as anywhere from a 10x
 118 to 100x (or more) improvement over the sb-eval interpreter.
 119 Consing is also usually decreased by a factor of 5 to 10.
 120 However (as called out in Known Bugs) there is possibly
 121 a problem with garbage retention.  That said, the interpreter
 122 sees daily use in a production setting with no problems.
 123
 124 Technical Notes
 125 ===============
 126
 127 As mentioned in CLtL2, it is essentially impossible to use any
 128 standard mechanism to cache macros (notably *MACROEXPAND-HOOK*)
 129 because an identical form appearing in two distinct lexical
 130 environments may expand differently, and implementations are
 131 expressly permitted to stack-allocate environments,
 132 precluding their use as keys in persistent datastructures.
 133
 134 Caching works by assuming that if (MACRO-FUNCTION M) did not change,
 135 then an invocation of (M args...) will always expand to the same
 136 thing, if in the identical lexical environment.
 137 This can fail in certain situations, but all such situations
 138 would *also* be nearly certainly wrong in compiled code.
 139 The biggest problem would be with nondeterministic macros.
 140 CLHS states specifically that macros which depend on when or how
 141 many times they are called are unportable.
 142
 143 A more subtle problem is that while the MACRO-FUNCTION serves
 144 as part of the "key" to expansion, there is no such key
 145 for global symbol-macros.  If a macro M, during its expansion,
 146 inquires whether a symbol S is a symbol-macro, and the answer
 147 is "no", then if the answer becomes "yes", it might not happen
 148 that a subsequent invocation of M computes a new expansion.
 149
 150 Known Bugs
 151 ==========
 152
 153 * Reading through a symbol-macro is not inherently type-correct,
 154   but the interpreter does not cast the type onto the expansion.
 155   It does cast for SETF.  This is a compromise, as the existing
 156   behavior of the compiler is decidedly not ANSI-compliant.
 157   (It changes the macroexpansion to include a THE form).