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, [ xHere the anonymous procedure is declared to give a value as the right hand side of an assignment to the local variable[x,y|acc]; : | ^y; ] :||>[x] }; : ||>acc; }
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, [ xThe argument[x,y|acc]; : | ^y; ] :||>[x] }; : ||>[]; }
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).