2013-12-09

Rewriting the Univ-Operator (=..) in Prolog

While I was working on my research project, I stumbled on this three year old question on stackoverflow, and I got inspired by it to do an attempt at rewriting the univ-operator in Prolog.

I found one source claiming that the univ-operator was once written as a predicate with the name univ, but I could not find how this predicate was written. After searching around, I also could not find anyone who rewrote the univ-operator back into a Prolog predicate. So I saw this as an exercise for me, and tried to do it myself.

First, I explain what Prolog and the univ-operator are. Then I show how I implemented the univ-predicate, and finally, I show that my predicate works and discuss the matter further.


1. Preliminaries

1.1 Prolog

Prolog is a declarative programming language, and has its roots in First-Order Logic. The logic of Prolog programs is expressed in terms of relations, represented as facts and rules. A computation is initiated by running a query over these relations. The word arity is used to denote the number of arguments in a term. Also, www.learnprolognow.org/ is a good place to start if you want to learn Prolog.

1.2 The Univ-Operator

The univ-operator, written in Prolog as =.. (an equality sign followed by two dots), is an infix-operator that converts between a term and a list. The functionality of this operator is best shown with an example.

Here are some examples of using the univ-operator:

?- a =.. X.
X = [a].

?- f(x,y) =.. L.
L = [f, x, y].

?- Term =.. [f, x, y].
Term = f(x, y).

?- '=..'(f(x,y),L).
L = [f, x, y].



2. Implementation

I use SWI-Prolog for the implementation. The following code is what I came up with:


If you ever use this code, I would appreciate it if you gave me credit for it.

I will now explain the code per predicate.

2.1 univ

The univ-predicate has two arguments: a term and a list. Depending on which arguments are atomic and which are variable, the predicate shows slightly different behavior. First the number of arguments are count. Then either a new term is created with functor name/arity, where F is the name and N is arity, or the name and arity are retrieved from an already existing term. Next, either the arguments are filled into the new empty term, or the arguments are retracted from an already existing term. And finally, a cut is placed to prevent backtracking for multiple solutions. Only one solution (the first) is the right one, and any other attempt on getting more solutions will result in an infinite loop. Theoretically speaking, my countArgs-predicate can count up to infinity. This is also the predicate I am discussing next.

2.2 countArgs

This is a very simple predicate which counts the number of items in a list. If however both arguments of the countArgs-predicate are variable, then there are infinite solutions (every non-negative number can be unified with No in this case, and Args can be a list of any size). If only "Args" is variable, then a list with No unbounded arguments is created.

2.3 fillInArgs

The fillInArgs-predicate, as mentioned above, either fills a new empty term with give arguments, or retracts the arguments from an already existing term. It uses the arg-predicate to fill in or retrieve the arguments. It also counts the number of arguments, this needs to match the count done by countArgs so that all arguments are filled into the term.


3. Evaluation

The implentation works. The following example shows the functionality of my predicate is the same as the univ-operator:

?- univ(f(x,y),L).
L = [f, x, y].

?- univ(f(x,y),[f|Args]).
Args = [x, y].

?- univ(Term,[f,x,y]).
Term = f(x, y).


Now, this predicate can probably be improved in some ways. Perhaps it can be improved by combining the countArgs-predicate and the fillInArgs-predicate, but I see no need to do it for now. Maybe I will try that later, maybe I leave it as an exercise for you. Feel free to give the solution in the comments if you find one.

It could also be interesting to do a benchmark to see which is faster, my univ-predicate or the original univ-operator. It should not be too hard to do this, since Prolog has this nice built-in predicate statistics/2, but I did not want to do this right now. Maybe I will do it later.

Further more, is this predicate really useful? Why not use the operator? Well, it provides more freedom, you can learn from it, and adapt it. Maybe you only need part of univ's functionality, you can rewrite my univ-predicate to get only the part that you need. Maybe you need the univ-funtionality twice in succession, and it is better to rewrite it into a new single predicate. Maybe it does not improve that much on performance (but I have not benchmarked it (yet), so I do not know this), but I think it is a good practice to often try to find ways to improve the performance of your code, or your code in general.

Feel free to join the discussion.