content: = Modules =
  
  It's about time to add support for modules: our last compiler is almost 2000
  lines of code.
  
  == Party ==
  
  Continuing our RPG analogy, we liken modules to parties of heroes. Even in
  single-player games, we often direct a group of specialists rather than one
  powerful multi-talented being. Perhaps we enjoy observing teamwork, or
  following gaming traditions.
  
  But perhaps we also like parties for the same reasons we decompose a large
  problem into digestible subproblems. For example, we might only need to think
  about the intricacies of magic spells when controlling the wizard character.
  
  As usual, our first stab has limitations.
  This party is just getting started.
  
    * To avoid dealing with files, our compiler reads the concatenation of all
    the modules on standard input.
  
    * To keep parser changes minimal, all symbols are exported, and all module
    imports are unqualified.
  
    * Fixity declarations must precede all occurrences of their corresponding
    operators in the standard input.
  
    * At most one module should declare FFI imports.
  
    * Cyclic module dependencies cause an infinite loop.
  
  On the other hand, we proudly support `import` statements anywhere in the file,
  and multiple modules in the same file.
  
  In fact, this is why fixity declarations must appear first in the input. GHC
  insists on one module per file with imports appearing before other
  declarations, hence its parser can process imports before reaching any
  expressions and determine the fixity of any operators that appear when it later
  reaches them. With our scheme, we may encounter an operator in an expression
  before learning its fixity, which confuses our simple parser. In a later
  compiler we'll address this issue.
  
  We tweak the parser to support `module` and `import`, and add a new field to
  `Neat` that hold the imports of a module. A module with no explicit `module`
  declaration is taken to be the `Main` module. Concatenation implies such a
  module would have to appear first.
  
  We add a new `Link` field to the `Extra` data type, which holds the module,
  symbol, and type of a top-level variable defined in another module. During
  inference, we replace a `V` field with a `Link` field if we find it is exported
  from one of the imported modules.
  
  We introduce a one-off `Dep` monad because we lack monad transformers, and
  would like a combination of the `Either` and `State` monads when finding the
  dependencies of a definition.
  
  Up until now, all symbols were global across a single file. As we Scott-encoded
  ADTs and generated types and selector functions for typeclass methods, we
  simply threw them on a big pile in a `Neat` value being passed around.
  Modules force us to be more careful.
  
  We invent a special module "#" preloaded with built-in definitions required by
  the Haskell syntax we support:
  
    * The unit type and value `()` is part of the language.
    * If expressions and guards require `Bool`, `True`, and `False`.
    * Pairs are part of the language, even though suitably defined ADTs could be
      used instead (link:ioccc.html[the IOCCC edition of our compiler] does this
      to save room). Curiously, Haskell has no built-in type for the dual of
      pairs; requiring the programmer to define `Either`.
    * Lists are famously built into Haskell.
    * String literals require lists.
    * We compile recursive let definitions with `fix`.
    * Operations involving native integer types: `chr ord intAdd intMul`
      and so on.
    * Primitives for IO monad methods.
    * The RTS reduces `fail#` on failed case matches.
  
  Each module implicitly imports this special "#" module, so these built-in
  primitives are accessible to all.
  
  This is a good time to mention that rewriting means:
  
    * Ranges become expressions involving `enumFromTo` and `enumFrom`.
    * Failed pattern matches are `undefined`.
    * We need `pure` (for `pure ()`) and `>>=` to support `do` notation.
    * Patterns containing integer and character literals require `(==)`.
    * List comprehensions are expressed in terms of `concatMap` and `pure`.
  
  None of these are built-in; they must be explicitly defined at the top level if
  these language features are used. The last of these implies we must define an
  `Applicative` instance for lists. To remove these gotchas, we could define
  low-level primitives as we do for the others.
  
  Code generation now has two phases. The first corresponds to GHC incrementally
  compiling a module: it resolves all locally defined symbols, and leaves `Link`
  values indicating where to put addresses of symbols defined elsewhere. The
  generated code is not position-independent; rather, for each module, we are
  given the current heap pointer, and return an updated heap pointer.
  
  The second phase replaces all `Link` values with heap addresses, as all
  entities are in the heap by this point.
  
  Modules make us regret older expedient decisions regarding typeclasses.
  We threw default method definitions in one data structure, and lumped together
  method type signatures and instances in another. But now we might find a
  typeclass definition in one module, and an instance of it in another, so our
  code that searches imports for this information is messy. For example,
  the `fillSigs` helper raids other modules for the types of methods.
  
  We had previously substituted the syntax trees for default method
  implementations straight into instances. If we one day want incremental
  compilation, then it is likely easier to compile a default implementation
  once, then access it from other modules via a layer of indirection. With this
  in mind, for each method `foo`, we generate a method called `{default}foo`
  whose body is the default method implementation of `foo` if given, and
  `fail#` otherwise.
  
  Since we toss dictionary selector functions on to a big pile of ordinary
  definitions, to find the type of a method we add `typeOfMethod`, whose logic is
  similar to `findImportSym`, but differs enough that we implement it
  independently.
  
  We modify the code to insert dictionaries one strongly-connected-component at a
  time rather than one function at a time. This is required to correctly compile
  mutually recursive functions that use typeclasses. Each function of the
  component may wind up calling any other, so it needs all the relevant
  dictionaries.
  
  Up until now we had preserved topological order of the top-level definitions
  as they made their way through our compiler. We change the code generator so
  it no longer needs this precondition, so that we can store compiled functions
  and modules in maps rather than delicately manicured lists.
  
  We introduce a single combinator to act as `BK` which frequently occurs due to
  Scott encoding.
  
  If `B K x y z = x y` is reduced individually, our virtual machine allocates
  a new app-cell for `K (x y)`, only to immediately rewrite it as `I (x y)`,
  which again must be reduced to yield `x y` at last. The `BK` combinator
  avoids this needless song and dance.
  
  A dedicated `BK` combinator is also aesthetically pleasing. Consider some
  three-argument combinator given `x y z`. We can leave `x` alone or apply it to
  `z`, and similarly for `y`, and then apply the first thing to the second:
  
  ------------------------------------------------------------------------
  (x  )(y  )
  (x  )(y z)
  (x z)(y  )
  (x z)(y z)
  ------------------------------------------------------------------------
  
  The last 3 are the `B C S` combinators. The first one is `BK`.
  Smullyan appears not to have assigned a bird to this combinator, so we resort
  to the clunky name `BK` throughout our code.
  
  The BK combinator makes it easy for `optim` to rewrite `B BK V` as `CONS`.
  
  We add the `LEFT` combinator, which is equivalent to `B BK T` and also arises
  frequently in Scott encodings; indeed, the data constructor `Left` compiles to
  `LEFT`. We add the KI combinator to shave off a few more reductions.
  
  [#party.toggleshow]
  ---------
  include::party.hs[]
  ---------
  
  == Multiparty ==
  
  We put our changes to the test by splitting `party.hs` into modules.
  (We really should do the same for our "marginally" compiler, namely create
  an intermediate stage that is exactly the same except we use indentation
  instead of braces and semicolons. This would make it easier to compare against
  its successor "methodically".)
  
  ------------------------------------------------------------------------
  cat Base0.hs Ast.hs Map.hs Parser.hs Kiselyov.hs Unify.hs RTS.hs Typer.hs party.hs
  ------------------------------------------------------------------------
  
  [#Base0.toggleshow]
  ---------
  include::inn/Base0.hs[]
  ---------
  
  [#Map.toggleshow]
  ---------
  include::inn/Map.hs[]
  ---------
  
  [#Kiselyov.toggleshow]
  ---------
  include::inn/Kiselyov.hs[]
  ---------
  
  (There are more files, which I'll include if I get around to writing a tool to
  help show several source files in HTML. For now, see the git repo.)
  
  == GHC compatibility ==
  
  The main obstacle to compiling our modules with GHC is the Prelude. We define
  entities such as `Monad` and `(==)` from scratch, which breaks `do` notation
  for example because GHC always uses `Prelude.Monad`.
  
  We remove this obstacle by simply removing any overlap with the Prelude. We use
  a stripped-down `Base.hs` when testing with GHC, whereas our compilers really
  use files like `Base0.hs`.
  
  This implies much of our `Base` code is untested, but for this special case,
  perhaps we can add a wrapper to test it on its own with GHC.
  
  [#Base-GHC.toggleshow]
  ---------
  include::inn/Base.hs[]
  ---------
  
  Another obstacle is our built-in support for quasi-quoted raw strings. We solve
  this by adding the line:
  
  ------------------------------------------------------------------------
  import_qq_here = import_qq_here
  ------------------------------------------------------------------------
  
  immediately after the import statements. Then we enable the C pre-processor and
  define `import_qq_here` to be `import Text.RawString.QQ --`.
  
  We perform similar tricks to hide `Prelude` symbols we define in the `System`
  module.
  
  [#RTS-GHC.toggleshow]
  ---------
  include::inn/RTS.hs[]
  ---------
  
  Our source now works with GHC with the following options:
  
  ---------
  include::inn/compat.ghci[]
  ---------
  
  In the `inn` subdirectory:
  
  ------------------------------------------------------------------------
  $ ghci -ghci-script compat.ghci party.hs ../stub.o
  ------------------------------------------------------------------------
  
  Here, the `stub.o` has been created from `stub.c` with `clang -c` or similar.
  
  We gave the nice filenames to GHC, which expects to find modules in files with
  matching names. Our compilers tolerate weird filename prefixes and suffixes
  because we can simply concatenate different files. An alternative is to manage
  different subdirectories containing the same filenames.
  
  We can test later iterations with GHCi by symlinking appropriate versions of
  each file in a dedicated subdirectory.
  
  == Party1 ==
  
  Modules feel revolutionary. Our source becomes clearer, because modularization
  forces us to think about interdependencies, which guided refactoring so
  breaking up was less hard to do. And we can progress by making a small change
  to a small file, like our earliest compilers back in the day.
  
  However, we face new challenges. Addressing the limitations listed above will
  require effort. Prepending a little wrapper no longer suffices for GHC
  interoperability. And how are we going to keep track of many versions of many
  files?
  
  For now we answer the last question by tweaking an existing filename and
  `Makefile` rule. The module name remains the same but we concatenate a
  different file.
  
  For link:mvp.html[mutual let definitions] we wrote code that traversed a syntax
  tree to substitute certain variables. An alternative is to build a syntax tree
  that describes this substitution. After all, lambda calculus is substitution
  incarnate. In other words, we rely more on dynamic rather than static
  semantics, a distinction that sometimes blurs because beta-reducing may occur
  during optimization.
  
  One advantage of this approach is we can remove `overFreePro`, a helper that
  traverses over syntax trees before case expressions and pattern matches have
  been transformed away.
  
  We extend the parser to support named record fields in data type declarations
  such as:
  
  ------------------------------------------------------------------------
  data Foo = Foo { bar :: Int, baz :: String } | Qux
  ------------------------------------------------------------------------
  
  For accessors, we generate one function definition per field. For example:
  
  ------------------------------------------------------------------------
  bar = \case Foo bar baz -> bar
  ------------------------------------------------------------------------
  
  except at a lower level, exploiting our knowledge that our data types are
  Scott-encoded.
  
  Record updates and initialization are more challenging. We need more than plain
  function definitions, and furthermore, we only have all valid field names after
  parsing. This means we ought to extend our syntax tree to hold lists of field
  bindings for record updates and initializations.
  
  Instead of adding a new data constructor to our `Ast` type, we invent two
  basic combinators `Basic "{="` and `Basic "=}"` which act as delimiters
  for a list of field bindings, where the `A` data constructor acts like a cons.
  An alternative is to use recursion schemes for our many variants of syntax
  trees.
  
  By pattern compilation, we know all the field names, so at this point we call
  `resolveFieldBinds` to transform, say:
  
  ------------------------------------------------------------------------
  x { bar = 42 }
  ------------------------------------------------------------------------
  
  into:
  
  ------------------------------------------------------------------------
  case x of \Foo {orig}bar {orig}baz -> Foo 42 {orig}baz
  ------------------------------------------------------------------------
  
  though again using a lower level representation since we know we're
  Scott-encoding the data types. The `{orig}` added by our code to each variable
  name guards against variable capture.
  
  For record initializations, we only generate the right-hand side of the case
  match and use `undefined` for missing fields instead of `{orig}` variables.
  
  We implement `deriving` for `Eq` and `Show`. It would be nice to automatically
  derive `Eq` for our primitive data types (unit, boolean, pairs, lists) but this
  would require all programs to define the `Eq` class.
  
  Recall for data types, we maintain a map from a data constructor name to the
  list of all data constructors of the same type, along with the types of any
  field they may have. Even though we need to generate a unique and predictable
  symbol per type to represent corresponding case expressions, the function
  `specialCase` simply builds this symbol from the first data constructor.
  
  We barely modify this map for named fields. As a result, there's no easy way
  for `findField` to look up relevant information based on a field name. We
  inefficiently search linearly through possibly repeated entries. It may be
  better to add a separate map for named fields, but it's tedious to add fields
  to the `Neat` type when our current compiler lacks support for naming them!
  Once again, a proto-chicken comes first.
  
  To test with GHC, we create a new directory containing appropriately named
  symlinks to the desired versions of the modules. Incremental development means
  we only need to change a few symlinks at a time, but in the long run, we ought
  to automate symlinking from a given set of module files.
  
  [#Ast1.toggleshow]
  ---------
  include::inn/Ast1.hs[]
  ---------
  
  [#Parser1.toggleshow]
  ---------
  include::inn/Parser1.hs[]
  ---------
  
  [#Typer1.toggleshow]
  ---------
  include::inn/Typer1.hs[]
  ---------
  
  We replace a list with a `Map` for faster type unification.
  
  [#Unify1.toggleshow]
  ---------
  include::inn/Unify1.hs[]
  ---------
  
  == Party2 ==
  
  Recall we require a fixity declaration to precede the use of its corresponding
  operator, which forces us to concatenate module sources in a particular order.
  We remove this wart by adding a new phase. Once done, not only may we paste
  together modules in any order, but we may also declare fixities anywhere within
  a module.
  
  During parsing, operators have the same precedence. When a chain of two or more
  appear in a row, we abuse the syntax tree to store them in a right-associative
  list, for example: `[1 + 2, * 3, - 4, + 5]`.
  
  For patterns, we use the list field of a `PatCon` value; a made-up data
  constructor `"{+"` indicates the beginning of such a list. Expressions are
  clumsier; we bookend chains with `L "("` and `V ")"`, and fashion a list out of
  `A` and `V` nodes.
  
  Later, once all fixity declarations are known, we traverse the syntax tree, and
  we re-associate each specially marked infix chain. The algorithm starts with
  the first binary infix expression, that is, two operands and one operator such
  as `1 + 2`. For each operator and operand we add on the right, we walk down the
  right spine of the current syntax tree until we reach a node of higher
  precedence; leaf nodes are considered to have maximum precedence. Then we
  insert the operator and operand at this point. We also check for illegal infix
  operator conflicts.
  
  The code is messy due to a couple of wrinkles. Firstly, we have two distinct ad
  hoc representations of lists for holding infix chains. Secondly, we temporarily
  store the AST being reshaped in one-off tree structures.
  
  However, we're still cheating: we maintain one giant fixity declaration table
  for all operators across all modules, which relies on operators being distinct.
  Also, we only allow top-level fixity declarations. We could add support for
  scoped fixity declarations with yet more ad hoc encodings that we later use to
  create scoped fixity lookup tables that override the global ones.
  
  We fix the problem with foreign imports across multiple modules. In the
  lone-module days, we numbered the imports as we parsed the source. Now,
  the numbering must be consistent across all modules.
  
  In the spirit of incremental compilation, we replace the number of an import
  with its name in the syntax tree, which we map to a number during our code
  generation that corresponds to linking.
  
  We reuse the `Link` data constructor for this. The special `{foreign}` module
  indicates the function name is foreign.
  
  We also check for name conflicts among foreign imports and exports.
  
  We take advantage of our new ability to derive `Eq` and `Show` instances,
  and also name the fields of the `Neat` data type.
  
  https://www.haskell.org/onlinereport/syntax-iso.html[The Haskell report]
  describes layout parsing as a separate phase, and we had followed this closely
  in our first implementation of the feature.
  
  It turns out to be less code to inline the various bits and pieces of the
  layout logic in the parser. We do wind up with a touch more complexity, as
  comments and whitespace must be parsed in a different code path, but it's
  manageable.
  
  For parsing one of `let where do of`, and also `\case` since we act as if the
  `LambdaCase` is enabled, the `curlyCheck` function temporarily disables the
  angle-bracket indentation rule by placing an indent value of 0 at the head of
  the `indents` list.
  
  [#Base1.toggleshow]
  ---------
  include::inn/Base1.hs[]
  ---------
  
  [#Ast2.toggleshow]
  ---------
  include::inn/Ast2.hs[]
  ---------
  
  [#Parser2.toggleshow]
  ---------
  include::inn/Parser2.hs[]
  ---------
  
  [#Typer2.toggleshow]
  ---------
  include::inn/Typer2.hs[]
  ---------
  
  [#RTS1.toggleshow]
  ---------
  include::inn/RTS1.hs[]
  ---------
  
  [#party1.toggleshow]
  ---------
  include::inn/party1.hs[]
  ---------
  
  +++++++++
  include::toggleshow.js[]
  +++++++++
  