You are here: Atomic Programs of Joy
TITLE> Atomic Programs of JoyAbstract: Joy is a functional programming language based on the composition of functions taking one stack as argument and yielding one stack as value. Stacks can contain values of simple types such as truth values, characters and integers, and values of aggregate types such as sets, character strings and quoted programs with lists as a special case. The stack functions include the usual operations such as addition, comparison and list manipulation, but also many new kinds of functions which dequote quoted programs in various ways. These new functions behave like higher order functions, such as conditionals, various forms of recursion, and for aggregates the map, fold and filter functions. This paper gives an overview of the basic programs from which others are built by composition and quotation.
Keywords: functional programming, function composition, higher order functions, quotation and dequotation of programs, combinators.
Joy programs denote functions which take states as arguments and as values. Programs are built from atomic programs which also denote functions which take states as arguments and as values. The meaning of compound programs has to be given in terms of the meanings of atomic programs. It is useful to classify atomic programs into categories depending on what kind of function they denote. A coarse classification distinguishes just three, called 1) the literals, 2) the operators and 3) the combinators.
Firstly, the literal atomic programs are those which look like constants in conventional languages. They comprise literal numbers (or, more correctly, numerals) such as integers, and other literals of type character, string, truth value and set. Literals do not denote numbers, characters, strings and so on, but they denote functions which take one state as argument and yield as value another state which is like the argument state except that the value of the literal has been pushed onto the stack component.
Secondly, the operator atoms are those which look like n-ary operators in other languages. They include the operations such as for addition and the other arithmetical operations, and for the various operations on other types. Like all programs, operators denote functions from states to states, but the functions are not defined on all states. An n-ary operator (such as the binary addition operator) denotes a function which is defined only on states whose stack component has n items (such as two integers) on top.
The function yields as value another state which is like the argument state except that the n items on the stack have been replaced by the result (such as the sum).
Also included as operators are those atoms denoting mere structural
functions of the stack component such as dup,
swap and pop, and those that involve input and
output such as get and put.
Thirdly, the combinator atoms are like operators in that they require the top of the stack to contain certain items. But unlike operators, they do not treat these items as passive data. Instead they execute these items - and hence those items must be quoted programs. So, combinators also denote functions which are defined only on states having the appropriate number of quoted programs on top of the stack. They yield as values another state which depends on the argument state, including the quoted programs, and on the combinator itself.
Literals, operators and combinators can be concatenated to form programs. These may then be enclosed in square brackets to form literal quotations. Such literals are not atomic, but if they occur in a program they are treated just like other literals: they cause the quoted program to be pushed onto the stack. So, literal quotations denote functions which take any stack as argument and yield as value another stack which is like the argument stack except that it has the quotation pushed on top. Quotations on top of the stack can be treated like other values, they can be manipulated, taken apart and combined, but they can also be executed by combinators. If a quotation contains only literals, then it is a value of the list type. The component literals do not have to be of the same type, and they may include further quotations. If a list is executed by a combinator, then its components are pushed onto the stack.
The remainder of this paper is organised as follows: The next section describes the principal types of Joy and their literals. Following that are four sections on operators, the general ones applicable to all types, then those applicable to simple types such as integers, characters and truth values, then those applicable to aggregate types such as strings, sets and lists, and finally the predicates which return truth values. The following three sections deal with combinators, first those that are independent of any typing, then those specialised to simple types, and finally those specialised to aggregate types.
Some atoms can be applied to any stack and their effect is to push something on the stack. The items that can be pushed are of various types. There are simple types such as integers, characters and truth values. There are also aggregate types such as strings, sets and quoted programs. Atomic programs which push a simple or aggregate value onto the stack will be called literals. A different kind of atom can be applied only to a non-empty stack. Their effect is to re-organise the top few elements of the stack.
Some, like dup, swap and pop, just edit the top few elements. Others expect the top few elements to be of certain types and their effect is to replace these elements by the result of applying a function to them as arguments. These include the arithmetic and relational operators for addition, multiplication and comparisons, and the truthfunctional operators. They also include list operations like concatenation. Collectively all of them will be called operators. A third kind of atoms expect quoted programs on the top of the stack. Like the operators, they pop the quoted programs off the stack. But they do not treat them as passive data structures in the way operators do. Instead they cause the quoted programs to be executed. These are called combinators.
After this rough exposition of the classification it is important to suppress any procedural reading and to revert to the official interpretation of Joy programs as denoting unary functions. So the three classes of atoms, namely literals, operators and combinators, all denote unary functions from and to states which include a stack as a principal component. The remainder of this section will deal with literals.
First, the literals of the integer type. The following is the offical semantics of those atoms that look like numerals:
A digit string such as "123" denotes not a
number but a function from states to states. For any
state S1 as argument this function yields as its value another state
S2 which is like S1 except that its stack component has an additional
item, the number 123 pushed onto it.
The semantics for the truth value type is similar: The two
symbols true and false denote functions which
for any state as argument yields as value another state which is like
the argument state except that the logical constant true
or false has been pushed onto the stack. Literals of the
character type can be treated just like small numbers. So, a
quoted character such as 'A denotes a function taking any
state into another state with that character pushed onto the stack.
The three types of truth values, characters and integers constitute what will be called simple types. They are simple in that their values do not have parts. There are also aggregate types which do have parts. The parts can be extracted by suitable operators and the aggregates can be constructed from their parts. Joy has three different aggregate types: sets of small numbers, strings of characters, and quoted programs, which have lists as a special case.
The set type comprises the usual unordered collections
familiar from set theory. The elements of a set are written inside
curly braces, such as {1 3 5}. The whole is a literal
atom, and it denotes a function pushing that set onto the stack. For
most implementations on current machines the elements of sets will be
small numbers in the range 0 .. 31, The
string type of character strings constitutes another
aggregate type. Its literals are written as zero or more characters
enclosed in double quotes, such as "Hello". Such a
literal again denotes a function, one which pushes that string.
The third aggregate type is that of quoted programs, or briefly, quotations. Its literals are written inside square brackets. A program consists of zero or more literals, operators or combinators. Enclosing it in square brackets turns it into a quoted program. Quotations denote functions which push the quoted program; the quoted program is not executed, it is pushed onto the stack in "suspended animation". The following are quotations:
[1 2 3] ['A 'B "CDE" {10 11 12}]
[pop dup *] [[[]]]
[peter paul mary] ["" {} [] [hello "Hello"]
A value of the list type is just a special case of a
quotation in which the elements are themselves literals. Quotations
can contain other quotations, and hence lists can contain other lists.
The following concern connections between quotations and the stack. The stack is normally a sequence of values of various types. This sequence is just a special list which is modified by programs. Since it 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. Finally, it should be possible to create a new, empty stack. There are three operators that do just that:
stack unstack newstack
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. The
newstack operator deletes the entire stack and replaces it
with a new, empty one. 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.
It is sometimes useful to treat several types together. The numeric types are integers and characters, the Boolean types are truth values and sets, and the sequence types are strings and lists. A leaf is anything which is not a list, and a tree is either a leaf or a (possibly empty) list of trees.
This completes the brief survey of the six principal types and their literals. Other types might be included in more elaborate versions of Joy. Obvious simple types to add are real (and perhaps complex) numbers, and an enumeration type as in Pascal. It is less clear what new aggregate types are useful since lists already are so versatile. Records and arrays are certainly possible. Only files will be considered briefly below.
First, the following unary operators are defined on all stacks containing at least one element:
pop dup
The top element does not have to satisfy any particular condition, it
can be of any type. The pop operator removes the top
element. The dup operator pushes a duplicate on top, so it
replaces the one original by two copies.
The following binary operators are defined on all stacks containing at least two elements:
swap popd popop dupd
The swap operator interchanges the top two elements. The
popd operator removes the second element. The
popop operator removes the first and the second element.
The dupd operator duplicates the second element.
The following ternary operators are defined for all stacks containing at least three elements:
swapd rollup rolldown
The swapd operator interchanges the second and third
elements but leaves the first element in place. The rollup
operator moves the third and second element into second and third
position and moves the first element into third position. The
rolldown operator moves the second and first element into
third and second position and moves the third element into first
position.
There is another ternary operator:
choice
The choice operator expects three values on top of the
stack, say X, Y and Z, with
Z on top. The third value from the top, X,
has to be a truth value. If it is true, then the
choice operator just leaves Y on top of the
stack, and X and Z disappear. On the other
hand, if X is false, then the choice operator
just leaves Z on top of the stack, and X and
Y disappear. This operator is related to two combinators
ifte and branch which are explained in the
next sections.
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.
opcase
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.
The following two operators handle input and output:
put get
The put operator expects one item on top of the stack, it
removes it and writes it to the output file. The get
operator expects one item in the input file, it reads it from there
and pushes it on top of the stack.
+ - * / % max min
The following unary operators are defined for all numeric types.
succ pred abs sign
The succ and pred operators yield the
successor and predecessor, respectively. The
abs operator computes the absolute value, and the
sign operator returns the signum value, an integer
which is -1, 0 or +1 depending on
whether the parameter is negative, zero or positive.
The following mathematical functions are provided:
fact exp fib nfib gcd
The unary fact operator computes the factorial
function. The binary exp operator computes the
exponentiation function, the exponent is the top parameter.
The binary fib operator computes the Fibonacci
function. The binary nfib operator computes a similar
function, which is the number of calls which a recursive
implementation of the Fibonacci function would need; if this function
is implemented recursively, then the number of its calls is the same.
The binary gcd operator computes the greatest common
divisor.
The type of truth values is one of the Boolean types. The operators are
and or xor not
The three binary operators and, or and
xor compute the logical conjunction, inclusive
disjunction and exclusive disjunction. The unary
not operator computes the negation.
first second third rest
The first operator extracts the first element of values of
the sequence types string and list. For sets it extracts the first
member using the underlying ordering. The second operator
expects an aggregate of at least two elements, for sequences it
extracts the second element, for sets it extracts the second element
under the ordering. The third operator expects an
aggregate of at least three members, it extracts the third element.
The rest operator expects an aggregate with at least one
member, it returns an aggregate which is like the parameter aggregate
but has its first element removed.
The following binary operators require an aggregate and a potential member on top of the stack:
cons swons
The cons operator expects the aggregate on top of the stack
and the potential member below. The effect is to add the potential
member into the aggregate. In the case of strings and lists the
potential member is added in front. In the case of sets the potential
member is added only in case it is not already a member. The
swons operator does essentially the same except that it
expects the potential member on top and the aggregate below.
Essentially swons is equivalent to the composition
swap cons, and hence its name. The two operators are
converses of each other.
The following unary operators also require a non-empty aggregate on top of the stack:
uncons unswons
The uncons operator replaces the aggregate element by two
elements, the first and the rest, with the rest on top. The
unswons operator does the same, but with the first on top.
These two operators differ from other operators in that they leave
two values on top of the stack. Such operators would not
make much sense in other notations. Their names were chosen because
their effect is to undo the effect of the two binary operators
cons and swons.
There are two operators for indexing in various ways:
at of drop take
These four binary operators expect an aggregate and a number. That
number is used for indexing into the aggregate. The at
operator expects the aggregate A and above that a number N, it
returns that member of the aggregate which is at the N-th position
in the aggregate. The of operator expects a number N and
above that an aggregate A, it returns the N-th member of A. So
the two operators are converses of each other. The
drop and take operators both expect an aggregate
A and above that a number N. The drop operator
returns an aggragate like A except that the first N elements have
been removed. The take operator returns an aggregate like
A except that only the first N elements have been retained. For
all four operators in the case of sequences the sequence ordering is
used, and for sets the underlying ordering is used.
The following are some general operators for aggregates:
size reverse concat swoncat
zip flatten transpose
The unary size operator determines the number of elements
of any aggregate, and for lists this means top level members. The
unary reverse operator reverses strings and lists, it has
no effect on sets. The binary concat operator concatenates
two sequences of the same type, it appends the top parameter to the
second parameter. The swoncat operator does the same
except that it executes a swap first. The binary
zip operator expects two aggregates of the same type. It
returns a list of lists of two elements, each pair taken from
corresponding elements in the aggregates. The size of the result list
is the same as the size of the smaller of the two parameter
aggregates. The unary flatten operator expects a list of
sequences and combines them by concatenation. The unary
transpose operator is for matrix manipulation. It also
expects a list of lists L1, L2 ... and returns a list of
lists. The first sublist contains the first members of the Li,
the second sublist contains the second members, and so on. The list
returned has as many members as the shortest of the Li.
The type of sets is another of the Boolean types. The operators are
and or xor not
The three binary operators and, or and
xor compute the intersection, union and
symmetric difference. The unary not operator
computes the complement. For most implementations on current
machines the complement will be with respect to the largest set,
{0..31}.
The following operators on sequences deal with ordering of their elements:
qsort qsort1 merge
The unary qsort operator uses the quicksort
algorithm to return a sorted version of the parameter. The
qsort1 operator does the same, except that it expects a
list of sequences which it sorts according to the first element of the
sequences. The binary merge operator is like the
concat operator in that it produces a single sequence.
The difference is that it picks elements from the two sequences in
accordance with their order. If the two sequences were sorted, then
the result of merging them is also sorted.
The following are arithmetic operations for lists of numbers:
sum product scalarproduct
The first two expect a list of numbers, the sum operator
adds them up, the product operator multiplies them, and for
empty lists the results are 0 and 1 respectively. The
scalarproduct operator expects a list of two lists of
numbers. It multiplies corresponding elements of the two lists and
returns the sum of these products.
The following unary operators expect an aggregate on top of the stack and leave a list of various subaggregates on top of the stack:
frontlist restlist powerlist subseqlist permlist
Let the size of the aggregate be (N). The frontlist and
restlist operators return a list of N+1 subaggregates.
The frontlist operator returns a list, beginning with the
empty aggregate, obtained by successively adding the last, second last
... first member of the original aggregate. The restlist
operator returns a list, beginning with the original aggregate, by
successively removing the first, second ... last member of the
original aggregate. The powerlist operator returns a list
of all 2^N subaggregates such that for each member of the
original aggregate there will be one subaggregate in the list
containing it and one not containing it. The subseqlist
operator is similar, but it returns a shorter list of (N * (N-1) / 2
+ 1 ) subaggregates containing only consecutive members of the
original aggregate. The permlist only applies to sequence
aggregates, it returns a list of all the N! (N factorial)
permutations of the sequence.
A related binary operator is
insertlist
The insertlist operator expects a sequence and above that
another potential member. It returns the list of all sequences
obtained by inserting the potential member in all possible positions
in the sequence.
A related binary operator for finding the cartesian product is
cartproduct
which expects two aggregates that do not have to be of the same type.
The cartproduct operator returns a list of all pairs (as
two element lists) of elements taken from the two aggregates. If the
aggregates have M and N members, there will be M × N pairs
in the result list.
The following unary operators expect a tree:
treeflatten treestrip treereverse treesize
The treeflatten operator turns a tree into a flat list
containg the leaves of the tree. The treestrip operator
returns a tree with the same structure but with all leaves removed.
The treereverse operator returns a tree in which
(recursively) all internal lists have been reversed. The
treesize operator returns an integer which is the number of
leaves.
odd even positive negative
The odd and the even predicate return
true or false just in case the parameter is
odd or even. The positive and the negative
predicate return true or false just in case
the parameter is positive or negative -- note that truth values and
characters are never negative.
The following binary predicates are defined for all numeric types, they have their usual meaning:
= != < <= > >=
The following are two unary predicates defined for all types:
null small
The null predicate is true if its simple parameter is
numerically zero or its aggregate parameter is empty. The
small predicate is true if its simple parameter is
numerically zero or 1, or its aggregate parameter contains at most one
element.
The following binary predicates test aggregates for members:
in has
The in-predicate is true if the second parameter is in the
top aggregate parameter. The has-predicate is true if the
aggregate second parameter has the top parameter as a member. The two
predicates are converses of each other.
The following binary predicate is defined for two aggregates of the same kind:
equal
The equal predicate is true if the two aggregates have the
same members. For strings and lists this means same members in the
same positions. For lists this means recursive equality.
Sometimes it is necessary to test a parameter for its type. This is done by the following unary predicates:
logical char integer set string list leaf
The predicates logical, char,
integer, set, string and
list are true if the parameter is a true value, character,
integer, set, string or list, respectively. The predicate
leaf is true if the parameter is not a list.
Sometimes it is useful to operate on quoted predicates to obtain another quoted predicate. There are three such operators:
conjoin disjoin negate
The two operators conjoin and disjoin expect two
quoted predicates and return one quoted predicate. If that is ever
called it will compute the conjunction or disjunction of the two
parameters. The other operator is negate which expects one
quoted predicate and returns a quoted predicate which computes the
negation.
Combinators can be classified in many ways: in terms of the number of expected quotations, in terms of the total number of expected parameters, quotations and others, in terms of their behaviour, and so on. To fix the terminology, combinators will be called unary, binary, ternary and so on, if they expect one or two or three quotations, and so on. But note that many combinators expect further parameters below the quotations which they will execute. The following are some simple unary combinators which require the top of the stack to be one quotation.
i x y
The i combinator pops the quotation off the stack and
executes it, effectively by dequoting. The x
combinator leaves the quotation on the stack and executes it.
Consequently the x combinator will be executing on a stack
which has as its top element the very same quotation which it is
currently executing. The y combinator first converts the
quotation [P] into a different quotation [Q]
with the following strange property: if [Q] is ever called
by some combinator, then it builds a copy of itself on top of the
stack and then executes the [P]-part of itself. After
this conversion, the y combinator calls the
[Q] it has constructed. In this way the y
combinator builds some of the behaviour of the x
combinator into the [Q].
Another unary combinator is
nullary
No matter how many parameters the quotation consumes from the stack
when nullary executes it, they are all restored and the
final value calculated by the execution of the quotation is pushed on
top of that.
The next unary combinators allow manipulation of the stack below the top few elements:
dip dipd dipdd
The dip combinator requires a further element X
to be below the quotation. It removes the quotation and
X, saves X somewhere, executes the quotation
on the remainder of the stack, and finally restores X.
The dipd and the dipdd combinator are similar.
They expect two or three elements, (X) and (Y), or (X), (Y)
and (Z) below the quotation. The two or three elements are saved
and restored after the execution of the quotation.
Three further unary combinators are
app1 app2 app3
Apart from the quotation which they expect on top of the stack, they
require one or two or three further elements on the stack. So the
app2 combinator requires two further elements, say
X and Y. In this case the quotation will be
executed twice, once with X on top of the stack and once
with Y on top of the stack. The executions could be done
in any order, even concurrently, provided there are no side effects.
If both executions terminate, both should leave behind a non-empty
stack with respectively X' and Y' on top.
These two values, in their order, are then pushed onto the stack in
place of X and Y. The two other combinators
app1 and app3 behave analogously: The
app1 combinator causes just one execution of the
quotation, and it replaces X by X'. The
app3 combinator cases three executions of the quotation,
and it replaces X, Y and Z by
X', Y' and Z', maintaining the
order.
The binary combinators expect two quotations on top of the stack.
b cleave
The b combinator expects two quotations [P] and
[Q], with [Q] on top. It removes the two
quotations and executes first [P] and then
[Q]. The cleave combinator also expects two
quotations, and below that an item X. It also first
executes [P], with X on top, and then saves
the top result element, say P(X). Then it executes
[Q], again with X, and saves the top result as
Q(X). Finally it restores the stack to what it was below
X and pushes the two results P(X) and
Q(X).
The ternary combinators expect three quotations on top of the stack. One of the most important is
ifte
The ifte ("if-then-else") combinator 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. It executes
the if-part, which must yield a truth value. It saves that value and
restores the stack to what it was before the if-part was executed. If
the saved value was true the then-part is executed,
otherwise the else-part is executed.
There are two combinators for doing simple looping:
whiledo tailrec
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. The ternary tailrec
("tail-recursion") combinator 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.
The quaternary combinators expect four quotations on top of the stack.
linrec binrec genrec
The linrec combinator for linear recursion expects
an if-part, a then-part, an else1-part and on top an else2-part. Like
the ifte combinator it executes the if-part, and if that
yields true it executes the else-part. Otherwise it executes the
else1-part, then it recurses with all four parts, and finally it
executes the else2-part. The binrec combinator for
binary recursion is similar, except that the else1-part has
to produce two values. The recursion with all four parts is executed
an the two values separately. The else2-part then has available the
two results from these two executions. The genrec
combinator for general recursion is also has an if-part, a
then-part and two else-parts.
It differs from the other two combinators in that after the execution of the else1-part nothing in particular is executed, but a program consisting of the four parts and the combinator is pushed onto the stack. The else2-part thus has it available as a parameter.
For linear recursion the if-part often is [null] and the
else1-part often is either [pred] for numeric types or
[uncons] for aggregate types. The two parts are built
into
primrec
for primitive recursion. The binary primrec
combinator expects two quotations, a start-part (similar to the
else-part of the earlier combinators) and a combine-part (similar to
the else2-part of the earlier combinators. Below that it expects a
value of any type. The combinator essentially supplies the other two
parts.
There are several combinators which do not have a fixed number of quotation parameters. Instead they use a list of quotations. They are
cond condlinrec
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. 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
have an additional then2-part. Again the first if-part that yields
true selects its corresponding then1-part for execution.
If there is a then2-part, the combinator first recurses and then
executes the then2-part. The last program is the default, it does not
have an if-part.
The cleave combinator also has a generalisation:
construct
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.
The following binary combinator expects a truth value below its two quotation parameters:
branch
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.
The following unary combinator expects a numeric value below its quotation parameter:
times
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.
The stack is just a list, so any list could serve as the stack, including a list which happens to be on top of the stack. The following unary combinator expects a list below its quotation parameter:
infra
The infra combinator temporarily discards the remainder of
the stack and takes the list to be the stack. It then executes the
quotation which yields a result stack. This result is then pushed as
a list onto the original stack replacing the original list. Hence any
quotation can serve as a complex unary operation on lists.
The following unary combinator expects an aggregate below its quotation parameter:
step
The step combinator removes the aggregate and the
quotation, and then repeatedly puts the members of the aggregate on
top of the remaining stack and executes the quotation. For sequential
aggregates such as strings, lists or more generally, quotations, the
members are selected in the order of their occurrance in the
aggregate. For sets the members are selected on the basis of their
underlying order. So the quotation is executed as many times as the
aggregate has members. What happens to the members depends entirely
on the quotation. In the simplest though unlikely case where the
quotation does nothing, the members are left on the stack in the order
in which they occurred in the aggregate with the last member on top.
There is a related combinator for stepping through two aggregates:
step2
The step2 expects two aggregates which do not have to be of
the same type. Above that it expects a quotation. It steps through
the lower aggregate and for each member it steps through the higher
aggregate. The pairs of members are then made available to the quoted
program. If the aggregates have M and N members, there will be M
× N pairs.
The following combinators for aggregates are mostly familiar from list processing languages:
map fold filter split
All four step through the members of the aggregate in the same manner
as the step combinator. The map combinator
combines the results of applying the quotation to create a new
aggregate of the same type as the original. The fold
combinator expects a quotation which computes a binary function, below
that a value, the initial value, and below that an
aggregate. It uses the binary function to combine the members of the
aggregate into one single value, and if the aggregate happens to be
empty it returns the initial value.
The filter combinator needs a quotation which computes a truth value, so it is a test. It applies the test to each member of the aggregate and creates a new aggregate containing those members of the original which pass the test. The resulting aggregate is of the same types as the parameter. The split combinator only makes sense in a language in which a function can return two values.
It is like the filter combinator except that it returns
two aggregates - one containing the members of the original which did
not pass the test, and above that another containing those which did
pass the test. The resulting aggregates are of the same type as the
parameter. In both result aggregates the ordering of the original
aggregate is preserved in case they are strings or lists.
The following unary combinators expect an aggregate below their quotation parameter which must compute a truth value:
some all
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 following unary combinator expects two aggregates and above that a program suitable for combining their respective elements:
zipwith
The zipwith combinator produces a list which is as long as
the smaller of the two aggregate parameters. The elements of the
resultlist are obtained by using the program parameter to combine
corresponding members of the two aggregates.
The following unary combinators expect a program and below that a tree:
treestep treemap treefilter treefold
They all resemble corresponding combinators for aggregates. The
treestep combinator uses the program to process the leaf
nodes in the same way as step handles members of an
aggregate. The treemap combinator uses the program to
compute replacement leaves for a tree which has the same structure.
The treefilter combinator needs a program that yields a
truth value, it produces a tree of only those leaves which pass the
test. The treefold combinator expects an initial
value above the tree and above that the quotation which is used to
combine the leaves with the initial value.
There are two tree combinators which are similar to the
genrec combinator:
treerec treerecgen
and above that two quotations, [O] and [C].
If the tree is a leaf, then [O] is executed, typically an
operation on a leaf. If the tree is not a leaf, then then combinator
[C] is executed, and it will find on top of the stack the
program [[O] [C] treerec]. The slightly more general
treerecgen combinator also expects a tree but above that
three quotations: [O1], [O2] and
[C]. If the tree is a leaf, then [O1] is
executed. If it is not a leaf, then first [O2] is
executed, and then the combinator [C] is executed which
will find [[O1] [O2] [C] treerecgen] on top of the stack.