[Haskell-cafe] Learn Prolog...

Thomas Conway drtomc at gmail.com
Tue Sep 4 23:21:52 EDT 2007

On 9/2/07, Andrew Coppin <andrewcoppin at btinternet.com> wrote:
> > One of standard exercices in Prolog is the construction of the
> > meta-interpreter of Prolog in Prolog. While this is cheating, I recommend
> > it to you. It opens eyes.
> Ever tried implementing Haskell in Haskell? ;-)

In many respects, Haskell is a much higher-level language than Prolog.
Before you all gasp and go <plonk!>, consider the following argument.

In Prolog, you need to pay close attention to the exact order in which
things are executed. In preditcate logic you may write (using
haskellish term notation)

a(xs,ys,zs) <= (xs = [] /\ ys = zs) \/ (xs = (x:ws) /\ zs = x:vs /\
a(ws, ys, vs))

but to interpret this as a *program* you have to consider how it will
be executed. In particular, using SLD resolution, conjunction (/\, or
',' in Prolog notation) is not commutative as it is in predicate

This is good in some respects - in this respect it is easier to write
efficient Prolog than Haskell, but at the same time, compilers can't
rewrite programs (i.e. optimize) nearly so effectively. And that's not
even taking into account that Prolog is impure, so the compiler has to
watch out for side effects.

Also, still considering "append", as a high level specification of the
relationship between lists and their concatenation, it is ill-typed:

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

(Ye Gods! My Prolog *has* rusted quickly!)

>From the clauses, it is clear that the first argument must satisfy

list([X|Xs]) :- list(Xs).

but the same is not true of the second and third arguments.

?- append([1,2,3], 4, Zs).
Zs = [1|[2|[3|4]]]

Lee Naish has written in detail on this subject.

Another argument in favour of Haskell being high-level is John Hughes'
"glue" argument. If you don't know what I mean, go and read "Why
Functional Programming Matters".

Hey, that was fun. I have barely written *any* Prolog since I finished
my thesis. :-)

Dr Thomas Conway
drtomc at gmail.com

Silence is the perfectest herald of joy:
I were but little happy, if I could say how much.

More information about the Haskell-Cafe mailing list