diff options
Diffstat (limited to 'docs/history/17-o3-boundaries/code/examples')
17 files changed, 459 insertions, 0 deletions
diff --git a/docs/history/17-o3-boundaries/code/examples/bf.zc b/docs/history/17-o3-boundaries/code/examples/bf.zc new file mode 100644 index 0000000..384025a --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/bf.zc @@ -0,0 +1,50 @@ +// a brainfuck compiler. it turns a brainfuck program into zc source, hands +// that to the compiler that's sitting in memory, and runs the result, which on +// arm64 means native code. runs of + - < > fold into one statement each. +// give it a program after a backtick, or it runs the hello world below. +let out[30000], n, depth; +fn emit(s) { let i = 0; while (s[i]) { out[n] = s[i]; n++; i++; } return 0; } +fn emitn(int v) { if (v >= 10) emitn(v / 10); out[n] = '0' + v % 10; n++; return 0; } +// how many times does c repeat from s[i] +int run(s, int i, int c) { int k = 0; while (s[i + k] == c) k++; return k; } + +fn translate(s) +{ + int i = 0, k; + n = 0; depth = 0; + emit("let t[30000], p = 0;\n"); + while (s[i]) { + switch (s[i]) { + case '+', '-': + k = run(s, i, s[i]); + emit("t[p] = (t[p] "); emit(s[i] == '+' ? "+ " : "- "); emitn(k); emit(") & 255;\n"); + i = i + k; continue; + case '>', '<': + k = run(s, i, s[i]); + emit("p "); emit(s[i] == '>' ? "+= " : "-= "); emitn(k); emit(";\n"); + i = i + k; continue; + case '[': emit("while (t[p]) {\n"); depth++; + case ']': emit("}\n"); depth--; + case '.': emit("putc(t[p]);\n"); + case ',': emit("t[p] = eof() ? 0 : getc() & 255;\n"); + } + i++; + } + emit("return 0;\n"); + out[n] = 0; + return depth; +} +let hello = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."; +let prog[20000]; +fn main() +{ + let src = hello, k = 0, lines = 0, i = 0; + while (!eof() && k < 19999) { let c = getc(); if (c != 10) { prog[k] = c; k++; } } + prog[k] = 0; + if (k) src = prog; + if (translate(src)) { puts("unbalanced brackets\n"); return 1; } + while (out[i]) { if (out[i] == 10) lines++; i++; } + puts("compiled to "); putn(lines); puts(" lines of zc, running it:\n"); + evals(out); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/dump.zc b/docs/history/17-o3-boundaries/code/examples/dump.zc new file mode 100644 index 0000000..6082213 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/dump.zc @@ -0,0 +1,32 @@ +// printing any struct with no printing code: the heap knows each object's +// type, and reflection walks its fields +struct person { *char name; int age; }; +struct item { *char name; int count; *person owner; }; + +fn dump(p) +{ + let t = typeof_obj(p), i = 0; + if (!t) { puts("?"); return 0; } + tprint(t); puts(" { "); + while (i < tnfields(t)) { + let ft = tftype(t, i), v = p[tfoff(t, i)]; + if (i) puts(", "); + puts(tfname(t, i)); puts(": "); + if (tkind(ft) == TY_PTR && telem(ft) == typeof(char)) { putc('"'); puts(v); putc('"'); } + else if (tkind(ft) == TY_PTR) { if (v) dump(v); else puts("null"); } + else putn(v); + i++; + } + puts(" }"); + return 0; +} +fn main() +{ + *person ana = new(person); + ana.name = "ana"; ana.age = 30; + *item lamp = new(item); + lamp.name = "lamp"; lamp.count = 3; lamp.owner = ana; + dump(lamp); putc(10); + free(d*lamp); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/echo.zc b/docs/history/17-o3-boundaries/code/examples/echo.zc new file mode 100644 index 0000000..01f28b0 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/echo.zc @@ -0,0 +1,2 @@ +// everything after the backtick is left unread, for the program itself +fn main() { while (!eof()) putc(getc()); return 0; } diff --git a/docs/history/17-o3-boundaries/code/examples/fact.zc b/docs/history/17-o3-boundaries/code/examples/fact.zc new file mode 100644 index 0000000..2a218b2 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/fact.zc @@ -0,0 +1,4 @@ +fn fact(n) { if (n < 2) return 1; return n * fact(n - 1); } +// prints in binary, like the old asm example +fn bin(n) { if (n > 1) bin(n >> 1); putc('0' + (n & 1)); return 0; } +fn main() { bin(fact(10)); putc(10); putn(fact(10)); putc(10); return 0; } diff --git a/docs/history/17-o3-boundaries/code/examples/hello.zc b/docs/history/17-o3-boundaries/code/examples/hello.zc new file mode 100644 index 0000000..f36a810 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/hello.zc @@ -0,0 +1 @@ +fn main() { puts("hello, world!\n"); return 0; } diff --git a/docs/history/17-o3-boundaries/code/examples/lang.zc b/docs/history/17-o3-boundaries/code/examples/lang.zc new file mode 100644 index 0000000..e4d91c5 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/lang.zc @@ -0,0 +1,53 @@ +// growing the language from inside a program, while it compiles + +// x |> f calls f(x). on a stack machine that's just "call": the value is +// already on the stack, under f's address. +immediate fn pipe_op() { next(); add_binop("|>", 1, "c"); return 0; } +pipe_op + +// unless (c) stmt +immediate fn unless() +{ + let a; + next(); expect(intern("(")); plainuse(expr()); rval(); expect(intern(")")); + emitseq(useq[0], ulen[0]); // not + a = hole(); op(O_JZ); + substmt(); + setlit(a, here); + return 0; +} +// assert (c): the failure message carries the line it was written on +fn assert_fail(int line) { puts("assertion failed on line "); putn(line); putc(10); halt(); return 0; } +immediate fn assert() +{ + let a, l = tline; + next(); expect(intern("(")); plainuse(expr()); rval(); expect(intern(")")); + emitseq(useq[0], ulen[0]); // not: the jump below skips the failure when it holds + a = hole(); op(O_JZ); + lit(l); callname(intern("assert_fail")); op(O_DROP); + setlit(a, here); + return 0; +} +// times N { body }: the body pasted N times, at compile time +immediate fn times() +{ + let n, b, i = 0; + next(); n = tv; next(); + b = grab(); + while (i < n) { feed(qdup(b)); i++; } + free(d*b); + return 0; +} + +fn double(x) { return x * 2; } +fn inc(x) { return x + 1; } +fn main() +{ + putn(5 |> double |> inc |> double); putc(10); + unless (1 > 2) puts("one isn't bigger than two\n"); + times 3 { putc('*'); } + putc(10); + assert(double(4) == 8); + assert(inc(1) == 3); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/life.zc b/docs/history/17-o3-boundaries/code/examples/life.zc new file mode 100644 index 0000000..a43d660 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/life.zc @@ -0,0 +1,38 @@ +// conway's life on a 10 x 20 torus, with typed 2d arrays in a struct. +// a glider walks diagonally and wraps around the edges. +const H = 10, W = 20; +struct board { [10][20]int c; }; + +int get(*board b, int y, int x) { return b.c[(y + H) % H][(x + W) % W]; } +fn step(*board from, *board to) +{ + for (int y = 0; y < H; y++) + for (int x = 0; x < W; x++) { + int n = 0; + for (int dy = 0 - 1; dy <= 1; dy++) + for (int dx = 0 - 1; dx <= 1; dx++) + if (dy || dx) n += get(from, y + dy, x + dx); + to.c[y][x] = n == 3 || (n == 2 && from.c[y][x]); + } + return 0; +} +fn show(*board b, int gen) +{ + puts("generation "); putn(gen); putc(10); + for (int y = 0; y < H; y++) { for (int x = 0; x < W; x++) putc(b.c[y][x] ? '#' : '.'); putc(10); } + return 0; +} +fn main() +{ + *board a = new(board), b = new(board); + a.c[0][1] = 1; a.c[1][2] = 1; a.c[2][0] = 1; a.c[2][1] = 1; a.c[2][2] = 1; + // two generations a pass, a -> b -> a: owned boards can't be swapped + // through a temporary, since the analyzer can't follow that + for (int g = 0; g <= 40; g += 2) { + if (g % 20 == 0) show(a, g); + step(a, b); + step(b, a); + } + free(d*a); free(d*b); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/lists.zc b/docs/history/17-o3-boundaries/code/examples/lists.zc new file mode 100644 index 0000000..3cf0206 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/lists.zc @@ -0,0 +1,34 @@ +// ownership in practice: a list owns its boxes. nothing here calls free; +// everything is released at the end of the block that owns it. +.u box(v) { let b = new(1); b[0] = v; return u*b; } +.u mklist(cap) { let l = new(cap + 1); l[0] = 0; return u*l; } +// item m*arrives (it was given down), and goes d*on into the borrowed list +fn push(.m l, .d item) { l[l[0] + 1] = d*item; l[0] = l[0] + 1; return 0; } +fn show(.m l) +{ + let i = 1; + putc('['); + while (i <= l[0]) { if (i > 1) putc(' '); putn(l[i][0]); i++; } + putc(']'); + return 0; +} +.u squares(n) { + let l = mklist(n), i = 0; + while (i < n) { + let b = box(i * i); + push(l, d*b); + i++; + } + return u*l; +} +fn main() +{ + let before = live_objects(); + { + let l = squares(6); + show(l); putc(10); + puts("live: "); putn(live_objects() - before); putc(10); + } + puts("after the block: "); putn(live_objects() - before); putc(10); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/mandel.zc b/docs/history/17-o3-boundaries/code/examples/mandel.zc new file mode 100644 index 0000000..5810397 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/mandel.zc @@ -0,0 +1,36 @@ +// the mandelbrot set in 16.16 fixed point. the cpu has no fixed-point +// multiply, so one gets wired in: a 32x32 -> 64 bit multiply, keeping the +// middle 32 bits. the jit inlines it as two native multiplies and a shift. +enhance fmul(a, b) micro + "r2 = mul a b; r3 = mulhs a b" + "; r3 = shl r3 16; r2 = shr r2 16; a = or r3 r2"; + +const ONE = 65536, W = 72, H = 28, MAXIT = 40; +let shades = " .,:;-=+*%#@"; + +int escape(int cx, int cy) { + int x = 0, y = 0, i = 0; + while (i < MAXIT) { + int xx = fmul(x, x), yy = fmul(y, y); + if (xx + yy > 4 * ONE) return i; + y = 2 * fmul(x, y) + cy; + x = xx - yy + cx; + i++; + } + return MAXIT; +} +fn main() +{ + int row = 0; + while (row < H) { + int col = 0, cy = (row * 2400 / (H - 1) - 1200) * ONE / 1000; + while (col < W) { + int cx = (col * 3200 / (W - 1) - 2200) * ONE / 1000, it = escape(cx, cy); + putc(it == MAXIT ? '@' : shades[it * 11 / MAXIT]); + col++; + } + putc(10); + row++; + } + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/primes.zc b/docs/history/17-o3-boundaries/code/examples/primes.zc new file mode 100644 index 0000000..26df0b5 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/primes.zc @@ -0,0 +1,38 @@ +// primes below 60000: an o3 sieve over a fixed array, the primes +// gathered into a growable one, then a few questions asked of them. +// with ZYTRACE=1 the o3 lines show each region being lifted and compiled. + +// marks the composites; f[i] ends up 1 for every prime i +o3 int sieve(fixed []int f) +{ + int n = len(f), c = 0; + for (int i = 2; i < n; i++) f[i] = 1; + for (int i = 2; i * i < n; i++) + if (f[i]) for (int j = i * i; j < n; j += i) f[j] = 0; + for (int i = 2; i < n; i++) c += f[i]; + return c; +} +// the largest gap between neighbours, and where it starts +o3 int gap(fixed []int f, *int at) +{ + int n = len(f), last = 2, best = 0, where = 0; + for (int i = 3; i < n; i++) + if (f[i]) { if (i - last > best) { best = i - last; where = last; } last = i; } + *at = where; + return best; +} +fn main() +{ + fixed []int f = new(fixed []int, 60000); + []int ps = new([]int); + int c = sieve(f), at = 0, twins = 0; + for (int i = 2; i < len(f); i++) if (f[i]) push(ps, i); + o3 { for (int k = 1; k < len(ps); k++) if (ps[k] - ps[k - 1] == 2) twins++; } + puts("primes below 60000: "); putn(c); putc(10); + puts("the last five:"); for (int k = len(ps) - 5; k < len(ps); k++) { putc(' '); putn(ps[k]); } putc(10); + puts("twin pairs: "); putn(twins); putc(10); + int g = gap(f, &at); + puts("widest gap: "); putn(g); puts(", after "); putn(at); putc(10); + free(d*f); free(d*ps); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/quine.zc b/docs/history/17-o3-boundaries/code/examples/quine.zc new file mode 100644 index 0000000..23be8cb --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/quine.zc @@ -0,0 +1 @@ +let s="let s=#;fn main(){let i=0;while(s[i]){if(s[i]==35){putc(34);puts(s);putc(34);}else putc(s[i]);i++;}putc(10);return 0;}";fn main(){let i=0;while(s[i]){if(s[i]==35){putc(34);puts(s);putc(34);}else putc(s[i]);i++;}putc(10);return 0;} diff --git a/docs/history/17-o3-boundaries/code/examples/repl.zc b/docs/history/17-o3-boundaries/code/examples/repl.zc new file mode 100644 index 0000000..b7b81b8 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/repl.zc @@ -0,0 +1,27 @@ +// a repl on the resident compiler: each backtick-separated chunk of input is +// compiled as a function body and run. definitions (fn ...) can be loaded too: +// a chunk that starts with "fn" goes through load instead of eval. +let buf[4000]; +fn readchunk() +{ + let n = 0, c; + while (!eof()) { + c = getc(); + if (c == 96) break; + if (n < 3999) { buf[n] = c; n++; } + } + buf[n] = 0; + return n; +} +fn main() +{ + let q, i; + while (!eof()) { + readchunk(); + q = tokens(buf); + if (q[0] && q[1] == T_ID && q[2] == intern("fn")) load(q); + else eval(q); + free(d*q); + } + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/selfpatch.zc b/docs/history/17-o3-boundaries/code/examples/selfpatch.zc new file mode 100644 index 0000000..074ccec --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/selfpatch.zc @@ -0,0 +1,17 @@ +// code is data: find the literal 'A' inside f's compiled words and rewrite it. +// on the jit the store lands on translated code, which gets dropped and +// retranslated on the next call. +fn f() { putc('A'); return 0; } +fn litw(v) { return v + v + 1; } // how the vm encodes a literal push +fn main() +{ + let p = f; + f(); + while (*p != litw('A')) p++; + *p = litw('B'); + f(); + *p = litw('C'); + f(); + putc(10); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/staged.zc b/docs/history/17-o3-boundaries/code/examples/staged.zc new file mode 100644 index 0000000..5f6342e --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/staged.zc @@ -0,0 +1,35 @@ +// staged code: a program writes a specialized function as source, compiles it +// while running, and calls it. here, polynomials with their coefficients baked +// in as constants, so there's no loop and no array left at runtime. +let buf[2000], n; +fn put(s) { let i = 0; while (s[i]) { buf[n] = s[i]; n++; i++; } return 0; } +fn putnum(int v) { if (v >= 10) putnum(v / 10); buf[n] = '0' + v % 10; n++; return 0; } + +// coefficients c[0] + c[1] x + ... in horner form: ((c3 x + c2) x + c1) x + c0 +fn specialize(*int c, int deg) +{ + n = 0; + put("fn poly(x) { return "); + for (int i = 0; i < deg; i++) put("("); + if (c[deg] < 0) { put("0 - "); putnum(0 - c[deg]); } else putnum(c[deg]); + for (int i = deg - 1; i >= 0; i--) { + put(") * x "); + if (c[i] < 0) { put("- "); putnum(0 - c[i]); } else { put("+ "); putnum(c[i]); } + } + put("; }"); + buf[n] = 0; + return buf; +} +fn main() +{ + [4]int c; + c[0] = 7; c[1] = 0 - 3; c[2] = 0; c[3] = 2; // 2x^3 - 3x + 7 + let src = specialize(c, 3), q = tokens(src); + puts(src); putc(10); + load(q); // compiled now, into the running program + free(d*q); + let f = sval[lookups("poly")]; // and found by name in the compiler's symbol table + for (int x = 0 - 2; x <= 3; x++) { putn(f(x)); putc(' '); } + putc(10); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/tree.zc b/docs/history/17-o3-boundaries/code/examples/tree.zc new file mode 100644 index 0000000..90a01d4 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/tree.zc @@ -0,0 +1,28 @@ +// a binary search tree where every node owns its children. there's no free +// anywhere: when the root's block ends, the whole tree goes with it. +struct node { int v; *node left, right; }; + +*node.u leaf(int v) { *node n = new(node); n.v = v; return u*n; } +// n is borrowed; storing a new leaf into it makes n the leaf's owner +fn insert(*node.m n, int v) +{ + if (v < n.v) { if (n.left) insert(n.left, v); else n.left = leaf(v); } + else { if (n.right) insert(n.right, v); else n.right = leaf(v); } + return 0; +} +fn walk(*node n) { if (!n) return 0; walk(n.left); putn(n.v); putc(' '); walk(n.right); return 0; } +int height(*node n) { if (!n) return 0; int l = height(n.left), r = height(n.right); return 1 + (l > r ? l : r); } + +fn main() +{ + let before = live_objects(); + { + *node root = leaf(50); + int x = 7; + for (int i = 0; i < 30; i++) { x = (x * 37 + 11) % 100; insert(root, x); } + walk(root); putc(10); + puts("height "); putn(height(root)); puts(", live objects "); putn(live_objects() - before); putc(10); + } + puts("after the block: "); putn(live_objects() - before); putc(10); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/typed.zc b/docs/history/17-o3-boundaries/code/examples/typed.zc new file mode 100644 index 0000000..3bba399 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/typed.zc @@ -0,0 +1,44 @@ +// types: structs, a generic container, and looking at it all through reflection +typecheck on; +struct point { int x, y; }; +struct vec<T> { int len, cap; *T items; }; + +*vec<T>.u mkvec<T>(int cap) { + *vec<T> v = new(vec<T>); + v.cap = cap; + v.items = new(T, cap); + return u*v; +} +// x is given away (.d): the vector's memory holds it from now on, and the +// collector looks after it +bool push<T>(*vec<T> v, T.d x) { + if (v.len == v.cap) { free(d*x); return 0; } + v.items[v.len] = d*x; + v.len++; + return 1; +} +fn show(word t) +{ + let i = 0; + tprint(t); puts(" is "); putn(tsize(t)); puts(" words: "); + while (i < tnfields(t)) { if (i) puts(", "); puts(tfname(t, i)); puts(" "); tprint(tftype(t, i)); i++; } + putc(10); + return 0; +} +int main() { + *vec<*point> v = mkvec<*point>(4); + int i = 0; + while (i < 3) { + *point p = new(point); + p.x = i; p.y = i * i; + push(v, d*p); + i++; + } + puts("last: "); putn(v.items[2].y); putc(10); + show(typeof(point)); + show(typeof(*v)); + puts("push is "); tprint(sigof(push)); putc(10); + // generic code is compiled once, so what mkvec stamped is vec<T> + puts("the heap says v is a "); tprint(typeof_obj(v)); puts(", and v.items[0] is a "); tprint(typeof_obj(v.items[0])); putc(10); + return 0; +} diff --git a/docs/history/17-o3-boundaries/code/examples/wiring.zc b/docs/history/17-o3-boundaries/code/examples/wiring.zc new file mode 100644 index 0000000..d5e64f4 --- /dev/null +++ b/docs/history/17-o3-boundaries/code/examples/wiring.zc @@ -0,0 +1,19 @@ +// virtual enhancements: custom opcodes wired into the cpu while compiling. +// the recipes run through the core's optimizer; the jit inlines the result. +enhance popcount(x) micro + "r1 = shr x 1; r1 = and r1 0x55555555; x = sub x r1" + "; r1 = shr x 2; r1 = and r1 0x33333333; x = and x 0x33333333; x = add x r1" + "; r1 = shr x 4; x = add x r1; x = and x 0x0f0f0f0f; x = mul x 0x01010101; x = shr x 24"; +enhance div10(x) micro "x = udiv x 10"; // becomes a multiply-high, no divide +enhance hypot2(a, b) vm { 0 $ * ~ 0 $ * + }; // lifted from vm code +enhance 2 minmax(a, b) micro "r2 = min a b; r1 = max a b; r0 = r2"; +let lo, hi; +fn main() +{ + putn(popcount(0xff00ff)); putc(' '); + putn(div10(12345)); putc(' '); + putn(hypot2(3, 4)); putc(' '); + asm { 9 4 minmax hi ! lo ! } + putn(lo); putc('/'); putn(hi); putc(10); + return 0; +} |