prev up next

10) Local Procedures

Here is a version of quick sort which uses Prolog-like pattern matching rather than stream-reading:

#qsort(xs)<

   #part(p,xs)->(s,g)
   {
    xs=[x|xs1], x>p  || g<-[x|g1], part(p,xs1)->(s,g1);
    xs=[x|xs1], x<=p || s<-[x|s1], part(p,xs1)->(s1,g);
    xs=[]            || s<-[], g<-[];
   }

{
 xs=[x|xs1] ||>qsort(s)++[x|qsort(g)], 
               part(x,xs1)->(s,g);
 xs=[]      ||>[];
}
Note here that ++ is a prefix operator is Aldwych which appends lists. Similar operators to ++ are >> which merges two streams with a biased merge - the merger will take a value from the first stream unless no value is currently available on that stream in which case it will take one from the second if one is available there, and >= which is a non-biased merge, taking values from either stream as they become available.

This version of quick-sort shows the procedure part as a local procedure inside the procedure qsort. This means this procedure can only be used in the rules for qsort, or in other local procedures for qsort if there were any. If there were a top-level procedure called part this would not be useable within qsort since the local one would override it. Any level of embedding of procedures is allowed, so a local procedure may have its own local procedures.

In the above example, the local procedure has scope throughout the procedure it is within, shown by it being declared before the rules of that procedure. It is also possible to have procedures which are local to just one rule, done by declaring the local procedure(s) immediately after the bar of the rule, as in:

#qsort(xs)<
{
 xs=[x|xs1] ||
               
   #part(p,xs)->(s,g)
   {
    xs=[x|xs1], x>p  || g<-[x|g1], part(p,xs1)->(s,g1);
    xs=[x|xs1], x<=p || s<-[x|s1], part(p,xs1)->(s1,g);
    xs=[]            || s<-[], g<-[];
   }

               >qsort(s)++[x|qsort(g)], 
               part(x,xs1)->(s,g);

 xs=[]      ||>[];
}
Note, however, that local procedures may not refer to variables of their enclosing procedures. The local nature refers only to the scope of the reference of the procedure name. Otherwise, local procedures are self-contained.

Aldwych also allows anonymous local procedures. Here is a version of quick sort where the partition is given by an anonymous local procedure:

#qsort(xs)<
{
 xs?x ||
               
   $(p<-x,xs)->(s,g)
   {
    xs?x, x>p  | g^x;
    xs?x, x<=p | s^x;
    :         || s<-[], g<-[];
   },
   >qsort(s)++[x|qsort(g)]; 
 xs=[]      ||>[];
}
Anonymous local procedures start with $ immediately followed by the argument list. If an input argument name is the same as one of the variables in the clause body in which the procedure is called, the argument of that name within the procedure is initialised to the value of the variable. However, its change of the value within the anonymous call does not affect the value of the variable outside that call. The variable xs above demonstrates that. If an input argument to an anonymous call is a variable name not used in the surrounding clause body, it must be initialised to an expression composed using values from the clause body, as with the variable p above. If output variables in the anonymous procedure have the same name as variables in the enclosing clause, those variables will be assigned the final value of those output variables when the call to the anonymous procedure terminates.

So the above example is just as if there were a call part(x,xs)->(s,g) to a procedure with heading part(p,xs)->(s,g) whose set of clauses is the same as those within the inner { and }. Note here that the declaration of an anonymous procedure takes the place of a procedure call, thus it must be followed by a comma as procedure calls must to separate from following procedure calls or assignments.

If an output variable used in an anonymous procedure is not to have the same name inside that procedure as the name of the variable outside it that it gives a value to, then in the header to the anonymous procedure it is written iv->ov where iv is the variable in the anonymous procedure, and ov the outside variable written to. For example, quicksort could be written:

#qsort(xs)<
{
 xs?x ||
               
   >qsort(l)++[x|qsort(g)],
   $(p<-x,xs)->(s->l,g)
   {
    xs?x, x>p  | g^x;
    xs?x, x<=p | s^x;
    :         || s<-[], g<-[];
   };
 xs=[]      ||>[];
}

An anonymous procedure may also be declared and used in the place of a value. Below, this is done in a version of insertion sort where the insert procedure is anonymous:

#isort(xs)<
<(acc$)
{
 xs?x | acc<-$(x,acc)<
             {
              acc?y, 
                [
                 x[x,y|acc];
                  :   | ^y;
                ]
              :||>[x]
             };
 :    ||>acc;
}
Here the anonymous procedure is declared to give a value as the right hand side of an assignment to the local variable acc. It is as if there were an assignment acc<-insert(x,acc) with the set of clauses for acc being those within the inner { and }. Anonymous procedure calls used as a value must have an anonymous output, and the output of the call is the value of the procedure declaration and call.

Here is an alternative version which does not have the local variable acc:

#isort(xs)<
{
 xs?x |>$(x,acc<-<)<
        {
         acc?y,
           [
            x[x,y|acc];
             :   | ^y;
           ]
         :||>[x]
        };
 :    ||>[];
}
The argument acc<-< indicates that the variable acc in the anonymous procedure is initialised to the output of the implicit recursive call to isort.

Procedures written in a functional style may also be used anonymously. For example, the following maps the square function onto a the list [1,2,3,4] and prints the result:

#main() == aio\stdio().putt(map() ($[x]<==>x*x) [1,2,3,4]).nl;
The square function is given by the anonymous function ($[x]<==>x*x).

prev up next