This paper describes a conditional term rewriting system for Joy based on the two constructors concatenation and quotation.
A rewriting system consists of a set of
syntactic rules for performing replacements on certain suitable entities.
The best known such system is the one we learnt at school
for evaluating arithmetic expressions.
Any programming language can be given a rewriting system,
but for Joy it is particularly simple.
The basic binary rewriting relation will be written in infix notation
as =>, pronounced "can be rewritten as".
The following are some sample rules for the + operator,
the < predicate
and the dip combinator.
2 3 + => 5
2 3 < => true
a [P] dip => P a
In the last example,
P is any program and a is any literal
(such as a number) or a program
whose net effect is to push exactly one item onto the stack.
The rewriting relation is extended to allow rewriting in appropriate contexts,
further extended to accomodate several rewriting steps,
and finally extended to become a congruence relation,
an equivalence relation compatible with program concatenation.
This congruence relation between programs
is essentially the same as the identity relation in the algebra
of of functions which the programs denote.
Although Joy functions take a stack as argument and value,
in the rewrite rules the stack is never mentioned.
The following are rewriting rules for arithmetic expressions in four different notations: infix, functional, prefix and postfix:
2 + 3 => 5 +(2,3) => 5
+ 2 3 => 5 2 3 + => 5
In each case on the left the operands are 2 and 3,
and the operator or constructor is +,
so they all refer to the same arithmetic term.
Since Joy uses what looks like postfix notation,
it might be thought that one should attempt a term rewriting system
with rules just like the second one in the last line.
That would treat the short program 2 3 +
as being composed of two operands and one operator or constructor.
It would also treat the gap between 2 and 3
as quite different from the gap between 3 and +.
The difference would be explained away as a syntactic
coincidence due to the choice of notation.
Apart from + there would be very many term constructors.
However, Joy has operators for manipulating the top few elements of the stack, such as swap, dup and pop. These are also found in the language Forth, see for example \AX{Salman {\it et al}}{1984}{Salman-etal:84} and \AX{Kelly {\it et al}}{1986}{Kelly-etal:86}. These operators take a stack as argument and yield a stack as value, and their presence forces all other operators to be of the same type. For example, the following is a rewrite rule for swap:
a b swap => b a
Unlike Forth, Joy also has
quotations and combinators.
These features also force the conclusion that
the appropriate rewriting system is a string rewriting system.
Consider the following four programs:
[2] [3 +] b [2] [3 +] concat i
[2 3] [+] b [2 3] [+] concat i
They all eventually have to reduce to 5,
just like the earlier Joy program 2 3 +.
It suggests that in the latter the gaps have to be treated
in the same way,
the program is a concatenation of three atomic symbols,
and it denotes the composition of three functions.
So, at least for Joy programs without quotations
and combinators,
the appropriate system is a string rewriting system.
Such a system is equivalent to a term rewriting system
with a concatenation constructor for programs as the only constructor.
To handle combinators,
a quotation constructor has to be introduced
as a second constructor.
The remainder of this paper is organised as follows: The next section introduces rewriting systems in general. Then follows a section on the principal concepts of a rewriting system for Joy. The next two sections give details of rewriting rules for operators and for combinators. Two other sections re-examine the stack and the quotation constructor. It is argued that the stack is not just an optimisation useful in an inmplementation, but that it is almost essential for understanding the semantics of Joy. The possibility of an extensional version of the quotation constructor is discussed but dismissed as unnecessarily restrictive. A final section is an outline of a rewriting system for Joy types; the system resembles a categorial grammar.
Rewriting systems can be classified according to the entities that are being rewritten. In a string rewriting system those entities are linear sequences of symbols or strings of symbols. In a term rewriting system these entities are expressions or terms build from operands and operators. In a graph rewriting system they are graphs of various kinds.
A string rewriting system is based on an alphabet which is just a set of symbols. Strings over a given alphabet are arbitrary sequences of symbols, each taken from the alphabet. The empty sequence or null string is included. A rewriting rule is of the form
x => y
where both x and y are strings.
A string rewriting system consists
of an alphabet and a relation =>,
a set of such pairs or rules.
A wider relation ==> is defined as follows:
For strings w, x, y and z,
w x z ==> w y z
if and only if x => z. This relation allows
replacement of x by y in arbitrary contexts w..z.
A term rewriting system also requires an alphabet of symbols. Each symbol has an associated arity which is a natural number (0, 1, 2, ...). Symbols of arity 0 are nullary symbols or operands, symbols of positive arity are unary, binary, ternary and so on symbols or operators. A term over such an alphabet is either an operand or it is an operator of arity $n$ together with $n$ further terms. Terms are really abstract syntax trees, and various notations can be used for their concrete linear representation. A rewriting rule is again a pair of the form
x => y
where x and y now have to be terms.
A term rewriting system consists of an alphabet of symbols,
each with their own arity,
and a set of such rules.
A wider relation ==> is defined as follows:
y ==> z
if and only if y and z are alike terms except that
y contains a subterm u where z contains
a subterm w such that u => w.
In any rewriting system it is useful to define ==>> as
the reflexive transitive closure of ==> .
x ==>> z
if and only if x = z or for some y,
x ==> y and y ==>> z.
Here is an example for a fragment of a rewriting system for arithmetical expressions in Joy:
2 3 + => 5
7 2 3 + * ==> 7 5 *
7 2 3 + * ==>> 35
In the second line the subexpression 2 3 + on the left
is called a reducible expression or redex
since it can be reduced using the rule in the first line.
There are two distinct ways in which a string rewriting system
can be interpreted as a term rewriting system.
On the first interpretation,
the term system has exactly one operand.
It has as unary constructors all the symbols of the string system.
It has no other constructors.
The single operand is just the null string,
and any symbol, say s from the string alphabet
is interpreted as a unary operator append s.
The appending is either uniformly on the left or uniformly on the right.
On the second interpretation, the term system has as operands all the symbols from the string system. It has only one binary constructor, concatenation. This interpretation is most useful for a rewriting system for Joy because it is now possible to add the unary quotation constructor which is needed for the combinators.
Rewriting systems can be based just on unconditional rules of the
form x => y,
but they can also have conditional rules.
Such rules state that certain rewritings are permitted
provided certain other rewritings are permitted.
The next sections give a conditional rewriting system for Joy.
A short general introduction to rewriting systems is in \AX{Salomaa}{1985}{Salomaa:85}. String rewriting systems in particular are discussed in \AX{Book}{1985}{Book:85}. A general survey of rewriting systems is in \AX{Schmitt}{1987}{Schmitt:87}. %
This section describes the basis of a conditional rewriting system for Joy using a notation similar to Prolog.
A rewriting system for Joy will be a collection of syntactic rules for rewriting Joy programs. Such a system must be based on the two principal program constructors, program concatenation and program quotation. The system to be presented here uses (unconditional) axioms of the form
P => Q
where P and Q are programs.
There are also conditional rules of the following forms,
where R, S, T and U
are further programs.
P => Q :- R => S.
P => Q :- R => S, T => U.
The rules are written in a Prolog-like syntax.
The turnstyle :- is pronounced "if".
On its left is the conclusion or consequent.
On the right is a premise or antecedent.
The antecedent can be a conjunction, as in the second form
above, and the comma , is pronounced "and".
So the second of the above rules can be read as:
"P can be replaced by Q if
R can be replaced by S and
T can be replaced by U".
Details of these rules are given in the next two sections.
Using the same notation, the relation ==> is defined by the three rules
P ==> Q :- P => Q.
P Q ==> P R :- Q ==> R.
P R ==> Q R :- P ==> Q.
The last two clauses allow rewriting in a context --- P on the left
or R on the right.
The next rules for ==> concern combinators.
In the following, C$i$ is any combinator expecting
at least $i$ quotation parameters.
[P] C1 ==> [Q] C1 :- P ==> Q.
[P] [R] C2 ==> [Q] [R] C2 :- P ==> Q.
[P] [S] [R] C3 ==> [Q] [S] [R] C3 :- P ==> Q.
[P] [T] [S] [R] C4 ==> [Q] [T] [S] [R] C4 :- P ==> Q.
Note that there is no rewrite rule
[P] ==> [Q] :- P ==> Q.
The reason for this is further explained in section 7.
The final relation to be introduced is ==>>,
the reflexive transitive closure of ==>.
It is defined by
P ==>> P.
P ==>> R :- P ==> Q, Q ==>> R.
The simplest examples of rewriting axioms are those generated
by definitions.
If an atom name has been defined using == as program P,
in the form
name == P
then name may be rewritten as P:
name => P
The stack is normally a sequence of values of various types.
This sequence is just a special list
which is modified by programs.
The first general operator is newstack,
which clears the stack.
Clearing twice is the same as clearing just once.
If literals were pushed before the clearing,
this has the same effect as just clearing.
So newstack is in fact the right zero element for
program concatenation.
newstack newstack => newstack.
P newstack => newstack.
Since the stack is a list,
it should be possible to put this list on top of the stack ---
that is to say, on top of itself.
Also, it should be possible to make the list on top of the stack
become the stack.
There are two operators that do just that:
The stack operator pushes onto the stack
a list containing all the elements of the stack.
The unstack operator expects a list on top
of the stack
and makes that the stack.
The unstack operator undoes what the stack operator
does,
but the reverse is true only in special cases.
newstack stack => newstack [].
[] unstack => newstack.
newstack L => [L] reverse unstack.
In the last rule, L has to be a list of literals.
Also, it should be noted that the stack is not always
a sequence of values, it can also contain operators
and combinators.
So, strictly speaking the stack is always a quotation,
and the stack operator pushes a quotation
onto the stack,
and the unstack operator expects a quotation
on the stack and makes that the new stack.
Although the stack was mentioned in these informal explanations, it should be noted that it is not referred to at all in the rewrite rules. The same will be true in the sections to follow. Rewrite rules are purely syntactic, and the stack is a semantic entity. Joy symbols denote functions from stacks to stacks. But syntax does not concern semantic concepts such as denotation. rem
The unary operators pop and dup
are defined on all stacks containing at least one element.
In the rewrite rules to follow, let a be any literal
or a program whose net effect is to push exactly one value onto the stack.
a pop => id.
a dup => a a.
The generalisation that a may be not just a literal but can be
a program whose effect is to push a single value
is needed for rare cases like the following:
[*] first dup => [*] first [*] first.
The two programs on the left and right of the arrow
have the net effect of pushing two occurrences
of the multiplication operator * onto the stack.
The binary operators swap, popd, and dupd
are defined on all stacks containing at least two elements.
Let a and b be any literals or equivalent programs.
a b swap => b a.
a b popd => b.
a b dupd => a a b.
The ternary operators swapd, rollup, rolldown
and rotate
are defined on all stacks containing at least three elements.
Let a, b and c be any literals
or equivalent programs.
a b c swapd => b a c.
a b c rollup => c a b.
a b c rolldown => b c a.
a b c rotate => c b a.
The ternary operator choice also expects three elements,
but the third element has to be a truth value.
Let a and b be any literals or equivalent.
true a b choice => a.
false a b choice => b.
The simple types of Joy are the truth value type, the character type and the integer type. The next rules are for the operators on these types.
Rewrite rules for the unary operators
succ, pred, abs and sign
for integer operands is given by the following rules.
Since characters are just small positive integers,
the operators can also be applied to characters.
The last two operators can also be applied to truth values.
In what follows, let i, j and k
be any integers.
i succ => j. ( j = i+1 )
i pred => j. ( j = i-1 )
i abs => j. ( j = abs(i) )
i sign => j. ( j = sign(i) )
Rewrite rules for the binary operators +, -, *, /, rem, max and min for integers operands are as follows.
i j + => k. ( k = i+j )
i j - => k. ( k = i-j )
i j * => k. ( k = i*j )
i j / => k. ( k = i/j )
i j rem => k. ( k = i mod j )
i j max => k. ( k = max(i,j) )
i j min => k. ( k = min(i,j) )
Again these binary operators can be applied to characters
as well as integers.
In the mixed case the type of the result k
is the same as the type of the second parameter i.
Most implementations of Joy will also provide many other arithmetical operations. Since these will be defined in a library, no reduction rules should be given here.
The type of truth values is one of the Boolean types.
The binary operators are and, or and xor
(exclusive or).
The unary operator is not.
Let p and q be truth values
true or false.
p q and => r. ( r = p and q )
p q or. => r ( r = p or q )
p q xor. => r ( r = p xor q )
p not => r. ( r = not p )
A predicate is a function which leaves a truth value on the stack. The unary predicates null, small, odd, even, positive and negative are defined for all numeric types:
i null => p. ( p = (i=0) )
i small => p. ( p = (i<2) )
i odd => p. ( p = odd(i) )
i even => p. ( p = even(i) )
i positive => p. ( p = positive(i) )
i negative => p. ( p = negative(i) )
The binary predicates =, !=, <, <=, > and >= have the obvious rewrite rules:
i j = => p. ( p = (i = j) )
i j != => p. ( p = not(i = j) )
i j < => p. ( p = (i < j) )
i j <= => p. ( p = (i <= j) )
i j > => p. ( p = (i > j) )
i j >= => p. ( p = (i >= j) )
The remainder of this section deals with aggregate types: sets, strings and quotations, with lists as a special case. The unary operators first, second, third and rest expect a non-empty aggregate on top of the stack. The following are the rules for list aggregates:
[a L] first => a.
[a b L] second => b.
[a b c L] third => c.
[a L] rest => [L].
Here [a L] is a non-empty list or quotation
whose first member is a and whose rest is [L].
For strings an analogous notation can be used
to obtain analogous rules. For example
"cS" first => 'c.
"cS" rest => "S".
Here "cS" denotes a non-empty string whose first character
is 'c and whose remaining characters are the string "S".
For sets the rules are entirely analogous, except that the numeric ordering of the members is used. One possible notation is the following:
{a S} first => a.
{a S} rest => {S}.
Here {a S} denotes a non-empty set whose smallest
member is a and whose other members are those of {S}.
The binary operators cons and swons expect an aggregate and a potential member on top of the stack. These are the rules for list aggregates:
a [L] cons => [a L].
[L] a swons => [a L].
The rules for strings and sets are analogous.
The unary operators uncons and unswons also expect a non-empty aggregate. The rules for list aggregates are:
[a L] uncons => a [L].
[a L] unswons => [L] a.
So for strings and sets some of the rules are
'c "S" cons => "cS".
{S} a swons => {a S}.
{a S} uncons => a {S}.
The two binary operators at and of are for indexing into aggregates. For list the rules might be written:
[l1 l2 ... li ... ln] i at => li.
i [l1 l2 ... li ... ln] of => li.
So the two operators are converses of each other.
For both operators in the case of sequences
the sequence ordering is used,
and for sets the underlying ordering is used.
But the notation with the dots ... is not
satisfactory.
Here is a better version for at applied to lists:
[a L] 1 at => a.
[a L] n at => b :- [L] (n-1) at => b.
And here is a version for of applied to sets:
1 {a S} of => a.
n {a S} of => b :- (n-1) {S} of => b.
The unary operator size takes an aggregate and determines the number of elements:
[] size => 0.
[a L] size => (n+1) :- L size => n.
The unary operator reverse can be applied to any aggregate but it is useful only for sequences:
[] reverse => [].
[a L] reverse => [M a] :- L reverse => M.
These rules for reverse are correct but inefficient
since appending to the right to produce [M a]
requires copying --- at least for the obvious implementation of lists.
Most implementations would use an accumulating parameter
to optimise the reverse operator.
It is of some interest that this optimisation can
be expressed in rewrite rules:
reverse => [] swap shunt.
[L] [] shunt => [L].
[L] [a M] shunt => [a L] [M] shunt.
The binary operator concat can be applied to two sequences which are either both lists or both strings.
[] [L] concat => [L].
[a L] [M] concat => [a N] :- [L] [M] concat => [N].
The operators and, or, xor and not can be applied not only to truth values but also to values of the set type. The reduction rules look exactly as for the truth values, except that the operations have to be performed bitwise. So they compute the intersection, union, symmetric difference and complement with respect to the largest set.
The two unary predicates null and small can also be applied to aggregates. These are the rules for lists, those for strings and sets are analogous.
[] null => true.
[a L] null => false.
[] small => true.
[a] small => true.
[a b L] small => false.
The two binary predicates in and has test aggregates for members.
a [] in => false.
a [a L] in => true.
a [b L] in => a [L] in
The has predicate is just the converse:
[] a has => false.
[a L] a has => true.
[b L] a has => [L] a has.
Most implementations of Joy will provide an operator for sorting a sequence and a binary operator merge for combining two already sorted sequences. Since these will be implemented in a library, no reduction rules are given here. The same applies to many other operators for aggregates. %
Sometimes it is necessary to test a parameter for its type. The unary predicates logical, char, integer, set, string and list are true if the parameter is a truth value, character, integer, set, string or list, respectively. The predicate leaf is true if the parameter is not a list.
false logical => true.
123 logical => false.
123 integer => true.
['A 'B 'C] leaf => false.
There is another operator for multi-choices.
It expects a non-empty list of non-empty lists on top of the stack
and below that one further item.
The opcase operator
matches the type of the item
with the first members of the lists.
When a match is found,
the rest of that list is pushed onto the stack.
If no match is found,
then the last list is used as the default.
123 [ [0 P] ['a Q] ["" R] ... ] opcase => 123 [P].
'c [ [0 P] ['a Q] ["" R] ... ] opcase => 'c [Q].
"Hello" [ [0 P] ['a Q] ["" R] ... ] opcase => "Hello" [R].
The simplest unary combinators are i and x,
they require the top of the stack to be one quotation.
Let P be any program.
[P] i => P.
[P] x => [P] P.
The next unary combinators, dip, dip2 and dip3,
allow manipulation
of the stack below the top few elements.
Let P be any program,
let a, b and c be any literals
or equivalent.
a [P] dip => P a.
a b [P] dip2 => P a b.
a b c [P] dip3 => P a b c.
Another unary combinator is nullary.
Its rewrite rule has to be expressed conditionally.
Let L, M and P be any programs.
L [P] nullary => L a :- L P => M a.
Three similar unary combinators are
unary, binary and ternary:
L b [P] unary => L a :- L b P => M a.
L b c [P] binary => L a :- L b c P => M a.
L b c d [P] ternary => L a :- L b c d P => M a.
Three further unary combinators are
app1, app2 and app3.
Let a, a', b, b', c and c'
be any literals or equivalent.
Note that the primed versions are used as the result
of applying P to the unprimed versions.
L a [P] app1 => L a' :-
L a P => M a'.
L a b [P] app2 => L a' b' :-
L a P => M a', L b P => N b'
L a b c [P] app3 => L a' b' c' :-
L a P => M a', L b P => N b', L c P => O c'.
There is even an app4 combinator which applies [P]
to four parameters a, b, c and d.
The binary combinators expect two quotations
on top of the stack.
The b combinator expects two quotations [P] and [Q],
with [Q] on top.
[P] [Q] b => P Q.
The cleave combinator
also expects two quotations,
and below that an item a.
L a [P] [Q] cleave => L b c :- L a P => M b, L a Q => N c.
The ternary combinators expect three quotations on top of the stack. One of the most important is ifte which performs branching. Its third parameter is the if-part, its second parameter is the then-part, its first parameter, on top, is the else-part.
L [I] [T] [E] ifte => T :-
L I => M true.
L [I] [T] [E] ifte => E :-
L I => M false.
The binary whiledo combinator is similar to the ifte combinator
in that it has a test, the while-part, which is second on the stack.
The combinator repeatedly executes the while-part
and while that yields true it executes the other part,
the do-part.
L [W] [D] whiledo => L :-
L W => M false.
L [W] [D] whiledo => L D [W] [D] whiledo :-
L W => M true.
The ternary tailrec combinator
for tail recursion also has a test, the third parameter.
If that yields true,
the second parameter is executed and the combinator exits,
otherwise the top parameter is executed
and after that the process is repeated.
L [I] [T] [R] tailrec => L T :-
L I => M true.
L [I] [T] [R] tailrec => L R [I] [T] [R] tailrec :-
L I => M false.
The quaternary combinators expect four quotations
on top of the stack.
The linrec combinator for linear recursion
expects an if-part [I], a then-part [T],
and two recursion parts [R1] and [R2].
L [I] [T] [R1] [R2] linrec => L T :-
L I => M true.
L [I] [T] [R1] [R2] linrec => L R1 [I] [T] [R1] [R2] linrec R2 :-
L I => M false.
The binrec combinator for binary recursion is similar, except that the first recursion part has to produce two values. The recursion with all four parts is applied to the two values separately. The second recursion part then has available the two results from these two applications.
L [I] [T] [R1] [R2] binrec => L T :-
L I => M true.
L [I] [T] [R1] [R2] binrec => L a b R2 :-
L T => M false,
L R1 [I] [T] [R1] [R2] binrec => N a b.
The genrec combinator for general recursion is also has an if-part, a then-part and two recursion parts. It differs from the other two combinators in that after the execution of the first recursion part nothing in particular is executed, but a program consisting of the four parts and the combinator is pushed onto the stack. The second recursion part thus has it available as a parameter.
L [I] [T] [R1] [R2] genrec => L T :-
L I => M true.
L [I] [T] [R1] [R2] genrec =>
L R1 [[I] [T] [R1] [R2] genrec] R2 :-
L I => M false.
There are several combinators which do not have a fixed number
of quotation parameters.
Instead they use a list of quotations.
The cond combinator is like the one in Lisp,
it is a generalisation of the ifte combinator.
It expects a non-empty list of programs,
each consisting of a quoted if-part followed by a then-part.
The various if-parts are executed until one is found
that returns true, and then its corresponding then-part
is executed.
The last program in the list is the default
which is executed if none of the if-parts yield true.
L [ [[I1] T1] REST ] cond => L T1 :-
L I1 => M true.
L [ [[I1] T1] REST ] cond => L [ REST ] cond :-
L I1 => M false.
The condlinrec combinator is similar,
it expects a list of pairs or triples of quoted programs.
Pairs consist of an if-part and a then1-part,
and triples consist of an if-part, a rec1-part and a rec2-part.
Again the first if-part that yields true
selects its corresponding then-part or rec1-part for execution.
If there is a rec2-part,
the combinator first recurses and then executes the rec2-part.
The last program is the default,
it does not have an if-part.
The cleave combinator also has a generalisation,
The construct combinator
expects two parameters,
a quotation and above that a list of quotations.
Each quotation in the list
will produce a value that will eventually be pushed
onto the stack,
and the first quotation determines the stack
onto which these values will be pushed.
L [P] [..[Qi]..] construct => L P ..qi.. :- L Qi => M qi.
Some combinators expect values of specific types below their quotation parameters. The next few combinators expect values of simple types.
The binary combinator branch
expects a truth value below its two quotation parameters:
The branch combinator resembles the
choice operator and the ifte combinator.
The truth value below the two quotations
determines which of the two quotations will be executed.
If the truth value is true,
then the if-part, the second parameter, is executed,
otherwise the then-part, the top parameter, is executed.
true [P] [Q] branch => P.
false [P] [Q] branch => Q.
The unary combinator times expects a numeric value
below its quotation parameter:
The times combinator executes its quotation parameter
as many times as indicated by the numeric value;
if the value is zero or less,
then the quotation is not executed at all.
0 [P] times => id.
n [P] times => P (n-1) [P] times.
%
The stack is normally a list,
so any list could serve as the stack,
including a list which happens to be on top of the stack.
But the stack can also contain operators and combinators,
although this does not happen often.
So the stack is always a quotation,
and any other quotation could serve as the stack,
including one on top of the stack.
The infra combinator
expects a quotation [P] which will be executed
and below that another quotation which normally will be just a list [M].
The infra combinator
temporarily discards the remainder of the stack
and takes the quotation or list [M] to be the stack.
It then executes the top quotation [P] which yields a result stack.
This resulting stack is then pushed as a list [N] onto the original
stack replacing the original quotation or list.
Hence any quotation can serve as a complex unary operation
on other quotations or lists.
L [M] [P] infra => L [N] :- [M] unstack P => N.
For linear recursion over numeric types
the if-part often is [null]
and the first recursion part is [dup pred].
The primrec combinator has this built in.
For integers the rewrite rules are:
0 [T] [R2] primrec => pop T.
i [T] [R2] primrec => i dup pred [T] [R2] primrec R2.
The primrec combinator can also be used for
aggregates.
The implicit if-part is again [null],
and the implicit first recursion part is [rest].
Below is the version for lists, the versions for sets and strings
are analogous.
[] [T] [R2] primrec => pop T.
[a L] [T] [R2] primrec => a [L] [T] [R2] primrec R2.
The unary combinators step, map, filter and split all expect an aggregate below their quotation parameter.
For step operating on lists the rewrite rule is:
[] [P] step => id.
K [a L] [P] step => M [L] [P] step :-
K a P => M.
For strings and sets the rules are analogous.
The same is true of the rules to follow.
For map operating on lists the rewrite rule is:
[] [P] map => [].
K [a L] [P] map => K [b M] :-
K a P => K b, K [L] [P] map => K M.
The filter combinator expects a predicate
as its quotation parameter.
[] [P] filter => [].
K [a L] [P] filter => K [a M] :-
K a P => J true, K [L] [P] filter => K [M].
K [a L] [P] filter => K [M] :-
K a P => J false, K [L] [P] filter => K [M].
The split combinator is like filter
except that it produces two lists.
The first list is just like the one from filter,
the second list is the list of those elements which did
not pass the predicate test [P]
and hence are not members of the first list.
[] [P] split => [].
K [a L] [P] split => K [a M] [N] :-
K a P => J true, K [L] [P] split => K [M] [N].
K [a L] [P] split => K [M] [a N] :-
K a P => J false, K [L] [P] split => K [M] [N].
The unary combinator fold expects a quotation which computes a binary operation. Below that has to be a literal and below that an aggregate. The literal is used as a start value to fold or reduce the aggregate. Applied to lists the combinator has these rules:
[] a [P] fold => a.
[b L] a [P] fold => d :-
a b P => c,
[L] a [P] fold c P => d.
The two unary combinators some and all
expect an aggregate below their
quotation parameter.
The quotation must be a predicate,
yielding a truth value.
The some combinator returns true if some members
of the aggregate pass the test of the quotation,
otherwise it returns false.
The all combinator returns true if all members
of the aggregate pass the test of the quotation,
otherwise it returns false.
For empty aggregates some returns false
and all returns true.
The rules for some are:
[] [P] some => false.
L [a A] [P] some => L true :-
L a P => M true.
L [a A] [P] some => L [A] [P] some :-
L a P => M false.
The rules for all are:
[] [P] all => true.
L [a A] [P] all => L false :-
L a P => M false.
L [a A] [P] all => L [A] [P] all :-
L a P => M true.
The unary combinator zipwith expects two aggregates and above that a program suitable for combining their respective elements. For lists the rules are
[] [A] [P] zipwith => [].
[A] [] [P] zipwith => [].
L [a A] [b B] [P] zipwith => L [c C] :-
L a b P => M c,
L [A] [B] [P] zipwith => L [C].
%
This section deals with the role of the Joy stack from a syntactic and semantic point of view.
First, let us consider a quite small arithmetic expression in postfix notation:
2 3 + 8 5 - *
A reduction might begin by doing the addition first,
or the subtraction first,
followed in a second step by the other operation.
In fact, the addition and the subtraction could be done in parallel
in the same step.
Only when both reductions have been done will it be possible to do the
final multiplication.
The final result is the value 20,
and it is independent of the order in which
the reductions have been applied.
In detail,
the first mentioned reduction sequence will look like this:
2 3 + 8 5 - *
5 8 5 - *
5 3 *
15
One possible strategy for reductions is the following:
Scan the expression from left to right until a redex is found, an expression that can be replaced in accordance with a rewrite rule. Apply the rule. Repeat until no more rules can be applied.
This strategy is most efficient for reducing expressions in which redexes are found early. The following is an example. Again all operators are binary, but note that except at the beginning operators and literals alternate. In each step the first three symbols constitute a redex.
10 5 / 3 * 4 - 1 +
The strategy is least efficient when a redex is found late.
In the example below, note that all operators occur towards the end.
3 2 6 8 6 - / + *
The strategy requires skipping the 3, 2 and 6
and only then replacing 8 6 - by 2.
The next step requires skipping 3 and 2
and only then replacing 6 2 / by 3.
The next step requires skipping 3
and only then replacing 2 3 + by 5.
The final step requires no skipping,
3 5 * is replaced by 15.
All this skipping is of course inefficient.
A better strategy would apply the next operator at the point of the most recent change, if that is possible. An obvious way to do this is to use a stack of values for intermediate results. As the expression is being processed, operands such as literal numbers are pushed, and operators pop their arguments off the stack and push their result. This is of course the method commonly used for evaluating postfix expressions. So we have the following situation: The rewriting rules for programs are purely syntactic, they do not mention the stack. But the stack can be used as an optimisation of the rewrite rules. On the other hand, the stack is apparently an essential semantic entity, it is the argument and value of the functions denoted by programs.
But this now raises the question whether the stack is just an optimisation for the rewriting system or whether it is really needed as a semantic object. In other words, is it possible to give a semantic characterisation of Joy which does not involve a stack at all? In such a semantics the programs will have to denote something, and presumably they will have to denote functions. But what might be the arguments and values of these functions?
It will help to review the stack based semantics of Joy: The literals such as numerals, characters, strings and quotations denote functions taking any stack as argument and producing another stack as value which is like the argument stack except that a single item has been pushed on top. The operators also denote unary functions from stacks to stacks, and the result stack is like the argument stack except that the top few items have been replaced by the result of applying some operation. Likewise, the combinators denote unary functions from stacks to stacks, and the result stack depends on the combinator and the top few quotations.
To obtain a Joy semantics without a stack we take our hint from the rewriting rules. The operators and combinators no longer denote functions from stacks to stacks. The rewrite rule for addition transforms a program ending with two numerals into a program ending with a numeral for their sum. This is the key for a semantics without a stack: Joy programs denote unary functions taking one program as arguments and giving one program as value. The literals denote append operations; the program returned as value is like the program given as argument, except that it has the literal appended to it. The operators denote replacement operations, the last few items in the argument program have to be replaced by the result of applying the operator. Similarly the combinators also denote (higher order) functions from programs to programs, the result program depends on the combinator and the last few quotations of the argument program.
It is clear that such a semantics without a stack is possible and that it is merely a rephrasing of the semantics with a stack. Purists would probably prefer a system with such a lean ontology in which there are essentially just programs operating on other programs. But most programmers are so familiar with stacks that it seems more helpful to give a semantics with a stack. Its is of course irrelevant for the semantics that for efficiency reasons any implementation of Joy will in fact use a stack.
There is one other argument for a stack semantics. By a program one would normally mean one that can be run, at least when supplied with appropriate parameters. The stack, however, can sometimes contain sequences of items that make the stack a non-executable program because it violates type rules. Such situations arise for example by executing one of the following:
[ 3 * ] second
[ pop cons map ] [] step
The first results in the one operator * being pushed.
The second results in two operators and one combinator to be pushed.
Such situations are required only rarely.
But the possibility is needed,
for example for a Joy interpreter joy written in Joy itself.
Such an interpreter is described in another paper.
It was mention in section 3 that for quotations there is no rewrite rule of the form
[P] ==> [Q] :- P ==> Q.
If there were such a rule, then the rewriting
42 dup ==> 42 42.
would license
[ 42 dup ] ==> [ 42 42 ].
and hence
[ 42 dup ] second ==>> [ 42 42 ] second.
dup ==>> 42.
which is absurd.
On the other hand,
[ 42 dup ] i + ==> [ 42 42 ] i +
is acceptable.
So, quotations must not allow substitutions in all contexts,
but only in those where the quotation is guaranteed to be undone
by a dequoting operation, by a combinator.
In other words, quotation is an intensional constructor.
There is a simple way out of this,
and it is to treat quotations of programs to be very different
from lists.
Notice that the absurdity comes from taking the second
element of the quotations [42 dup] and [42 42].
If it were forbidden to treat quoted programs as data structures,
then the fatal inference would be blocked.
In detail,
such a treatment would look like this:
If P is a program, then (P) is its quotation,
now written inside round parentheses.
Also, [P] is its list, as before written inside
square brackets.
Both (P) and [P] can be pushed onto the stack,
can be swapped, duplicated and popped,
can be inserted into lists and later extracted.
But only (P) can be used as a parameter for combinators,
and it cannot treated as a list.
On the other hand, [P] cannot be used
as a parameter for combinators,
but it can be treated as a list.
Importantly, there could then be a reduction rule
(P) ==> (Q) :- P ==> Q.
and hence quotation would be an extensional constructor.
This is a draconian solution, it allows programs such as
[2] cons reverse
but forbids
(+) cons map
The latter uses map to add a single number on top of the stack
to each member of a list that is second on the stack.
If the single number on top of the stack is, say 7,
then the cons operation produces (7 +)
to be used by map.
The prohibition would rule out parameterisation.
In general,
the prohibition would rule out using constructed programs
as parameters to combinators.
It is possible to make a less drastic compromise:
As before, quotations (P)
serve as parameters to combinators,
but they can also be built up by list operations
such as concatenation or consing
further items into their front.
This would allow parameterisation as in the map example above.
Quotations could be constructed and built up further and further
and eventually called by a combinator,
but quotations could not be destructed.
On this proposal constructive operations on quotations
would be allowed, but destructive operations would not.
All list operations would need to be classified as constructive
or destructive.
Even the size operator would turn out to be destructive.
This compromise solution has much in its favour. Quotation is extensional, combinators can use constructed programs, but the absurdity does not arise. On the other hand, the compromise requires a syntactic distinction between quotations and lists, and it requires a semantic distinction between operations that can be applied to lists and to quotations, and those that can be applied only to lists.
On the whole, then, it does seem preferable to have quotation as an intensional constructor.
The rewriting system described up to here concerned values.
It is also possible to give a rewriting system for Joy type expressions.
We shall need constant and variable symbols for these types.
The following will be used as type constants:
Log for the truth values,
Chr for the characters,
Int for the integers,
Set for the sets,
Str for the strings and
Lst for possibly heterogeneous lists.
For lists whose member are all of the same type, say Int,
the notation [Int] will be used.
As variables we use
T, T1, T2 and so on.
So [T] is the type of lists whose members are all of
the type T.
The following is a sample of one style of rules for operators:
T1 T2 swap => T2 T1.
Int Int + => Int.
Str size => Int.
The notation used above has been made as close as possible
to the notation for the rewriting rules for values.
In the following a different notation will be introduced
which is more useful.
Literals have atomic types,
operators and combinators have compound types.
There are three constructors for compound types:
type concatenation, type quotation and type cancellation.
The first two are derived from the corresponding program constructors.
The third is new and has no counterpart program constructor.
It uses the infix symbol -> to combine two types into a new one.
If T is a type, then so is its quotation [T] .
If T1 and T2 are types,
then so are their concatenation
(T1 T2) and their cancellation T1->T2 .
If P1 and P2 are programs of types
T1 and T2 ,
then the type of their concatenation (P1 P2)
is the concatenation (T1 T2) of their types.
Cancellation satisfies the law
T1 T1->T2 => T2
For types with concatenated parameter types:
(T1 T2)->T3 => T1->(T2->T3)
The expression on the right of the arrow can be written
without parentheses on the convention that the cancellation
operator \ is taken to be right associative.
The three rules given above should now be rewritten in this style:
swap => (T1 T2) -> (T2 T1).
+ => (Int Int) -> Int.
size => Str -> Int.
The following are a sample of further rules in the two styles: Those in the left column are in the earlier style, those in the right are in the new style.
Chr succ => Chr. succ => Chr->Chr.
Int Int > => Log. > => (Int Int)->Log.
Log Log and => Log. and => (Log Log)->Log.
[T Lst] first => T. first => [T Lst]->T.
[T Lst] rest => Lst. rest => [T Lst]->Lst.
T Lst cons => [T Lst]. cons => (T Lst)->[T Lst].
[T Lst] uncons => T Lst. uncons => [T Lst]->(T Lst).
Chr Str cons => Str. cons => (Chr Str)->Str.
Set null => Log. null => Set->Log.
Consider now the program P below.
Its type is given by the concatenation of the types of its parts,
in the line just below.
All the types here are built from the atomic type Int
of integers.
By four applications of cancellation the type in line 1 is simplified
to the type Int in line 4.
P: 2 3 + dup * 1. Int Int (Int Int)->Int Int->(Int Int) (Int Int)->Int 2. Int Int->(Int Int) (Int Int)->Int 3. (Int Int) (Int Int)->Int 4. Int
For combinators only only a few examples will be given here, for i and map.
i => [T] -> T.
map => ([T1 -> T2]) -> ([T1] -> [T2]).
The formalism used in this section is that of categorial grammars. These have their origin in the (simple) theory of types and as generating devices are as powerful as context free grammars. Expositions and applications are to be found in the volume edited by \AX{Oehrle {\it et al}}{1988}{Oehrle-etal:88}, see in particular the contributions by \X{Casadio} and \X{Lambek}. Another reference is the volume edited by \AX{Buskzkowski {\it et al}}{1988}{Buszkowski-etal:88}.
Rewriting systems are purely syntactic. If the object language has a semantics, then the rewriting rules have to be shown to be correct with reepsect to this semantics. This is true of the rewriting rules of the previous sections which dealt with values. It is also true for the rewriting rules for types. The basic semantic notion here is that of assigning types to programs. These take the form
P : T
which is not a rewriting rule but a statement
which says that program P is of type T.
The basic type statements are to atomic programs,
literals, operators and combinators.
Here are some examples:
42 : Int 'A : Chr
succ : Chr -> Chr > : Int Int -> Log
first : [T Lst] -> T i : [T] -> T
This is the style adopted in the Joy manual.
To obtain rewrite rules using =>
a single conditional rule is needed which converts the semantic
predicate : into the syntactic =>,
as follows.
X => T :- X : T.
The material in this section has very tentative, most of the details need to be worked out fully.