Factorial

Factorial

Let's look at a slightly less trivial program. Here is a function that computes the factorial of a non-negative integer.

:- func factorial(int) = int.

factorial(N) =
    ( if N = 0 then
        1
    else
        N * factorial(N - 1)
    ).

Similar to a predicate declaration, the first line declares a function named factorial that takes an argument of type int and returns a result of type int. int is a built-in type, representing signed integers.

Next is a clause that defines the function. To the left of the equals sign is the clause head. When the function is called, the input argument will be bound to the variable N. Variables are easy to spot as they always begin with a capital letter or underscore. To the right of the equals sign is an expression which computes the result in terms of the input.

The if-then-else structure is a conditional expression which has this form:

( if COND-GOAL then EXPRESSION1 else EXPRESSION2 )

We have:

• COND-GOAL is N = 0

• EXPRESSION1 is 1

• EXPRESSION2 is N * factorial(N - 1)

A conditional expression is evaluated as follows. First COND-GOAL is executed. If it succeeds, the value of the conditional expression is the value obtained by evaluating EXPRESSION1, otherwise it is the value obtained by evaluating EXPRESSION2.

We have seen goals already without introducing the terminology: call goals, and conjunctions made by conjoining two goals with a comma.

Now we meet another type of goal: N = 0 is a unification goal. When a unification goal is executed, the terms on the left and right hand sides of the equals sign will be unified. We will ignore the details of the algorithm for now, but it is essentially a matching process. If the two terms match, the unification succeeds, otherwise it fails. In this case, the unification succeeds if N is zero.

To reiterate, = means unification and not assignment. It is also not the equality operator that evaluates to a boolean value.

Recursion

The definition of factorial refers to itself so isn't it tautological? Let's try to evaluate factorial(4) by substituting 4 for N in the definition. That is, every time the variable N appears, replace it with 4. (Variables in Mercury are immutable, if you were wondering.)

factorial(4) = ( if 4 = 0
               then 1
               else 4 * factorial(4 - 1)
               )

The unification 4 = 0 must fail, we can simplify the conditional expression:

factorial(4) = 4 * factorial(4 - 1)

Assuming that - means minus, we can evaluate it immediately:

factorial(4) = 4 * factorial(3)

We can replace factorial(3) using the definition as before:

factorial(4) = 4 * ( if 3 = 0
                   then 1
                   else 3 * factorial(3 - 1)
                   )

Simplify, and repeat:

factorial(4) = 4 * (3 * factorial(2))

factorial(4) = 4 * (3 * ( if 2 = 0
                        then 1
                        else 2 * factorial(2 - 1)
                        ))

factorial(4) = 4 * (3 * (2 * factorial(1)))

factorial(4) = 4 * (3 * (2 * ( if 1 = 0
                             then 1
                             else 1 * factorial(1 - 1)
                             )))

factorial(4) = 4 * (3 * (2 * (1 * factorial(0))))

factorial(4) = 4 * (3 * (2 * (1 * ( if 0 = 0
                                  then 1
                                  else 0 * factorial(0 - 1)
                                  ))))

The unification 0 = 0 must succeed, so we can write:

factorial(4) = 4 * (3 * (2 * (1 * (1))))

which is what we are looking for.

So, defining a function in terms of itself works out as long as the recursion stops at some point -- there must be a base case to prevent the recursion from carrying on forever. Mercury does not have any looping construct so repetition is done through recursion.

The full program

To use the function in a program, we require much the same boilerplate as before:

:- module factorial.
:- interface.

:- import_module io.

:- pred main(io::di, io::uo) is det.

:- implementation.

:- import_module int.

:- func factorial(int) = int.

factorial(N) =
    ( if N = 0 then
        1
    else
        N * factorial(N - 1)
    ).

main(!IO) :-
    F = factorial(5),
    write_int(F, !IO),
    nl(!IO).

You can save this to a file factorial.m and compile it with mmc factorial.m.

The interface section is the same as before.

The definition of factorial is in the implementation section. Definitions of predicates and functions always occur in the implementation section.

Unlike main, the declaration of factorial appears in the implementation section of the module. That means factorial would not be visible from outside this module, if this module were to be imported by another module. This will become important for organising larger programs.

We import the module int (from the standard library) in the implementation section. The int module provides the usual arithmetic functions on int values, such as - and *. The int module is not needed in the interface so is imported in the implementation section.

In main, we compute 5! by calling factorial(5) and assigning the result to a variable F. Actually, F = factorial(5) is another unification, between the variable F on the left, and a function call on the right. Unifications can fail, but there is nothing to stop F from unifying with the result of the function call so this unification always succeeds.

Every variable has a type, but the types don't need to be mentioned explicitly. Unification can only be performed on two terms of the same type. Since unification is performed between F and the result of factorial(5), both must have the same type. The result type of factorial was declared to be int, so F has type int as well.

To print out the value of F (that we know has type int) we call the predicate write_int from the io module.

Finally, we print out a newline by calling nl, again from the io module.

And that's it!

Questions

• What happens if the argument to factorial is less than zero?

• What is the factorial of 21?

• Does factorial(5) = F look weird to you?