ivy
7 months ago[tools] Add tools/test.py as the project test runner develop
Cassie Jones [Sun, 7 Feb 2021 08:30:08 +0000 (03:30 -0500)]
[tools] Add tools/test.py as the project test runner

7 months ago[Docs] Mention run.py and trace.py in the README
Cassie Jones [Sun, 7 Feb 2021 08:19:48 +0000 (03:19 -0500)]
[Docs] Mention run.py and trace.py in the README

7 months ago[tools] Format code
Cassie Jones [Sun, 7 Feb 2021 08:09:43 +0000 (03:09 -0500)]
[tools] Format code

7 months ago[tools] Move ANSI color printing code into its own file
Cassie Jones [Sun, 7 Feb 2021 08:07:24 +0000 (03:07 -0500)]
[tools] Move ANSI color printing code into its own file

7 months ago[tools] Add tools/lit.py
Cassie Jones [Sun, 7 Feb 2021 07:24:35 +0000 (02:24 -0500)]
[tools] Add tools/lit.py

This tool is inspired by LLVM's lit, but is much less fancy.

7 months ago[Parser] Support code with trailing comments
Cassie Jones [Sun, 7 Feb 2021 07:03:51 +0000 (02:03 -0500)]
[Parser] Support code with trailing comments

The previous implementation using ess::parse_one and then checking that
there was no trailing text would fail if there were trailing comments.
Parsing and then checking that there was only one expression returned
avoids this issue.

7 months ago[tools] Make tools directly executable
Cassie Jones [Sun, 7 Feb 2021 04:59:40 +0000 (23:59 -0500)]
[tools] Make tools directly executable

7 months ago[tools] Add tools/run.py to compile and immediately run scripts
Cassie Jones [Sun, 7 Feb 2021 04:58:02 +0000 (23:58 -0500)]
[tools] Add tools/run.py to compile and immediately run scripts

7 months ago[test] Add a filecheck program
Cassie Jones [Sun, 7 Feb 2021 04:57:04 +0000 (23:57 -0500)]
[test] Add a filecheck program

7 months ago[NFC] Formatting
Cassie Jones [Sun, 7 Feb 2021 03:52:06 +0000 (22:52 -0500)]
[NFC] Formatting

7 months ago[rt] More misc fixes
Cassie Jones [Sat, 6 Feb 2021 04:39:53 +0000 (23:39 -0500)]
[rt] More misc fixes

8 months ago[rt] Misc small cleanups
Cassie Jones [Sun, 3 Jan 2021 07:50:27 +0000 (02:50 -0500)]
[rt] Misc small cleanups

8 months ago[rt] Change is_<type> predicates to tag checks
Cassie Jones [Sat, 2 Jan 2021 23:03:27 +0000 (18:03 -0500)]
[rt] Change is_<type> predicates to tag checks

8 months ago[rt] Change destructor decref to use immutable slices
Cassie Jones [Sat, 2 Jan 2021 22:37:58 +0000 (17:37 -0500)]
[rt] Change destructor decref to use immutable slices

It should be safe since the destructor should have exclusive access to
the object, but this avoids making potentially aliased references.

8 months ago[rt] Split the runtime into multiple modules
Cassie Jones [Sat, 2 Jan 2021 22:12:47 +0000 (17:12 -0500)]
[rt] Split the runtime into multiple modules

8 months ago[rt] Make Obj variant padding explicit
Cassie Jones [Sat, 2 Jan 2021 02:12:48 +0000 (21:12 -0500)]
[rt] Make Obj variant padding explicit

This is motivated by concern about UB from accessing the ObjHeader in
the Obj union. More concretely, modifications to an ObjHeader may modify
the implicit padding in the struct, breaking fields that were inside the
padding on the underlying object. Having mismatched integer types in the
header prefix should be fine since Rust's unions seem to consider this
sort of punning acceptable as long as there are valid values for the
fields.

8 months ago[rt] Improve memory ordering of incref/decref
Cassie Jones [Sat, 2 Jan 2021 01:48:00 +0000 (20:48 -0500)]
[rt] Improve memory ordering of incref/decref

8 months ago[rt] Fix some FFI safety issues
Cassie Jones [Sat, 2 Jan 2021 00:36:57 +0000 (19:36 -0500)]
[rt] Fix some FFI safety issues

Need #[repr(C)] on a union to make it FFI safe, and need extern "C" on
FFI function pointers.

18 months agoAdd more notes to the README
Cassie Jones [Tue, 3 Mar 2020 01:34:31 +0000 (02:34 +0100)]
Add more notes to the README

18 months agoRequire ivy_rt.a to be on the library path
Cassie Jones [Tue, 3 Mar 2020 01:29:48 +0000 (02:29 +0100)]
Require ivy_rt.a to be on the library path

Currently the compiler would only work correctly when run from the
current directory. It's not useful to have it required, so making the
library named something more distinct and requiring it be on the path is
a more scalable option.

18 months agoAdd runtime trace debuggers
Cassie Jones [Mon, 2 Mar 2020 19:04:41 +0000 (20:04 +0100)]
Add runtime trace debuggers

Since the runtime tracing prints out object addresses, it's possible to
track which objects are which and propagate that information through
applications. Since creating lambdas prints the function pointer
address, it's possible to resolve the symbols and print all of the
applications as symbolic.

The trace tool runs the output under lldb since lldb disables ASLR,
which makes resolving function addresses much more straightforward.

For an example, run:

    cargo run --release ivy-examples/fibonacci.vy
    python3 tools/trace.py --debug-only a.out

And it will print out the numbers instead of an opaque debug
representation.

18 months agoRename "program" to "fibonacci"
Cassie Jones [Mon, 2 Mar 2020 19:09:11 +0000 (20:09 +0100)]
Rename "program" to "fibonacci"

18 months agoAdd support for some arithmetic built-ins
Cassie Jones [Mon, 2 Mar 2020 19:02:49 +0000 (20:02 +0100)]
Add support for some arithmetic built-ins

This adds support for addition, subtraction, and comparisons. All of
these built-ins are written as definitions in assembly. Currently the
true and false functions are included unconditionally in compilation,
and have their numbers hard-coded.

18 months agoStop with #![no_std] in the runtime
Cassie Jones [Mon, 2 Mar 2020 18:12:14 +0000 (19:12 +0100)]
Stop with #![no_std] in the runtime

It was cool because it brought the final small binaries down from
roughly 250K to 20K, but it was preventing me from adding features I
wanted like debug tracing and better panic messages.

This also adds conditional runtime tracing, which prints extra messages
if the IVY_RT_TRACE environment variable is set.

18 months agoAdd CFI directives
Cassie Jones [Mon, 2 Mar 2020 15:24:00 +0000 (16:24 +0100)]
Add CFI directives

CFI is the "Call Frame Information", it provides instructions about
where the call frame is. Since we're not emitting a frame pointer, we
need some way to tell debuggers where our call frames our. These CFI
directives let you provide instructions to find the beginning of the
call frame. In our case, we just want to tell it what offsets from the
stack pointer it needs to find it.

These cause the assembler to put all of this metadata in a separate
"eh" frame info section that tools can inspect, it doesn't modify the
actual code.

Adding these makes using the "up" and "down" commands in the debugger
more reliable when looking at my emitted functions. Previously they
would sometimes fail to figure out where they were, making debugging
annoying.

18 months agoAvoid redundant loads in capture generation
Cassie Jones [Mon, 2 Mar 2020 15:07:40 +0000 (16:07 +0100)]
Avoid redundant loads in capture generation

When generating the SSA form for captures, the previous code generated
loads of all the variables that existed. This worked correctly for
some cases, but since it skipped the system in trans_expr that forwards
loads, it would sometimes generate loads to SSA variables that could
just be directly referenced instead, which would end up causing loads
from stack slots that were never written to due to optimizations.

Using trans_expr on the captured variable instead of generating loads
directly lets us reuse that capture logic, and it ends up making the
code simpler :D

18 months agoLoad numbers directly instead of via stack
Cassie Jones [Mon, 2 Mar 2020 00:06:12 +0000 (01:06 +0100)]
Load numbers directly instead of via stack

Assembly output for programs that used number literals was getting hard
to read because it indirected everything through the stack, directly
loading numbers in programs instead makes things behave much better.
This works via the same approach as the previous load forwarding.

18 months agoImplement variable capture
Cassie Jones [Sun, 1 Mar 2020 20:15:16 +0000 (21:15 +0100)]
Implement variable capture

We just copy the variables into the closure environment after it gets
allocated. This involves a decent chunk of stack traffic because we have
to increment their reference counts.

In the process, I figured out that the "ivy_app_mut" optimization for
later functions isn't sound in the presence of nested functions, because
one of the earlier applications can return a shared function which isn't
acceptable to mutate. (There are ways to make it sound if you know for
sure what functions are being called).

18 months agoReduce stack traffic by finding loads through SSA
Cassie Jones [Sun, 1 Mar 2020 16:28:31 +0000 (17:28 +0100)]
Reduce stack traffic by finding loads through SSA

Instead of loading Load instructions directly and then storing them onto
the stack, we perform loads by looking through the SSA and seeing what
instruction generated them. If it was a load, we run that load directly,
otherwise we load from the stack slot that it corresponds to.

18 months agoMake entry point symbols respect mangling
Cassie Jones [Sun, 1 Mar 2020 14:53:18 +0000 (15:53 +0100)]
Make entry point symbols respect mangling

The entry point symbols were hardcoded in strings, now they use the
Label::Extern so they get proper printing. These should be migrated to
use the assembly instruction types, probably.

18 months agoModify runtime symbol decoration
Cassie Jones [Sun, 1 Mar 2020 13:30:22 +0000 (14:30 +0100)]
Modify runtime symbol decoration

C name decoration varies across platforms. On macOS, names from C are
prefixed with an underscore. On Linux, they're not, and on 64-bit
Windows they're not.

The macOS situation observed by inspecting the symbols.
Linux compatibility issue discovered here (and above in the thread):
https://twitter.com/16kbps/status/1233955883148861440
Windows symbol decoration documented here:
https://docs.microsoft.com/en-us/cpp/build/reference/decorated-names#FormatC
> Note that in a 64-bit environment, functions are not decorated.

Currently handling this with conditional compilation, but that prevents
cross-compilation. In the future it would be good to have the formatting
method select how to print them, but that would involve switching away
from fmt::Display, since we can't pass the ABI information into that.
Alternately, we could pack the ABI information into the symbol enum.

18 months agoRemove unused ffi::OsStr import
Cassie Jones [Sun, 1 Mar 2020 12:54:58 +0000 (13:54 +0100)]
Remove unused ffi::OsStr import

18 months agoAdd a compiler CLI
Cassie Jones [Sun, 1 Mar 2020 02:10:11 +0000 (03:10 +0100)]
Add a compiler CLI

The compiler CLI lets you output assembly, the pretty-printed code, or a
compiled binary. It shells out to clang for assembling. You have to have
clang installed, and you have to have the runtime library in the correct
place. I need to figure out a way to embed the runtime library or
something...

18 months agoAdd an extensible framework for adding built-ins
Cassie Jones [Sun, 1 Mar 2020 00:48:44 +0000 (01:48 +0100)]
Add an extensible framework for adding built-ins

Now builtins can be written in assembly at the bottom, and they'll be
included and registered in the entry point on-demand by the program.
Only functions that are referenced will be included in the output.

This will need to be extended to handle functions which reference other
functions (like the handling of "true" and "false" if any of the
comparisons are included), but that's a matter of front-end changes.

18 months agoImplement basic code generation
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.

18 months agoAdd skeleton of x64 compilation code
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.

18 months agoAdd the target-independent trans module
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.

18 months agoAdd a link to the etymology of the language name
Cassie Jones [Fri, 28 Feb 2020 23:27:25 +0000 (00:27 +0100)]
Add a link to the etymology of the language name

It's good to make it so people can understand your memes.

18 months agoAdd runtime library and example assembly
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.

18 months agoRemove assembly experiments
Cassie Jones [Fri, 28 Feb 2020 20:20:23 +0000 (21:20 +0100)]
Remove assembly experiments

They were committed for posterity, but they've served their purpose now.

18 months agoAdd memory layout docs and assembly experiments
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.

18 months agoAdd a pretty-printer for the AST
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.

18 months agoAdd support for globals which don't get captured
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.

18 months agoParse S-expressions into the abstract syntax tree
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.

18 months agoAn s-expression parser and an example program
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?