[stack] In praise of Prolog

For a long time I had been dreaming of static type checking for Joy, and
perhaps even a Joy compiler of some kind.  Only recently did I have a lucky
thought: why not look at Prolog as an implementation language? (Prolog =
PROgramming in LOGic  - if you are willing to do violence to anybody¹s
definition of logic. Apart from the name, a wonderful language with
backtracking and unification(two sided pattern matching).

I had had an some experience with Prolog starting 25 years ago, but dropped
any involvement after the Japanese ³5-th generation language²  programme
faded. But I had written some very early Joy interpreters in Prolog.

Found an old SWI-prolog on my inherited home computer, and started
what turned out to be very fruitful 6 weeks.

Implementing core Joy is ridiculously simple. There are transformation
rules for turning one stack into another:

    swap turns [X, Y | S] into [Y, X | S].
    + turns [I, J | S] into [K | S]  :-  K is I + J.

This readable syntax is what Prolog allows you to do. The four occurrence of
³ | S mean ³the rest of the stack². The definition for swap has no
condition, the one for + has as condition the little bit after the :-
³turnstyle². Everything else is in the same style, even the combinators

I am leaving out the annoying fact that Prolog needs a comma as a separator
between listi items. I am also leaving out that I use a simple preprocessor
(written in Prolog, of course), which ³decorates² literals in programs, or
the stack, or in quotations, with type information. To keep things simple,
at the moment I only allow two types: numbers and lists.

For core Joy I only have the basic stack and list shufflers, which all do
not have a body in their definition, just like swap above. Only one
arithmetic operator, +, so far, and quite a few combinators including the
recursive step and map. That is the core interpreter.

In principle it sounds easy to turn any interpreter into a compiler: in the
program to be compiled, for each instruction of the source language, emit
the instructions of the target language which the interpreter would be
executing if it were running that program.

In practice this is a dreadful undertaking if the implementation language is
C, as it is in my version on the web. Essentially one would be writing
something as complex as the original interpreter, or more complex. Also, it
is not easy to have to maintain two large programs, especially if the
language is developing. Better to have only one version, and have a program
to turn the interpreter into the compiler. Or have a definitional version
(perhaps in M4), which can produce the interpreter or the compiler.

Prolog (like Joy) has the wonderful capability of allowing one to look at
the bodies of definitions (by ³clause²), doing something with these bodies
and constructing something that can later be executed (by ³call²). Languages
such as the Algol descendents cannot do this. I do not know whether (the
interpreted implementations of) the Lisps can (John Cowan: ?).

So Prolog allows Prolog programs to inspect other Prolog programs like the
above snippets for swap and +. This means it is extremely simple to write
all kinds of meta programs.

One kind are interpreters, which mimic the operation of Joy with some
variation. For example, I have written a simple tracer which behaves like
the i combinator but also writes out every step taken during the execution
of the quoted parameter, even if that quotation contains calls to other
combinators like the recursive step and map and their parameters. There
are several variations to this general idea.

The other kind are compilers which, just like i again, expect a quotation
(written in Joy) and leave behind a translation into Prolog. One interesting
feature of this process is that stack and list shufflers just disappear from
that translation, because all their work is essentially summarised in the
stack description for the before- and after-stack of the entire quotation.
Redundant stack and list operations just disappear. Optimisation for nix!

The output of the compilation is a typically rather short program in Prolog
which needs to be called to do any work. Compilation and calling satisfies
the equation:

     compile call  ==  i

In fact there are already variations on the compile/call theme.

I am still learning about the various possibilities of meta programs, and I
intend to explore the area further, especially since it is so easy to do in
Prolog.

So far I do not have definitions in Joy. I have left this for later, because
the intention is of course to store not the Joy form of a program but
preferably its compiled form in Prolog.

I¹ll be happy to answer any questions. Also, I intend to report further on
any progress. But I will have to learn how to move files from my PC at home
to my Emac here at (what used to be) work. Only then will I be able to send
examples to this group.

To the concatenative language smiths: best wishes with you efforts.

- Manfred






[Non-text portions of this message have been removed]