Cassie Jones [Sat, 29 Feb 2020 18:28:23 +0000 (19:28 +0100)]
Implement basic code generation
This commit makes it possible to compile and assemble sixty-four.vy, and
compute the correct result!!!!!!!
In order to avoid having to do any detailed analysis on variable usage,
this currently accesses everything via the stack. This means allocating
stack space for every instruction, and then saving and loading
everything from the stack frame.
The translation of individual functions is pretty direct. Due to going
via the stack for everything, we can translate each individual
instruction on its own, in order, without looking at other instructions.
This currently doesn't implement copying data into the closures, because
the current test case doesn't do that at all.
This also hard-codes the one builtin (debug) that's referred to by the
test program.
Cassie Jones [Sat, 29 Feb 2020 16:56:45 +0000 (17:56 +0100)]
Add skeleton of x64 compilation code
We compile the globals and functions in the program into a list of
global labels and definitions. Add a bunch of instruction and etc. types
here for formatting. Then, assemble all of this together in the program.
The program realigns the stack (probably overkill?) and then calls into
the entry point symbol, then exits.
I added ivy_exit so that I wouldn't have to refer to any
platform-specific symbols in the assembly that's emitted, all of that
can be handled by the runtime. Unfortunately there will still be
platform specific behavior because of different calling conventions.
Cassie Jones [Sat, 29 Feb 2020 15:21:48 +0000 (16:21 +0100)]
Add the target-independent trans module
This handles translation of the AST to an SSA form. Currently not doing
any control flow constructs inside a function, so functions just have a
single basic block with linear SSA. This does some basic load forwarding
and de-duplication optimizations since they're straightforward.
The most important effect here is translating the globally resolved
names into offsets into the closure record, and listing the variables
that need to be copied into constructed closures.
Cassie Jones [Fri, 28 Feb 2020 20:39:37 +0000 (21:39 +0100)]
Add runtime library and example assembly
This is further exploration into what the code could look time, but this
time there were productive results. This has a few parts:
- The runtime is written as Rust code! It's almost 100% unsafe code
because I didn't want to think about safety boundaries with the
assembly code that's outside the runtime. I can probably end up making
almost all of it safe code with a little bit of work.
- The code mostly works by constructing lambdas with the runtime
function, and then lambda bodies are mostly just applying objects to
each other with the ivy_app function.
This sample program implements doing arithmetic on Church numerals, and
then uses it to run the debug print 64 times.
Cassie Jones [Fri, 28 Feb 2020 20:03:07 +0000 (21:03 +0100)]
Add memory layout docs and assembly experiments
My goal was to figure out how I intended to compile the language by
writing the assembly myself and figuring out the format of all the
objects. I pretty quickly realized that lots of this belongs as runtime
routines rather than sequences the compiler outputs, for things like
creating closures, allocating objects, etc.
What you see here is in a sort of mixed-up state because it started out
by making raw system calls (so allocate and free were more involved),
but is now set up to call into system calls via libSystem.dylib. It
doesn't do anything interesting right now, it was just set up to learn
some things.
Most of the code here is implementing type-checking for the tagged
pointer + 63-bit integer scheme, which is inspired by OCaml. The
specific object layouts are described in docs/object-layout.md.
Cassie Jones [Thu, 27 Feb 2020 18:26:23 +0000 (19:26 +0100)]
Add a pretty-printer for the AST
This uses the pretty-crate for wadler-style pretty-printers. I'm
printing them with a pretty syntax and not with s-expressions, because
it's easier to print pretty than it is to parse pretty.
Cassie Jones [Thu, 27 Feb 2020 17:27:37 +0000 (18:27 +0100)]
Add support for globals which don't get captured
Lots of top-level definitions don't need to be copied into every
closure, because they're constant for the whole program. Global
variables are never inserted into the upvars entry, so they won't be
copied into closures.
This also adds "builtin" names that are inserted into the initial
context for arithmetic and comparisons. Booleans have to be builtin due
to being returned by the comparisons, but they're still intended to be
implemented via church encoding.
Cassie Jones [Thu, 27 Feb 2020 16:58:19 +0000 (17:58 +0100)]
Parse S-expressions into the abstract syntax tree
While doing this, we handle name resolution and "upvar" captures. The
name resolution context "Env" forms a stack that has a reference to the
outer environment at each level. A new level is pushed at each lambda
that's introduced. The environment includes a list of "upvars" that have
to be copied into the closure, which is updated every time a variable
lookup finds the variable in an outer environment instead of the local
environment. This process has to use a RefCell because you can't make
the lifetimes work out with a chain of mutable references.
The parsing aside from that environment stack is relatively
straightforward parsing.
Cassie Jones [Thu, 27 Feb 2020 13:19:40 +0000 (14:19 +0100)]
An s-expression parser and an example program
This is intended to be a slightly fancier lambda calculus with
arithmetic support. The way I've written the example here suggests not
making conditionals a builtin, and instead just using church encodings.
This will probably be bad for displaying data purposes? I'm not sure how
I want to handle I/O. Maybe do an ML and put impure I/O in here?