doc/mim.md

   1 # Component Relationships
   2
   3 ## MIM
   4
   5 Language with Muddle's control flow, object model, and syntax, but
   6 much more static semantics, straightforwardly compilable to MIM
   7 ops. Restrictions compared to Muddle:
   8 - no EVAL, BIND, or QUOTEd args
   9 - local variables must be resolvable lexically (explicit LVAL
  10   operations available for creating SPECIAL variables)
  11 - the first position of a form is bound to a function at compile time
  12 - FUNCTIONs can't be rebound from the perspective of MIM code (MUM can
  13   override anything for other MUM code, but the implementation of
  14   builtins written in MIM won't use the new versions)
  15 Most of these restrictions would have been in place in Muddle 105's
  16 MIMOC--at the time it was common practice for dynamic languages to
  17 have different semantics when compiled (full Muddle semantics are
  18 impossible to properly AOT compile; see *The Theory of Fexprs is
  19 Trivial*, M. Wand, '98).
  20
  21 ## MIMC
  22
  23 Library defining MIM as a collection of SUBRs that construct
  24 bytecode when invoked, so that a program written in MIM can be
  25 compiled by running it, and arbitrary code can be used in a macro-like
  26 manner. E.g. after importing MIMC, this call will push a single MIM
  27 operation into the current code buffer, looking up the buffer and the
  28 local slots in the current dynamic scope:
  29     <cons x xs = xxs>
  30 (This is actually a great example of the usefulness of dynamic scoping
  31 in enabling DSLs when context is important.) More complex MIM builtins
  32 (e.g. FCN, MAPF) will emit multiple opcodes, insert branches, build
  33 MSUBR headers, etc.
  34
  35 Generally, libraries written in MIM (incl. most of the stdlib) will be
  36 compiled AOT to reduce load time. We'll probably want to compile
  37 per-file and link separately (faster turnaround time when working on
  38 large libraries; enforces modularity).
  39
  40 ## MUMC
  41
  42 MUMC can be a method JIT implemented as an extension of MIMC. This
  43 eliminates the work of managing the correspondence between MUM's
  44 environment and control flow and MIM's. This mainly requires
  45 implementing some helper functions for complex MUM builtins, and
  46 supporting alternate semantics for some operations (e.g. when
  47 compiling in MUM mode locals are SPECIAL by default [just like
  48 changing Muddle 105's SPECIAL-MODE flag], and so new scopes will emit
  49 the LBIND-managing ops).
  50
  51 As mentioned above, full Muddle can't be AOT-compiled; but it's
  52 straightforward to method-JIT it to MIM *speculatively*, when the
  53 source is still available as a fallback if "dynamic behavior" is
  54 observed. This in itself doesn't have any benefit over only
  55 source-interpreting with an efficient format for structure constants,
  56 (packed into a vector in depth-first order). What it gets us is the
  57 power to perform some important optimizations relatively easily.
  58 - inline short MIM builtins (many operations are simpler to perform
  59   directly than to APPLY)
  60 - inline FEXPRs with constant folding and DCE
  61 We can eliminate the guards on the hotpath and pay almost no runtime
  62 cost to have the dynamic paths available (that is, when the user isn't
  63 actually redefining core builtins, UNASSIGNing the locals of their
  64 ancestors' scopes, and modifying the code of their callsites), if we
  65 set hooks for GVAL modifications to functions that are called by
  66 functions that have a JIT resident.
  67
  68 Also, once we have a basic working system and want to make it decently
  69 fast, for such a dynamic language the only way to go is with a tracing
  70 JIT for the hot loops--but just tracing an interpreter accomplishes
  71 nothing (see *Tracing The Meta-Level*, C. Bolz, '09). With the MUM
  72 method-jitted to MIM ops, a simple MIM bytecode JIT will also be a
  73 tracing JIT for MUM.
  74
  75 Example of what compiling some MUM-calls to MIM ops might look like
  76 (and where guards would be needed), along with structure constants
  77 (for fallback to EVAL) for the call
  78 `<A <B1> <B2 <C>>>`:
  79         consts:
  80                 call = [A B1 FORM:1 B2 C FORM:1 FORM:2 FORM:3] ;structured objects stored in depth-first vector
  81         entry:
  82                 ; [GVAL modification hook (A): enable bypass to slowpath-a]
  83                 <APPLYGLI B1 0 = PUSH> ; <APPLY G/LVAL IMM local:atom args:byte =>
  84                 ; [GVAL modification hook (B2): rewrite B1's return to slowpath-b2]
  85                 <APPLYGLI C 0 = PUSH>
  86                 <APPLYGLI B2 1 = PUSH>
  87         b2-done:
  88                 <APPLYGLI A 2 = ret>
  89         a-done:
  90                 <RET ret>
  91         slowpath-a:
  92                 <LOADRPN A.. = call>
  93                 <EVAL call = ret>
  94                 <JUMP a-done>
  95         slowpath-b2:
  96                 <LOADRPN B2.. = b2-call>
  97                 <EVAL b2-call = PUSH>
  98                 <JUMP b2-done>
  99
 100 # The Bytecode
 101
 102 ## Format
 103
 104 The MIM design is a 3-operand register machine. This is an excellent
 105 instruction format for enabling the implementation of an efficient
 106 interpreter, though it has a higher minimum complexity than other
 107 common layouts.
 108
 109 ## Encoding
 110
 111 The docs we have are mum about instruction encoding, but given this
 112 set of opcodes we're going to want something like this:
 113
 114 bit31                        bit0
 115 v                               v
 116 .-------------------------------.
 117 |   D   |   C   |   B   |  op   |
 118 '-------------------------------'
 119
 120 bit31                        bit0
 121 v                               v
 122 .-------------------------------.
 123 |      CD       |   B   |   op  |
 124 '-------------------------------'
 125
 126 32-bit fixed-width operations with 1-byte fields are easy to decode.
 127 Storing the op at the numerically low end makes it easiest to read
 128 first. Operand B can be decoded with the opcode before dispatching,
 129 which enables simplifications like a fallthrough implementation for
 130 ops that have one variant that takes an immediate in the B position
 131 and another variant (with a different opcode) that takes a local.
 132
 133 Operand types can be:
 134 - immediate Byte (incl. signed offset for must jump operations)
 135 - immediate Word (offset for the "long jumps"--JUMP/EMP?/FALSE?)
 136 - index into the current function's Constants table
 137 - index into the current function's Locals table
 138 - index into the Locals table containing an LVAR to be dereferenced
 139 Generally each opcode has a fixed interpretation of each operand; any
 140 necessary variants are encoded as separate opcodes rather than
 141 branching on flag bits. The only common non-guard branches are the
 142 opcode dispatch, (occasionally prefixed-opcode dispatch), and dispatch
 143 for polymorphic/mistyped ops.
 144 Some ops use use base/length pairs to blit ranges of locals/constants.
 145
 146 Some ~1/3 of the operations in the MIM docs are both rare (unlikely to
 147 occur in hot loops) and short (don't need all 3 operand bytes), so we
 148 can encode them all under 1 prefix opcode and sub-dispatch on operand
 149 B, freeing a lot of opcode space for more critical instructions.
 150
 151 ## Type System
 152
 153 The type system is mostly the same between the level of MIM ops and
 154 MUM, with some caveats. MIM mostly looks at PRIMTYPEs and doesn't care
 155 about the high bits, while MIM-level PRIMTYPEs have a couple of bits
 156 that are masked out from MUM's view, to support the implementation of
 157 weak pointers (STACK objects) and large allocations (see below).
 158
 159 STRING will need to have a different PRIMTYPE from BYTES, because it
 160 would be unsafe to allow CHTYPE-ing arbitrary BYTES to utf-8 STRINGs
 161 (and would expose the implementation detail of our string encoding;
 162 eventually we might want to switch to Python 3's uniform-1/2/4 format,
 163 trading some type system complexity for more speed).
 164
 165 To be compatible with MUM's polymorphic builtins, operations like
 166 <REST> are polymorphic in bytecode. Operations that need to be fast
 167 (like the primary looping operator, used for MAPF) also have
 168 type-specialized versions for the major types. At opcode level, typing
 169 is weak: when a typed opcode is applied to the wrong kind of object,
 170 it redispatches to the polymorphic implementation; an ERROR only
 171 occurs if no version of the operation is applicable to the
 172 operand. This allows the implementation to support inline caching:
 173 when a polymorphic loop operator is invoked, after dispatching on the
 174 collection's type it overwrites the instruction pointer with the
 175 type-specialized version of its opcode. Thus only the first iteration
 176 of any loop requires polymorphic dispatch.
 177
 178 ## Object Format
 179
 180 We can fit them in 64 bits!
 181
 182 A typical object layout, common to UBLOCK/BYTES/STRING:
 183 bit63
 184 v
 185 .-------------------------------.
 186 |            end-ptr            |
 187 +-------------------------------+
 188 |     length    |  Typ  | Prim  |
 189 '-------------------------------'
 190                                 ^
 191                                                          bit0
 192 The address is 32-bit. Length is 16-bit, with an interpretation that
 193 scales by object size. REST and EMPTY? don't need to tell the 3 object
 194 types apart (less dispatching), but NTH needs to know the item
 195 length. A "normal" allocation can be used for lengths up to 2**16
 196 objects.
 197
 198 Large object layout for UBLOCK/BYTES/STRING:
 199 .-------------------------------.
 200 |            cur-pos            |
 201 +-------------------------------+
 202 |   end-align   |  Typ  | Prim  |
 203 '-------------------------------'
 204 Cur-pos is a pointer, potentially offset from a static
 205 large-allocations base and scaled by object size. End-align indicates
 206 the number of trailing zero bits in the allocation's past-the-end
 207 address.
 208
 209 This large object model comes out of two observations:
 210 - Language semantics require that typical operations on collections be
 211   polymorphic anyway, so there's little cost to potentially
 212   dispatching to one more type of alternate format (especially since
 213   we'll never have to dispatch in loops).
 214 - For objects larger than 64KB we probably want to mmap the allocation
 215   outside the normal heap in any case, so at that point we can find a
 216   highly-aligned location and use the alignment to only need to store
 217   the log2 of the length.
 218
 219 ## Additional/Modified Opcodes
 220
 221 - <FALSE? local:any tgt:2byte>
 222   - This seems essential, not sure why there's nothing like it in the
 223     docs.
 224 - LENL: added a max-value
 225   - LENGTH can be implemented in terms of LENGTH? with an optional
 226     max, but not the other way around
 227 - <ERROR local:atom local:any local:any>
 228   - Seems necessary.
 229 - <DESTRUC(L/U/B/R/.../x)? target:byte =>
 230   - Single-op implementation of idiomatic loops (MAPF/MAPR). Has the
 231     semantics of REST-NTH_1-EMPTY?-JUMP, but with much less work.
 232 - implementing RETURN:
 233   - CALLs (and RESUMEs) are decoded twice: the 1st time does a call
 234     (ignoring the parameter specifying the result destination); the
 235     2nd reads only the result byte (of the instruction that is
 236     *before* the return address, e.g. last executed before call) so it
 237     knows what local to set with its result. (Result parameters are
 238     always in the D position, so RETURN doesn't need to know *what*
 239     it's returning to.)
 240
 241 # GC interface
 242
 243 The bulk of the GC (marker/sweeper, compactor) can be written in MIM,
 244 and run in an internal PROCESS, though some fundamental ops need to be
 245 compiled for a particular type of GC implementation (because hooks for
 246 allocation and read/write barriers need to be as fast as possible).