Exploring biphasic programming: a new approach in language design
rybicki.io
rybicki.io
https://en.wikipedia.org/wiki/Multi-stage_programming
https://okmij.org/ftp/meta-programming/index.html
Comment from 2019 about it, which mentions Zig, Terra/Lua, Scala LMS, etc.:
https://news.ycombinator.com/item?id=19013437
We should also mention big data frameworks and ML frameworks like TensorFlow / Pytorch.
The "eager mode" that Chris Lattner wanted in Swift for ML and Mojo is to actually to get rid of the separation between the stage of creating a graph of operators (in Python, serially) and then evaluating the graph (on GPUs, in parallel).
And also CMake/Make and even autoconf/make and Bazel have stages -- "programming" a graph, and then executing it in parallel:
Language Design: Staged Execution Models - https://www.oilshell.org/blog/2021/04/build-ci-comments.html...
It's used by some of the pytorch back ends.
https://github.com/herumi/xbyak
Example use: https://github.com/oneapi-src/oneDNN/blob/main/src/cpu/aarch...
I learned about these through a blog post about speeding up pytorch on ARM: https://pytorch.org/blog/optimized-pytorch-w-graviton/
> And compared to Lisps like Scheme and Racket which support hygenic macros, well, Zig doesn’t require everything to be a list.
This comment is a bit ignorant. Racket has the most advanced staging system of any language that I'm aware of. You can build languages in Racket with conventional yet extensible syntax: https://docs.racket-lang.org/rhombus/index.html Zig's metaprogramming facilities are very simple in comparison.
I think staging could be extremely useful in many application, and I wish it was better supported in mainstream langauges.
They work differently, is the main thing. Racket's #lang extensions are very sophisticated indeed, but/and they do what Lisp-style compile-time evaluation has always done: they build up lists which represent the program, what we'd call an AST in most other languages. Yes, I'm well aware that Racket has more data structures than lists! But that is the output of front ends like Rhombus. Some of those lists represent a program which creates a hash map and so on. That's fine.
Zig comptime is part of the compiling process. Sometimes this mutates the AST or IR, often it does not, instead producing object code or .rodata which is embedded into the final binary. The current implementation is a bit ad-hoc, with some arbitrary limitations (no allocation being the big one), but it's a solid design. Already quite useful, even eloquent, and I'm optimistic that the final form will be a real thing of beauty.
But it isn't accurate to say that it's 'very simple' in comparison to Racket. They spend their complexity budget in different places.
1. If you are claiming that "compile-time evaluation" (macros) in Racket works with lists (i.e. the input to a macro is a list, and the output from a macro is a list), that is false. It works with syntax objects: https://docs.racket-lang.org/guide/stx-obj.html
2. A macro can do anything. It usually emits syntax, but because it's just code it can print output, play a jaunty tune, or implement type checking.
It seems to me that Racket's macros are strictly a super-set of Zig's comptime. Like comptime a macro can do arbitrary computation. However AFAIK there only two stages in Zig (compile-time and run-time) while Racket has an arbitrary number of stages, and macros can, of course, implement new syntactic forms.
This is a distinction without a difference. From your quote:
> A syntax object contains symbols, lists, and constant values (such as numbers) that essentially correspond to the quoted form of the expression.
If it's important to you that it's actually atoms and lists, well, some of us generalize better than others. But calling it false? Lame. As is your feigned confusion.
> A macro can do anything
Syntax and side effects. Take your pick.
> It seems to me that Racket's macros are strictly a super-set of Zig's comptime.
The difference here is that you have experience with one of these systems. I have experience with both. I doubt further interactions would be informative for either of us.
My confusion is real. I don't get your point. How does "they do what Lisp-style compile-time evaluation has always done: they build up lists" delineate Racket's capabilities compared to Zig? It's false on the surface (syntax objects are not lists) and it's false at a deeper level (macros can do anything). Even if it were true, I don't understand the significance of using lists, or not, as a representation of a program. I know, from experience, you can put any value into a syntax object / list so ¯\_(ツ)_/¯
I don't understand what "Zig comptime is part of the compiling process" means in contrast to Racket. How does this differentiate between the two? Macros provide an API to the compiler, are part of the compiling process, and you can insert, e.g, assembly code generated by a macro into a Racket program (I did this a long time ago).
> Syntax and side effects. Take your pick.
What does this mean? "Take your pick" implies xor, but you use and. Is this a typo?
If you doubt that macros can do arbitrary side-effects, put the following in a file (e.g. "comptime.rkt") and from Racket call (require "comptime.rkt")
#lang racket
(define-syntax when (lambda (stx) (begin (println "Compile-time") (datum->syntax stx '(println "b")))))
(begin (println "a") (when) (println "c"))
You'll see the output
"Compile-time" "a" "b" "c"
The println in the macro when runs before the code in the begin form evaluates. I.e. it is running at compile-time.
You've made that clear, yes.
* dynamic typing vs static typing, a continuum that JIT-ing and compiling attack from either end -- in some sense dynamically typed programs are ALSO statically typed -- with all function types are being dependent function types and all value types being sum types. After all, a term of a dependent sum, a dependent pair, is just a boxed value.
* monomorphisation vs polymorphism-via-vtables/interfaces/protocols, which trade roughly speaking instruction cache density for data cache density
* RC vs GC vs heap allocation via compiler-assisted proof of memory ownership relationships of how this is supposed to happen
* privileging the stack and instruction pointer rather than making this kind of transient program state a first-class data structure like any other, to enable implementing your own co-routines and whatever else. an analogous situation: Zig deciding that memory allocation should NOT be so privileged as to be an "invisible facility" one assumes is global.
* privileging pointers themselves as a global type constructor rather than as typeclasses. we could have pointer-using functions that transparently monomorphize in more efficient ways when you happen to know how many items you need and how they can be accessed, owned, allocated, and de-allocated. global heap pointers waste so much space.
Instead, one would have code for which it makes more or less sense to spend time optimizing in ways that privilege memory usage, execution efficiency, instruction density, clarity of denotational semantics, etc, etc, etc.
Currently, we have these weird siloed ways of doing certain kinds of privileging in certain languages with rather arbitrary boundaries for how far you can go. I hope one day we have languages that just dissolve all of this decision making and engineering into universal facilities in which the language can be anything you need it to be -- it's just a neutral substrate for expressing computation and how you want to produce machine artifacts that can be run in various ways.
Presumably a future language like this, if it ever exists, would descend from one of today's proof assistants.
This was done in the 60s/70s with FORTH and LISP to some degree, with the former being closer to what you're referring to. FORTH programs are typically images of partial applications state that can be thought of as a pile of expanded macros and defined values/constants (though there's virtually no guardrails).
That being said, I largely agree with you on several of these and think would like to take it one step further: I would like a language with 99% bounded execution time and memory usage. The last 1% is to allow for daemon-like processes that handle external events in an "endless" loop and that's it. I don't really care how restricted the language is to achieve that, I'm confident the ergonomics can be made to be pleasant to work with.
They have this concept of codata for the other 1% to make practical, interactive apps - codata represents things like event streams.
Around 2000, Chuck Moore dissolved compile-time, run-time and edit-time with ColorForth, and inverted syntax highlighting in the process (programmer uses colors to indicate function).
I don't think this is actually desireable. This is what Smalltalk did, and the problem is it's very hard to understand what a program does when any part of it can change at any time. This is problem for both compilers and programmers.
It's better, IMO, to be able to explicitly state the stages of the program, rather than have two (compile-time and run-time) or one (interpreted languages). As a simple example, I want to be able to say "the configuration loads before the main program runs", so that the configuration values can be inlined into the main program as they are constant at that point.
I don't think dissolving this difference necessarily results in Smalltalk-like problems. Any kind of principled dissolution of this boundary must ensure the soundness of the static type system, otherwise they're not really static types, so the dynamic part should not violate type guarantees. It could look something like "Type Systems as Macros":
You can write useful programs in Agda. I wrote all kinds of programs in Agda including parsers and compilers.
No it isn't; nobody wants that. Or not all the time.
We'd like to use the same language at compile time and run-time.
But it's useful for compile time to happen here, on our build system, and run-time on the customer's system.
We don't want those to be the same system, or at least not in production with the actual customer.
// Import some libraries.
bring s3;
// Bring some libraries.
?MIT AI Memo 57, Timothy P. Hart, MACRO Definitions for LISP, October 1963
http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/ai/aim/...
Lisp languages tend to blend together "runtime" with "load time", and in case of compiled languages, also "compile time". You can write code executing during any one, or any combination of, these phases. You can reuse code between those phases. You can interleave them at will - e.g. by loading more code at runtime, or invoking a compiler, etc.
I think normal forth words are way closer to that. They (1) normally just do whatever their definition implies, but inside a colon definition, they (1) compile code that does whatever their definition implies.
They do miss C++ constexpr (https://en.cppreference.com/w/cpp/language/constexpr). I haven’t read Zig docs, but that seems highly similar to Zig’s comptime to me.
(1) technically, it’s not “they” doing that themselves but whatever code processes them.
but also you can just put the code you would have put between the [ ] delimiter words into an immediate word, and call it where you would have put the [ ] block. the effect is not exactly the same but it has semantics slightly more consistent with the usual semantics because your immediate word is in fact compiled just like non-immediate words are
What I recently realized is that while compilers in the standard perspective process a language into an AST, do some transformations, and then output some kind of executable, from another perspective they are really no different than interpreters for a DSL.
There tends to be this big divide between what we call a compiler and what we call an interpreter. And we classify languages as being either interpreted or compiled.
But what I realized, as I'm sure many others have before me, is that that distinction is very thin.
What I mean is this: from a certain perspective a compiler is really just an interpreter for the meta language that encodes and hosts the compiled language. The meta-language directs the compiler, generally via statements, to synthesize blocks of code, create classes with particular shapes, and eventually write out certain files. These meta-languages don't support functions, or control flow, or variables, in fact they are entirely declarative languages. And yet they are the same as the normal language being compiled.
To a certain degree I think the biphasic model captures this distinction well. Our execution/compilation models for languages don't tend to capture and differentiate interpreter+script from os+compiled-binary very well. Or where they do they tend to make metaprogramming very difficult. I think finding a way to unify those notions will help languages if and when they add support for metaprogramming.
Even hardware is, at some point, "programmed" by someone to behave a certain way.
https://docs.raku.org/language/phasers
It has many more than 2 phases.
Phasers is one of the ideas Raku takes as pretty core and really runs with it. So in addition to compile time programming, it has phasers for run time events like catching exceptions and one that's equivalent to the defer keyboard in several languages.
The block inside of a class or module definition is executed first, and then the application can work on the resulting structure generated after that pass. Sorbet (a Ruby static typing library) uses this first-pass to generate its type metadata, without running application code. (I think by stubbing the class and module classes themselves?)
- Documentation generated from inline code comments (Knuth's literate programming)
- Test code
We could expand to
- security (beyond perl taint)
- O(n) runtime and memory analysis
- parallelism or clustering
- latency budgets
And for those academically inclined, formal language semantics like https://en.wikipedia.org/wiki/Denotational_semantics versus operational and others..
Very excited for multi-stage - especially it's potential to provide very good LSP/diagnostics for library users (and authors). It's hard to provide good error messages from libraries for static errors that are hard to represent in the type system, so sometimes a library user sees vague/unrelated errors.
[1] https://github.com/gsuuon/kita/blob/d741c0519914369da9c89241...
it's interesting to read this biphasic programming article in the context of pg's tendentious reading of programming language history
> Over time, the default language, embodied in a succession of popular languages, has gradually evolved toward Lisp. 1-5 are now widespread. 6 is starting to appear in the mainstream. Python has a form of 7, though there doesn't seem to be any syntax for it. 8, which (with 9) is what makes Lisp macros possible, is so far still unique to Lisp, perhaps because (a) it requires those parens, or something just as bad, and (b) if you add that final increment of power, you can no longer claim to have invented a new language, but only to have designed a new dialect of Lisp ; -)
it of course isn't absolutely unique to lisp; forth also has it
i think the academic concept of 'staged programming' https://scholar.google.com/scholar?cites=2747410401001453059... is a generalization of this, and partial evaluation is a very general way to blur the lines between compile time and run time
Can we have:
oof dup rot swap foo
Word definitions do something like this. There is a : (colon) word which causes the next word to be interpreted as a name for a new definition and then subsequent words until a semicolon are shored up into the definition. But that's a fixed thing, built into the language. It's not defined in the Forth standard as a symbolic quoting mechanism.
Similarly, Freeforth (anonymous definitions) and Able Forth (same) can do this. You also have aliasing and hooks in the languages as other tools.
The way Rebol and derivatives (Red, Rye) treat blocks and dialects [myword yourword] executedword is similar, though they are all interpreted, not compiled.
retroforth quotes are just anonymous definitions, and the words inside of them have the same meaning they would have in any other definition. as far as i can tell, you can't even index into them or query their length the way you can with {executable arrays} in postscript. i think the same is true of anonymous definitions in freeforth and able forth
ansi standard forth has :noname https://forth-standard.org/standard/core/ColonNONAME which is the same thing as retroforth quotes, except that it doesn't nest within other definitions, so you can't use it to define properly nesting control structures, the way retroforth does
but kaz was asking if it's possible to construct a context that gives the words inside it a completely different meaning, so that you can interpret dup, rot, and swap in a way that is unrelated to duplicating, rotating and swapping stack elements. this is in fact possible in ansi forth and in most other forths (my comment sibling to yours explains how), although i don't know if it's possible in the forths you've mentioned
you can do this by having oof parse words from the input stream until it parses foo, and all the facilities for doing that are included in the ansi standard (i.e., it doesn't require knowledge of theoretically private implementation details of a given forth). there aren't any standard words that work this way, although, as you're probably aware, \ " .( ( char [char] c" s" and ." do consume data from the input stream in various ways (but without parsing it into words), and in particular ' ['] create value variable constant marker parse-name to defer is and postpone all read a single word from the input and do various things with it
i'm no forth expert but i think you can define your desired oof as follows in ans forth:
: roof begin parse-name \ read oof
2dup s" foo" compare 0= if 2drop exit then spoof again ;
: oof immediate goof roof proof ;
create boof 256 allot 0 value poof \ buffer and pointer for oof
: proof boof poof type ; : goof 0 to poof ; \ print oof, gone oof
: spoof >r poof boof + r@ move r> poof + to poof ; \ string put for poof
i can't swear that this is ansi-compliant forth but i did test it in gforth and pfe. i also tried testing it in yforth and jonesforth but couldn't get them to run on this amd64 linux
the one debatable thing here is that you said 'symbols', but spoof's arguments are just a string pointer and a length, probably in some kind of input buffer. forth doesn't natively have symbols in the lisp sense, but it does have something very similar, which is a dictionary of words. spoof can look up a word in the dictionary in the same way ' or ['] would, by using the word find†, which returns a pointer to the word's dictionary entry (a so-called 'execution token')
this may sound suspiciously like symbol interning in lisp, and if the naming of ' in forth isn't inspired by the lisp readmacro of the same name, it's at least a damned suspicious coincidence. but the semantics are different from interning in an important way, which is why i didn't use find in my definition of roof above: if the word you're searching for hasn't been defined, find doesn't add it to the dictionary. for dup, rot, and swap, you'd be fine, but if you stuck a bar or a quux in there, find would return 0 (and the original string). also, in forth, you can have more than one word with the same spelling, and find will only find the latest one that's still in scope, which is a different behavior from lisp symbols
if you want the lisp symbol behavior, you'd have to define your own obarray and intern, which is not too hard
______
† the standard word find wants a counted string, and that's enough hassle that many implementations like gforth provide a find-name which takes a string in the format provided by parse-name instead, and define find in terms of find-name. but find-name isn't in the ans standard, and you can define it in terms of find if you have to
constexpr does not mean that you can evaluate arbitrary C++ code at compile time. It allows you to evaluate a _very specific subset_ of C++ at compile time that is not at all easy to wrap your head around: look no further than https://en.cppreference.com/w/cpp/language/constexpr to understand the limitations.
The Metamine language allowed for a magic equals := if I recall correctly, which had the effect of always updating the result anytime the assigned value changed for the rest of the life of the program. Mixing it with normal assignments and code made for some interesting capabilities.
[0] https://guix.gnu.org/manual/en/html_node/G_002dExpressions.h... [1] https://guix.gnu.org/manual/en/html_node/Build-Phases.html#i... [2] https://guix.gnu.org/manual/en/html_node/Shepherd-Services.h...
The implementation shall be JIT compiled with a separate linter running in the editor for that is the right thing.
We aren't there yet but I believe it's where we'll end up.
I think the actual problem is the glacial pace of applying it, and the lack of support in trait impls (e.g. i32.min) and syntax. If it were applied to every pure fn+syntax it would probably cover a great deal of what Zig is doing.
> characterized by languages and frameworks that enable identical syntax to express computations executed in two distinct phases or environments while maintaining consistent behavior (i.e., semantics) across phases
Munging together strings into something which is hopefully source code is the ultimate escape valve for languages which have poor or nonexistent facilities for biphasic programming. You compile a program, it executes, it spits out a program, you compile that and run it. That isn't biphasic: it's one phase, twice.
Multi-stage programming and distribution with the same syntax between clients and servers has been _the_ key feature of Opa (opalang.org) 15 years back. Funny because Opa was a key inspiration for React and its JSX syntax but it took a lot of time to match the rest of the features.
Often you don't actually want some things done at compile time although they could be done. It can lead to, e.g., excessive executable sizes, excessive compile times. If you've ever considered using `-ftemplate-depth` in C++, you've probably encountered such a case.
Maybe it sounds like I'm splitting hairs and you would say "of course in such crazy cases it's not true", but if you look at C++ projects and what can be done at compile time with modern C++, you would find it's not rare at all.
I once worked on an Elixir application whose configuration was accessed almost exclusively at compile time. This was done with the well-intended notion that saving runtime cycles was a good thing. It meant that changing any config (e.g.: "name of s3 bucket") meant recompiling the entire application. It also meant we had to wait for a full application rebuild in CI to deploy fixes for simple configuration errors. Not so super.
So Zig actually does what you seem to think it should do (and I agree! it's great!): if something can be calculated at compile time, it is. Only when the compiler can't statically deduce a compile-time construct is it necessary to use the `comptime` keyword: in fact, it's an error to use the keyword when the context is already comptime.
I've been rendering the same React components on the server and browser side for close to decade and I've come across some really good patterns that I don't really see anywhere else.
Here's the architectural pattern that I use for my own personal projects. For fun I've starting writing it in F# and using Fable to compile to JS:
A foundational element is a port of express to the browser, aptly named browser express:
https://github.com/williamcotton/browser-express
With this you write not only biphasic UI components but also route handlers. In my opinion and through lots of experience with other React frameworks this is far superior to approaches taken by the mainstream frameworks and even how the React developers expect their tool to be used. One great side effect is that the site works the same with Javascript enabled. This also means the time to interaction is immediate.
It keeps a focus on the request itself with a mock HTTP request created from click and form post events in the browser. It properly architects around middleware that processes an incoming request and outgoing response, with parallel middleware for either the browser or server runtime. It uses web and browser native concepts like links and forms to handle user input instead of doubling the state handling of the browser with controlled forms in React. I can't help but notice that React is starting to move away from controlled forms. They have finally realized that this design was a mistake.
Because the code is written in this biphasic manner and the runtime context is injected it avoids any sort of conditionals around browser or server runtime. In my opinion it is a leaky abstraction to mark a file as "use client" or "use server".
Anyways, I enjoyed the article and I plan on using this term in practice!
Linq. Have a a set of collection manipulation methods that could be run in c# or transformed in SQL.
Blazor. Have components that can run on the server, or in the browser, or several other rendering tactics.
Suggesting that the macros of C and Rust may be the same is an insane failure.
BTW: meta-programming means "code which generates code" and not "code which runs earlier than other code".