by Manfred von Thun
Joy is a functional programming language which is significantly different from other programming languages of that kind. This paper provides an overview of most of its practical and theoretical aspects.
To add two integers, say 2 and 3, and to write their sum, you type the program:
2 3 +This is how it works internally: the first numeral causes the integer
2 to be pushed onto a stack. The second numeral causes the integer 3 to
be pushed on top of that. Then the addition operator pops the two
integers off the stack and pushes their sum, 5. The system reads inputs
like the above and executes them when they are terminated by a period
".", like this:
2 3 + .In the default mode there is no need for an explicit output
instruction, so the numeral 5 is now written to the output
file which normally is the screen. So, in the default mode the
terminating "." may be taken to be an instruction to write
the top element of the stack. In what follows the terminating period
will not be shown any further.
To compute the square of an integer, it has to be multiplied by itself. To compute the square of the sum of two integers, the sum has to be multiplied by itself. Preferably this should be done without computing the sum twice. The following is a program to compute the square of the sum of 2 and 3:
2 3 + dup *After the sum of 2 and 3 has been computed, the stack just contains
the integer 5. The dup operator then pushes another copy of the 5 onto
the stack. Then the multiplication operator replaces the two integers by
their product, which is the square of 5. The square is then written out
as 25. Apart from the dup operator there are several others
for re-arranging the top of the stack. The pop operator removes the top
element, and the swap operator interchanges the top two elements.
A list of integers is written inside square brackets. Just as integers can be added and otherwise manipulated, so lists can be manipulated in various ways. The following concatenates two lists:
[1 2 3] [4 5 6 7] concatThe two lists are first pushed onto the stack. Then the
concat operator pops them off the stack and pushes the list
[1 2 3 4 5 6 7] onto the stack. There it may be further
manipulated or it may be written to the output file.
Joy makes extensive use of combinators. These are like operators in that they expect something specific on top of the stack. But unlike operators they execute what they find on top of the stack, and this has to be the quotation of a program, enclosed in square brackets. One of these is a combinator for mapping elements of one list via a function to another list. Consider the program:
[1 2 3 4] [dup *] mapIt first pushes the list of integers and then the quoted program onto
the stack. The map combinator then removes the list and the
quotation and constructs another list by applying the program to each
member of the given list. The result is the list [1 4 9 16]
which is left on top of the stack.
In definitions of new functions no formal parameters are used, and hence there is no substitution of actual parameters for formal parameters. After the following definition:
square == dup *the symbol square can be used in place of
dup *.
As in other programming languages, definitions may be recursive, for
example in the definition of the factorial function. That definition
uses a certain recursive pattern that is useful elsewhere. In Joy there
is a combinator for primitive recursion which has this pattern
built in and thus avoids the need for a definition. The
primrec combinator expects two quoted programs in addition
to a data parameter. For an integer data parameter it works like this:
If the data parameter is zero, then the first quotation has to produce
the value to be returned. If the data parameter is positive then the
second has to combine the data parameter with the result of applying the
function to its predecessor. For the factorial function the required
quoted programs are very simple:
[1] [*] primreccomputes the factorial recursively. There is no need for any
definition. For example, the following program computes the factorial of
5:
5 [1] [*] primrecIt first pushes the number 5 and then it pushes the two
short quoted programs. At this point the stack contains three elements.
Then the primrec combinator is executed. It pops the two
quotations off the stack and saves them elsewhere. Then
primrec tests whether the top element on the stack
(initially the 5) is equal to zero. If it is, it pops it
off and executes one of the quotations, the [1] which
leaves 1 on the stack as the result. Otherwise it pushes a
decremented copy of the top element and recurses. On the way back from
the recursion it uses the other quotation, [*], to multiply
what is now a factorial on top of the stack by the second element on the
stack. When all is done, the stack contains 120, the
factorial of 5.
As may be seen from this program, the usual branching of recursive
definitions is built into the combinator. The primrec
combinator can be used with many other quotation parameters to compute
quite different functions. It can also be used with data types other
than integers. Joy has many more combinators which can be used to
calculate many functions without forcing the user to give recursive or
non-recursive definitions. Some of the combinators are more
data-specific than primrec, and others are far more
general.
Joy programs are built from smaller programs by just two operations: concatenation and quotation. Concatenation is a binary operation, and since it is associative it is best written in infix notation and hence no parentheses are required. Since concatenation is the only binary operation of its kind, in Joy it is best written without an explicit symbol. Quotation is a unary operation which takes as its operand a program. In Joy the quotation of a program is written by enclosing it in square brackets. Ultimately all programs are built from atomic programs which do not have any parts. The semantics of Joy has to explain what the atomic programs mean, how the meaning of a concatenated program depends on the meaning of its parts, and what the meaning of a quoted program is. Moreover, it has to explain under what conditions it is possible to replace a part by an equivalent part while retaining the meaning of the whole program.
Joy programs denote functions which take one argument and yield one value. The argument and the value are states consisting of at least three components. The principal component is a stack, and the other components are not needed here. Much of the detail of the semantics of Joy depends on specific properties of programs. However, central to the semantics of Joy is the following:
The concatenation of two programs denotes the composition of the functions denoted by the two programs.
Function composition is associative, and hence denotation maps the associative syntactic operation of program concatenation onto the associative semantic operation of function composition. The quotation of a program denotes a function which takes any state as argument and yields as value the same state except that the quotation is pushed onto the stack. One part of a concatenation may be replaced by another part denoting the same function while retaining the denotation of the whole concatenation. One quoted program may be replaced by another denoting the same function only in a context where the quoted program will be dequoted by being executed. Such contexts are provided by the combinators of Joy. These denote functions which behave like higher order functions in other languages.
The above may be summarised as follows: Let P,
Q1, Q2 and R be programs, and let
C be a combinator. Then this principle holds:
IF Q1 == Q2
THEN P Q1 R == P Q2 R
AND [Q1] C == [Q2] CThe principle is the prime rule of inference for the algebra of Joy which deals with the equivalence of Joy programs, and hence with the identity of functions denoted by such programs. A few laws in the algebra can be expressed without combinators, but most require one or more combinators for their expression.
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:
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 list. 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.
Concatenation of Joy programs denote the composition of the functions
which the concatenated parts denote. Hence if Q1 and
Q2 are programs which denote the same function and
P and R are other programs, then the two
concatenations P Q1 R and P Q2 R also denote
the same function. In other words, programs Q1 and
Q2 can replace each other in concatenations. This can serve
as a rule of inference for rewriting. As premises one needs
axioms such as in the first three lines below, and definitions such as
in the fourth line:
(+) 2 3 + == 5
(dup) 5 dup == 5 5
(*) 5 5 * == 25
(def square) square == dup *A derivation using the above axioms and the definition looks like this:
2 3 + square
== 5 square (+)
== 5 dup * (def square)
== 5 5 * (dup)
== 25 (*)The comments in the right margin explain how a line was obtained from the previous line. The derivation shows that the expressions in the first line and the last line denote the same function, or that the function in the first line is identical with the function in the last line.
Consider the following equations in infix notation: The first says
that multiplying a number x by 2 gives the same result as
adding it to itself. The second says that the size of a reversed list is
the same as the size of the original list:
2 * x = x + x size(reverse(x)) = size(x)In Joy the same equations would be written, without variables, like this:
2 * == dup + reverse size == sizeOther equivalences express algebraic properties of various
operations. For example, the predecessor pred of the
successor succ of a number is just the number itself. The
conjunction and of a truth value with itself gives just the
truth value. The less than relation < is the converse of
the greater than relation >. Inserting a number with
cons into a list of numbers and then taking the sum of that
gives the same result as first taking the sum of the list and then
adding the other number. In conventional notation these are expressed
by:
pred(succ(x)) = x x and x = x
x < y = y > x sum(cons(x,y)) = x + sum(y)In Joy these are expressed without variables:
succ pred == id dup and == id
< == swap > cons sum == sum +Some properties of operations have to be expressed by combinators. One of these is the dip combinator which expects a program on top of the stack and below that another value. It saves the value, executes the program on the remainder of the stack and then restores the saved value.
In the first example below, the dip combinator is used
to express the associativity of addition. Another combinator is the
app2unary2 combinator which expects a program on
top of the stack and below that two values. It applies the program to
the two values.
In the second example below it expresses one of the De Morgan laws.
In the third example it expresses that the size of two lists
concatenated is the sum of the sizes of the two
concatenands.
The last example uses both combinators to express that multiplication
distributes (from the right) over addition. (Note that the program
parameter for app2unary2 is first constructed
from the multiplicand and *.):
[+] dip + == + +
and not == [not] unary2 or (* app2 *)
concat size == [size] unary2 + (* app2 *)
[+] dip * == [*] cons unary2 + (* app2 *)A deep result in the theory of computability concerns the elimination of recursive definitions. To use the stock example, the factorial function can be defined recursively in Joy by:
factorial ==
[0 =] [pop 1] [dup 1 - factorial *] ifteThe definition is then used in programs like this:
5
factorialBecause in Joy programs can be manipulated as data, the factorial function can also be computed recursively without a recursive definition, as follows:
5
[ [pop 0 =] [pop pop 1] [[dup 1 -] dip i *] ifte ]
[dup cons] swap concat dup cons iThe second line in this program does much the same as the body of the
definition of factorial, but it is a quoted program. The third line
first transforms this into another longer quoted program which performs
“anonymous” recursion, and then the final i combinator
essentially dequotes this program causing its execution.
The third line implements Joy’s counterpart of the Y combinator of the lambda calculus. Exactly the same line can be used to cause anonymous recursion of other functions which are normally defined recursively.
Joy has other combinators which make recursive execution of programs more succinct. (Of course it is also possible in Joy to compute the factorial function more efficiently with iteration instead of recursion.)
Since Joy is very different from familiar programming languages, it takes a while to become used to writing programs in Joy. One way to start the learning process is by way of writing some simple generally useful library programs. In an implementation these may be part of an actual library, or they may be built into the language.
Some general utility programs include operators for manipulating the Joy stack just below the top element, further operators for manipulating aggregate values, and a few output programs.
Generally useful are the stack type and the queue type. Values and operators of these two types are easily implemented as Joy lists and list operators.
Another collection of useful operators take an aggregate as parameter and produce a list of subaggregates. These operators are polymorphic in the sense that the aggregate parameter can be a (small) set, a string, or a list. One such operator can take a set as parameter and produces a list of its subsets. All of these operators are definable without recursion by using the linrec combinator.
Some arithmetic operators are often used to illustrate recursive definitions, although it is well known that iterative execution is more efficient. In particular the use of accumulating parameters can often replace recursion. This is easily done in Joy using various iteration combinators.
Values of sequence types, such as strings and lists, can be sorted, and sorted sequences can be merged. Programs for doing this are easily written in Joy without recursive definitions but using appropriate combinators instead.
Joy’s inbuilt datatype of sets is implemented just as bitstrings, and hence it is limited to small sets of small numbers. The more useful big set type, which allows large sets of elements of any type, can be implemented in any language which has lists. It is simple to do in Joy, and the usual set-theoretic operations are easily provided. A similar implementation can be used for the dictionary type, which uses lookup tables for finite functions.
Also useful is the tree type, of lists, or lists of lists, or lists of lists of lists … of elements other than lists.
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 + and < operators and for the dip
combinator:
2 3 + -> 5
2 3 < -> true
a [P] dip -> P aIn 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 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 + -> 5In 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 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 an 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.
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 aUnlike 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 iThey 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 best known functional languages are the lambda calculus and, based on it, the programming languages LISP and its descendants. All of them rely heavily on two operations, abstraction and application, which are in some sense inverses of each other. Abstraction binds free variables in an expression, and it yields a function which is a first class value.
The bound variables are the formal parameters of the function, and, importantly, they are named. Application of an abstracted function to some actual parameters can be understood as resulting in a substitution of actual for formal parameters and then evaluation of the modified expression. More efficiently application can be implemented using an environment of name-value pairs. The lambda calculus does not need definitions, but all functional programming languages allow them as a matter of convenience. Definitions also use named formal parameters, and in applications these have to be substituted or an environment has to be maintained.
Two other functional languages are the combinatory logic of Curry and the FP language of Backus. They are not based on the lambda calculus, they eliminate abstraction completely and hence do not have to deal with substitution and environments. As a result these languages can be manipulated using simple algebraic techniques. But like the lambda calculus and the languages derived from it, both are based on the application of functions to arguments. However, application does not have attractive algebraic properties, and hence there is no theoretical reason for preferring one concrete notation over another.
The languages of category theory comprises another group of functional languages. Whereas the other functional languages use function application, these use function composition. No high-level programming language has been based on this formalism, but it has been used as a low level machine language as a target for compilation from a (typed) lambda calculus source. Joy is a high-level programming language which resembles the categorical languages more than it resembles any of the other functional languages.
The prototype implementation is written in (K&R) C; it uses a simple stop-copy heap management.