Home | About | Partners | Contact Us

SourceForge Logo

Quick Links
Building XL
XL Mailing List

Understanding XL
Conceptual overview
XL examples
Inside XL
Concept Programming

In depth
Browse GIT
SourceForge Info

Other projects
GNU Project
The Mozart Project

XLR: Extensible Language and Runtime

The art of turning ideas into code

Computing a factorial in XL

Prev: Hello World


Next: Maximum

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 * (N-1)!

This function makes use of a written form to implement expression reduction for expressions of the form N!. In other words, the expression (N-1)! is equivalent to Factorial(N-1).

The function above takes an integer argument and returns an integer. In practice, this type is an implementation-defined built-in 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 trade-off. 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 * (N-1)!

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 * (N-1)!

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 * (N-1)!

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 size-limited 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.

Prev: Hello World


Next: Maximum

Copyright 2008 Christophe de Dinechin (Blog)
E-mail: XL Mailing List (polluted by spam, unfortunately)