content: = Client-side compiler =
  
  Our next goal is a browser-based edition of our compiler.
  
  == Crossly ==
  
  We first add a few features related to WebAssembly. Firstly, the `wasm` command
  compiles Haskell to C intended to be compiled to wasm. The resulting binary
  assumes the host environment supplies a few functions such as `env.getchar`.
  Secondly, the `warts` command prints the RTS generated by the compiler, also as
  C code intended to be compiled to wasm. We later use this to build compilers
  that can go directly from Haskell to wasm.
  
  We do some housekeeping. Given a `Neat`, type inference had produced a tuple of
  a particular type that contained the data needed by the next phase. We change
  it to produce a new `Neat` with an updated `typedAsts` field, so there's one
  fewer data type to occupy our thoughts and APIs. We no longer need to pick out
  specific fields to pass to the next phase, as we simply pass everything.
  
  We take a first stab at top-level type declarations. We treat them similarly to
  default typeclass methods, in that during type inference, we trust the symbol
  has its annotated type, and only afterwards that we verify the annotated type
  matches the inferred type. It's more complex because we must process an entire
  strongly connected component at a time.
  
  Adding modules has made a mess of our various functions for looking up data
  constructors, top-level variables, typeclasses, and so on. We reorganize them
  a little to standardize the logic for searching through the list of imports.
  This makes it easier to add support for lists of export symbols. We also
  replace the giant global operator precedence table with local tables.
  
  We experiment with hash consing which reduces heap usage by maximizing
  sharing. However, it may cost too much, as our compiler has grown appreciably
  slower.
  
  [#Ast3.toggleshow]
  ---------
  include::inn/Ast3.hs[]
  ---------
  
  [#Parser3.toggleshow]
  ---------
  include::inn/Parser3.hs[]
  ---------
  
  [#Typer3.toggleshow]
  ---------
  include::inn/Typer3.hs[]
  ---------
  
  [#party2.toggleshow]
  ---------
  include::inn/party2.hs[]
  ---------
  
  == Precisely ==
  
  Before proceeding, we crudely implement arbitrary-precision integers to enable
  some cool demos. It also exercises our code that handles typeclasses.
  
  Unlike standard Haskell, we add a `Ring` typeclass rather than `Num`. The `(+)`
  and `(*)` operators should be reserved for rings, and there are uses for rings
  that are not also instances of the `Num` typeclass. For example, Gaussian
  integers are great for indexing a 2D rectangular board, especially when we want
  to rotate by a right angle (multiplication by i) or talk about the cardinal
  directions (which correspond the units).
  
  The integers are https://en.wikipedia.org/wiki/Initial_algebra[the initial
  ring], so we treat the integer constant `n` as `fromInteger n`; if this results
  in ambiguity, then we drop `fromInteger`.
  
  Thus the laws that we know to be true in our bones, such as `a*(b + c) = a*b +
  a*c`, will never lead us astray. We must explicitly write `fromIntegral` to,
  say, map a `Word32` to a `Word64`. Other languages convert silently, and wind
  up defying our algebraic intuition.
  
  To represent an integer, we use a list of `Word32` numbers, plus a boolean to
  represent its sign. For GHC compatibility we call the function
  `integerSignList` instead of pattern matching on `Integer` values.
  
  We implement schoolbook algorithms for basic arithmetic, which is
  straightforward except for division. I realized that when doing long division
  by hand, to find the next digit of the divisor, I pick something that seems
  reasonable via a method that seems partly subconscious! How can we possibly
  code this?
  
  Luckily, there is a simple algorithm that makes good guesses. See Knuth, _The
  Art of Computer Programming_.
  
  We rename `div` and `mod` to `quot` and `rem`, then introduce wrappers for
  `div` and `mod`. Now our divisions behave correctly, though it is sad that
  `div` and `mod` need more instructions. (FORTRAN set an unfortunate precedent
  of truncating division to zero, ultimately
  https://github.com/WebAssembly/design/issues/250[forcing languages like C and
  WebAssembly and even hardware to conform].)
  
  Our treatment of integer literals causes a bootstrapping issue. Suppose a
  literal "0" is to be converted to an `Int`. Then our compiler applies the `Int`
  edition of `fromInteger` to the `Integer` 0, which involves a call to `mpView`,
  whose implementation needs the `Int` 0. If we simply code this as `0`, then we
  wind up with a circular definition, because our compiler would insert another
  `fromInteger` call. We work around this with a definition that bypasses
  overloading by returning `ord '\0'`.
  
  [#BasePrecisely.toggleshow]
  ---------
  include::inn/BasePrecisely.hs[]
  ---------
  
  == Wasm to Haskell? ==
  
  It'd be nice to write wasm ourselves, but for expedience, we rely on Clang to
  compile our runtime system to a wasm binary which we manipulate.
  WebAssembly turns out to be pleasantly malleable. A binary breaks up into
  independent sections, and we can add, delete, or modify sections before
  stitching them together again.
  
  We write a tool that just does enough wasm parsing to print the sections of a
  wasm file we want in the form of a Haskell module, and run this on the output
  of `crossly warts` to create `WartsBytes.hs`.
  
  [#warts2hs.toggleshow]
  ---------
  include::inn/warts2hs.hs[]
  ---------
  
  The RTS includes generate code that wraps foreign imports. It can only be used
  with programs that declare the same foreign imports.
  
  == Webby ==
  
  We build a compiler that goes directly from Haskell to wasm. The code does
  little more than dumping the runtime system wasm binary along with bytes
  describing the initial contents of the heap.
  
  For now we look for the `main` function in the `Main` module and export it as
  the `go` function; export declarations are ignored.
  
  [#Webby.toggleshow]
  ---------
  include::inn/Webby.hs[]
  ---------
  
  == webby.wasm ==
  
  To build a browser-based compiler, we essentially run the previous compiler on
  itself, thus producing a wasm binary that can translate Haskell directly into
  wasm.
  
  One change is needed: we swap `System.hs` for `SystemWasm.hs`. The
  Linux version declares foreign imports for those in our runtime system for
  Linux. The wasm version declares foreign imports for functions provided by
  the host environment.
  
  [#SystemWasm.toggleshow]
  ---------
  include::inn/SystemWasm.hs[]
  ---------
  
  == Messy ==
  
  By now, we're painfully aware of the effects of rash decisions made while
  writing our earlier compilers. Compilation time has grown rapidly. Parts of the
  code are difficult to extend.
  
  I'm cleaning up the `precisely` compiler first, and intend to backport the
  changes later, so the journey will look smoother. Until then, the evolution
  of our compiler will appear jumpy.
  
  Examples:
  
    * Rewriting let expressions as lambda terms should happen after
    type-checking, so that type annotations are easier to handle.
  
    * Some library-like functions like `overFree` should be scrapped because
    they're only used once.
  
    * I renamed `beta` to `fill` as it really fills holes in a context, that is,
    it substitutes without caring about variable capture. We get away with this
    because we unshadow variables during type-checking except for join point
    variables.
  
  Introducing features in a different order also smooths the journey. For
  example, I originally tried hash consing just before the `virtually` compiler,
  which slowed compilation and whose code changed markedly as syntax features
  were added. I pushed it to a far later compiler for faster bootstrapping and
  more stable code. Another example is the `Show` typeclass, which I originally
  added in a surprisingly recent compiler.
  
  Built-in primitives started in their own `#` module, then were replaced by code
  that pre-defined them for every module. But I think I was right the first time,
  and switched it back. Hopefully there are no traces of my misadventure left.
  
  At the same time, I'm introducing more chaos as I forge ahead with new
  experiments, especially those involving the web. The above only chronicles the
  start of adventures in the browser. A fuller account:
  
    * The `crossly wasm` command modifies the output C so Clang can compile it to
    wasm: it adds a minimal bump `malloc` implementation, and uses attributes to
    declare exports.
  
    * The `crossly warts` command also modifies the output C so Clang can compile
    to wasm, though it avoids `malloc` so it can prepopulate the heap. At the
    time, I didn't want to allocate a heap and then copy the initial state. It
    only generates code for FFIs and the RTS, and assumes a tool like `webby`
    will supply the initial heap contents.
  
    * The `Imp` compiler is like `webby` but with an extra hack to request the
    source of dependent import modules.
  
    * The `reply` family of REPLs introduced more complications. To avoid
    compiling `Base` every time, we define a CBOR-based object file format
    that contains the bytecode for each definition, along with symbols, types,
    typeclasses, fixities, type aliases, and so on.
  
    * For the REPL, we add a `scratchpad` buffer where the interpreter writes
    new bytecode. For definitions, we write the number of new symbols and call
    `vmgcroot()` to add roots so they survive GC. There's also a tagging
    mechanism, where the least significant bit indicates the rest of the word is
    the index of a previous definition. We do all this because GC could occur
    while compiling new definitions; the `scratchpad` is untouched by GC.
  
    * Related are `introspect.c`, which lets us examine the heap from the REPL,
    and a reduction function that is aware of "gas": a feature that allows us to
    run a program for a limited number of steps, and resume execution later if
    it has yet to finish.
  
  Designing the object file format leads us to take a closer look at the many
  phases of compilation:
  
    1. During parsing, we compile `data` declarations, generating
    ASTs for their Scott-encoding and lookup tables for field names.
    We also genreate instances for `deriving` clauses.
  
    2. During parsing, we generate selector code for each typeclass
    declaration.
  
    3. During parsing, we compile each FFI import to an `F` combinator,
    adding a lambda abstraction for each argument.
  
    4. Immediately after parsing, we find all exported symbols. The sole
    purpose of the `type2Cons` field is to find all exported constructors
    in a declaration like `Foo(..)`.
  
    5. We apply type aliases to canonicalize all type names.
  
    6. We topologically sort the modules, giving us an order which we can
    compile them. Recall our compilers expect the input to be the concatenation
    of all source modules, except for `imp.wasm`, which has a way of requesting
    more modules.
  
    7. We rewrite expressions according to fixity declarations, and rewrite
    pattern matches as lambda terms.
  
    8. At last, we compile top-level definitions to combinators, reconciling
    them with any type annotations. Life was simpler with our early compilers,
    where this was the only task we performed.
  
    9. It is only now we can compile typeclass instance definitions, as they may
    depend on top-level definitions. (In the previous step, there are
    dependencies going the other way, but we know the purported types of all
    instances, which is the only information needed.)
  
  Our data structures freely mix information collected during parsing with
  information generated by compilation.
  
  +++++++++
  include::toggleshow.js[]
  +++++++++
  