**SA**: *May I begin by asking you about the
origins of Joy? You come to programming language design by way of
philosophy. How exactly did that come about? Or are these
activities unrelated? *

**MvT**: The relation is mainly historical, and
certainly not logical. My first fifteen year period in academia,
first as a student and later as staff, was a comedy(?) of errors.
I enrolled in Psychology and Philosophy because "I wanted to
know how the human mind works". But rats and stats in
Psychology and logic and scientific method in Philosophy quickly
changed my directions. In particular, I became interested in the
justification of induction, and I wrote my PhD in the field of
inductive logic and logical probability. After my appointment
here at La Trobe I had to catch up with deductive logic and have
been teaching it at various levels. I have also taught courses in
philosophy of science, philosophy of psychology, cybernetics, and
of course various bits in first year philosophy. In 1978 two of
us logicians started using the university's new DEC10 computer.
My colleague soon settled on Snobol, and I on Pascal. We had no
help at all, and at that time for me there was just the Pascal
User Manual and Report and Wirth's *Algorithms +
Datastructures = Programs*. I was particularly fascinated by
the miniature compiler for the PL0 language. Most of my Symbolic
Programming in Pascal, which I wrote over quite a number of
years, was influenced by Wirth. I have given courses at all
levels for the Computer Science Department.

**SA**: *All your programming in Pascal was
procedural. So how did you get into functional programming? How
did Joy evolve? *

**MvT**: In the early 1980's I came across the
famous Backus paper "Can programming be liberated from the
von Neumann style," and I was immediately intrigued by the
higher level of programming in his FP. From my deductive logic I
also knew about Quine's predicate functors and about Tarski's
cylindric algebras. Like Schoenfinkel's and Curry's combinatory
logic, Backus elimiminates not only assignable variables but also
formal parameters, and Quine eliminates variables of
quantification. I designed a strange little logic programming
language based on some of these ideas, and implemented it in
Prolog. It had some rather useless features - among others a
"Wheatstone bridge" combinator which takes five binary
relations to produce a new binary relation.

Joy then evolved from this in an entirely haphazard way: First I restricted the binary relations to unary functions, and this of of course was a dramatic change. Second, to allow the usual arithmetic operations with their two arguments, I needed a place from which the arguments were to come and where the result was to be put - and the obvious place was a stack with a few shuffling combinators, originally the four inspired by Quine. Third, it became obvious that all these combinators could be replaced by unary functions, with only function composition remaining. Finally the very different distinctively Joy combinators emerged, which take one or more quoted programs from the stack and execute them in a specific way. Along the way of course, lists had already been seen as just special cases of quoted programs. This meant that programs could be constructed using list operations and then passed on to a Joy combinator.

**SA**: *So Joy emerged after a tortuous
history. But by now it is quite stable. How would you describe
its main features? *

**MvT**: The language Joy is a purely functional
programming language. Whereas all other functional programming
languages are based on the application of functions to arguments,
Joy is based on the composition of functions. All such functions
take just a stack as argument and produce a stack as value, but
there are a few which additionally take files and the file system
as argument and value. Because of the stack, much of Joy looks
like ordinary postfix notation. However, in Joy a function can
consume any number of parameters from the stack and leave any
number of results on the stack. Moreover, there are some stack
functions which shuffle the top few elements of the stack around.
So, although for example the program 2 3 + is an arithmetical
expression in postfix notation and also in Joy notation (leaving
5 on the stack), the Joy program 5 dup * (leaving 25) is not
arithmetic because dup is neither a number nor an arithmetic
operator. That is why I say that much of Joy "looks like
postfix". In reality this is what Billy Tanksley so
appropriately called "concatenative notation". The
semantics of this notation is summed up by: "The
concatenation of appropriate programs denotes the composition of
the functions which the programs denote". In such languages
the application operation of the lambda calculus is uniformly
replaced by composition.

What distinguishes Joy from (the functional subsets of) Forth and Postscript is the datatype of quoted programs. Many Joy functions expect quoted programs on top of the stack and execute them in different ways, effectively by dequoting. This is similar to Lisp's eval, but in Joy there are many of them, each performing the job of higher order functions. But whereas in other languages the higher order functions take abstractions as arguments, the combinators of Joy take quoted programs from the stack.

As a result, there are no named formal parameters, no substitution of actual for formal parameters, and no environment of name-value pairs. Consequently Joy has an exceptionally simple algebra, and its programs are easily manipulated by hand and by other programs. Many programs first construct another program which is then executed by one of the combinators.

**SA**: *In Joy, a primitive like + operates
on the stack. Should we think of this operation as replacing the
top two elements x y with their sum x+y, or as two successive
operations: first replace y with the unary function _+y and then
replace x with x+y? *

**MvT**: You spoke of "replacing" and
"and then", which are imperative or procedural notions
and hence have no place in a purely functional language. So the
official answer has to be: the program 2 3 + denotes the
composition of three functions, and the program 5 denotes one
function and it is identical with the composition of the other
three. How the addition is performed internally is a different
matter, it might be by pattern matching, or by two push
operations followed by an add (the obvious stack implementation),
or any other (invisible) method that gives the right result.

But you also said "Should we think...", and that requires a different answer. Indeed imperative or procedural thinking can be very useful for Joy, both for explaining the meaning of the Joy primitives and also when writing programs. Here one should be eclectic and pragmatic - use whatever works. I would tend to use your first mode of thinking, and only sometimes the second. Two other modes would use message passing: a) send the parameterless addition message to the pair 2 3, or b) send the addition message with parameter 3 to the number 2. Maybe Forth programmers know more about the psychology of stack programming.

**SA**: *You mention the combinators of Joy.
What exactly is a combinator, and how do those of Joy differ from
the combinators of Schonfinkel and Curry? *

**MvT**: Combinators are second (or even higher)
order functions which take first (or higher) order functions as
parameters. They may return another function or instead
immediately apply that function to some argument(s). When we say
"John loves Mary and conversely", this might be
analysed as "(loves AND CONVERSE(loves)) (John, Mary)".
Here CONVERSE is a unary combinator (corresponding to the passive
transform "John is loved by Mary"), and AND is a binary
combinator. Similarly, "Bob admires himself" might be
analysed as "SELF(admires) (Bob)", where SELF
transforms the binary admires predicate into a unary one. These
combinators are not restricted to predicates (functions which
yield a truth value). For example, the unary squaring function
might be defined with the binary multiplication function by SELF(*).
In Schonfinkel's and Curry's system combinators similar to these
serve to shuffle arguments of functions around, a job which in
the lambda calculus is done by variables.

**SA**: *K programmers should understand this.
We would define SELF as a function which takes a binary function
f and returns a unary function which applies f[x;x]:*

SELF:{[f]{f[x;x]}} g:SELF[*] g[3] 9

**MvT**: If a parenthesis free notation such as
postfix is used, then there are two possibilities: either use
SELF as a higher order function as before, or work on a stack,
using a stack function dup:

5 SELF(*) 5 dup *

Joy, like Forth uses the latter. Note that dup is not a second order function at all. The same two possibilities would arise for prefix notation. In the same way the effect of CONVERSE can be achieved by a stack function swap. All the functions involved now are strictly speaking unary functions from stacks to stacks. Even multiplication is unary, although one can of course continue to think mainly in terms of how many parameters a function expects on the stack.

**SA**: *Yes, I think a similar choice exists
for K. We can define 'sqr' as either SELF[*] or as the unary
function*

sqr:*. 2#

*which makes two copies of its argument, and then applies *
"dot-wise", mapping the first copy to *'s first
argument, and the second copy to *'s second argument. *

**MvT**: But there are combinators which do not
simply shuffle arguments around. One of these is the mapping
function which applies a function to all members of a list to
produce a list of results. In a fantasy notation:

MAP(SELF(*)) ([1 2 3 4]) = [1 4 9 16]

Or in postfix and in concatenative Joy notation:

[1 2 3 4] MAP(SELF(*)) [1 2 3 4] [dup *] map

Whereas MAP above is a second order function, Joy's map is just an ordinary unary first order function from stacks to stacks - it expects a list and what in Joy is called a quoted program on top of the stack, and it returns a stack with a single list on top, the list [1 4 9 16].

**SA**: *This is where Joy and K diverge. For
us, 'each' really is second-order: it takes a function and
returns a function which applies to each element of a list. We
are taught to understand*

sqr'2 3 4

*as having the structure*

(sqr')2 3 4

*Apply 'each' to 'sqr', and apply the resulting function to
2 3 4. It is even more obvious in classical APL, where functions
such as 'sqr' are not first class. You can operate on a function
only by feeding it as on operatand to one of a handful of "operators",
such as /, and then immediately applying the resulting function
to data. In K, +/ is a first class function, which can be
assigned and passed into other functions as an argument. *

**MvT**: Joy has a large number of such
combinators which are really first order functions that do the
work of second order functions because they expect one or more
quoted programs on top of the stack. Consider the conditional IF-Then-Else
combinator, where the if-part produces a truth value and the then-part
and the else-part are again functions (and not statements).

IFTE(ifpart,then-part,else-part)

In Joy there is a combinator ifte with the most common syntax

[if-part] [then-part] [else-part] ifte

which expects three quoted programs on top of the stack. But actually quoted programs which map and ifte expect on top of the stack do not have to be pushed just before the combinator - they can be the result of stack shuffling or construction. Similar to ifte is a combinator linrec for linear recursion which can eliminate the need for many recursive definitions that would otherwise clutter up the symbol table and the programmer's mind:

[if-part] [then-part] [rec1-part] [rec2-part] linrec

The implicit recursion occurs between the [rec1-part] and the [rec2-part] quoted programs. There is a similar combinator for binary (tree-) recursion that makes quicksort a one-liner:

[small] [] [uncons [>] split] [swapd cons concat] binrec

**SA**: *This seems quite powerful! Over the
years, APL developers have experimented with a variety of
recursion operators, hoping that, just as the classical adverbs
such as 'reduction', 'scan', and 'each' enabled us to factor out
explicit loops, so the new operators would help eliminate at
least some explicit recursion. For example, in K, we can define a
function 'apply_to_atoms' which takes a monadic function f and
returns a g which, applied to a list, recurses to the atoms and
applies f:*

apply_to_atoms:{[f]{:[@x;f x;_f'x]}} f:2*!: g:apply_to_atoms f A:(1 2;(3 2 4;(5 6))) A (1 2 (3 2 4 5 6)) g A ((,0 0 2) ((0 2 4 0 2 0 2 4 6) (0 2 4 6 8 0 2 4 6 8 10)))

*But it's never been clear what the "best" set of
K-recursors might be, partly because K functions can take any
number of arguments, and partly because recursion can involve
more than one function.*

*To what extent to do you think the recursive combinators
of Joy will replace explicit recursion? APLers are familiar with
the fact that it often takes time and one or two "aha's"
before a problem breaks apart into an "array" solution,
a program without loops and counters. And some problems are
stubbornly, perhaps essentially loopy. It seems to me that a
certain way of thinking needs to be acquired, analogous to "array
thinking" in APL, which would let the programmer factor out
the recursion pattern of problem such as quicksort. I'm thinking
here of the way the nested recursion combinator arose as you
contemplated Ackermann's function, which most programmers would
have said required explicit recursion. *

**MvT**: Yes, the recursion combinators are very
powerful indeed. To have just one linear recursion combinator
seems only possible in a language in which all functions have the
same arity (like in Joy, where all are unary). I do not have a
proof for this claim, except that I have not been able to define
one for Lisp or Scheme, and if it were possible it would surely
be in the literature. Maybe it can be done with clever macros.
The same is true for tail recusion as a special case of linear
recursion, and also for binary and nested recursion.

But probably it is not true that all recursion patterns can be captured by a small fixed menu of recursion combinators, especially the mutual recursion patterns. As an example, one might look at the intricate and highly specialised mutual recursion that occurs in the definition of the Lisp functions eval and apply. For those cases ordinary explicit recursive definitions seem unavoidable. On the other hand, I would estimate that at least 50% of recursions in Joy can be handled by the list combinators map, filter and fold, of the remainder at least 50% can be handled by the more general linear recursion combinator. What is left can often be handled by the binary and nested recursion combinators, and finally a small percentage does need explicit recursion.

As far as programming practice is concerned though, I have to confess that earlier on I sometimes caught myself first thinking recursively and only later using a combinator to remove the recursion. It does not happen much nowadays, the combinators do become second nature.

**SA**: *In APL we are used to thinking of
programs as special datatypes, distinct from lists, arrays, and
quotations. But in Joy, lists and programs are the same datatype.
*

[10 20 30]

*is a list with three elements, but it is also an example
of a Joy program. Can you spend a moment explaining how this
works? *

**MvT**: If you ask primary school children to do
the sum: "5 + 0 - 0 + 0" they will be perplexed and
find it hard. Indeed, some problems are difficult because they
really are so easy. In Joy, as in Lisp and some other list
processing languages, lists can be heterogeneous, the elements
can be of all sorts of types. So this is a perfectly acceptable
list:

[11 22 true London Peter Santa-Claus foo dup *]

This list might have been the result of concatenating three lists:

[11 22 true] [London Peter Santa-Claus foo] [dup *]

The first list would normally be described as containing two numbers and a truth value, because that is the ordinary meaning of the symbols. Now consider the second list - are its members a city, two persons ..? No, sorry, there is no Santa-Claus, just having a symbol or name does not create a thing to which the name refers. What about foo ? It is a standard symbol for nothing in particular. Finally in the third short list, what does it contain? two symbols or the two functions which they normally stand for? If the latter, then with an appropriate definition even foo from the other list might stand for something. So, it is not at all easy to say what a list really is. But it is straightforward to understand concatenation of lists.

Much the same with all the other operations on lists: taking its first members, deleting its first member, sticking something on the stack in front of a list, writing out a list or any of its members. But the stack is as problematic as any other list: what is the result of taking the first element of [11 22] or of [London Peter] or of [Santa-Claus foo] or of [dup *]? Taking the first of a list leaves something on the stack, but what is it? the number 11, the city London (too big!), Santa-Claus (sorry), the duplication function? I think that we have to say that strictly speaking all lists and all stacks just contain representations of something that may or may not refer to something in reality.

In Joy, as you remarked, some lists like [11 22 true] can be executed by a combinator, and this one in particular results in three things being pushed onto the stack. Another that can be executed is [dup *], and, as we say, "it expects a number on the stack and replaces it by its square". But in our pedantic mode we should rephrase that.

In describing Joy I have used the term quotation to describe all of the above, because I needed a word to describe the arguments to combinators which fulfill the same role in Joy as lambda abstractions (with variables) fulfill in the more familiar functional languages. I use the term list for those quotations whose members are what I call literals: numbers, characters, truth values, sets, strings and other quotations. All these I call literals because their occurrence in code results in them being pushed onto the stack. But I also call [London Paris] a list. So, [dup *] is a quotation but not a list.

**SA**: *It's
interesting how K and Joy partition these concepts in different
ways. In K, strings can be used to quote code: *

"2+3"

*As you would expect, it doesn't
evaluate unless you apply "eval": *

."2+3" 5

*But a list evaluates immediately, so
one can use K expressions to build lists "from within".
For example *

(!5;!3)

*builds a list whose first item is 0
1 2 3 4 and whose second item is 0 1 2. But in Joy, supposing
that we had the program *

3 enum [0 1 2]

*we couldn't use it in the following
context:*

[5 enum 3 enum]

*since this is a program. Instead, we
would construct the list out of its parts:*

5 enum 3 enum unit cons

*Of course, as you pointed out
earlier, it is this very feature which allows the Joy programmer
to construct programs out of simpler components. *

**MvT**: You want the infra combinator, I think.
It expects a list and above that a quotation. It then treats the
list as a temporary stack and executes the quotation on that.
More often than not the list that is supplied is actually an
empty list. Example:

[] [2 3 + 4 5 *] infra [5 20]

Now if enum is already implemented as you described, producing a list, and if [5 enum 3 enum] is already on top of the stack, then all you need is just [] swap infra, which will leave [[0 1 2 3 4] [0 1 2]] on the stack. Of course if you want the two sublists concatenated, then you do an extra [concat] infra first, or in this case simply flatten.

**SA**: *Programming in Joy over the last few
years, I've come to think of the operators as falling into two
classes: those which produce new information from data, such as +
and cons, and those which move items on the stack into position
where the informational operators can do their work, such as swap
and dup. Languages with variables appear to have a productivity
advantage here, since one can simply invoke data by name. Billy
Tanksley has proposed closing the gap with something he calls
"shuffle notation", where "before" and "after"
stack patterns are specified. For example, if the stack is *

.. 10 20 30

*and you want: *

.. 20 20 30 10 10

*then you could say: *

"abc-bbcaa" shuffle

*which would have the same effect as: *

rolldown [dupd] dip dup

*What's your take on this and similar efforts to deal with
the problem of "stack noise"? *

**MvT**: Indeed, conventional languages with
named formal parameters in definitions of functions can simply
use the name to pick up the value of the corresponding actual
parameter. For functions with many parameters this is indeed an
advantage. But these languages need to carry around an
environment of name-value pairs. Joy tries to avoid the latter
completely, but pays a price when there are many parameters. One
possibility would be to do what Forth does: when appropriate
allow named formal parameters. An interesting alternative is
Billy Tanksley's solution or some syntactic variant of that. It
does not introduce formal parameters to be used in the body of a
function, and also it need not be used just at the beginning of a
definition. So it deserves very careful attention.

The proposal in effect defines an infinity of possible stack shuffling operators. Currently Joy has 12 inbuilt stack shuffling operators, a few others defined in the standard library and other, deeper shufflings can be expressed using the dip combinator. Two possiblities arise: 1) replace all the current Joy mechanisms by the new shuffle operator, or 2) allow both, and leave it up to the programmer to select what fits best. To make any decision one would want to see some programs expressed in the old and in the new notations. I have not done any experiments along these lines.

One other consideration concerns efficiency. The shuffle operator (or any syntactic variant) requires a before-after after string to be examined - and that means interpreting its pattern. A simple minded implementation would be slow. An only slightly more sophisticated one would look for common patterns, and replace for example "a-aa" shuffle by dup. It would use the interpreted form only in the less common but tricky cases, like your example. On the other hand, this decision might well be left to the programmer. So, my answer is not very definite at all, sorry.

**SA**: *It might be
interesting to explore algorithms which translate shuffle
notation into a fixed vocabulary of stack-shuffling words. Are
there small bases for which efficient algorithms exist? What if
we allow the stack diagrams to express structural
transformations, e.g.: *

[ab]c -- [ac][bc]

*I imagine that Brent Kerby would
have opinions on this matter (and quite possibly an algorithm or
two!) *

**MvT**: Yes, Brent Kirby has done very
interesting work on a combinatory algebra for concatenative
languages, see his paper from the main page of Joy. For Joy
itself the following seems to be an adequate base for shuffling
the stack: the three simple operators swap dup and pop, together
with the combinator dip. (This combinator expects a quotation on
top of the stack and below that another value. It pops the two,
saving the value somewhere, executes the quotation, and then
restores the saved value on top. So, for example, [swap] dip will
interchange the second and third element on the stack.) But I do
not have a proof that these four primitives are indeed complete
in the sense required.

However, if the transformations also take apart lists on the left of the transformation pattern, or construct lists on the right of the transformation pattern, then the list operations will be needed. In fact it helps to think of your transformation [ab]c -- [ac][bc] to be composed of two transformations, firstly [ab]c -- abc and secondly abc -- [ac][bc]. Then the first has to take the list apart, and in general the list operators first and rest should be adequate for that, but uncons and unswons would also help. The second transformation has to construct two lists, and in general the list constructors [] (empty list) and cons should do, but swons might also be useful. Both kinds of component transformations would also need some of the four general primitives mentioned earlier. An actual implementation would presumably collapse the two component transformations back into your original.

I have not done any work on implementing this sort of thing for Joy. If I were to do so, I would look at the by now well understood implementations of pattern matching that are used in languages such as Prolog, Miranda and now in Haskell. An older book by Peyton-Jones describes this in detail. For a while I used to think that these transformations would re-introduce something like lambda variables into Joy, and that there is a problem of what the scope of the introduced variables would be. But I was wrong, the scope is just the right side of the transformation, so the variables cannot actually occur elsewhere in the Joy program. So if somebody wants to volunteer ...

**SA**: *I'm curious
about Joy's internals. For example, in APL and its descendants,
at least some of the bulk datatypes are implemented in
consecutive memory locations without any links, and for that
reason APL doesn't require garbage collection. I know that K uses
a reference-counting mechanism. Since the typical K application
uses a small number of large objects, this is quite efficient. So
what choices have you made for Joy, and for what reasons?*

**MvT**: Yes, the implementation of bulk
datatypes in consecutive memory locations is in many ways ideal
simply for efficiency reasons. I have often wondered what kind of
a cousin of Joy might be implemented like that without
sacrificing efficiency elsewhere. One worry of course concerns
adding a new first element to a very large array: it requires
copying the entire array. So, if this happens often, much
effiency is lost. But must it happen often? Presumably the APL
experience shows that it need not be a concern at all for a vast
number of applications.

Then there is the possibility of a mixed implementation: mostly consecutive, but some links. This may or may not require memory management in some way, either as mark-sweep, or copying, or reference counting. The last cannot handle circular structures, but that may or may not matter. At any rate there seem to be many possibilities for languages similar to APL, J and K but with a concatenative syntax to explore. You yourself, Stevan, have done some interesting work in this field with cK, a concatenative version of K. I look forward to seeing more of it, not the least because it would offer an implementation that is more efficient than the current Joy because of the way bulk datatypes are handled. At the same time, I see no reason why a more sophisticated implementation of Joy could not use the same method wherever possible.

This is perhaps the best place to mention Billy Tanksley's work, which is inspired by the consecutive memory implementation of the stack of the Forth language. Since in Joy the stack is a sequence just like lists and other quotations, there is a possibility of using consecutive memory locations wherever possible and using links only where necessary. So I think Billy's work is a step in this direction, and I welcome it.

But you also asked about the choices made in the implemention of Joy, and for their reasons. My background had been very much in logic and other symbolic processing, and the structures one needs there tend to be trees of some sort. So I have had rather little use for arrays in consecutive locations, except for implementing trees. I had used Prolog a fair bit, but Lisp I only studied in detail from a purely theoretical perspective. It was clear to me from the outset that a uniform linked implementation for Joy would be simultaneously simple and sufficiently general. Since Joy then had no assignments or other destructive updates, and hence no possibility of circular lists, memory management by reference counting was a possibility that I did consider quite carefully. In the end I decided against it, largely on the grounds that a problem would arise if I ever wanted to allow circular lists. I knew that the problem would not be insurmountable, but for a first implementation it looked like a lot of work. It so happens that Joy is still purely functional and hence has no destructive updates of any kind, so a simple reference counting memory management would still be possible. That would have the advantage of not requiring occasional hiccups for memory management and hence better suitablitity for real time work. On the other hand, it is known that reference counting is more CPU intensive, spreading the total work more continuously. Whether Joy will remain purely functional for ever (look what they did to the original Lisp), I do not know at this stage.

**SA**: *What is the current status of Joy?
What are the plans for the future development?*

**MvT** After several proof-of-concept
implementations, the current implementation, written in unadorned
C, evolved smoothly from one that was started 1995. In early 2001
John Cowan added files, floating point numbers and access to
standard C functions, and he did a lot of cleaning up. He also
added the option of not using my original garbage collector but
using the professional BDW collector, an improvement which
allowed space used for strings to be reused. This extended the
functionality of Joy tremendously, and I a very grateful for all
the work he did. Since then Nick Forde has also added a number of
features, and I thank him for that.

The current implementation is essentially an interpreter. It translates (compiles) the external ASCII form of programs into internal tree code which is then interpreted in a rather conventional manner. No attempt is made to do any optimisation, and my earlier "clever tricks" I always came to regret fairly soon because they interfered with my garbage collector. There is a growing list of general and special purpose libraries, ranging over many kinds of possible programming applications, and most of my work in the last few years has been on those. For the immediate future I plan to examine and test the so far rather underutilised module system, by writing libraries for some specialised types such as big sets, trees and dictionaries of arbitrary basetypes.

Several other people have published other more or less complete Joy interpreters, written in ML and in Scheme, in the "concatenative" mailing group. At this point in time I have no plans to write a full compiler. A first version of such a compiler would presumably use C as an intermediate language and leave the generation of machine code to the C compiler. I would very much welcome if somebody were to take up the task.

12 December 2003