LR Parsing Is An Abstract Interpretation of LL Parsing
We show that LR parsing (not recognition) is an abstract interpretation of LL parsing, and use these results to show the correspondence of (deterministic) LR parse traces and LL parse traces.
Computer scientist · Singapore
Foo Yong Qi.
I study programming languages, and how to make them more expressive, efficient, and a little more elegant.
Instructor & PhD candidate in Computer Science
National University of Singapore
A small explorationFIG. 01
00 / Start with an empty set
The rule always includes a, adds b when a is present, and adds c when b is present. Each iteration keeps the elements already found. Starting from the empty set, the process reaches the fixed point containing a, b, and c.From rules to resultsFIG. 02
The program
edge(a, b). edge(b, c). edge(c, d).
path(X, Y) :- edge(X, Y).
path(X, Z) :- path(X, Y),
edge(Y, Z).All known facts · I00 facts
∅
Highlighted facts are new this round.
Round 00 · 0 newStart with an empty set of facts.
A few things I think aboutProgramming languagesFixed-point programmingCompiler optimizations
01Ideas into papers
Selected research
Class-Dictionary Specialization with Rank-2 Polymorphic Functions
Making expressive Haskell abstractions efficient: a partial evaluator that unlocks specialization for recursive rank-2 polymorphic functions.
Pushing the Information-Theoretic Limits of Random Access Lists
How close can a functional list get to optimal random access? New variations on Myers lists approach the information-theoretic lower bound.
Fixed-Point-Oriented Programming: A Concise and Elegant Paradigm
A paradigm for expressing work-list algorithms correctly and concisely.
02Along the way
Recently
I presented our work on "Class-Dictionary Specialization with Rank-2 Polymorphic Functions" at SPLASH/ISSTA 2026!
[NUS] IT5100E—Industry Readiness: Security Best Practices starts today. See you there!
[NUS] IT5000—Introduction to Computing Foundations starts today. I will be teaching the Discrete Structures portion (Day 1, 4 Aug). See you there!
I am a ACM SRC grand finals candidate. Didn't win though. My paper is here.
03In the classroom
Making the abstract
make sense.
I teach programming, systems, and the mathematics behind them, connecting foundational ideas to the practice of building software.
IT5100ATyped Functional ProgrammingIT5100BStream ProcessingIT5100ESecurity Best PracticesTeaching & course materialsRecipient of the NUS Faculty Teaching Excellence Award, 2025.