diff options
Diffstat (limited to 'archive/3.transect')
| -rw-r--r-- | archive/3.transect/Readme | 6 | ||||
| -rwxr-xr-x | archive/3.transect/build | 109 | ||||
| -rwxr-xr-x | archive/3.transect/build_and_test_until | 18 | ||||
| -rwxr-xr-x | archive/3.transect/clean | 8 | ||||
| -rw-r--r-- | archive/3.transect/compiler10 | 304 | ||||
| -rw-r--r-- | archive/3.transect/compiler2 | 27 | ||||
| -rw-r--r-- | archive/3.transect/compiler3 | 73 | ||||
| -rw-r--r-- | archive/3.transect/compiler4 | 84 | ||||
| -rw-r--r-- | archive/3.transect/compiler5 | 32 | ||||
| -rw-r--r-- | archive/3.transect/compiler6 | 36 | ||||
| -rw-r--r-- | archive/3.transect/compiler7 | 46 | ||||
| -rw-r--r-- | archive/3.transect/compiler8 | 53 | ||||
| -rw-r--r-- | archive/3.transect/compiler9 | 254 | ||||
| -rw-r--r-- | archive/3.transect/ex3.k2 | 22 | ||||
| -rw-r--r-- | archive/3.transect/ex4.k2 | 34 | ||||
| -rw-r--r-- | archive/3.transect/ex5.k2 | 30 | ||||
| -rw-r--r-- | archive/3.transect/ex6.k2 | 23 | ||||
| -rw-r--r-- | archive/3.transect/ex7.k2 | 64 | ||||
| -rw-r--r-- | archive/3.transect/ex8.k2 | 36 | ||||
| -rw-r--r-- | archive/3.transect/factorial.k2 | 16 | ||||
| -rw-r--r-- | archive/3.transect/vimrc.vim | 36 |
21 files changed, 1311 insertions, 0 deletions
diff --git a/archive/3.transect/Readme b/archive/3.transect/Readme new file mode 100644 index 00000000..821ccde0 --- /dev/null +++ b/archive/3.transect/Readme @@ -0,0 +1,6 @@ +Abortive series of attempts at building a bootstrappable low-level language. +Type-checked, but feasible to implement in some sort of notation for machine +code (like SubX). + +The latest version is in compiler10. But it doesn't account for checking +how programs allocate registers. diff --git a/archive/3.transect/build b/archive/3.transect/build new file mode 100755 index 00000000..150c6b4d --- /dev/null +++ b/archive/3.transect/build @@ -0,0 +1,109 @@ +#!/bin/sh +# returns 0 on successful build or nothing to build +# non-zero exit status only on error during building +set -e # stop immediately on error + +# [0-9]*.cc -> transect.cc -> transect_bin +# (layers) | | +# tangle $CXX + +# can also be called with a layer to only build until +# $ ./build --until 050 +UNTIL_LAYER=${2:-zzz} + +# there's two mechanisms for fast builds here: +# - if a command is quick to run, always run it but update the result only on any change +# - otherwise run it only if the output is 'older_than' the inputs +# +# avoid combining both mechanisms for a single file +# otherwise you'll see spurious messages about files being updated +# risk: a file may unnecessarily update without changes, causing unnecessary work downstream + +test "$CXX" || export CXX=c++ +test "$CC" || export CC=cc +test "$CFLAGS" || export CFLAGS="-g -O3" +export CFLAGS="$CFLAGS -Wall -Wextra -ftrapv -fno-strict-aliasing" + +# return 1 if $1 is older than _any_ of the remaining args +older_than() { + local target=$1 + shift + if [ ! -e $target ] + then +#? echo "$target doesn't exist" + echo "updating $target" >&2 + return 0 # success + fi + local f + for f in $* + do + if [ $f -nt $target ] + then + echo "updating $target" >&2 + return 0 # success + fi + done + return 1 # failure +} + +# redirect to $1, unless it's already identical +update() { + if [ ! -e $1 ] + then + cat > $1 + else + cat > $1.tmp + diff -q $1 $1.tmp >/dev/null && rm $1.tmp || mv $1.tmp $1 + fi +} + +update_cp() { + if [ ! -e $2/$1 ] + then + cp $1 $2 + elif [ $1 -nt $2/$1 ] + then + cp $1 $2 + fi +} + +noisy_cd() { + cd $1 + echo "-- `pwd`" >&2 +} + +older_than ../enumerate/enumerate ../enumerate/enumerate.cc && { + $CXX $CFLAGS ../enumerate/enumerate.cc -o ../enumerate/enumerate +} + +older_than ../tangle/tangle ../tangle/*.cc && { + noisy_cd ../tangle + { + grep -h "^struct .* {" [0-9]*.cc |sed 's/\(struct *[^ ]*\).*/\1;/' + grep -h "^typedef " [0-9]*.cc + } |update type_list + grep -h "^[^ #].*) {" [0-9]*.cc |sed 's/ {.*/;/' |update function_list + ls [0-9]*.cc |grep -v "\.test\.cc$" |sed 's/.*/#include "&"/' |update file_list + ls [0-9]*.test.cc |sed 's/.*/#include "&"/' |update test_file_list + grep -h "^[[:space:]]*void test_" [0-9]*.cc |sed 's/^\s*void \(.*\)() {$/\1,/' |update test_list + grep -h "^\s*void test_" [0-9]*.cc |sed 's/^\s*void \(.*\)() {.*/"\1",/' |update test_name_list + $CXX $CFLAGS boot.cc -o tangle + ./tangle test + noisy_cd ../transect # no effect; just to show us returning to the parent directory +} + +LAYERS=$(../enumerate/enumerate --until $UNTIL_LAYER |grep '.cc$') +older_than transect.cc $LAYERS ../enumerate/enumerate ../tangle/tangle && { + # no update here; rely on 'update' calls downstream + ../tangle/tangle $LAYERS > transect.cc +} + +grep -h "^[^[:space:]#].*) {$" transect.cc |grep -v ":.*(" |sed 's/ {.*/;/' |update function_list +grep -h "^\s*void test_" transect.cc |sed 's/^\s*void \(.*\)() {.*/\1,/' |update test_list +grep -h "^\s*void test_" transect.cc |sed 's/^\s*void \(.*\)() {.*/"\1",/' |update test_name_list + +older_than transect_bin transect.cc *_list && { + $CXX $CFLAGS transect.cc -o transect_bin +} + +exit 0 diff --git a/archive/3.transect/build_and_test_until b/archive/3.transect/build_and_test_until new file mode 100755 index 00000000..385558be --- /dev/null +++ b/archive/3.transect/build_and_test_until @@ -0,0 +1,18 @@ +#!/bin/sh +# Run tests for just a subset of layers. +# +# Usage: +# build_and_test_until [file prefix] [test name] +# Provide the second arg to run just a single test. +set -e + +# clean previous builds if they were building until a different layer +touch .until +PREV_UNTIL=`cat .until` +if [ "$PREV_UNTIL" != $1 ] +then + ./clean top-level + echo $1 > .until +fi + +./build --until $1 && ./transect_bin test $2 diff --git a/archive/3.transect/clean b/archive/3.transect/clean new file mode 100755 index 00000000..2c49d7d7 --- /dev/null +++ b/archive/3.transect/clean @@ -0,0 +1,8 @@ +#!/bin/sh +set -e + +set -v +rm -rf transect.cc transect_bin* *_list +test $# -gt 0 && exit 0 # convenience: 'clean top-level' to leave subsidiary tools alone +rm -rf ../enumerate/enumerate ../tangle/tangle ../tangle/*_list ../*/*.dSYM +rm -rf .until diff --git a/archive/3.transect/compiler10 b/archive/3.transect/compiler10 new file mode 100644 index 00000000..ce0e487a --- /dev/null +++ b/archive/3.transect/compiler10 @@ -0,0 +1,304 @@ +=== Goal + +A memory-safe language with a simple translator to x86 that can be feasibly written without itself needing a translator/compiler. + +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 statement's types in isolation. + Pass 2: emit code for each statement in isolation. + +=== Language summary + +Program organization is going to be fairly conventional and in the spirit of C: programs will consist of a series of type, global and function declarations. More details below. Functions will consist of a list of statements, each containing a single operation. Since we try to map directly to x86 instructions, combinations of operations and operands will not be orthogonal. You won't be able to operate at once on two memory locations, for example, since no single x86 instruction can do that. + +Statement operands will be tagged with where they lie. This mostly follows C: local variables are on the stack, and variables not on the stack are in the global segment. The one addition is that you can lay out (only word-size) variables on registers. This is kinda like C's `register` keyword, but not quite: if you don't place a variable on a register, you are *guaranteed* it won't be allocated a register. Programmers do register allocation in this language. + +The other memorable feature of the language is two kinds of pointers: a 'ref' is a fat pointer manually allocated on the heap, and an 'address' is a far more ephemeral thing described below. + +--- Ref + +Refs are used to manage heap allocations. They are fat pointers that augment the address of a payload with an allocation id. On x86 a ref requires 8 bytes: 4 for the address, and 4 for the alloc id. Refs can only ever point to the start of a heap allocation. Never within a heap allocation, and *certainly* never to the stack or global segment. + +How alloc ids work: Every heap allocation allocates an additional word of space for an alloc id in the payload, and stores a unique alloc id in the payload as well as the pointer returned to the caller. Reclaiming an allocation resets the payload's alloc id. As long as alloc ids are always unique, and as long as refs can never point to within a heap allocation, we can be guaranteed that a stale pointer whose payload has been reclaimed will end up with a mismatch between pointer alloc id and payload alloc id. + + x <- alloc # x's alloc id and *x's alloc id will be the same, say A + y <- copy x # y also has alloc id A + free x # x's alloc id is now 0, as is *x's alloc id + ..*y.. # y's alloc id is A, but *y's alloc id is 0, so we can signal an error + z <- alloc # say z reuses the same address, but now with a new alloc id A' + ..*y.. # y's alloc id is A, but *y's alloc id is A', so we can signal an error + +--- Address + +Since our statements are really simple, many operations may take multiple statements. To stitch a more complex computation like `A[i].f = 34` across multiple statements, we need addresses. + +Addresses can be used to manage any memory address. They can point inside objects, on the stack, heap or global segment. Since they are so powerful we greatly restrict their use. Addresses can only be stored in a register, never in memory on the stack or global segment. Since user-defined types will usually not fit on a register, we forbid addresses in any user-defined types. Since an address may point inside a heap allocation that can be freed, and since `free` will be a function call, addresses will not persist across function calls. Analyzing control flow to find intervening function calls can be complex, so addresses will not persist across basic block boundaries. + +The key open question with this language: can we find *clear* rules of address use that *don't complicate* programs, and that keep the type system *sound*? + +=== Language syntax + +The type system basically follows Hindley-Milner with product and (tagged) sum types. In addition we have address and ref types. Type declarations have the following syntax: + + # 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 statements in the body: + + fn f a : int b : int -> b : int [ + ... + ] + +Statements 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. + +Two example programs: + + i) Factorial: + + fn factorial n : int -> result/EAX : int [ + result/EAX <- copy 1 + { + compare n, 1 + break-if <= + var tmp/EBX : int + tmp/EBX <- copy n + tmp/EBX <- subtract 1 + var tmp2/EAX : int + tmp2/EAX <- call factorial, tmp/EBX + result/EAX <- multiply tmp2/EAX, n + } + return result/EAX + ] + + ii) Writing to a global variable: + + var x : char + + fn main [ + call read, 0/stdin, x, 1/size + result/EAX <- call write, 1/stdout, x, 1/size + call exit, result/EAX + ] + +One thing to note: variables refer to addresses (not to be confused with the `address` type) just like in Assembly. We'll uniformly use '*' to indicate getting at the value in an address. This will also provide a consistent hint of the addressing mode. + +=== Compilation strategy + +--- User-defined statements + +User-defined functions will be called with the same syntax as primitives. 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: + + push EBP + copy ESP to EBP + push arg 1 + push arg 2 + ... + call + pop arg n + ... + pop arg 1 + copy EBP to ESP + pop ESP + +Implication: each function argument needs to be something push/pop can accept. It can't be an address, so arrays and structs will either have to be passed by value, necessitating copies, or allocated on the heap. We may end up allocating members of structs in separate heap allocations just so we can pass them piecemeal to helper functions. (Mu has explored this trade-off in the past.) + +--- Primitive statements + +Operands may be: + in code (literals) + in registers + on the stack + on the global segment + +Operands are always scalar. Variables on the stack or global segment are immutable references. + + - Variables on the stack are stored at addresses like *(EBP+n) + - Global variables are stored at addresses like *disp32, where disp32 is a statically known constant + + #define local(n) 1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n/disp8 + #define disp32(N) 0/mod 5/rm32/include-disp32 N/disp32 + +Since the language will not be orthogonal, compilation proceeds by pattern matching over a statement along with knowledge about the types of its operands, as well as where they're stored (register/stack/global). We now enumerate mappings for various categories of statements, based on the type and location of their operands. + +Many statements will end up encoding to the exact same x86 instructions. But the types differ, and they get type-checked differently along the way. + +A. x : int <- add y + + Requires y to be scalar (32 bits). Result will always be an int. No pointer arithmetic. + + reg <- add literal => 81 0/subop 3/mod ...(0) + reg <- add reg => 01 3/mod ...(1) + reg <- add stack => 03 1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n/disp8 reg/r32 ...(2) + reg <- add global => 03 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(3) + stack <- add literal => 81 0/subop 1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n/disp8 literal/imm32 ...(4) + stack <- add reg => 01 1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n/disp8 reg/r32 ...(5) + stack <- add stack => disallowed + stack <- add global => disallowed + global <- add literal => 81 0/subop 0/mod 5/rm32/include-disp32 global/disp32 literal/imm32 ...(6) + global <- add reg => 01 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(7) + global <- add stack => disallowed + global <- add global => disallowed + +Similarly for sub, and, or, xor and even copy. Replace the opcodes above with corresponding ones from this table: + + add sub and or xor copy/mov + reg <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 + reg <- op reg 01 or 03 29 or 2b 21 or 23 09 or 0b 31 or 33 89 or 8b + reg <- op stack 03 2b 23 0b 33 8b + reg <- op global 03 2b 23 0b 33 8b + stack <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 + stack <- op reg 01 29 21 09 31 89 + global <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 + global <- op reg 01 29 21 09 31 89 + +B. x/reg : int <- mul y + + Requires y to be scalar. + x must be in a register. Multiplies can't write to memory. + + reg <- mul literal => 69 ...(8) + reg <- mul reg => 0f af 3/mod ...(9) + reg <- mul stack => 0f af 1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n/disp8 reg/r32 ...(10) + reg <- mul global => 0f af 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(11) + +C. x/EAX/quotient : int, y/EDX/remainder : int <- idiv z # divide EAX by z; store results in EAX and EDX + + Requires source x and z to both be scalar. + x must be in EAX and y must be in EDX. Divides can't write anywhere else. + + First clear EDX (we don't support ints larger than 32 bits): + 31/xor 3/mod 2/rm32/EDX 2/r32/EDX + + then: + EAX, EDX <- idiv literal => disallowed + EAX, EDX <- idiv reg => f7 7/subop 3/mod ...(12) + EAX, EDX <- idiv stack => f7 7/subop 1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n/disp8 ...(13) + EAX, EDX <- idiv global => f7 7/subop 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(14) + +D. x : int <- not (weird syntax, but we'll ignore that) + + Requires x to be an int. + + reg <- not => f7 3/mod ...(15) + stack <- not => f7 1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n/disp8 ...(16) + global <- not => f7 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(17) + +E. x : (address t) <- get o : T, %f + + (Assumes T.f has type t.) + + o can't be on a register since it's a non-primitive (likely larger than a word) + f is a literal + x must be in a register (by definition for an address) + + reg1 <- get reg2, literal => 8d/lea 1/mod reg2/rm32 literal/disp8 reg1/r32 ...(18) + reg <- get stack, literal => 8d/lea 1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n+literal/disp8 reg/r32 ...(19) + (simplifying assumption: stack frames can't be larger than 256 bytes) + reg <- get global, literal => 8d/lea 0/mod 5/rm32/include-disp32 global+literal/disp32, reg/r32 ...(20) + +F. x : (offset T) <- index i : int, %size(T) + + This statement is used to translate an array index (denominated in the type of array elements) into an offset (denominated in bytes). It's just a multiply but with a new type for the result so that we can keep the type system sound. + + Since index statements translate to multiplies, 'x' must be a register. + The %size(T) argument is statically known, so will always be a literal. + + reg1 <- index reg2, literal => 69/mul 3/mod 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 5/base/EBP 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) + +G. x : (address T) <- advance a : (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 5/base/EBP 4/index/none 0/scale n+literal/disp8 reg/r32 ...(25) + reg <- advance stack, reg2 => 8d/lea 1/mod 4/rm32/SIB 5/base/EBP 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) + +=== 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): + + 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) + +=== More complex statements + +A couple of statement types expand to multiple instructions: + Function calls. We've already seen these above. + Bounds checking against array length in 'advance' + Dereferencing 'ref' types (see type list up top). Requires an alloc id check. + +G'. Bounds checking the 'advance' statement begins with a few extra instructions. For example: + + x/EAX : (address T) <- advance a : (array T), literal + +Suppose array 'a' lies on the stack starting at EBP+4. Its length will be at EBP+4, and the actual contents of the array will start from EBP+8. + + compare *(EBP+4), literal + jump-if-greater panic # rudimentary error handling + +Now we're ready to perform the actual 'lea': + + lea EBP+8 + literal, reg # line 25 above + +H. Dereferencing a 'ref' needs to be its own statement, yielding an address. This statement has two valid forms: + + reg : (address T) <- deref stack : (ref T) + reg : (address T) <- deref global : (ref T) + +Since refs need 8 bytes they can't be in a register. And of course the output is an address so it must be in a register. + +Compiling 'deref' will take a few instructions. Consider the following example where 's' is on the stack, say starting at EBP+4: + + EDX : (address T) <- deref s : (ref T) + +The alloc id of 's' is at *(EBP+4) and the actual address is at *(EBP+8). The above statement will compile down to the following: + + EDX/s <- copy *(EBP+8) # the address stored in s + EDX/alloc-id <- copy *EDX # alloc id of payload *s + compare EDX, *(EBP+4) # compare with alloc id of pointer + jump-unless-equal panic # rudimentary error handling + # compute *(EBP+8) + 4 + EDX <- copy *(EBP+8) # recompute the address in s because we can't save the value anywhere) + EDX <- add EDX, 4 # skip alloc id this time + +Subtleties: + a) if the alloc id of the payload is 0, then the payload is reclaimed + b) looking up the payload's alloc id *could* cause a segfault. What to do? + +=== More speculative ideas + +Initialize data segment with special extensible syntax for literals. All literals except numbers and strings start with %. Global variable declarations would now look like: + + var s : (array character) = "abc" # exception to the '%' convention + var p : point = %point(3, 4) + +=== Credits + +Forth +C +Rust +Lisp +qhasm diff --git a/archive/3.transect/compiler2 b/archive/3.transect/compiler2 new file mode 100644 index 00000000..5c06cc4f --- /dev/null +++ b/archive/3.transect/compiler2 @@ -0,0 +1,27 @@ +to dereference a heap allocation + copy handle to stack + perform lookup to stack + +lookup x in *(ESP+4) of type (handle T) + + reg <- copy *(ESP+5) : (address T stack) + payload alloc id <- copy *reg + address alloc id <- copy *(ESP+4) + compare payload alloc id, address alloc id + jump if not equal to print stack trace and panic + address <- add reg, 1 + +types: + + address T reg + address T stack + address T heap + address T global + +copy down this spectrum is not permitted, but up is. + +addresses aren't allowed in types, globals and on the heap. Only handles. +addresses are only for temporary manipulations. + + +*(address T) <- copy T diff --git a/archive/3.transect/compiler3 b/archive/3.transect/compiler3 new file mode 100644 index 00000000..6bc6bf85 --- /dev/null +++ b/archive/3.transect/compiler3 @@ -0,0 +1,73 @@ +== Goal + +A memory-safe language with a simple translator to x86 that can be feasibly written in x86. + +== Definitions of terms + +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. + +== Implications + +=> Each instruction matches a pattern and yields a template to emit. +=> There's a 1-to-1 mapping between instructions in the source language and x86 machine code. + Zero runtime. +=> Programmers have to decide how to use registers. +=> Translator can't insert any instructions that write to registers. (We don't know if a register is in use.) + +== Lessons from Mu + +1. For easy bounds checking, never advance pointers to arrays or heap allocations. No pointer arithmetic. +2. Store the array length with the array. +3. Store an allocation id with heap allocations. Allocation id goes monotonically up, never gets reused. When it wraps around to zero the program panics. +4. Heap pointers also carry around allocation id. +5. When dereferencing a heap pointer, first ensure its alloc id matches the alloc id of the payload. This ensures some other copy of the pointer didn't get freed (and potentially reused) + +== Problem 1 + +How to index into an array? + + The array has a length that needs to be checked. + Its elements have a type T. + The base will be in memory, either on the stack or the heap. + The index may be in the register, stack or heap. + +That's too much work to do in a single instruction. + +So arrays have to take multiple steps. And we have to guard against the steps +being misused in unsafe ways. + +To index into an array with elements of type T, starting with the size of the +array in bytes: + + step 1: get the offset the index is at + <reg offset> : (index T) <- index <reg/mem idx> : int, <literal> : (size T) + step 2: convert the array to address-of-element + <reg x> : (address T) <- advance <reg/mem A> : (array T), <reg offset> : (index T) + implicitly compares the offset with the size, panic if greater + => + compare <reg offset> : (index T), <reg/mem> : (array T) + jge panic + step 3: use the address to the element + ... + +(index T) is a special type. You can do only two things with it: + - pass it to the advance instruction + - convert it to a number (but no converting back) + +(address T) is a short-term pointer. You can't store addresses in structs, you +can't define global variables of that type, and you can't pass the type to the +memory allocator to save to the heap. Only place you can store an (address T) +is on the stack or a register. + +[But you can still be holding an address in a long-lived stack frame after +it's been freed?!] + +== Problem 2 + +How to dereference a heap allocation? diff --git a/archive/3.transect/compiler4 b/archive/3.transect/compiler4 new file mode 100644 index 00000000..8dfb8ccd --- /dev/null +++ b/archive/3.transect/compiler4 @@ -0,0 +1,84 @@ +== Goal + +A memory-safe language with a simple translator to x86 that can be feasibly written in x86. + +== Definitions of terms + +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. + +== Implications + +=> Each instruction matches a pattern and yields a template to emit. +=> There's a 1-to-1 mapping between instructions in the source language and x86 machine code. + Zero runtime. +=> Programmers have to decide how to use registers. +=> Translator can't insert any instructions that write to registers. (We don't know if a register is in use.) + +== Lessons from Mu + +1. For easy bounds checking, never advance pointers to arrays or heap allocations. No pointer arithmetic. +2. Store the array length with the array. +3. Store an allocation id with heap allocations. Allocation id goes monotonically up, never gets reused. When it wraps around to zero the program panics. +4. Heap pointers also carry around allocation id. +5. When dereferencing a heap pointer, first ensure its alloc id matches the alloc id of the payload. This ensures some other copy of the pointer didn't get freed (and potentially reused) + +== Problem 1 + +How to index into an array? + + The array has a length that needs to be checked. + Its elements have a type T. + The base will be in memory, either on the stack or the heap. + The index may be in the register, stack or heap. + +That's too much work to do in a single instruction. + +So arrays have to take multiple steps. And we have to guard against the steps +being misused in unsafe ways. + +To index into an array with elements of type T, starting with the size of the +array in bytes: + + step 1: get the offset the index is at + <reg offset> : (index T) <- index <reg/mem idx> : int, <literal> : (size T) + step 2: convert the array to address-of-element + <reg x> : (address T) <- advance <reg/mem A> : (array T), <reg offset> : (index T) + implicitly compares the offset with the size, panic if greater + => + compare <reg offset> : (index T), <reg/mem> : (array T) + jge panic + step 3: use the address to the element + ... + +(index T) is a special type. You can do only two things with it: + - pass it to the advance instruction + - convert it to a number (but no converting back) + +(address T) is a short-term pointer. You can't store addresses in structs, you +can't define global variables of that type, and you can't pass the type to the +memory allocator to save to the heap. You also can't store addresses in the +stack, because you may encounter a free before you end the function. + +Maybe we'll also forbid any sort of copy of address types. Only place you can +store an (address T) is the register you saved to. To copy you need a handle +to a heap allocation. + +Still not entirely protected against temporal issues. But pretty close. + +== Problem 2 + +How to dereference a heap allocation? + +== List of types + +int +char +(address _) X +(array _) +(handle _) diff --git a/archive/3.transect/compiler5 b/archive/3.transect/compiler5 new file mode 100644 index 00000000..aeb857f4 --- /dev/null +++ b/archive/3.transect/compiler5 @@ -0,0 +1,32 @@ +== Goal + +A memory-safe language with a simple translator to x86 that can be feasibly written in x86. + +== Definitions of terms + +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. + +== types + +int +char +(address _ t), t ∋ {stack, heap, global} +(array _ t), t ∋ {stack, heap, global} + +stack addresses can't be copied to heap or global +heap addresses can't be copied [1] +global addresses you're free to use anywhere + +[1] (address _ heap) can't be copied or stored, can't be part of a type or +choice. Only thing you can do with it is access it from the register you wrote +it to. And even that not past a call instruction. Important detail: `free()` +is a call. So an address to something on the heap can never be invalid if the +program type-checks. + +<reg x> : (address T m) <- advance <reg/mem> : (array T m), <reg offset> : (index T) diff --git a/archive/3.transect/compiler6 b/archive/3.transect/compiler6 new file mode 100644 index 00000000..48a7030f --- /dev/null +++ b/archive/3.transect/compiler6 @@ -0,0 +1,36 @@ +== Goal + +A memory-safe language with a simple translator to x86 that can be feasibly written in x86. + +== Definitions of terms + +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. + +== types + +int +char +(address _) +(array _ n) +(ref _) + +addresses can't be saved to stack or global, + or included in compound types + or used across a call (to eliminate possibility of free) + +<reg x> : (address T) <- advance <reg/mem> : (array T), <reg offset> : (index T) + +arrays require a size +(ref array _) may not include a size + +== open questions +Is argv an address? +Global variables are easiest to map to addresses. +Ideally we'd represent 'indirect' as a '*' and we could just count to make +sure that an instruction never has more than one '*'. diff --git a/archive/3.transect/compiler7 b/archive/3.transect/compiler7 new file mode 100644 index 00000000..cf7d454f --- /dev/null +++ b/archive/3.transect/compiler7 @@ -0,0 +1,46 @@ +== Goal + +A memory-safe language with a simple translator to x86 that can be feasibly written in x86. + +== Definitions of terms + +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. + +== types + +int +char +(address _ stack|heap|global) +(array _ n) # on stack or global +(ref _) +(ref array _) # by definition always on the heap + +addresses to global can be saved and manipulated as usual +addresses on stack can't be saved to heap +addresses on heap can't be saved to global (use ref) + +addresses to stack or heap can't be included in compound types + or used across a call + or used across a label + +<reg x> : (address T stack|global) <- advance <reg/mem> : (array T), <reg offset> : (index T) +<reg x> : (address T heap) <- advance *<mem> : (ref array T), <reg offset> : (index T) + +arrays require a size +(ref array _) may not include a size + +Arguments of type 'address' are required to be on the stack or global. Can't +be on the heap. + +So we need duplication for address and ref arguments? + +Argv has type (array (address (array char) global)) + +variables on stack, heap and global are references. The name points at the +address. Use '*' to get at the value. diff --git a/archive/3.transect/compiler8 b/archive/3.transect/compiler8 new file mode 100644 index 00000000..b3b35271 --- /dev/null +++ b/archive/3.transect/compiler8 @@ -0,0 +1,53 @@ +== Goal + +A memory-safe language with a simple translator to x86 that can be feasibly written in x86. + +== Definitions of terms + +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. + +== types + +int +char +(address _) +(array _ n) +(ref _) + +== implications + +addresses can't be saved to stack or global, + or included in compound types + or used across a call (to eliminate possibility of free) + +<reg x> : (address T) <- advance <reg/mem> : (array T), <reg offset> : (index T) + +arrays require a size +(ref array _) may not include a size + +argv has type (array (ref array char)) + +variables on stack, heap and global are references. The name points at the +address. Use '*' to get at the value. + +instructions performing lookups write to register, so that we can reuse the register for temporaries +instructions performing lookups can't read from the register they write to. + But most instructions read from the register they write to?! (in-out params) + +== open questions + +If bounds checks can take multiple instructions, why not perform array +indexing in a single statement in the language? + +But we want addresses as intermediate points to combine instructions with. + +Maybe disallow addresses to function calls, but allow addresses to non-heap +structures to be used spanning function calls and labels. + +That's just for ergonomics. Doesn't add new capability. diff --git a/archive/3.transect/compiler9 b/archive/3.transect/compiler9 new file mode 100644 index 00000000..26becf48 --- /dev/null +++ b/archive/3.transect/compiler9 @@ -0,0 +1,254 @@ +=== 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 register. + - You need them in a register to do a lookup, and + - Saving them to even the stack increases the complexity of checks needed on + function calls or labels. + +Compilation proceeds by pattern matching over an instruction along with +knowledge about the types of its operands, as well as where they're stored +(register/stack/global). We now enumerate mappings for various categories of +instructions, based on the type and location of their operands. + +Where types of operands aren't mentioned below, all operands of an instruction +should have the same (word-length) type. + +Lots of special cases because of limitations of the x86 ISA. Beware. + +A. x : int <- add y + + Requires y to be scalar. Result will always be an int. No pointer arithmetic. + + reg <- add literal => 81 0/subop 3/mod ...(0) + reg <- add reg => 01 3/mod ...(1) + reg <- add stack => 03 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(2) + reg <- add global => 03 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(3) + stack <- add literal => 81 0/subop 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 literal/imm32 ...(4) + stack <- add reg => 01 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(5) + stack <- add stack => disallowed + stack <- add global => disallowed + global <- add literal => 81 0/subop 0/mod 5/rm32/include-disp32 global/disp32 literal/imm32 ...(6) + global <- add reg => 01 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(7) + global <- add stack => disallowed + global <- add global => disallowed + +Similarly for sub, and, or, xor and even copy. Replace the opcodes above with corresponding ones from this table: + + add sub and or xor copy/mov + reg <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 + reg <- op reg 01 or 03 29 or 2b 21 or 23 09 or 0b 31 or 33 89 or 8b + reg <- op stack 03 2b 23 0b 33 8b + reg <- op global 03 2b 23 0b 33 8b + stack <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 + stack <- op reg 01 29 21 09 31 89 + global <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 + global <- op reg 01 29 21 09 31 89 + +B. x/reg : int <- mul y + + Requires both y to be scalar. + x must be in a register. Multiplies can't write to memory. + + reg <- mul literal => 69 ...(8) + reg <- mul reg => 0f af 3/mod ...(9) + reg <- mul stack => 0f af 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(10) + reg <- mul global => 0f af 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(11) + +C. x/EAX/quotient : int, y/EDX/remainder : int <- idiv z # divide EAX by z; store the result in EAX and EDX + + Requires source x and z to both be scalar. + x must be in EAX and y must be in EDX. Divides can't write anywhere else. + + First clear EDX (we don't support ints larger than 32 bits): + 31/xor 3/mod 2/rm32/EDX 2/r32/EDX + + then: + EAX, EDX <- idiv literal => disallowed + EAX, EDX <- idiv reg => f7 7/subop 3/mod ...(12) + EAX, EDX <- idiv stack => f7 7/subop 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 ...(13) + EAX, EDX <- idiv global => f7 7/subop 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(14) + +D. x : int <- not + + Requires x to be an int. + + reg <- not => f7 3/mod ...(15) + stack <- not => f7 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 ...(16) + global <- not => f7 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(17) + +E. x : (address t) <- get o : T, %f + + (Assumes T.f has type t.) + + o can't be on a register since it's a non-primitive (likely larger than a word) + f is a literal + x must be in a register (by definition for an address) + + below '*' works on either address or ref types + + For raw stack values we want to read *(ESP+n) + For raw global values we want to read *disp32 + For address stack values we want to read *(ESP+n)+ + *(ESP+n) contains an address + so we want to compute *(ESP+n) + literal + + reg1 <- get reg2, literal => 8d/lea 1/mod reg2/rm32 literal/disp8 reg1/r32 ...(18) + reg <- get stack, literal => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n+literal/disp8 reg/r32 ...(19) + (simplifying assumption: stack frames can't be larger than 256 bytes) + reg <- get global, literal => 8d/lea 0/mod 5/rm32/include-disp32 global+literal/disp32, reg/r32 ...(20) + +F. x : (offset T) <- index i : int, %size(T) + + reg1 <- index reg2, literal => 69/mul 3/mod 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 diff --git a/archive/3.transect/ex3.k2 b/archive/3.transect/ex3.k2 new file mode 100644 index 00000000..63151396 --- /dev/null +++ b/archive/3.transect/ex3.k2 @@ -0,0 +1,22 @@ +# add the first 10 numbers, and return the result in the exit code + +fn main [ + var result/EBX : int + result/EBX <- copy 0 + var counter/ECX : int + counter/ECX <- copy 1 + { + compare counter/ECX, 10 + break-if > + result/EBX <- add counter/ECX + counter/ECX <- add 1 + loop + } + call exit, 1 +] + +fn exit x : int [ + code/EBX <- copy x + code/EAX <- copy 1/exit + syscall +] diff --git a/archive/3.transect/ex4.k2 b/archive/3.transect/ex4.k2 new file mode 100644 index 00000000..9a7ddee7 --- /dev/null +++ b/archive/3.transect/ex4.k2 @@ -0,0 +1,34 @@ +## read a character from stdin, save it to a global, write it to stdout + +# variables are always references +# read their address with their names: x (can't write to their address) +# read/write their contents with a lookup: *x +var x : char + +fn main [ + call read 0/stdin, x, 1/size + result/EAX <- call write 1/stdout, x, 1/size + call exit, result/EAX +] + +fn read fd : int, x : (address array byte), size : int [ + EBX <- copy fd + ECX <- copy x + EDX <- copy size + EAX <- copy 3/read + syscall +] + +fn write fd : int, x : (address array byte), size : int [ + EBX <- copy fd + ECX <- copy x + EDX <- copy size + EAX <- copy 4/write + syscall +] + +fn exit x : int [ + code/EBX <- copy x + code/EAX <- copy 1/exit + syscall +] diff --git a/archive/3.transect/ex5.k2 b/archive/3.transect/ex5.k2 new file mode 100644 index 00000000..0d7148fe --- /dev/null +++ b/archive/3.transect/ex5.k2 @@ -0,0 +1,30 @@ +# read a character from stdin, save it to a local on the stack, write it to stdout + +fn main [ + var x : char + call read 0/stdin, x, 1/size + result/EBX <- call write 1/stdout, x, 1/size + call exit-EBX +] + +fn read fd : int, x : (address array byte), size : int [ + EBX <- copy fd + ECX <- copy x + EDX <- copy size + EAX <- copy 3/read + syscall +] + +fn write fd : int, x : (address array byte), size : int [ + EBX <- copy fd + ECX <- copy x + EDX <- copy size + EAX <- copy 4/write + syscall +] + +# like exit, but assumes the code is already in EBX +fn exit-EBX [ + code/EAX <- copy 1/exit + syscall +] diff --git a/archive/3.transect/ex6.k2 b/archive/3.transect/ex6.k2 new file mode 100644 index 00000000..cd68f861 --- /dev/null +++ b/archive/3.transect/ex6.k2 @@ -0,0 +1,23 @@ +## print out a (global variable) string to stdout + +var size : int = 14 +var x : (array character) = "hello, world!" + +fn main [ + call write 1/stdout, x, size + call exit, 0 +] + +fn write fd : int, x : (address array byte), size : int [ + EBX <- copy fd + ECX <- copy x + EDX <- copy size + EAX <- copy 4/write + syscall +] + +fn exit x : int [ + code/EBX <- copy x + code/EAX <- copy 1/exit + syscall +] diff --git a/archive/3.transect/ex7.k2 b/archive/3.transect/ex7.k2 new file mode 100644 index 00000000..3ede2c5e --- /dev/null +++ b/archive/3.transect/ex7.k2 @@ -0,0 +1,64 @@ +# example showing file syscalls +# +# Create a file, open it for writing, write a character to it, close it, open +# it for reading, read a character from it, close it, delete it, and return +# the character read. + +var stream : int = 0 +var a : char = 97 +var b : char = 0 +var filename : (array char) = ".foo" + +fn main [ + call create, filename + *stream <- call open, filename, 1/wronly + call write, *stream, a, 1 + call close, *stream + stream <- call open, filename, 0/rdonly + call read, *stream, b, 1 + call close, *stream + call unlink, filename + var result/EBX : char + result/EBX <- copy b # TODO: copy char to int? + call exit-EBX +] + +fn read fd : int, x : (address array byte), size : int [ + EBX <- copy fd + ECX <- copy x + EDX <- copy size + EAX <- copy 3/read + syscall +] + +fn write fd : int, x : (address array byte), size : int [ + EBX <- copy fd + ECX <- copy x + EDX <- copy size + EAX <- copy 4/write + syscall +] + +fn open name : (address array byte) [ + EBX <- copy name + EAX <- copy 5/open + syscall +] + +fn close name : (address array byte) [ + EBX <- copy name + EAX <- copy 6/close + syscall +] + +fn unlink name : (address array byte) [ + EBX <- copy name + EAX <- copy 10/unlink + syscall +] + +# like exit, but assumes the code is already in EBX +fn exit-EBX [ + code/EAX <- copy 1/exit + syscall +] diff --git a/archive/3.transect/ex8.k2 b/archive/3.transect/ex8.k2 new file mode 100644 index 00000000..dfef03b0 --- /dev/null +++ b/archive/3.transect/ex8.k2 @@ -0,0 +1,36 @@ +# Example reading commandline arguments: compute length of first arg. + +fn main argc : int, argv : (array (ref array char)) -> [ + var tmp : (index char) + tmp <- index 1, %size(ref array char) + var tmp2 : (address (ref array char)) + tmp2 <- advance argv, tmp + var s/EBX : (ref array char) + s/EBX <- copy *tmp2 + var result/EAX : int + result/EAX <- ascii_length s/EBX + call exit, result/EAX +] + +fn ascii_length s : (ref array char) -> result : int [ + var result/EBX : int + result/EBX <- copy 0 + { + var tmp0/EDI : (offset char) + tmp0/EDI <- index result/EBX, %size(char) + var tmp/EDX : (address char) + tmp/EDX <- advance *s, tmp0/EDI + var c/ECX : char + c/ECX <- copy *tmp + compare c/ECX, 0 + break-if-equal + loop + } + return result/EBX +] + +fn exit x : int [ + code/EBX <- copy x + code/EAX <- copy 1/exit + syscall +] diff --git a/archive/3.transect/factorial.k2 b/archive/3.transect/factorial.k2 new file mode 100644 index 00000000..79269773 --- /dev/null +++ b/archive/3.transect/factorial.k2 @@ -0,0 +1,16 @@ +# compute the factorial of 5, and return the result in the exit code + +fn factorial n : int -> result/EAX : int [ + result/EAX <- copy 1 + { + compare n, 1 + break-if <= + var tmp/EBX : int + tmp/EBX <- copy n + tmp/EBX <- subtract 1 + var tmp2/EAX : int + tmp2/EAX <- call factorial, tmp/EBX + result/EAX <- multiply tmp2/EAX, n + } + return result/EAX +] diff --git a/archive/3.transect/vimrc.vim b/archive/3.transect/vimrc.vim new file mode 100644 index 00000000..d8b70fbc --- /dev/null +++ b/archive/3.transect/vimrc.vim @@ -0,0 +1,36 @@ +" Highlighting literate directives in C++ sources. +function! HighlightTangledFile() + " Tangled comments only make sense in the sources and are stripped out of + " the generated .cc file. They're highlighted same as regular comments. + syntax match tangledComment /\/\/:.*/ | highlight link tangledComment Comment + syntax match tangledSalientComment /\/\/::.*/ | highlight link tangledSalientComment SalientComment + set comments-=:// + set comments-=n:// + set comments+=n://:,n:// + + " Inside tangle scenarios. + syntax region tangleDirective start=+:(+ skip=+".*"+ end=+)+ + highlight link tangleDirective Delimiter + syntax match traceContains /^+.*/ + highlight traceContains ctermfg=darkgreen + syntax match traceAbsent /^-.*/ + highlight traceAbsent ctermfg=darkred + syntax match tangleScenarioSetup /^\s*% .*/ | highlight link tangleScenarioSetup SpecialChar + + " Our C++ files can have Mu code in scenarios, so highlight Mu comments like + " regular comments. + syntax match muComment /#.*$/ + highlight link muComment Comment + syntax match muSalientComment /##.*$/ | highlight link muSalientComment SalientComment + syntax match muCommentedCode /#? .*$/ | highlight link muCommentedCode CommentedCode + set comments+=n:# +endfunction +augroup LocalVimrc + autocmd BufRead,BufNewFile *.cc call HighlightTangledFile() +augroup END + +" Scenarios considered: +" opening or starting vim with a new or existing file without an extension (should interpret as C++) +" starting vim or opening a buffer without a file name (ok to do nothing) +" opening a second file in a new or existing window (shouldn't mess up existing highlighting) +" reloading an existing file (shouldn't mess up existing highlighting) |