| Version 18 (modified by dr2chase, 3 weeks ago) |
|---|
Fibonacci Functions In Fortress
To illustrate some features of Fortress, we describe several different ways to implement a function that computes the nth Fibonacci number in Fortress. Recall first that the Fibonacci sequence is a sequence of natural numbers beginning 1, 1, 2, 3, 5, 8, and so on, such that every subsequent number in the sequence is the sum of the two previous numbers. 0 is often prepended to this sequence, and called the 0th Fibonacci number. Thus, if F[n] is the nth Fibonacci number, then we have:
F[0] = 0 F[1] = 1 F[n] = F[n-1] + F[n-2] for n > 1
Simple Recursive Definitions
We can easily define a recursive Fortress function that computes F[n] as follows:
This declares a function named fibonacci that takes a single argument of type ZZ and returns a value of type ZZ (ZZ is a type that represents the integers; it is defined in the built-in libraries of Fortress). When fibonacci is called, its parameter n is bound to the argument it is passed and then the body of the declaration is evaluated. In this case, the body is a straightforward encoding of the definition: a single if expression with three clauses, the "if n = 0" clause, the "elif n = 1" clause and the "else" clause. As in other languages, the clauses are evaluated one at a time in order, and only the consequent of the first clause whose predicate evaluates to true is evaluated. However, Fortress differs from most languages in that expressions may be evaluated in parallel. In particular, if the else clause is evaluated, fibonacci(n-1) and fibonacci(n-2) may be evaluated concurrently by separate threads. After both subexpressions have been evaluated, the results are added, and the sum is the value of the entire body.
Fortress is expression-oriented: The body of a function is a Fortress expression. The result of evaluating a call to fibonacci is just the result of evaluating the body with its parameters bound to the arguments passed, and the result of evaluating the body, which is an if expression, is the result of evaluating the consequent expression of the appropriate clause. There is no return statement as in statement-oriented languages.
Fortress also provides a case expression, which we can use instead of an if expression:
The case expression has a condition expression (i.e., n) and several clauses each consisting of a guarding expression (or the keyword else) and a consequent expression (separated by =>). A case expression is evaluated by first evaluating the condition expression and then comparing the result to the result of evaluating the guarding expression of each clause in order until a match is found. The result of evaluating the case expression is the result of evaluating the consequent expression of the matching clause. Although helpful to the reader, indentation in Fortress does not affect the computation expressed.
Because in each of the base cases, F[n] = n, we can collapse these cases into one:
The expression 0:1 denotes the range of integers from 0 to 1. When the type of the guarding expression is of a kind that contains values of the type of the condition expression, as the range is in this example, the case expression checks for membership rather than equality. We could have also used the set {0,1} instead of 0:1 as the guarding expression for the base case.
We can also simplify the first definition above as follows:
One problem with the functions defined above is that they take any integer as a parameter, but Fibonacci numbers are defined only for nonnegative integers. If a negative integer is passed to any of the first three functions, the evaluation will never complete. We can improve the safety of the function by checking whether the argument passed is negative and throwing an exception if it is. Like the Java programming language, Fortress provides both checked and unchecked exceptions; checked exceptions must be specified in the header of the function declaration. For simplicity, we assume there is an unchecked exception named Error, which we throw in case of any problem. In this case, we can define fibonacci as follows:
Even better, Fortress allows programmers to include a requires clause that specifies conditions that the arguments of a function must satisfy:
Calling this version of fibonacci with a negative number results in the unchecked exception CallerViolation being thrown.
A problem with all the definitions for fibonacci above, which all embody essentially the same computation, is that the amount of work they do to compute the nth Fibonacci number is exponential in n. Specifically, for n > 3, computing fibonacci(n) involves computing both fibonacci(n-1) and fibonacci(n-2), which in turn respectively involve computing fibonacci(n-2) and fibonacci(n-3), and fibonacci(n-3) and fibonacci(n-4), and so on until the base cases of 0 and 1 are reached. Indeed, if N(n) is the number of times fibonacci(0) or fibonacci(1) is called in the evaluation of fibonacci(n), then N(0) = 1, N(1) = 1, and N(n) = N(n-1)+N(n-2) for n > 1, so N(n) = F[n+1], and, as we show later, F[n] is exponential in n. We can eliminate redundant recursive calls to fibonacci by remembering the results of previous computations rather than recomputing them every time, a technique called memoization. We illustrate this technique at the end of this article. However, we first consider several other methods for computing Fibonacci numbers.
Linear Iterative Computations
Observe that in computing the nth Fibonacci number, we compute all the smaller Fibonacci numbers, and indeed, do so repeatedly, resulting in the redundant computations noted above. If, however, we generate the Fibonacci sequence from the beginning, producing each subsequent number by summing the previous two, we avoid this redundancy: each Fibonacci number is computed exactly once, and then used in the computation of the next two Fibonacci numbers. We can express such a computation in Fortress as follows:
In this definition, the else clause is a block expression, a sequence of local declarations and expressions that are evaluated one at a time in order. The value of the block expression is the value of the last expression in the block.
The first line of the block declares a local variable F, an array in which we will store the Fibonacci numbers as they are generated. F is an immutable variable set to be an array of ZZ of size n+1, indexed by 0 through n. The entries of the array are initially uninitialized, and it is an error to read them before they are initialized. Although F is an immutable variable, the array bound to F is mutable; that is, F is always bound to the same array, but the entries in the array may change.
We first initialize F[0] and F[1] with 0 and 1 respectively, reflecting the base cases of the Fibonacci recurrence. Then for each k from 2 to n (i.e., in the range 2:n), we initialize F[k] using a for expression (commonly called a for loop). Finally, the result of the function is the value F[n] in the last entry of the array.
In Fortress, a range "generates" the values it contains, and the for loop binds the variable k to each value generated for each iteration of the for loop. In general, the different iterations of a for loop in Fortress may be evaluated in parallel, but in this case, we specify that the values are generated sequentially in order using seq(2:n), so that earlier entries are initialized before they are accessed.
Fortress provides a succinct alternative to short "for loops" that mimics common use in mathematics, providing the body before the iteration variable and its domain (text following "(*)" until the end of the line is a comment):
This program is semantically equivalent to the previous one, and any for loop whose body is a single expression can be rewritten to use this alternative form. However, unless the body is simple, an explicit for loop may be clearer.
It is easy to see that the two previous functions compute the nth Fibonacci with O(n) operations, rather than the exponential number of operations of the recursive version. They also use O(n) space, because they compute and store the first n+1 Fibonacci numbers. However, to compute any Fibonacci number, we need only the values of the previous two ones, so we don't need to keep the earlier ones:
In this function, the first two lines of the block expression declare and initialize local variables prev and curr; curr maintains the value of the latest Fibonacci number computed, and prev maintains the value of the Fibonacci number immediately before that. The var modifier indicates that these variables are mutable; they may be assigned new values using the assignment operator (:=). (The var modifiers above are redundant because they are implicitly assumed whenever the initialization expression follows := rather than =, as it does above.)
Within the for loop, we compute the new values for prev and curr. To do so, we introduce temporary variables prev' and curr' to store the next values of prev and curr, respectively. (We could do with only a single temporary variable, but using two makes the code a bit easier to understand.) Note that the declarations of prev' and curr' do not include the var modifier (and their initialization expression follows = rather than :=), so these variables are immutable; they may not be reassigned in their scope (i.e., the body of the for expression). However, prev' and curr' are declared anew, with different initialization values, in each iteration.
We can improve this example in a few small ways. First, we can declare prev and curr together, and we can eliminate the temporary variables by using multiple assignment. Second, note that the iteration variable k is not used anywhere, so it need not be bound; Fortress provides the special token _ to be used in such situations. Third, the base case of n = 1 is handled correctly by the else clause, so we can simplify the if clause to handle only the case in which n = 0:
This version also allows some (very little) parallelism not allowed in the previous version: the elements of the tuple in the multiple assignment may, in principle, be evaluated in parallel. However, the variables on the left-hand side of the multiple assignment are not reassigned before their values are used on the right-hand side; that is, the values read by variable references on the right-hand side are the values of those variables before the assignment takes place. This is why we don't need the temporary variables in this version.
Fortress also provides a while expression, which we could have used instead of forcing the for loop to be sequential. For brevity, I also use x and y instead of prev and curr. We must reintroduce an iteration variable to keep track of the iterations. The while loop expects and maintains the invariant that x = F[i-1] and y = F[i]. The loop terminates when i = n, at which point y = F[n]:
We can express this computation even more concisely:
In this version, the body of the function is a do expression, which is an explicit block expression. The first line declares a local function iter, which takes three arguments, x, y and i, and captures the computation of the ith iteration of the previous version; the parameters of this function replace the local variables of the previous version. Fortress implementations may be tail-recursive, so that functions like iter will be executed using constant space. Note that the body of the local iter function refers to n, which is bound in the environment in which iter is defined.
None of the previous three versions use subtraction. An alternate version of fibonacci can decrement from n rather than incrementing up to it.
This version has the advantage that the local function need not capture n, and that on many systems, checking whether a value is zero is faster than checking whether it is equal to a nonzero value. It has the disadvantage that we can no longer characterize x and y in terms of the iteration variable alone; the characterization depends on n. In particular, x = F[n-j] and y = F[n-j+1]. This means that this function computes F[n+1]. We could stop earlier by checking j = 1 (or starting with iter(0,1,n-1)) and returning y in that case, but this formulation, adapted from SICP (Hal Abelson's, Jerry Sussman's and Julie Sussman's "Structure and Interpretation of Computer Programs", MIT Press, 1984; ISBN 0-262-01077-1), seems to be the most common one.
Memoization
We now consider solutions that use memoization to avoid redundant computation. The idea here is to remember values of Fibonacci numbers that were previously computed, so they can be looked up rather than recomputed. As in the first iterative solution above, we store these values in a local array of the appropriate size (text delimited by "(*" and "*)" is a comment):
We need to initialize all the entries of the array with some default value that means that the corresponding value has not yet been computed. Since the nth Fibonacci number is nonzero for all n =/= 0, we can use 0 as this value as long as we don't check the F[0] entry in the array.
One subtle point in this function is that we don't require any additional explicit synchronization when accessing the array. This has never been an issue before because all the previous functions were either sequential or else did not have shared mutable data structures. In Fortress, arguments of a function or operator may be evaluated in parallel, and thus multiple threads may try to compute the kth Fibonacci number and then store it in F[k]. Also, still other threads may attempt to read F[k] while it is being written. These are all conflicting accesses, and typically such access require explicit synchronization to ensure that correctness. However, in this case, every thread that writes F[k] after initialization writes the same value (the kth Fibonacci number). So the writes don't really conflict with each other. Writes do conflict with reads, but Fortress guarantees that a thread reading a location concurrently with another thread writing it will read either the value before the write, or the value being written, and not some arbitrary value. So a thread either reads 0, and then proceeds to compute the kth Fibonacci number, or else it reads the kth Fibonacci number.
