mvp.lhs

= Minimum Viable Product =

What features would make our compiler friendlier? My biggest gripes are that
symbols must be defined before use, a finicky parser that lacks support for
indentation rules, and pathetic error handling.

We work on the first two problems, and make a tiny dent on the third, while
taking care of a few other issues. This leads to a compiler that I found
surprisingly usable, at least when I could spot mistakes on my own.

== Mutually ==

C requires symbols to be declared before use. Our compilers are fussier still,
as they require symbols to be completely defined before use. This irks
programmers, especially when mutual recursion is desired, and also irks our
compilers, because we must process functions and instance methods in the order
they appear. This is particularly annoying when the two are interleaved.

Supporting arbitrary orderings of definitions requires changing multiple stages
of our compiler.

We break type inference into 3 steps:

  1. As we parse, we generate the type and abstract syntax tree of each data
  constructor and each typeclass method, adding them to pre-defined primitives.

  2. We infer the types of top-level definitions. For this stage, we construct
  a dependency graph (that is, we determine the symbols required by each
  symbol) then find its strongly connected components. Each member of a
  component mutually depends on each other member, and we infer their types
  together. Our `inferno` function continually piles on more type constraints
  for each member of a component, and only resolves them after all have been
  processed.

  3. We infer the type of instance method definitions, and check they are
  correct. A later compiler supports default class method definitions, which
  are also handled in this phase.

During code generation, we no longer know the address of a dependent symbol.
Instead, we must leave space for an address and fill it in later. We take
advantage of lazy tying-the-knot style so the code appears to effortlessly
solve this problem.

We also support definitions appearing in any order in a let block. This is
trickier than at the top-level, because of shared variable bindings floating
around. Again, we find the strongly connected components to detect mutual
dependencies, but instead of a table of addresses, we apply simple lambda
lifting.
See https://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-tutorial/[Peyton Jones and Lester, _Implementing Functional Languages: a tutorial_], Chapter 6.

In brief, we order the members of each component arbitrarily and insert
variables so they can all reach each other; we automate what we did by hand
when writing mutually recursive functions for older versions of our compiler.
For example:

------------------------------------------------------------------------
let
  a = foo a b c
  b = bar a b c
  c = baz a b c
in qux a b c
------------------------------------------------------------------------

is rewritten to the cycle-free:

------------------------------------------------------------------------
let
  a b c = foo (a b c) (b c) c
  b c   = bar (a b c) (b c) c
  c     = baz (a b c) (b c) c
in qux (a b c) (b c) c
------------------------------------------------------------------------

A triangle appears on the left-hand side, explaining our choice of function
name, and while the idea is straightforward, the implementation is tedious
because we recurse in all sorts of ways over the non-empty tails of lists of
variables, such as `[[a, b, c], [b, c], [c]]` and because we perform
substitutions in the syntax tree while it still possibly contains case
expressions and pattern matches.

As we now have a predefined `Bool` type, we use if-then-else instead of
matching on `True` and `False`.

[#mutually.toggleshow]
---------
include::mutually.hs[]
---------

We ignore the following subtle bug for now.
Consider definitions whose right-hand side is a lone variable. Our `optiComb`
function follows lone variables so that:

------------------------------------------------------------------------
f = g
g = h
h = f
x = (f, g, h)
y = x
z = y
w = (x, y, z)
------------------------------------------------------------------------

compiles to:

------------------------------------------------------------------------
f = g
h = g
g = Y I
x = (g, g, g)
y = x
z = x
w = (x, x, x)
------------------------------------------------------------------------

That is, afterwards, a variable with a lone variable definition only appears on
the right-hand side if its definition has been rewritten to `fix id`, so is no
longer a lone variable. Our `asm` function relies on this, because it skips
anything whose right-hand side is a lone variable.

This causes a corner case to fail: our compiler crashes on attempting to export
a symbol whose right-hand side remains a lone variable after `optiComb`.

== Virtually ==

Concatenating the runtime system with the compiler output is tiresome.  Our
next compiler also generates the source for the virtual machine.

We change `Int` from unsigned to signed.
We rename `(/)` and `(%)` to match Haskell's `div` and `mod`, though they
really should be `quot` and `rem`; we'll fix this later.

We add support for `newIORef`, `readIOref`, and `writeIORef`.
An IORef holding a value `x` of type `a` is represented as `REF x` where `REF`
behaves like `NUM`:

------------------------------------------------------------------------
REF x f --> f (REF x)
------------------------------------------------------------------------

Thus an IORef takes one app-cell in our VM, which adds a layer of indirection.
The address of this app-cell may be freely copied, and `writeIORef` can update
all these copies at once, by changing a single entry. We hardwire the following:

------------------------------------------------------------------------
newIORef = NEWREF
readIORef ref world cont = ref READREF world cont
writeIORef ref value world cont = ref (WRITEREF value) world cont
NEWREF value world cont = cont (REF value) world
READREF (REF x) world cont = cont x world
WRITEREF value (REF _) world cont = cont () world
------------------------------------------------------------------------

NEWREF has a subtle side effect: it ensures the `REF value` cell it creates is
new. Originally, we defined `newIORef value world cont = cont (REF value)
world` but this is unsafe because the `REF value` might be shared, causing
writes to stomp over each other.

WRITEREF also has a side effect: it overwrites the given app-cell with `REF
value` before returning `cont`. It is the only combinator that can modify the
values in the heap, excluding changes caused by lazy updates and garbage
collection.

We clean up top-level definitions as mutual recursion is now possible.

The `leftyPat` function supports patterns on the left-hand side of definitions,
for example:

------------------------------------------------------------------------
[a,b,c] = expr
------------------------------------------------------------------------

Our solution is simplistic. We find all pattern variables, such as  `a,b,c`. If
nonempty, we prepend `@` to the first variable, for example `@a`, to generate a
symbol unique to the current scope (a cheap trick to approximate Lisp's
`gensym`). Then we define this generated symbol to be the expression on the
right-hand side, for example `@a = expr`, and then we generate case expressions
for each pattern variable to define them, for example

------------------------------------------------------------------------
@a = expr
a = case @a of [a,b,c] -> a
b = case @a of [a,b,c] -> b
c = case @a of [a,b,c] -> c
------------------------------------------------------------------------

Our scheme fails to handle the wild-card pattern `_` correctly, which we'll
fix in a later compiler. Until then, we tread carefully with patterns on the
left.

[#virtually.toggleshow]
---------
include::virtually.hs[]
---------

== Marginally ==

https://en.wikipedia.org/wiki/Off-side_rule[Landin's off-side rule]
is sorely missed. Although cosmetic, layout parsing rules give Haskell a clean
mathematical look.

We split off a lexer from our parser, and follow the rules in section 10.3 of
https://www.haskell.org/onlinereport/haskell2010/haskellch10.html[the Haskell
2010 spec].

We add support for multiple predicates in the context of an instance. We should
have done this before, as it's just a small parser tweak; the rest of the code
can already handle it.

This is a good moment to support `do` notation. We deviate from the spec.
Trailing `let` statements are legal; they just have no effect. It is also legal
for the last statement to be a binding, in which case we implicitly follow it
with `pure ()`.

We replace `fpair` and `flst` with more idiomatic Haskell.

[#marginally.toggleshow]
---------
include::marginally.hs[]
---------

== Methodically ==

We correct a glaring defect. Up until now, the methods of an `instance` must be
defined in the same order they are declared in their `class`, otherwise bad
code is silently produced.

We add support for default methods as it involves the same code.  Our simple
approach insists the type of the default implementation of a method in a class
`Foo` to have the constraint of the form `+Foo a =>+`, because we always pass a
dictionary as the first argument. We could improve this slightly by inserting
`const` in the syntax tree if we deduce no constraints are present.

We ruthlessly remove semicolons and braces from our source.

Now that the syntax is slightly more pleasant:

  * We refine `leftyPat` so it correctly handles the wild-card pattern `_` in
  the left-hand side of a definition.

  * We support ranges, except for those that specify a step size.

  * We support list comprehensions.

We prepare to change `getChar` to match Haskell's, which throws an exception on
end of input. Up until now, ours simply calls the `getchar` function of C,
which returns -1 on end of input. Also, we would like Haskell's `isEOF` so we
can avoid this exception.

This takes two steps. The current compiler, whose RTS was generated by the
previous compiler, must use the `getChar` and `isEOF` of the previous
compiler. The most we can do is have it generate a new RTS supporting the
new `getChar` and `isEOF`. Programs compiled by this compiler will use these.
Our next compiler is one such program.

Complications arise because C's `feof(stdin)` only reports the end of input
after `getChar` has attempted to read past it and returned -1, while Haskell's
more clairvoyant version returns `True` before `getChar` would throw an error
because of the end of input. Additionally, our primitive FFI mechanism has
no way to convert a C int to `Bool`.

We write wrappers to get `getChar` and `isEOF` with the desired behaviour, and
add them to the C source to the runtime in the `RTS` module. Thus our next
compiler will print the new runtime in its output. However, it is unable to use
any new runtime features itself; only the programs it builds can do that.

If an FFI call encounters an error, instead of unceremoniously calling
`exit()`, we ought to push an exception-handling combinator on the stack. With
this in mind, I experimented with setting a global flag on failure to trigger
exception handling, but it caused a massive performance hit. Compiler build
times went up from around 7 seconds to 10 seconds on my laptop, mostly caused
by checking the flag for every `getChar`, `isEOF`, and `putChar` call. The
compiler source is about 70000 characters, and the output is about 200000
characters. Each input byte needs one `isEOF` and one `getChar` call, and each
output byte needs one `putChar` call, which suggests we're eating close to 10
extra microseconds per check.

I tried removing the flag and reordering foreign function calls so that they
occur after the stack has been primed to return results; this way, the foreign
call wrapper can simply push an exception combinator on the stack on error. But
I ran into a smaller but still significant performance hit. Even without
conditional branching in the happy path, the reordering is evidently enough to
mess up C compiler optimizations.

We can work around this problem with a better `getContents` implementation,
and indeed, perhaps this would already improve current build times.
For now we'll just put up with `exit()` instead of exceptions.

[#methodically.toggleshow]
---------
include::methodically.hs[]
---------

++++++++++
include::toggleshow.js[]
++++++++++