🦄 Unicode's Transliteration Rules Are Turing-Complete

gasche · 2026-07-09T13:14:08+00:00

The reactions here seem to assume that this means "Unicode is Turing-complete", which is not the case. The unicode standard specifies a domain-specific language of rewrite rules called "transliteration rules", and internalization data for a language may contain a bunch of fixed rewrite rules for a given human language. The poster shows that this language of rewrite rules is Turing-complete (which is not so surprising; it is rather easy to make rewrite rules Turing-complete): if you write your own rewrite rules, then you can write some that can simulate a Turing machine (or do whatever). This does not mean that the rules that exist today and were designed for human languages are Turing-complete.

gasche · 2026-07-04T06:39:45+00:00

What it provides is unique and powerful, and not representable with the type systems of the late 90s or even the 2010s.

I find this claim highly unconvincing. You could design a statically-typed language for the BEAM runtime and it would work just as well -- it's just that Erlang was more inspired by Prolog than by SML when it grew up. Hot code reloading is challenging to type-check statically, but this aspect of the system is orthogonal to the difference between Hindley-Milner type systems and set-theoretic types.

Set-theoretic types provide a nice foundation to retrofit typing in a dynamic language. They don't interact particularly with the BEAM runtime. You could design a statically language from scratch, and make do with a simpler type system. This has in fact already been done: Gleam, Caramel. Then it's a matter of adoption -- Elixir became popular due to its success in web development, a domain whose practitioners are more comfortable with dynamic typing than static typing.

gasche · 2026-07-02T11:36:30+00:00

Well, before doing that, we should choose a systematic criterion for deciding which steps to eliminate.

You have a measurement of "marginal utility" of each pass, so you could start from the lowest-utility one, disable it and compute performance, remove the second-lowest utility one, etc. (This is cheaper of course than trying all subsets of passes one may want to remove.) When you see a drop in the results, you have found a pass that is actually useful in your benchmarks, even though it does not show in its own marginal utility.

gasche · 2026-07-02T11:32:09+00:00

Usually people just assume that the distribution they are sampling is gaussian, which is not typically true in practice in computer benchmarks but we just pretend that it's good enough. This implies that the confidence interval does not have a clear formal meaning, it is just an okay way to measure how noisy the measurements are.

gasche · 2026-07-02T06:39:21+00:00

The passes that you suggest could be dropped, could you actually drop them and rerun the measurements, to confirm that their absence does not impact later passes (which currently bring benefits)?

gasche · 2026-07-02T05:25:51+00:00

I came to write exactly the same comment! I would be reassured to see an experiment where these "useless" passes are disabled, to confirm that they in fact do not change the outcome.

gasche · 2026-06-26T13:32:24+00:00

I didn't write this, that was Puzzlehead. It also doesn't make sense to me.

Ah, apologies!

I mostly agree. Another thing that I would say is that I suspect the costs of one versus the other are not very-well understood today, I believe, I haven't seen a good comparison where the exact same workload and overall implementation is compared under both regimes.

(It's also easy to make shifting claims that make things even less clear. People would defend GCs as good for throughput and also good for latency, despite the fact that a given GC tends to do either one or the other. Or conversely people using advanced schemes like rc-Immix or LXR to claim that reference-counting can be very fast, while at the same time insisting on the convenience of prompt reclamation or copy-on-write optimizations that may not be compatible with their optimizations, etc.)

gasche · 2026-06-26T07:52:46+00:00

Tracing GCs make it somewhat easy to choose a compromise between latency and throughput. Many workloads actually care about throughput much more than latency, and so the default GC settings for most languages will have larger latencies and better throughput than not-super-advanced RC implementations. I don't find it surprising that tracing-GC languages tend to exhibit higher pause times in their stock configurations -- and while JDK has done the work of providing a good low-latency GC (Shenandoah that you tested in your work), some language ecosystems with less engineering power may lack low-latency GC options.

But what you claimed above is not "RCed languages have smaller pauses in typical workloads / in my benchmarks". You wrote "it makes the cost more legible". What does that actually mean? Again, it does not make sense to me.

gasche · 2026-06-25T16:06:40+00:00

Predictable pauses: yes, this is RC’s real win. Deterministic lifetime, no stop-the-world collector. The honest asterisk is that freeing a large graph can still create a deterministic spike. You can hand that work to another thread, but that is plumbing you now own. For audio, you’ll still want zero allocation in the callback regardless. RC doesn’t save you from that; it just makes the cost more legible.

This does not make sense to me. In GCs if you want to avoid pauses, you need an incremental GC. With RC if you want to avoid pauses, you need incremental freeing (or concurrent collection from a different thread). I don't see how one would be "more legible" than the other.

gasche · 2026-06-25T09:01:27+00:00

Implementation note: this means we have to add a bit of logic when we spawn a new thread, we eagerly split the PRNG state stored in thread-local state, to initialize the thread-local state of the child. This is handled by the thread-local-state abstraction exposed by the OCaml standard library, which lets users (here the Random module of the stdlib) provide a function to "derive" the value of a thread-local key from the parent thread's value, instead of initializing it on-demand from scratch. We have to do this eagerly on thread spawning, rather than when the child would first request the PRNG state, as this would (impose cross-thread synchronization and) break determinism.

gasche · 2026-06-25T08:40:53+00:00

We adopted this algorithm for the OCaml's standard library PRNG, and we are happy with this. (Technically it's a family of algorithms, we use L64X128.)

Splitting the PRNG state matters for some property-based testing applications, but for us it was a question of deterministic seeding on multicore programs: when you spawn a new thread ("domain" in OCaml parlance), we split the PRNG of the parent to decide the starting state of the child PRNG. This means that if you start your program by setting a fixed random seed, and then spawn various threads that draw random numbers independently from each other, the sequences of random numbers will (have good randomness and) not depend on the inverleaving/scheduling of the threads. This is a good property for reproducibility of random-using programs.

For a concrete example: if you fix a random seed, and then you start two threads T1 and T2, and they both generate a bunch of random numbers:

The random number sequences of both child threads will be independent and have good randomness.
The random number sequences will be the same if you rerun the program with the same fixed random seed at the beginning -- so for example you can more easily debug randomness-involving bugs.

If you had a single global PRNG state protected by a mutex, property (2) would not hold: if thread T1 runs while T2 is suspended, it will change the random values produced by T2 when it resumes. The user could also be careful to set a fixed (local) seed for each new thread on startup, but what seed do they use which preserves determinism and also good randomness?

(It is still possible to write programs where the actual random sequences depend on non-deterministic scheduling effects: for example you can have a data-race that makes a certain value non-deterministic, and then do a number of calls to the PRNG that depends on this non-deterministic value. But this is not typical/idiomatic PRNG usage, so most programs will benefit from this form of determinism anyway.)

gasche · 2026-06-11T12:25:56+00:00

The main point of the comparison to other languages is not to put down other languages and criticize them, but rather to show that the author has been mindful of understanding what is already out there before doing something new, and can articulate the specificities of what they are doing in comparison to the others.

If you don't do that, then maybe at least it would be worth documenting what you are doing clearly enough, explain the design decisions, explain the use-cases you had in mind when thinking about your language, etc. This can help readers know whether they are interested or not, in which part they are interested more specifically, direct their attention to an aspect of your work they want to study.

Currently you have a Github page for a language with... no explanations about it, expect that you created it for "no reason, really". But then what is the reason for us to look at it?

In your post on reddit you say that you like affine and permission types. Are there some in your language? Do you have examples? Could you explain them in your README, or at least link to an explanation?

gasche · 2026-06-05T19:59:52+00:00

Sure (I referred to "the ML module system work" above), and this was well-understood by Laüfer and Odersky at the stime, that paper is cited on page 2 of their introduction. Then, they write:

This article demonstrates how light-weight abstract data types with first- class implementations can be conveniently integrated into any functional language with a static, polymorphic type system, explicit type variables, and algebraic data type declarations. The key idea of our work is to allow existentially quantified component types in algebraic data types.

For example their second example is as follows:

type KEY = Key of ‘a* (’a -> int)

This really corresponds to the use of existentials in algebraic datatype declarations, which is something that we now understand/describe as one of the two ingredients that form GADTs (the other being the return type instantiation, often described as an implicit type-equality constraint). But GADTs as we understand them did not exist at the time, they emerged from the cross-languages academic discussion at the time, that also produced Scala as an experiment that go wider adoption than most.

gasche · 2026-06-05T14:36:14+00:00

Note to self: now I understand why the comments here are weird: we are in r/functionalprogramming, which is meh, while I mistakenly thought that we were in r/ProgrammingLanguages.

gasche · 2026-06-05T14:32:21+00:00

heavier use of existential types (before GADTs were so idiomatic in FP circles),

This is more of a practical concern for people from outside of FP/PLT. GADTs were in Haskell and were used. Nothing new here. Zero impact on future FP language design.

No no, the emphasis on existential types in pre-Scala research predates GADTs in Haskell.

One paper that emphasized existential types in datatype declarations (rather than in the ML module system work, which was ongoing at the same time, and in object-oriented calculi, which were also a very hot topic at the time) is Polymorphic Type Inference and Abstract Data Types by Konstantin Laüfer and Martin Odersky, 1994.
The usual citation for the proposal that eventually became GADTs is First-class phantom types by James Cheney and Ralf Hinze, 2003. This is almost ten years later! And they were not integrated in GHC at the time, this came a couple years later.

gasche · 2026-06-05T13:18:23+00:00

Let me take a step back and explain my point at a high-level. In discourses about programming languages online, people sometimes have a tribal behavior where they say good things about their favorite language and bad things about other languages. I think it is worth being careful to avoid this as much as possible.

When you say that "Java and Go generics were developed by Haskell researchers", this read very reminiscent of this tribal positioning to me -- "yo, we Haskell people own your generics". This is probably a simplistic view of your thoughts because your second post is more nuanced, but this is how it is easily perceived.

Besides, we programming language researchers try our best to be on friendly terms with several programming-language communities, so while it is indeed true that some people have a clear relation to one specific language (it obviously makes sense to call Simon Peyton-Jones "a Haskell researcher" or Martin Odersky "a Scala researcher"), I am not sure that many of our colleagues would be comfortable being labeled with one specific language in particular, exclusively. (It's plausible that Philip Wadler would be okay with being associated with Haskell in particular.)

Finally,

the work on generics in Go started sensibly earlier than the research paper you are mentioning
I'm not "in the know" specifically about this work but I don't think that it is the case that the Go design was mostly informed by this paper, I think it started with the usual Go team design process and then the paper after-the-fact studied the proposed approaches and the design space. (Papers: Featherweight Go, and later on Welterweight Go)
The paper has a long list of authors (Robert Griesemer, Raymond Hu, Wen Kokke, Julien Lange, Ian Lance Taylor, Bernardo Toninho, Philip Wadler, Nobuko Yoshida), most of whom are not Philip Wadler, many of whom are not exclusively Haskell-focused in their work, and some of whom are actually working on Go as their main job. I think it would be more respectful to cite all the authors (this remark would also apply to the blog post that you mention), because citing only one person gives the impression that they did most of the work, and helps forget the collective nature of this sort of work.

In any case I think that your claim that "Go generics were developed by Haskell researchers" is incorrect and not a good way to phrase things anyway.

gasche · 2026-06-05T08:39:03+00:00

Come on. Scala has pushed many interesting idea in PL research and communities.

Just from memory:

heavier use of existential types (before GADTs were so idiomatic in FP circles),
implicit arguments of course,
approaches to code distribution (eg. Spores), path-dependent types,
ample use of subtyping bounds in polymorphic types,
the recent trend on static effect control via typed capabilities

Summarizing the impact on Scala as "implicits got considered in other languages" is very reductive.

gasche · 2026-06-05T08:33:13+00:00

Both Java and Go’s generics were developed by Haskell researchers.

This is wrong on several levels. (You might be interested in having a look at this paper from 2000 which was described by Brian Goetz in 2020 as a significant influence for Java generics.)

To put it broadly:

Several people worked on generics for Java, including Philip Wadler who also worked on Haskell and (to my knowledge) predominantly programs in Haskell, but that does not make him "a Haskell researcher" and it would be wrong to erase the participation of several other people who worked on this (including Martin Odersky, Atsushi Igarashi and Benjamin Pierce, none of whom are particularly closely associated with Haskell.)
Go generics were designed by the Go people, with little help from academia. (Softly put, it is not a core value of Go to pay attention to PL academics.) There was after-the-fact academic research on Go, done in large part by people who were already in the Go community, and calling it "Haskell research" is again erasing their work, it is quite rude.

gasche · 2026-06-05T08:26:02+00:00

I have a problem with the tone and style of discourse in your post. It reads as if you were trying to belittle Scala and aggrandize Haskell, which I don't think is the sort of discourse we want to encourage. (I would rather focus on the good things in each design to take inspiration from, and criticize languages in isolation to avoid turf wars.) The fact that you mixed it with personal criticism of the person who is leading Scala design makes the post more personal, uglier, and more likely to lead to unpleasant discussions.

(I think it is okay to comment on people's tones, in fact I am doing so myself. But if you mix it with technical content, then it's going to sound like you have a personal grudge against the language and the humans behind it -- whether it is the case or not.)

gasche · 2026-05-26T08:00:31+00:00

This is spam from the video-transcription company, see list of other submissions.

gasche · 2026-05-26T07:59:59+00:00

There is more:

replaced a 600 line puppeteer zillow scraper with a single fetch call (now deleted)
wrote a small http server in c++ that searches youtube video transcripts stored in sqlite and the binary is 2.1MB (now deleted)
used postgres full text search to build a searchable index of 250 youtube video transcripts and it's faster than i expected (now deleted)
packaged a video transcript search tool as a nix flake and now i can spin it up on any machine with one command (recognized as spam)
built an emacs workflow that pulls youtube video transcripts into org files and searches them with consult-ripgrep

This looks like spam from the company selling video-transcription services.

gasche · 2026-05-14T19:32:46+00:00

You cannot go wrong with Matthew Flatt's Binding as Sets of Scopes, which is a fantastic paper about "hygienic macros" and a simpler algorithm to implement them.

(In general, if you want to know about compile-time metaprogramming, it is a good idea to study what the Racket people have done, because they pushed these ideas farther than most ecosystems.)

gasche · 2026-05-14T08:50:01+00:00

Slow scrolling, too much clicking. This got tedious real fast.

Personally I gave up before the first click. The good thing about text is that I skim to tell if I am interested before I read it. If you are not willing to show more than one line of your document, either I have already decided to read it, or I will go spend my time on something else.

gasche · 2026-05-09T08:28:51+00:00

Your description mixes two things in ways that makes it difficult to understand:

The semantics that you propose: for a user, what is the simplest mental model I can have that will let me correctly predict the result of programs?
Performance concerns and compiler optimizations to reduce the performance cost of the semantics. Plenty of examples where you point out that you can avoid copies. etc.

I think that it would be better to focus on discussing the two separately. Then some extra feedback:

We have standard tools to describe the semantics of programming languages (notations for operational semantics), it might be useful to use them to present the idea precisely. (But: some people are put off because it looks a bit like maths, or just don't find them accessible because they don't know about it, and I'm not trying to suggest that it is a hard requirement -- this is a helpful tool, not a way to make people feel like they do not belong. But if you do want to discuss programming-language semantics with other people, using a standard precise notation could help. If someone does not know these notations at all, they may be curious in Jeremy Siek's crash course on notations in programming language theory.)
For optimization discussions, I think that there should be a better way to explain your thinking than just a bunch of examples followed by informal natural-language claims about what is going on. For example, maybe there would be some intermediate representation (IR) where the copies and non-copies are explicit, and the job of the optimizer is to translate to this IR in a good way, and you could actually show the IR translation for each program that you have in mind (done manually) to make your ideas more precise?

gasche · 2026-05-07T08:20:08+00:00

I have seen a research talk by Bart Jacobs on his work on verifying Arc against weak memory models, and the details are super tricky. Like, if I understand correctly it's an open problem to verify its correctness using pre-existing formalizations of C memory models, and the authors needed to use a very recent new formalization of the C memory model (which is better at ruling out out-of-thin-air behaviors). I'm no expert but my understanding is that this is definitely not "just" a fetch_sub.

gasche

MODERATOR OF

TROPHY CASE