prev up next

5) Lists

Lists of values may be constructed in Aldwych. The : is the list constructor, so a:b is a list whose head is a and whose tail is b. The list constructor is right associative, so a:b:c is a list whose head is a and whose tail is b:c, that is, a list whose first element is a, second element b and c is the list consisting of the remaining elements. The $ symbol is used to mean the empty list. Note, the elements of lists may be any values (including lists) and need not be all of the same type, but lists may not contain objects.

Here is a program which will read a sequence of numbers from the command window, terminating when it reads 0, store the sequence in a list, and then print out those numbers: 

#main ==
   Screen<-aio\stdio(),
   writeNumsList(Screen,list),
   Screen.fwrite("Enter some numbers terminated by zero: "),
   readNums(Screen)->list;
   
#readNums(Screen)<
<(n<-Screen.readInt)
{
 n=0 ||>$;
  :  ||>n:readNums(Screen);
}

#writeNumsList(Screen,list)=
{
 list$  || 
     Screen.nl;
 list=head:tail || 
     Screen.writeInt(head).putc(' '),
     writeNumsList(Screen,tail)
}
Here, the concurrent execution means that if the numbers are entered on separate lines, printing of them may start before reading has finished. However, Aldwych guarantees that the prompt is printed before it attempts to read the numbers, because a message sent in a set of statements is always sent before messages sent in procedures which form part of these statements. In this case, the fwrite message will always come before any readInt or writeInt message to Screen.

As writeNumsList shows, a$ is the test on the lhs of a rule for whether a is an empty list, while a=b:c is a test for whether it is a non-empty list. In the latter case, b and c become local variables which may be used on the rhs of the rule. More complex patterns may be employed, for example a=b:c:d is a lhs test that a takes the form a:b:c, while a=b:$ is a lhs test that a is a list of exactly one value, which is then referenced by variable b. It is also possible to introduce a local variable on the rhs and test that, so a=b:c,c=d:e tests that a is a list of the form b:d:e but enables local variable c to be used to represent d:e. writeNumsList also shows how a void procedure (one which has no return value) is written - with a = following the list of parameters.

The readNums procedure shows that a variable which is local to a whole procedure rather than a rule in a procedure is possible. It is local to a procedure call, so each call of readNums will have its own n.

Now let us consider a program similar to the above, but which inserts the numbers read into an ordered list, resulting in an ordered list of the numbers being printed: 

#main ==
   aio\stdio()->Screen,
   writeNumsList(Screen,list),
   Screen.fwrite("Enter some numbers terminated by zero: "),
   readNumsAndOrder(Screen)->list;
   
#readNumsAndOrder(Screen)<
<(n<-Screen.readInt)
{
 n=0 ||>$;
  :  ||>insert(n,readNumsAndOrder(Screen));
}

#writeNumsList(Screen,list)=
{
 list$  || 
     Screen.nl;
 list=head:tail || 
     Screen.writeInt(head).putc(' '),
     writeNumsList(Screen,tail)
}

#insert(n,list)<
{
 list$ ||>n:$;
 list=head:tail, n<head ||>n:list;
 :
 list=head:tail ||>head:insert(n,tail)
}
This will give one error when compiled by Aldwych - the second rule for insert defines the local variable tail but makes no use of it. A variable which occurs in a pattern but is not used elsewhere can be replaced by an underscore to avoid the error message: 
list=head:_, n<head ||>n:list;
Although the variable head is not used on the rhs, since it occurs in a test on the lhs as well as in a pattern it counts as both defined and used. An alternative to the underscore is to include a statement of the form -var on the rhs, which counts as a use of but otherwise has no effect. This would give us: 
list=head:tail, n<head ||>n:list,-tail;
Aldwych also allows Prolog-like list notation as an alternative to the above, so [h|t] can be used as an alternative to h:t in both the rule condition and rule body, [] can be used to mean the empty list, [x,y|z] can be used to mean x:y:z and so on.

Compound rule conditions

Another way of writing insert is: 
#insert(n,list)<
{
 list$ ||>n:$;
 list=head:tail 
   [
    n<head  ||>n:list;
    n>=head ||>head:insert(n,tail)
   ]
}
A structure of the form 
a [ b || c; d || e]
is equivalent to two rules: 
a, b || c;
a, d || e;
More than two rules may be enclosed within the square brackets, and square bracket structures may be nested, so 
a [
   b || c;
   d [
      e || f;
      g || h
     ]
   j || k
  ]
is equivalent to: 
a, b    || c;
a, d, e || f;
a, d, g || h;
a, j    || k
It is possible to include otherwise operators within the square brackets, making insert: 
#insert(n,list)<
{
 list$ ||>n:$;
 list=head:tail 
   [
    n<head  ||>n:list;
     :      ||>head:insert(n,tail)
   ]
}
Note, in order to retain the correct operation of otherwise, the rules may be reordered, so: 
a [ 
   b || c; 
   :
   d || e
  ]
f [
   g || h;
   :
   j || k
  ]
m || n
becomes: 
a, b || c;
f, g || h;
m    || n;
:
a, d || e;
f, j || k

prev up next