Wiki Navigation

Using Generators in Fortress
Defining Generators in Fortress

Using Generators in Fortress

In Fortress, generators play the role that iterators play in many other programming languages. If you're used to writing iterators in languages like C++ and Java you may find that writing a Fortress Generator is a good deal easier and simpler---but that you'll have to turn your old mindset inside out. The key thing to remember is this:

In Fortress, the Generator is in charge of how a loop is run.

A generator extends the type Generator[\E\], where E is the type of the elements the generator produces. Here are a few examples of generators:

Expression	Type	Generates	Description
0#5	Range[\ZZ32\]	ZZ32	5 integers starting with 0, ie 0,1,2,3,4
seq(0#5)	SeqRange[\ZZ32\]	ZZ32	The same, but guaranteed to be sequential
a = array1[\String,5\](fn (i) => "Howdy, " i)	Array1[\String,0,5\]	String	The strings "Howdy, n" for n=0,1,2,3,4
a.indices()	Indexed[\ZZ32,ZZ32\]	ZZ32	The indices of a, ie 0,1,2,3,4 ; see also ArrayIndices
a.indexValuePairs()	Indexed[\(ZZ32,String),ZZ32\]	(ZZ32,String)	The pairs (n,"Howdy, n") for n=0,1,2,3,4. For arrays with dimensionality > 1, the first element of the pair is a tuple of indices
l = <\| "The", "quick", "brown", "fox" \|>	List[\String\]	String	The list elements
l.indices()	Indexed[\ZZ32,ZZ32\]	ZZ32	The indices of `l`, ie 0,1,2,3
(0#5).map(fn x => x x)	MappedGenerator[\ZZ32\]	ZZ32	The squares of 0#5, ie 0,1,4,9,16
a.map(fn x => x ", how are you?")	Array1[\String,0,5\]	String	A fresh array holding "Howdy, n, how are you?"

For Loops

Fortress provides three forms of convenient syntax for using generators. The first and most obvious is the for loop:

for i <- 2:4, s <- a do println(i ": " s) end

One run of this program printed:

3: Howdy, 2
2: Howdy, 0
2: Howdy, 1
2: Howdy, 2
2: Howdy, 3
2: Howdy, 4
4: Howdy, 2
4: Howdy, 3
3: Howdy, 4
3: Howdy, 1
3: Howdy, 3
3: Howdy, 0
4: Howdy, 1
4: Howdy, 0
4: Howdy, 4

Note that the lines appear to have been printed in no particular order! This is one of the most important aspects of Generators:

A Generator can run computations in any order it wants, and usually runs them in parallel.

There's an important proviso here, though: sequential generators. We can wrap any generator with seq(...) and obtain a sequential version of the same generator. Every generator has a so-called natural order; this is the order in which its elements appear when we sequentialize it using seq. Let's try running the above sequentially:

for i <- seq(2:4), s <- seq(a) do println(i ": " s) end

Now we obtain:

2: Howdy, 0
2: Howdy, 1
2: Howdy, 2
2: Howdy, 3
2: Howdy, 4
3: Howdy, 0
3: Howdy, 1
3: Howdy, 2
3: Howdy, 3
3: Howdy, 4
4: Howdy, 0
4: Howdy, 1
4: Howdy, 2
4: Howdy, 3
4: Howdy, 4

This is more like the behavior we were expecting. As you might expect, the natural order of an array produces its contents from lowest to highest index. This also leads us to another handy rule of thumb:

When doing I/O, use sequential loops.

Below we'll look at ways that we can circumvent this particular problem.

Reductions and comprehensions

The other two convenient syntaxes for generators in Fortress are reductions:

SUM [i <- 1:10] i^2

And comprehensions:

<| i^2 | i <- 1:10 |>

At the time of writing these don't work yet. But note that even though body computations occur in parallel, the results are combined together in their natural order. Consider the following code:

s = BIG DOT [i <- 2:4, s <- a] (i ": " s "\n")
print(s)

This will print:

2: Howdy, 0
2: Howdy, 1
2: Howdy, 2
2: Howdy, 3
2: Howdy, 4
3: Howdy, 0
3: Howdy, 1
3: Howdy, 2
3: Howdy, 3
3: Howdy, 4
4: Howdy, 0
4: Howdy, 1
4: Howdy, 2
4: Howdy, 3
4: Howdy, 4

But it does so by first computing (in parallel) the individual lines of the string, and appending them together; the resulting string is then printed. This can be particularly useful if it requires effort to compute the individual strings in the first place.

The Generate Function

The real magic of the type Generator[\E\] is found in the generate method:

generate[\R\](r: Reduction[\R\], body: E->R): R

We can call the generate function explicitly in our code, as follows:

s = a.generate[\String\](StringReduction, fn (s) => s "\n")
print(s)

This prints:

Howdy, 0
Howdy, 1
Howdy, 2
Howdy, 3
Howdy, 4

Let's take a look at the arguments to generate. The second argument is the "body" of the reduction. Each time the generator produces an element, it calls body passing that element as an argument. The body is free to do any kind of computation it likes using that element, but ultimately it'll produce a result of type R. The first argument to generate is a reduction, an object that packages up an associative operation with its identity. This operation is used to combine together all those results of type R into a final answer. From FortressLibrary.fss:

trait Reduction[\ R \]
    empty(): R
    join(a: R, b: R): R
end

There are a number of pre-defined reductions in the library:

VoidReduction	Reduction[\()\]	Discards its inputs.
SumReduction[\N\]()	Reduction[\N\]	Sums objects of type `N`
AndReduction	Reduction[\Boolean\]	Boolean AND
OrReduction	Reduction[\Boolean\]	Boolean OR
StringReduction	Reduction[\String\]	String concatenation

The join operation takes two Rs and combines them together in order to produce an R. It must obey three rules:

join(a,join(b,c)) = join(join(a,b),c)(Associativity)
join(empty(),r) = r (Left identity)
join(r,empty()) = r (Right identity)

The first rule is the most important from the perspective of parallelism. It says that if we combine elements together according to the natural order of the generator, it doesn't matter exactly how we group the combining operation. Consider for example what happens if we concatenate the contents of l:

"The" "quick" "brown" "fox" => "Thequickbrownfox"

It doesn't matter how we do the concatenation:

("The" "quick") ("brown" "fox") = (("The" "quick") "brown") "fox" = "The" ("quick" ("brown" "fox"))

That's the key property of the join function, and it allows the generate method to be pretty flexible about how it combines together results.

By bending these rules a little bit, we can see what's going on under the covers of generate. Let's write a reduction and a body that log some of their output:

object LoggingReduction extends Reduction[\String\]
  join(a:String, b:String): String = do
      println("Joining \"" a "\" and \"" b "\"")
      a b
    end
  empty(): String = ""
end

run(args:String...) = do
    loggingBody(i:ZZ32): String = do
        println("Iteration " i)
        "i" i
      end
    r = (1:16).generate[\String\](LoggingReduction, loggingBody)
    println(r)
  end

One run of this program printed:

Iteration 1
Iteration 2
Joining "i1" and "i2"
Iteration 13
Iteration 14
Joining "i13" and "i14"
Iteration 15
Iteration 16
Joining "i15" and "i16"
Joining "i13i14" and "i15i16"
Iteration 11
Iteration 12
Joining "i11" and "i12"
Iteration 10
Iteration 9
Joining "i9" and "i10"
Joining "i9i10" and "i11i12"
Joining "i9i10i11i12" and "i13i14i15i16"
Iteration 3
Iteration 4
Joining "i3" and "i4"
Iteration 5
Iteration 6
Joining "i5" and "i6"
Iteration 7
Iteration 8
Joining "i7" and "i8"
Joining "i5i6" and "i7i8"
Joining "i1i2" and "i3i4"
Joining "i1i2i3i4" and "i5i6i7i8"
Joining "i1i2i3i4i5i6i7i8" and "i9i10i11i12i13i14i15i16"
i1i2i3i4i5i6i7i8i9i10i11i12i13i14i15i16

Individual iterations---and individual combining operations---are run in parallel. The logging output appears higgeldy-piggeldy; the only thing we can really rely upon is that we can't join together two iterations until they've happened! But the result we obtain and print on the last line will be the same every single time the program is run.

Defining Generators in Fortress

Download in other formats:

Plain Text