That's a very interesting topic and nice write-up, thank you for sharing!<p>For comparison, here is a small interpreter for a subset of Prolog, written in Prolog:<p><pre><code> mi([]).
mi([G|Gs]) :-
clause_(G, Body),
mi(Body),
mi(Gs).
</code></pre>
This states that: First, the empty conjunction (of goals) is true, and second, if there is at least one goal left, than the conjunction is true <i>if</i> there is a suitable clause whose body evaluates to true, and the same holds for all remaining goals.<p>For example, we can define append/3 as follows in this representation:<p><pre><code> clause_(append([], Ys, Ys), []).
clause_(append([X|Xs], Ys, [X|Zs]), [append(Xs,Ys,Zs)]).
</code></pre>
and then evaluate it with our interpreter:<p><pre><code> ?- mi([append([a,b,c], [d,e], Ls)]).
Ls = [a, b, c, d, e].
</code></pre>
Characteristically, it also works in other directions. For example:<p><pre><code> ?- mi([append([a,b,c], Rs, [a,b,c,d,e])]).
Rs = [d, e].
</code></pre>
and also:<p><pre><code> ?- mi([append(As, Bs, [x,y])]).
As = [],
Bs = [x, y] ;
As = [x],
Bs = [y] ;
As = [x, y],
Bs = [] ;
false.
</code></pre>
Now the point: The clauses of the meta-interpreter itself can <i>also</i> be stated in this form, namely as:<p><pre><code> clause_(mi([]), []).
clause_(mi([G|Gs]), [clause_(G,Body),mi(Body),mi(Gs)]).
</code></pre>
Now we only have to define what clause_/2 means, which we can do with:<p><pre><code> clause_(clause_(G, Body), []) :- clause_(G, Body).
</code></pre>
And now we can use our meta-interpreter to evaluate its own code as it interprets a program, arbitrarily deeply layered:<p><pre><code> ?- mi([mi([mi([append([a,b,c],[d,e],Ls)])])]).
Ls = [a, b, c, d, e].
</code></pre>
Hence, Prolog admits a meta-circular evaluator in at most 5 lines of code. With a better representation for clauses (using list differences), you can reduce the interpreter to 4 lines of code and at the same time make it tail-recursive.