Joy is a purely functional language in the spirit of
pure Lisp, pure Scheme, ML and Miranda.
But whereas these languages are based on the application of functions
to parameters, Joy is based on the composition of functions.
Syntactically it looks much like Forth, and one consequence is that
in Joy all formal parameters of defined functions are anonymous.
However, unlike Forth, Joy also has lists which can be manipulated
as data structures and, provided they are of the right kind,
can be executed as programs by means of what are called *combinators*

The implementation described in the latter sections of this chapter is quite minimal. The implementation makes heavy use of the utilities developed in Chapter 17.

The first part of this introduction provides a theoretical motivation for the language, the second part gives a practical overview based on examples. These two parts can be read in any order; theoretically minded readers should read the first part first, practically minded readers should read the second part first.

In strongly typed languages the declaration of functions must include the types of the parameters and the type of the result. For example, in Pascal one might have the following declarations for the length of a list and the concatenation of two lists:

`*`

.
These type assignments to the two functions are entirely abstract,
they have nothing to do with the concrete syntax.
For example, the length of the concatenation of the two lists
`[a b]`

and `[c d e]`

could be written in any of the following ways:

`@`

is the explicit binary operation
of function application;
the function on its left is being applied to the parameter on its right.
For the application of concatenation the parameter is a pair.
Strictly speaking the words `length`

and `concat`

are used to denote functions as objects
--- the only function that is being used is the binary application function,
here written in infix, which takes two objects to produce a third.
Languages like this are sometimes called applicative languages
(as opposed to functional languages).
There is an analogy with set theory here:
whereas in predicate logic one uses all sorts of relations,
in set theory the only relations used are
Sometimes functions that take two or more parameters
are interpreted as taking them one at a time ---
they are then said to be *curried*.
The type assignments and the example expression now look like this:

`[a b]`

to any list to which
it is applied, here to `[c d e]`

.
The application symbol is often made left-associative,
and then the inner parentheses in the expression can be omitted.
However, the outer parentheses cannot be omitted, as in
However, length can be *composed* with concatenation,
and the result of composing these two functions is a function
which takes two lists as parameters and yields an integer as value.
Writing `o`

for composition of functions we have the type
assignment and the expression maximally and minimally parenthesised:

`[a b]`

it yields a function taking a list `L`

as a parameter
and giving as value `4 + (4 + length(L) * length(L)`

.
If `L`

is `[a b c]`

, then the value is 25, as required.
There is something very satisfying about composition,
it is associative and it has the identity function as
the left and right identity element:
If `id`

is the identity function, then for any function `F`

,

However, this does not work if any but the rightmost function takes more than one parameter. Clearly, instead of concatenating two lists, then taking the length and then the square, one could equivalently take the lengths of the two lists, take the sum of those, and then the square of that.

`[c d e]`

,
can be supplied as a parameter to sum because that is in the
middle of the composition expression.
So it seems that there is no way to have less than the two operations
of application and composition,
and to dodge the need for parentheses.
This is all the more infuriating if we compare the notation using composition and application with ordinary Polish or prefix notation. The two expressions are simply

One possible answer is that it is just a bad question to ask about any notation. For example, one would not ask this question about the infix notations

`+`

do not stand for anything semantic,
it is just a way of writing terms with two parameters.
It is the term that has semantic significance,
and it has no concrete syntactic properties at all.
This applies to any concrete notation,
and hence the concatenations in prefix notation
do not mean anything either.
Another possible answer is that the concatenations in prefix notation sometimes mean composition and sometimes mean application. In any one case the meaning depends on the number of parameters which the functions denoted require, and parentheses are restored as needed. On this view, then, the prefix notation is just short for the versions given earlier:

But there is a third possible answer,
and it is the one that will be pursued in the remainder of this
chapter.
This is the answer that in the prefix notation
the concatenation of symbols always means composition of functions.
This is a radical view because the functions being composed will *all*
have to be unary functions.
In particular,
concatenation and addition are unary and not binary,
operands such as list and numerals
are not nullary but unary.
On this view the prefix notation is shorthand for
the composition of unary functions:

`M`

, `M1`

, `M2`

...
Henceforth we omit the composition symbol `o`

again,
and remember that concatenation of symbols denotes composition
of the unary functions denoted.
Hence we have, for all `M`

,
the applications

`M`

.
And because the applications all result in the same object,
the composed functions themselves are identical.
On this view, then, computation takes unary functions as input
and produces unary functions as output.
The mystery objects can remain mysterious
unless making them explicit clarifies matters.
For long computations it is often helpful to be able
to see the result of intermediate computations.
One starts with some input data,
applies a partial computation and inspects the result.
If all went well one applies the next computation step
to the result of the previous computation.
This continues until the whole computation is completed.
If at any time the result is not what was expected,
one modifies the last computation step.
So the data come first, then comes computation step `S1`

, ...
finally comes computation step `SN`

:

`D1`

and `D2`

that both have to be processed individually first,
then combined, and the result processed further:
One advantage of mapping composition onto concatenation
is that it becomes easy to manipulate programs as data
and then to execute them with *combinators*.
The simplest combinator is `i`

which effectively removes brackets and executes
what is inside.
For example, all of the following are equivalent to 25:

`map`

combinator:
The following is a tutorial on Joy.

The large number of garbage collections is due to the fact that for testing purposes the amount of memory available for user nodes was on purpose kep absurdly small.

If you did not read the theoretical first part of this introduction, then you should do that now.

This section develops the design principles of the Joy language up to a full definition.

Joy was designed to make its semantics as simple as possible.
The semantics of any language is given by a function which
assigns meanings to the basic components of the language ---
be they formulas, terms or programs.
For example, in propositional logic the semantic function
assigns a set of interpretations in which a given formula is true.
In particular, a disjunction `P v Q`

is true in all interpretations in which `P`

is true or `Q`

is true.
Hence to a disjunction the semantic function `SEM`

assigns
the union of the interpretations in which `P`

is true
with the set of interpretations in which `Q`

is true.
Similarly,
to a conjunction `P & Q`

the function `SEM`

assigns
the intersection of the set of interpretations in which
`P`

is true and the set of interpretations in which `Q`

is true.
In an arithmetic language the semantic function `SEM`

assigns numbers to terms,
and to `X + Y`

it assigns the sum of the numbers assigned to `X`

and `Y`

.
In propositional logic there are two special formulas,
say `F`

and `T`

, which are the identity elements
for conjunction and disjunction,
the function `SEM`

maps them onto the
identity elements for union and intersection,
the empty set of interpretations
and the universal set of interpretations.
In arithmetic there is the numeral `0`

which the function `SEM`

maps onto the identity element for
addition, the number zero.

Binary composition of functions is an associative operation with the identity function as the left and right identity; together they form a monoid. For a very simple semantics, one now needs a binary operation on programs and a left and right identity such that the semantics preserves the operation and the identity; the semantic function which associates with every program a meaning then is a homomorphism. A suitable monoid on programs consists of the binary operation of concatenation of programs as lists together with the empty list as the left and right identity.

This section describes the core part of the language which is implemented directly. The other parts are built on top of this in the library.

*Pushing Data*:
Literals of type Boolean, character, integer and list
can be pushed onto the stack just by writing them.
Strictly speaking a numeral such as `123`

does not denote
the number 123 but a function which takes stacks as arguments
and stacks as values;
for an arbitrary stack S1 as argument the function has as its
value another stack S2 which is like S1 except that it has
an additional item, the number 123, on top.

The two Booleans are written `true`

and `false`

.
Character literals consist of a single quote followed by the character
or by the escape character `\`

followed by the decimal ASCII
value of the character.
Integers are written in decimal notation with an optional preceding
unary minus.
Lists are enclosed in `[`

and `]`

.
As a *meta*notation we write `[X]`

for the unit list
whose only element is `X`

,
we write `[]`

for the empty list,
`[Xs]`

for a list containing zero or more members `Xi`

,
and `[X Xs]`

for the list containing one or more members `Xi`

,
with `X`

as the first element.
Symbols are just letters followed by up to 15 further
letters, digits and underscores.

*Operators*:
There are several operators on values of various types.
They are written in postfix notation and take their parameters
from the stack.
Parameters are counted from the top of the stack;
so the third parameter is the third item on the stack.
The three untyped operators `pop`

, `dup`

and `swap`

take parameters of any type.

*Combinators*: These are operators which expect lists on the top
of the stack; they will remove them from the stack
and execute them as programs.
The simplest is the `i`

combinator.
It expects a list as its only mandatory parameter
on the top of the stack, it removes this list and executes
it as a program.
Hence it satisfies:

Slightly more complicated is the `dip`

combinator.
It expects two mandatory parameters on the top of the stack.
The second parameter can be anything.
The first parameter, topmost,
has to be a list.
The `dip`

combinator removes these two parameters from the stack
and then executes the list as a program.
Typically the execution will change the stack.
After that, the `dip`

combinator will restore what
was its second parameter to the top of the now current stack.
So its principal use is to produce a change
in the stack without affecting the top element.
For a data value `X`

, the `dip`

combinator satisfies

Very useful is the `step`

combinator,
which takes two mandatory parameters.
The second parameter has to be a list of arbitrary data values.
The first parameter, topmost, has to be a list
which can be executed as a program.
The `step`

combinator removes the two parameters.
Then, starting with the first element, if any,
of the list of data,
it pushes that datum on the stack and then executes the other list
as a program.
This is repeated for each datum member of the second parameter.
If that list was empty, then the first parameter is not executed at all.
The `step`

combinator satisfies

There are two combinators for stepping through the elements
of a list:
`stepl`

traverses the list from left to right, and
`stepr`

traverses the list from right to left.
The list to be stepped through has to be the fourth parameter
on the stack.
The other three are two functions and a constant.
The third parameter has to be a function,
for each element of the list it will be applied to the stack
with that element topmost, and below that what was below the list.
This application will produce a value on top of the stack.
The second parameter is a constant.
For the first element of the list the produced value will
now be combined with the constant using the first parameter.
For any further elements of the list the produced value
will be combined with the result of the previous combination.

There are two reasons for having such a small core language: 1) to help in identifying the necessary primitives, and 2) to keep the implementation as small as possible. One consequence is that the implementation is quite inefficient.

To turn the library into a complete reference,
the meanings of the primitives
are explained in comments.
The defined concepts and the primitives
are given in their alphabetical order
because the program uses a binary search through
the identifiers defined in the library.
The program makes two passes through the library.
The `SET`

, `IF`

and `PUT`

directives at the beginning and end
produce messages when the library is loaded.
There are also two `INCLUDE`

directives.
The first included file contains a definition of a Joy interpreter
written in Joy, it is discussed later in this chapter.
The second included file contains answers to some exercises
given at the end of this chapter.

This section develops some aspects of a theory of the Joy language: an algebra for manipulating Joy programs by means of reduction rules, a rudimentary theory of Joy types, and a Joy interpreter written in Joy.

`{a b ..}`

which may be finite or infinite.
Strings over A are sequences of zero or more members of A.
Let a binary relation between strings be given by a set of
identities of the form `S1 = T1`

, `S2 = T2`

and so on.
Write `S == T`

for the smallest reflexive, symmetric and transitive
extension of this relation which
also satisfies the condition
`R S U`

and `R T U`

are concatenations having
`S`

and `T`

somewhere in the middle.
*Example*:
propositional logic in prefix notation,
with just the constants 0 and 1, negation `-`

, and conjunction `&`

.
Consider the rewrite relation given by

Clearly the method works not only for various styles of notation but also for various types: truth values, numbers, strings, lists and other constructions. Since there are only two truth values, it is possible to give a short list of rewriting rules for the operators. But already for numbers an infinite collection of rewriting rules is needed. This collection has to be specified in a finite way --- but this does not present an obstacle. For Joy rewriting rules are needed for all data types and for the stack operations. Here is an example:

In Joy there is no need for named parameters in definitions --- the mechanism of naming is replaced by stack operations and by combinators. This is illustrated by all the functions defined in the standard library. (Note that any variables occurring there are inside comments explaining the meaning of primitives.)

Backus (1981) argued that programming concepts should satisfy strong and clean mathematical laws. In Joy the absence of named parameters has the consequence that his requirement holds in a rather startling way. The following are some examples of laws that can be written in infix or in functional notation and with variables - in the left column, and can also be written in Joy notation without variables - in the right column.

The associativity of concatenation and its left and right identity are expressed by the first two laws below. The third law relates the b-combinator with concatenation. The associativity of functional composition is expressed by the fourth law. (Henson (1987, p 258) criticises presentations of the FP-systems originally due to Backus (1978) in that they do not give a law to this effect, although they use it in proofs.) Finally, the last law expresses that the empty program is the left and right identity of functional composition.

In this part we develop a rudimentary theory of Joy types.

As indicated in the introduction, all Joy functions are unary functions taking a complex object as their sole parameter and yield a complex object as their value. The complex objects consist of a stack, an input file and an output file. Because of this, the composition of two appropriate functions is well-defined. Furthermore, all functions are of the same type.

For many purposes this last result about types leaves out far too much. It fails to distinguish the various data types that can be manipulated on the stack and shifted between the stack and the two files. Clearly there are some important differences between the following:

`B`

(oolean), `C`

(haracter),
`I`

(nteger) and `L`

(ist).
Here are some examples:
Because Joy uses postfix notation, an elegant calculus of types can be developed for it. This calculus is adapted from what are called categorial grammars, see the end of this section for some reading. The type expressions are defined recursively as the smallest set generated under the following rules:

The theory of Joy types needs to be developed much further. It would be most useful in a Joy compiler.

*Reading*:
The quotation type introduced here appears to be new.
On the other hand, the concatenation and cancellation types
in this section are adapted from categorial grammars,
a generating mechanism equivalent to context free grammars.
For a survey of uses of categorial grammars see the book
edited by Oehrle, Bach and Wheeler (1988).
In that book the chapters by Casadio and Lambek
are probably most useful for the theory of Joy types.

In this section we develop a Joy interpreter written in Joy itself. This will serve several purposes: it is an exercise in developing a Joy program, it shows how well Joy can talk about itself, and it is a basis of the Joy interpreter to be written in Pascal in the next section.

The first version is merely a reminder that
Joy already has a combinator, namely the `i`

combinator,
which removes a program from the top of the stack
and executes it.

The next version makes explicit the fact that Joy programs are lists which are interpreted by stepping through the members of the list and executing each in turn, by considering them as unit size programs:

The next version has to spell out the various cases.
The select-operator and the i-combinator together
perform rather like a `CASE`

statement in Pascal.
The list of cases has to be pushed first.
So the next version takes the *form*:

`CASELIST`

consists of a list of cases `c1`

, `c2`

and so on.
Clearly, among the cases to be considered are at least
the primitives used in the interpreter so far:
1) the `select`

operation,
2) pushing a list or program,
and 3) two combinators,
the `step`

combinator and the i-combinator.
It is best to consider the `select`

operation first.
It has to be handled like most other operations `P`

:
to interpret `P`

which is on top of the stack,
the primitive `P`

has to be popped,
and then the primitive operation `P`

has to be executed.
This gives the following case for the `select`

operation:
`[pop select]`

.
The `i`

combinator executes this,
which has the consequence of `pop`

ping the `select`

operator
which is now on top of the stack.
Then the `select`

operation is executed, as required.
As can be seen,
the interpreter will also have to use the `pop`

primitive,
and therefore it will also have to implement it:
`select`

operation used in the interpreter
only looks at the type of something,
so the empty list can serve as the sample list:
`step`

and `i`

combinators.
It would be possible to treat them just like operators:
`step`

combinator is being executed,
having a program `[Ps]`

as a parameter,
the `step`

combinator should encounter a program
which will eventually call the Joy interpreter
recursively, but first push `[Ps]`

.
So it has to execute
`step`

combinator.
First,
the `step`

combinator is popped off.
Now `[Ps]`

is on top of the stack.
Second, the unit program `[Joy]`

is pushed.
Then the two are `cons`

'ed together to yield `[[Ps] Joy]`

.
If this is ever executed, it will push `[Ps]`

and then use Joy to interpret it.
It will be executed as many times as there are
elements in the list below,
and the execution is under the control of
the `step`

combinator.
For uniformity the same method is used for the
`i`

combinator, although it would be possible for it
to just call the Joy interpreter recursively.
`cons`

operation,
so the interpreter has to be able to handle this operation, too.
Here then is a complete but minimalist version of Joy-in-Joy:

This is not universal yet,
what is still needed are two stack operations `swap`

and `dup`

,
one list destructor `uncons`

,
and one combinator `dip`

:

The final version is actually part of the library, as an included file:

*Declarations*:
The program makes use of the utilities from Chapter 17 almost everywhere.
Therefore the utilities have to be processed by the Pascal compiler
before the program proper can be processed.
But the utilities are not entirely stand alone,
they require several previously declared labels, constants
and even two types: symbols and standard identifiers.
Only after these have been declared can the file containing the
utilities be included.
After that file has been processed,
anything in the utilities is accessible.
Then follow any declarations specific to Joy:
constants, types, variables, procedures and functions,
and then the main program.
Hence the program has this structure:

*Data Structures*:
Apart from what is provided in the utilities,
there are two main data structures:
The first is a table of identifiers together with a code address.
The second is an array of code nodes,
consisting of an opcode, a value and a next field --- all used
by the program proper,
but also a Boolean flag needed for the garbage collector.
There are several registers pointing into the code.
One of these is the freelist of linked nodes that are known not to
be in use otherwise.
When the program needs a new node,
it calls a procedure to provide one;
normally it is taken from the freelist.
If the freelist has become empty,
then garbage collection occurs,
and hopefully the freelist will be replenished.
The garbage collector is described in detail
at the end of this section.

*Main*:
The main program begins by calling an initialisation procedure
whose body consists of calls to procedures in the utilities:
one call to initialise the scanner,
several calls to enter the reserved symbols,
and several calls to enter the standard identifiers.
Then the main program initialises the freelist:
all memory cells are set to unmarked,
all but the last memory cells are linked to their successor,
the last cell is linked to nothing,
and the freelist pointer is set to the first cell.

The main program then calls a procedure to read the library. It is necessary to make two passes through the library: on the first pass the identifiers to be declared are read and entered sequentially into the table of user identifiers; since the lookup procedure will use a binary search through this table, it is essential that the identifiers to be declared are in alphabetical order. On the first pass the right hand sides of the definitions are ignored. Then the library is read a second time. Now all identifiers can be looked up, and code can be generated for the right hand side of each definition and entered in the table for the identifier being defined. When the library has been read, any remaining memory is available to the user.

The main program then sets the stack to empty and enters its principal read-execute loop. It repeatedly reads a factor into its program register and then calls the Joy interpreter to execute that program.

*The interpreter*:
The principal interpreting procedure `joy`

is modelled after the Joy interpreter written in Joy
that was described in the previous section.
It takes as a value parameters a (possibly zero)
integer pointer to a sequence of next-linked nodes.
Its body consists of a loop which steps through this sequence,
thus modelling the operation of the `step`

combinator
of Joy-in-Joy.
Each individual step is handled by a `CASE`

statement
to model what in Joy-in-Joy is the
`select`

operator and the `i`

combinator.
The `CASE`

statement examines the op-field of the given node
and executes the appropriate code.

For pushing values of various types,
the `konS`

function is used to obtain a new node from the freelist.
For that node the op-field is the type of the value,
the value-field is the integer value,
and the next-field is the old stack.
For unary operations the required value is computed
for a new node whose next-field is the next-field of the old stack.
Since there are quite a few binary operations,
a tiny special purpose procedure can be used
which pushes the required item onto the old stack
with two of its top items removed.

For the combinators the interpreter has to call itself recursively.
The case for the `i`

combinator pops the topmost item of the stack
and executes it.
The case for the `dip`

combinator is similar,
except that the second item on the stack first has to be saved
on the dump.
Because this saving requires a new node and hence may trigger off
a garbage collection,
the first item also has to be saved on the dump.
After the execution,
the second item is restored from the dump onto the stack.
The case for the `step`

combinator
has to use a `WHILE`

loop to traverse
the list which is the second item on the stack.
For each element of that list,
the element has to be pushed onto the stack
and then the first item is executed.
The final case which results in a recursive call concerns uses of the library.
For these the required code sequence is taken from the
table of user declared identifiers,
the value field of the node contains the address in that table.
Hence that table does not have to be searched at run time.

Almost all the cases in the interpreter have to access value-fields and next-fields of nodes, they have to check that the nodes really exist and that they have the appropriate operator type. This is best done by a number of checking functions local to the interpreting procedure.

*Input and Output*:
The main program, the procedure to read the library,
and also the interpreter make use of two mutually recursive
procedures to read terms and factors.

The procedure for reading terms will read at least one factor,
and while the next symbol is the beginning of another factor
it will read a further one.
The code generated for this sequence of one or more factors
has to be linked correctly.
In a `VAR`

parameter the procedure returns
the address of the first factor it has read,
any further factors are linked to the first.

The procedure for reading factors consists essentially of a `CASE`

statement which dispatches on the currently seen symbol.
Number constants and character constants simply generate a new node.
Identifiers require the lookup procedure to be called to find the address,
then a new node is generated with that address as the value field.
Because the scanner handles hyphens before digits as unary minus
and otherwise as a special symbol,
the solitary hyphen cannot be handled together with other identifiers
but needs a special case.
Finally, a left bracket signals a list;
if the next symbol is the beginning of a factor,
then another term is read and made the content of that list,
otherwise the list is empty.
The procedure also uses a `VAR`

parameter to return the address
of the code for the factor it has read.

There are corresponding output procedures that are used by the interpreter and also in various places for listing, tracing and debugging.

The procedure for writing terms uses a `WHILE`

loop to write zero or more
factors by stepping along a list of next-linked nodes.
If there is a further factor,
a space separator is written, too.

The procedure for writing factors uses a `CASE`

statement to
dispatch on the op-field of the node.
For characters and integers it writes the values,
for Booleans it writes the appropriate identifier,
for identifiers in the library it uses the value-field
to index into the table of identifiers,
for all others it obtains the name from the table
of inbuilt standard identifiers.
For lists it writes `[`

and `]`

surrounding
what will be written by a call to the procedure for writing terms.

Both procedures do not actually do the writing themselves but call appropriate procedures from the utilities. This way whatever has to be written will get to the standard output file and, if a listing is being written, to the listing file.

For debugging and tracing it is useful to have another output procedure which writes the record fields of a given node to the output file and potentially to the listing file.

*The kons function and garbage collection*:
New memory nodes are needed by the program in many places:
to read the library,
to read a Joy program,
and when interpreting a Joy program
to manipulate the stack and the dump.
Addresses of new new nodes are provided by a function `kons`

,
normally new nodes are taken from the freelist
of linked nodes not otherwise used.
The function is similar to procedure generate in earlier programs:
its parameters are essentially the fields of the record
that is to be created.

When the freelist is empty, garbage collection must take place.
It is necessary to *mark* any nodes that are pointed to
directly or indirectly by the other registers:
the program, the stack and the dump.
The marking consists of a recursive traversal of any
so far unmarked nodes and setting the mark-bit for each node visited.
Then a single *sweep* is made through the available memory:
any nodes that are not marked are added to the freelist.
Also, in anticipation of the next garbage collection,
all nodes are set back to unmarked.
The mark sweep method is the simplest of all garbage collectors,
it takes only about 20 lines of code as part
of the body of the `kons`

function.

A good way to test a garbage collector is to exercise it (almost)
to death.
In the initial development of the implementation of Joy described here
only the absurdly small number of 20 memory cells was allowed
for user programs in addition to what is needed for the library.
This made detailed tracing of memory usage feasible,
and unfortunately it was necessary.
One of the early bugs discovered this way was the need for
the garbage collector to mark not only
the program-, stack- and dump-registers,
but also the value- and next-parameters of the `kons`

function itself.
Otherwise the execution of `swap`

, `cons`

and `uncons`

can create unmarked cells.

*Lookup*:
The only procedure that remains to be described is
the procedure which looks up identifiers in the table.
It is called in two places in the program:
when reading factors and for the second pass of
the procedure which reads the library.
It first searches the table for any identifiers
that might have been entered after the library has been read.
Since no order can be assumed,
this first search is linear,
starting with the most recent entry.
If the identifier was not found,
a binary search is made through the sorted portion
that was entered during the first pass through the library.
If it is still not found,
a binary search is made through the table of the inbuilt
primitives.
If it was not found there,
it is entered as the most recent entry
in the table of identifiers.
This part is not yet enabled when the library is being read.
The table of user introduced identifiers can only grow,
it is never scavenged.

The following is the Pascal source file.
It is not quite standard,
because it uses the utilities of the previous chapter
in an included file.
If your Pascal does not allow included files,
you will have to physically include that
file at the point where the `INCLUDE`

directive occurs,
about half a page down.
If your Pascal compiler follows the original (too) strict definition of
the language ---
by insisting that declarations of labels, types, variables
and procedures and functions occur strictly in this order ---
then the declarations of the utilities and of the Joy program
will have to be merged.
There are no procedures as parameters,
so it should be possible to write the program
in just about any version of Pascal.

*Algebra*:
Find Joy equations which express the De Morgan laws
and the left and right distributive laws.
All these laws have their duals, of course.

*Self-reproducing programs*:
1) Use the algebra of Joy programs to show that

`[Fs]`

for which
`i`

combinator finds a program of this kind
on the stack and then executes it,
then the execution will create that very same program on the stack.
2) Find some other programs which satisfy the same law.
3) Find programs `[Gs]`

and `[Hs]`

such that
`[Is]`

`[Js]`

`[Ks]`

`[Ls]`

`[Ms]`

such that
`=/=`

means `[Ms]`

is reproducing but not self-reproducing,
the child is not like its parent,
but the grandchild is like its grandparent.
5) Find a reproducing program such that each of
its descendants is different from each of its ancestors.
6) Find a self-reproducing program `[Ns]`

which is insensitive
to mutilation --- where a mutilation is either removing
the head (by `rest`

) or removing the body (by `first`

).
So it should satisfy
*Constructing Joy-in-Joy*:
The Joy interpreter written in itself
is very repetitive,
the cases fall into three groups in which the members
are almost alike.
Write a Joy program which is shorter than
the Joy-in-Joy interpreter and which constructs one.

*Automatic printout*:
In interactive work one frequently writes very small programs,
and in order to see what has been computed one tends to write
`put`

at the end of every little interactive program.
This can be a nuisance.
In Lisp this is avoided by the top-level read-eval-print loop
which always prints the last value that has been computed.
It is easy enough to add such a facility to the read-execute loop
of Joy.
But it would be better to have the automatic printing as an option.
Design a way of making automatic printout of the top item
of the stack, or even of the whole stack,
an option under user control.

*OOPS*:
In interactive work one often makes a mistake,
by accidentally deleting something from the stack
that was intended to be kept for later.
It would be useful be able to reset the stack
to what it was before the error was made.
One way to do so is to copy the stack register
to an OOPS-register before executing the next program.
Then, if a mistake did occur,
a new OOPS-command could restore the stack
to what it was.
Note that the OOPS-register will have to be marked
by the garbage collector.
Implement such an OOPS facility.

*Pretty Printing*:
The current output procedures just write to the output file
and potentially to the listing file without any formatting.
One way of improving on this is to devise
a method of indentation that makes it easier for the human reader.
A very simple method would add two columns of indentation
per list; the first `[`

to be written in the same line followed
by one space, then the first element (if any),
and the last element followed by a space and the closing `]`

.
So, for example,
the following is a list of three lists,
of 3, 0 and 2 elements respectively:

*Eliminating the dump*:
In the current implementation the dump serves to save
elements of the stack if they may be needed again later.
Describe at least two different implementation techniques
of eliminating the dump.
Do they offer any advantages?

*Implementing the library directly*:
As explained earlier,
this minimal implementation of the Joy language
is intended to highlight the essentials,
even at the expense of runtime efficiency.
Most of the useful operations are actually defined in the library,
and their execution requires the execution of many primitives.
For example,
the operation which selects the first element of a list
does so by 1) unconsing the list, producing
two elements, the first and the rest,
then by 2) swapping these two, so that the rest is now topmost,
and then by 3) popping the rest.
A total of four push operations occur,
when clearly just one would do.
So, having *first* not defined in the library but built in
as a primitive should speed up this common operation by a factor
of about three.
The same is true of just about all the operations
that are defined in the library -
it would be more efficient to include them as primitives.

One of the first combinators one would want to implement
directly is the `ifte`

combinator.
As it is currently implemented in the library,
essentially by the index-operation and the `i`

combinator,
it is particularly inefficient:
first, the `IF`

part and the `THEN`

part have to be swapped,
which uses two nodes.
Then they have to be paired to form a list of two elements.
The pairing requires an empty list to be pushed, another one node.
Then the two parts are cons'ed into that,
each requiring two nodes, a total of four.
Then the indexing operation pushes the appropriate part,
another node.
Only then does the `i`

combinator execute the appropriate part.
The total of eight wasted nodes could be eliminated entirely
by implementing the `ifte`

combinator directly.
Hence with four lines of easy Pascal one should be able to achieve
a speed up by a factor of eight for this combinator.

As an exercise, select some of the operators or combinators currently defined in the library and implement them as primitives. The chosen operations should then be commented out from the library. It would be possible to eliminate everything from the library, and then there would be no need for the program to read it (twice) prior to each run. However, the library would still be a useful document for the user to read, because it contains all definitions.

*Sets*:
Joy can be usefully augmented with other data types.
Sets could be useful, even if they do not have the same generality
as in Pascal.
As members of sets, just small numbers from 0 to, say, 31,
a maximum of 32, would be useful.
In a typical Pascal implementation
the value-field of a node can hold a 32 bit integer,
and alternatively it could be made to hold a 32 bit set instead.
There will have to be a notation for literal sets,
say for example {1 5 12}, which is similar to but different
from the notation for literal lists.
A range notation, as in say `{3..5 10..20}`

might be a good starting point.
As operations, just union and intersection would do
as binary operators,
and unary complementation with respect to
the universal set {0..31}.
To name these operations,
either new symbols could be introduced,
or the symbols `or`

, `and`

and `not`

could be made (ad hoc) *polymorphic*
by *overloading* their meaning in a type sensitive manner.
Additionally there should perhaps be transfer functions
which transform sets to lists and vice versa.

Larger sets would certainly be better, but they would occupy more space than the value-field can hold. So the value field could be made to hold a pointer to a set. But then sets have to be stored elsewhere, and separate memory management and garbage collection might have to be implemented just for that. One alternative is to implement large sets as linked lists of 32 bit sets.

*Reals*:
Much the same kind of decision has to be made if one wants to
implement real numbers.
If reals are going to be used a great deal,
then it is best to make the value-field large enough to hold a real.
Any other values will then waste some space.
If reals are only used rarely and memory is a problem,
then they should be implemented in a separate area of memory
with its own memory management and garbage collection.

*Other memory management*:
The efficient use of memory in dynamic languages
such as Lisp, Snobol and Prolog
has been the topic of intensive research.
Two broad areas of memory management are normally
distinguished:
garbage collection and reference counting.

Garbage collection requires a traversal of all used nodes to mark which ones are in use. The traversal can be either recursive, as it was done in the Joy implementation described above, or it can use a more sophisticated method of temporary pointer reversal to eliminate the need for the stack space in the recursion. Then in a second stage the unused nodes can be collected in a free-list; this is the mark-sweep method used here. Alternatively the used nodes can be copied to a dual area of memory from which further nodes will be taken until that is exhausted. Then this area is marked and the needed nodes are copied to the first area. This mark-copy method of garbage collection is particularly useful in virtual memory systems because it minimises fragmentation of memory.

Reference counters replace the mark-bit by an integer which keeps track of how many times a node is being referenced. When that count drops to zero, the node can be recycled. The great advantage of reference counting over garbage collection is that it works continuously. However, the method does not work with circular structures. Joy as described does not have circular structures, so reference counting is a candidate implementation method. On the other hand, one might well want to add circular structures to Joy, and then one would have to resort back to garbage collection.

*Reading*:
For a gentle exposition to functional programming
using Miranda see Bird and Wadler (1988).
For an exposition using ML see Reade (1989).
A more theoretical perspective can be found in Henson (1987).
The literature on Lisp contains many small interpreters
written in their own language.
Henderson (1980) develops this interpreter
into a program in a more conventional sequential language.
Kamin (1990) gives Pascal implementations of
small versions of many languages, including
several functional languages,
and of two memory management techniques:
mark-copy and reference counting.
Peyton Jones (1987) discusses theoretical aspects
of the compiler for Miranda.
For efficient implementations of functional languages,
using their inherent parallelism, and for
references to the extensive recent literature in that field,
see Kelly (1989).

The language Joy was inspired by Quine (1971) and Backus (1981), who in quite different fields argue for the elimination of variables (of different kinds). The earliest version of Joy was a (too) large implementation in Pascal, then followed much smaller ones in Prolog, Common Lisp, and, by a group of students, in C. A large, more or less final version is described in von Thun (1997). As all functional languages, Joy would lend itself to parallel execution, even if only by software on perhaps a transputer, but so far no attempts have been made in that direction. A Joy chip is at most a remote possibility.

Joy is unlike any of the conventional functional languages. The closest I have been able to find is the (virtual) machine language of CAM, the Categorical Abstract Machine in Curien (1986) and in Cousineau, Curien and Mauny (1987). The CAM machine language is not intended for the human programmer, instead it is used as the target language for implementations of languages such as ML. For Joy the programming language and the machine language are identical.

Any further development of the Joy language should consider the very high level combinators in Meijer, Fokkinga and Paterson (1991). These can be used to define the more familiar combinators such as map and fold.

Later, in Chapter 21, we will see a compiler written in itself,
in this chapter we have seen an interpreter written in itself.
The literature on Lisp and Prolog
contains other examples of interpreters written in their own language.
The idea of writing a language processor in its own language
can be carried further.
What are called *partial evaluators*
can compile interpreters into compilers;
and even more mind-boggling applications are possible.
For some recent references, see Jones (1990).
There is no reason why a partial evaluator
should not be written in Joy for Joy.
Another application of language processors written
in their own language gives rise to the
possibility of *reflection*,
a mode of interpretation in which a program
sometimes looks at itself rather than at the data.
This is an exciting new field,
references can be found in the collection
edited by Maes and Nardi (1988).

The projects outlined in this section go well beyond the scope of mere exercises. The first project concerns improving the efficiency of the implementation in a manner that goes deeper than the exercise suggested in the previous section. Two others deal with extending the language so that it becomes either an imperative or a relational one. The last section concerns a compiler for Joy.

Even if the entire library is eliminated in favour of primitives,
there is much room for optimisation.
Consider the if-then-else combinator `branch`

implemented directly in Pascal as suggested in the previous section.
It expects three items on top of the stack:
two executable programs, and below that one Boolean value
which will determine which of the two programs will be executed.
In most applications the two programs will occur literally
just before the `branch`

combinator.
Hence in any simple implementation the following will occur:
Some possibly complex calculation will produce the Boolean value.
Then two simple push operations will push the two programs onto the stack.
Then the `branch`

combinator will pop all three items,
and execute one of the two programs.
In other words,
the two programs are first pushed and then immediately popped.
But this is wasteful,
it would be better if the two programs were not pushed at all
but attached to the `branch`

combinator as parameters.
Then the calculation of the Boolean value will occur as before,
then this new kind of `branch`

combinator will inspect that value
and execute one of its parameters.

To implement this,
a special optimised version of the `branch`

combinator is needed.
Since the next field of any node is already needed for linkage,
only the value field is available.
It will have to be made to point to a pair of nodes,
one each for the two programs.
There are two places where special treatment is necessary:
in the compiling stage, where it is necessary to detect such
optimisable occurrences and to generate special code,
and in the interpreter, where this special code
is executed.
The compiler part would need fairly dramatic
redesign, since the code for pushing the two programs
will have to be taken back and attached to the
node for the special `branch`

combinator instead.
Since the code is generated not in an array but is taken
from the freelist,
any back references are not available and would have to be
added.
By contrast, adding a special case to the interpreter
to handle the optimised `branch`

combinator is quite trivial.

But there is a difficulty:
if a program is to be written and executed efficiently,
then two internal versions will be needed,
one for writing and one for executing.
This might seem like a draconian step,
but there are other reasons why one might consider this.
Take for example a simple program fragment `[ 2 3 + ]`

;
if this is to be written as a list with put,
then it will have to be stored that way;
and if it is to be evaluated with the `i`

combinator
or any other combinator, then
it is best if the program does constant folding
and replaces the `[ 2 3 + ] i`

by 5.
In other words, for maximal efficiency
one might trade the extra space required for
increased execution speed.

As a compromise,
one might consider actually changing the language:
say `BRANCH [thenpart] [elsepart]`

,
where `BRANCH`

is a binary prefix operator.

Recently there has been intensive research
devoted to functional programming with
infinite lists and other infinite data structures.
In this style of programming one
can (pretend to) compute an infinite structure
and then access arbitrary parts.
In reality the parts are only computed when they are needed.
The method of implementation used here
is called *lazy* evaluation.
For some reading, see Henderson (1980, Chapter 8),
Bird and Wadler (1988, Chapters 6 and 7),
and Reade (1989, Chapter 8).
To implement infinite structures and lazy evaluation
would require considerable redesign of the Pascal program.
However, it may be possible to write
an inefficient version of it in Joy itself.

The most dramatic increase in efficiency would be obtained by compiling Joy into some efficient language. But for full Joy the interpreter would still be needed for handling programs such as

`get`

.
So a compiler will only be able to speed up programs
that are known at compile time ---
and for many purposes that would be sufficient.
The difference between purely functional languages and sequential or imperative or procedural languages is this: In functional languages there is no internal state which can be changed, there is no notion of change at all, programs simply evaluate expressions. In the other languages there is an internal state --- typically a collection of variables whose values can be changed by assignments. As described so far, Joy is a purely functional language.

There is no computational reason why Joy should not be given assignable variables. These may but need not be declared to be of any particular type, indeed, since Joy as it stands is so weakly typed it is probably best not to introduce types for variables. In Joy it is possible to manipulate lists of symbols, for example one can write

`London`

does not result in a push operation,
any symbols not defined in the library are just noops,
denoting the identity function.
But this could be changed easily,
so that it does produce a push.
On the other hand, if one were to think
of symbols standing for assignable variables,
then one might want the The syntax for the assignment statement will have to distinguish the assignment position from the retrieving position. For example, the following could be taken to have the same meaning in Pascal and in extended Joy:

`Assign`

would be a unary prefix operator which takes
a variable as a parameter.
Note the difference between
`assign`

which takes a value, computed by `+`

,
and (a unit list of) a variable from the stack,
and `Assign`

which takes a value from the stack
and supplies its own variable.
The first is more flexible,
since the `[a]`

might have been computed;
but it is quite unclear whether such flexibility is desirable.
There is another way of introducing assignment
and hence change, it has been part of Lisp
since its inception.
To understand it one has to distinguish
between the variable, which is the name
of a location in memory,
and the location in memory itself.
When an assignment is being made,
what is made to change or vary is not the variable
but the memory location which it names.
So, if the locations could be referred to without naming them,
assignments need not use variables.
Suppose the stack contains at least two elements,
an arbitrary datum and a list, the list topmost.
The list is actually represented by
a memory node containing a pointer to a value
and a pointer to the next item.
The value and the next item in the list
could be changed by assignments,
for example by assigning to them
the value of the datum below the list.
In Lisp these two operations are called `replaca`

and `replacd`

;
for a good explanation of the implementation issues
see MacLennan (1983, pp 379 - 381)
and Henderson (1980, pp 116 and 175).

Joy programs denote functions taking a complex object
as parameter and yielding a complex object as value.
The objects consist of at least a stack, and at least
two files.
A quite different language would replace the functions
by relations, and to implement them one might use backtracking.
Possibly the two files would be excluded from the backtracking.
If there are assignable variables,
then two forms of assignment should be distinguished:
a normal assignment and a reversible one which is undone
on backtracking.
For such a language any program would denote
a relation between two memories which include stacks.
Many of these relations would be the familiar Joy functions,
but there could now be nondeterministic primitives:
a choice operation (`OR`

) and an impossible operation (`FAIL`

).
Nondeterministic additions to Lisp
are discussed in Henderson (1980, Chapter 7).
Another powerful addition would be the logical variables
as in Prolog.