In this post we’ll cover the built-in functions that Prolog has that are useful and also get into more advanced topics such as using assert and retract methods and talk a bit about how Prolog executes the code you write and how to trace through this execution to better understand how Prolog works.
Lets start by listing a few of the most important built-in functions that you’ll find yourself using a regular basis:
Type Testing
- var/1 - succeeds if term is currently not instantiated.
- nonvar/1 - succeeds if term is instantiated.
- atom/1 - succeds if term is an atom.
- integer/1, float/1, etc.
Term Unification
- =/2 (unification) - tests if Term1 and Term2 can be unified, example: A is 2 + 1, A = 3. % will succeed.
- =/2 (not unifiable) - tests that Term1 and Term2 can not be unified, example: 2 + 1 = 3. % will fail to unify.
Term Comparison
- ==/2 (equals) - straight up equality of the terms being compared.
- ==/2 (not equals) - straight up inequiltiy of the terms being compared.
- @</2 (lest than), etc - the various other comparison operators.
Lists
- append/3 - when it succeeds you’ll have a appended the first two terms to each other and the resulting list will be the contained in the third term.
- member/2 - succeeds if term1 is found within the list that term2 is referencing.
- delete/3, permutation/2, sublist/2
Above we’ve also introduced the predicate notation used to indicate how many arguments the predicate has which is /n where n is the number terms that the predicate requires.
You can always look up more predicates that are available to default installations on your own time now the interesting thing is going to be showing how powerful some of these harmless predicates really are. Lets start with the append/3 predicate and actually first show how this predicate is implemented:
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).The above is already built in so dont’ try loading a file with that otherwise you’ll be greated with a message stating “ native code procedure append/3 cannot be redefined (ignored)”. But lets use the predicate to show how easy it is to append lists to eachother, like the following shows:
That works as expected and gives us the response we’re expecting. Here is where we can show one of the most powerful features of Prolog and that is the ability to do inference of your predicates in order to logically fulfill them and do things that in other languages would require quite a lot of code writing.
Before we show how inference works lets instead do a trace of the previous usage of append so we can better understand how inference works. So to trace a Prolog execution in GNU Prolog once the interpreter is up hit Ctrl+C and pick t to enable trace. Then type the predicate as before and now you’ll be stepping through each step in the Prolog engine on the screen, like so:
Humm that was useless because the native method doesn’t trace through the Prolog implementation the same way. For this example load the previous append definition with a different name such as append1 and then you should be able to get a similar trace to the following:
Now the trace can be a bit hard to understand at first but as you trace through more and more predicate execution you’ll get the hang of how things work. So for our append implementation we defined append in a special way because we were taking advantage of tail recursion in Prolog and we defined the append predicate like so:
- If you have an empty list and a list Ys then the result of appending them is Ys.
- If you have a list with head X and tail Xs and another list Ys, then the resulting list is going to consist of putting X at the head of the list with Zs being the concatenation of Xs and Ys.
Because of that special definition the Prolog engine will create your resulting list as it exits from each of the calls and now while its proceeding to match the termination predicate at append1([],[4,5,6],_116). So knowing this and looking at the trace you now know that the Prolog enginew as trying to reduce your initial request of append1([1,2,3],[4,5,6],L) into one that terminated with the append1([],[4,5,6],_XX) and then worked its way backwards to create the resulting appended list.
The really interesting thing about this backward inference and the ability to deduce which elements were moved around based on how you defined a predicate allows Prolog to do even more interesting things such as:
We just used our append method to infer what list appended to [4,5] gives us the list [1,2,4,5]. This may not seem ground breaking but think about how hard this would be to implement in another language and you’ll soon see the power of inference. If you want to see a quick way that inference can be used, lets take the problem:
- given a list of elements enumerate all of the possible combinations of 2 lists that can be append to create the resulting list.
Getting Prolog to do this for us is as simple as:
Instead of having the interpret iterate the possible solutions lets introduce the usage of the findall predicate which can be used to create a List of solutions. The predicate itself is defined as findall(Object,Goal,List) where the Object is the elements from the Goal you wish to put in the List for each solution found. So lets just show how to use findall to get all the solutions in a nice neat little list.
While on the subject what if you wanted to not include any solutions with empty lists as part of the concatenation ? Here’s one possible solution:
A simple non unification test for A and B to the empty list term and we’ve fixed our problem.
We’ve covered quite a few things in this post and I am probably running through a lot of things without explaining too many details and showing more implementation and usage scenarios. I really don’t want to spend too much time writing up theory and explanations you can find online and instead would like to focus on how to use the various features to complete tasks that would be very difficult in other languages.
The next post will cover more details of tracing and I will try to also introduce the notion of “cutting”, which involves controlling how Prolog does backtracking through your predicates.