Zest: dialects and metaprogramming

Published 2024-02-28

(This is part of a series on the design of a language. See the list of posts here.)

I now have much of the core language sketched out and (poorly) implemented, including mutable value semantics, control-flow-capturing closures and a tentative solution for error-handling, but I'll cover those another day. Today I want to talk about the three dialects I'm planning:

zest-lax vs zest-strict

The design of meta-programming in zest takes a lot of inspiration from terra, julia and zig.

Terra is a c-like language that is embedded in lua. Compare to c and other systems, terra is barely a language. No type constructors, no module system, no macros/preprocessor. But within terra programs you can evaluate lua expressions at compile-time, and this totally replaces all of those features. Instead of type constructors you can call lua functions that return types. Instead of modules you build up lua tables containing terra functions. Instead of preprocessor ifdefs you call lua functions that return information about the build environment.

Zig takes this further by using (more or less) the same language for regualar programs and meta-programs. Regular zig is statically typed, uses manual memory management and has no first-class types. Comptime zig is dynamically typed, garbage-collected and has first-class types, but can't convert between integers and pointers (to preserve deterministic compilation). Otherwise the two dialects are very similar and most zig code will work in both dialects without modifications.

Both terra and zig defer type-checking until after specialization. This is a trade-off I've become fond of. It means we only ever deal with concrete types, the type-checker doesn't require unification, we can type-check function bodies with a single forward pass, and meta-programming can be expressed in the same(ish) language rather than requiring a separate logic language. The major downside is that we can't actually type-check generic functions, only specific uses of those functions.

Julia takes a slightly different tack. There is only a single dynamically typed language with first-class types attached to values. But functions are jit-specialized to the types of their arguments, at which point type inference and constant propagation is able to remove most dynamism. Effectively there is a statically-typed language hiding inside julia, but the programmer has little explicit access to that language and the boundary between the static and dynamic dialects is very porous.

The upside of the julia approach is that it's transparent. You can understand a program without knowing that the statically-typed dialect exists - it completely preserves the semantics of the dynamic language (except for a tiny corner-case - the dynamic type of an unannotated list comprehension depends on static type inference).

The downside of the julia approach is that it's unreliable. It can often be difficult to figure out whether a given function will produce efficient static code or whether type-inference will bail out and leave mess of dynamic dispatch and heap allocations. There's an ever-growing collection of tools to analyze julia code to detect such problems in critical code, but they are limited by not being able to cross the jit boundary whenever type inference fails.

So I want the best of both worlds.

The type system for zest-strict is a simple abstract interpretation of the reprs in zest-lax. This ensures that all the behaviour lives in the dynamic semantics and never depends on the results on type inference - any program that runs in zest-strict will produce the same result in zest-lax. But the type-system guarantees that a program that type-checks in zest-strict will never fail a type-asssertion.

Zest-lax can construct and call zest-strict functions, but zest-strict can only call zest-lax functions at compile-time for meta-programming. This ensures that zest-strict code is amenable to static analysis, won't feature any surprise runtime compilation, and can produce small binaries.


In my prototype compiler I found it really painful having the runtime written in a separate language.

Being able to just use zig structs and unions made it really easy to write operations on values, but then I had to either ensure the compiler emitted code with the same layout as zig, or route all operations through pre-compiled runtime functions. This is going to become increasingly painful once specialization comes into play - I don't want to end up going down the v8 route of specializing a large number of runtime functions inside the jit.

Linking the zig runtime and the compiler's wasm output was also pretty gross. I could probably hack together a better linking process, but I can't get around being tied to LLVM's calling conventions.

So the idea of zest-kernel is that it's a subset of zest that doesn't require a runtime, but is sufficient to write one. I'll implement allocation, refcount, strings, arraylists, hashmaps and reflection in zest-kernel. Then both zest-lax and zest-strict will lower to zest-kernel and get compiled together with the runtime in a single compilation unit. Specialization will extend all the way into the runtime to the arraylist and hashmap implementations so I won't have to special-case them in the compiler.

In the long run I'm aiming for a fully bootstrapped implementation, with both compiler and language runtime written in zest and only requiring a WASI runtime.