Atomic Programs of Joy

by Manfred von Thun

Abstract: 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.

Introduction

The design of Joy was motivated mainly by {Backus78} who argued that language concepts should be selected on the basis of yielding strong and clean mathematical laws. This paper describes the atomic programs of Joy from which larger programs are concatenated, it does not describe the algebra or other theoretical issues related to Joy.

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.

Types and Literals

Joy programs are built from smaller programs by means of concatenation. The ultimate building blocks are atomic programs which do not have any programs as parts. Like all programs, atoms denote unary functions. It is useful to classify atoms on the basis of what kinds of functions they denote. Three broad classes can be distinguished in terms of their domain and range. For expository purposes it is helpful to adopt procedural terminology for a while, and to express the classification in terms of what the atoms do to the stack component of the state.

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 comparison, 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 concerns 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.

General Operators

An operator is a function which expects as argument one stack whose top few elements satisfy some condition and which returns a stack in which the top few elements have been replaced by something else, and which otherwise is like the argument stack. For most operators the top few elements are replaced by just one element, but there are some for which they are replaced by none or by two. In fact, operators may be defined in which any number (0, 1 …) of elements on the argument stack are replaced by any number (0, 1 …) of elements on the result stack. A unary operator is one whose argument stack requires at least one element. A binary operator is one whose argument stack requires at least two elements. There are even some ternary operators.

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    pop2    dupd

The swap operator interchanges the top two elements. The popd operator removes the second element. The pop2 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 first 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.

Operators for Simple Types

The following binary operators are defined for all numeric types. They have their usual meaning, and the result is given the type of the second parameter:

        +    -    *    /    rem    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.

Operators for Aggregate Types

The following unary operators expect a non-empty aggregate on top of the stack:

        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 four 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 aggregate 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 containing 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.

Predicates

A predicate is a function which leaves a truth value on the stack. The following unary predicates are defined for all numeric types:

        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 sets 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 truth 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.

General Combinators

Most functional languages are based on the lambda calculus. As one of their fundamental operations they use the application of a function to its arguments or parameters. The formal parameters of functions have explicit names, and application requires the substitution of the actual parameters for the formal parameters. In Joy there are no named formal parameters, and most of the work of application is done instead by combinators. Combinators behave like higher order functions – they take other functions as parameters. However, they take those other functions in the form of quoted programs from the stack. Hence combinators are like literals and operators in that they denote first order functions from states to states. This is possible because the property of being higher order is transferred to (the stack component of) the state. So, combinators require that the top of the stack contains one or more quotations.

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 dipdand 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:

        i    unary2    unary3

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~~unary2 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~~i and ~~app3~~unary3 behave analogously: The ~~app1~~i combinator causes just one execution of the quotation, and it replaces X by X'. The ~~app3~~unary3 combinator causes 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:

        while    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 on the two values separately. The else2-part then has available the two results from these two executions. The genrec combinator for general recursion 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.

Combinators for Simple Types

Some combinators expect values of specific types below their quotation parameters. The combinators in this section expect values of simple types.

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.

Combinators for Aggregate Types

The combinators in this section expect aggregates below their quotation parameters.

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    treegenrec

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 the combinator [C] is executed, and it will find on top of the stack the program [[[O] C] treerec]. The slightly more general treegenrec 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] treegenrec] on top of the stack.