Do we use metacircular evaluators in real life?

In SICP, the authors define a metacircular evaluator of Scheme written in Scheme to change the semantics of the language. Do we do stuff like that in real life? In this episode, I explore this listener question.

Transcript

Eric Normand: Do people really use meta-circular evaluators? Hello, my name is Eric Normand and I help people thrive with functional programming.

This is from a listener question on one of the previous episodes. Very good question. This listener, they were reading "Structure and Interpretation of Computer Programs", and was wondering about whether in the real world, not in academic texts trying to teach lisp and programming, do we use the meta-circular evaluator? That's a really good question.

In order to answer it, I'm going to have to go back and explain what the book is doing, just so that all of us can understand the answer. In the book, Structure and Interpretation of Computer Programs, — I'm probably also going to call it SICP a little bit, that's the abbreviation SICP. There is an implementation of a scheme interpreter written in scheme. You write an interpreter for scheme in scheme.

Then in the next chapter, you actually take that and turn it into a compiler, which is pretty cool. You're compiling scheme to scheme. Now, why would you do that? A couple of reasons. One, is that scheme was designed as a language to explore programming language semantics.

When you write your new scheme interpreter in scheme, you're able to change the semantics of scheme a little bit. You could add instead of call by value — because functions are called by value in scheme. Meaning, if you do +AB, it takes the value of A and the value of B and passes it to the plus. But you could change it to call by name so that the variable A is passed in.

Then the plus function or whatever function could actually modify it or access it later. Maybe it accesses it lazily. It might never need to do that. You can play with the semantics of how the interpreter works, how the language itself works. That was the original design.

The second reason why you can infer why they did that is that the original lisp was defined in terms of itself. It's a tradition that these lisps — scheme is one of them — can interpret themselves. Then you're operating on code, which is represented as data. You could write a function that's an interpreter, and you're off to the races.

In that chapter, the interpreter is called the meta-circular evaluator. It's a bad name. It's too confusing what it means because it doesn't mean much meta-circular. What does that mean? Evaluator is fine.

Instead of an interpreter, it's called an evaluator. It just means it evaluates it to a certain value, a fixed value. Take some expression, and it evaluates it, you get the number five.

The meta-circular part is confusing because it's written in itself. That seems cool. A lot of people incorrectly understand. They incorrectly interpret that meta-circular means it's written in itself.

Meta-circular does not mean it's scheme written in scheme or it's Clojure written in Clojure. It's Haskell written in Haskell. That's not what meta-circular means.

What they mean in the book is that it's written with two mutually recursive functions. There's the eval function. That's the main evaluator function. It takes an expression and an environment, and it evaluates the expression.

Apply is the other function. A lot of the types of expressions you have in scheme are just handled in a big if statement in your evaluator. When you get to functions, you need to apply the function, so there's a function called apply, that takes the function and a list of arguments, and applies the function to it. Eval will call apply.

If you look at the definition of apply, it is defined in terms of eval because there's code in that function that now needs to be evaled. It's mutually recursive, which I think is a better name for this. Instead of meta-circular, it should be called mutually recursive evaluator.

Then it's not as cool because it's already recursive. Eval is already calling eval, but it's also calling apply, which is calling eval. They thought it was cool and whimsical.

There's diagrams with the yin-yang symbol and eval on one side. Eval is the yin, and apply is the yang. They're calling each other in this circle. At some point they're going to bottom out and hit a value that doesn't need to be applied.

It's a little cute. Let me put it that way. The idea of naming it something and calling out this idea that it's mutually recursive is not that interesting. Back to the question, do people really use this kind of interpreter in real work? I would say yes. In more advanced code, so code written by more advanced programmers.

I have seen this in the real world. Very much so. They're not writing Clojure in Clojure or Haskell in Haskell or what have you JavaScript in JavaScript. They're not doing that, but they are interpreting data using a recursive...It's recursive data. It's being interpreted, and the interpretation is complex enough that it is no longer a simple state machine.

It's moved on to the level of needing a stack, or it being Turing complete almost like it has an infinite tape. It's recursive, so the language is recursive. The data structure is recursive, and so the interpreter has to be recursive. Often it will have mutual recursion because there's the nesting of things.

Function calls are just nested expressions that are happened to be defined elsewhere. It's some sub-routine somewhere that you're calling out to. It's a call out there, but then it's just more code that needs to be interpreted. It's got that mutual nature that they were trying to call out with the name meta-circular interpreter, so yes.

I actually read a book recently called "Algebra-Driven Design". It uses Haskell as the language. They develop a grammar, a DSL for drawing graphics in an MC Escher style. Which actually comes from Structure and Interpretation of Computer Programs as well, and probably had its roots before then.

In Structure and Interpretation of Computer Programs, they just write the functions that do it. You can build up these layers of functions that operate on pictures. That copy them and mirror them and put them side by side and things like that. You can make these cool MC Escher style pictures.

Well, in this book, instead of writing the functions that do that, they write an interpreter for a minimal language that can represent these. It has the same effect. The only difference is that you have this data representation of all of the operations, all of the mirror and the rotate, and those things get represented in a data structure.

Then that data structure is interpreted into...Oh, and by the way, the data structure is normalized. Then it gets interpreted by this interpreter, and then you can rasterize it and draw it on the screen, which is pretty cool.

They were suggesting this technique because it lets you define that minimal set and operate as an interpreter would. There's room to add optimization steps and other things that you can't get when you're working in functions, which are purely opaque.

You're operating on this function that's going to return an image when you call it. You can't know like, "Well, if I rotate it four times, that's really the same as not rotating it. I can't optimize that away." It's going to rotate it four times because it's just a function. It's totally opaque.

Anyway, yes, we do use it. The complexity of the language is going to determine how complex your interpreter, your evaluator actually needs to be. You want to keep your evaluator simple. Often you can handle it with just a simple state machine.

If you've got a recursive language, you've got recursive expressions, then you're probably going to need a recursive one. Then if you got these nested things like a function is, then yeah, you're going to have a meta-circular one, a mutually recursive one.

If you liked this episode, please give me more questions so I can answer them. This is a cool one. I've actually got a backlog of questions. I've been not able to record as much as I'd like, but still, I love all these questions.

You can find this episode at lispcast.com/podcast. You can subscribe. You can find me on social media there. Also, my email, if you want to send me a question. I'm just going end it there.

My name is Eric Normand. This has been my thought on functional programming. Thank you for listening, and see you next time. Bye.