The AST Trap: How Compiler Design Mirrors Software Bloat

2025-09-30

The Abstract Syntax Tree (AST) has become the universal hammer in compiler design, and consequently, every compilation problem looks like a nail. This seemingly elegant approach—parse everything into a tree, then walk it repeatedly for different phases—exemplifies the same thinking that has led to software bloat across the industry. It’s a solution optimized for human comprehension rather than computational efficiency.

The AST Orthodoxy

Modern compiler textbooks present a standard pipeline: parse the entire input into an AST stored in memory, then perform multiple tree walks for different phases. One pass gathers declarations, another does type checking, another handles optimization, another emits code. Each phase assumes it needs access to the complete tree structure.

This approach feels natural to programmers trained in hierarchical thinking. It maps cleanly to object-oriented design patterns. It’s easy to explain in academic settings. But like many “clean” abstractions, it comes with hidden costs that compound into bloat.

The Memory Assumption

The AST approach assumes infinite memory availability. Every syntactic construct, no matter how transient, gets allocated space and persists until compilation completes. For large codebases, this memory footprint can become enormous—yet most compilation phases only need to see small portions of the code at any given time.

This mirrors the broader software industry’s cavalier attitude toward memory consumption. Virtual memory is treated as a substrate technology rather than a scarce resource to be used judiciously. The assumption that we can always allocate more RAM leads to designs that waste memory on principle.

Streaming vs. Storing

Many compilation phases don’t actually need random access to the entire tree. Symbol table construction only needs a stream of declarations and write access to a hash table. Semantic checking is fundamentally a relational process—matching uses to declarations, verifying type compatibility. These are naturally streaming operations that have been force-fitted into tree-walking patterns.

Even optimization doesn’t always require whole-program analysis. Local optimizations work on small code windows. Many global optimizations can operate on control flow graphs or data flow representations that are more compact and focused than full ASTs.

The Wrong Tool for Every Job

The AST has become a universal data structure, forced to serve problems it wasn’t designed for. Syntax trees excel at representing hierarchical program structure, but they’re awkward for:

• Data flow analysis (better served by flow graphs)

• Register allocation (better served by interference graphs)

• Code generation (better served by instruction templates)

• Optimization (better served by sea-of-nodes or DAG representations and peepholers and/or MIST decision trees)

Using ASTs for everything is like using a screwdriver to hammer nails—it works, but creates unnecessary complexity and inefficiency.

The Prolog Insight

Symbol resolution and type checking are inherently relational problems. We’re matching identifiers to declarations, checking compatibility relationships, and inferring types based on usage patterns. This is exactly what logic programming languages like Prolog excel at.

Yet most compilers implement these phases in imperative or functional languages, essentially hand-coding inferior versions of what a factbase and relation system would provide naturally. This is Philip Greenspun’s Tenth Rule in action: badly reinventing specialized tools within general-purpose languages.

Good Enough vs. Perfect

The pursuit of optimal compilation has driven enormous complexity in modern compilers. Multiple optimization passes, sophisticated register allocation algorithms, and global analysis techniques that consume gigabytes of memory. But for many programs, 80% efficiency would be perfectly adequate.

Consider the contrast between spreadsheets and functional programming. People solve real problems with spreadsheets every day, despite their computational limitations. When production engineering is needed, specialists optimize the critical paths. But the default shouldn’t be maximum optimization complexity.

Computer Science has become obsessed with production-engineering techniques rather than simplifying the programming process. This mirrors the broader software bloat problem: optimizing for theoretical performance while ignoring practical resource consumption.

Staged Computation

The fundamental issue is the starting assumption that a single syntactic representation can serve every compilation sub-problem. This invites epicycles and force-fitting of natural streaming processes into tree-walking patterns.

A better approach uses staged computation: break the job up into small tasks and form a processing pipeline without the restriction that stages can only output to one downstream stage. Fan-out is allowed. The front end streams the tree, instead of forcing it to remain in memory. Each subsequent stage streams whatever is necessary. Each subsequent stage builds whatever data representation is needed. Previous work on PT Pascal and Concurrent Euclid shows that many passes don’t need much in the way of in-memory data structures—many stages can just fire actions as the stream goes by. This previous work also shows that the tree gets whittled down in the process. By the time the stream reaches the emitter back-end, the stream only contains known-to-be-valid pre-code and allocation information—the info needed by the back-end for crafting code from the instruction stream, without extra fluff like variable declarations. Streaming like this used to be considered inefficient and bad form in the days when CPUs and memory were expensive, but those restrictions have been lifted. We are allowed to think about this differently than in the past.

Historical Alternatives

Effective alternatives to AST-everywhere have existed for decades:

Fraser/Davidson peephole optimization showed how to achieve good optimization with minimal complexity. GCC still uses these techniques. A complete peephole optimizer can be written in one page of AWK code.

Orthogonal Code Generation (OCG) separates correctness from efficiency. First emit simple, correct code. Then apply architecture-specific optimizations. This two-stage approach reduces complexity while maintaining portability.

Sea-of-nodes representations avoid the artificial hierarchies imposed by syntax trees, allowing more natural expression of data dependencies and control flow.

The Toolbelt Principle

No single paradigm should dominate an entire compilation pipeline. Different sub-problems call for different tools:

• Pattern matching for parsing

• Logic programming for semantic analysis

• Graph algorithms for optimization

• Template systems for code generation

• Peepholers and/or MIST decision trees for local code optimization

• etc.

A good compiler should combine multiple specialized approaches rather than forcing everything through a single abstraction. This requires workflows that support multiple languages and representations, gluing together the best tool for each sub-problem.

Breaking the AST Habit

Modern tools like OhmJS make it easy to build grammar parsers, but we shouldn’t let the convenience of AST generation dictate our entire architecture. Use ASTs as one tool among many, not as the universal solution.

The goal isn’t to eliminate trees entirely, but to recognize that syntax-driven representations create artificial constraints. Many compilation problems become simpler when freed from hierarchical thinking.

The AST habit derives from the function-based habit. This habit of thinking encourages one to miss thinking about other kinds of architectures for program development workflows. For example, we could build one super-optimized emitter for each target computer architecture using peepholing, decision trees and graphs, but function-based thinking encourages a psychological one-size-fits-all stance which complicates matters by encouraging one to force unrelated optimizations to co-exist in one enormous blob of compiler code.

Conclusion

The AST-everywhere approach in compiler design exemplifies the same thinking that produces bloated software: choosing abstractions that feel clean to human designers rather than efficient for computational execution. The result is compilers that consume enormous memory and computational resources to perform tasks that could be handled more efficiently with streaming, relational, or specialized graph-based approaches.

Like the broader software industry, compiler design has prioritized conceptual elegance over practical efficiency. The path forward requires abandoning the one-size-fits-all mentality and embracing diverse tools for diverse problems. Only then can we build compilation systems that match the efficiency of the hardware they’re designed to target.

Postscript: Why Write Compilers At All?

This is a provocative question. Don’t we already have enough compilers in 2025?

Creating a new language no longer means that we need to write a whole compiler for it. We simply need to transmogrify code written in the new language into some already-existing language.

Alan Kay suggests this very thing at 31:50 of his talk at

.

I succeeded at performing this experiment: I wrote the code for a whole message-passing kernel in a new language. Then, I built—easily—a transmogrifier (using OhmJS and a little DSL I call RWR) that converted the kernel code into code for three languages: Python, Node Javascript, Common Lisp. I could have kept going, but my interest waned.

The code for this is in the github repo https://github.com/guitarvydas/pbp-dev/tree/dev/kernel and I am in the process of writing a short book on transmogrification. In the meantime, I would be happy to answer questions about how to build little transmogrifiers.

This approach exemplifies the toolbelt principle discussed throughout this article: rather than building one enormous compiler with all its AST-driven complexity, we can compose small, specialized tools that each do one thing well. Transpilation sidesteps the entire AST-bloat problem by treating existing compilers as the back-end infrastructure they should be.

I know of someone who asked an LLM to build a transmogrifier. This highlights an interesting convergence: while LLMs themselves violate engineering principles through their unpredictability, they can serve as useful tools for generating deterministic transpilation code. The irony is that LLMs excel at pattern-matching and code transformation tasks—precisely the operations needed for transpilation—even though they shouldn’t be trusted for the kind of reliable, repeatable engineering work that compilers must perform. This suggests a pragmatic division of labor: use LLMs as assistants to generate boilerplate transpilation code, but verify and test the output rigorously to ensure it behaves deterministically. The transpiler itself remains an engineering artifact even if an LLM helped write it.

References

PT Pascal and Concurrent Euclid:

• Cordy, J.R., Holt, R.C., and Wortman, D.B. “PT Pascal Implementation.” S/SL Programming Language and Processor. https://research.cs.queensu.ca/home/cordy/pub/downloads/ssl/ (an staged implementation of PT Pascal using the S/SL compiler building language)

• Holt, R.C., Cordy, J.R., and Wortman, D.B. “A short introduction to Concurrent Euclid.” ACM SIGPLAN Notices, Vol. 17, No. 5, 1982. https://dl.acm.org/doi/10.1145/947923.947931

• Concurrent Euclid. Wikipedia. https://en.wikipedia.org/wiki/Concurrent_Euclid

• Euclid (programming language). Wikipedia. https://en.wikipedia.org/wiki/Euclid_(programming_language)

Fraser/Davidson Retargetable Peephole Optimizer:

• Davidson, J.W. and Fraser, C.W. “The Design and Application of a Retargetable Peephole Optimizer.” ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 2, No. 2, April 1980, pp. 191-202. https://dl.acm.org/doi/10.1145/357094.357098

• Davidson, J.W. and Fraser, C.W. “Automatic generation of peephole optimizations.” ACM SIGPLAN Notices, Vol. 19, No. 6, June 1984, pp. 111-116. https://dl.acm.org/doi/10.1145/989393.989407

• Davidson, J.W. and Whalley, D.B. “Quick compilers using peephole optimization.” Software: Practice and Experience, Vol. 19, No. 1, January 1989, pp. 195-203.

Cordy Orthogonal Code Generation (OCG):

• Cordy, James R. “Orthogonal Code Generation.” Ph.D. thesis, University of Toronto, 1984.

• Cordy, James. Wikipedia. https://en.wikipedia.org/wiki/James_Cordy (mentions orthogonal code generation method based on Ph.D. thesis work)

• Wortman, D.B., Holt, R.C., Cordy, J.R., Crowe, D.R., and Griggs, I.H. “Euclid: A Language for Producing Quality Software.” Proceedings of the National Computer Conference, Chicago, May 1981.

Sea of Nodes:

• https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=

• Click, Cliff. “Combining Analyses, Combining Optimizations.” Ph.D. thesis, Rice University, 1995. https://www.researchgate.net/publication/2394127_Combining_Analyses_Combining_Optimizations

• Click, Cliff and Paleczny, Michael. “A Simple Graph-Based Intermediate Representation.” ACM SIGPLAN Workshop on Intermediate Representations, January 1995.

• Sea of nodes. Wikipedia. https://en.wikipedia.org/wiki/Sea_of_nodes

• SeaOfNodes/Simple. GitHub repository. https://github.com/SeaOfNodes/Simple

OhmJS:

• ohm-js.org

See Also

Email: ptcomputingsimplicity@gmail.com

Substack: paultarvydas.substack.com

Videos: https://www.youtube.com/@programmingsimplicity2980

Discord: https://discord.gg/65YZUh6Jpq

Leanpub: [WIP] https://leanpub.com/u/paul-tarvydas

Twitter: @paul_tarvydas

Bluesky: @paultarvydas.bsky.social

Mastodon: @paultarvydas

(earlier) Blog: guitarvydas.github.io

References: https://guitarvydas.github.io/2024/01/06/References.html