The magic of metalinguistic programming

It's just a change of paradigm

A new chapter of Runnable Specifications has passed the “valuable enough to read” threshold. This time, it’s the Time Lens, which talks about build a notion of time into your model. As always, I appreciate questions and comments of all kinds. I’m not sensitive so you won’t hurt my feelings if you tell me you hate it! I’m especially looking for people to pick apart my reasoning. These ideas are at the edge of my abilities so I need all the help I can get.

Check out my book called Grokking Simplicity and it’s the functional programming book you can recommend to beginners. If you don’t recommend it to your friends, please recommend it on Amazon.

I will be speaking at the Houston Functional Programming User Group on January 15. It’s free and online and open to you. I’m going to present the last 2.5 domain modeling lenses.

---

The magic of metalinguistic programming

There’s a question I’ve asked myself for many years: Why is it that a good abstraction can save code? Let’s say I have some problem, and a straightforward solution takes 1,000 lines of code to write. It’s a straight path.

But along the way, I realize that there’s a shorter path. First, I write a small abstraction in 500 lines of code. Then I write 10 lines of code describing the problem I’m trying to solve. Then I’m done. In 510 lines! Where did the savings come from?

One reason it seems counterintuitive is probably because of the “path” metaphor I was using. There’s no path shorter than the straight path. Shortcuts only work if there are turns. But in code, it seems that the straight path sets a maximum bound for the length of the problem. If another solution takes more lines than the straightforward solution, you probably shouldn’t use it. But some solutions might take significantly less code if they take the right detours.

Take the expression simplification example in Lisp: A language for stratified design.

It should be possible to simplify (x + sin(xy)) (sin(xy) - x) + cos(xy) cos(ух) to 1-x².

Alright, go ahead and write a straightforward program that simplifies this. I’ll wait.

Or maybe don’t do it (like I haven’t) and just assume (like I have) that it will take hundreds or thousands of lines of code. It would have to have if statements that check if an expression includes a double negation, you can eliminate both negations. And one that checks for cos(2x) and replaces it with 1 - 2sin²(x).

You might see the repetition, where the if statements are different patterns you’re looking for, and you have to traverse the expression tree for each one looking for the elements to see that they’re related in just the right way. Plenty of duplication, but no way to eliminate it, no matter how hard you squint, using only the tools Scheme gives you—this is what I’m calling the straight path.

What the paper presents is to first take a detour and write an interpreter. The interpreter is 80 lines of Scheme which applies a set of rules to an expression. Then you write 30 rules, which are about 3-4 lines each. That’s 90-120 lines more. So in 200 lines of code, you’ve written a simplifier that can accomplish that simplification task, and more. The detour through the interpreter saves you code! Programming is non-linear.

Something is going on. I don’t quite understand all of it, but the paper provides a clue: It’s the change in paradigm. When you write an interpreter, you get to switch to a new programming paradigm. In this case, it’s from a functional language (Scheme) to a pattern matching language with backtracking (perhaps term rewriting is the closest). All of the tree traversal, checking of the elements and their relationships, and the backtracking (when you hit a dead end), is handled in the interpreter. The “program” you write consists only of the differences, which are the patterns and what they get replaced with. It just so happens that that paradigm is great for writing expression simplifiers.

Writing an interpreter in your language to solve a problem is called metalinguistic abstraction. It’s one of those things Lispers do a lot, sometimes without even knowing they’re doing anything special.

Notice that the metalinguistic abstraction isn’t magical at all. It’s purely mechanical leverage. It centralizes the if statements, loops, and equality checks you’d have to write by hand. But instead of writing them by hand for each rule, you drive them with data, and hence reuse them. But it’s also easier to write, with fewer lines of code. It’s similar with OO type-based dispatch. If you’re dispatching a lot based on type, you may get a lot of leverage out of a vtable system.

The term rewriting paradigm is not great for every problem. We still need to choose the right abstraction. It’s mechanical and not universal, so not magical. You need to choose the right detours.

Metalinguistic abstraction happens to be one of the main tricks Alan Kay’s team used at VPRI to take steps to reinvent computing: Make it super easy to embed a new language right where you are in the program. They seemed to make really good use of it. I find that it’s very powerful for some situations, but encountering them is rare.

I think metalinguistic abstraction is a rich, unexplored topic in industrial literature. It’s one of the books I might write after my current one. If I still feel like writing. The biggest problem I see with this topic is that there’s not much of an audience, so not as rewarding financially or spiritually. If you’d like something to read now, check out PAIP by Peter Norvig and Software Design for Flexibility by Hanson and Sussman.

Have you ever used metalinguistic abstraction? Let me know in the comments!

Rock on!
Eric