Implementing CP Prolog - 7

Calculating the factorial function is the poster boy of recursion. It's very easy to define the factorial of a positive number: if the number is 0 then the factorial is 1, else it's the number itself times the value of the factorial of the number less 1. In other words, the factorial of 1 is 1 * factorial (1 - 1) = 1, and the factorial of 2 is 2. More interestingly, the factorial of 3 is 6 (because that's 3 times 2), and the factorial of 4 is 24 (because that's 4 times 6). This can easily be defined in an imperative language such as Pascal as follows.

function factorial (n: integer): integer;
begin
 if n = 0
  then factorial:= 1
  else factorial:= n * factorial (n - 1)
end;

So simple yet so bad, as calculating the factorial of a number such as 10 will cause a great deal of stack space to be used because of the recursion. An iterative calculation is just as simple and executes with a constant and minimal amount of stack space, as well as being faster.

function factorial (n: integer): integer;
var
 i: integer;
 
begin
 result:= 1;
 for i:= 1 to n do
  result:= result * i;
end;

But what does the factorial function look like in Prolog?

factorial (0, 1).
factorial (N, F):- N > 0, N1 is N - 1, factorial (N1, F1), F is N * F1.

This matches the initial description that I gave. The factorial of 0 is 1, otherwise assuming that N is greater than 0, the result (F) comes from multiplying the number itself (N) by the factorial of N - 1 (F). The rule looks a bit strange but that's because of the syntax that Prolog requires. 

Last week's installment had the interpreter solving several goals where the final goal included an assignment ('is'), multiplication and addition. A great deal of work was spent on getting that 'is' functor to do what it was intended to do. Calculating the factorial depended on that 'is' functor as it is called twice on every invocation. It turns out that it wasn't correct. 

Before I could tackle the factorial, I wanted to ensure that the 'add' ¹ function that I added a few weeks ago still worked. It didn't, so first we had to spend no small amount of time getting this to work again. I knew that 'add' would be a goal on the path of getting the factorial to work.

Let us say that I spent several exceedingly frustrating hours yesterday and today trying to get my interpreter to calculate the factorial. I would run a test and show CoPilot the results. 'Add this', it would return. So I added something more and sometimes it would improve the situation but more often that not would make no change. There are parts of the interpreter (especially handling the 'is' functor) that went through several changes. Sometimes the changes would make things worse, meaning that I had to restore code from previous versions. At one stage, CoPilot said 'do A', then when that didn't work, 'do B', then 'do A'. Exceedingly frustrating. It completely ruined the 'resolve' function that lies at the heart of Prolog, so I had to restore this from last week's code (I back everything up religiously).

CoPilot of course was not running blind. I would run diagnostics and sometimes had enough understanding to see what the current problem was. A key breakthrough was made by me when we saw that that a specific block of code from CP (which had already been tweaked and improved on a previous version) was not doing something that it was supposed to do. That insight almost completely solved the problem. Finally, after having added and removed the same lines time and time again, CP said that You need to ensure that after the rule body succeeds, the rule head variables are unified with the goal arguments. (Does that make any sense? Why wasn't this suggested before?) This was the final piece in solving the puzzle. Now my interpreter can calculate factorials.

In getting this far, I had to take out several of the instrinsic functions that were added last week, so now these have to be restored, and there's no guarantee that the code that worked a week ago will work now because several aspects have been changed and tightened up. It seems that 'maintenance work' (i.e. restoring functions that had been removed to make things clearer) takes more time than actual development work.

I have two more goals to solve (deliberate Prolog speak), although these are not concerned with the external functionality of the interpreter. I want to implement 'garbage collection': in the course of a single query, a certain amount of memory is allocated which is not needed after the query completes and so should be released (and the calculation of factorial (10) will require much more memory than factorial (1)). I know that this doesn't make much difference when one has megabytes of memory, but it's good housekeeping.

In a similar manner, there's a small improvement that should be made in handling rules. Going back to the original family tree example², there were various functors used, like 'parent', 'male', 'female', 'father', 'mother' and 'grandparent'. If one is trying to find a fact that matches 'male', for example, there should be no need to iterate over all the 17 facts/rules in the database, but only those where the functor is 'male'. I know that this is done by means of a symbol table, where each functor is assigned an index: finding a suitable fact/rule can be done by comparing two index numbers as opposed to invoking the 'expensive' resolution functionality. I suspect that this will be relatively simple, but what seems to be simple is often complicated.

Internal links
[1] 2023
[2] 2014

---

This day in blog history:

Blog #	Date	Title	Tags
645	08/11/2013	Sorting in Excel via Delphi automation	Programming, Delphi, Excel, Office automation
900	08/11/2015	Conceptual change	DBA
901	08/11/2015	900 blogs	Meta-blogging
1438	08/11/2021	DBA update	DBA
1551	08/11/2022	First rain of the year	Weather
1853	08/11/2024	New CPAP mask	CPAP