Re: [stack] In praise of Prolog

On 3/13/07, Manfred Von Thun <[email protected]> wrote:
> On 9/3/07 6:54 PM, "Christopher Diggins" <[email protected]> wrote:
>
> I did look at your paper and read it with great interest. I am not really
> competent
> to judge the details, so I cannot help you in any substantial way. I had
> some
> superficial acquaintance with natural deduction rules for typing, but have
> never
> used the them in earnest. But it is a formalism which I should study and
> perhaps
> use to describe typed Joy.

A great book about the typing formalism which I think you may enjoy
(to be honest I found it very hard to understand, but I am not
formally educated) was Types and Programming Languages by Benjamin
Pierce which sums up the state of the art of type systems.

I hope to write an extended version of my paper which doesn't presume
a previous knowledge of type theory.

> Actually the type inference that I use for the
> Joy-to-Prolog
> compiler is so automatic when writing in Prolog that it is barely visible.
> It is simply
> this:
>
> IF a turns S into T1
> AND b turns T2 into U1
> AND c turns U2 into V
> THEN [a b c] turns S into V
>
> where there have to be the unifications T1=T2 and U1=U2. All that is
> automatic.

Now I see! That is brilliant! in a previous version of the Cat
compiler (which did type-inference) I ended up having to write a type
unifier from scratch. In effect I wrote a mini-prolog. I am surprised
that your technique of expresing types in a logic language (are there
others besides Prolog?) isn't used more often. Perhaps it is one of
those great ideas hiding in plain sight?

> There are two compilers at present, both about 18 lines long. One produces
> lengthy Prolog code which is still more efficient than the Joy source. The
> other produces optimised Prolog code in which all the stack-and
> list-shuffling
> is done at compile time and leaves no trace in the Prolog code. All thanks
> to
> Prolog¹s unification.

Very elegant!

> I also had a look at your implementation in C#. It looks much cleaner than
> my Joy implementation. Thanks in part perhaps to C#, but only in part.
> You are also a better programmer than I am. Well done.

Thank you, you make me blush. I am actually rewriting the parsing
engine so that it is easier to modify and extend. Afterwards I will
try to reimplement the type checking/inference engine (but first I
need to extend the type system with recursive types ... a long story
but I will say that they are neccessary to accurately express the type
of certain combinators such as Y and M).

Perhaps this may encourage others on the list to try their hand at
implementing their own concatenative languages. Anyway, C# is a very
pleasant and easy to use language. I find it is much easier to be
productive using C# than C or C++.

On other topic, for those interested I am now in the middle of
implementing a version of Cat with optional named parameters. This
will become the primary Cat variant (the one I plan on using in an
upcoming introductory programming book). This version of Cat gets
translated into the original point-free (i.e. no parameter names) Cat.

I'm taking a cue from Postscript with its different levels. In the end
the specification of Cat will likely have a half-dozen variants which
are expressed in terms of each other.

> - Manfred

Cheers,
Christopher