= Lambda VarName AST
| Apply AST AST
| Var VarName
| Literal Value
That's it. Those four nodes and I could do anything. I wrote an interpreter for this language in half an hour. I wrote a type inferencer in an hour, scrapped it, and took another hour to write another type inferencer. That's the beauty of a small core calculus. The optimial calculus is hard to come up with, but once you have it, everything else is cake. That's why PIL is so important.
The following three nodes get you to context-free (displayed in Haskell for its consice description of data structures, even though I'm actually writing it in Perl 6):
= Literal String
| Union Rule Rule
| Concat Rule Rule
Anyone with experience in formal languages will say "That's not context-free! That's not even regular!" Oh, but I neglected to mention: I allow infinite, recursive structures. It's easy to see how to build an inifite structure for the Kleene star. A similar technique will allow you to model every context-free language.
After playing with this structure a little bit, I have concluded that allowing infinite structures is a bad idea. It means that in order to do any processing that isn't straight-up execution, you have to use the graph variants of whatever tree algorithms you were going to use. Those can get complicated, and some algorithms even become impossible. It's like the waterbed theory: I'm pushing too much complexity out of the core calculus.
If we disallow recursive structures, then we need to add Kleene star to get back to regular. To get to context free from here, we basically need symbolic reference. But I'm not going to do that. I have an objection to symbolic reference, and that is that you have to add all sorts of machinery to get it to work in a powerful way: Lexical pads, full qualification, etc. What I'm looking for is a lambda-calculusesque fix, which allows you to build recursion without symbolic lookup or infinite structures.
Maybe that means that I just mimic the lambda calculus and do pretty much what Parsec does: build a value out of functions that can be used to match strings. That gives you the full power of the lambda calculus, and all the research that has been done on it, to match strings. And Parsec can do predictive parsing, which is something I've wanted. The only thing it can't do is bottom-up parsing, which is also something I've wanted. But bottom-up parsing is more restricted than Perl 6 rules, so maybe that belongs at a earlier stage in processing.