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' 1 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 example2, 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: