</s>Add standard library

We want to be able to call a function inside our for loop that has some
sort of side effect that we can observe: How about printing to stdout?
Our language isn't quite sophisticated enough yet to handle writing to
files and handles or make system calls, but we can work around this by
writing this code in another language and calling it from Kaleidoscope.

In this chapter we are going to write our standard library in C, but
feel free to experiment with compiling and linking other languages: Try
making raw system calls in assembly, or even writing it in Haskell!

The standard library contains one function, putchard, which takes in a
double and prints a character to stdout. It's the equivalent of
putchar(3), but since Kaleidoscope only works with doubles we need to
cast it first.

Once you have finished this chapter, you should now be able to run the
following code to print out a bunch of characters:

ready> extern putchard(x)

declare external ccc  double @putchard(double)

ready> for i = 0, i < 10 in putchard(42+i)

define external ccc  double @__anon_expr()    {

preheader_0:

  %initcond_0 = fcmp olt double 0.000000e0, 1.000000e1

  %initcond_1 = uitofp i1 %initcond_0 to double

  %initcond_2 = fcmp one double 0.000000e0, %initcond_1

  br i1 %initcond_2, label %loop_0, label %after_0

loop_0:

  %i_0 = phi double [0.000000e0, %preheader_0], [%nextvar_0, %loop_0]

  %body_0 = fadd double 4.200000e1, %i_0

  %body_1 =  call ccc  double  @putchard(double  %body_0)

  %nextvar_0 = fadd double %i_0, 1.000000e0

  %cond_0 = fcmp olt double %i_0, 1.000000e1

  %cond_1 = uitofp i1 %cond_0 to double

  %cond_2 = fcmp one double 0.000000e0, %cond_1

  br i1 %cond_2, label %loop_0, label %after_0

after_0:

  ret double 0.000000e0

}

Resolving MangledSymbol "_putchard" to 0x10574c2d0

*+,-./01234

Add rules for statically linking the standard library in

If statically linking in the Makefile, we need to make sure that our
putchard symbol/function doesn't get stripped out, as GHC passes the
-dead_strip flag to the linker to remove any unused functions. Since
nothing directly calls putchard in our program, it will get stripped out
unless we specify that we want to export it. We can use an export list
to indicate that we still want the symbol. (On Linux, you might need to
remove the underscore from _putchard. )

Resolve symbols

Now that the standard library is loaded into our process, we can finally
being to fill out our symbol resolver. The symbol resolver takes in a
symbol, and returns a pointer wrapped inside a JITSymbol if it can find
the address of it. Otherwise it returns an error.

You can use the symbol resolver to do much fancier stuff in OrcJIT, but
for now we are just going to look up symbols that we have previously
loaded into our process via loadLibraryPermanently.

Load the standard library

This is equivalent to dlopen(3), where it will load all the code and
symbols from our standard library into our process. We need to do this
so that later on we can call standard library functions whilst JITing.

If you went down the statically linked route, you still need to call
this with Nothing to expose the symbols to LLVM.

Add Makefile for building stdlib

There are two ways we can go about including our standard library in our
language.
The first method is via statically linking it into our final executable,
by compiling our Haskell code and standard library object file with it.
The second method is to compile the standard library into a shared
library and dynamically load it at runtime.

Here we are going to do the latter, since it means we can still run our
code with runghc, at the cost of needing to locate the path to the
library inside Main.hs. (I'll include an example later on of how to
include it the static way)

macOS produces dylibs - Linux typically uses .so files. You may want to
rename the rule to align with whatever operating system you are
targeting.

<s>Start the standard library

Our standard library so far is just going to contain a single function
that acts as a version of putchar(3), except it operates on doubles.
We'll also flush stdout so that we can immediately see what we've
printed when we're inside the repl.

</s>Add control flow

So far our language can parse and evaluate floating point expressions.
However each expression and it's subexpressions always gets evaluated. To
do more complex computations, we want to be able to control what gets
evaluated and what doesn't.

This is known as control flow, and the two most famous imperative
constructs are probably the if statement and for loop. We will add them
to our language in this chapter, and finally put our boolean expressions
(42 < i) to good use.

Generate code for for loops

Our for loops are like C style for loops, with an initial value,
condition and step.

We begin generating code by setting up the loop in the preheader. Here
we generate the initial value and compare it to the condition, finishing
early if we need to.

The main loop begins with choosing either the initial value, or the
incremented value for the loop variable (usually called the induction
variable). We can then put this inside the binding environment whenever
we generate the body expression with the `runReaderT` function: This
lets the body access the induction variable with the associated name,
without having to change our Reader transformer into a State
transformer.

Once we've generated the body, we just need to increment the induction
variable by the step, and check if the condition is met. Then depending
on the result of that we either branch back up to the top of the loop,
or to the after block to exit.

You might have noticed that we don't have any side-effects at the
moment, so you can't tell what went on inside a loop - it always
evaluates to zero. We're going to add something to do inside these loops
next.

Parse for loops

Watch out for the <++: this tries to parse whatever is on the left first,
and then only if it fails tries whatever is on the right. This is
different from <|>, which will include both in all the possible
final parsings.

Generate code for if statements

Hopefully you found this addition straightforward and enjoyable, now
that we have all the infrastructure in place. Let's walk through this
step by step.

We first start off our loop by creating a basic block called "if". A
basic block is a chunk of code that has a single entry and exit point,
and in this block we're putting in the condition expression.
Since everything in Kaleidoscope is a double (yuck), we need to compare
it to zero to get a boolean that we can actually branch with.

After branching we create two other basic blocks labelled "then" and
"else", containing the then and else expressions of the branch
respectively. They both branch back to the final basic block, "ifcont".

Now since LLVM IR is in SSA (single static assignment) form, the then
and else branches both write to separate variables: We can't write to
the same variable twice. In order to actually differentiate between the
then expression and the else expression, we use a phi node in the merge
block. Depending on what basic block it arrived from, it will use either
one of two operands that we've passed to it.

In this case, we use it to return the then expression if the then branch
was taken, or the else expression if the else branch was taken. Phi
nodes are very common in LLVM IR, and open up lots of optimisations by
allowing us to stay in SSA form.

You might have also noticed that unlike the C++ tutorial, we didn't need
to rewind our builder back and generate the "mergeB" block first. In
fact, we actually end up referencing mergeB before it is even declared!
How can this be possible? Through recursive do! The MonadFix instance on
IRBuilder allow us to exploit laziness and use mdo to refer to variables
that haven't yet been evaluated.

Tidy up the parsing a bit

The Text.ParserCombinators.ReadPrec/Text.ParserCominators.ReadP split
adds a bit of lifting cruft, so lets try to sweep that away.

<s>Parse if expressions

Back to the AST.

</s>Add JIT

We have LLVM IR now, but our computers still can't run it. We could
compile our code "offline" and write it to a file, but LLVM also
provides frameworks for JITing: Just-in-time compilation. This is where
the code is compiled just before it is run, and we will be using it make
an interactive REPL.

Note that JITs are not the same as interpreters: An interpreter reads
the program and directly computes the result. A JIT reads the program
and generates more code for the computer to run, which then computes the
result.

The current LLVM Kaleidoscope tutorial uses the old MC JIT framework:
This tutorial will be using the fancy new OrcJIT framework. It's a bit
more complicated but provides a lot more flexibility.

Find our JIT'ed function and run it

Here is where the magic happens. We first mangle the symbol before
passing it to findSymbolIn: The compilation then happens here. It will
spit back a FFI pointer, which we then need to invoke ourselves.

In order to do this we have to specify the Haskell type of the function
that we're pointing to, which resides in C-land, hence the ccall
attribute in our foreign declaration.

Try it out!

Detect and remove __anon_exprs in repl

You might have noticed that when entering in top-level expressions you
end up getting duplicate __anon_expr.1, __anon_expr.2s etc. Since we
don't want these anonymous functions to stick around, in this commit
we're detecting them and then removing them once we're done.

We also only want to run the JIT whenever the user has entered a
top-level expression, so we've also sketched that out.

<s>Set up the LLVM context and optimise the module

Now that we have some LLVM IR generated, we can run PassManager on our
module to get a bunch of neat optimisations on it. Try it out with 3 + 2
to see some constant folding.
Note that the original tutorial uses FunctionPassManager which optimises
on a function per function basis: llvm-hs doesn't expose this yet (and
this is all using the legacy pass manager anyway), so for now we just
optimise the entire module at the end.

</s>Add LLVM IR codegen

Now that we have our AST built up, its time to start thinking about
semantics. And to think about semantics, we need to start building up
code that does what our AST says.

In most compilers, we don't directly convert the AST right down to
machine code: Usually there's an intermediate representation involved
that's somewhere between our programming language and machine code. LLVM
has an intermediate representation called LLVM IR, and that's what we'll
be converting our AST to.

llvm-hs provides a monadic way of building up modules and functions,
with ModuleBuilder and IRBuilder respectively. To generate our code we
will traverse our AST inside these monads, spitting out LLVM IR as we go
along.

Generate code for call expressions

In order to call a function in LLVM IR, we need to grab a
GlobalReference to it. Currently we just make it ourselves, inferring
the type of it based on what arguments the caller provided and the fact
that all functions return a double.

Handle EOFs in the repl

This way whenever ^D is typed at the repl, the program gracefully
terminates and prints out the complete module.

Generate code for externs

Generate code for functions and variables

Now that we're generating functions, variables can now be bound. This
means we will have to somehow keep track of what variables are available
in scope (i.e. passed to us in 'funciton'), so we've wrapped our
IRBuilderT in a ReaderT (Map String Operand).

For now if the variable doesn't exist in scope, we just crash the
program. But later on we will introduce a mechanism for errors, and tidy
up the transformer stack.

Generate code for binary operations

Also throw in the rest of the comparisons whilst we're at it.

<s>Begin codegen

Now the fun begins.
You should start by installing the llvm-hs packages. This tutorial will
be keeping things "vanilla" by just installing the packages globally
rather than using a .cabal file.

$ cabal new-install --lib llvm-hs llvm-hs-pure llvm-hs-pretty --write-ghc-environment-files=always

The above command should be enough to install them, assuming you already
have LLVM installed correctly. (At the time of writing llvm-hs-pretty
needs to be installed from source for llvm-8.0:
https://github.com/llvm-hs/llvm-hs-pretty)

Like our parsing, our code generation is also monadic (this is a Haskell
tutorial). There are two monads that we can use: IRBuilder and
ModuleBuilder. The former is for LLVM IR instructions and the latter for
function definitions, constants and the like.

The original tutorial puts everything into one module, so we are going
to follow suit here. This makes things a bit hairy since now the repl
needs to take place inside of a ModuleBuilderT IO. In an effort to keep
our code as pure as possible, we've added a hoist function so that we
can keep our codegen code inside ModuleBuilder.

There's also a helper function to grab the most recent definition so
that we can print out similar to in the tutorial. This and hoist have
been tucked away into Util.hs.

So far we only generate code for numbers: But this now paves the way for
the rest of the code generation.

</s>Add AST and parsing

The first step in our compiler is to convert the source code into some
sort of data structure that we can work with. This data structure
usually ends up being a tree structure: nodes of expressions built up of
other expressions. For example, (1 + (3 - 2)) would be a tree where 1, 3
and 2 are leaf nodes and +/- are parent nodes.

It represents the syntax of the program, but is abstract as it doesn't
contain the details about it like whitespace or parenthesis: an abstract
syntax tree, if you will.

In the original LLVM Kaleidoscope tutorial, this abstract syntax tree
(AST) is usually built by first lexing the program into separate tokens
like identifiers and keywords, and then parsing it to build up the tree
structure. We're not going to do that in this tutorial, and instead opt
for the Haskell-ier way with parser combinators.

Parser combinators allow us to lex and parse at the same time by simply
specifying what we expect to parse. We'll be using the ReadP monad,
which is also used for the Read class: In fact we'll just be able to
parse our program by calling 'read'! The P in ReadP stands for
precedence, and you'll see later on we'll be able to add some tricks to
prefer certain patterns over others when parsing. We'll also be writing
all our parsing with do notation, which I think you'll agree feels very
natural to use.

Add basic repl

For the moment this doesn't have any parsing errors other than "Couldn't
parse". We'll go back to this later!
Also note we're printing to stderr.

Parse call expressions

The Call constructor stores the name of the callee and the list of
arguments being passed to it.

Parse parentheses

Yes, it's that easy. Try out the difference between
1 * 2 + 3
and
1 * (2 + 3)

Parse defs and externs

They both share a common prototype so we can split that out into a
separate definition. We also want to be able to parse top level
expressions, so we add constructor for that in AST.
Hopefully now you can see the beauty of monadic parsing:
Function <$> readPrec <*> readPrec

Parse variables in expressions

Parse more binary ops

We can parameterise the precedence that we parse so that * is parsed
before +/- etc.
Try it out with `ghci AST.hs`, and see the difference between
*AST> read "1 * 2 - 3"
and
*AST> read "1 + 2 - 3"

<s>Start parsing expressions

This starts off with defining not the AST, but just what expressions we
want to be able to parse.
So far we just handle numbers, and addition involving 2 numbers.
We use the built-in ReadPrec parser combinators, which allow us to
recursively parse the binary op of addition, and even allow us to reuse
the Read instance on Int!
prec and step are needed since without them, parseAdd will just get
stuck repeatedly trying to parse the left expression (a).

Initial commit