## Tournament computation in one dimension

In the post on factorial, the following code appears:

var f = tournamentOp₁.d.n.times (default₁.d.1.n.1 (#!d)) ;;

What is going on? Let us look at the definitions from the TransLucid Standard Header:

fun default₁.d.m.n.val X = Y where var Y [d : m..n] = X ;; var Y [d : nat] = val ;; end ;; fun tournamentOp₁.d.n.g X = Y @ [d <- 0] where dim t <- ilog.n ;; var Y = fby.t X (g.(LofPair.d Y).(RofPair.d Y)) ;; end ;;

The *default₁* function creates a stream *Y* varying in dimension *d* such that in the interval *[m,n]*, the result will be the value of *X*. Everywhere else, the value of *Y* is the default *val*.

As for *tournamentOp₁*, when *#!t ≡ 0*, the value of *Y* is *X*. When *#!t > 0*, each element of *Y* is the result of applying the binary function *g* to a pair of elements from *Y* when *#!t* was one less. This process is completed until there is just one element left. Since the number *n* is not necessarily a power of 2, we use *default₁* to fill in the slots of *X* with the neutral element of *g*.

This form of computation is called *tournament computation*, and writing programs this way encourages parallel implementations.

## Reply