Logic Programming with New Wombat

In the previous post I introduced the idea of negative types which are the type of holes. The most common way to introduce them is by backquote-identifer:

`three = 3

Here `three has inferred type -Int, and the hole is immediately filled, giving meaning to three.

Here is a classic logic programming predicate from the Mercury language:

append(Xs, Ys, Zs) :-
( Xs = [], Zs = Ys ;
 Xs = [X | Xs0], append(Xs0, Ys, Zs0), Zs = [X | Zs0] ).

The beauty of this is that it runs correctly whether you are given Xs and Ys and want to calculate Zs, or you are given Zs and want to calculate all of the Xs,Ys prefix-suffix pairs to make Zs, or various other options.

Rendering that in Wombat, we assume: that predicate returns unit (hence trailing “;”s) or fails harmlessly; and that a case expressions fails harmlessly if no entry matches (though I think the doc currently says something else); and that prepend does the same as the “|” construct in Mercury:

`append = {
(`Xs, `Ys, `Zs) = $;
case of [
{Xs=[]; Zs=Ys;}
{Xs=prepend(`X,`Xs0); append(Xs0,Ys,`Zs0); Zs=prepend(X,Zs0);}
]
}

We can call this with all arguments as values and it will just be an assertion style check:   

append([1 2], [3 4], [1 2 3 4])

Or we can call it with the 3rd argument as a hole, and it will be filled in:

append([1 2], [3 4], `rslt)

Here Zs gets unified to be the same hole as `rslt. The unification step Zs=prepend(X,Zs0) then fills that hole.

If we have the concatenated result and want the pairs that will give that:

append(`prefix, `suffix, [1 2 3 4])

then we only get the first option with prefix=[] and suffix=[1 2 3 4]. It would be nice to introduce iterators and backtracking to Wombat in a compatible way. However before we go there, we note that it is more natural in Wombat to do this in a way that looks functional.

`listCat = {
(`Xs, `Ys) = $; `Zs = `$;
case of [
{Xs=[]; Zs=Ys;}
{Xs=prepend(`X,`Xs0); `Zs0 = listCat(Xs0,Ys); Zs=prepend(X,Zs0);}
]
}

In the old Wombat, `$ was always the hole that was where the procedure result would go. In the new Wombat it might not be. If the result of the call is being unified with something, then the something becomes the value of `$. Suddenly the semantics of Wombat unification become much simpler. So in

[1 2 3 4] = listCat( [1 2], [3 4])

`$ will be set to the value [1 2 3 4]. Indeed `$ could be a structure with a mix of values and holes:

[1 2 `x] = listCat( [1], [2 3])

This is all a little too good to be true. I’m sure I’m missing something.

Getting back to iterators and backtracking. It can’t be as simple as Python iterators, because each yield has to specify values for all the holes in input and output that the procedure is responsible for. It would be nice if `{ initiated an iterator and one could write:

`listCat = `{
(`Xs, `Ys) = $; `Zs = `$;
eachCase of [
{Xs=[]; Zs=Ys;}
{Xs=prepend(`X,`Xs0); `Zs0 = listCat(Xs0,Ys); Zs=prepend(X,Zs0);}
]
}

And have it create an iterator-like thing that the caller can advance. I fear I don’t know enough to get this right.

[It is an interesting thing how much parallel there is between programming and physics. Holes are a recurring theme in Physics, being places where particles are absent, they often act like particles. Here we have been expanding the role of holes in Wombat and making them behave a bit more like values. Physics also has its Quantum core where everything is reversible and information is neither created nor destroyed. Programming languages can, and possible should, have a reversible logic core. Then, in both physics and programming, we have the real world where things move forward irreversibly with entropy increasing.]