Day two of Prolog focused on problem solving with recursion and lists, as well as a more understanding of what unification in Prolog is. Let us look at some code.

fib(X, Ans) :- Xm1 is X - 1 ,Xm2 is X - 2 ,
               fib(Xm1, Sub1), fib(Xm2, Sub2),
               Ans is Sub1 + Sub2.

This is an implementation of the fibonacci function in Prolog. In reading this it is important to remember that questions are usually asked of Prolog in the form of some query with a variable for Prolog to fill in. Thus we are going to call fib(5, Ans) and Prolog will put the answer in the variable Ans, as opposed to doing something like Ans = fib(5) like we would in other languages.

The first two lines define the base case of the function, if Prolog can match (unify) the number you pass in the first position to 0 or 1, it will unify the answer variable with 0 or 1 respectively. If you pass in a number higher than 1 then the third rule unifies to this and Prolog can begin to explore the subgoals.

The first two subgoals assign some variables to values we want to use. Note that this is the first use of assignment we have seen in Prolog, and the predicate that performs this is the 'is' predicate. Everything else we have seen so far is unification, even something like X = Y is unification, not assignment; it means 'make X and Y the same' (which could involve doing something to X or Y or both depending on the other rules in the accompanying context). With that the rest of the function should be fairly clear, we call recursively call fib on the successively smaller numbers until the base case is reached, at which point it will add up all of those sub answers, note that in the recursive calls to fib, we give a different variable for the answer to bind to so that it is available for us to add together when it returns.

Lists and Recursion

Lists are an important data structure in Prolog, in fact so far i have only seen two, lists and tuples, with tuples appearing to be immutable. Lists can also be deconstructed in the following manner

[a, b, c] = [Head|Tail]

Prolog will unify Head to 'a' and Tail to the rest of the list [b, c]. Note that [Head|Tail] cannot unify with an empty list as there aren't two things to pull apart in that for unification. A one element list will unify with [Head|Tail] with Tail being set to the empty list. With that let as look at some code that operates on lists.

rev([Head|[]], [Head]). % rev of a single element list is the list
%Note append will not work with non list parameters, remember to put Head in []
rev([Head|Tail], Ans) :- rev(Tail, Sub),
                         append(Sub, [Head], Ans).

The code above reverses a list in Prolog. The base case is to reverse a one element list (which is simply the list itself). The second case, splits the list into Head and Tail parts and then calls reverse on the Tail (putting the answer in Sub). It finishes by appending Head to whatever comes back from reversing the tail.

The append function will be true when the third param equals a concatenation of the first two, thus when used in this way, with Ans unbound at the moment it acts as a list builder. Another way to think of this is Prolog will do whatever it can to make the call to append true, part of that involves building the list that is your answer.

% the semicolon ; is an OR. commas, are AND
min([Head|[Head2|[]]], Ans) :- Head @< Head2, Ans is Head; Head2 @=< Head, Ans is Head2.
min([Head|Tail], Ans) :- min(Tail, Sub),
                         Ans is min(Head, Sub).

This piece of code finds the minimum value in a list. Its base case is a two element list. You will note that in the left hand side, we deconstruct the input parameter in a way that the first clause will only match two element lists and thus we can define our base case. The subgoals for this case are interesting because in figuring this out, I found out how to do an OR operation by using the semicolon. For this rule to be true either the first part or the second can be true. In proving which is true, Prolog will compare the two elements in the list and set Ans to hold the lower one. Note that the assignment operation will only work if the subgoal preceding it (the comparison) turns out to be true.

In dealing with larger lists we use the same strategy as above. Split the list into the first element (Head) and the rest (Tail), find the minimum in Tail and then find the minimum between Head and the answer you got in the previous step!

Looking at the left hand side of the clauses above, one thing I noted is that in many Prolog solutions a lot of work gets done in that deconstruction, and understanding it is key to understanding how the solution is going to work.

The last task in the days homework was to write a sort function in Prolog. I decided to try to come up with something using similar strategies as above. I came up with the following that kind of works but is definitely not the best solution. I say 'kind of works' because while the first answer I get from Prolog when calling my sort function is correct, it can continue to generate an infinite amount of incorrect solutions (one thing to note is that whenever the Prolog system finds a solution to your problem it stops and shows it to you, it then asks if you want it to continue to look for other solutions - this can be highly useful, but is obviously not correct in this situation).

/*The following is a pretty hacky way of sorting. The first solution that satisfies
 ysort will be correct, however it will continue to generate an infinite number
 of (incorrect and longer) solutions. lsub also generates multiple answers, only the
 first one is correct. I don't have enough understanding of prolog at the moment to
 figure out why it continues to generate answers*/
lsub([], Minus, []).
lsub([Minus|[]], Minus, []).
lsub([Head|[]], Minus, [Head]).
lsub([Minus|Tail], Minus, Tail).
lsub([Head|Tail], Minus, Ans) :- lsub(Tail, Minus, Sub),
                                 append([Head], Sub, Ans).

/* Overall, it is closest to an insertion sort, it finds the smallest element of the
source list puts it at the head of the target list and continues building the list
in this fashion. */
ysort([], []).
ysort([Head|[]], [Head]).
ysort(List, Ans) :- min(List, CurrMin),
                    lsub(List, CurrMin, Rest),
                    ysort(Rest, Sub),
                    append([CurrMin], Sub, Ans).

The first function defined was my way of removing a single element from a list, thus lsub(1,2,3,4, 3, Ans) should put [1,2,4] in Ans. As you can see most of the work is done in the restructuring of the input lists, particularly I define a number of cases for two element lists, and check to see if the value we want to remove, Minus, is an element of those lists, in which case I return the rest of the list. I also check to see if is the first element of a given list of length longer than two. If you look at the code and think of it in terms of Prolog unifying your input the variables in the clause it makes sense. I then use the recursive approach used above to build up the new list, with the element in question removed.

The second function, ysort, works by getting the smallest element in the source list, appending it to a new list, then removing it from the source list and repeating the operation. It's pretty much an insertion sort, and makes sense to me when I read it. I can't tell if it is this function or lsub that is the cause of my multiple answer generation woes (note lsub also generates multiple answers, the first of which is correct).

Prolog code is very dense, once you get into thinking of unification and the system trying to 'make your clauses true by any means available' the code becomes more understandable.

After my attempt at sorting I looked for some proper solutions to this and found a few useful links. One of which gives code for a bunch of different sorting algorithms including mergesort and quicksort. It takes a minute to grok exactly what is going on, but reading these reminded me that what is going on the left hand side of a clause is just as important if not more than the right hand side. In some of these the right hand side is effectively a condition to determine whether to apply the unification described on the left. For the curious here is the link.

My code for the day, that includes the above as well as a couple other small functions is up at github.