Computing a factorial in XL

A simple recursive implementation of
factorial for integer numbers is:
function Factorial (N : integer) return integer written N! is
if N = 0 then
return 1
else
return N * (N1)!
This function makes use of a written form to implement
expression reduction for expressions of the
form N!. In other words, the expression (N1)! is
equivalent to Factorial(N1).
The function above takes an integer argument and returns an
integer. In practice, this type is an implementationdefined builtin
data type with a limited number of bits. So factorial of relatively
small numbers will be too large for the type. This is an example of
semantic noise, and we have to make a tradeoff. A better solution for
some applications makes use of the big_integer type for the
return value.
import BIG = XL.MATH.BIG_INTEGER
function Factorial (N : integer) return BIG.integer written N! is
if N = 0 then
return 1
else
return N * (N1)!
Note that the name of the integer type in the XL.MATH.BIG_INTEGER
module is also integer. In XL, integer is not a keyword
but a type name, and it can be redefined where it makes sense.
This implementation will work for very large factorials (depending on
the amount of memory available to the program. However, computing
large factorials may require substantial amount of machine resources
(memory, CPU time). It may sometimes be preferable to have an
approximation of the result, even if this means that some digits are
lost. This can be done by returning a real number instead of the
normal integer result. This is left as an exercise for the reader.
As these examples illustrate, the choice of the return type is best
left to the user of the factorial. We can do that by using a
generic type as the return value.
generic [type large_integer]
function Factorial (N : integer) return large_integer written N! is
if N = 0 then
return 1
else
return N * (N1)!
With that particular implementation, the user of the factorial can
select to use integer, BIG.integer or real as
the return type. The compiler will automatically create the
appropriate code. The above can be simplified further by making use
of a predefined true generic type called
number, which will ensure that only types considered numbers
will be used to instantiate Factorial.
function Factorial(N : integer) return number written N! is
if N = 0 then
return 1
else
return N * (N1)!
All the implementations above were recursive. It is often more
efficient to write iterative code, since recursion for that example consumes
more resources. An iterative version of the code above can be written
as:
function Factorial(N : integer) return number written N! is
result := 1
for I in 1..N loop
result *= I
This version makes use of the result predefined variable,
which can be used to hold the result of a function. It uses a
for loop to iterate over the range
1..N. The *= operator has the same meaning as in
C or C++, it multiplies its left operand in place by its right
operand.
This version doesn't correctly represent the original factorial
concept yet, because based on the code above, one can call
Factorial(1) and expect a result. This is not defined in the
problem space. Similarly, if one uses an sizelimited integer type which
doesn't perform range checking, the factorial of a sufficiently large
input would be zero or negative, due to limitations of the type.
A require specification can be used to limit input to positive
numbers. A ensure specification can be used to indicate that
only positive results are valid. Together, they form
a contract, as popularized by the Eiffel language.
function Factorial(N : integer) return number
written N!
require N >= 0
ensure result > 0
is
I : integer
result := 1
for I in 1..N loop
result *= I
The contract specifies the responsibilities. A negative input
indicates a bug in the caller of the function. A negative output
indicates a bug in the body of the function (which might be, in our
case, because it has been instantiated with an integer type which is
too limited). Appropriate use of contracts can significantly reduce
semantic noise.
