please, share your favorite resources about programming languages and DSL design

I've collected a bunch of resources about this, notably in the

little languages

,

notations and paradigms

,

programming languages and programming systems

sections. https://github.com/Little-Languages/reading-club/tree/main/topics Notably: • Searching for Justice in Programming Language Design” by Amy Ko (2023) • Programming Pearls: Little Languages ◦ • Programming Paradigms for Dummies: What Every Programmer Should Know •

Some of you have read (or at least listened to commentary on) "A Case for Feminism in Programming Language Design" by Felienne Hermans and Ari Schlesinger. It references Amy J. Ko’s Wordplay. That led me to Ari Schlesinger’s PhD dissertation, "Addressing Computing's Discrimination Problem: A Framework for Anti-Discriminatory Computing". Chapter 6 – Exclusion and Inclusion in Programming Languages: A Case Study relates closely, but I enjoyed it overall.

I like @Christopher Shank’s collection on little languages. Lately, I have formed the opinion that we should become interested in “little networks”. https://programmingsimplicity.substack.com/p/little-networks?r=1egdky

I agree with most of https://tonsky.me/blog/dsl/ However, I think verbosity can be replaced/achieved/assisted by "IDE integration" to some degree, e.g. if IDE suggests would show, limit, and explain tokens I can use in curtain expression positions – tokens themselves could be short.

I learned to write compilers without building ASTs. That means using “staged computation” (scan, parse, semantic analysis, allocation, code emission). Each stage gets its own little parser front end to direct its actions (today, this appears to be called “pattern matching”). From that perspective it becomes straight-forward to build DSLs by mapping, in stages, input syntax to some existing programming language, i.e. using existing languages as “assemblers”. CFG-based tools like YACC, make this kind of thinking difficult. Recursive descent code and tools, like S/SL (Syntax / Semantic Language) make this imaginable. New-fangled tools based on PEG - ohmjs.org - make this kind of thinking much, much easier. I think of a stage in two parts - 1. parse, 2. rewrite. To this end, I use OhmJS for (1) and a little DSL for (2). I call the little DSL: RWR. I’ve combined these two parts into a tool I call T2T (text-to-text). Super-simple examples can be seen in abc and abc to python and arith - stock arithmetic grammar emitting JS, Py, CL, WASM. Big examples of creating a DSL can be seen in the PBP kernel project. This project uses PBP with some T2T components to create a new DSL called ‘rt’ and compiles the DSL code to Python and Javascript and Common Lisp. RWR spec T2T dev repo ancient manifestation of a compiler built in a staged computation manner (PT Pascal built using S/SL)

/tangent/ What do you call "(building) AST" here? Is it "Intermediate Representation with common structure for parses of all expressions"? It seems to me, AST is just a result of "1. parse", not necessarily of the same shape/structure for each parse, whatever that looks like. ohmjs emits parse tree (https://ohmjs.org/editor/), you did not build it, but you use it. "AST is just some IR" – makes it sound way less controversial. I think, the more optimizations you need in output code, the more convenient/necessary it would be to have IR of format common across the expressions, to be able to operate not only on a list of opaque sibling nodes, but on several levels of the (AS)Tree at once (in a body of a single function). For transpiler use case, not having many things compilers usually have is even expected (what I saw in those repos looks more like transpiler than compiler, as in: all optimizations and not-1-to-1-input-to-output translations are outsourced to actual js/python/cl compilers).

...

(recent relevant Sam H. Smith – Parsing without ASTs and Optimizing with Sea of Nodes – BSC 2025)

https://www.wolczko.com/CS294/ advanced course on language VM/runtime techniques. I barely watched 50%, and much is over my head, and most language design probably doesn't — shouldn't! — require knowing these. But I'm enjoying the vibe (and the guest lectures). It feels like there is tons of "advanced compiler optimization" materials out there (eg. this one has been shared before) and much fewer "advanced interpreter/systems" experts, so this is a rare resource.

The "..." was meant to say "I'm working on a response, but haven't finished yet" (I couldn't find an emoji that seemed appropriate). I seem to have created drafts for one article that attempts to answer your questions, plus two more spin-off articles. When I use the word "AST" I actually mean "in-memory CST". (CST is a concrete parse tree based on possibilities allowed by the AST. Many people use the word "AST" to mean both). My main concern with the AST-approach for writing compilers has to do with memory issues. Roughly, I'd say that the AST-approach needs about 10x more memory than a staged computation approach. There are other ways to build compilers, but, they seem to have been pushed aside. Right, OhmJS does build a CST (AST). I consider that to be an implementation detail and focus on the use of PEG in OhmJS (on top of which, OhmJS gets "separation of concerns" more right than any other parsing tool that I've witnessed). To me, OhmJS, and PEG in general, make it very much easier to construct programs using staged computation, because they make it easy to put a parser into the front end of every stage, and make it easy to build code using "pattern matching". And, when you do that, you can customize the parser in every stage to be specific to the job at hand for each stage. All of which, I claim, leads to simplicity. (@Misha A)

Can you show some (pseudocode/pseudostruct?) examples of: AST, ConcreteST, sea of nodes, flow graph, inference graph? I was under impression, all of these names are used to emphasize purpose, not actual structure developer has to deal with (some specific vector/set/hashmap). Is "AST" you talk about – specifically an actual tree, like deeply nested json map, eg.

{id 0, type if, test {id 1 ...}, then {id 2 ...}, else {id 3 ...} ...}

), and not, say, flat list of nodes where ids are idx in that same list? eg.

[{id 0, type if, test 1 then 2 else 3}, {id 1 ...}, {id 2 ...}, {id 3 ...}]

Because to me – both are "ASTs", and which actual structure (or several) to use is up to me (how convenient or performant is to use it within compiler).

Compressing AST data structures is not the issue, IMO: https://programmingsimplicity.substack.com/p/rethinking-memory-assumptions-in?r=1egdky @Misha A

I don't get where "AST always leads to infinite-memory-assuming design" implication is coming from. I can come up with counterexamples to many points in the article, eg. "garbage collection comes from infinite memory thinking", when to run java program you explicitly specify max allowed memory footprint with

-Xmx 1Gb

. I guess 1 in 1000 of developers even heard term AST, and 1 out of 100 of those – had a hands on experience with "it". So "AST" (whatever you actually mean by it) is not to blame for all the bloated crappy software in existence. Why not blame Turing for a concept of infinite tape then? 🙂 again, ohmjs gives you parse tree (how is this not AST?), and if expression is deeply nested enough, your "say, 128KB" would go bye bye too. Please, show a concrete (pseudocode) example of an AST.

Paraphrasing: the original question was about tools for building DSLs. I know that it is possible to build DSLs without using ASTs, using staged computation. Staged computation, at the level of building DSLs is a different line of reasoning/problem-solving than is the common approach of using function-based programming (which has grown into functional programming). The AST designs that were shown in this thread were sufficient, but, they are still ASTs designed using the function-based-infinite-memory mindset. https://open.substack.com/pub/programmingsimplicity/p/the-spherical-cows-of-programming?r=1egdky&utm_campaign=post&utm_medium=web&showWelcomeOnShare=true