prev up next

## 7) State

Up till this point, we have suggested that procedures have double bar rules and no state. However an Aldwych procedure may have state and single-bar rules which alter the state without ending the computation initiated when the procedure is called. Here is an alternative version of factorial, employing state:

```#fact(n)<
<(acc<-1)
{
n>0 | n-=1, acc*=n;
: ||>acc;
}
```
A call to `fact` sets up a computation with a state consisting of two variables, `n` and `acc`. Variable `n` is initialised by the argument to the call, and variable `acc` is initialised to 1. The first rule says that if `n` is greater than 0, its is reduced by 1 and `acc` is multiplied by `n`. The changes to the state in a rule should be considered as always taking place after the computations of the values which are assigned in the state changes. So the value of `n` by which `acc` is multiplied is the value before it is reduced by 1. If there was a rule
```a>b | a<-b, b<-a;
```
the effect would be to swap the values of `a` and `b` in the state if `a` is greater than `b`.

The second rule in `fact` above causes the computation to halt and return the value of `acc` when the value of `n` is not greater than 1. So a single bar rule causes computation to continue and should also change the state in order that it does not get into a non-terminating loop. A double-bar rule causes computation to halt and should return the value expected. It can be seen that the body of this procedure is equivalent to a while loop:

```acc=1;
while(n>0) {
acc*=n;
n-=1;
}
return acc;
```
It is possible to have single bar rules with a return statement in a procedure. In this case, the value is returned when computation commits to that rule, but computation will continue using further rule applications until it uses a double-bar rule. The symbol `<` is used on the rhs of a single-bar rule to mean the result returned from the continuing computation. Using this, an alternative form of the factorial procedure is:
```#fact(n)<
{
n=0 ||>1;
:    |>n*<, n-=1
}
```
This is equivalent to the usual recursive version of factorial.

## Streams

In the factorial case, the value returned cannot be computed until the recursive factorial of `n-1` is computed so the multiplication can take place. However, with lists, `x:y` can be returned and made use of elsewhere as soon as `x` is known even if `y` is still being computed. This allows stream concurrency to be exploited. Here is a version of `map` returning a value from a single-bar rule:
```#map(Func,list)<
{
list\$ ||>\$;
}
```
The value returned in the second rule is the input function applied to the head of the input list consed onto the result of the rest of the computation, which will be the map of the function onto the tail of the list.

Aldwych has some notation to enable list operations to be viewed as working with streams. Here is an alternative version of `map` using some of that notation:

```#map(Func,list)<
{
list\$ ||>\$;
}
```
The statement `^e` where `e` is any expression is equivalent to `>e:<`. It can be considered as sending `e` on the output stream. Multiple values can be sent in this way, so `^e1^e2` is equivalent to `>e1:e2:<`. The notation `list?head` on the lhs is a combination of `list=head:tail` and `list<-tail`, with the effect of the `list<-tail` taking place before the rhs is executed, that is `list` on the rhs refers to the tail of the input `list`. This can be considered as receiving a value on an input stream. Again, the notation can be used to deal with multiple values, so `list?x?y` can be considered a combination of `list=x:y:tail` and `list<-tail`.

An operation to look ahead at values in a stream without consuming them is available. In this, `list/?x` on the lhs is equivalent to `list=x:tail` but without `list` being set to `tail` on the rhs. There can only be one `/` symbol in a stream pattern, dividing the consumed part from the lookahead part, so `list?x/?y` is equivalent to `list=x:y:tail` with `list` set to `y:tail` on the rhs, while `list/?x?y` is equivalent to `list=x:y:tail` on the lhs with `list` still having the value `x:y:tail` on the rhs.

Using lookahead, the following gives an ordered merge of two ordered streams, eliminating duplicates:

```#omerge(stream1,stream2)<
{
stream1\$ ||>stream2;
stream2\$ ||>stream1;
stream1?x, stream2/?y, x<y | ^x;
stream1/?x, stream2?y, y<x | ^y;
stream1?x, stream2?y, x==y | ^x
}
```