• ## Tournament computation in two dimensions

Tournament computation can also take place in two dimensions. Here, tournamentOp₂ applies a quaternary function g to a 2-dimensional variable X, and keeps doing this to the results until there is a single result.

```fun tournamentOp₂.d₁.d₂.n.g X = Y @ [d <- 0]
where
dim t <- ilog.n ;;
end ;;
```

As for the single-dimensional case, it is useful to have a way of filling a two-dimensional grid with a neutral element if we do not have a grid whose extent in every dimension is the same power of 2.

```fun default₂.d₁.m₁.n₁.d₂.m₂.n₂.val X = Y
where
var Y [d₁ : m₁..n₁, d₂ : m₂..n₂] = X ;;
var Y [d₁ : nat, d₂ : nat] = val ;;
end ;;
```

• ## 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.

• ## The intension as first-class value

The origins of Cartesian Programming came from what was called Intensional Programming, in which the behavior of a program was context-dependent: a context is a set of (dimension,ordinate) pairs,
and the program can change behavior if some of the ordinates are changed. Formally, a variable in an intensional programming language is an intension, i.e., a mapping from contexts to values.

In TransLucid, after several failed attempts at defining the semantics of functions over these intensions, it finally dawned on us that the intension itself needs to be a first-class value. What this means is that
the context in which an intension is created is as important as the context in which it is evaluated. Consider:

```var tempAtLocation = ↑{location} temperature ;;
var tempInInuvik = tempAtLocation @ [location ← "Inuvik"] ;;
```

What this means is that whatever the value of the location-ordinate, variable tempInInuvik would always give the temperature in Inuvik, allowing any other dimensions to vary freely. Hence

```↓tempInInuvik @ [location ← "Paris", date ← #!date - 1] ;;
```

would give the temperature in Inuvik yesterday, not in Paris yesterday.

• ## Programming with infinite arrays: Factorial

Here we give an example of programming with infinite arrays. We take the well-known factorial function, and calculate using tournament computation. The TransLucid source code is found below.

We build an array f which varies with respect to dimensions t and d, effectively creating a computation tree. For example, to compute the factorial of 3, the variable f becomes

```    d
t 1 1 2 3 1 1 ...
1 6 1 1 1 1 ...
6 1 1 1 1 1 ...
```

and the answer is 6, picked up when t=2 and d=0.

Similarly, for the factorial of 6, f becomes

```      d
t   1   1   2   3   4   5   6   1   1 ...
1   6  20   6   1   1   1   1   1 ...
6 120   1   1   1   1   1   1   1 ...
720   1   1   1   1   1   1   1   1 ...
```

and the answer is 720, picked up when t=3 and d=0.

When t = 0, the value of f is a d-stream such that f is the current d-index if it is between 1 to n, and 1 otherwise. When t > 0, the value of f is a d-stream such that f is the product of pairs from the (t-1) d-stream.

```fun fact.n = f
where
dim d <- 0 ;;
var f = tournamentOp₁.d.n.times (default₁.d.1.n.1 (#!d)) ;;
end ;;
```

• ## TransLucid preamble

There are now a number of TransLucid examples available at the TransLucid Web site.
All of these examples use the declarations found in the preamble.

• ## Publication archive

To help gather the open problems related to implementing TransLucid,
a publication archive has been prepared. It is available at
http://plaice.web.cse.unsw.edu.au/archive
Included in that archive are the collected works of John Plaice,
Blanca Mancilla and Bill Wadge, along with all of the papers
presented at the International Symposia on Lucid and
Intensional Programming
and the Conferences on
Distributed Communities on the Web
.

• ## The first release of TransLucid is out!

It has taken a long time to come, but the first release of TransLucid,
version 0.1.0, is out. It is available at the following link.

• ## Formalization of the interpreter

The interpreter needs to be formalized once the operational semantics is finished. This is a necessary step towards writing TransLucid in TransLucid. The key missing parts for writing TL in TL are:

1. Besfitting
2. Parsing (a form of bestfitting)
3. Printing (a form of bestfitting)
4, Libraries

We are close on all of these. But nothing is finalized.

• 1. We need a good algorithm to determine the bestfit equation. The best I can think of would be n^2 because it has to determine for every equation whether it is more specific than every other.
2. Not sure about how to tackle this still. Some sort of recursive descent thing which mimics spirit could be feasible. I can see that in the future we could even beat spirit, possibly blowing it out of the water. We quite possibly need functions in TL to do this.
3. String operations are probably required, apart from that it seems trivial.
4. It seems that we just need some proper semantics. At the moment a library adds equations when it’s loaded. Libraries are currently written in c++, we could allow these to be translucid files too.

• If you store information separately for each variable, then testing applicability is linear in the number of entries for that variable. Among the applicable entries, finding bestfit ones is quadratic in the number of applicable entries.

This can be improved by using just-in-time ideas. After each modification of the set of equations for a variable, the first time that a demand is made for that variable would force the creation of a finite-state automaton that would be run upon any request for that variable (until, of course, the next modification to the set of equations).

• #### cartesianprogramming 10:14 on 2010/09/14 Permalink

The initial implementation can be done using the linear-quadratic solution. Just-in-time ideas can be kept for future optimization.

• #### jarro2783 00:18 on 2010/09/16 Permalink

what about including priority in that?

• ## System dimensions

Dimensions necessary for the proper behaviour of the system should not be allowed to be manipulated. That includes deletion. Should we write the TransLucid interpreter in TransLucid, we will reconsider this decision. This will allow rewriting, optimization and specialization of the interpreter as in Smalltalk.

• That makes sense, it’s fairly trivial to do too. Although we should define semantics better, currently it is just in the c++ interface that dimensions can be deleted. It would be better if it was all consistent with time and so on and could actually be done with in TransLucid too.

• Just to confirm the email exchange, system dimensions will be put in a separate symbol table in the parser so that way they have a container which has a list of all their names, accessible to the programmer.

• #### jarro2783 06:35 on 2010/09/21 Permalink

Yes that is what I will do.

• #### jarro2783 07:25 on 2010/09/23 Permalink

I have completed this now, the interface is the same. System dimensions are in system_dimension_symbols, so addDimensionSymbol and removeDimensionSymbol only affects user dimensions.

• ## Outputtting uuid in tlcore

```tlcore --uuid %% x=5;; %% x;; 4557f67592cb498fa684d50f5511a65 intmp<5>```

This is neat, here are a few comments.

1. The output from the equations section should be separated from the output from the expressions section with a %%.

2. The uuid “4557f67592cb498fa684d50f5511a65” should read “uuid<4557f67592cb498fa684d50f5511a65>“.

3. The output from the equations section is not taking into account the –verbose option.

4. In –verbose mode, we should output equations, demands and expressions as eqn<…>, dem<…> and expr<…>, respectively.

5. Should there be ;; at the end of each line of output?

6. Should there be a separator between the input and output? As in a line ?

• uuid or uuid … ?
The rest is easily fixed.

• Problems with angle brackets. Now fixed.

• #### jarro2783 11:24 on 2010/08/26 Permalink

and my reply got broken with the angle brackets too, that doesn’t say what I intended it to.

• The fix looks good. Points 5 and 6 should be tried out. For point 6, that is two dashes on a separate line, to separate the input lines from the output lines. In the reactive mode, there should be two lines with two dashes, before and after each output. If this is too verbose, we can remove it.

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r