# Shed

## Compiler implementation

The compiler has the following major components:

* Tokeniser: converts a string into a sequence of tokens.

* Parser: converts a sequence of tokens into an untyped AST.

* Type checker: convert an untyped AST into a typed AST and associated type
  information.

* Shid code generator: converts a typed AST into a high-level intermediate
  representation known as Shid. This representation is highly specific
  to Shed. This can mostly be thought of as a desugaring step,
  without answering any fundamental implementation questions like memory layout
  or the implementation of effects.

  In principle, this IR should be appropriate for multiple platforms.

* Backend: converts Shid IR into an executable for a given platform.

### Patio backends

In practice, all backends currently have the same structure:

* Patio code generator: converts Shid IR into a lower-level intermediate
  representation known as Patio. This representation is, in principle,
  independent of Shed.

  Patio is appropriate for platforms that treat memory as a bunch of bytes, with
  access to memory through pointers. For instance, this maps well onto LLVM and
  WASM, but likely wouldn't be appropriate for the JVM.

  This assumes the existence of a runtime that is built separately and linked
  into the final executable.

* Platform-specific code generators (LLVM and WASM): convert Patio IR into a
  representation suitable for a particular platform.

* Runtime: provides functionality expected by the Patio code generator, such as
  memory allocation. Implemented in C and compiled to each platform.

## TODO:

Update assignment syntax:

```
var message = "hello, ";
set! message = message! + "world\n";
print!(message);
```

Explicit heap / mutation context?

```
native type MutableArray[!M <: Mutate, T] {
    native fun size(This) -> Int;

    // Precondition: unsafeSet has previously been called with the same index.
    native fun unsafeGet(This, Int) ! M -> T;

    // Precondition: the index is in the range [0, size).
    native fun unsafeSet(This, Int, T) ! M -> Unit;
}
```

Issue: without linear types, no way of knowing whether there are multiple
references to the mutable array, therefore building the array within a list
builder requires either a new, immutable array to be constructed, or for the
builder to mark its internal array as having been built, and therefore a copy
should be created on the next append.