News Features Index > Ziggurat Column - Cracking eggs with sledgehammer

Popular Computer Weekly 17 March, 1983 Ziggurat Column - Cracking eggs with sledgehammers

Cracking eggs with

You have probably heard of the "Liar Paradox" (see Eugene P Northrop, Riddles in Mathematics, Penguin Books, for an admirable discussion - especially the chapter on "Paradoxes in Logic").
For those who have not, its essence is simple. There is a statement, which we can call E, and the content of E is E: the statement named E is false.
If E is true, then E is false. If E is false, then E must be true - and so the spiral goes on. What we have here is an example of a self-referential statement (ie, a statement which can refer to itself). By approaching from two different directions (it is true, or it is false) we reach two inconsistent results.
Self-reference is given another name in computing: it is called "Recursion". A definition of recursion might take the form - Recursion: see recursion.
The easiest example to give is the factorial function. The factorial of the number N is equal to all the numbers from 1 to N multiplied together. The factorial of 4 is thus 1 x 2 x 3 x 4 = 24. But, as is easily seen, the factorial of 4 is 4 times the factorial of 3 (which is 1 x 2 x 3 = 6).
A recursive definition of the factorial function is thus: Factorial (N)* Factorial (N-1) with the rider that Factorial (0) = 1.
Some programming languages allow recursive functions and procedures (BBC Basic is one). Sometimes they can add a touch of elegance to a program - sometimes they can be very wasteful. When a language translator comes across a recursive function (recursive comes from the Latin meaning to run again) then it stores the information about the state of affairs on a stack. It has to turn the definition on its side to disentangle its implications.
As Forth is a stack-using language I will use Forth to show what happens (Ace Forth and Atom Forth).
On the Jupiter Ace if I want to write a recursive definition for a factorial function, I follow the recursive scheme above, and within my definition of the factorial I use the name of the factorial : Fact ?Dup If Dup 1– Fact * Else 1 Then; and, though you might not be able to program in Ace Forth, you can that Fact is defined and uses itself later.
The word Fact checks to see if the number on the stack is non-zero and duplicates the number (?Dup). If it is non-zero the number on top of the stack is decremented by 1 (1–), and Fact is reactivated; Else the number one is left on the stack, and the nested Facts unwind. This will work on the Ace but not on the Atom because, on the Atom, a dictionary entry (ie, Fact) cannot find itself while it is being defined. (Also, trying this with ZXForth from Artic is a good way of crashing the system.)
To calculate the factorial by use of recursion on the Atom, you have to define a special word : Recursive Latest Pfa Cfa , ; Immediate which says to the system, take the very latest definition and put it here (which is what the Immediate means). To perform a recursive definition of Fact we insert the word Recursive for Fact in the main body of the definition.
I am always impressed by recursive definitions: they seem like sledge-hammers to crack eggs at times.