A more complicated example: a Fibonacci iterator

In this example, we will focus on using abstract functions from the Cogent standard library, called libgum. The program generates the n-th Fibonacci number using the generic iterator from libgum.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
include  <gum/common/iterator.cogent>

@ fibonacci returns the n-th Fibonacci number.
fibonacci : U32 -> U32
fibonacci n =
   let ((_, fibn, _), _) = iterate #{
       gen = fib_gen,
       cons = fib_consume,
       acc = (0, 1, 1),
       obsv = n
       }
   in fibn

@ fib_gen --- calculate the next Fibonacci number, unless we're finished.
@ Accumulator contains (n-1)th and nth Fibonacci numbers, and n in third place.
@ The accumulator returned by GeneratorResult has the same pattern; no value is returned for Stop / Yield etc.
fib_gen : #{acc : (U32, U32, U32), obsv : U32} -> GeneratorResult () () () (U32, U32, U32)
fib_gen #{acc = (n1, n2, n), obsv} =
  if | n == obsv -> ((n1, n2, n), Stop ())
     | else      -> ((n2, n1+n2, n+1), Yield ())

@ fib_consume is a verbose no-op.
fib_consume : #{obj : (), acc : (U32, U32, U32), obsv : U32} -> ConsumerResult () () (U32, U32, U32)
fib_consume #{obj, acc, obsv} = (acc, Next)

On line 1, the include command imports the iterator.cogent file. There are two forms of include command in Cogent, either include "something.cogent" or include <somelib.cogent>. They work in the same way as their #include counterparts in C.

The comment after the @ symbol on line 3 (and the other two functions) is for documentation generation, especially for documenting libraries and APIs. They can be generated by Docgent, which can be run by cogent --docgent <COGENT_SRC>, if your Cogent compiler is built with docgent flag enabled. See Optional features on how to enable the flags.

On line 6, a function iterate is invoked. This is a very general iterator that Cogent’s standard library provides. Let’s have a look at its type signature and some relevant type synonyms:

iterate : all (y, r, s, acc, obsv).
  #{ gen  : Generator y r s acc obsv!
   , cons : Consumer  y r s acc obsv!
   , acc  : acc
   , obsv : obsv!
   } -> IterationResult acc r s

type GeneratorResult y r s acc = (acc, <Return r | Yield y | Stop s>)
type Generator y r s acc obsv = #{acc : acc, obsv : obsv!} -> GeneratorResult y r s acc

type ConsumerResult r s acc = (acc, <Return r | Stop s | Next >)
type Consumer y r s acc obsv = #{obj : y, acc : acc, obsv : obsv!} -> ConsumerResult r s acc

-- Return if the body (enumerator) returned a value, or Stop if generator had no more
type IterationResult acc r s = (acc, <Return r | Stop s>)

The iterate function is polymorphic over type variables y, r, s, acc and obsv. Because in this example, they will be instantiated to (), (), (), (U32, U32, U32) and U32 respectively, all of which are simple, the type inference engine is capable of knowing what they are. In this case, type application to iterate is not necessary. You can nevertheless write them out as iterate [(), (), (), (U32, U32, U32), U32] if you think its more informative or clearer.

The function’s argument is an unboxed record of four fields. In Cogent, each function can only take exactly one argument. If more arguments are required, they can always be packed in a (usually unboxed) record or a tuple. In the argument record, gen and cons are the generator function and the consumer function respectively, which we will come back to shortly. acc is the accumulator, which is a read/write object that gets threaded through all the iterations. obsv is the observable object, which is a readonly (indicated by the ! operator on its type) object that the generator and/or the consumer can observe. As Cogent doesn’t have closures, the gen and cons functions cannot directly access variables in iterate’s scope; they have to be passed in explicitly as arguments. E.g. (in Haskell’s syntax), instead of

$> let v = 3
    in map (\a -> v + a) as

we have to write

g :: Int -> Int -> Int
g a b = a + b

$> let v = 3
    in map (g v) as

In each iteration, the generator is first called. The generator takes the accumulator (initial value) and the observable, and generates a result of either Return, Yield or Stop, updating the accumulator. If Return r or Stop s is returned, then the iteration will terminate immediately. The difference between them is that Return indicates that an early exit has happened, whereas Stop means the iterator has exhausted itself, terminating normally. If Yield y is returned, the result y will be further processed (or consumed) by the consumer. The consumer cons, takes the result y of the generator, the accumulator and the observable as usual, returns a pair of the updated accumulator, and either Return, Stop or Next. Return and Stop have the same meaning as mentioned above; Next means it will enter the next iteration. The overall iterate function will return the final accumulator, paired with the payload of either Return or Stop, of different types. As we can see, this iterator is very general, and there are more specific looping or recursion functions defined in other files in the libgum. The Cogent FFI of these types and functions can be found in cogent/lib/gum/common/iterator.cogent and the underlying C definitions in cogent/lib/gum/anti/iterator.ac.

In the code snippet above, all the work is done in the generator function; the consumer function just returns the accumulator unchanged, together with a Next tag to keep looping. As you can see, iteration is verbose.

The accumulator is a triple. Its first two terms are the n-1-th and n-th Fibonnaci numbers. Its third term is n. Each time fib_gen is invoked, it adds the first two terms together, increments n and creates a new accumulator:

Step Accumulator
1 (0,1,1)
2 (1,1,2)
3 (1,2,3)
4 (2,3,4)
5 (3,5,5)
6 (5,8,6)

When the third term reaches the observer (here just a U32), the generator returns Stop to end the loop; the pattern in the main function picks out the second term in the triple as the return value for the Fibonacci function.

In the antiquoted C file, the main function invokes the fibonacci function and prints the tenth such value:

$esc:(#include <stdio.h>)
#include "fib.c"
#include <gum/anti/iterator.ac>

int main(void)
{
   u32 n;
   n = $exp:fibonacci(10);
   printf("10th Fibonacci is %u\n", n);
   return 0;
}

The building process is very similar to the previous example (c.f. A First Program). The complete code and Makefile for this example can be found here.