The previous post on partial evaluation was for too vague for my liking, so i will try to write some mathy looking stuff, in an effort to bring more clarity into the approach that is swirling around.
Let me try and get some symbols out and detail these thoughts. Since the original paper of Futurama talks vaguely about variables and ends mostly in questions, let's start from zero.
Let's take a language to be defined by an interpreter. An interpreter must have a syntax tree to walk/interpret, but how the tree comes about (eg though parsing of a text form) is not the defining feature of a language.
Through the interpretation the interpreter defines what the constructs of the language (or nodes of the tree) mean. A more precise definition would then be through tests and expected behaviour.
We define a hierachy of languages in Levels 0-x, where the level 0 has a hardware interpreter we call computer. And while it uses a binary format for it's representation it is important to note that it is still interpretation, ie the cpu/computer is the interpreter of level 0 "code".
Writing a new Language level thus always involves writing an interpreter for that language. And since the language does not exists, the interpreter has to be written in a language that does, often a level below. This is especially obvious for level 4 languages and i'll go into why it was not so obvious for level 3 below.
I'll just define Transpilers before moving on to Partial evaluation as it will be relevant in the future
Partial evaluation is a technique to speed up programs by evaluating static data, or doing calculations involving static data. `E^m` is a partial evaluator when `E^m(P_m) == P_n^' ` so that `E^m(P_m xx I) == P_n^' xx I -> O` with the objective that `P_n^'` runs faster
We can take the generated Program to be one of two (main) things. Either `n == m` , so of the same language. This makes sense as the Evaluator works on the language `m`. But the paper hints at creating an executable, thus `n == 0 != m` , in which case the Evaluator would include a compiler, we shall exclude this option, or rather prefer to make such an arrangement explict. This "deviation" also changes the second projection to produce a Transpiler, not compiler.
The first projection is when when we use an Evaluator on an Interpreter we get a program that is faster than the original. So with the Program being static in respect to the evaluation we get `P_0 ( I_d ) == E^m (Int_0^m ( P_m)) ( I_d) -> O` Here we are faced with an uncertainty, namely which language the interpreter is written inwe will call it `n` (and discuss melow). So we get to `E^n (Int_0^n ( Int_n^m xx P_m)) ( I_d) -> O` . The Projection then reads `E^n (Int_n^m xx P_m) == P_m^'` being faster than the original `P_m`
The second projection is that when we use an Evaluator on its own code and an Interpreter we can generate a transpiler that can nevertheless be compiled. This assumes the Evaluator to be in the same language as the Interpreter, so we expand the previous to `E^m (E_n^m(Int_n^m ( P_m))) == T_n^(mm) (P_m)` . Since `T_n` is written in `n` we can use an existing compiler `C^n` to compile it , and thus `C^n (T_n^(mm) xx P_m) -> P_0`
To "generate" a compiler by writing an Evaluator and Interpreter makes sense for a new level of language. Writing a compiler involves holding the compile, and runtime in ones head at the asme time and doing this while solving an unknown problem. Also debugging is extremly difficult. Which is (imho) why it has never been done for level 4 languages.
The approach seems promising for `n == m - 1`, or specifically `n == 3` and `m == 4`
It might even be expanded to the layers below. I shall make this explicit, ie use real languages and not numbers, in the next post.
