w == [dup] dip
Then the square of 3 is also computed in Joy by
3 [*] w
In both languages one can introduce a mapping combinator to apply
a function to a list.
In the examples to follow the list will be just [1 2 3 4].
In combinatory logic one might define a Map combinator by
Map f [] = []
Map f [X | Xs} = [f X | Map f Xs]
where the bar | separates the first element of the list
from the rest.
Then the list of squares of the given list is computed by
Map (W *) [1 2 3 4]
Note that the parentheses around (X *) are necessary.
The same computation is expressed in Joy by
[1 2 3 4] [[*] w] map
Superficially one version is just the reverse of the other.
Combinatory logic uses prefix notation,
and Joy uses what looks like postfix notation.
But the apparent similarity is deceptive.
To see this it will help to write both versions with the hidden
operators made explicit.
In combinatory logic the hidden binary operator is application
of a function to an argument,
which might be written explicitly as infix "@".
Fully parenthesised the combinatory version thus is
(Map @ (W @ *)) @ [1 2 3 4]
In Joy the hidden binary operator is composition
of functions,
which might be written explicitly as infix ".".
The Joy version thus is
[1 2 3 4] . [[*] . w] . map
There are as many compositions in the Joy version as there are
applications in the combinatory logic version.
Since composition is associative, it does not matter how the
expression is parenthesised.
Because of associativity the following is also meaningful in Joy:
[1 2 3 4] . [[*] . w]
It denotes a function which pushes two items,
a list and a quotation, onto the stack.
By contrast its combinatory counterpart
(W @ *) @ [1 2 3 4]
is not meaningful.
This is because the squaring function on the left,
(W @ *),
expects to be applied to a number on the right,
and not a list.
Another way of noting the difference between combinatory logic and Joy is in the following equations, here again with application and composition left implicit:
Map (W *) [1 2 3 4] = [1 4 9 16]
[1 2 3 4] [[*] w] map == [1 4 9 16]
The combinatory logic version denotes the identity of objects,
in this case lists.
The Joy version denotes the identity of functions,
in this case functions which,
when applied to a stack, will push a list.
Stacks are the arguments to which all Joy functions are applied,
but this application plays no role in the construction of programs.
By contrast, application is the principal program constructor
in combinatory logic,
even if the application operator is left implicit.
Wald (1993)
develops a theory of 'unary pairfunctions'
with primitives L, S, D and B
satisfying
L(<a,b>) = a S(<a,b>) = <b,a>
D(a) = <a,a> B(<a,<b,c>>) = <<a,b>,c>
He gives a finite presentation (69 axioms)
of a semigroup of such functions under composition.
The theory is not intended as the basis of an implementation,
but it would appear that there are some connections
with Joy that are worth exploring.
Backus' FP systems
In his Turing award lecture Backus (1978) introduced his FP system, short for "Functional Programming system". The system is not about programming using functions, as Lisp and its descendents are, but about programming with functionals, also known as higher order functions or combinators or, in his terminology, functional forms.
Backus builds his FP systems on three kinds of entities. Firstly, there are objects. These are built recursively from atomic objects such as truth values and numbers, and the only constructor is that of forming sequences or lists of objects. Secondly there are primitive functions. These comprise the usual arithmetic operations and relations and several powerful operations on lists. Importantly all primitive functions are unary functions technically, since functions requiring several arguments are provided with a single list of these arguments. Furthermore, all functions are first order. Thirdly there are functional forms, and these are the essential novelty of the system. They are second order functions used to build more complex functions from simpler ones. Since all primitive functions are unary, and the combining forms preserve this property, all functions in the system are unary. Combining forms, however, can have several functions as parameters. In detail, the combining forms are as follows.
The composition form requires two functions.
The resulting functions is that function which applied
to its argument always gives the same value
as applying first the one function and then the other.
The conditional form takes three functions as parameters,
an if-function, a then-function and an else-function.
The if-function is applied to the argument,
if that yields true the the value returned is that
given by applying the then-function,
otherwise it is that of applying the else-function.
The construction form takes as single parameter
a list of functions.
Applied to one argument the resulting function
returns a list of values,
each obtained by applying the functions to the argument.
The apply-to-all form
is essentially the same as
The combining forms as operations on unary functions
constitute a rich but unfamiliar algebra.
Importantly, the arguments of the functions
do not play any role at all.
Backus gives an elaborate axiomatisation of the algebra;
in Williams (1982) a smaller version is given
comprising just 11 axioms.
Two axioms deal with the interplay between composition and conditional,
two deal with composition, construction and insert,
and one deals with just composition and construction.
Two deal with construction and indexing into a list.
Another concerns nested conditionals with the same if-function.
Two deal with the append-left function
(elsewhere known as cons)
and the apply-to-all form.
A final one deals with composition and constant.
As may be seen, each combining form
has a significant relationship
with at least some other combining form.
The FP system is further explained and expanded in
Williams (1982) .
A very useful exposition to the FP systems is found in
Henson (1987 Chapter 5) .
The book also gives a very extensive bibliography.
For a good exposition to the
relation between the lambda calculus, combinatory logic
and the FP systems of Backus see
Revesz (1988 section 5.3) .
Givler and Kieburtz (1984)
present methods for automatically and reliably
transforming clear and correct
but possibly inefficient FP programs
into possibly obscure but efficient equivalent programs.
Bellegarde (1984)
presents a set of convergent rewriting rules
for the algebra of FP programs but without conditionals.
Whereas FP is a strict language,
Dosch and M\"{o}ller (1984)
describe the algebraic semantics of a lenient variant of FP
allowing infinite objects
and using both busy and lazy evaluation.
Sheeran (1984)
uses a variant of FP as a VLSI design language
for describing semantics and physical layout of hardware.
For a critique of the FP systems, see
Harland (1984 section 18.4) .
A recent descendant of the FP system by Backus
is the FL language described in
Backus, Williams and Wimmers (1990)
Another variant is the language GRAAL
which implements ("infinite") streams
using call-by-need;
it is described in
Bellot and Robinet (1985) .
In FP there are three kinds of semantic entities,
the objects, the functions and the combining forms.
They correspond fairly well to three kinds of functions in Joy:
those denoted by literals,
by operators and by combinators.
But the Joy functions are all of the same kind,
they are functions taking one stack as argument
and giving a new stack as value.
In FP combining forms are applied to functions
and the resulting functions are applied to objects.
In Joy there is no application of functions to arguments at all,
there is just composition of functions.
In FP the function parameters of combining forms cannot depend
on any objects supplied
as arguments to functions.
In Joy the quotation parameters of combinators
can be manipulated at run time.
Hence it is possible to call constructed programs
which have been built on the fly.
In his Turing award lecture Backus also introduces another language,
FFP system, short for "Formal Functional Programming system".
In addition to objects as in FP there are now explicit expressions.
In addition to the listforming constructor as in FP
there is now a new binary constructor to form applications
consisting of an operator and an operand.
Operator expressions which are atoms of course denote functions
which can be applied to an argument.
Operator expressions which are lists must have as their first
element an expression denoting a function.
When such an expression is applied to an argument,
the function is applied to a pair consisting
of the original list and the argument.
This last rule, metacomposition, is immensely powerful.
It can be used to define arbitrary new functional forms,
including of course the fixed forms from FP.
The rule also makes it possible to compute recursive functions
without a recursive definition.
This is because in the application
the functions is applied to a pair which includes the original
list operand which in turn contains as its first element
the expression denoting the very same function.
The method is considerably simpler than the
use of the Y combinator.
Williams (1982)
extends the method to mutually recursive functions,
even ones that are not primitive recursive.
Joy is in fact closer to FFP than any of the languages mentioned
so far.
Both replace abstraction by other mechanisms,
both rely heavily on higher order functions,
and both obey the principle that program = data.
Both permit construction of first order
and higher order recursive and non-recursive functions
without ever using named formal parameters.
An effect similar to metacomposition
is achieved in Joy with the
One important difference is that FFP still uses application
as an essential operation,
whereas Joy uses composition.
It appears that this makes the algebra of Joy considerably simpler.
Meertens (1989 p 72)
speaks of
"the need of a suitable system of combinators
for making functions out of component functions
without introducing extra names in the process.
Composition should be the major method, and not application."
Meertens (1989 p 71) writes
"The basic problem is that the basic operation of the classical combinator
calculus (and also of the closely related lambda calculus)
is application instead of composition.
Application has not a single property.
Function composition is associative
and has an identity element
(if one believes in the 'generic' identity function)."
He develops a system of combining functions
that is more suitable to formal manipulation
than the classical combinators.
It is worth noting that in monads
the monadic composition operator is associative.
A category consists of a collection of objects
and for any two objects a collection of morphisms,
each having the one object as their source
and the other object as their target.
For any single object, the morphisms must include an
identity morphism with that single object
as source and target.
For any object and two morphisms having it as source and target
respectively, there must be a composite morphism
having as source the source of one morphism and as target
the target of the other.
This composition of morphisms must be associative,
with identity morphisms as left and right unit elements.
An object is a terminal object in a category
if for each object as source there is exactly one
morphism with that object as target.
An object is a product object
of two given objects
if there are two special projection morphisms
having the product as source.
For any arbitrary morphism having an arbitrary object as source
and either of the two given objects as target
there must be a corresponding morphism
having the same arbitrary object as source
and the product object as target.
That arbitrary morphism must then be the composition
of that corresponding morphism and the appropriate
projection morphism.
In a category with products there may also be exponential objects
of a given source object and a given target object.
Such an exponential object must have a special evaluation morphism
having the product of the given source object
and the exponential object as source
and the given target object as target.
For any arbitrary morphism
having the product of the source object and an arbitrary object
as source there must be exactly one corresponding ("curried")
morphism.
That arbitrary morphism must then be (essentially)
the composition of the corresponding morphism
and the evaluation morphism.
A Cartesian closed category
is one which has a terminal object,
and for any two objects their product and exponential,
together with their projection and evaluation morphisms.
In the category of sets,
products are Cartesian products,
exponentials are functions from sets to sets,
and evaluation morphisms are the application
of a function to a value.
In the category of logical systems,
products are conjunctions,
exponentials are conditionals,
projections are and-elimination rules
and evaluation morphisms are the modus ponens rule.
The language of categories is another functional language.
If it has products,
then it can deal with functions of several variables.
If it has exponentials,
then functions are "first class citizens".
The language is therefore an alternative
to the (typed) lambda calculus and to combinatory logic.
Whereas the lambda calculus needs variables,
the combinatory language and the categorical language do not.
Cartesian closed categories are explained for example in
Barr and Wells (1990 Chapter 6)
and in
Poigne (1992) .
Barr and Wells give an example of a simple lambda expression
with variables and a complicated looking categorical equivalent formula.
They suggest an acceptable reformulation of the categorical formula.
Both categorical versions
essentially replace occurrences of variables by
use of projection functions.
Could the language of categories be used for writing programs?
Any lambda expression can be translated into a categorical expression,
so the language of categories is expressively complete.
But this does not make it a suitable language for writing
programs.
As it stands it is a very low-level language.
On the other hand,
category theory has given rise to another model of computation:
the CAM or Categorical Abstract Machine,
described in
Cousineau et al (1985) ,
Cousineau et al (1987)
and in
Curien (1986) .
The machine language of the CAM is very elegant,
but programs in that language
look as inscrutable as low level programs in other
machine languages.
The language is of course suitable as the target language
for compilation from any functional language.
A very compact but comprehensive exposition
of a compiler from (a mini-) ML to CAM is described in
Clement et al (1986) .
Mauny and Su\'{a}rez (1986)
describe compilers from a strict and a nonstrict
version of ML
to an eager and a lazy version of the CAM.
The original translation from lambda expressions
to categorical combinators was quadratic in the worst case, but
Lins (1987)
introduces a linear translation to a simplified abstract machine code.
Hannan (1991)
uses a variant of the CAM for generating more concrete
code suitable for register-level implementation
or even micro-coding on conventional architectures.
An extension of ML for data-parallel computation has been implemented by
Hains and Foisy (1993)
to run on a distributed version of the CAM.
Combinatory languages should be seen as abstract machine languages.
In contrast, Joy was designed to be a high level language
to be used by the human programmer.
In all high level languages a program consists of a possibly
large collection of definitions and a comparatively small
main program.
The collection of definitions and their interrelations
can become very difficult to comprehend and maintain.
Many languages provide some mechanisms
for giving additional structure to the definitions
of functions and their interrelations.
One kind of interrelation is due to their mutual calling patterns.
The main program calls functions at level one,
and these call each other or functions at level two,
and so on.
A second structure that can be exploited is that due to
common types.
For example, functions which concatenate two strings
and reverse a string will not call each other
but belong together in an implementation of strings.
A third possible device only makes sense in imperative languages
because procedures have additional interrelations
due to global assignable variables
which might be written by one procedure and read by another.
One of the simplest but very powerful structuring mechanisms
is block structure.
It was already used in the earliest Lisp and in Algol 60,
and later in Pascal.
It has been retained almost all their descendants.
A block consists of any number of definitions followed by a body,
and a definition consists of a header and a block.
So definitions can contain local definitions and so on,
with no intrinsic limit to the levels of nesting.
Hence any definition can at least provide some
hiding of information
that is not needed outside.
This hiding could be used even in cases where what is defined
does not take any parameters at all.
(Thus it could be used in context-free grammars,
but apparently never is.)
More importantly, if there are parameters
in the header of a definition,
then the bodies of any enclosed definition can access those parameters.
Additionally, for an imperative language,
if there are assignable variables in a block,
then the bodies of any enclosed block can access these variables.
Access to non-local parameters and variables is automatic
via a static chain or a display.
This mechanism achieves what otherwise would have to be handled by
explicitly passing them as parameters.
Joy currently does not have block structure,
but it would be easy to implement.
Since Joy does not have formal parameters and no assignable
variables, block structure would only provide the benefit
of information hiding.
The popular imperative C language does not have block structure
but it does address the problem of hiding information about
assignable variables from function bodies that do not need this
information.
One such mechanism is that of own variables,
or internal static variables in C-terminology.
Such a variable can be declared, initialised and used within a single
function body and not be visible outside.
The value of the variable persists between successive calls
of the function.
The other mechanism is that of independent compilation units.
These are just files containing declarations of global variables
and functions without a main program.
The variables can be made invisible from outside their unit.
A complete program then consists of very few variables
visible everywhere,
and several files each containing a collection of variables
and procedures that belong together.
In Joy the first mechanism does not even make sense
because Joy as a functional language does not have any assignable
variables.
The second mechanism could still allow related functions to be kept
together in one file.
The current implementation of Joy does not use a single input file
but a stack of such files.
A new file can be opened and become the current input file
by an
Independent compilation units in files are not without problems.
One criticism is that in order to achieve independence,
programs have to be spread over too many files.
Another concerns security,
since a simple compiler does not check type conformity of
formal parameters in the declarations of in one unit
and the actual parameters in the calls of another unit.
A third criticism is that such units cannot be nested.
The language Modula2 overcomes these problems.
A collection of declarations and definitions can be
wrapped up inside a module.
A single file can contain several modules.
In addition to a detailed implementation module
there is a short definition module containing
only type information, especially about formal parameters.
This interface is used to check type conformity with calls
from another module.
Finally, modules can be nested.
A module specifies explicitly which of its identifiers
are to be exported and made visible to the outside.
Any others remain hidden.
But the total number of identifiers exported from various
modules in a program can still be very large.
Moreover, if different modules were written by different
programmers, the exported identifiers might clash.
To avoid this problem,
Modula2 allows use of qualified names which are similar to record
notation.
Such names consist of the name of the module together with
the name of the exported identifier.
Structuring devices similar to modules would benefit any language
for programming in the large.
Because Joy is so weakly typed,
definition modules would be almost pointless.
However, implementation modules with selective export would hide
utility functions of a module that are not needed outside the module.
Qualified names would then be as in Modula2.
A crude substitute for a hiding facility and for qualified names
is already used in the Joy libraries.
Hidden functions are given names that are not displayed by the
Since Joy does not have any assignable variables,
the notion of class and objects are not applicable.
However, hiding, inheritance and polymorphism would still be
useful.
Many operators in Joy are already polymorphic,
and it is possible to write libraries
which retain or even extend this property.
One of the most sophisticated devices for structuring programs
is to be found in the language ML.
For a good introduction, see
Paulson (1992 Chapter 7)
and
Sokolowski (1991 Chapters 8 and 9) .
A signature is very much like an definition module
in Modula2,
it specifies parameter types and result types of functions,
but it does not specify their bodies.
A structure is like an implementation module,
it specifies the bodies of functors
but does not hide implementation details.
Real hiding and hence real abstraction is provided by functors,
inspired by category theory.
In their simplest form they simply hide implementation detail.
But they can also take one or more other structures
as formal parameters and produce other structures as value.
The bodies of functions can access all the functions in
the formal structure parameters.
Functors must be instantiated with actual structures
before they can be used,
and they can be instantiated several times with
different actual parameters.
Instantiation of functors thus resembles calling a function
with actual parameters,
but like the generics of Ada, it occurs at compile time.
However, the functors of ML are far more powerful than
the generics of Ada.
Functors are again structuring devices for programming in the large.
They could be used not just for functional languages
but equally well for procedural,
logical or actor languages.
A mathematically very mature treatment of modules
in terms of category theory is given in
Ehrig and Mahr (1990) .
Categorical combinators
Programming in the large