content: = Patterns and Guards =
  
  Patterns and guards make programming much more pleasant.
  
  == Patty ==
  
  We support definitions spread across multiple equations, and patterns in
  lambdas, case expressions, and the arguments of function definitions.
  
  We leave supporting patterns as the left-hand side of an equation for another
  day. We also ignore fixity declarations for pattern infix operators.
  
  We probably should have started by reading Peyton Jones,
  https://www.microsoft.com/en-us/research/wp-content/uploads/1987/01/slpj-book-1987-small.pdf[_The
  Implementation of Functional Programming Languages_], Chapter 5.
  Instead, we forge ahead with the first algorithm that comes to mind.
  
  Consider a top-level function defined with multiple equations:
  
  \begin{code}
  f (Left (Right x)) y     z@(_, 42) = expr1:
  f (Right a)        "foo" y         = expr2;
  \end{code}
  
  This is parsed as:
  
  \begin{code}
  f = Pa [ ([(Left (Right x)), y,     z@(_, 42)], expr1)
         , ([(Right a)       , "foo", y        ], expr2)
         ]
  \end{code}
  
  where `Pa` is a data constructor for holding a collection of lists of patterns
  and their corresponding expressions.
  
  We rewrite this as a lambda expression.  Since there are 3 parameters, we
  generate 3 variable names and begin defining `f` as:
  
  \begin{code}
  f = \1# 2# 3# -> ...
  \end{code}
  
  In our example, we start numbering the generated variable names from 1, but in
  general they start from the value of a carefully maintained counter.
  
  We bind a `join#` variable that represents a join point which we later
  construct from the other defining equations.
  
  \begin{code}
  f = \1# 2# 3# -> \join# -> ...
  \end{code}
  
  The first pattern of the first equation is `(Left (Right x))`, so we add:
  
  \begin{code}
  f = \1# 2# 3# -> \join# -> case 1# of
  { Left 4# -> case 4# of
    { Left _ -> join#
    ; Right 5# -> ...
    }
  ; Right _ -> join#
  }
  \end{code}
  
  We encounter a variable `x` so we replace all free occurrences of `x` in
  `expr1` with `5#` which we denote `expr1[5#/x]`.
  
  The second pattern is `y`, so we replace all free occurrences of this
  variable in `expr1` with `2#` to get `expr1[5#/x,2#/y]`.
  
  For the third pattern, we start by replacing all free occurrences of `z` in
  with `3#`. We have finished the first equation so we apply what we have so far
  to the expression we will obtain from rewriting the other definitions.
  
  \begin{code}
  f = \1# 2# 3# -> (\join# -> case 1# of
  { Left 4# -> case 4# of
    { Left _ -> join#
    ; Right 5# -> case 3# of
      { (6#, 7#) -> if 7# == 42 then expr1[5#/x,2#/y,3#/z] else join#
      }
    }
  ; Right _ -> join#
  }) $ ...
  \end{code}
  
  The first pattern of the second equation is `Right a`.
  
  \begin{code}
  f = \1# 2# 3# -> (\join# -> case 1# of
  { Left 4# -> case 4# of
    { Left _ -> join#
    ; Right 5# -> case 3# of
      { (6#, 7#) -> if 7# == 42 then expr1[5#/x,2#/y,3#/z] else join#
      }
    }
  ; Right _ -> join#
  }) $ \join# -> case 1# of
  { Left _ -> join#
  ; Right 8# -> ...
  }
  \end{code}
  
  We replace all free occurrences of `a` in `expr2` with `8#`, which we denote
  `expr2[8#/a]`.
  
  Continuing in this fashion, by the end of the second equation we arrive at:
  
  \begin{code}
  f = \1# 2# 3# -> (\join# -> case 1# of
  { Left 4# -> case 4# of
    { Left _ -> join#
    ; Right 5# -> case 3# of
      { (6#, 7#) -> if 7# == 42 then expr1[5#/x,2#/y,3#/z] else join#
      }
    }
  ; Right _ -> join#
  }) $ (\join# -> case 1# of
  { Left _ -> join#
  ; Right 8# -> if 2# == "foo" then expr2[8#/a,3#/y] else join#
  }) $ ...
  \end{code}
  
  As there are no more equations, we finish off with `fail#`, which causes
  program termination on execution:
  
  \begin{code}
  f = \1# 2# 3# -> (\join# -> case 1# of
  { Left 4# -> case 4# of
    { Left _ -> join#
    ; Right 5# -> case 3# of
      { (6#, 7#) -> if 7# == 42 then expr1[5#/x,2#/y,3#/z] else join#
      }
    }
  ; Right _ -> join#
  }) $ (\join# -> case 1# of
  { Left _ -> join#
  ; Right 8# -> if 2# == "foo" then expr2[8#/a,3#/y] else join#
  }) $ fail#
  \end{code}
  
  We treat case expressions as applying a special case of the above to the
  scrutinee, namely the case when there is exactly one pattern per alternative.
  This is horribly inefficient, and indeed, I originally insisted on coding a
  jump table. My position has evolved: for the sake of less incomprehensible
  code, better to put up with a few seconds extra of compilation, and postpone
  faster case expressions to our next compiler.
  
  We try to avoid dead code with the `optiApp` helper which beta-reduces
  applications of lambdas where the bound variable appears at most once in the
  body, but this is imperfect because of the `Pa` value that may appear during
  `Ca` rewrites: we look for the bound variable before rewriting the `Pa` value,
  thus our count is wrong if the variable is later eliminated when rewriting the
  `Pa` value.
  
  We predefine the `Bool` type, as our next compiler will handle guards, which
  translate to expressions involving booleans.
  
  [#patty.toggleshow]
  ---------
  include::patty.hs[]
  ---------
  
  == Guardedly ==
  
  Now that the syntax lets us breathe easier, we immediately work on speedier
  case expressions via jump tables. Suppose we have:
  
  \begin{code}
  case scrutinee of
    Foo (Left 42) -> expr1
    Baz           -> expr2
    Foo (Right a) -> expr3
    Bar x "bar"   -> expr4
    z             -> expr5
    w             -> expr6
    Baz           -> expr7
    Bar x y       -> expr8
    x             -> expr9
  \end{code}
  
  We combine contiguous data constructor alternatives into maps, where the keys
  are the data constructors, and the values are the corresponding expressions
  appended in the order they appear, leading to:
  
  \begin{code}
    [ (Foo, [(Left 42) -> expr1, (Right a) -> expr3])
    , (Bar, [x "bar" -> expr4])
    , (Baz, [ -> expr2])
    ]
  
  z -> expr5
  
  w -> expr6
  
    [ (Bar, [x y -> expr8])
    , (Baz, [ -> expr7])
    ]
  
  x -> expr9
  \end{code}
  
  We rewrite this to:
  
  \begin{code}
  (\v -> (\join# -> case v of
    Foo 1# -> Pa [(Left 42) -> expr1, (Right a) -> expr3]
    Bar    -> Pa [x "bar" -> expr4]
    Baz    -> Pa [ -> expr2]
  ) $ (\join# -> expr5[v/z]
  ) $ (\join# -> expr6[v/z]
  ) $ (\join# -> case  v of
    Foo _ -> join#
    Bar   -> [x y -> expr8]
    Baz   -> Pa [ -> expr7]
  ) $ (V "fail#")
  ) scrutinee
  \end{code}
  
  Then:
  
  \begin{code}
  (\v -> (\join# -> case v of
    Foo 1# -> case 1# of
      Left 2# -> if 2# == 42 then expr1 else join#
      Right 3# -> expr3[3#/a]
    Bar 4# 5# -> if 5# == "bar" then expr 4 else join#
    Baz -> expr2
  ) $ (\join# -> expr5[v/z]
  ) $ (\join# -> expr6[v/z]
  ) $ (\join# -> case v of
    Foo 8# -> join#
    Bar 9# 10# -> expr8[9#/x 10#/y]
    Baz -> expr7
  ) $ (V "fail#")
  ) scrutinee
  \end{code}
  
  We define the built-in primitive `join#` to `fail#`, so that by default, if
  none of the given patterns match, then the program exits.
  
  Our case rewriting algorithm uses lambda abstractions to change the meaning of
  `join#`, so that instead of exiting, we examine the next batch of case
  patterns. For every case expression and let definition, we must restore the
  original meaning of `join#` so failed matches once again cause program exit,
  hence the `joinIsFail` function.
  
  Rather than globally define `join#`, we could have applied `joinIsFail` to
  all definitions, but my hunch is this is slower.
  
  Our last compiler passed an unfortunate milestone: it's over 1000 lines long.
  We use language features we just added to shrink the code.
  
  At the same time, we add support for guards. During parsing, we rewrite guard
  conditions as chains of if-then-else expressions, where the last else branch
  is the join point.
  
  Our previous compiler defined `charEq` and `charLE` which we use in this
  compiler to define the typeclass instance for `Eq Char`. This prepares for
  treating `Int` and `Char` as distinct types in our next compiler.
  
  Doing so will quash a subtle bug. Up until now, a hack treats `Int` and
  `Char` as equal during type checking, but it fails to treat them as equals in
  dictionaries; for example, `Eq Char` differs to `Eq Int`. We could have fixed
  this by treating `Char` as a type synonym for `Int` in the same way `String` is
  a type synonym for `[Char]`, but this breaks FFI typing.
  
  
  [#guardedly.toggleshow]
  ---------
  include::guardedly.hs[]
  ---------
  
  == Assembly ==
  
  We split off and delay address lookup for symbols from bracket abstraction, and
  also delay converting literals to combinators as late as possible.
  
  All this slows our compiler and adds more lines of code, but it disentangles
  various phases of the pipeline.
  
  The refactoring makes it easy to dump the output of bracket abstraction on the
  source code, which is somewhat analogous to a typical compiler printing the
  assembly it generates.
  
  We add support for quasiquoted raw strings; see
  http://hackage.haskell.org/package/raw-strings-qq/docs/Text-RawString-QQ.html[the
  raw-strings-qq package].
  
  [#assembly.toggleshow]
  ---------
  include::assembly.hs[]
  ---------
  
  ++++++++++
  include::toggleshow.js[]
  ++++++++++
  