<p>
<h1>Sums and Functions</h1>
<p>
Next on the agenda is how to construct predicates and functions that
calculate with numbers.  <em>Mercury</em> is unusual in that you actually have
to import the module that defines the basic integer operations,
whereas in most languages they are built in.  There are good reasons
for this, but this tutorial is probably not the place to discuss them.
So just trust us.
<p>
Here's how one might code the factorial function:
<p>
<center><table border=1 width=90%><tr><td><pre>

:- module factorial.

:- interface.

:- pred factorial(int, int).
:- mode factorial(in, out) is det.

:- implementation.

:- import_module int.

factorial(N, F) :-
        N =< 0 ->
                F = 1
        ;
                factorial(N - 1, F0),
                F = N * F0.
</pre></tr></table></center>
<p>
Let's examine some of these lines.
<p><center><table border=1 width=90%><tr><td><pre>

:- pred factorial(int, int).
</pre></tr></table></center><p>
This simply says that this module defines a predicate <tt>factorial/2</tt>,
both of whose arguments are integers (<tt>int</tt> is a built-in type in
<em>Mercury</em>).
<p>
The mode declaration
<p><center><table border=1 width=90%><tr><td><pre>

:- mode factorial(in, out) is det.
</pre></tr></table></center><p>
says that <tt>factorial/2</tt> can be called with its first argument as an
input and its second argument as an output, in which case the
predicate behaves deterministically (i.e. it will have exactly one
<em>solution</em> when called in this way).
<p>
The implementation section makes use of various integer operations
such as subtraction and comparison and so needs to import the <tt>int</tt>
module:
<p><center><table border=1 width=90%><tr><td><pre>

:- import_module int.
</pre></tr></table></center><p>
<p>
Finally, we get to the definition:
<p><center><table border=1 width=90%><tr><td><pre>

factorial(N, F) :-
        N =< 0 ->
                F = 1
        ;
                factorial(N - 1, F0),
                F = N * F0.
</pre></tr></table></center><p>
<p>
This might look a little strange at first, but it's really very
simple.  Any code that looks like
<p><center><table border=1 width=90%><tr><td><pre>

        Condition ->
                TrueCase
        ;
                FalseCase
</pre></tr></table></center><p>
is simply an if-then-else.  If the <tt>Condition</tt> code succeeds, then
the <tt>TrueCase</tt> code is executed, otherwise the <tt>FalseCase</tt> code is
executed.
<p>
The call to <tt>=</2</tt> in the condition will either succeed or fail.  If
you look at the interface for the <tt>int</tt> module you will see a line
<p><center><table border=1 width=90%><tr><td><pre>

:- mode in =< in is semidet.
</pre></tr></table></center><p>
Since <tt>N</tt> is an input and <tt>0</tt> is a constant (and therefore an
input argument), the call to <tt>=</2</tt> will be be semideterministic,
which simply means that it will either succeed or fail.
<p>
If the call succeeds, then the branch
<p><center><table border=1 width=90%><tr><td><pre>

                F = 1
</pre></tr></table></center><p>
is executed.  So the call <tt>factorial(0, X)</tt> will succeed with <tt>X = 1</tt>.
<p>
On the other hand, if the condition fails (<tt>N</tt> is greater than zero)
then the other branch is executed
<p><center><table border=1 width=90%><tr><td><pre>

                factorial(N - 1, F0),
                F = N * F0
</pre></tr></table></center><p>
This recursively calculates the factorial of <tt>N - 1</tt> and binds the
result to <tt>F0</tt>.  The result <tt>F</tt> is then bound to <tt>N * F0</tt>.
<p>
Notice that recursion is the only looping construct available in
<em>Mercury</em>.  The compiler will perform tail-call optimisation where
possible so functions that would be iterative in another language
don't incurr any penalty for being written in <em>Mercury</em>.
<p>
This predicate notation can be a little clumsy, though, so <em>Mercury</em>
provides the means for writing more natural looking functions.  Here's
the naive definition for calculating the <em>n</em>th Fibonacci number:
<p><center><table border=1 width=90%><tr><td><pre>

:- func fibonacci(int) = int.
:- mode fibonacci(in) = out is det.
<p>
fibonacci(N) = F :-
        N =< 2 ->
                F = 1
        ;
                F = fibonacci(N - 1) + fibonacci(N - 2).
</pre></tr></table></center><p>
Observe that <tt>fibonacci/2</tt> is declared using the slightly different
<tt>func</tt> syntax and that it may be called "<em>inline</em>" as part of an
expression rather than "<em>outline</em>" as with <tt>factorial/2</tt>.
<p>
Let's build a top-level module that makes use of these two, assuming
<tt>fibonacci/2</tt> is exported from a module called <tt>fibonacci</tt>:
<p>
<center><table border=1 width=90%><tr><td><pre>

:- module facnfib.

:- interface.

:- import_module io.

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

:- implementation.

:- import_module factorial, fibonacci.

main -->
        io__write_string("factorial(7) = "),
        { factorial(7, X) },
        io__write_int(X),
        io__nl,
        io__write_string("fibonacci(7) = "),
        io__write_int(fibonacci(7)),
        io__nl.
</pre></tr></table></center>
<p>
Look out for the use of <tt>{ ... }</tt> in <tt>main/2</tt> to suppress the
addition of the extra DCG argument pair in the call to
<tt>factorial/2</tt>.  The call to <tt>fibonacci(7)</tt> doesn't need to be
<em>escaped</em> in this fashion since the DCG expansion doesn't add the
extra arguments to nested calls.
<p>
After compiling and running we get
<p><center><table border=1 width=90%><tr><td><pre>

$ ./facnfib 
factorial(7) = 5040
fibonacci(7) = 13
</pre></tr></table></center><p>
Excellent!