path: root/docs/history/transcript.md

# development transcript

these are historical requests and replies, kept as originally recorded. commands and feature descriptions here may refer to earlier layouts. use the current README.md and LEARN.md for instructions.


each of my messages is quoted exactly, followed by a summary of the reply.

### 1

> codegolf a tiny cpu vm in C89. the goal is to achieve the lowest character count possible. include an assembler as well (scored separately) and a hello world program (not scored, but elegance and simplicity is a bonus)
> it must be capable of re-entrant code and a realistically workable instruction set.

**summary:** a two-stack forth-style machine. the vm was 384 bytes: one ternary chain inside `while(o=m[p++])`, the top two stack items cached in `a` and `b`, the program loaded with `read(open(...))` so it needs no headers, and both stacks inside the 65536-word memory. it had 22 opcodes including div and mod, a two-word literal, and jump/call targets popped from the stack. the assembler was 348 bytes and two-pass, using `strcspn` instead of `strchr` so the implicit int return stays safe on 64-bit. hello world was a pointer loop over a string with a zero terminator. re-entrancy was shown with a recursive factorial plus a recursive decimal printer.

### 2

> your cpu should also be realistically close to hardware (translating it to logical circuitry hardware should be fairly easy) and sport an acceptably fast execution (if hypothetically ported to hardware, not in software)
>
> assume i/o is handled by two external functions, `char Q()` (getchar) and `void G(char)` (putchar) and a state variable J (boolean, shows if input is empty).
>
> don't be afraid to use macros.

**summary:** no reply was sent to this message at the time. it was answered together with message 3.

### 3

> pro tip: if you define a macro as `!o--`, you can save 2 characters per if condition
> oh and btw, newlines are free

**summary:** used the tip as `#define X !--o?`, with pre-decrement because opcode 0 (halt) is already handled by the loop, and with the `?` folded into the macro and free newlines used as separators. the hardware-oriented redesign: bit 0 of each word is a literal flag, so literals take one cycle like the j1 cpu. div and mod were dropped because they can't finish in one cycle and were replaced by an arithmetic shift right, giving 8 alu ops that decode from 3 bits. every instruction does a fixed amount of work with at most one data memory access, and call and jump share a datapath (`r-=o`). i/o now goes through `Q`, `G` and a `?` op that reads `J`. the result was the vm at 339 bytes and the assembler at 346. the final golfed code:

```c
#define X !--o?
int m[1<<16],p,s=65e3,r=6e4,o,a,b;main(c,v)char**v;{read(open(v[1],0),m,s);while(o=m[p++])a=m[s],b=m[s+1],o&1?m[--s]=o>>1:(o/=2,X
m[s]=m[a]:X
m[a]=b,s+=2:X
m[s]=m[s-~a]:X
s++:X
m[s]=b,m[s+1]=a:(o-=2)<1?m[r]=p,r-=o,p=a,s++:X
p=b?p:a,s+=2:X
p=m[--r]:X
m[--s]=Q():X
m[--s]=J:X
G(a),s++:(m[++s]=X
b+a:X
b-a:X
b*a:X
b&a:X
b|a:X
b^a:X
b>>a:b<a));}
```

```c
char t[9999][99],*o="q@!$_~cjzr,?.+-*&|^><",*q;A[9999],k,i,j,n,P;E(y){n++;write(P,&y,4);}V(char*s){for(j=k;j--&&(*t[j]-58||strcmp(t[j]+1,s)););return~j?A[j]:atoi(s);}main(){while(~scanf("%s",t[k]))k++;for(;P<2;P++)for(n=i=0;i<k;i++)if(*(q=t[i])==34)while(*++q)E(*q);else*q==58?A[i]=n:!q[1]&&o[j=strcspn(o,q)]?E(j*2):*q==35?E(V(q+1)):E(V(q)*2+1);}
```

### 4

> now let's move in stages. write a compiler that takes this assembler's code and converts it into darwin arm

**summary:** an ungolfed c89 compiler from vm assembly to darwin arm64 assembly. every word got its own label, the image was emitted as an addressable data array, x19/x20/x21 held the memory base and the two stack pointers, and computed jumps went through a table of offsets. a literal followed by a jump became a direct branch. `Q` and `G` went through `sxtb`, since char is signed on apple arm64, and `J` was read with `ldrb`. it was verified by assembling with llvm-mc for darwin, then rewriting to linux with sed and running under qemu, where it matched the vm byte for byte. this version couldn't handle self-modifying code.

### 5

> can you write the assembler in assembly and pair the code with the assembly and the assembler so that it can re-wire itself at runtime? or maybe include an interp for self-modification, otherwise fns are exec'd native

**summary:** both. `aslib.s` is the assembler written in vm assembly as a library (`a.src`, `a.dst`, `a.org`, `a.lab`, then `a.run c`), and with `asmain.s` it's a 568-word standalone assembler. it's byte-identical to the c assembler and reaches a fixpoint when assembling itself. this is also where the `:;comment` trick came from. the compiler became a hybrid. the image is split into basic blocks, each block counts how many of its words differ from the original image, and stores into code go through a slow path that updates the counters. clean blocks run native, while dirty blocks and anything past the image run in an interpreter compiled into the same binary, which hands control back to native code whenever it lands in a clean block. `cc -t` printed `[` and `]` at each switch. the demo rewired a function at runtime to point at freshly assembled code and then restored it.

### 6

> which one do you like more? and which is more performant?
> keep that one, then port to using llvm ir so that it can be platform independent

**summary:** no reply was sent at the time. the llvm port was dropped when message 7 changed direction. the question was answered at the start of the reply to message 7: the hybrid was the favorite because it kept the vm's semantics exact. the plain compiler was slightly faster on code that never rewrites itself, but it silently ran stale code once anything did. the zygote beats both.

### 7

> can you make it a zygote approach?
> a minimal core loads first, reads and compiles the program (either wholly or partially, for speed) and replaces it with itself. so it's like a jvm but self-contained and on the same level as itself, where the assembler can itself be modified in-memory to assemble different code. for this we need to ditch llvm

**summary:** the current design, described above. the native core only does jit and glue. it loads the genome (boot loader + assembler, both vm code) at 48000. the boot loader reads source until eof or a backtick, assembles it at 0 and jumps there. compilation is lazy per block, straight from live memory, with superblocks through `z`, fused constant targets, and dispatch chained through a table. invalidation uses the coverage byte map plus a store hook, so self-modified code gets retranslated instead of interpreted. the resident assembler sits at fixed addresses, and `repl.s` rewrites its mnemonic table so `p` means out, then assembles and runs input chunks in a loop, overwriting the same address each time. verified under qemu on linux arm64, including the self-hosted assembler running on the zygote. about 4x faster than the golfed interpreter.

### 8

> damn dawg you made an entire baremetal os?
>
> let's move to cowork. pack everything up alongside a transcript of every message i've sent and your own notes on what you've implemented in an md file, with the code, so i can move it.

**summary:** not quite an os. it's a userland runtime. it still runs on darwin or linux, uses their mmap for executable memory, and gets i/o from the host through `Q`, `G` and `J`. there's no scheduler, no drivers and no hardware access, so a closer description is a tiny self-hosting jit, in the spirit of a jvm. the first packing attempt bundled every stage's code with a full test script.

### 9

> nono we don't need all the code, just the recent ones. my msgs and your summaries are more important and all should be there

**summary:** this package. only the zygote stack plus its examples and tests are included, and earlier stages appear only as summaries. the golfed reference vm and assembler are inlined under message 3, because they define the instruction set.

### 10

> we're gonna make this thing cooler. make the syntax C-like whilst still keeping the forth capabilities like super-homiconicity and the likes, add explicit and automatic gc (use a fast approach) and memory management that looks like this:
> every heap object has a classifier u m d, up middle down. up means the object will die at the scope above (becomes m when returned to the parent scope, and it must be returned and cannot be discarded). m means it must be used here and can be passed down (but once it's recasted as u or d it can't be casted back to m in this scope). d means the variable is passed down, and its lifetime ends after it's given for the first time to a scope lower than the current one.
> ask me questions to clarify this approach, then add it to the code and also add a simple static analyzer which checks these lifetimes

my answers to the clarifying questions, exactly:

> scope: every { } block
>
> lending an m object to a callee: borrow, no escape (Recommended)
>
> storing a heap object inside another object or a global: container gets ownership. putting a value inside a container requires its umd to match the parent, and from then on, the umd for that is also inherited from the parent (as in if a parent m is casted to d, so is the child heap object)
>
> gc: free lists + mark-sweep (Recommended)
>
> where the compiler lives: resident in vm code. bootstrap it step by step, by writing a c-like in core.c and then rewriting the compiler inside the c-like. also bring back llvm if you think it'll make your job easier
>
> homoiconic features: parse words, quoted code blocks, inline stack code, patchable compiler tables
>
> how an inner block hands a u object up: expression and assign, both
>
> when the analyzer runs: inside the compiler but can be turned off if the code requests it

**summary:** the genome is now zc, a typeless c-like language, described above. stage 0 is `zc0.c` (kept as its own file next to core.c rather than inside it, so the runtime still has one native file), and the resident compiler is `src/compiler.zc` plus `src/rt.zc`, which reached a byte-identical fixpoint compiling itself. llvm wasn't brought back, since the target is the vm itself. memory went to 1m words, and core.c gained an interpreter for non-arm64 hosts. calls i made without asking: tags go on signatures (`fn f(m a, d b) -> u`) and recasts are `x as u` / `x as d`; a d object touched inside an inner block moves into that block; storing into a borrowed object, a global or untracked memory needs `as d`; handing a u up by assignment only reaches the directly enclosing block; unchecked code gives its objects to the collector. the old asm genome moved to `legacy/`.

### 11

> progress report?
> add types please :)
> mostly as a compiler primitive though, plus type-inspection via reflection
> and a small optional typechecker (default off)
> oh and keep the stuff you write as a history scrapbook
> if it helps, add a path to the hardware which is called "virtual enhancements", and allows up to 512 custom operations to be compiled down via jit into hardware-level speeds and interoped directly into a fast path in the vm to become essentially custom wiring. useful for division and other stuff as a dynamic runtime path

my answers to the clarifying questions, exactly:

> types: words + structs + generics
>
> reflection: runtime type of heap objects, function signatures, typeof at compile time
>
> how an enhancement is defined: either actual C or llvm ir code or vm code or micro-ops passed through an optimizer. since for example, micro-ops and vm code are not sufficient for optimizing things like division
>
> scrapbook: notes + code snapshots

**summary:** the progress report said the previous round was finished and shipped. i then laid out a plan where the core would compile c or llvm ir enhancement sources at runtime with the host toolchain and load the result. part of that reply was stopped by a safety check before it finished, so i stopped and checked in instead of building it.

### 12

> also make the umd syntax like `type.u name`, and casting is multiplication `u*name`
> ideally i'd prefer memory to be unlimited words growing until system oom, but 1m is fine
> core.c plain interp is also nice
> zc0.c own file is fine
> i mentioned llvm for portability to non-arm targets
> yes, d object semantic that was intended
> u object hands up one block and becomes an m, that's fine. the code can make it a u or a d or whatever
> explain your gaps more
>
> wait why safety check? what's wrong with that

my answers to the clarifying questions, exactly:

> declarations: c-style, var -> let
>
> tags on untyped values and the names u, m, d: names reserved, bare .u allowed, untype is m by default
>
> llvm: llvm jit backend (Recommended)

**summary:** on the safety check: nothing was wrong with the request. my best guess was that it tripped on the plan for a program inside the vm handing source text to the system compiler and loading the result into the running process, since that pattern also shows up in malware. with llvm meant for portability, that path wasn't needed. the gaps got the longer explanations that are now under open ends above. then the round itself:

**syntax.** declarations are c-style (`int x`, `*node.m p`), `let` replaces `var` for untyped and inferred declarations, tags are `.u .m .d` after the type or on their own, recasts are `u*x` / `d*x` / `m*x`, `u m d` are reserved, and an untagged parameter counts as an m lend.

**types.** a compiler primitive: hash-consed records with structs, generic structs and functions, fixed arrays, function types, `typeof`/`sizeof`, `as` casts and a reflection api, with object headers carrying their type. the typechecker is off by default and turned on with `typecheck on;`.

**virtual enhancements.** opcode 21 installs, 22 to 533 are the slots. micro-op recipes and lifted vm code go through an optimizer in the core (folding, cse, dce, multiply-high division by constants) and get inlined by both jits. the language's own `/ % <<` now run on them.

**backends.** a tiered llvm backend (`-DZYLLVM`) for non-arm hosts.

**bootstrap and history.** it still reaches its fixpoint on all three backends. `history/` holds notes for every stage and code from stages 7, 10 and this one (in 11-types-enhancements).

### 13

> gaps
> 1. when there's a var state change to d, mark that var as dead by default for any other scope that can access it afterwards. u is fine since it just returns
> 2. any suggestions for a cheap fix?
> 3. it's fine, rare occurrence (probably?), suggest a fix
> 4. fix that
> 5. suggest a fix
> 6. fix
> 7. fix

**summary:** the numbers followed the gap list from my previous chat message. here's what each one got.

**1. joins.** a variable that became d, or was given away, on any path is dead after the join, and fixup code frees it on the paths that still own it. a loop's exit state is the join of its breaks and its normal exit. giving something away on a path that loops back is still an error. u and borrows don't get the dead treatment.

**2, 3 and 5.** suggestions only, now under open ends: a quarantine on reuse plus "borrowed from" marks on pointer-typed values for aliases, a stack-depth opcode for the collector, and page-indexed invalidation plus per-slot install tracking for the jit.

**4. heap.** a buddy allocator.

**6. stack checks.** all three stacks are checked: data and return at every block exit on all backends, and frames in every prologue.

**7. the small stuff.** error recovery with up to 20 reported errors, line numbers carried in token lists, a signature prescan over the whole unit so prototypes are optional, storing into a borrowed object moving the object automatically, `?:`, and go-style `switch`. on the side, a 4-token lookahead fixed `**` declarations.

### 14

> how costly is it if we add a counter to each block to see how many times it runs, then run the optimizer on it if it's a hot path?

> continue

**summary:** answered without building anything. about 4 instructions per block entry while a block is being counted, and nothing once its optimized translation replaces it. the optimizing pass would reuse the enhancement lifter, optimizer and register allocator. lifting whole blocks would need jz side exits and barriers at calls and i/o. compiling a block that way takes microseconds, against milliseconds for llvm, and keeping values in registers instead of the memory stack likely gives 2 to 4x on tight loops. it's listed under open ends. then the gap fixes continued.

### 15

> write some really cool examples for this language

> no, wdym building a fresh vm?? just pocs 😭 we already have a compiler and everything

**summary:** my progress note had said "building a fresh vm", which only meant compiling core.c into a binary to run the examples. eight proofs of concept went into `examples/`: mandel, bf, dump, tree, lang, staged, quine and life, each described under files above and checked by `test.sh` on all three backends.

### 16

> add opt keywords, for example `optim` (or o3, i prefer o3 as the keyword) will cause any vars in a scope to not assign heap type metadata, compiles with opt level o3 and is immediately compiled down to native, and when used with variables they must be always typed and it reduces the perf cost for accessing or modifying them, etc etc. add a `fixed` keyword which says that an array has a fixed size and cannot be resized, etc

my answers to the clarifying questions, exactly:

> where o3 goes: functions, blocks and single vars
>
> how far o3 goes: real optimizing tier (Recommended)
>
> what o3 code may give up: type stamps on objects, zero-filling new objects, the address of o3 vars, stack and frame checks, also i don't like the -> return type syntax. please replace it with the c-like syntax
>
> arrays: add growable arrays too (Recommended)

**summary:** three things changed.

**return types.** functions are declared c-style now, `int f(int x)`, `*node.u make()`, with fn types written `int(int, *char)`. `->` is gone from the compiler, zc0, the tests and the examples.

**arrays.** `[]T` grows (`push`, `pop`, `resize`, `len`, `cap`), and `fixed []T` can't change size after `new(fixed []T, n)`. both are bounds-checked. `[n]T` stays as it was, plus a compile-time check for constant indexes.

**o3.** on functions, blocks and single variables, with the trade-offs you picked, and a real optimizing tier in the core, described in the o3 section above. it compiles at install time on arm64 and llvm and has a region interpreter for the plain build. measured gains are 1.5 to 2.8x on the interpreter, 8 to 100x on llvm and 20 to 43x on arm64 (under qemu) for loop-heavy kernels, and much less for call-heavy ones. on the way, the arm64 jit learned to specialize an enhancement on literal inputs, so `x / 7` is a multiply-high everywhere, not only in o3 code. tests for arrays and o3 turned up an old heap bug: freeing a container could merge one of its children into it while it was still being freed, which corrupted a free list. growable arrays hit it every time. it's fixed.

### 17

> generics should go after fn name and before parens
> we also need some machinery for converting values to/from o3. to is pretty easy, we just hand over the data, and o3 ignores the fat metadata. from is a bit harder, there needs to be a system to get type hints and fatten the metadata for the packed data
> variables just get the latest free register, it's fine for now
> add the fixed array once per region thing
>
> also if you have any tips on how to make the memory system better (aka avoiding gc and leaks/uaf as much as possible) do tell

**summary:** generics went back after the name, `T first<T>(...)`, with the return type allowed to use them before the list declares them. o3 got fattening on the way out (the section above): `new_raw` keeps the requested size in the type word, and the compiler calls `fatten` with the static type wherever o3 data reaches normal code. registers now follow scopes, so a closed scope's register goes to the next variable. fixed arrays in o3 variables keep their items and length in two hidden register variables. the memory tips were answered in chat, not built.


### 18

> there's been changes. run a consistency pass, fix comment stylings (change the cringe dry ones to the format you used), bug fixes, fix the lsp, write tests for it, then impl the remaining points in todo.md
>
> the analyzer should be in tandem with the compiler, and immediate words / syntax modifications should affect it just the same. same with the syntax highlighter.

**summary:** the language server is the compiler now. `src/compiler.zc` has a check mode (errors become records, compiling goes on, hints are reported), and `lsp/server.zc` is only the json-rpc layer, the document store and the token writer on top of it, so parse words and syntax changes apply to the check and the highlighting exactly as they do in a build. the old standalone analyzer (`lsp/zclsp.zc`) is gone. struct methods with `this` and closures are real compiler features (they were only recognised by the old analyzer), pointer types can be written `int*`, `vec<T>*`, `point**` (the prefix form still parses), braces are on the same line across the sources, and there is a webassembly build of the microcore with a browser page. the rest of the sweep is in `history/44-check-mode`.