I'm open for consulting for fall/winter/spring. Databases and query engines are most familiar but I'm also spilling out into compilers. I've had some good gigs lately doing general performance engineering too, and I think testing/fuzzing would also work well.
zest progress
I got really unstuck this month.
namespaces
The decision I was been blocked on all summer was how namespaces should work. I'm glad I took a long time to think and talk it through because the final decision ended up being very different from my initial inclinations, but now that I've actually implemented it I can see that it was definitely the right choice. In particular, the way the internals naturally worked out ended up looking very salsa-like, so I think it will be possible to build ide support in the same codebase by adding dependency tracking and evaluation timeouts.
recursive functions
Namespaces also provide recursive functions. Recursive type inference isn't possible with the purely linear dataflow algorithm I'm using so I had to add a tiny amount of backwards propagation. I wanted to do this only for return-type annotations on functions, but due to silly desugaring decisions I made earlier I can't actually separate those annotations from the body of the function. That is, given:
is-even = (n /i64) /bool {
if {n == 0} true else if {n == 1} false else is-even(n - 2)
}
I immediately desugar into:
is-even = (n0) {
n = i64(n)
bool(
if {n == 0} true else if {n == 1} false else is-even(n - 2)
)
}
Currently both of these will type-check, because I propagate information backwards from the entire body of the function to the return-type. But that can lead to type inference being quite sensitive to the details of how the function is written, or even the order in which functions are type-checked. Eg the following wouldn't type-check, because it hits the recursive call before propagating type information to the return-type:
is-even = (n0) {
n = i64(n)
result = bool(
if {n == 0} true else if {n == 1} false else is-even(n - 2)
)
result
}
So I want to make only the first example type-check, and for the second and third examples tell the programmer that they need to add an explicit return-type annotation. But doing that requires some annoying refactoring that I haven't gotten around to yet.
moved inlining
Interpreted and compiled code have different calling conventions. The way I handle this at the moment is I generate a function with the compiled calling convention, and then also generate a wrapper function that handles the interpreter calling convention. The wrapper function then gets inlined during compilation.
Previously I was doing the inlining during codegen, but that caused issues with recursive type inference because there was an invisible extra function blocking the backwards propagation of return-type information. So I moved the inlining of wrapper functions into type inference instead and this ended up being much cleaner anyway.
destination types
I added inference based on destination types - a form of bidirectional typing used heavily in zig.
my-type = union[
a: i64,
b: string,
]
x /my-type = if {condition()} [a: 42] else [b: 'hey']
When the code above is being evaluated in the dynamically-typed interpreter and condition() evaluates to true, the expression returns the single-field struct [a: 53]. On assignment to x it is implicitly converted to my-type. All good.
But in type inference, we infer that the true branch of the expression has type struct[a: i64] and the false branch has type struct[b: string]. These two types are not compatible so an error is reported at compile time.
We could fix this by directly annotating the literals:
x /my-type = if {condition()} [a: 42]/my-type else [b: 'hey']/my-type
This is effectively the solution used in rust and other ml-like languages where you have to import a type in order to use it's constructors. But instead, copying zig, during type inference we can notice that the result of the if expression will always be converted to my-type and push that conversion down through the if expression.
// You write this code.
x /my-type = if {condition()} [a: 42] else [b: 'hey']
// Will be converted to this code during type inference.
x /my-type = if {condition()} [a: 42]/my-type else [b: 'hey']/my-type
This is particularly nice when calling libary functions.
// You write this code.
foo([a: 42], [c: 'blah'])
// Will be converted to this code during type inference.
my-type = %import('cool-library').my-type
my-other-type = %import('cool-library').my-other-type
foo([a: 42]/my-type, [c: 'blah']/my-other-type)
Note though that this never changes the behaviour of the program! The dynamic semantics were always going to do this conversion. But pushing the conversion down during inference allows more programs to succesfully type-check.
I also extended the implicit conversions to work recursively through types, so you can eg implictly convert struct[x: u32] to struct[x: i64].
dead code don't infer
f = (x) {
if %only(%repr-of(x) == i64) {
x + 1
} else {
x
}
}
f(42) // = 43
f('foo') // = 'foo'
Here is a silly function that adds 1 to integers, but returns values of other types unchanged. The %only is a (to-be-renamed) staging annotation - it says that this condition should be evaluated at compile-time. When called with an i64 we only emit the true branch, and when called with other types we only emit the false branch.
I've had that working for a while, but once I started writing real code I realized I was still type-checking both branches even though one of the results would be thrown away. In this case, this meant that f('foo') produced a type error for string + i64 even though that branch is dead code.
I fixed that and now the function type-checks succesfully.
iteration
I've gone for internal iterators because they work better with second-class references.
You can obviously iterate over lists (boring) but also over structs and unions.
print-each = (x) {
%each(x, (i, k, v) {
print(%from-only(i))
print(' = ')
print(%from-only(k))
print(' = ')
print(v)
print('\n')
})
}
print-each([a: 42, b: 'hey'])
// prints:
// 0 = 'a' = 42
// 1 = 'b' = 'hey'
my-type = union[
a: i64,
b: string,
]
print-each([b: 'hey']/my-type)
// prints:
// 0 = 'b' = 'hey'
The IR in the interpreter is very inspired by wasm. Values are pushed and popped on the stack, which makes nested expressions very easy to handle. All other stack actions are expressed by moving values between local variables. Control flow is implicit - most instructions fall through to the next instruction. I like it.
But all of this made it very awkward to bake %each into the interpreter - it's a single instruction that contains backwards-branching control flow and makes function calls. But I didn't want to pay the (mostly type-check related) overhead of desugaring it into an actual loop with several variables and a dynamic field lookup.
My first pass at this required a bunch of ugly special cases spread through the interpreter, and when I came back to it a month later I couldn't remember how anything worked. My second approach was much nicer. I desugar into three consecutive instructions - each_begin, each_body, each_end - each of which only cost one byte in the IR. Execution goes like this:
- We start with
obj, funon the stack. each_beginadds the loop index0to the stack.each_body- Pops
obj, fun, indexfrom the stack. - If
index > obj.len, jumps to the instruction aftereach_end. - Puts
obj, fun, index+1, index, obj[index].key, obj[index].valon the stack. - Calls
fun.
- Pops
funreturns toeach_end.each_endjumps toeach_body.
I also switched while loops to a similar scheme.
enforce purity
Anything that is evaluated at compile-time is not allowed to perform observable side-effects. I got around to actually enforcing this.
namespace{
x = print('foo')
}
// Error: Tried to perform a side effect during pure evaluation: zest.Builtin.print
self-hosted runtime
To avoid having to duplicate a lot of functionality between the interpreter and compiler, I've long planned to have a lot of the zest runtime be implemented in zest (swift and go both take this approach too). I'm now actually loading the runtime and making calls to it.
This required some replumbing because up until now all my code assumed that there was only a single source file to evaluate. Fortunately, the code is all written in a very data-oriented style, so the change was mostly just adding an extra id to a bunch of map lookups.
list and any
Lists are created by conversion from structs.
['a', 'b', 'c'] /list[string]
They don't offer much else yet apart from iteration.
The any type offers type-erasure:
things /list[any] = [42, 'foo', [a: 1, b: 2]]
things.0 // = 42/any
%repr-of(things.0) // = any
%from-any(things.0) // = 42
%repr-of(%from-any(things.0)) // = i64
While you can use any in typed code, it's obviously impossible to use %from-any because we can't know the return type. I plan to also add typed versions, so that all of the below would type-check:
%repr-of-any(things.0) // = i64
%from-any(things.0, type: i64) // = 42
%from-any(things.0, type: string) // panics
reflection
I initially blindly copied the design of reflection from zig's TypeInfo. The builtin function %reflect would return a description of a type:
// This must be in the same order as Repr
reflection = union[
u32: struct[],
i64: struct[],
string: struct[],
struct: reflection-struct,
// etc...
]
reflection-struct = struct[
keys: list[any],
values: list[repr],
]
For example:
%reflect(struct[a: i64, b: string])
// evaluates to:
['struct': [
keys: ['a', 'b'] /list[any],
values: [i64, string] /list[repr],
]]
This is why I added list and any this month! I thought I needed them.
In zig you could write a generic print function using reflection like this (slightly simplified):
fun print(thing: anytype) void {
switch (@typeInfo(@TypeOf(thing))) {
.Struct => |sti| {
printString("{");
inline for (sti.fields, 0..) |field, ix| {
if (ix != 0) printString(", ");
printString(".");
printString(field.name);
printString(" = ");
print(@field(thing, field.name));
}
printString("}");
},
// etc...
}
}
The equivalent code in zest (minus a bunch of annoying manual staging annotations) looked like:
print = (x) {
t = %reflect(%repr-of(x))
if %union-has-key(t, 'struct') {
%print('[')
%each(t.struct.keys, (ix, _, key) {
if {ix != 0} %print(', ')
print(%from-any(key))
%print(': ')
print(x.{%from-any(key)})
})
%print(']')
} else {
// etc...
}
}
But after writing a bunch of code in this style I decided that the whole reflection type feels like an unnecessary indirection. I wanted to stay closer to the ideal of thinking with syntax.
One big difference between zig and zest is that in zig struct is just syntax, but in zest struct is a value in it's own right. And we can also iterate over structs directly, without needing a list of keys. So if we have a type like struct[a: i64, b: string] we can just skip the reflection entirely. All we need is a way to get at the individual pieces of the type:
%unmake(struct[a: i64, b: string])
// evaluates to
[
struct,
[a: i64, b: string],
]
Now the printing code (minus a bunch of annoying manual staging annotations) looks like:
print = (x) {
[head, args] = %unmake(%repr-of(x))
if {head == struct} {
%print('[')
%each(x, (ix, key, value) {
if {ix != 0} %print(', ')
print-key(key)
%print(': ')
print(value)
})
%print(']')
} else {
// etc...
}
}
Printing types is also easy because the arguments to type constructors are just regular structs:
print-repr = (t) {
[head, args] = %unmake(t)
if {head == struct} {
%print('struct')
} else {
// etc...
}
print(args)
}
This kind of parsimony of concepts make me feel like I'm on the right track.
I do eventually want to have pattern matching, so the printing code would look even more direct, and we'd get exhaustiveness checking too:
print = (x) {
match(%repr-of(x),
(struct[..args]) {
%print('[')
%each(x, (ix, key, value) {
if {ix != 0} %print(', ')
print-key(key)
%print(': ')
print(value)
})
%print(']')
},
// etc...
)
}
print-repr = (t) {
match(t,
(struct[..args]) {
%print('struct')
print(args)
},
// etc...
)
}
function/namespace validation stubs
One of the ideals of zest is that any value can be printed and read back in to produce an equal value.
f = (a) (b) a + b
g = f(1)
g
// [a: 1]/fun[42, a: i64]
to-string(g)
// '[a: 1]/fun[42, a: i64]`
read(to-string(g))
// [a: 1]/fun[42, a: i64]
g == read(to-string(g))
// true
But what if I make up an invalid function and then call it:
h = read('[b: 1]/fun[99999, c: string]')
h()
It's tempting to say that the call to read should throw an error, but then we can't read and manipulate data printed by other programs. So it has to be the call h() that throws the error. But then do we have to validate every function on every call? That would be expensive.
My solution for now is to add a bit to the function type tracking whether it is valid/unknown. When calling a function in dynamically-typed, if the bit is set to unknown then we do the validation. If validation succeeds, we set the bit to valid. If validation fails, we throw an error. (We don't set the bit to invalid, because we might later load the code needed for that function and try to call it again).
At compile-time we know the types of functions so we can do the validation immediately and then not need to check the bit at runtime in compiled code.
The actual validation code currently is just panic("TODO") because I don't actually need it yet, I just needed to make sure I had a solution.
You'll also notice at the moment I'm using consecutive integer ids for functions (fun[42, ...]), which is obviously not going to work great when copying data between different programs. But I think I have a scheme worked out that allows using content-addressed hashes instead, that guarantees (up to cryptographic hash collision) that functions with the same type have the same code, while also preserving lazy compilation/imports/tree-shaking.
printing
All of the features above were in service of being able to write a generic print function in the runtime, where all the reflection is staged away at compile-time. Behold it in all of it's work-in-progress glory:
print = (x) {
if %only(%repr-of(x) == u32) {
%print(x)
%print('/u32')
} else if %only(%repr-of(x) == i64) {
%print(x)
} else if %only(%repr-of(x) == string) {
%print('\'')
// TODO escape
%print(x)
%print('\'')
} else if %only(%repr-of(x) == any) {
// TODO Need to be able to jump back into interpreter for unknown types.
%print('TODO/any')
} else {
unmade = %only(%unmake(%repr-of(x)))
head = %only(%from-only(unmade).0)
args = %only(%from-only(unmade).1)
if %only(%from-only(head) == struct) {
%print('[')
positional mut = 1
%each(x, (ix, key, value) {
if %only(%from-only(ix) > 0) %print(', ')
if %only(%from-only(key) != %from-only(ix)) { positional@ = 0 }
if {positional == 0} {
print-key(%from-only(key))
%print(': ')
}
print(value)
})
%print(']')
} else if %only(%from-only(head) == union) {
%print('[')
%each(x, (ix, key, value) {
if %only(%from-only(key) != 0) {
print-key(%from-only(key))
%print(': ')
}
print(value)
})
%print(']/')
print-repr(%only(%repr-of(x)))
} else if %only(%from-only(head) == list) {
%print('[TODO]/')
print-repr(%only(%repr-of(x)))
} else if %only(%from-only(head) == fun) {
print(%closure(x))
%print('/')
print-repr(%only(%repr-of(x)))
} else if %only(%from-only(head) == namespace) {
print(%closure(x))
%print('/')
print-repr(%only(%repr-of(x)))
} else if %only(%from-only(head) == only) {
%print('%only(')
print(%from-only(x))
%print(')')
} else {
%print('TODO/')
print-repr(%only(%repr-of(x)))
}
}
}
print-repr = (x) {
if %only(%from-only(x) == u32) {
%print('u32')
} else if %only(%from-only(x) == i64) {
%print('i64')
} else if %only(%from-only(x) == string) {
%print('string')
} else if %only(%from-only(x) == any) {
%print('any')
} else if %only(%from-only(x) == repr) {
%print('repr')
} else if %only(%repr-of(x) == repr-kind) {
print-repr-kind(%only(x))
} else {
unmade = %only(%unmake(%from-only(x)))
head = %only(%from-only(unmade).0)
args = %only(%from-only(unmade).1)
print-repr-kind(head)
%print('[')
positional mut = 1
%each(args, (ix, key, value) {
if %only(%from-only(ix) > 0) %print(', ')
if %only(%from-only(key) != %from-only(ix)) { positional@ = 0 }
if {positional == 0} {
print-key(%from-only(key))
%print(': ')
}
if %only(%repr-of(%from-only(value)) == repr) {
print-repr(value)
} else {
print(%from-only(value))
}
})
%print(']')
}
}
print-repr-kind = (x) {
if %only(%from-only(x) == struct) {
%print('struct')
} else if %only(%from-only(x) == union) {
%print('union')
} else if %only(%from-only(x) == list) {
%print('list')
} else if %only(%from-only(x) == fun) {
%print('fun')
} else if %only(%from-only(x) == namespace) {
%print('namespace')
} else if %only(%from-only(x) == only) {
%print('only')
} else {
panic('Unreachable')
}
}
print-key = (key) {
// TODO If key is a valid name then omit the quotes.
print(key)
}
Everything boils down to %print, which is a builtin function that can only print strings and integers. It's injected into the compiled wasm by the javascript host:
let wasmInstance;
try {
wasmInstance = new WebAssembly.Instance(wasmModule, {
env: {
print_u32: function (u32) {
var enc = new TextEncoder();
writeAllSync(Deno.stdout, enc.encode(u32.toString()));
},
print_i64: function (i64) {
var enc = new TextEncoder();
writeAllSync(Deno.stdout, enc.encode(i64.toString()));
},
print_string: function (ptr, len) {
let str = new Uint8Array(memory.buffer, ptr, len);
writeAllSync(Deno.stdout, str);
},
},
});
} catch (error) {
console.error(error);
}
If we call print(42), all the reflection and staging compiles away and the remaining code is just:
(import "env" "print_string" (func (;2;) (type 3)))
(func (;6;) (type 2) (param i64)
(call 1
(local.get 0)))
Now that I have printing working in compiled code I can finally write tests that return non-integer values. It's starting to feel like an actual language!
next
Everything has been building towards printing for a while. Now that it's done I haven't decided yet what to work on next. But there are some obvious candidates.
next = staging?
I wasn't sure how I wanted the developer experience of staging to feel, so for now I left it all manually annotated (%only and %from-only).
I also wanted to make sure that it fit smoothly into type inference rather than being a separate, parallel system (like rust's many type systems). So I implemented staging in terms of first-class values. %only(1 + 1) returns a value of type only[2], a type which is only inhabited by the value 2 and whose runtime representation is zero-sized.
For mutable references I took the same approach. References are created with @ and have type ref[T]. But you can never write code that observes these types, because during desugaring I automatically insert %from-ref around any expression that doesn't use the value mutably. We know at desugaring time which variables are refs because they have to be annotated with mut or ref (depending on whether you are creating a new mutable location or assigning a new name to an existing location).
Having written some amount of staged code now, I think the exact same pattern would work for only. Variables that are known at compile-time would have to be annotated with only (or const or # or whatever, I haven't thought of a satisfying name/syntax yet). Expressions wrapped in only{...} would be evaluated at compile-time. Whenever an expression of type only is used in a non-only context, we would wrap it in %from-only during desugaring. Except in function calls, where foo(only{...}) would pass the staged value to foo where it would either be used or unwrapped depending on how the parameters of foo are annotated (foo = (x only) ... vs foo = (x) ...).
It's always reassuring to see that same patterns come up for different subsystems.
A nice side-effect of this is that iterators can offer staged values and callees can decide whether they want to use them. Eg in %each(thing, (i, k only, v) ...) if thing is a big struct with type [a: string, b: string, c: string, etc...] then we'll we get specializations for the callee [i: i64, k: only[a], v: string], [i: i64, k: only[b], v: string], [i: i64, k: only[c], v: string] etc. But if we don't need the key to be a staged value then we can instead write %each(thing, (i, k, v) ...) and just get the one specialization [i: i64, k: string, v: string].
One open question is whether I want to allow writing functions that behave differently depending on whether or not their arguments are staged? For example, for the builtin %each(thing, (i, k, v) ...), if thing is a struct then v is a regular value, but if thing is a staged struct then v is a staged value. Maybe programmers will want to have the ability to write functions like that themselves. We could do this by adding an annotation only? that doesn't unwrap staged values, but also doesn't required them. But it's not clear how we'd then write the body of the function. Do we write only?{...} in the body to indicate evaluating at compile-time if possible? Or do we have to write two different versions of the body? Needs some real examples to work with...
next = allocation?
At the moment there is no way to allocate new heap values in zest. (The only list values are ones that are baked into the executable during compile-time evaluation.)
I have an allocator in the runtime, and unsafe %load and %store primitives to touch memory. So I can build up lists and maps etc.
But I haven't figured out the rules for reference-counting yet.
I know that I don't want to increment refcounts on every use of a variable - that's expensive. But I also want the costs to be easily understandable from just looking at the code, which is in tension with the fancy schemes in languages like in koka or lean.
Also, unlike koka and lean, I have mutable references. I guarantee that anything pointed to by a mutable reference has refcount 1, so I need to be careful that maintaining that guarantee doesn't lead to surprising expenses.
I have an intuition that below is a reasonable set of rules, but I haven't put any effort into disproving it yet:
-
- Whenever copying a value from a immutable location higher on the stack to an immutable location lower on the stack, 'lend' the value (shallow copy).
-
- Whenever copying a value otherwise, 'share' the value (shallow copy and increment refcounts for all pointers).
- 3a) Whenever obtaining a mutable reference to the interior of a reference-counted value (eg
ref = value[i]@), 'steal' the value first (if the refcount of the heap allocation is >1 then copy the heap allocation). - 3b) Whenever assigning a value to a mutable reference (eg
ref@ = value), 'steal' the value first (if the refcount of the heap allocation is >1 then copy the heap allocation).
Rule 1 is important because it avoids the accidental copies of big structs that are a constant source of performance drag in zig and go.
I think that either 3a or 3b are sufficient to maintain the aliasing rules. But neither is optimal. Consider list[i]@ = elem. If elem is a non-reference-counted type (eg i64) then 3a has to do a refcount check whereas 3b has no overhead. But if elem is a reference-counted type (eg string) then 3b makes a copy of the string even if we never want to mutate it whereas 3a allows sharing the string.
Swift has some optimizations around 3a eg it will hoist the check out of a loop so it only happens once. But this is a) potentially fragile/non-obvious and b) doesn't pair well with internal iterators (ie where the loop body is in a different function).
Another complication is that I have equivalents of zigs PRO (pass function arguments by reference rather than by value) and RLS (in x = foo() pass a pointer to x as an argument to foo and write directly to it). (In zig the combination of the two is dangerous, but in zest I have alias tracking so I can statically prevent dangerous combinations.) This means that in function calls, I don't even want a shallow copy but instead just a pointer.
Existentialize Your Generics
Java-style generic erasure requires universal layouts, which causes a lot of indirection and memory overhead. Rust-style monomorphization allows type-specific layouts, but generates a lot of code, requires knowing all possible combinations of types at runtime, and cannot provide separate compilation.
Swift (at abi boundaries) use dictionary passing. This preserves separate compilaton without requiring universal layout. The paper has the tiniest possible evaluation of the performance cost vs monomorphization. It doesn't really feel informative.
A Lightweight Type-and-Effect System for Invalidation Safety
They've developed a type system which can express (and infer) union/intersection/negation types. By adding effects, they can use negations to express carveouts in generic effects like 'this function may perform any effect except IO'. By adding unique nominal types to each variable and adding those types to the effects of expressions that use those variables, they can express invalidation - 'this function may perform any effect except using the variable x'. Any value that leaves a variables scope gets upcast to a type that doesn't include the variable effect - this can be used to prevent stack-allocated values escaping.
The result is they get a lot of the benefits of a rust-like borrowing system, but they built it out of type system features they were already using elsewhere. I'm not fluent enough in type systems to be able to figure out if there are rough corners that they're not mentioning, but I am a sucker for parsimony of concepts.
Do we understand SQL?
I just can't resist. Even more weird inconsistencies that I haven't thought of before.
ZJIT: Building a New JIT Compiler for Ruby
This mostly isn't new information if you've been following zjit, but I was surprised that part of the motivation for zjit vs yjit was that compiling per method rather than per basic block means storing way less metadata, which means that your metadata isn't under so much pressure to be minimal/lossy.
books
Dirtbag: Essays. I thought it would be an insight into the Bernie Sanders campaign. Instead it's 90% complaining about random people she worked with in the past and 10% celebrating her favorite twitter dunks.
Rethinking Positive Thinking: Inside the New Science of Motivation. Scientists once did an experiment and you too can over-generalize from this blah blah blah...
The Path of Aliveness: A Contemporary Zen Approach to Awakening Body and Mind. I really wanted to finish reading this but it's all
Water stands for emptiness. Conceptually, emptiness means activity, interdependence, and nonself. Each observable thing is the temporary manifestation of an undivided activity and not a self-same entity separate from other self-same entities. Conventionally we can speak of things, but ultimately they do not exist in the way our convention suggests. And our own self is no exception. Whatever I determine about myself in this moment may seem real and relevant, but it is only so in an ungraspable wave-like fashion.
and there are only so many hours that I can spend being beaten over the head with the revelation that we don't have direct access to reality and that categories are an approximation before I start to wonder if the book has literally any other point to make.