=== Goal A memory-safe language with a simple translator to x86 that can be feasibly written without itself needing a translator. Memory-safe: it should be impossible to: a) create a pointer out of arbitrary data, or b) to access heap memory after it's been freed. Simple: do all the work in a 2-pass translator: Pass 1: check each instruction's types in isolation. Pass 2: emit code for each instruction in isolation. === Overview of the language A program consists of a series of type, function and global variable declarations. (Also constants and tests, but let's focus on these.) Type declarations basically follow Hindley-Milner with product and (tagged) sum types. Types are written in s-expression form. There's a `ref` type that's a type-safe fat pointer, with an alloc id that gets incremented after each allocation. Memory allocation and reclamation is manual. Dereferencing a ref after its underlying memory is reclaimed (pointer alloc id no longer matches payload alloc id) is guaranteed to immediately kill the program (like a segfault). # product type type foo [ x : int y : (ref int) z : bar ] # sum type choice bar [ x : int y : point ] Functions have a header and a series of instructions in the body: fn f a : int -> b : int [ ... ] Instructions have the following format: io1, io2, ... <- operation i1, i2, ... i1, i2 operands on the right hand side are immutable. io1, io2 are in-out operands. They're written to, and may also be read. User-defined functions will be called with the same syntax. They'll translate to a sequence of push instructions (one per operand, both in and in-out), a call instruction, and a sequence of pop instructions, either to a black hole (in operands) or a location (in-out operands). This follows the standard Unix calling convention. Each operand needs to be something push/pop can accept. Primitive operations depend on the underlying processor. We'd like each primitive operation supported by the language to map to a single instruction in the ISA. Sometimes we have to violate that (see below), but we definitely won't be writing to any temporary locations behind the scenes. The language affords control over registers, and tracking unused registers gets complex, and besides we may have no unused registers at a specific point. Instructions only modify their operands. In most ISAs, instructions operate on at most a word of data at a time. They also tend to not have more than 2-3 operands, and not modify more than 2 locations in memory. Since the number of reads from memory is limited, we break up complex high-level operations using a special type called `address`. Addresses are strictly short-term entities. They can't be stored in a compound type, and they can't be passed into or returned from a user-defined function. They also can't be used after a function call (because it could free the underlying memory) or label (because it gets complex to check control flow, and we want to translate each instruction simply and in isolation). === Compilation to 32-bit x86 Values can be stored: in code (literals) in registers on the stack on the global segment Variables on the stack are stored at *(ESP+n) Global variables are stored at *disp32, where disp32 is statically known Address variables have to be in a reg

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.
Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

d reg2/rm32 literal/imm32 -> reg1/r32 or 68/mul 3/mod reg2/rm32 literal/imm8 -> reg1/r32 ...(21) reg1 <- index stack, literal => 69/mul 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 literal/imm32 -> reg1/r32 ...(22) reg1 <- index global, literal => 69/mul 0/mod 5/rm32/include-disp32 global/disp32 literal/imm32 -> reg1/r32 ...(23) optimization: avoid multiply if literal is a power of 2 use SIB byte if literal is 2, 4 or 8 or left shift G. x : (address T) <- advance o : (array T), idx : (offset T) reg <- advance a/reg, idx/reg => 8d/lea 0/mod 4/rm32/SIB a/base idx/index 0/scale reg/r32 ...(24) reg <- advance stack, literal => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n+literal/disp8 reg/r32 ...(25) reg <- advance stack, reg2 => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP reg2/index 0/scale n/disp8 reg/r32 ...(26) reg <- advance global, literal => 8d/lea 0/mod 5/rm32/include-disp32 global+literal/disp32, reg/r32 ...(27) also instructions for runtime bounds checking === Example Putting it all together: code generation for `a[i].y = 4` where a is an array of 2-d points with x, y coordinates. If a is allocated on the stack, say of type (array point 6) at (ESP+4): offset/EAX : (offset point) <- index i, 8 # (22) tmp/EBX : (address point) <- advance a : (array point 6), offset/EAX # (26) tmp2/ECX : (address number) <- get tmp/EBX : (address point), 4/y # (18) *tmp2/ECX <- copy 4 # (5 for copy/mov with 0 disp8) Many instructions, particularly variants of 'get' and 'advance' -- end up encoding the exact same instructions. But the types differ, and the type-checker checks them differently. === Advanced checks Couple of items require inserting mapping to multiple instructions: bounds checking against array length in 'advance' dereferencing 'ref' types (see type list up top) A. Dereferencing a ref tmp/EDX <- advance *s, tmp0/EDI => compare (ESP+4), *(ESP+8) ; '*' from compiler2 jump-unless-equal panic EDX <- add ESP, 8 EDX <- copy *EDX EDX <- add EDX, 4 EDX <- 8d/lea EDX + result === More speculative ideas Initialize data segment with special extensible syntax for literals. All literals except numbers and strings start with %. %size(type) => compiler replaces with size of type %point(3, 4) => two words and so on. === Credits Forth C Rust Lisp qhasm