Home » forums » LtU Forum

Question: do you have to climb the tower of interpreters?

You know what is interesting about meta-circular interpreters? The infinite recursion of eval-apply is always broken in the end by the application of some primitives. So in the end, no matter what your computational model is, you are still executing a stream of primitives in your "ground" language. And, usually, "lambda" is all you'll ever need as a primitive. But looking at so many toy interpreters you'd see that "lambda" is not quite so "primitive" and requires a lot of machinery to work.
So instead of providing some means of abstraction directly as a ground mechanism to build everything else around it, I wanted to do a simple thought exercise and to go from another direction: if we have a fixed set of primitives, without means of abstraction, what are the ways to compose/combine them?

Imagine we have a really old CPU without a support for a call instruction, but it has a conditional jump, ALU instructions, loads/stores. It's a simple exercise to define how would a call instruction would look like (in pseudo-assembler):

define CALL(target_addr):
load stack_pointer, tmp
store tmp, the-address-of-the-next-instruction-after-call //don't care now how we can get this
dec tmp
store stack_pointer, tmp
//skipped the frame pointer manipulation
branch target_addr

So, in general, our CPU IS capable of doing necessary steps to create an abstraction mechanism, but there is no way to "plug it in" by the CPU itself unless our preprocessor rewrites all "CALL" tokens into these primitives. Not good.
The only other way I could think of is to interpret another language, which has this CALL as primitive. I.e. the CPU itself becomes such a "preprocessor". But does that mean that the only way to escape deficiencies of your current computational model is to climb the tower of interpreters? (aka interpret another language that has that capability. My favorite examples: a Scheme interpreter with first-class macros in scheme by Matt Might, Kernel interpreter in Scheme by J.Shutt, 3-LISP by Brian Smith)

Are there any other ways, besides interpreting another language? Maybe there is a way to build such a reflexive virtual machine that can modify and extend itself? I haven't seen such yet.

I've recently stumbled upon Ian Piumarta's "Open,extensible composition models" VPRI Technical Report TR-2011-002 which describes a meta-circular evaluator, where instead of your usual big cond-statement in eval you select your evaluator based on the type of expression you are evaluating (same for applicators) and this mapping is available for the programmer. I've found this a very interesting read, maybe someone could comment on this paper, as I've surely missed a lot.

I have surely asked a lot of questions in a very unstructed form, but if anyone would maybe give some useful pointers (something to read on the topic, maybe) it would be greatly appreciated.

By artemonster at 2017-07-26 08:56 | LtU Forum | previous forum topic | next forum topic | other blogs | 4500 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Link

Open, extensible composition models, Ian Piumarta; VPRI Technical Report TR-2011-002.

By John Shutt at Wed, 2017-07-26 12:58 | login or register to post comments

Nature of the tower

A meta-interpretive tower is, after all, a way of understanding how a PL works by describing how to interpret it. There isn't really a /unique/ tower; for each PL one could climb "up" in various directions, each step up depending on what meta-language one chooses. I explored Kernel using a meta-circular evaluator written in Kernel, but of course one could also write one in Scheme, or any number of other languages (and I take it folks have used lots of other languages for this :-). So really the observer creates the tower in the process of climbing it. (I do look forward to studying that VPRI paper.)

The presence of an explicit eval device, I note, doesn't directly limit the direction of a meta-evaluation tower, but does imply that the language is effectively interpreted rather than compiled — which I believe has profound cognitive consequences that I don't have a good handle on, and profound formal theoretical consequences that I wrote an essay on last year (blog post).

By John Shutt at Wed, 2017-07-26 13:47 | login or register to post comments

Alternatives?

Are there any alternatives to the interpreter tower? The same guy, Ian Piumarta has several very interesting publications on this topic:
Open, extensible object models. The simple extensible message passing system is implemented, where even message passing semantics are extensible.
This, and his other research then culminates in COLA (renamed to ALBERT):
Accessible Language-Based Environments of Recursive Theories. I am sure you'll find this read very entertaining.
Also, I never knew you had a blog. *grabs popcorn* I know what I'll do for next hours :D

By artemonster at Wed, 2017-07-26 19:14 | login or register to post comments

Why not good?

Why is it not good that CALL be expanded to the primitives?

It's a key question IMHO. The way I see it, you have a ground system and an architecture for extension. Historically, extensions had two distinct kinds: macros and subroutines. Macros (as in IBM macro assembler) are all powerful but typically only provide one level, that is, you cannot use them to define new ways to define more macros, only new machine calculations. Subroutines are almost directly supported but architecturally highly restricted, if you know exactly what call and return do you can "undo" them and get additional value out of them.

For example, if you call a label which starts by popping the return address to some location, which you can subsequently call, you have just added explicit continuation passing to your tool box. But to macro'ise it, you have to regularise where that continuation is saved to.

What I'm saying is that you cannot isolate protocols of machine instruction execution from their architectural model. In Haskell, you can do all sorts of nasty things like mutation you're not supposed to be able to do, not directly in the language but by building a model and then emulating it inside that model.

The problem is such models don't necessarily compose well with other models you might build. The tower of interpreters arises because each one first imposes an architectural model in order to actually define anything and allows extension within that model. If you want to do something that doesn't fit that architecture, you can always do it by building a new architecture *on top* of that one (assuming the model is powerfui enough to allow model building).

So the real problem is not to get away from the tower, but to make all the levels of the tower the same structure so transcending is easy.

There IS such a system. Yes, there really is. Its called Category Theory. You get three levels, categories, functors, and natural transformations and then you have everything: its meta-recursive because you can organise your functors into categories and so ascend as far as you like, all using the *same* architecture.

In my own system I am trying to do something less ambitious: I have quirky expressions, slighly more regular types which are loosely normally evaluated lambda calculus, and now I'm doing kinds, which are a simple, pure lamda calculus. The idea is when I needs sorts, I can just reuse the kinding calculus one level up. The "tower" has a roof when the architecture for the modelling reaches a fixed point.

By skaller at Wed, 2017-07-26 14:29 | login or register to post comments

This is why

Why is it not good that CALL be expanded to the primitives?
Because that means that someone else has to do this for us. That means that we are not on the ground level. That means someone "interprets" our code beforehand (i.e. at compile time).

What I'm saying is that you cannot isolate protocols of machine instruction execution from their architectural model.
This is a very good thought. I'll save that and think about it for a while.

So the real problem is not to get away from the tower, but to make all the levels of the tower the same structure so transcending is easy.
Nooow I am starting to slowly understand what all these papers about towers of interpreters were *actually* about ^^

There IS such a system. Yes, there really is. Its called Category Theory.
A quick googling revealed some stuff that is beyond my comprehension. Is there any good introductory material that you can recommend? Or maybe some practical examples?

Thanks for your interesting insights!

By artemonster at Wed, 2017-07-26 19:26 | login or register to post comments