It’s even worse: not just “one of the top language engineers in the world” but specifically architect of both the language being ported and architect of the language they’re saying it should be ported to.
The fucking presumption, the unmitigated arrogance of some people, woof.
The TypeScript dev lead posted this response about the language choice on Reddit, for anyone who’s curious:
(dev lead of TypeScript here, hi!)
We definitely knew when choosing Go that there were going to be people questioning why we didn’t choose Rust. It’s a good question because Rust is an excellent language, and barring other constraints, is a strong first choice when writing new native code.
Portability (i.e. the ability to make a new codebase that is algorithmically similar to the current one) was always a key constraint here as we thought about how to do this. We tried tons of approaches to get to a representation that would have made that port approach tractable in Rust, but all of them either had unacceptable trade-offs (perf, ergonomics, etc.) or devolved in to “write your own GC”-style strategies. Some of them came close, but often required dropping into lots of unsafe code, and there just didn’t seem to be many combinations of primitives in Rust that allow for an ergonomic port of JavaScript code (which is pretty unsurprising when phrased that way - most languages don’t prioritize making it easy to port from JavaScript/TypeScript!).
In the end we had two options - do a complete from-scrach rewrite in Rust, which could take years and yield an incompatible version of TypeScript that no one could actually use, or just do a port in Go and get something usable in a year or so and have something that’s extremely compatible in terms of semantics and extremely competitive in terms of performance.
And it’s not even super clear what the upside of doing that would be (apart from not having to deal with so many “Why didn’t you choose Rust?” questions). We still want a highly-separated API surface to keep our implementation options open, so Go’s interop shortcomings aren’t particularly relevant. Go has excellent code generation and excellent data representation, just like Rust. Go has excellent concurrency primitives, just like Rust. Single-core performance is within the margin of error. And while there might be a few performance wins to be had by using unsafe code in Go, we have gotten excellent performance and memory usage without using any unsafe primitives.
In our opinion, Rust succeeds wildly at its design goals, but “is straightforward to port to Rust from this particular JavaScript codebase” is very rationally not one of its design goals. It’s not one of Go’s either, but in our case given the way we’ve written the code so far, it does turn out to be pretty good at it.
And it’s not even super clear what the upside of doing that would be (apart from not having to deal with so many “Why didn’t you choose Rust?” questions)
People really miss the forest for the trees.
I looked at the repo and the story seems clear to me: 12 people rewrote the TypeScript compiler in 5 months, getting a 10x speed improvement, with immediate portability to many different platforms, while not having written much Go before in their lives (although they are excellent programmers).
This is precisely the reason why Go was invented in the first place. “Why not Rust?” should not be the first thing that comes to mind.
I honestly do think the “Why not Rust?” question is a valid question to pop into someone’s head before reading the explanation for their choice.
First of all, if you’re the kind of nerd who happens to follow the JavaScript/TypeScript dev ecosystem, you will have seen a fair number of projects either written, or rewritten, in Rust recently. Granted, some tools are also being written/rewritten in other languages like Go and Zig. But, the point is that there’s enough mindshare around Rust in the JS/TS world that it’s fair to be curious why they didn’t choose Rust while other projects did. I don’t think we should assume the question is always antagonistic or from the “Rust Evangelism Strike Force”.
Also, it’s a popular opinion that languages with algebraic data types (among other things) are good candidates for parsers and compilers, so languages like OCaml and Rust might naturally rank highly in languages for consideration.
So, I honestly had the same question, initially. However, upon reading Anders’ explanation, I can absolutely see why Go was a good choice. And your analysis of the development metrics is also very relevant and solid support for their choice!
I guess I’m just saying, the Rust fanboys (myself, included) can be obnoxious, but I hope we don’t swing the pendulum too far the other way and assume that it’s never appropriate to bring Rust into a dev conversation (e.g., there really may be projects that should be rewritten in Rust, even if people might start cringing whenever they hear that now).
While tweaking a parser / interpreter a few years ago written in Go, I specifically replaced a struct with an ‘interface {}’ in order to exercise its pseudo-tagged-union mechanisms. Together with using type-switch form.
These day’s I’d actually make it a closed interface such that it is more akin to a tagged-union. Which I did for another project which was passing around instances of variant-structs (i.e. a tagged union), rather than building an AST.
So it is quite possible to use that pattern in Go as a form of sum-type, if for some reason one is inclined to use Go as the implementation language.
A relevant quote is that C# has “some ahead-of-time compilation options available, but they’re not on all platforms and don’t really have a decade or more of hardening.”
Yeah Hjelsberg also talks about value types being necessary, or at least useful, in making language implementations fast
If you want value types and automatically managed memory, I think your only choices are Go, D, Swift, and C# (and very recently OCaml, though I’m not sure if that is fully done).
I guess Hjelsberg is conceding that value types are a bit “second class” in C#? I think I was surprised by the “class” and “struct” split, which seemed limiting, but I’ve never used it. [1]
And that is a lesson learned from the Oils Python -> C++ translation. We don’t have value types, because statically typed Python doesn’t, and that puts a cap on speed. (But we’re faster than bash in many cases, though slower in some too)
Now that I’ve worked on a garbage collector, I see a sweet spot in languages like Go and C# – they have both value types deallocated on the stack and GC. Both Java and Python lack this semantic, so the GCs have to do more work, and the programmer has less control.
There was also a talk that hinted at some GC-like patterns in Zig, and I proposed that TinyGo get “compressed pointers” like Hotspot and v8, and then you would basically have that:
Yeah, I’m kind of curious about whether OCaml was considered at some point (I asked about this in the Reddit thread, haven’t gotten a reply yet).
OCaml seems much more similar to TS than Go, and has a proven track record when it comes to compilers. Maybe portability issues? (Good portability was mentioned as a must-have IIRC)
Not sure what more TypeScript would have needed. In fact, Flow’s JavaScript parser is available as a separate library, so they would have shaved off at least a month from the proof of concept…
Although thinking about it a bit more, I think Nim, Julia, (and maybe Crystal) are like C#, in that they are not as general as Go / D / Swift.
You don’t have a Foo* type as well as a Foo type, i.e. the layout is orthogonal to whether it’s a value or reference. Instead, Nim apparently has value objects and reference objects. I believe C# has “structs” for values and classes for references.
I think Hjelsberg was hinting at this category when saying Go wins a bit on expressiveness, and it’s also “as close to native as you can get with GC”.
I think the reason this Go’s model is uncommon is because it forces the GC to support interior pointers, which is a significant complication (e.g. it is not supported by WASM GC). Go basically has the C memory model, with garbage collection.
I think C#, Julia, and maybe Nim/Crystal do not support interior pointers (interested in corrections)
Someone should write a survey of how GC tracing works with each language :) (Nim’s default is reference counting without cycle collection.)
Yeah that’s interesting. Julia has a distinction between struct (value) and mutable struct (reference). You can use raw pointers but safe interior references (to an element of an array for example) include a normal reference to the (start of the) backing array, and the index.
I can understand how in Rust you can safely have an interior pointer as the borrow checker ensures a reference to an array element is valid for its lifetime (the array can’t be dropped or resized before the reference is dropped). I’m very curious - I would like to understand how Go’s tracing GC works with interior pointers now! (I would read such a survey).
Ok - Go’s GC seems to track a memory span for each object (struct or array), stored in kind of a span tree (interval tree) for easy lookup given some pointer to chase. Makes sense. I wonder if it smart enough to deallocate anything dangling from non-referenced elements of an array / fields of a struct, or just chooses to be conservative (and if so do users end up accidentally creating memory leaks very often)? What’s the performance impact of all of this compared to runtimes requiring non-interior references? The interior pointers themselves will be a performance win, at the expense of using an interval tree during the mark phase.
It’s been a few years since I’ve written any Go, but I have a vague recollection that the difference between something being heap or stack allocated was (sometimes? always?) implicit based on compiler analysis of how you use the value. Is that right? How easy it, generally, to accidentally make something heap-allocated and GC’d?
That’s the only thing that makes me nervous about that as a selling point for performance. I feel like if I’m worried about stack vs heap or scoped vs memory-managed or whatever, I’d probably prefer something like Swift, Rust, or C# (I’m not familiar at all with how D’s optional GC stuff works).
$ go build -gcflags "-m" main.go
.\main.go:8:14: *y escapes to heap
.\main.go:11:13: x does not escape
So the toolchain is pretty transparent. This is actually something I would like for the Oils Python->C++ compiler, since we have many things that are “obviously” locals that end up being heap allocated. And some not so obvious cases. But I think having some simple escape analysis would be great.
Hejlsberg said they got about 3x performance from native compilation and value types, which also halved the memory usage of the compiler. They got a further 3x from shared-memory multithreading. He talked a lot about how neither of those are possible with the JavaScript runtime, which is why it wasn’t possible to make tsc 10x faster while keeping it written in TypeScript.
Yeah but I can get bigger memory wins while staying inside JS by sharing the data structures between many tools that currently hold copies of the same data: the linter, the pretty-formatter, the syntax highlighter, and the type checker
I can do this because I make my syntax tree nodes immutable! TS cannot make their syntax tree nodes immutable (even in JS where it’s possible) because they rely on the node.parent reference. Because their nodes are mutable-but-typed-as-immutable, these nodes can never safely be passed as arguments outside the bounds of the TS ecosystem, a limitation that precludes the kind of cross-tool syntax tree reuse that I see as being the way forward
Hejlsberg said that the TypeScript syntax tree nodes are, in fact, immutable. This was crucial for parallelizing tsgo: it parses all the source files in parallel in the first phase, then typechecks in parallel in the second phase. The parse trees from the first phase are shared by all threads in the second phase. The two phases spread the work across threads differently. He talks about that kind of sharing and threading being impractical in JavaScript.
In fact he talks about tsc being designed around immutable and incrementally updatable data structures right from the start. It was one of the early non-batch compilers, hot on the heels of Roslyn, both being designed to support IDEs.
It’s true that I haven’t watched the interview yet, but I have confirmed with the team that the nodes are not immutable. My context is different than Hejlsberg’s context. For Hejlsberg if something is immutable within the boundaries of TS, it’s immutable. Since I work on JS APIs if something isn’t actually locked down with Object.freeze it isn’t immutable and can’t safely be treated as such. They can’t actually lock their objects down because they don’t actually completely follow the rules of immutability, and the biggest thing they do that you just can’t do with (real, proper) immutable structures is have a node.parent reference.
So they have this kinda-immutable tech, but those guarantees only hold if all the code that ever holds a reference to the node is TS code. That is why all this other infrastructure that could stand to benefit from a shared standard format for frozen nodes can’t: it’s outside the walls of the TS fiefdom, so the nodes are meant to be used as immutable but any JS code (or any-typed code) the trees are ever exposed to would have the potential to ruin them by mutating the supposedly-immutable data
To be more specific about the node.parent reference, if your tree is really truly immutable you need to replace a leaf node you must replace all the nodes on the direct path from the root to that leaf. TS does this, which is good.
The bad part is that then all the nodes you didn’t replace have chains of node.parent references that lead to the old root instead of the new one. Fixing this with immutable nodes would mean replacing every node in the tree, so the only alternative is to mutate node.parent, which means that 1) you can’t actually Object.freeze(node) and 2) you don’t get all the wins of immutability since the old data structure is corrupted by the creation of the new one.
See https://ericlippert.com/2012/06/08/red-green-trees/ for why Roslyn’s key innovation in incremental syntax trees was actually breaking the node.parent reference by splitting into the red and green trees, or as I call them paths and nodes. Nodes are deeply immutable trees and have no parents. Paths are like an address in a particular tree, tracking a node and its parents.
Hm yeah it was a very good talk. My summary of the type checking part is
The input to the type checker is immutable ASTs
That is, parsing is “embarassingly parallel”, and done per file
They currently divide the program into 4 parts (e.g. 100 files turns into 4 groups of 25 files), and they do what I’d call “soft sharding”.
That is, the translation units aren’t completely independent. Type checking isn’t embarassingly parallel. But you can still parallelize it and still get enough speedup – he says ~3x from parallelism, and ~3x from Go’s better single core perf, which gives you ~10x overall.
What wasn’t said:
I guess you have to de-duplicate the type errors? Because some type errors might come twice, since you are duplicating some work
Why the sharding is in 4 parts, and not # CPUs. Even dev machines have 8-16 cores these days, and servers can have 64-128 cores.
I guess this is just because, empirically, you don’t get more than 3x speedup.
That is interesting, but now I think it shows that TypeScript is not designed for parallel type checking. I’m not sure if other compilers do better though, like Rust (?) Apparently rustc uses the Rayon threading library. Though it’s hard to compare, since it also has to generate code
A separate thing I found kinda disappointing from the talk is that TypeScript is literally what the JavaScript code was. There was never a spec and will never be one. They have to do a line-for-line port.
There was somebody who made a lot of noise on the Github issue tracker about this, and it was basically closed “Won’t Fix” because “nobody who understands TypeScript well enough has enough time to work on a spec”. (Don’t have a link right now, but I saw it a few months ago)
Why the sharding is in 4 parts, and not # CPUs. Even dev machines have 8-16 cores these days, and servers can have 64-128 cores.
Pretty sure he said it was an arbitrary choice and they’d explore changing it. The ~10x optimization they’ve gotten so far is enough by itself to keep the project moving. Further optimization is bound to happen later.
I’m not sure if other compilers do better though, like Rust (?) Apparently rustc uses the Rayon threading library.
Work has been going on for years to parallelize rust’s frontend, but it apparently still has some issues, and so isn’t quite ready for prime time just yet, though it’s expected to be ready in the near term.
Under 8 cores and 8 threads, the parallel front end can reduce the clean build (cargo build with -Z threads=8 option) time by about 30% on average. (These crates are from compiler-benchmarks of rustc-perf)
I guess this is just because, empirically, you don’t get more than 3x speedup.
In my experience, once you start to do things “per core” and want to actually get performance out of it, you end up having to pay attention to caches, and get a bit into the weeds. Given just arbitrarily splitting up the work as part of the port has given a 10x speed increase, it’s likely they just didn’t feel like putting in the effort.
But check the chapters, they’re really split into good details. The video is interesting anyway, technically focused, no marketing spam. I can also highly recommend watching it.
Another point on “why Go and not C#” is that, he said, their current (typescript) compiler is highly functional, they use no classes at all. And Go is “just functions and data structures”, where C# has “a lot of classes”. Paraphrasing a little, but that’s roughly what he said.
Acknowledging some weak spots, Go’s in-proc JS interop story is not as good as some of its alternatives. We have upcoming plans to mitigate this, and are committed to offering a performant and ergonomic JS API.
There are some iterator combinators such as count that take an additional Self: Sized bound². But because trait objects are themselves sized, it all mostly works as expected:
This isn’t quite right. Trait objects are not themselves sized. The subsequent code sample works because of the impl<I> Iterator for &mut I where I: Iterator + ?Sizedimplementation. The count method isn’t being directly invoked on the trait object, it’s being invoked on the &mut which is a concrete iterator implementation.
You can prove this yourself by making your own custom Iterator implementation that provides a custom implementation of the count() method, and then invoking it via a &mut dyn Iterator (Rust Playground). If you do that, your custom count() won’t be called, the default implementation on the &mut I instead will be used.
The count method isn’t being directly invoked on the trait object, it’s being invoked on the &mut which is a concrete iterator implementation
Is this considered a bug? I understand how and why works, but the code in your playground link is really counter-intuitive, it’s clearly a footgun. I wonder if this could be fixed?
I can’t quite follow this post.. How exactly are you getting the data from Dexcom? You mention HTTPS, so I’m guessing you get it from the Dexcom web services?
I do the same in my Garmin Watchface but I’m not happy with it, because it requires (1) the phone to be near you (2) the phone to have internet access. So I don’t see the data when flying, or out exercising without the phone.
It also adds about 30 seconds of delay between the phone receiving the data and the watch.
xDrip+ can act as a Dexcom receiver so it looks like they figured out the protocol, but I don’t know too much about BLE and I wasn’t sure if a Garmin watch can connect to a Dexcom transmitter as a receiver. Plus I hate Garmin SDK, the language (MonkeyC) is just awful. It’s clear that they have no idea how to design and implement a language.
Ideally I want the watch to act as a Dexcom receiver and remove the phone from the equation but I have no idea how. It would be great to collaborate!
(The last part is to anyone who’s interested, not just to the author of the post!)
Should I be excited about this development? I’ve never used Pebble but I’ve been looking for a smart watch that will give me control over BLE features of the watch and allow me to connect to other devices via BLE. Will this be possible with the new Pebble?
I also switched to Zed a few months ago after more than a decade of vim.
The main reasons why I keep using it are (1) the project-wide search screen with mini-buffers is quite good (2) out-of-the-box LSP integration just works.
Editing features in general are not as good as vim yet. Paragraph formatting (gq in vim) and line joining (J in vim) don’t work as nice, and it doesn’t have spell checking, which makes editing comment blocks painful.
It also wants tree-sitter grammar for even the most basic editing features. I’m working on my own programming language, and it can’t even find matching parentheses (% in vim) because I don’t have a tree-sitter grammar yet. The problem is tree-sitter grammars are extremely painful to implement, especially for indentation-sensitive languages. So for now I go back and forth between Zed and vim when editing.
Finally, if you’re stuck with whatever when using Zed, you’re unlikely to get help, because the community is small and there aren’t a lot of discussions on sites like SO or on GitHub discussions.
I do hope this unified treatment of code generation, generics and type inference under “comptime” becomes standard practice, as it looks very reasonable to the user.
In Haskell we have typed TH which comes close, but also has some limitations in the types of terms that can be type-inferred (if you’re into experimental type systems, that is).
As a non-Zig user, my impression is that using comptime as generics has the exact same limitations as C++ templates: the generic code (or at least the usages of the generic type parameter) is not type-checked until it is actually used somewhere in the program, and this means that when you write generic libraries you don’t get static guarantees until you use them with example clients. This will make the experience much worse than proper generics, at scale. I am also worried about the quality of the editor-level type feedback in presence of heavy generics usage, for similar reasons.
(I’ve said this in the past and some Zig maintainers pointed out that Zig works hard to partially type-check code with comptime arguments and that it probably works fine in practice. My intuition rather stubbornly tells me that this will be very annoying in practice when used at scale.)
The problem is that when you say comptime T : type, you don’t give any static information about what the code below actually assumes about T. If it handles T as a completely generic/opaque type on which nothing is known, this is fine. But in practice most code like this will assume things about T, that it has certain fields, support certain operations, etc., and it will work fine because it will be used by callers with types that match these assumptions. But these assumptions are not made explicit in the generic function, and thus they cannot be reasoned about statically.
What makes generics hard in most languages is the desire to type-check assumptions about them statically. For example, if a function is generic over a type-former (a parametrized type) such as List, maybe you want to use subtyping in the body of the function, and so the type-system designers have to come up with a small static language to express variance assumptions about generic type-former parameters – it is one of the complex and annoying parts of Java generics, for example. They could also give up and say “well let’s just check on each usage type that the subtyping assumptions is in fact correct”, this would be much simpler design-wise, and the ergonomics would be much worse.
Maybe “worse is better” and having a simple type system with worse ergonomics is indeed a good idea that will become standard practice. (It certainly helps in lowering the entry barrier to designing type systems, and it possibly makes it easier for programmers to be confident about what is going on.) But I remain skeptical of such claims, especially when they are formulated without acknowledging the notable downsides of this approach.
As a Zig user, fully agree with all of the above! Some extra thoughts:
While I am 0.9 sure that for simple-to-medium cases, declaration side type-checking leads to better ergonomics, I am maybe at 0.5 that there’s complexity tipping point, where call-site checking becomes easier to reason about for the user. In other words, I observe that in languages with expressive generics, some libraries will evolve to try to encode everything in the type-signatures, leading to a programming style where most of the code written manipulates types, instead of doing the actual work. I’ve certainly seen a number of head-scratching Rust signatures. Here’s a recent relatively tame example of this sort of dynamics playing out: https://github.com/rust-lang/rust/pull/107122#issuecomment-2385640802.
I am not sure that just doing what Zig does would magically reduce the overall complexity here, but it seems at least plausible that, at the point where you get into the Turing tarpit when specifying function signatures, it might be better to just use the base imperative language for types?
When comparing with C++, it’s worth noting that you get both instantiation-time type-checking and a Turing tarpit. A big part of perceived C++ complexity is due to the fact that the tools of expressiveness are overloading, ADL, and SFINAE. Zig keeps instantiation-time checking (or rather, dials it up to 11, as even non-generic functions are checked at call-site), but also simplifies everything else a lot.
Another dimension to think about here is crates.io style packages. It seems that declaration-checking plays a major role in SemVer — semantic versioning starts with defining what is and what is not your API. But, at the same time, the resulting ecosystem also depends on culture of making changes, not only on technical means to enforce it. And Zig’s package manager/build systems is shaping up to be the best-in-class general purpose small-scale dependency management solution. I am extremely curious what the ecosystem ends up looking like, after the language stabilizes.
And Zig’s package manager/build systems is shaping up to be the best-in-class general purpose small-scale dependency management solution. I am extremely curious what the ecosystem ends up looking like, after the language stabilizes
Could you say a few words (or point us to some documentation) on what you think makes Zig’s package manager/build system the best?
There are no docs! As a disclaimer, Zig is a work-in-progress. If you want to just use the thing,
it’s much too early for that, come back five years later!
That being said, why I am excited about a hypothetical Zig ecosystem:
First, Zig aims to be dependency zero. One problem that is traditionally hard in this space is how
do you get the environment that can execute the build/packaging logic? There’s a lot of tools
that, eg, depend on Python, which make building software at least as hard as provisioning Python.
Another common gratuitous dependency is sh/bash and core utils. Yet another option is JVM (gradle,
bazel).
In contrast, zig is a statically linked binary that already can execute arbitrary scripts (via zig run) and can download stuff from the internet (via zig fetch). That is big! If you can run stuff,
and can download stuff to run from the internet, you can do anything with no headache. What’s more,
it’s not confined to your build system, you can write normal software in Zig too (though, tbh, I am
personally still pretty skeptical about viability of only-spatially-memory-safe language for general
purpose stuff).
Second, I think Zig arrived at the most useful general notion of what is a dependency — a
directory of files identified by a hash. From the
docs:
This field (hash) is the source of truth; packages do not come from a url; they come from a
hash. url is just one of many possible mirrors for how to obtain a package matching this hash.
There’s no special casing for “Zig” dependencies. You use the same mechanism to fetch anything (eg,
in TigerBeetle we use this to fetch a prebuilt copy of llvm-objcopy). I expanded on this a bit in
https://matklad.github.io/2024/12/30/what-is-dependency.html. inb4 someone mentions nix: nix can do
some of this, but it is not a good dependency zero, because it itself depends on posix.
Third, the build system is adequate. It uses general purpose imperative code to generate a static
build graph which is then incrementally executed. This feels like the least sour spot for general
purpose build systems. While you get some gradle-vibes from the requirement to explicitly
structure your build as two phases, the fact that it all is simple procedural code in a
statically-typed language, rather than a DSL, makes the end result much more understandable.
Similarly, while static build graph can’t describe every imaginable builds, some builds (at lest at
a medium scale) are better left to imagination.
Fourth, Zig is serious about avoiding dependencies. For example, cross compilation works. From
windows, you can build software that dynamically links a specific version of glibc, because the
Zig folks did the work of actually specifying the ABI of specific glibc version. This, combined with
the fact that Zig also is a C/C++ compiler, makes it possible to produce good builds for existing
native software.
I like the theoretical idea of Zig being dependency zero, but in practice this ends up being horrible: if your toolchain is your bootstrap point, you’re chained at the waist to whatever version of the compiler you happen to have installed. Compare this to rustup, which allows a single installation but will auto-detect and install the toolchain version required for each project. It’s not just rustup either: there’s a reason that games (Veloren for example) separate the main body of the code from their installer/launcher: it allows the former to have a higher update cadence than the latter without enormous annoyance for the user.
One elegant solution is to not install anything! I don’t have zig in my PATH, I always use ./zig/zig to run stuff. For example, hacking on TigerBeetle is
git clone https://github.com/tigerbeetle/tigerbeetle && cd tigerbeetle
./zig/download.sh
./zig/zig build
Having a tiny .sh/.bat to download the thing is not elegant, but is not too bad. Certainly simpler than rustup installer!
Actually, I should have added “Zig promotes local installs” to the list above: Zig’s pretty clear that make install is generally a bad idea, and that you should install stuff locally more often.
And then, as kristoff says and Go demonstrates, nothing prevents the toolchain from updating itself. Zig already JIT some lesser used commands (compiler ships its components in the form of the source code), it certainly can learn to upgrade itself.
build.zig.zon (the Zig equivalent of package.json) supports specifying a minimum version supported of the compiler toolchain. This field is currently not used by the toolchain, but there’s a proposal to have Zig download another copy of Zig when the installed version doesn’t satisfy the constraint declared in build.zig.zon.
But even without adding this support in the toolchain itself, you could have a zigup project responsable to auto-detect and install the toolchain in the required version of each project.
In other words, I observe that in languages with expressive generics, some libraries will evolve to try to encode everything in the type-signatures, leading to a programming style where most of the code written manipulates types, instead of doing the actual work. I’ve certainly seen a number of head-scratching Rust signatures.
That’s part of the issue with what Wedson presented, and that Ts’o reacted to. Wedson had a very nice slide with a call that returned a very extensive type definition and claimed that was good.
Don’t get me wrong, Ts’o’s reaction was very bad. He should have behaved better. But on the technical merit, I think Wedson missed the mark.
I can’t see similar thing happening with Zig (at least not anytime soon) - not because you can’t do it, but because the ecosystem around the language seems to be allergic to cramming all things into the type system. Comptime presents itself as an easy escape valve to keep things simple.
But than, it needs to be compared with safe transmute which is quite an infra…
I am still not sure what I think here. The signature is quite impenetrable either way! But then, the fact that I can just write the logic for “is this reasonable to transmute?” like this is neat:
As a Go user, a lot of problems other languages solve with complex type constraints I see get solved with func f(x any) { if !matchConstraint(x) { panic("type must foo and bar") …. (I do it in my own code here.) In practice it usually isn’t a problem because you catch the panics with even minimal testing. It is unsatisfying though.
Using any has lots of downsides though, for one you lose the help of the compiler and your tooling to e.g. auto-complete a method. It is fine for a self contained method in a relatively small code base, but starts to get hairy as your code increases in complexity.
it seems at least plausible that, at the point where you get into the Turing tarpit when specifying function signatures, it might be better to just use the base imperative language for types?
I feel like this doesn’t entirely preclude better ergonomics though, at least if there were something like C++ concepts. Then you’d at least be able to observe the signatures to see what the expectations of the type are.
When comparing with C++, it’s worth noting that you get both instantiation-time type-checking and a Turing tarpit. A big part of perceived C++ complexity is due to the fact that the tools of expressiveness are overloading, ADL, and SFINAE. Zig keeps instantiation-time checking (or rather, dials it up to 11, as even non-generic functions are checked at call-site), but also simplifies everything else a lot.
IME this actually doesn’t affect the day-to-day ergonomics that much; ADL fails are usually pretty obvious in client code unless you’re doing some REALLY cursed library stuff, and SFINAE errors are actually pretty decent these days. The big thing that wasn’t fixed until concepts was just goofs like “I thought I had a map and not a vector so I passed a value type as the allocator” and suddenly you have like a zillion errors and need to fish out the actual goof. Zig…well it kinda fixes that w/ generally shorter instantiation traces, due to enhancements like “actually having loops”, but it’s still not super great.
This suggests that your programming style around generics is fairly simple, and therefore easy to test – there is not a lot of conditional logic in your generics that would require several distinct tests, etc. You would also do just fine in Zig if you were to write similar code. This is good news!
But several members of the C++ design community have spent a decade of their life working on C++ Concepts to solve these issues (the first proposal started in 2005-2006 I believe, it was planned in C++0x that became C++11, and then dropped because too complex, and then “Concepts Lite” appeared in 2016 but were rejected from C++17 and finally merged in C++20). I believe that this dedication comes from real user-stories about the perils of these aspects of C++ templates – which are largely documented online; there was a clear perceived need within the C++ community that comes from the fact that a lot of template code that many people are using was in fact much more complex than yours and suffered from these scaling issues.
Yeah definitely, I think it’s best to keep to simple generic code.
I don’t find the philosophy of “maxing out” compile time in C++ to be effective, and I don’t see the programmers I admire using it a lot, with maybe a few exceptions. (e.g. Carmack, Jeff Dean, Bellard, DJB, don’t really care about compile time programming as far as I can tell. They just get a lot of work done) There was also a recent (troll-ish) post by Zed Shaw saying that C++ is fun once you push aside the TMP stuff
All of Oils is written with Python as the metaprogramming language for C++, with textual code gen. Textual code gen takes some work, but it’s easy and simple to reason about.
IMO, it’s nicer than using the C preprocessor or using the C++ template system. (Although we also use the C++ template system for a few things – notably the compiler is the only thing that has access to certain info, like sizeof() and offsetof() )
The main thing that would make it better is if the C++ type system didn’t have all these HOLES due to compatibility with C! I mentioned that here:
(although I also forgot to mention that the C++ type system is extremely expressive too, what I called “hidden static expressiveness”)
The other main downside is that you need a good build system to handle code gen, which is why I often write about Ninja!
So I might think of comptime as simply using the same language, rather than having the Python/C++ split. I can see why people might not like that solution, and there are downsides, but I think it works fine. The known alternatives have steep tradeoffs.
Metaprogramming has a pretty common taxonomy where you decide which part of the compiler pipeline you hook into:
textual source code – the kind of metaprogramming that is supported by every language!
the lexer - the C preprocessor has its own C-like lexer, and hooks in here
the reader/parser - Lisp-like macros - for “bicameral syntax”
the runtime - I think Lua/Terra is more in this category. I think you can create Terra data structures “directly” in Lua, with an API
I don’t think any way is strictly better than the others – they all have tradeoffs.
But we are doing #1 and I think Lua/Terra is more like #4, or #3.
But spiritually you can write the same kinds of programs. It just means that we end up generating the source code of C++ functions rather than having some kind of API to C++.
Of course you often write little “runtime” shims to make this easier – that is sort of like your API to C++. The garbage collected data structures are the biggest runtime shim!
I do still think we need a “proper” language that supports this model.
It could be YSH – What if the shell and the C preprocessor were the same language? :-)
the generic code (or at least the usages of the generic type parameter) is not type-checked until it is actually used somewhere in the program
comptime extends this to all code; anything not reachable from an export as a general rule. It’s what allows for the dependent-esque decision making, cross-compilation/specializing using normal control flow, and general reflection. Without it, other langs default to a secondary declarative system like Rust’s #[cfg()] or C’s #ifdef. It’s a bit restrictive though, so a higher level build script (like proc-macros in Rust) is used for similar comptime effect.
But these assumptions are not made explicit in the generic function, and thus they cannot be reasoned about statically.
They technically can given comptime reflection (i.e. @typeInfo) is available. It just ends up being quite verbose so in practice most rely on duck typing instead.
My intuition rather stubbornly tells me that this will be very annoying in practice when used at scale. […] the ergonomics would be much worse
Ergonomics ok for now given you can x: anytype. What sort of environments do you see it causing the most annoyance? Im thinking maybe for cases where people learn exclusively through an LSP.
Without it, other langs default to a secondary declarative system like Rust’s #[cfg()] or C’s #ifdef.
I’m not saying that all uses of comptime are bad, and maybe it’s nice when it replaces macros for conditional compilation. I was pointing out that it is probably not the magic answer to all problems about “generics and code inference” that should become “standard practice”.
What sort of environments do you see it causing the most annoyance?
I would expect the usual downsides of late-type-checking of C++ templates to show up:
The validity of the template code is only checked at callsites. Library authors often write generic code without having full coverage of all possible configuration in their testsuite, and they will commit changes that break in practice because they didn’t have user code checking a particular configuration. This problem gets worse as templates get more elaborate, with conditional logic etc., and an exponential blowup in the number of different scenarios to test.
Error messages can be quite poor because the type-checker does not know whether to blame the author of the template or the caller of the template. The type T provided does not offer operation fobar, is it a typo in the template code or a mistake of the caller? If you write generic code with, say, type-classes or traits (where the expected operations are explicitly listed in the class constraint / trait bound present in the generic code), you can tell when there is a typo in the generic code and not blame the caller.
Compilation times can become quite large because each callsite needs to be re-checked for validity. This can become an issue or not depending on the amount of generic logic used by the programming community, but these conventions typically change over time and there can be surprisingly exponential cliffs.
Maybe Zig has (technical or social) solutions to some or all of these problems, and/or maybe the people explaining how great comptime is are too naive about this. If there is some secret sauce that makes this all work well, then it should be carefully explained and documented along the explanation of how simple comptime is; this is important in the context of encouraging other languages to adopt this approach (as done in the post I was replying to), they need to also understand the pitfalls and how to avoid them.
The first point is sometimes an issue for cross-compilation especially. Zig’s ability to do so from any machine (-target whatever) makes it easier to test locally but in practice this error is often caught by CI.
Error messages are surprisingly readable; “Type does not provide operation” is usually the caller’s fault (genuinely never seen it be the callee’s - whats an example of that?) and can be figured out through docs or variable naming. A good example of this is forgetting to wrap the format args parameter for std.fmt.format in a tuple.
Comptime speed does indeed become noticeable in larger projects. But its primarily due to reflection and constexpr execution rather than type-checking (AFAIK that part alone is always fast even for multiple nested instantiations).
I dont think there’s secret sauce. You tend to either 1. not run into these 2. figure them out intuitively / with a little help due to lacking documentation or 3. cannot adjust / dont prefer it, having come from other langs. After the first or second time hitting them, it becomes a non-issue (like eager-PRO). It’s similar to how zig-folk recommend reading the stdlib to learn the language; wouldn’t really be a good idea other languages like C++, Rust, etc. but makes perfect sense (and works) in Zig.
I once tried using stdlib JSON decoder to decode some structure that contained std.hash_map.HashMap. Let’s say that the error wasn’t clear at all why it is happening and how I can resolve it. It is especially painful when it happen deeply within some obscure internals of something that is mostly out of your control.
Zig is nice, but yeah, their generic errors make me remember old C++ templating failures.
Curious what it looked like. The worst cases IME are when it doesnt print the trace due to compiler bugs or when it gives error: expected type 'T', found 'T' which is pretty unclear. Or the slightly easier (but still annoying) case of expected T(..., a, ...), found T(..., b, ...).
“Type does not provide operation” is usually the caller’s fault (genuinely never seen it be the callee’s - whats an example of that?)
Imaginary scenario: for scientific programming, there is a naming convention for types that satisfy a certain set of operations, that comes from the important (imaginary) library ZigNum. Your project is using library Foo, which implements datatype-generic algorithms you care about, and also ZigNum directly – calling generic functions from both on the same types. The next version of ZigNum decides, for consistency reasons, to rename one of the operation (their previous name for the cartesian product was a poor choice). Then you code starts breaking, and there are two kind of errors that are displayed in exactly the same way:
For the errors in calls to functions from ZigNum, the code break because the operation names assumed by ZigNum have changed, you want to follow best practices so you update your own code; in a sense it was “the caller’s fault”, or at least the “right fix” is to change the caller.
But now you start getting errors in calls from Foo as well, because Foo hasn’t been updated and is using the previous name. In this case you have decided to stick to the naming conventions of the ZigNum project, so for those errors the library Foo is to blame, it should be updated with the new names.
If ZigNum would export a [type-class / module interface / concept / trait] that describes the operation names it expects, then compiling Foo against the new version of ZigNum would have failed, blaming the code (in Foo) that needs to be updated. Instead the error occurs in your own user code. If the person encountering this failure happens to be familiar with ZigNum and Foo, they will figure things out. Otherwise they may find this all fairly confusing.
Is ZigNum here an interface or an implementation? Having difficultly following the confusion: “A uses B. I just updated B and compiler says A started breaking on B stuff. I probably need to update A too.” seems like a fair reaction.
The error would occur in Foo, but zig errors are stack traces so the trace would lead back down to your code. This scenario however still looks like its the caller’s fault for passing incompatible types to a library. Something similar can also happen when you compile a zig 0.11.0 codebase (with dependencies also expecting a 0.11.0 stdlib) using a zig 0.13.0 compiler.
Well articulated and leads to a fascinating bit of reasoning.
First thought is, “well, you need multiple phases then.” Execute the comptime code, settle on what it produces, and then typecheck the code that relies on it.
But a moment’s thought shows that:
(a) you’d eventually need 3 levels, sometimes 4, etc.
(b) … and this is really just plain old code generation!
So we of course face the same fundamental issue as always. Wording it in terms of Lisp macros, you need to be able to flip back and forth between using the macro, and seeing/understanding the full expansion of the macro.
What we need is an outstanding solution to that fundamental problem.
C++ is gradually adding things that you’re permitted to do in constexpr contexts. You can now allocate memory, though it must be destroyed at the end of the constant evaluation. Generalising this much further is hard because the language needs to be able to track pointers and replace them with relocations, which is not possible in the general case for C/C++ (pointers can be converted to integers and back and so on). That’s mostly solvable, but there are also problems with things like trees that use addresses as identity, because even the relationship between the addresses at compile time isn’t constant: if I create two globals and put them in a tree, I after COMDAT merging and linking I don’t know which will be at a lower address.
Being able to merge the expression and type languages is very nice, but you either need to be able to create types at run time, or have a subset of the expression language that is only available at compile time. Smalltalk takes the former approach, C++ is quite heavily entrenched in the latter.
JSON streaming works fine but it needs minimal buy-in on the protocol end that many popular protocols (cough JSON-RPC cough) manage to flounder. So many APIs have {"type": "Name", "data": {}}… totally unstreamable.
In my experience streaming isn’t well supported in the json library world. I’m getting flashbacks to dealing with >10GB objects when trying to recover a corrupt Cassandra database – their recovery tools would generate files that other tools in their suite could not consume.
This means that your system probably can’t safely handle JSON documents with unknown fields.
Like Protobuf handles unknown fields any better?
If you’re sending me unknown fields, as, in they’re not in my published schema, I’m either ignoring them if I’m honouring Postel, or you’re getting a 400 Bad Request.
I honestly can’t think of a reason why I would accept unknown fields you’re POSTing to my API.
And if JSON is so bad, you need to ask yourself why it’s so obiquitous.
Also, streaming parsers for JSON exist. I can’t speak to their implementation, but I’ve seen them.
And if JSON is so bad, you need to ask yourself why it’s so obiquitous.
That’s really never been a good argument. It’s popular, like many other things, because it’s the easiest format for the first few hours/days (especially when javascript is involved). By the time the (numerous) downsides become more apparent, it’s too late to change your service/data/protocol.
In general, public APIs should drop unknown fields on server-side to prevent security attack via unknown fields. For example, garbage unknown fields may cause a server to fail when it starts to use them as new fields in the future.
Yeah, that’s why I mentioned ignoring unknown fields. But generally in a distributed system I’d use a schema registry like Apicurio so that when a publisher uses a new version of a schema, consumers can pull it down as needed.
Scheme registries are nice— I’ve used buf— but it doesn’t solve the fundamental problem that old consumers will run at the same time as updated consumers.
Ingress services can do what they want with unknown fields, but middleboxes need to pass them unmolested.
I think we need a more structural editing solution, but we cannot go fully structured: that will require either inventing a new language (extremely difficult on its own), or supporting sometimes hundreds of types of expressions and statements in a structural way (not sure if possible conveniently).
What I propose in my blog post is a middle ground where you have structural editing at the top-most layers, starting from packages to statement/expression level, and from there you edit as before. I think it can be done, and should give us a lot of the benefits of structural editing.
I got around this by inventing a new language that isn’t a programming language but is rather a data description language not unlike HTML. Most people forget that structured editing is a solved problem on the internet to the extent that I’m using a live structure editor to compose this post right now.
You don’t need incremental parsing even. Parsing from scratch is fast enough most of the time.
IntelliJ doesn’t generally do incremental parsing, and yet it has full access to syntax tree all the time.
Incremental parser is helpful, but by no means it is table stakes.
What you need though is resilient parser, a parser that can deal with incomplete syntax. This is table stakes, and not typically available.
Other that that, agree with a thesis: almost everything you can get with a structural editor you can get faster and cheaper by just writing a parser which doesn’t bail on the first error, and you get all text-editing goodies like multiple cursors for free.
In some sense, one can do anything in manually written parsers if one has the skill and the patience to do so. I hope I’m not claiming that Wagner’s approach does something that’s impossible in other settings!
That said, Wagner’s approach does have some cool things that can be harder (not impossible, but harder) in a “reparse everything” setting. For example, its approach to error recovery can use “history”: if you make a program syntactically invalid it can use a past parse of that part of the program to try and fix it, and then move on. I don’t think that’s the only thing one needs to do for error recovery – it doesn’t work very well for new portions of a program, for example – but it’s an example of something that requires some sort of memory / caching.
I didn’t try the resilient LL(1) technique, but it seems like it could be a good mix of powerful and expressive vs. easy to write. Obviously it again depends on the language
I am trying to decide if shell is a special case or not, as far as the complexity of the syntax … I think JavaScript is starting to resemble shell, because you have JSX literals in JS, and then you have JS and CSS in HTML, etc. You also have TypeScript
i.e. there are more arbitrary interleavings of composed languages in modern JavaScript.
I think the problem is that the original authors of those tools are NOT necessarily using grammars, so a given metalanguage can’t necessarily handle what they have done with arbitrary code, at least not easily.
I am trying to decide if shell is a special case or not, as far as the complexity of the syntax
I wouldn’t say it’s exactly a special case, because there are a number of other languages whose grammars can not be specified in a way that we can meaningfully statically reason about (give me an LL/LR grammar and I’ll guarantee strong properties about it; give me, say, a PEG and… I can’t). But it is definitely in the “I wish the syntax hadn’t evolved in this way, because it’s difficult to reason about for humans and machines” category!
Shell has the same issue that Ruby has – you have to parse it to lex it:
It might be the case that Ruby isn’t possible to lex without parsing.
A reason in shell is that
$(case x in x) echo hi ;; esac)
has 1 left paren, and 2 right parens, and you have to parse to know where the $( ends. You can’t just lex.
And I also think that complicates any kind of incremental parsing, if the lexer has to invoke the parser.
So then to me a very fruitful research question is to find a parsing metalanguage that can express shell and Ruby (and JS and C++, etc.)
I think Treesitter comes very close, but doesn’t hit the mark. Again, to the authors’ credit, they tested it on some of the most difficult languages, but perhaps not the Ruby/shell level of difficulty.
I noticed that the Wagner incremental lexing can accept arbitrary lexers via runtime instrumentation, rather than static analysis. (notably, Treesitter doesn’t implement Wagner incremental lexing – though you have to use its peculiar interface!)
On the other hand, Wagner incremental parsing is grammar-based. But IMO this restriction makes it infeasible for shell and Ruby. I suppose it’s an open question if some approximation is “good enough”, but I don’t think so, and I don’t see it in practice.
Originally I thought I would use PEGs for https://www.oilshell.org/, but PEGs don’t traditionally separate lexing and parsing, and there is a non-trivial interface to the lexer in OIls. For example, there is a stack of “hints” in the lexer to to find the closing ) in the case above, and there are a few other mechanisms too.
But our parsing style [1] is not unlike PEGs, and it is expressive. It turned out to be capable of expressing 4 interleaved sublanguages with different lexical syntax, as well as 6 or so mini-languages. (We also interleave with a generated parser!)
I haven’t looked in detail at work on incrementally parsing PEGs [2], but if making PEGs incremental is possible, then I think making the Oils model incremental is probably also possible.
That is, recast it as something more like a set rather than an algorithm, like PEGs. I think in practice having the lexer/parser separation is useful, and it probably doesn’t complicate the theory too much (?)
As a concrete example, PEG has “lookahead assertions”. Somewhat late in the Oils development, I added a method to “look ahead with a certain lexer mode” to handle a few language constructs. A lexer mode is simply a mapping of regular languages to tokens.
So that kind of thing is a small difference that I think should be possible to formalize, and recast as a set, although certainly there could be other issues that make it harder.
I would also conjecture that if such a metalanguage can handle shell, it can handle Ruby and JavaScript and TypeScript.
C/C++ may need an additional hack for the symbol table -> lexer feedback, and possibly the “most vexing parse”.
It might be the case that Ruby isn’t possible to lex without parsing.
This has been my experience, having written a from-scratch Ruby parser/interpreter/etc. that gets all the hard stuff right — doing it the traditional lex/yacc way, you need many “lexical tie-ins” (i.e. situations where the parser modifies lexer state).
AFAICT Rocq (née Coq) is LL1 but parsing requires partial evaluation (extensible syntax with notations let one sentence change the parser before it parses the next one). I’ve only heard dire warnings about trying to implement your own parser.
IntelliJ Java parser is incremental. It is absolute table stakes. Without it you wouldn’t be able to get the snappiness that IntelliJ has even in modest files. Source: wrote lots of code in IntelliJ back then. Including lots of different parsers.
Thanks, I’ll double check this! Let me be more precise about my current beliefs about “generally doesn’t do” for the record, to pin down exactly how wrong I am. This is about the state around 2016-2017, haven’t looked at the code much since then:
Anything that builds on top of Grammar-Kit is not incremental
Dart plugin in particular doesn’t do even incremental text sync with the analysis server
XML parsing is incremental, as the files are too big
I don’t know about Java&Kotlin parsers specifically, they might be incremental
Every lexer is incremental
On top of the full parser, there’s a tree-diffing layer that makes updating the PSI tree incremental.
Hm, I think this is basically right? Java is parsed incrementally, but there’s no direct support for incrementally in GranmarKit and many other language are not incremental. In particular, Python only grew support for incremental parsing this year:
Which is to say: incrementality is useful, but you probably can get by without it. This is in contrast to resilience, without which the thing simply won’t work most of the time.
That being said, my original wording is misleading! It does imply that Java parsing is not incremental, and that is plain wrong, thanks for chiming in here to correct that!
I don’t have IntelliJ around anymore but I bet that if you open 20k lines file and start typing you could easily tell which parser is incremental and which is not.
So you’re probably right: it is not essential. But if you want to dethrone IJ, then it is :)
Sorry, don’t know anything about grammar kit. Last time I touched idea was probably 2008-2009 :) So you should replace “is” with “was” below.
As for Java incremental parser: it is important to understand that IntelliJ incremental parser is not optimal: i.e. it doesn’t guarantee minimal reparse, but something that works well in practice. E.g. if I remember correctly, code block is the unit of reparse, which could still be pretty big but is much smaller than the whole file.
Another case where incremental parsing is essential is when you type in ‘{‘: you don’t want full file structure to break.
Additional aspect of incrementality is to detect when parse yields the same tree structure and do not generate node updates (I’d call this incremental parse tree).
And on somewhat generic note: to be snappy you need to press ctrl+space and see completion in < 100ms. That includes doing a lot of work, re-parsing and re-resolving lots of files, which means that in reality parsing update should be on the order of milliseconds. We’ve got Eclipse engineers including EG coming to our boothes and asking why are we so fast? They never really got that it starts from the lowest level of code manipulation.
PS all credit for the speed goes to incredible kip for building PSI and later max.
Yeah, that’s also a very important point: you don’t need to invent a general incremental parsing algorithm, a simple heuristics work and it doesn’t actually require modifying the parser itself much.
One related anecdote here is that rust-analyzer included more or less the same block reparsing heuristic from the beginning, but, as far as I am aware, it is not actually enabled still. Not sure if this is because computers in 2018 were faster than in 2008, because its JVM vs Rust thing, or due to inherent asynchrony of LSP, but parsing never was near the top of cost-centers for completion, it was always Rust global-ish type inference with traits.
I think the main use case for incremental parsing would be as a basis for incrementalizing complex and costly analyses, maybe even compilation.
Imagine analyses (or even compilation) implemented with queries like “find the main function”, “get constructors of type X” etc. and a framework that records queries done to answer one query, and cache results.
(I think the idea is similar to Rust’s Salsa and/or Adapton, but I don’t have too much experience in any of them, so I’m not sure.)
Incremental parsing (as described by Wagner’s thesis, mentioned in the blog post) gives you the changed nodes in the AST, which you can use to invalidate results of queries that use those nodes, and start recomputing from there.
Without incremental parsing you have to compare the program AST before and after an edit to find which nodes are updated and invalidate query results based on that. I suspect it may be more efficient with incremental parsing.
Not sure! The thing is, if you add a blank line at the start of the file, you need to recompute all error messages (as they include line numbers) but keep the errors themselves (as nothing about the semantics of the file changes).
The way this works is that you have a sort-of recompilation firewall query, which takes raw syntax tree, and splits it into volatile parts (text offsets, specific concrete syntax choices, etc) and stable parts (the set of names defined in a file). And most of costly recompilation is driven by the changes in that small, stable part. And, as the firewall query is arbitrary code, its is kinda hard to incremntalize it automatically, but also it is cheap itself, so diffing its results is fast enough.
IOW, you can’t directly feed incremental tree updates into semantic analysis.
you need to recompute all error messages (as they include line numbers)
Why not just compute the error messages on the fly using the current positions? Sum trees make it log(n) to figure out line and column information on the fly without needing to store it
Another interesting point related to this topic might be what Unison does. To my knowledge, it stores basically “AST-nodes” in its own, normalized format. This gives the language automatic deduplication of identical functions (even when they are not textually identical, only semantically, e.g. whitespace difference).
Treesitter’s original application is smart syntax highlighting, and Treesitter is incremental … I’m pretty sure that will be too slow without incremental parsing.
e.g. compare it with Vim – it updates on every keystroke, does the weaker kind of syntax highlighting, and it is line-based.
If you want syntax highlighting be as responsive as Vim, and if Treesitter were NOT incremental, I don’t think that would work well. I think a full parse is too slow on every keystroke
I think IntelliJ must have more Vim-like syntax highlighting, not something like Treesitter? Not that this is bad, I think there can be a better compromise than Treesitter.
Although I kinda want to investigate some kind of “coarse parsing” first. So instead of using a line as a window Vim, then maybe you can use some delimiters like {}. Although then that also has the resiliency issues.
Not a good point of comparison as vim (to the best of my knowledge) doesn’t do any “parsing” so much as it does “brute force regex all things” with different regex rules for each syntax element. I don’t think it does it just once, either - pretty sure it tries repeatedly as the “syntax window” shifts. You’d be laughed out of the ballpark if you shipped a compiler (or whatever) that “parsed” your language in the same fashion vim does.
(This applies to neovim as well, but neovim has a still-in-the-works “native” TreeSitter integration to change that.)
I’m comparing them because both vim and Treesitter do syntax highlighting, and I believe Treesitter is incremental because doing full parses would be too slow for that use case.
I also think it should be possible to get the best of both worlds – accuracy and speed.
I think IntelliJ must have more Vim-like syntax highlighting, not something like Treesitter?
Since I’m in a memory trip lane: IntelliJ highlighter is multi-layered. On the lowest level highlighter uses lexer information, but keeps adding more highlights when there’s more information available. That includes syntax trees and even resolved references (semantic highlighting).
I wrote a syntax highlighter using libclang around 15 years ago and it did three things:
Use precompiled headers so it didn’t need to reparse the megabytes of headers in a typical C-family compilation unit (not necessary for other languages).
Tokenize immediately, parse later.
Keep highlighting from previous parses until it was replaced.
It was not incremental and the syntax highlighting often lagged a second or so behind (on a 1.2 GHz P3 Celeron), but it was pretty usable.
Treesitter’s original application is smart syntax highlighting, and Treesitter is incremental … I’m pretty sure that will be too slow without incremental parsing.
Tree-sitter is not the right solution if you only need syntax highlighting, syntax highlighting can be done with a lexer/tokenizer because you don’t need the tree structure for syntax highlighting, and lexing will be much faster to run from scratch and also easier to make incremental if it’s still not fast enough.
Unless you’re using a language like C++ where you can’t tell the difference between a variable declaration and function declaration without type information.
you need LSP semantic highlighting to correctly highlight Most Vexing Parse, tree-sitter doesn’t work (iirc it always highlights it as a function declaration)
I am kind of going on a tangent here, because the original post is about structured editing, not syntax highlighting
But the original goal of Treesitter was to use grammatical structure for syntax highlighting, not just lexical structure, like say Vim or SublimeText. This was clearly stated in one of the talks - https://tree-sitter.github.io/tree-sitter/#talks-on-tree-sitter
Tree-sitter enables reference highlighting, where various identifiers can be highlighted differently depending on whether they’re referencing a variable, function, parameter, constant, etc. GitHub uses this for some languages, and also extends it to cross-file reference resolution with stack graphs. Nvim-treesitter does have in-file reference highlighting but it is very slow so I usually disable it once the file grows beyond a certain size.
I’m pretty sure that will be too slow without incremental parsing.
That’s exactly the thesis of matklad’s post- it’s often easily fast enough without incremental parsing. I have had similar experiences with parsing in response to keystrokes in an editor, and you can see a lot of LSP implementations (which provide “semantic” syntax highlighting based on the full parse tree) also work this way. This includes IntelliJ- as matklad put it, “it has full access to syntax tree all the time.” The expensive thing here is usually not parsing itself but all the analysis done on the result.
It’s possible tree-sitter itself might be too slow without incremental parsing, but tree-sitter uses a relatively expensive parsing algorithm (for good reason, don’t take this as a dunk on tree-sitter in any way) so that wouldn’t really be indicative of the general “parse from scratch” approach. (At the same time, outside of syntax highlighting, I have done some benchmarking of non-incremental tree-sitter against things like clangd, and it’s still much faster than those “traditional” frontends…)
it parses all languages, not a single language. If you are building a universal solution, you might as well incur more engineering complexity as it amortizes better
IIUC, tree sitter was originally meant to be used alongside a scripting language, so you’d have one JS object per syntax node. And avoiding churning through GC objects is worthwhile, and incrementally give you that. IntelliJ also avoids re-allocating the entire PSI tree, but it does that through tree diffing, not through incremental parse.
Well I sort of changed the subject from structured editing to syntax highlighting
But I would say you should have a 10-20 ms budget per keystroke, for syntax highlighting. (As a data point, 16.6 ms is 60 frames per second). Ideally it would be (much) less than 1 ms, but that’s a maximum. Because the CPU has to do other things too.
That’s definitely enough to parse small files, but large files are a problem.
Many editors and IDEs choke on large files, while Vim generally doesn’t. One solution is to just bail out for large files, since 99% are small. You can “degrade” to a text editor in that case.
Important clarification from mikea below: for Java, IntelliJ is incremental. But it’s not incremental “by default”, languages have to opt-into incrementally, and many don’t, or do it rather late in the lifetime of a particular language plugin.
That’s the crux of caching: you don’t need it if the base system can handle the load. I’d go even further and claim that if language and compiler are co-designed for efficiency, you might not even need incremental compilation majority of the time.
From what I understand this is more an issue with the design of Swift’s type system, i.e. the combination of subtyping, ad-hoc overloading (based on type, including return type polymorphism) and global type inference. This is well known to be a problem if you are familiar with the research on type checking, both for performance and usability, and there are approaches to deal with it, and to avoid the unrestricted mixing of problematic features as is seen in Swift.
You can have fast type inference, but it does mean designing your type system with that in mind. Adding in bidirectional typing to direct the flow of information through the type checker can be great for usability and performance too, giving type errors closer to the source of the problem based on annotations provided by the programmer.
Also note that Hindley Milner does not require generating and collecting constraints, you can also perform unification destructively as you go, which greatly improves performance (at the expense of biasing your type errors based on location. edit: looking at the blog post this is actually the approach it takes).
I asked Chris about this and he clarified that he meant that specifically in the context of Swift, not for languages in general. Here’s a recording where he clarified what he meant by that:
Also, the language that set the bar for high-quality error messages is Elm, which uses Hindley-Milner type inference and has a very fast compiler, and the Rust team cited Elm as the inspiration for the overhaul of their error messages which gave Rust a reputation for nice error messages:
Thanks for clarifying it. I would be curious to see the Reddit/HN comment (didn’t find it myself).
Also, the language that set the bar for high-quality error messages is Elm, which uses Hindley-Milner type inference and has a very fast compiler, and the Rust team cited Elm as the inspiration for the overhaul of their error messages which gave Rust a reputation for nice error messages:
Let me give you an example. Take this Rust code. The error message it produces:
error[E0597]: `ctx.field` does not live long enough
--> src/main.rs:10:27
|
9 | async fn async_fn(ctx: Context) {
| --- binding `ctx` declared here
10 | let mut field_guard = ctx.field.write().await;
| ^^^^^^^^^--------
| |
| borrowed value does not live long enough
| argument requires that `ctx.field` is borrowed for `'static`
11 | tokio::task::spawn_blocking(move || blocking_fn(&mut field_guard)).await;
12 | }
| - `ctx.field` dropped here while still borrowed
To me, the error message is hardly nice. I know what’s going on here: tokio::sync::RwLock::write() borrows ctx.field for lifetime 'a that’s limited to async_fn() scope. Whereas tokio::task::spawn_blocking() takes a closure which is 'static and thus all lifetimes within the closure must be 'static as well. A type error.
Now, look at how the explanation differs from the error message itself. There’s multiple problems here:
borrowed value does not live long enough points to ctx.field but there’s no borrowing (&) visible at this point in code. The actual borrowing is elsewhere — it’s the write(&self). It should show up in the error message IMO.
argument requires that ctx.field is borrowed for 'static doesn’t say, nor points to what “argument” exactly. There’s multiple arguments within the body of that function so it’s imprecise.
Finally, the biggest issue IMO, the error message doesn’t enumerate the reasoning chain the compiler performs so that a programmer could follow it and point out exactly the step at which it diverges from what’s happening inside of the programmer’s head. Ideally, it would look something like:
let mut field_guard = ctx.field.write().await;
^^^^^^^^^--------
|
`ctx.field` is borrowed here for lifetime 'x
let mut field_guard = ctx.field.write().await;
^^^^^^^^^^^
|
field_guard's lifetime is 'x
tokio::task::spawn_blocking(move || blocking_fn(&mut field_guard)).await;
^^^^^^^^^^^^^^^^
|
`field_guard` is borrowed here for lifetime 'y so 'x must live at least as long as 'y
tokio::task::spawn_blocking(move || blocking_fn(&mut field_guard)).await;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
expression lifetime is 'y
tokio::task::spawn_blocking(move || blocking_fn(&mut field_guard)).await;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
argument lifetime is 'y
fn spawn_blocking<F, R>(f: F) -> JoinHandle<R> where F: FnOnce() -> R + Send + 'static, R: Send + 'static
^^^^
|
parameter lifetime is 'static
tokio::task::spawn_blocking(move || blocking_fn(&mut field_guard)).await;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
argument lifetime is 'static
=> Thus 'y = 'static
=> Error: Unable to prove 'x lives at least as long as 'static
Oh I just brought up the Rust error messages as an example of a non-HM language that overall has a reputation for nice error messages (your mileage may vary, but the common view is that Rust’s error message quality is among the best) and that its error messages were inspired by a HM language.
Respondents aren’t content with the current error messages, but those error messages are a damn sight better than most of the competition! See how a recent post advises users into letting the compiler guide them: https://steveklabnik.com/writing/when-should-i-use-string-vs-str/. Compare that to TypeScript’s errors, which are unhelpful at best.
I’ll agree that Rust has great error messages until it doesn’t, and the situations where it doesn’t are usually the most annoying parts of the language like async, which I think is one of those situations and the example you highlight, so I’d also vote that error messages need work but would still think they are nice.
I speculate that “has a reputation for nice error messages” has an unsaid qualification “among programming language designers who appreciate the complexity of the problem”.
The common view is that Rust’s error message quality is among the best
Nevertheless, 98% of Rust users are not content with them and want them to be better
I don’t have any hard data to back up the claim that it’s a common view, but I just asked Perplexity “what programming languages have the nicest compiler error messages?” and its response listed Rust first, Elm second, and “TypeScript and Go” third.
Maybe I don’t understand what context-insensitive means here, but I just want to point out that if you infer types of variables without looking at the uses and you have subtyping, you can turn non-breaking changes into breaking changes. Example: https://gist.github.com/osa1/b17e09f84c33c0d478640e6d7811ed37.
This actually happened to me in real code and I had to revert a change.
If the type checker took the uses of the variable x into account this would work as expected.
You could not do type inference and ask the programmer to annotate variables with types, but that can easily get tedious, in most cases the type will be obvious, so that’s also not ideal.
One thing the resonated with me was “the behaviour of dynamically typed languages makes sense to users”. I heard a similar thing firsthand from one of the creators of Julia. Perhaps not an unpopular opinion but one not spoken openly about enough.
To me, the fact that backtracking inference affects the program behaviour (by eg casting values) confuses the hell out of me. (The latest example being me learning rust - all the auto casting of various refs lead me to learn the wrong behavior…).
With header files don’t you have to write all your type signatures and type definitions twice? I hated them when I worked with OCaml.
It makes more sense to just implement the described feature in IDEs/editors, instead of making every programmer copy/paste their types/signatures to a separate file.
Dunno about OCaml, but in C public types go in the header, private types in the implementation, so all that gets duplicated is the function prototypes.
It might be nice to allow function definitions to be abbreviated, so the types don’t have to be repeated, but on the other hand it might be bad for the full prototype to be so far from the body. On the gripping hand, I usually have both files open so that I can make sure the implementation and documentation match.
But my prehensile tail points out that having the documentation, type signature, and body right next to each other in one file is a lot more convenient, and rustdoc does a fine job of pulling out and presenting just the public interface.
Yes, header files can totally serve this purpose. They provide a nice overview of what’s the public interface of a module.
And, in the spirit of improving UX (which is what this post is about), i think it would be crucial to have seamless integration between header files and implementation files. E.g., it should be trivial to toggle between them; if i “go to definition”, the definition on the implementation file should be open; if i edit the signature of a function in the implementation file, the change should be made in the header file automatically; etc.
But, if we had all this, then the header file would become almost a “projection” of the implementation file. In practical terms, it’d be almost a modified view of the same source code. Something that could be entirely derived, but for some reason still exists as a separate source file.
I.e., header files with good UX would be something very very similar to the feature this post is proposing; minus the need for duplicated information in two different files :)
As @fanf mentions, the article of which we’re talking touches on this. But, if this is a genuine question(*), i also commented on why the article’s proposal is IMO superior to an “outline” view elsewhere on this discussion :)
*: I initially read it as a kind of slight, “don’t you know this has been a common thing for decades?”, but you probably didn’t mean it that way. Or at least i hope so! hehe
I don’t understand, the post doesn’t mention at all the IDE’s existing “outline” feature which already does everything mentioned here. Like when I open a code file, I have a separate panel which tells me all the methods in a file with their parameters, etc. and this has worked pretty much in every IDE I’ve ever worked in. e.g. this : https://ibb.co/48nXwn4 ; this was already a thing in dev-c++ in 2005.
Header files have the documentation and the complete public types. That outline looks fine for navigating a source file, but it isn’t a substitute for a header or for Matklad’s folded view.
But, if we had all this, then the header file would become almost a “projection” of the implementation file. In practical terms, it’d be almost a modified view of the same source code. Something that could be entirely derived, but for some reason still exists as a separate source file.
Ideally, (part of) the implementation would be a projection of the header, because you really want the interface to be primary. And no, I have no idea how to implement that, at least not one that’s also in any way reasonable.
(One company that I worked at did automatic header generation as a matter of course. It worked. It was…hmm…let’s just say I adopted many of the habits and practices from there, but not that one)
Yes. It’s good that languages are less redundant nowadays, but we definitely lost some nice ergonomic and information-hiding aspects of headers.
When I was working in C# back in the 00s, I invented a “header file” format for C# (basically the public/protected class and function declarations with no bodies) and made a little tool that generated it from a DLL.
I think we did have Intellisense in Visual Studio back then, but that just shows one method at a time, whereas this let you see the full picture of a library (or your own code).
My main problem with header files is that any refactor that involves changing a function’s signature requires changing it in two places, which is annoying.
My favorite description of HM inference is Section 4.4.4 in Samuel Mimram’s Proof=Program; they provide a description of level-based generalization which is more efficient than a generalize that needs to perform an occurs check to avoid generalizing variables not defined by the current binding (e.g. avoiding generalizing x in the definition of y in fun x -> let y = \z -> x in y, as the given example)
Algorithm M is interesting - it seems to have the localization benefits of systems like bidirectional type systems, while requiring no annotations
Regarding row polymorphism - Daan Leijen’s “Extensible records” paper is the simplest approach I know of, and is similar to the approach Elm/Roc use. At least in Roc, the approach is to bind a type variable to a record that unifies freely; for example the call (fun r -> r.x) {x: 1, y: 1} types the function as {x: a}b -> a (where b is free) and the record as {x: int, y: int}c (where c is free); {x: a}b ~ {x: int, y: int}c yields b = {y: int}d, c = {}d (where d is fresh). I don’t know of a good way to enforce that a record is “closed”, i.e. avoiding creating a fresh type variable representing expanding the width of the record, but I haven’t seen this be a problem in practice yet - but maybe there is an easy way?
And regarding variants, I think there is a simpler approach than OCaml’s approach by implementing the dual of the row-polymorphic approach above (which Roc also does)… that is, an expression `A 1 = `B "foo" is types the LHS and RHS as [A int]a and [B str]b respectively, the constraint [A int]a ~ [B str]b then solves a = [B str]c, b = [A int]c and both the LHS and RHS have type [A int, B str]c. In this case I think you do want to distinguish between extensible and non-extensible variants though, because a function [A, B]a -> {} is materially different than [A, B] -> {} - if you have a pattern match over the input on the former, you always need a catch-all branch, whereas a pattern match on the latter only needs a branch for A and B.
Anecdotally, subtyping seems to be more intuitive for folks than row polymorphism/polymorphic variants, but of course then it’s hard not to lose a lot of the niceties HM affords..
How are you doing with the Lambda Set stuff? It looks absolutely impenetrable and I’m wondering if you have hot tips or a better description. How hard would it be to build on top of what we already have for HM?
I have taken a bit of a break from it due to some other commitments. @rtfeldman is working on a better version of what is currently implemented.
My fault in the existing implementation was attempting to do it in a minimal number of passes relative to the rest of a compiler. Pulling it out to a separate pass as the original authors of the Lambda Set paper (Morphic) did makes it quite straightforward. I have a toy compiler (online playground) demonstrating it (sorry if it’s a bit opaque).
The main tip I would have is to do it in a separate pass once you already have already specialized all generic types, assuming you have a specializing compiler. At that point, run HM-style inference to determine how function calls are propagated in a program (this is actually equivalent to inferring polymorphic variants via the method described above). If you don’t have a specializing compiler, you give up being able to specialize all call sites but you can run the inference pass in or out of band to specialize calls that are known to be direct.
One last thing to note is that the lambda set-style stuff is disjoint from the type system, since lambda sets are directly encoding values, and not types per-se. So while you can reuse code between the two, fundamentally there is no reason to tie the type system to function-call specialization.
Sorry if this is still a bit opaque, happy to dive into more details as needed (here or in DM)!
We don’t have specialization right now because all we have is run-time type checks :) With the addition of HM inference we begin the specialization journey. So id = x -> x is still one IR node and one C function right now.
If we tack on the lambda set stuff, where do you think we should make cut points to specialize or at least change indirect calls to direct calls? We only have two passes right now (infer and C codegen) but would be interesting to add another before codegen. Maybe this will force us to create an actual useful IR.
EDIT: The other day I was also wondering if it was a good idea (possible?) do even do normal worklist call graph / CFA, just to see something working. Maybe it could be useful to additionally filter/refine by type but ¯\_(ツ)_/¯
if you tack on the lambda set stuff you would need to do an inference pass before codegen, but then you can codegen the direct calls in-line (the inference is sufficient to direct how calls should be transformed). I don’t think you necessarily need to have an intermediate IR unless you want to for other reasons too.
yeah, lambda sets is CFA with a unification-based approach.
Roughly, it’s a collection of possible function (ie lambda/closure) values you might expect in a given place (eg variable containing a function with a given signature).
By tracking this precisely the compiler (as an optimization) can store the various closures in a variant/sum type like data structure, enabling stack allocation of closures, inlining, etc. This can be faster than using function pointers and allocating every closure on the heap (another popular way due to simplicity of implementation).
Given most lambda variables would have a single concrete definition, it makes it simple for the compiler to eg inline the function call.
Different languages approach the problem in different ways (eg zig allows concrete function values or else function pointers, julia assigns a nominal type per function or closure but also allows for function pointers, etc), but this is another way which I’ve read about being applied to newer languages with ML-like type systems since the closures can just be treated like polymorphic variants and you get optimization benefits flowing pretty straightforwardly.
Assuming 60 FPS is responsive enough, you can measure how many bytes you can copy with memcpy in 16ms and that should give you an idea of when this editor will start feeling slow when editing large files.
I love the comments from their GitHub discussion on “Why Go?”.
One of the top language engineers in the world makes a decision on which language to use.
Randos on GitHub:
It’s even worse: not just “one of the top language engineers in the world” but specifically architect of both the language being ported and architect of the language they’re saying it should be ported to.
The fucking presumption, the unmitigated arrogance of some people, woof.
The TypeScript dev lead posted this response about the language choice on Reddit, for anyone who’s curious:
Source: https://www.reddit.com/r/typescript/comments/1j8s467/comment/mh7ni9g
People really miss the forest for the trees.
I looked at the repo and the story seems clear to me: 12 people rewrote the TypeScript compiler in 5 months, getting a 10x speed improvement, with immediate portability to many different platforms, while not having written much Go before in their lives (although they are excellent programmers).
This is precisely the reason why Go was invented in the first place. “Why not Rust?” should not be the first thing that comes to mind.
I honestly do think the “Why not Rust?” question is a valid question to pop into someone’s head before reading the explanation for their choice.
First of all, if you’re the kind of nerd who happens to follow the JavaScript/TypeScript dev ecosystem, you will have seen a fair number of projects either written, or rewritten, in Rust recently. Granted, some tools are also being written/rewritten in other languages like Go and Zig. But, the point is that there’s enough mindshare around Rust in the JS/TS world that it’s fair to be curious why they didn’t choose Rust while other projects did. I don’t think we should assume the question is always antagonistic or from the “Rust Evangelism Strike Force”.
Also, it’s a popular opinion that languages with algebraic data types (among other things) are good candidates for parsers and compilers, so languages like OCaml and Rust might naturally rank highly in languages for consideration.
So, I honestly had the same question, initially. However, upon reading Anders’ explanation, I can absolutely see why Go was a good choice. And your analysis of the development metrics is also very relevant and solid support for their choice!
I guess I’m just saying, the Rust fanboys (myself, included) can be obnoxious, but I hope we don’t swing the pendulum too far the other way and assume that it’s never appropriate to bring Rust into a dev conversation (e.g., there really may be projects that should be rewritten in Rust, even if people might start cringing whenever they hear that now).
While tweaking a parser / interpreter a few years ago written in Go, I specifically replaced a struct with an ‘interface {}’ in order to exercise its pseudo-tagged-union mechanisms. Together with using type-switch form.
https://github.com/danos/yang/commit/c98b220f6a1da7eaffbefe464fd9e734da553af0
These day’s I’d actually make it a closed interface such that it is more akin to a tagged-union. Which I did for another project which was passing around instances of variant-structs (i.e. a tagged union), rather than building an AST.
So it is quite possible to use that pattern in Go as a form of sum-type, if for some reason one is inclined to use Go as the implementation language.
That is great explanation of “Why Go and not Rust?”
If you’re looking for “Why Go and not AOT-compiled C#?” see here: https://youtu.be/10qowKUW82U?t=1154s
A relevant quote is that C# has “some ahead-of-time compilation options available, but they’re not on all platforms and don’t really have a decade or more of hardening.”
That interview is really interesting, worth watching the whole thing.
Yeah Hjelsberg also talks about value types being necessary, or at least useful, in making language implementations fast
If you want value types and automatically managed memory, I think your only choices are Go, D, Swift, and C# (and very recently OCaml, though I’m not sure if that is fully done).
I guess Hjelsberg is conceding that value types are a bit “second class” in C#? I think I was surprised by the “class” and “struct” split, which seemed limiting, but I’ve never used it. [1]
And that is a lesson learned from the Oils Python -> C++ translation. We don’t have value types, because statically typed Python doesn’t, and that puts a cap on speed. (But we’re faster than bash in many cases, though slower in some too)
Related comment about GC and systems languages (e.g. once you have a million lines of C++, you probably want GC): https://lobste.rs/s/gpb0qh/garbage_collection_for_systems#c_rrypks
There was also a talk that hinted at some GC-like patterns in Zig, and I proposed that TinyGo get “compressed pointers” like Hotspot and v8, and then you would basically have that:
https://lobste.rs/s/2ah6bi/programming_without_pointers#c_5g2nat
[1] BTW Guy Steele’s famous 1998 “growing a language” actually advocated value types in Java. AFAIK as of 2025, “Project Valhalla” has not landed yet
Compilers written in OCaml are famous for being super-fast. See eg OCaml itself, Flow, Haxe, BuckleScript (now ReScript).
Yeah, I’m kind of curious about whether OCaml was considered at some point (I asked about this in the Reddit thread, haven’t gotten a reply yet).
OCaml seems much more similar to TS than Go, and has a proven track record when it comes to compilers. Maybe portability issues? (Good portability was mentioned as a must-have IIRC)
Maybe, but given that Flow, its main competitor, distributes binaries for all major platforms: https://github.com/facebook/flow/releases/tag/v0.264.0
Not sure what more TypeScript would have needed. In fact, Flow’s JavaScript parser is available as a separate library, so they would have shaved off at least a month from the proof of concept…
Also Nim.
Also Julia.
There surely are others.
Yes good points, I left out Nim and Julia. And apparently Crystal - https://colinsblog.net/2023-03-09-values-and-references/
Although thinking about it a bit more, I think Nim, Julia, (and maybe Crystal) are like C#, in that they are not as general as Go / D / Swift.
You don’t have a
Foo*type as well as aFootype, i.e. the layout is orthogonal to whether it’s a value or reference. Instead, Nim apparently has value objects and reference objects. I believe C# has “structs” for values and classes for references.I think Hjelsberg was hinting at this category when saying Go wins a bit on expressiveness, and it’s also “as close to native as you can get with GC”.
I think the reason this Go’s model is uncommon is because it forces the GC to support interior pointers, which is a significant complication (e.g. it is not supported by WASM GC). Go basically has the C memory model, with garbage collection.
I think C#, Julia, and maybe Nim/Crystal do not support interior pointers (interested in corrections)
Someone should write a survey of how GC tracing works with each language :) (Nim’s default is reference counting without cycle collection.)
Yeah that’s interesting. Julia has a distinction between
struct(value) andmutable struct(reference). You can use raw pointers but safe interior references (to an element of an array for example) include a normal reference to the (start of the) backing array, and the index.I can understand how in Rust you can safely have an interior pointer as the borrow checker ensures a reference to an array element is valid for its lifetime (the array can’t be dropped or resized before the reference is dropped). I’m very curious - I would like to understand how Go’s tracing GC works with interior pointers now! (I would read such a survey).
Ok - Go’s GC seems to track a memory span for each object (struct or array), stored in kind of a span tree (interval tree) for easy lookup given some pointer to chase. Makes sense. I wonder if it smart enough to deallocate anything dangling from non-referenced elements of an array / fields of a struct, or just chooses to be conservative (and if so do users end up accidentally creating memory leaks very often)? What’s the performance impact of all of this compared to runtimes requiring non-interior references? The interior pointers themselves will be a performance win, at the expense of using an interval tree during the mark phase.
https://forum.golangbridge.org/t/how-gc-handles-interior-pointer/36195/5
It’s been a few years since I’ve written any Go, but I have a vague recollection that the difference between something being heap or stack allocated was (sometimes? always?) implicit based on compiler analysis of how you use the value. Is that right? How easy it, generally, to accidentally make something heap-allocated and GC’d?
That’s the only thing that makes me nervous about that as a selling point for performance. I feel like if I’m worried about stack vs heap or scoped vs memory-managed or whatever, I’d probably prefer something like Swift, Rust, or C# (I’m not familiar at all with how D’s optional GC stuff works).
Yes, that is a bit of control you give up with Go. Searching for “golang escape analysis”, this article is helpful:
https://medium.com/@trinad536/escape-analysis-in-golang-fc81b78f3550
So the toolchain is pretty transparent. This is actually something I would like for the Oils Python->C++ compiler, since we have many things that are “obviously” locals that end up being heap allocated. And some not so obvious cases. But I think having some simple escape analysis would be great.
Yes, the stack/heap distinction is made by the compiler, not the programmer, in Go.
Why did you leave JS/TS off the list? They seem to have left it off too and that confuses me deeply because it also has everything they need
Hejlsberg said they got about 3x performance from native compilation and value types, which also halved the memory usage of the compiler. They got a further 3x from shared-memory multithreading. He talked a lot about how neither of those are possible with the JavaScript runtime, which is why it wasn’t possible to make tsc 10x faster while keeping it written in TypeScript.
Yeah but I can get bigger memory wins while staying inside JS by sharing the data structures between many tools that currently hold copies of the same data: the linter, the pretty-formatter, the syntax highlighter, and the type checker
I can do this because I make my syntax tree nodes immutable! TS cannot make their syntax tree nodes immutable (even in JS where it’s possible) because they rely on the
node.parentreference. Because their nodes are mutable-but-typed-as-immutable, these nodes can never safely be passed as arguments outside the bounds of the TS ecosystem, a limitation that precludes the kind of cross-tool syntax tree reuse that I see as being the way forwardHejlsberg said that the TypeScript syntax tree nodes are, in fact, immutable. This was crucial for parallelizing tsgo: it parses all the source files in parallel in the first phase, then typechecks in parallel in the second phase. The parse trees from the first phase are shared by all threads in the second phase. The two phases spread the work across threads differently. He talks about that kind of sharing and threading being impractical in JavaScript.
In fact he talks about tsc being designed around immutable and incrementally updatable data structures right from the start. It was one of the early non-batch compilers, hot on the heels of Roslyn, both being designed to support IDEs.
Really, you should watch the interview https://youtu.be/10qowKUW82U
AIUI a typical LSP implementation integrates all the tools you listed so they are sharing a syntax tree already.
It’s true that I haven’t watched the interview yet, but I have confirmed with the team that the nodes are not immutable. My context is different than Hejlsberg’s context. For Hejlsberg if something is immutable within the boundaries of TS, it’s immutable. Since I work on JS APIs if something isn’t actually locked down with
Object.freezeit isn’t immutable and can’t safely be treated as such. They can’t actually lock their objects down because they don’t actually completely follow the rules of immutability, and the biggest thing they do that you just can’t do with (real, proper) immutable structures is have anode.parentreference.So they have this kinda-immutable tech, but those guarantees only hold if all the code that ever holds a reference to the node is TS code. That is why all this other infrastructure that could stand to benefit from a shared standard format for frozen nodes can’t: it’s outside the walls of the TS fiefdom, so the nodes are meant to be used as immutable but any JS code (or any-typed code) the trees are ever exposed to would have the potential to ruin them by mutating the supposedly-immutable data
To be more specific about the
node.parentreference, if your tree is really truly immutable you need to replace a leaf node you must replace all the nodes on the direct path from the root to that leaf. TS does this, which is good.The bad part is that then all the nodes you didn’t replace have chains of
node.parentreferences that lead to the old root instead of the new one. Fixing this with immutable nodes would mean replacing every node in the tree, so the only alternative is to mutatenode.parent, which means that 1) you can’t actuallyObject.freeze(node)and 2) you don’t get all the wins of immutability since the old data structure is corrupted by the creation of the new one.See https://ericlippert.com/2012/06/08/red-green-trees/ for why Roslyn’s key innovation in incremental syntax trees was actually breaking the
node.parentreference by splitting into the red and green trees, or as I call them paths and nodes. Nodes are deeply immutable trees and have no parents. Paths are like an address in a particular tree, tracking a node and its parents.You are not joking, just the hack to make type checking itself parallel is well worth an entire hour!
Hm yeah it was a very good talk. My summary of the type checking part is
That is, the translation units aren’t completely independent. Type checking isn’t embarassingly parallel. But you can still parallelize it and still get enough speedup – he says ~3x from parallelism, and ~3x from Go’s better single core perf, which gives you ~10x overall.
What wasn’t said:
I guess this is just because, empirically, you don’t get more than 3x speedup.
That is interesting, but now I think it shows that TypeScript is not designed for parallel type checking. I’m not sure if other compilers do better though, like Rust (?) Apparently rustc uses the Rayon threading library. Though it’s hard to compare, since it also has to generate code
A separate thing I found kinda disappointing from the talk is that TypeScript is literally what the JavaScript code was. There was never a spec and will never be one. They have to do a line-for-line port.
There was somebody who made a lot of noise on the Github issue tracker about this, and it was basically closed “Won’t Fix” because “nobody who understands TypeScript well enough has enough time to work on a spec”. (Don’t have a link right now, but I saw it a few months ago)
Pretty sure he said it was an arbitrary choice and they’d explore changing it. The ~10x optimization they’ve gotten so far is enough by itself to keep the project moving. Further optimization is bound to happen later.
Work has been going on for years to parallelize rust’s frontend, but it apparently still has some issues, and so isn’t quite ready for prime time just yet, though it’s expected to be ready in the near term.
In my experience, once you start to do things “per core” and want to actually get performance out of it, you end up having to pay attention to caches, and get a bit into the weeds. Given just arbitrarily splitting up the work as part of the port has given a 10x speed increase, it’s likely they just didn’t feel like putting in the effort.
Can you share the timestamp to the discussion of this hack, for those who don’t have one hour?
I think this one: https://www.youtube.com/watch?v=10qowKUW82U&t=2522s
But check the chapters, they’re really split into good details. The video is interesting anyway, technically focused, no marketing spam. I can also highly recommend watching it.
Another point on “why Go and not C#” is that, he said, their current (typescript) compiler is highly functional, they use no classes at all. And Go is “just functions and data structures”, where C# has “a lot of classes”. Paraphrasing a little, but that’s roughly what he said.
They also posted a (slightly?) different response on GitHub: https://github.com/microsoft/typescript-go/discussions/411
Yes please!
This isn’t quite right. Trait objects are not themselves sized. The subsequent code sample works because of the
impl<I> Iterator for &mut I where I: Iterator + ?Sizedimplementation. Thecountmethod isn’t being directly invoked on the trait object, it’s being invoked on the&mutwhich is a concrete iterator implementation.You can prove this yourself by making your own custom
Iteratorimplementation that provides a custom implementation of thecount()method, and then invoking it via a&mut dyn Iterator(Rust Playground). If you do that, your customcount()won’t be called, the default implementation on the&mut Iinstead will be used.Is this considered a bug? I understand how and why works, but the code in your playground link is really counter-intuitive, it’s clearly a footgun. I wonder if this could be fixed?
I can’t quite follow this post.. How exactly are you getting the data from Dexcom? You mention HTTPS, so I’m guessing you get it from the Dexcom web services?
I do the same in my Garmin Watchface but I’m not happy with it, because it requires (1) the phone to be near you (2) the phone to have internet access. So I don’t see the data when flying, or out exercising without the phone.
It also adds about 30 seconds of delay between the phone receiving the data and the watch.
xDrip+ can act as a Dexcom receiver so it looks like they figured out the protocol, but I don’t know too much about BLE and I wasn’t sure if a Garmin watch can connect to a Dexcom transmitter as a receiver. Plus I hate Garmin SDK, the language (MonkeyC) is just awful. It’s clear that they have no idea how to design and implement a language.
Ideally I want the watch to act as a Dexcom receiver and remove the phone from the equation but I have no idea how. It would be great to collaborate!
(The last part is to anyone who’s interested, not just to the author of the post!)
Should I be excited about this development? I’ve never used Pebble but I’ve been looking for a smart watch that will give me control over BLE features of the watch and allow me to connect to other devices via BLE. Will this be possible with the new Pebble?
I also switched to Zed a few months ago after more than a decade of vim.
The main reasons why I keep using it are (1) the project-wide search screen with mini-buffers is quite good (2) out-of-the-box LSP integration just works.
Editing features in general are not as good as vim yet. Paragraph formatting (
gqin vim) and line joining (Jin vim) don’t work as nice, and it doesn’t have spell checking, which makes editing comment blocks painful.It also wants tree-sitter grammar for even the most basic editing features. I’m working on my own programming language, and it can’t even find matching parentheses (
%in vim) because I don’t have a tree-sitter grammar yet. The problem is tree-sitter grammars are extremely painful to implement, especially for indentation-sensitive languages. So for now I go back and forth between Zed and vim when editing.Finally, if you’re stuck with whatever when using Zed, you’re unlikely to get help, because the community is small and there aren’t a lot of discussions on sites like SO or on GitHub discussions.
It has a lot of potential though.
I do hope this unified treatment of code generation, generics and type inference under “comptime” becomes standard practice, as it looks very reasonable to the user. In Haskell we have typed TH which comes close, but also has some limitations in the types of terms that can be type-inferred (if you’re into experimental type systems, that is).
As a non-Zig user, my impression is that using comptime as generics has the exact same limitations as C++ templates: the generic code (or at least the usages of the generic type parameter) is not type-checked until it is actually used somewhere in the program, and this means that when you write generic libraries you don’t get static guarantees until you use them with example clients. This will make the experience much worse than proper generics, at scale. I am also worried about the quality of the editor-level type feedback in presence of heavy generics usage, for similar reasons.
(I’ve said this in the past and some Zig maintainers pointed out that Zig works hard to partially type-check code with comptime arguments and that it probably works fine in practice. My intuition rather stubbornly tells me that this will be very annoying in practice when used at scale.)
The problem is that when you say
comptime T : type, you don’t give any static information about what the code below actually assumes aboutT. If it handlesTas a completely generic/opaque type on which nothing is known, this is fine. But in practice most code like this will assume things aboutT, that it has certain fields, support certain operations, etc., and it will work fine because it will be used by callers with types that match these assumptions. But these assumptions are not made explicit in the generic function, and thus they cannot be reasoned about statically.What makes generics hard in most languages is the desire to type-check assumptions about them statically. For example, if a function is generic over a type-former (a parametrized type) such as
List, maybe you want to use subtyping in the body of the function, and so the type-system designers have to come up with a small static language to express variance assumptions about generic type-former parameters – it is one of the complex and annoying parts of Java generics, for example. They could also give up and say “well let’s just check on each usage type that the subtyping assumptions is in fact correct”, this would be much simpler design-wise, and the ergonomics would be much worse.Maybe “worse is better” and having a simple type system with worse ergonomics is indeed a good idea that will become standard practice. (It certainly helps in lowering the entry barrier to designing type systems, and it possibly makes it easier for programmers to be confident about what is going on.) But I remain skeptical of such claims, especially when they are formulated without acknowledging the notable downsides of this approach.
As a Zig user, fully agree with all of the above! Some extra thoughts:
While I am 0.9 sure that for simple-to-medium cases, declaration side type-checking leads to better ergonomics, I am maybe at 0.5 that there’s complexity tipping point, where call-site checking becomes easier to reason about for the user. In other words, I observe that in languages with expressive generics, some libraries will evolve to try to encode everything in the type-signatures, leading to a programming style where most of the code written manipulates types, instead of doing the actual work. I’ve certainly seen a number of head-scratching Rust signatures. Here’s a recent relatively tame example of this sort of dynamics playing out: https://github.com/rust-lang/rust/pull/107122#issuecomment-2385640802.
I am not sure that just doing what Zig does would magically reduce the overall complexity here, but it seems at least plausible that, at the point where you get into the Turing tarpit when specifying function signatures, it might be better to just use the base imperative language for types?
When comparing with C++, it’s worth noting that you get both instantiation-time type-checking and a Turing tarpit. A big part of perceived C++ complexity is due to the fact that the tools of expressiveness are overloading, ADL, and SFINAE. Zig keeps instantiation-time checking (or rather, dials it up to 11, as even non-generic functions are checked at call-site), but also simplifies everything else a lot.
Another dimension to think about here is crates.io style packages. It seems that declaration-checking plays a major role in SemVer — semantic versioning starts with defining what is and what is not your API. But, at the same time, the resulting ecosystem also depends on culture of making changes, not only on technical means to enforce it. And Zig’s package manager/build systems is shaping up to be the best-in-class general purpose small-scale dependency management solution. I am extremely curious what the ecosystem ends up looking like, after the language stabilizes.
Could you say a few words (or point us to some documentation) on what you think makes Zig’s package manager/build system the best?
There are no docs! As a disclaimer, Zig is a work-in-progress. If you want to just use the thing, it’s much too early for that, come back five years later!
That being said, why I am excited about a hypothetical Zig ecosystem:
First, Zig aims to be dependency zero. One problem that is traditionally hard in this space is how do you get the environment that can execute the build/packaging logic? There’s a lot of tools that, eg, depend on Python, which make building software at least as hard as provisioning Python. Another common gratuitous dependency is sh/bash and core utils. Yet another option is JVM (gradle, bazel).
In contrast, zig is a statically linked binary that already can execute arbitrary scripts (via
zig run) and can download stuff from the internet (viazig fetch). That is big! If you can run stuff, and can download stuff to run from the internet, you can do anything with no headache. What’s more, it’s not confined to your build system, you can write normal software in Zig too (though, tbh, I am personally still pretty skeptical about viability of only-spatially-memory-safe language for general purpose stuff).Second, I think Zig arrived at the most useful general notion of what is a dependency — a directory of files identified by a hash. From the docs:
There’s no special casing for “Zig” dependencies. You use the same mechanism to fetch anything (eg, in TigerBeetle we use this to fetch a prebuilt copy of
llvm-objcopy). I expanded on this a bit in https://matklad.github.io/2024/12/30/what-is-dependency.html. inb4 someone mentions nix: nix can do some of this, but it is not a good dependency zero, because it itself depends on posix.Third, the build system is adequate. It uses general purpose imperative code to generate a static build graph which is then incrementally executed. This feels like the least sour spot for general purpose build systems. While you get some gradle-vibes from the requirement to explicitly structure your build as two phases, the fact that it all is simple procedural code in a statically-typed language, rather than a DSL, makes the end result much more understandable. Similarly, while static build graph can’t describe every imaginable builds, some builds (at lest at a medium scale) are better left to imagination.
Fourth, Zig is serious about avoiding dependencies. For example, cross compilation works. From windows, you can build software that dynamically links a specific version of glibc, because the Zig folks did the work of actually specifying the ABI of specific glibc version. This, combined with the fact that Zig also is a C/C++ compiler, makes it possible to produce good builds for existing native software.
I like the theoretical idea of Zig being dependency zero, but in practice this ends up being horrible: if your toolchain is your bootstrap point, you’re chained at the waist to whatever version of the compiler you happen to have installed. Compare this to
rustup, which allows a single installation but will auto-detect and install the toolchain version required for each project. It’s not justrustupeither: there’s a reason that games (Veloren for example) separate the main body of the code from their installer/launcher: it allows the former to have a higher update cadence than the latter without enormous annoyance for the user.One elegant solution is to not install anything! I don’t have
zigin my PATH, I always use./zig/zigto run stuff. For example, hacking on TigerBeetle isHaving a tiny .sh/.bat to download the thing is not elegant, but is not too bad. Certainly simpler than rustup installer!
Actually, I should have added “Zig promotes local installs” to the list above: Zig’s pretty clear that
make installis generally a bad idea, and that you should install stuff locally more often.And then, as kristoff says and Go demonstrates, nothing prevents the toolchain from updating itself. Zig already JIT some lesser used commands (compiler ships its components in the form of the source code), it certainly can learn to upgrade itself.
build.zig.zon(the Zig equivalent ofpackage.json) supports specifying a minimum version supported of the compiler toolchain. This field is currently not used by the toolchain, but there’s a proposal to have Zig download another copy of Zig when the installed version doesn’t satisfy the constraint declared inbuild.zig.zon.This is not true, the toolchain can also be responsable to manage versions, especially since everything in Zig is also compiled statically, a.k.a. how Go does: https://kokada.dev/blog/quick-bits-go-automatically-downloads-a-newer-toolchain-if-needed/.
But even without adding this support in the toolchain itself, you could have a zigup project responsable to auto-detect and install the toolchain in the required version of each project.
That’s part of the issue with what Wedson presented, and that Ts’o reacted to. Wedson had a very nice slide with a call that returned a very extensive type definition and claimed that was good.
fn get_or_create_inode(&self, ino: Ino) -> Result<Either<ARef<INode<T>>, inode::New<T>>>.Don’t get me wrong, Ts’o’s reaction was very bad. He should have behaved better. But on the technical merit, I think Wedson missed the mark.
I can’t see similar thing happening with Zig (at least not anytime soon) - not because you can’t do it, but because the ecosystem around the language seems to be allergic to cramming all things into the type system. Comptime presents itself as an easy escape valve to keep things simple.
What signature would you have preferred?
This feels similar-lish:
https://github.com/ziglang/zig/blob/6a21d18adfe9ae4ff7f4beacbd4faed4d04832b8/lib/std/mem.zig#L4079
But than, it needs to be compared with safe transmute which is quite an infra…
I am still not sure what I think here. The signature is quite impenetrable either way! But then, the fact that I can just write the logic for “is this reasonable to transmute?” like this is neat:
https://github.com/tigerbeetle/tigerbeetle/blob/5b485508373f5eed99cb52a75ec692ec569a6990/src/stdx.zig#L312
As a Go user, a lot of problems other languages solve with complex type constraints I see get solved with
func f(x any) { if !matchConstraint(x) { panic("type must foo and bar") …. (I do it in my own code here.) In practice it usually isn’t a problem because you catch the panics with even minimal testing. It is unsatisfying though.Using
anyhas lots of downsides though, for one you lose the help of the compiler and your tooling to e.g. auto-complete a method. It is fine for a self contained method in a relatively small code base, but starts to get hairy as your code increases in complexity.Wait until you learn about languages where there is nothing except any! It’s a crazy world out there.
I feel like this doesn’t entirely preclude better ergonomics though, at least if there were something like C++ concepts. Then you’d at least be able to observe the signatures to see what the expectations of the type are.
IME this actually doesn’t affect the day-to-day ergonomics that much; ADL fails are usually pretty obvious in client code unless you’re doing some REALLY cursed library stuff, and SFINAE errors are actually pretty decent these days. The big thing that wasn’t fixed until concepts was just goofs like “I thought I had a map and not a vector so I passed a value type as the allocator” and suddenly you have like a zillion errors and need to fish out the actual goof. Zig…well it kinda fixes that w/ generally shorter instantiation traces, due to enhancements like “actually having loops”, but it’s still not super great.
Note: while writing this reply I ended up encountering this blog post, Zig-style generics are not well-suited for most languages, which makes basically the same point.
I personally don’t find this to be a problem in C++ … Whenever I write generic code, I write a unit test, with an instantiation
IME, that completely solves the problem, and it’s not like I didn’t need to test that code …
This suggests that your programming style around generics is fairly simple, and therefore easy to test – there is not a lot of conditional logic in your generics that would require several distinct tests, etc. You would also do just fine in Zig if you were to write similar code. This is good news!
But several members of the C++ design community have spent a decade of their life working on C++ Concepts to solve these issues (the first proposal started in 2005-2006 I believe, it was planned in C++0x that became C++11, and then dropped because too complex, and then “Concepts Lite” appeared in 2016 but were rejected from C++17 and finally merged in C++20). I believe that this dedication comes from real user-stories about the perils of these aspects of C++ templates – which are largely documented online; there was a clear perceived need within the C++ community that comes from the fact that a lot of template code that many people are using was in fact much more complex than yours and suffered from these scaling issues.
Yeah definitely, I think it’s best to keep to simple generic code.
I don’t find the philosophy of “maxing out” compile time in C++ to be effective, and I don’t see the programmers I admire using it a lot, with maybe a few exceptions. (e.g. Carmack, Jeff Dean, Bellard, DJB, don’t really care about compile time programming as far as I can tell. They just get a lot of work done) There was also a recent (troll-ish) post by Zed Shaw saying that C++ is fun once you push aside the TMP stuff
All of Oils is written with Python as the metaprogramming language for C++, with textual code gen. Textual code gen takes some work, but it’s easy and simple to reason about.
IMO, it’s nicer than using the C preprocessor or using the C++ template system. (Although we also use the C++ template system for a few things – notably the compiler is the only thing that has access to certain info, like sizeof() and offsetof() )
The main thing that would make it better is if the C++ type system didn’t have all these HOLES due to compatibility with C! I mentioned that here:
https://www.oilshell.org/blog/2024/09/retrospective.html#appendix-more-viewpoints
https://lobste.rs/s/wtk2rk/types_comparison_rust_zig#c_5lbiuf
(although I also forgot to mention that the C++ type system is extremely expressive too, what I called “hidden static expressiveness”)
The other main downside is that you need a good build system to handle code gen, which is why I often write about Ninja!
So I might think of comptime as simply using the same language, rather than having the Python/C++ split. I can see why people might not like that solution, and there are downsides, but I think it works fine. The known alternatives have steep tradeoffs.
Are you familiar with Terra? https://terralang.org/
Sounds like you rolled something similar yourself, with Python as the meta language for C++.
Yeah I always found Terra very interesting, it’s linked here: https://github.com/oils-for-unix/oils/wiki/Metaprogramming
Unfortunately the implementation is “research-grade”: https://erikmcclure.com/blog/a-rant-on-terra/
Metaprogramming has a pretty common taxonomy where you decide which part of the compiler pipeline you hook into:
I don’t think any way is strictly better than the others – they all have tradeoffs.
But we are doing #1 and I think Lua/Terra is more like #4, or #3.
But spiritually you can write the same kinds of programs. It just means that we end up generating the source code of C++ functions rather than having some kind of API to C++.
Of course you often write little “runtime” shims to make this easier – that is sort of like your API to C++. The garbage collected data structures are the biggest runtime shim!
I do still think we need a “proper” language that supports this model.
It could be YSH – What if the shell and the C preprocessor were the same language? :-)
comptimeextends this to all code; anything not reachable from anexportas a general rule. It’s what allows for the dependent-esque decision making, cross-compilation/specializing using normal control flow, and general reflection. Without it, other langs default to a secondary declarative system like Rust’s#[cfg()]or C’s#ifdef. It’s a bit restrictive though, so a higher level build script (like proc-macros in Rust) is used for similar comptime effect.They technically can given comptime reflection (i.e.
@typeInfo) is available. It just ends up being quite verbose so in practice most rely on duck typing instead.Ergonomics ok for now given you can
x: anytype. What sort of environments do you see it causing the most annoyance? Im thinking maybe for cases where people learn exclusively through an LSP.I’m not saying that all uses of
comptimeare bad, and maybe it’s nice when it replaces macros for conditional compilation. I was pointing out that it is probably not the magic answer to all problems about “generics and code inference” that should become “standard practice”.I would expect the usual downsides of late-type-checking of C++ templates to show up:
Tprovided does not offer operationfobar, is it a typo in the template code or a mistake of the caller? If you write generic code with, say, type-classes or traits (where the expected operations are explicitly listed in the class constraint / trait bound present in the generic code), you can tell when there is a typo in the generic code and not blame the caller.Maybe Zig has (technical or social) solutions to some or all of these problems, and/or maybe the people explaining how great
comptimeis are too naive about this. If there is some secret sauce that makes this all work well, then it should be carefully explained and documented along the explanation of how simplecomptimeis; this is important in the context of encouraging other languages to adopt this approach (as done in the post I was replying to), they need to also understand the pitfalls and how to avoid them.The first point is sometimes an issue for cross-compilation especially. Zig’s ability to do so from any machine (
-target whatever) makes it easier to test locally but in practice this error is often caught by CI.Error messages are surprisingly readable; “Type does not provide operation” is usually the caller’s fault (genuinely never seen it be the callee’s - whats an example of that?) and can be figured out through docs or variable naming. A good example of this is forgetting to wrap the format args parameter for
std.fmt.formatin a tuple.Comptime speed does indeed become noticeable in larger projects. But its primarily due to reflection and constexpr execution rather than type-checking (AFAIK that part alone is always fast even for multiple nested instantiations).
I dont think there’s secret sauce. You tend to either 1. not run into these 2. figure them out intuitively / with a little help due to lacking documentation or 3. cannot adjust / dont prefer it, having come from other langs. After the first or second time hitting them, it becomes a non-issue (like eager-PRO). It’s similar to how zig-folk recommend reading the stdlib to learn the language; wouldn’t really be a good idea other languages like C++, Rust, etc. but makes perfect sense (and works) in Zig.
I once tried using stdlib JSON decoder to decode some structure that contained
std.hash_map.HashMap. Let’s say that the error wasn’t clear at all why it is happening and how I can resolve it. It is especially painful when it happen deeply within some obscure internals of something that is mostly out of your control.Zig is nice, but yeah, their generic errors make me remember old C++ templating failures.
Curious what it looked like. The worst cases IME are when it doesnt print the trace due to compiler bugs or when it gives
error: expected type 'T', found 'T'which is pretty unclear. Or the slightly easier (but still annoying) case ofexpected T(..., a, ...), found T(..., b, ...).Imaginary scenario: for scientific programming, there is a naming convention for types that satisfy a certain set of operations, that comes from the important (imaginary) library ZigNum. Your project is using library Foo, which implements datatype-generic algorithms you care about, and also ZigNum directly – calling generic functions from both on the same types. The next version of ZigNum decides, for consistency reasons, to rename one of the operation (their previous name for the cartesian product was a poor choice). Then you code starts breaking, and there are two kind of errors that are displayed in exactly the same way:
If ZigNum would export a [type-class / module interface / concept / trait] that describes the operation names it expects, then compiling Foo against the new version of ZigNum would have failed, blaming the code (in Foo) that needs to be updated. Instead the error occurs in your own user code. If the person encountering this failure happens to be familiar with ZigNum and Foo, they will figure things out. Otherwise they may find this all fairly confusing.
Is ZigNum here an interface or an implementation? Having difficultly following the confusion: “A uses B. I just updated B and compiler says A started breaking on B stuff. I probably need to update A too.” seems like a fair reaction.
The error would occur in Foo, but zig errors are stack traces so the trace would lead back down to your code. This scenario however still looks like its the caller’s fault for passing incompatible types to a library. Something similar can also happen when you compile a zig 0.11.0 codebase (with dependencies also expecting a 0.11.0 stdlib) using a zig 0.13.0 compiler.
Well articulated and leads to a fascinating bit of reasoning.
First thought is, “well, you need multiple phases then.” Execute the comptime code, settle on what it produces, and then typecheck the code that relies on it.
But a moment’s thought shows that: (a) you’d eventually need 3 levels, sometimes 4, etc. (b) … and this is really just plain old code generation!
So we of course face the same fundamental issue as always. Wording it in terms of Lisp macros, you need to be able to flip back and forth between using the macro, and seeing/understanding the full expansion of the macro.
What we need is an outstanding solution to that fundamental problem.
C++ is gradually adding things that you’re permitted to do in
constexprcontexts. You can now allocate memory, though it must be destroyed at the end of the constant evaluation. Generalising this much further is hard because the language needs to be able to track pointers and replace them with relocations, which is not possible in the general case for C/C++ (pointers can be converted to integers and back and so on). That’s mostly solvable, but there are also problems with things like trees that use addresses as identity, because even the relationship between the addresses at compile time isn’t constant: if I create two globals and put them in a tree, I after COMDAT merging and linking I don’t know which will be at a lower address.Being able to merge the expression and type languages is very nice, but you either need to be able to create types at run time, or have a subset of the expression language that is only available at compile time. Smalltalk takes the former approach, C++ is quite heavily entrenched in the latter.
I don’t understand the point about streaming, you can stream JSON just fine. We support parsing JSON in chunks in the Dart standard library.
JSON streaming works fine but it needs minimal buy-in on the protocol end that many popular protocols (cough JSON-RPC cough) manage to flounder. So many APIs have
{"type": "Name", "data": {}}… totally unstreamable.While that is possible, you may encounter pretty basic parse errors later. E.g. an object might not be properly closed, etc.
If you mitigate against that, you can certainly parse JSON in chunks.
In my experience streaming isn’t well supported in the json library world. I’m getting flashbacks to dealing with >10GB objects when trying to recover a corrupt Cassandra database – their recovery tools would generate files that other tools in their suite could not consume.
Like Protobuf handles unknown fields any better?
If you’re sending me unknown fields, as, in they’re not in my published schema, I’m either ignoring them if I’m honouring Postel, or you’re getting a 400 Bad Request.
I honestly can’t think of a reason why I would accept unknown fields you’re POSTing to my API.
And if JSON is so bad, you need to ask yourself why it’s so obiquitous.
Also, streaming parsers for JSON exist. I can’t speak to their implementation, but I’ve seen them.
That’s really never been a good argument. It’s popular, like many other things, because it’s the easiest format for the first few hours/days (especially when javascript is involved). By the time the (numerous) downsides become more apparent, it’s too late to change your service/data/protocol.
What’s the problem with protobuf unknown fields? I checked the official Dart, Java, Python, C++ implementations, they all handle unknown fields.
You probably shouldn’t. The protobuf guide says:
Kenton Varda’s reflections on the design of Protocol Buffers (protobufs):
Yeah, that’s why I mentioned ignoring unknown fields. But generally in a distributed system I’d use a schema registry like Apicurio so that when a publisher uses a new version of a schema, consumers can pull it down as needed.
Scheme registries are nice— I’ve used buf— but it doesn’t solve the fundamental problem that old consumers will run at the same time as updated consumers.
Ingress services can do what they want with unknown fields, but middleboxes need to pass them unmolested.
I also wrote about structural editing a few weeks ago: https://osa1.net/posts/2024-11-02-structural-editor.html.
I think we need a more structural editing solution, but we cannot go fully structured: that will require either inventing a new language (extremely difficult on its own), or supporting sometimes hundreds of types of expressions and statements in a structural way (not sure if possible conveniently).
What I propose in my blog post is a middle ground where you have structural editing at the top-most layers, starting from packages to statement/expression level, and from there you edit as before. I think it can be done, and should give us a lot of the benefits of structural editing.
I got around this by inventing a new language that isn’t a programming language but is rather a data description language not unlike HTML. Most people forget that structured editing is a solved problem on the internet to the extent that I’m using a live structure editor to compose this post right now.
You don’t need incremental parsing even. Parsing from scratch is fast enough most of the time.
IntelliJ doesn’t generally do incremental parsing, and yet it has full access to syntax tree all the time.
Incremental parser is helpful, but by no means it is table stakes.
What you need though is resilient parser, a parser that can deal with incomplete syntax. This is table stakes, and not typically available.
Other that that, agree with a thesis: almost everything you can get with a structural editor you can get faster and cheaper by just writing a parser which doesn’t bail on the first error, and you get all text-editing goodies like multiple cursors for free.
See https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html for explanation of resilient parsing that works in production.
In some sense, one can do anything in manually written parsers if one has the skill and the patience to do so. I hope I’m not claiming that Wagner’s approach does something that’s impossible in other settings!
That said, Wagner’s approach does have some cool things that can be harder (not impossible, but harder) in a “reparse everything” setting. For example, its approach to error recovery can use “history”: if you make a program syntactically invalid it can use a past parse of that part of the program to try and fix it, and then move on. I don’t think that’s the only thing one needs to do for error recovery – it doesn’t work very well for new portions of a program, for example – but it’s an example of something that requires some sort of memory / caching.
I think there are cases where manually written parsers take less skill and patience
i.e. not everyone has a good time writing a Treesitter grammar – it depends on what you’re trying to parse
https://lobste.rs/s/9huy81/tbsp_tree_based_source_processing#c_bfbtbr (thread about Markdown and shell and the Helix editor, also linked in my top-level comment)
I didn’t try the resilient LL(1) technique, but it seems like it could be a good mix of powerful and expressive vs. easy to write. Obviously it again depends on the language
I am trying to decide if shell is a special case or not, as far as the complexity of the syntax … I think JavaScript is starting to resemble shell, because you have JSX literals in JS, and then you have JS and CSS in HTML, etc. You also have TypeScript
i.e. there are more arbitrary interleavings of composed languages in modern JavaScript.
I think the problem is that the original authors of those tools are NOT necessarily using grammars, so a given metalanguage can’t necessarily handle what they have done with arbitrary code, at least not easily.
I wouldn’t say it’s exactly a special case, because there are a number of other languages whose grammars can not be specified in a way that we can meaningfully statically reason about (give me an LL/LR grammar and I’ll guarantee strong properties about it; give me, say, a PEG and… I can’t). But it is definitely in the “I wish the syntax hadn’t evolved in this way, because it’s difficult to reason about for humans and machines” category!
Yeah I think shell and Ruby have similar syntactic complexity, judging by this post on “weird lexical syntax”
https://justine.lol/lex/
and by the recent posts on the Prism Ruby parser:
https://lobste.rs/s/4jpfyy/prism_2024_history_ruby_parsers
Shell has the same issue that Ruby has – you have to parse it to lex it:
A reason in shell is that
has 1 left paren, and 2 right parens, and you have to parse to know where the
$(ends. You can’t just lex.And I also think that complicates any kind of incremental parsing, if the lexer has to invoke the parser.
So then to me a very fruitful research question is to find a parsing metalanguage that can express shell and Ruby (and JS and C++, etc.)
I think Treesitter comes very close, but doesn’t hit the mark. Again, to the authors’ credit, they tested it on some of the most difficult languages, but perhaps not the Ruby/shell level of difficulty.
I noticed that the Wagner incremental lexing can accept arbitrary lexers via runtime instrumentation, rather than static analysis. (notably, Treesitter doesn’t implement Wagner incremental lexing – though you have to use its peculiar interface!)
On the other hand, Wagner incremental parsing is grammar-based. But IMO this restriction makes it infeasible for shell and Ruby. I suppose it’s an open question if some approximation is “good enough”, but I don’t think so, and I don’t see it in practice.
Originally I thought I would use PEGs for https://www.oilshell.org/, but PEGs don’t traditionally separate lexing and parsing, and there is a non-trivial interface to the lexer in OIls. For example, there is a stack of “hints” in the lexer to to find the closing
)in the case above, and there are a few other mechanisms too.But our parsing style [1] is not unlike PEGs, and it is expressive. It turned out to be capable of expressing 4 interleaved sublanguages with different lexical syntax, as well as 6 or so mini-languages. (We also interleave with a generated parser!)
I haven’t looked in detail at work on incrementally parsing PEGs [2], but if making PEGs incremental is possible, then I think making the Oils model incremental is probably also possible.
That is, recast it as something more like a set rather than an algorithm, like PEGs. I think in practice having the lexer/parser separation is useful, and it probably doesn’t complicate the theory too much (?)
As a concrete example, PEG has “lookahead assertions”. Somewhat late in the Oils development, I added a method to “look ahead with a certain lexer mode” to handle a few language constructs. A lexer mode is simply a mapping of regular languages to tokens.
So that kind of thing is a small difference that I think should be possible to formalize, and recast as a set, although certainly there could be other issues that make it harder.
I would also conjecture that if such a metalanguage can handle shell, it can handle Ruby and JavaScript and TypeScript.
C/C++ may need an additional hack for the symbol table -> lexer feedback, and possibly the “most vexing parse”.
[1] How to Parse Shell Like a Programming Language - https://www.oilshell.org/blog/2019/02/07.html
https://github.com/oils-for-unix/oils/wiki/Why-Lexing-and-Parsing-Should-Be-Separate
[2] e.g. https://people.seas.harvard.edu/~chong/abstracts/YedidiaC2021.html
This has been my experience, having written a from-scratch Ruby parser/interpreter/etc. that gets all the hard stuff right — doing it the traditional lex/yacc way, you need many “lexical tie-ins” (i.e. situations where the parser modifies lexer state).
You can use a just-in-time lexer without falling all the way back to feeding the parser the characters one by one…
This is why the BABLR core is expressed as a GLR parser VM not an LL VM. Effectively you “just write the parser”
AFAICT Rocq (née Coq) is LL1 but parsing requires partial evaluation (extensible syntax with notations let one sentence change the parser before it parses the next one). I’ve only heard dire warnings about trying to implement your own parser.
IntelliJ Java parser is incremental. It is absolute table stakes. Without it you wouldn’t be able to get the snappiness that IntelliJ has even in modest files. Source: wrote lots of code in IntelliJ back then. Including lots of different parsers.
Thanks, I’ll double check this! Let me be more precise about my current beliefs about “generally doesn’t do” for the record, to pin down exactly how wrong I am. This is about the state around 2016-2017, haven’t looked at the code much since then:
Hm, I think this is basically right? Java is parsed incrementally, but there’s no direct support for incrementally in GranmarKit and many other language are not incremental. In particular, Python only grew support for incremental parsing this year:
https://github.com/JetBrains/intellij-community/commit/ba6015d27f49636a9824db4e063fdfc17618b0ef
Which is to say: incrementality is useful, but you probably can get by without it. This is in contrast to resilience, without which the thing simply won’t work most of the time.
That being said, my original wording is misleading! It does imply that Java parsing is not incremental, and that is plain wrong, thanks for chiming in here to correct that!
I don’t have IntelliJ around anymore but I bet that if you open 20k lines file and start typing you could easily tell which parser is incremental and which is not.
So you’re probably right: it is not essential. But if you want to dethrone IJ, then it is :)
Sorry, don’t know anything about grammar kit. Last time I touched idea was probably 2008-2009 :) So you should replace “is” with “was” below.
As for Java incremental parser: it is important to understand that IntelliJ incremental parser is not optimal: i.e. it doesn’t guarantee minimal reparse, but something that works well in practice. E.g. if I remember correctly, code block is the unit of reparse, which could still be pretty big but is much smaller than the whole file.
Another case where incremental parsing is essential is when you type in ‘{‘: you don’t want full file structure to break.
Additional aspect of incrementality is to detect when parse yields the same tree structure and do not generate node updates (I’d call this incremental parse tree).
And on somewhat generic note: to be snappy you need to press ctrl+space and see completion in < 100ms. That includes doing a lot of work, re-parsing and re-resolving lots of files, which means that in reality parsing update should be on the order of milliseconds. We’ve got Eclipse engineers including EG coming to our boothes and asking why are we so fast? They never really got that it starts from the lowest level of code manipulation.
PS all credit for the speed goes to incredible kip for building PSI and later max.
Yeah, that’s also a very important point: you don’t need to invent a general incremental parsing algorithm, a simple heuristics work and it doesn’t actually require modifying the parser itself much.
One related anecdote here is that rust-analyzer included more or less the same block reparsing heuristic from the beginning, but, as far as I am aware, it is not actually enabled still. Not sure if this is because computers in 2018 were faster than in 2008, because its JVM vs Rust thing, or due to inherent asynchrony of LSP, but parsing never was near the top of cost-centers for completion, it was always Rust global-ish type inference with traits.
I think the main use case for incremental parsing would be as a basis for incrementalizing complex and costly analyses, maybe even compilation.
Imagine analyses (or even compilation) implemented with queries like “find the main function”, “get constructors of type X” etc. and a framework that records queries done to answer one query, and cache results.
(I think the idea is similar to Rust’s Salsa and/or Adapton, but I don’t have too much experience in any of them, so I’m not sure.)
Incremental parsing (as described by Wagner’s thesis, mentioned in the blog post) gives you the changed nodes in the AST, which you can use to invalidate results of queries that use those nodes, and start recomputing from there.
Without incremental parsing you have to compare the program AST before and after an edit to find which nodes are updated and invalidate query results based on that. I suspect it may be more efficient with incremental parsing.
Not sure! The thing is, if you add a blank line at the start of the file, you need to recompute all error messages (as they include line numbers) but keep the errors themselves (as nothing about the semantics of the file changes).
The way this works is that you have a sort-of recompilation firewall query, which takes raw syntax tree, and splits it into volatile parts (text offsets, specific concrete syntax choices, etc) and stable parts (the set of names defined in a file). And most of costly recompilation is driven by the changes in that small, stable part. And, as the firewall query is arbitrary code, its is kinda hard to incremntalize it automatically, but also it is cheap itself, so diffing its results is fast enough.
IOW, you can’t directly feed incremental tree updates into semantic analysis.
Why not just compute the error messages on the fly using the current positions? Sum trees make it log(n) to figure out line and column information on the fly without needing to store it
Another interesting point related to this topic might be what Unison does. To my knowledge, it stores basically “AST-nodes” in its own, normalized format. This gives the language automatic deduplication of identical functions (even when they are not textually identical, only semantically, e.g. whitespace difference).
Treesitter’s original application is smart syntax highlighting, and Treesitter is incremental … I’m pretty sure that will be too slow without incremental parsing.
e.g. compare it with Vim – it updates on every keystroke, does the weaker kind of syntax highlighting, and it is line-based.
If you want syntax highlighting be as responsive as Vim, and if Treesitter were NOT incremental, I don’t think that would work well. I think a full parse is too slow on every keystroke
I think IntelliJ must have more Vim-like syntax highlighting, not something like Treesitter? Not that this is bad, I think there can be a better compromise than Treesitter.
Although I kinda want to investigate some kind of “coarse parsing” first. So instead of using a line as a window Vim, then maybe you can use some delimiters like
{}. Although then that also has the resiliency issues.Not a good point of comparison as vim (to the best of my knowledge) doesn’t do any “parsing” so much as it does “brute force regex all things” with different regex rules for each syntax element. I don’t think it does it just once, either - pretty sure it tries repeatedly as the “syntax window” shifts. You’d be laughed out of the ballpark if you shipped a compiler (or whatever) that “parsed” your language in the same fashion vim does.
(This applies to neovim as well, but neovim has a still-in-the-works “native” TreeSitter integration to change that.)
I’m comparing them because both vim and Treesitter do syntax highlighting, and I believe Treesitter is incremental because doing full parses would be too slow for that use case.
I also think it should be possible to get the best of both worlds – accuracy and speed.
Since I’m in a memory trip lane: IntelliJ highlighter is multi-layered. On the lowest level highlighter uses lexer information, but keeps adding more highlights when there’s more information available. That includes syntax trees and even resolved references (semantic highlighting).
I wrote a syntax highlighter using libclang around 15 years ago and it did three things:
It was not incremental and the syntax highlighting often lagged a second or so behind (on a 1.2 GHz P3 Celeron), but it was pretty usable.
Tree-sitter is not the right solution if you only need syntax highlighting, syntax highlighting can be done with a lexer/tokenizer because you don’t need the tree structure for syntax highlighting, and lexing will be much faster to run from scratch and also easier to make incremental if it’s still not fast enough.
Unless you’re using a language like C++ where you can’t tell the difference between a variable declaration and function declaration without type information.
you need LSP semantic highlighting to correctly highlight Most Vexing Parse, tree-sitter doesn’t work (iirc it always highlights it as a function declaration)
If you need type information you also can’t do it properly with a parser.
I am kind of going on a tangent here, because the original post is about structured editing, not syntax highlighting
But the original goal of Treesitter was to use grammatical structure for syntax highlighting, not just lexical structure, like say Vim or SublimeText. This was clearly stated in one of the talks - https://tree-sitter.github.io/tree-sitter/#talks-on-tree-sitter
Tree-sitter enables reference highlighting, where various identifiers can be highlighted differently depending on whether they’re referencing a variable, function, parameter, constant, etc. GitHub uses this for some languages, and also extends it to cross-file reference resolution with stack graphs. Nvim-treesitter does have in-file reference highlighting but it is very slow so I usually disable it once the file grows beyond a certain size.
That’s exactly the thesis of matklad’s post- it’s often easily fast enough without incremental parsing. I have had similar experiences with parsing in response to keystrokes in an editor, and you can see a lot of LSP implementations (which provide “semantic” syntax highlighting based on the full parse tree) also work this way. This includes IntelliJ- as matklad put it, “it has full access to syntax tree all the time.” The expensive thing here is usually not parsing itself but all the analysis done on the result.
It’s possible tree-sitter itself might be too slow without incremental parsing, but tree-sitter uses a relatively expensive parsing algorithm (for good reason, don’t take this as a dunk on tree-sitter in any way) so that wouldn’t really be indicative of the general “parse from scratch” approach. (At the same time, outside of syntax highlighting, I have done some benchmarking of non-incremental tree-sitter against things like clangd, and it’s still much faster than those “traditional” frontends…)
For tree sitter, two things are importnat:
Well I sort of changed the subject from structured editing to syntax highlighting
But I would say you should have a 10-20 ms budget per keystroke, for syntax highlighting. (As a data point, 16.6 ms is 60 frames per second). Ideally it would be (much) less than 1 ms, but that’s a maximum. Because the CPU has to do other things too.
That’s definitely enough to parse small files, but large files are a problem.
Many editors and IDEs choke on large files, while Vim generally doesn’t. One solution is to just bail out for large files, since 99% are small. You can “degrade” to a text editor in that case.
I’m not sure of the exact threshold, but I think it’s pretty easy to find 100K line files that most tools choke on, e.g. this kind of file https://github.com/microsoft/TypeScript/blob/main/src/compiler/checker.ts
Important clarification from mikea below: for Java, IntelliJ is incremental. But it’s not incremental “by default”, languages have to opt-into incrementally, and many don’t, or do it rather late in the lifetime of a particular language plugin.
That’s the crux of caching: you don’t need it if the base system can handle the load. I’d go even further and claim that if language and compiler are co-designed for efficiency, you might not even need incremental compilation majority of the time.
Unpopular opinion: I agree with Chris Lattner that constraint generation/resolution based type checkers are a dead end in terms of UX. What he calls context-insensitive type checkers result in better error messages and faster compilation.
From what I understand this is more an issue with the design of Swift’s type system, i.e. the combination of subtyping, ad-hoc overloading (based on type, including return type polymorphism) and global type inference. This is well known to be a problem if you are familiar with the research on type checking, both for performance and usability, and there are approaches to deal with it, and to avoid the unrestricted mixing of problematic features as is seen in Swift.
You can have fast type inference, but it does mean designing your type system with that in mind. Adding in bidirectional typing to direct the flow of information through the type checker can be great for usability and performance too, giving type errors closer to the source of the problem based on annotations provided by the programmer.
Also note that Hindley Milner does not require generating and collecting constraints, you can also perform unification destructively as you go, which greatly improves performance (at the expense of biasing your type errors based on location. edit: looking at the blog post this is actually the approach it takes).
I asked Chris about this and he clarified that he meant that specifically in the context of Swift, not for languages in general. Here’s a recording where he clarified what he meant by that:
https://www.youtube.com/watch?v=ENviIxDTmUA&t=4379s
Also, the language that set the bar for high-quality error messages is Elm, which uses Hindley-Milner type inference and has a very fast compiler, and the Rust team cited Elm as the inspiration for the overhaul of their error messages which gave Rust a reputation for nice error messages:
https://blog.rust-lang.org/2016/08/10/Shape-of-errors-to-come.html
Oh, that’s a much better, nuanced clarification! Pretty much addresses all the stuff in my comment.
Thanks for clarifying it. I would be curious to see the Reddit/HN comment (didn’t find it myself).
Let me give you an example. Take this Rust code. The error message it produces:
To me, the error message is hardly nice. I know what’s going on here:
tokio::sync::RwLock::write()borrowsctx.fieldfor lifetime'athat’s limited toasync_fn()scope. Whereastokio::task::spawn_blocking()takes a closure which is'staticand thus all lifetimes within the closure must be'staticas well. A type error.Now, look at how the explanation differs from the error message itself. There’s multiple problems here:
borrowed value does not live long enoughpoints toctx.fieldbut there’s no borrowing (&) visible at this point in code. The actual borrowing is elsewhere — it’s thewrite(&self). It should show up in the error message IMO.argument requires that ctx.field is borrowed for 'staticdoesn’t say, nor points to what “argument” exactly. There’s multiple arguments within the body of that function so it’s imprecise.Oh I just brought up the Rust error messages as an example of a non-HM language that overall has a reputation for nice error messages (your mileage may vary, but the common view is that Rust’s error message quality is among the best) and that its error messages were inspired by a HM language.
That’s not a common view at all. Rust survey results indicate only around 2% of respondents are content with current error messages: https://blog.rust-lang.org/2024/02/19/2023-Rust-Annual-Survey-2023-results.html
Respondents aren’t content with the current error messages, but those error messages are a damn sight better than most of the competition! See how a recent post advises users into letting the compiler guide them: https://steveklabnik.com/writing/when-should-i-use-string-vs-str/. Compare that to TypeScript’s errors, which are unhelpful at best.
I’ll agree that Rust has great error messages until it doesn’t, and the situations where it doesn’t are usually the most annoying parts of the language like async, which I think is one of those situations and the example you highlight, so I’d also vote that error messages need work but would still think they are nice.
I speculate that “has a reputation for nice error messages” has an unsaid qualification “among programming language designers who appreciate the complexity of the problem”.
Both of these can be true at the same time:
I don’t have any hard data to back up the claim that it’s a common view, but I just asked Perplexity “what programming languages have the nicest compiler error messages?” and its response listed Rust first, Elm second, and “TypeScript and Go” third.
https://www.perplexity.ai/search/what-programming-languages-hav-OQacQ8BwTKi4bdKvaTwRKA#0
Maybe I don’t understand what context-insensitive means here, but I just want to point out that if you infer types of variables without looking at the uses and you have subtyping, you can turn non-breaking changes into breaking changes. Example: https://gist.github.com/osa1/b17e09f84c33c0d478640e6d7811ed37.
This actually happened to me in real code and I had to revert a change.
If the type checker took the uses of the variable
xinto account this would work as expected.You could not do type inference and ask the programmer to annotate variables with types, but that can easily get tedious, in most cases the type will be obvious, so that’s also not ideal.
Me too.
One thing the resonated with me was “the behaviour of dynamically typed languages makes sense to users”. I heard a similar thing firsthand from one of the creators of Julia. Perhaps not an unpopular opinion but one not spoken openly about enough.
To me, the fact that backtracking inference affects the program behaviour (by eg casting values) confuses the hell out of me. (The latest example being me learning rust - all the auto casting of various refs lead me to learn the wrong behavior…).
So header files aren’t a bad idea after all?
Header files are the best thing ever! I wish so hard that Rust kept .crate files (the old ones, like .mli, not the Cargo tarballs).
With header files don’t you have to write all your type signatures and type definitions twice? I hated them when I worked with OCaml.
It makes more sense to just implement the described feature in IDEs/editors, instead of making every programmer copy/paste their types/signatures to a separate file.
Dunno about OCaml, but in C public types go in the header, private types in the implementation, so all that gets duplicated is the function prototypes.
It might be nice to allow function definitions to be abbreviated, so the types don’t have to be repeated, but on the other hand it might be bad for the full prototype to be so far from the body. On the gripping hand, I usually have both files open so that I can make sure the implementation and documentation match.
But my prehensile tail points out that having the documentation, type signature, and body right next to each other in one file is a lot more convenient, and rustdoc does a fine job of pulling out and presenting just the public interface.
I just went full-circle thinking about this.
Yes, header files can totally serve this purpose. They provide a nice overview of what’s the public interface of a module.
And, in the spirit of improving UX (which is what this post is about), i think it would be crucial to have seamless integration between header files and implementation files. E.g., it should be trivial to toggle between them; if i “go to definition”, the definition on the implementation file should be open; if i edit the signature of a function in the implementation file, the change should be made in the header file automatically; etc.
But, if we had all this, then the header file would become almost a “projection” of the implementation file. In practical terms, it’d be almost a modified view of the same source code. Something that could be entirely derived, but for some reason still exists as a separate source file.
I.e., header files with good UX would be something very very similar to the feature this post is proposing; minus the need for duplicated information in two different files :)
Why would you need header files when all the IDEs since 30 years have an “outline” feature?
As @fanf mentions, the article of which we’re talking touches on this. But, if this is a genuine question(*), i also commented on why the article’s proposal is IMO superior to an “outline” view elsewhere on this discussion :)
*: I initially read it as a kind of slight, “don’t you know this has been a common thing for decades?”, but you probably didn’t mean it that way. Or at least i hope so! hehe
I read a great blog post earlier which explains that IDEs lack the right kind of outlining.
I don’t understand, the post doesn’t mention at all the IDE’s existing “outline” feature which already does everything mentioned here. Like when I open a code file, I have a separate panel which tells me all the methods in a file with their parameters, etc. and this has worked pretty much in every IDE I’ve ever worked in. e.g. this : https://ibb.co/48nXwn4 ; this was already a thing in dev-c++ in 2005.
Header files have the documentation and the complete public types. That outline looks fine for navigating a source file, but it isn’t a substitute for a header or for Matklad’s folded view.
Ideally, (part of) the implementation would be a projection of the header, because you really want the interface to be primary. And no, I have no idea how to implement that, at least not one that’s also in any way reasonable.
(One company that I worked at did automatic header generation as a matter of course. It worked. It was…hmm…let’s just say I adopted many of the habits and practices from there, but not that one)
Yeah, I think that every modern language server/IDE has supported seamless navigation between header and source files like this for 10+ years 😅
Header files should be auto-generated. The painful thing about headers is having to make changes in two places.
For example, Xcode displays auto-generated “headers” of Swift system frameworks.
We used to generate ObjC headers all the time. It has upsides and downsides.
The upside is obviously less duplication.
However, the downsides are also significant, because you have the implementation driving the interface.
Yes. It’s good that languages are less redundant nowadays, but we definitely lost some nice ergonomic and information-hiding aspects of headers.
When I was working in C# back in the 00s, I invented a “header file” format for C# (basically the public/protected class and function declarations with no bodies) and made a little tool that generated it from a DLL.
I think we did have Intellisense in Visual Studio back then, but that just shows one method at a time, whereas this let you see the full picture of a library (or your own code).
My main problem with header files is that any refactor that involves changing a function’s signature requires changing it in two places, which is annoying.
Even better - Pascal’s interfaces ;)
Though it’s still tangential to what the author is asking for, i.e. overally easier file navigation, which I 100% agree with.
At least in VSCode I can fold only specific level, which works most of the time.
I always liked header files for this reason. It provides an overview of what you can do with a module.
Awesome post!
My favorite description of HM inference is Section 4.4.4 in Samuel Mimram’s Proof=Program; they provide a description of level-based generalization which is more efficient than a
generalizethat needs to perform an occurs check to avoid generalizing variables not defined by the current binding (e.g. avoiding generalizingxin the definition ofyinfun x -> let y = \z -> x in y, as the given example)Algorithm M is interesting - it seems to have the localization benefits of systems like bidirectional type systems, while requiring no annotations
Regarding row polymorphism - Daan Leijen’s “Extensible records” paper is the simplest approach I know of, and is similar to the approach Elm/Roc use. At least in Roc, the approach is to bind a type variable to a record that unifies freely; for example the call
(fun r -> r.x) {x: 1, y: 1}types the function as{x: a}b -> a(wherebis free) and the record as{x: int, y: int}c(wherecis free);{x: a}b ~ {x: int, y: int}cyieldsb = {y: int}d, c = {}d(wheredis fresh). I don’t know of a good way to enforce that a record is “closed”, i.e. avoiding creating a fresh type variable representing expanding the width of the record, but I haven’t seen this be a problem in practice yet - but maybe there is an easy way?And regarding variants, I think there is a simpler approach than OCaml’s approach by implementing the dual of the row-polymorphic approach above (which Roc also does)… that is, an expression
`A 1 = `B "foo"is types the LHS and RHS as[A int]aand[B str]brespectively, the constraint[A int]a ~ [B str]bthen solvesa = [B str]c, b = [A int]cand both the LHS and RHS have type[A int, B str]c. In this case I think you do want to distinguish between extensible and non-extensible variants though, because a function[A, B]a -> {}is materially different than[A, B] -> {}- if you have a pattern match over the input on the former, you always need a catch-all branch, whereas a pattern match on the latter only needs a branch forAandB.Anecdotally, subtyping seems to be more intuitive for folks than row polymorphism/polymorphic variants, but of course then it’s hard not to lose a lot of the niceties HM affords..
How are you doing with the Lambda Set stuff? It looks absolutely impenetrable and I’m wondering if you have hot tips or a better description. How hard would it be to build on top of what we already have for HM?
I have taken a bit of a break from it due to some other commitments. @rtfeldman is working on a better version of what is currently implemented.
My fault in the existing implementation was attempting to do it in a minimal number of passes relative to the rest of a compiler. Pulling it out to a separate pass as the original authors of the Lambda Set paper (Morphic) did makes it quite straightforward. I have a toy compiler (online playground) demonstrating it (sorry if it’s a bit opaque).
The main tip I would have is to do it in a separate pass once you already have already specialized all generic types, assuming you have a specializing compiler. At that point, run HM-style inference to determine how function calls are propagated in a program (this is actually equivalent to inferring polymorphic variants via the method described above). If you don’t have a specializing compiler, you give up being able to specialize all call sites but you can run the inference pass in or out of band to specialize calls that are known to be direct.
One last thing to note is that the lambda set-style stuff is disjoint from the type system, since lambda sets are directly encoding values, and not types per-se. So while you can reuse code between the two, fundamentally there is no reason to tie the type system to function-call specialization.
Sorry if this is still a bit opaque, happy to dive into more details as needed (here or in DM)!
We don’t have specialization right now because all we have is run-time type checks :) With the addition of HM inference we begin the specialization journey. So
id = x -> xis still one IR node and one C function right now.If we tack on the lambda set stuff, where do you think we should make cut points to specialize or at least change indirect calls to direct calls? We only have two passes right now (infer and C codegen) but would be interesting to add another before codegen. Maybe this will force us to create an actual useful IR.
EDIT: The other day I was also wondering if it was a good idea (possible?) do even do normal worklist call graph / CFA, just to see something working. Maybe it could be useful to additionally filter/refine by type but ¯\_(ツ)_/¯
if you tack on the lambda set stuff you would need to do an inference pass before codegen, but then you can codegen the direct calls in-line (the inference is sufficient to direct how calls should be transformed). I don’t think you necessarily need to have an intermediate IR unless you want to for other reasons too.
yeah, lambda sets is CFA with a unification-based approach.
What is Lambda Set?
https://dl.acm.org/doi/abs/10.1145/3591260
Roughly, it’s a collection of possible function (ie lambda/closure) values you might expect in a given place (eg variable containing a function with a given signature).
By tracking this precisely the compiler (as an optimization) can store the various closures in a variant/sum type like data structure, enabling stack allocation of closures, inlining, etc. This can be faster than using function pointers and allocating every closure on the heap (another popular way due to simplicity of implementation).
Given most lambda variables would have a single concrete definition, it makes it simple for the compiler to eg inline the function call.
Different languages approach the problem in different ways (eg zig allows concrete function values or else function pointers, julia assigns a nominal type per function or closure but also allows for function pointers, etc), but this is another way which I’ve read about being applied to newer languages with ML-like type systems since the closures can just be treated like polymorphic variants and you get optimization benefits flowing pretty straightforwardly.
If you’d like an explanation in podcast form, @hafiz and I talked about it on this episode: https://pod.link/1602572955/episode/82423b3eae6782b9fc47381241d24dd9
I wonder what they mean by very large files….
And for that matter what they mean by fast…
I read the source code a little bit. It looks like the text is stored as a flat byte array (not sure which encoding) + a separate array for offsets of line starts.
So editing is
O(n)wherenis the size of the buffer.For example, here’s the char insertion. It calls
insert_string_raw, which callsarray_insert_bytes_at, which shifts the rest of the buffer and inserts the given bytes.Edits also mark the buffer as “dirty” and before redrawing it does a scan over the
bytesarray to re-generate the line starts.Assuming 60 FPS is responsive enough, you can measure how many bytes you can copy with
memcpyin 16ms and that should give you an idea of when this editor will start feeling slow when editing large files.I don’t know if there are other inefficiencies.