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.
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$ ||>$;
list=head:tail |>Func head:<,list<-tail
}
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$ ||>$;
list?head | ^Func head
}
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
}