One of the simplest functional languages is the one we encountered in primary school, the language of arithmetical expressions. We learnt how to do evaluations such as the following:
(2 + 3) * (7 - 4) 5 * (7 - 4) 5 * 3 15Note that the evaluation steps in the second and third line could have been interchanged or even done in parallel. In contrast, in imperative languages it is not always possible to execute assignment statements in arbitrary order.
Expressions need not be numerical, subexpressions can be of different types, and the operations can be unary. In the following the only operand is a list of numbers, here writen inside square brackets.
(1) square( size( rest( [11 22 33] ) ) ) square( size( [22 33] ) ) square( 2 ) 4This will serve as the running example in most of the remaining sections.
(2 + 3) * (7 - 4)The whole expression, the two parenthesised subexpressions, the four single digit numerals and the final two digit end result - all of them denote numbers. The three symbols "+", "*" and "-" are infix operators which denote binary functions from two numbers to give a result number.
In the second example:
(1) square( size( rest( [11 22 33] ) ) )the symbol "[11 22 33]" denotes a list of three elements which happen to be numbers. The symbol "rest" denotes a unary function from lists to lists, the symbol "size" denotes a unary function from lists to numbers, and "square" denotes a unary function from numbers to numbers.
In both examples all lines of the evaluation denote the same number, the end results 15 and 4 respectively. Alternatively we say that all lines have the same value. So, single symbols denote all sorts of things, numbers, lists and various functions. Expressions always denote, or have, values.
Denotations and values are semantic notions, and so is evaluation, the end result of the process of finding the value. By that we mean finding an expression that does not contain function or operator symbols, but has the same value. Typically, though by no means always, the final expression is shorter than the original.
The actual evaluation process, however, is purely syntactic, it is just a matter of rewriting the given expression in accordance with certain rules. The rewriting rules are essentially derived from the semantics, but using the rules is a purely syntactic process. One can do it without knowing what the symbols mean, even without understanding the difference between a symbol and what it denotes. Most of us understood the difference between a numeral and a number only when we encountered notations to bases other than ten. (I am told that one textbook says that computers use hexadecimal numbers as addresses, which is nonsense.)
The difference between a symbol and what it denotes will become important in what follows. This is because in Joy many symbols look more or less familiar, but there is an important difference between what they denote conventionally and what they denote in Joy. One can learn to program in Joy barely noticing the difference, but there is a deep shift in denotation. Some people might speak of a "paradigm shift", but I would be reluctant to use the term here.
(2) square @ (size @ (rest @ [11 22 33]) ) square @ (size @ [22 33] ) square @ 2 4
Application is a second order function because one of its arguments, the one written on the left, is itself a function. The reason for hiding the explicit symbol "@" externally is that it just adds to the syntactic complexity. The reason for introducing application internaly will be explained in Section 4.
The best known applicative functional languages are:
(f . g) @ x == f @ (g @ x)Since the "f" and the "g" appear in the same order on the left side as in the applicative expression on the right, this is sometimes called "applictive order" notation for composition.
The functions in the running examples are all unary, so it can be written in two ways:
(square . (size . rest)) @ [11 22 33] ((square . size) . rest) @ [11 22 33]Function composition is in fact associative, and hence the two have the same value. So the running example might as well be written without the inner parentheses as
(3) (square . size . rest) @ [11 22 33]The change to function composition has eliminated the first two occurrences of "@" in (2) of the previous section.
Application is not associative, and apart from being a function it has no formal properties at all. Could the last application "@" also be eliminated and turned into composition? Clearly not, because "[11 22 33]" does not denote a unary function. Therefore it seems that functional languages need application.
(4) square . size . rest . [11 22 33]The entire composition would have to be applied to a suitable suppressed argument.
One suitable argument is a stack which is initially empty. Then "[11 22 33]" denotes not a list but a stack function which pushes a list. Similarly "square", "size" and "rest" would denote stack functions which replace the top element of the stack. The previous result, "4", denotes not a number but a stack function which pushes a number. Then all five symbols denote unary functions from stacks to stacks. What normally are binary operators "+" and "*" for addition and multiplication now also denote unary stack functions, they replace the top two elements of the stack by a single one. The idea is simple enough, and it is one of the key features of Joy.
An alternative for function composition would use a reverse notation. It is sometimes defined using an infix operator, say ";", instead of the previous ".":
(f ; g) @ x == g @ (f @ x)This is is known as "diagrammatic order" notation for composition. Then the running example would be written
(5) [11 22 33] ; rest ; size ; squareOne advantage of this notation is that the order in the notation reflects the order of the execution.
Any functional language which completely replaces application, by explicit or implicit "@", by composition, with explicit or implicit "." or ";", might be called a compositional functional language.
Here is an example: the squaring function can be mapped over the elements of a list [1 2 3] to yield the result [1 4 9]. In a compositional language one might write
[1 2 3] map squarewhere "map" is an infix operator just like ";". Now "[1 2 3]" and "square" denote unary stack functions, and the two are transformed by the higher order mapping function into another unary stack function, the one denoted by "[1 4 9]".
With two distinct infix operators ";" and "map", there arises the possibility of expressions containing both. Typically it will be necessary to use parentheses too, as in the following:
([1 2 3] ; rest) map square ([1 2 3] map square) ; restIt so happens that the two expressions denote the same function, the one denoted by "[4 9]".
Functional languages need the mapping function and several others, especially a conditional, or "if-then-else" of some kind. However, if a compositional language has no other function operator, then there is no point in ever writing the ";". The running example would now be written as
(6) [11 22 33] rest size squareNow the concatenation of any consecutive two or three or all four of the parts of (6) denote the composition of the stack functions tht the parts denote. This is a desirable consequence. But it must not come at the price of not being able to express other higher order functions such as the mapping function or the conditional or the many others that a mature language needs. The topic is resumed in section 10.
A language in which the concatenation of programs denote the composition of functions has been called a concatenative language. I first heard this terminology from Billy Tanksley.
2 3 + 4 7 - *with four number operands and three binary operators. Just as in the evaluation of the original infix expression, the addition and the subtraction could be done in any order, even simultaneously. Just as in the original infix expression, the whole expression, the two subexpressions, the four single digit numerals - all of them denote numbers.
The expression is also correct concatenative notation (though not in compositional languages that use ";"). So what is the difference? Consider some consecutive parts such as
+ 3 + + 4 3 + 4 7 - *These do not denote numbers, they are not postfix expressions. However, they are perfectly correct concatenative expressions, each denoting, as always, unary functions from stacks to stacks.
The difference between postfix notation and concatenative notation becomes even more obvious in the following. The square of a number is just the number multiplied with a duplicate of itself. Let "dup" denote a stack function which duplicates the top element of the stack. So the running example might be written as
(7) [11 22 33] rest size dup *The duplication operator only makes sense in compositional languages that use a stack (or perhaps something similar), and hence also in concatenative languages. Two others are for popping off the top element of the stack and for swapping the top two elements.
Postfix notation is used in some pocket calculators. Concatenative notation is used in Forth, Postscript and Joy. The unix utility dc (which similates a desk calculator) is often described as using postfix, but the presence of a duplication operator d actually makes it concatenative. The two other stack manipulators are easily defined in dc.
square(x) == x * xInternally, and possibly externally too, the definition would be
square == Lx : x * xwhere "Lx" is sometimes written "\x" or "lambda x" or "fun x". The expression on the right side of the definition then is to be read as "the function of one argument x which yields the value x * x". An expression like that is known as a lambda abstraction.
Such a definition would be used as in the evaluation
square @ 2 (Lx : x * x) @ 2 2 * 2 4In the second line "square" is being replaced by its definition. This sets up an environment in which x = 2, in which the formal parameter x has been given the value of the actual parameter 2. An environment is a collection of associations of formal and actual parameters. In all but the simplest cases the environment will contain several such associations. In the third line this environment is used to replace the formal parameter x by the actual parameter 2. All this is completely hidden from the user when the first style of definition is used.
The two operations of lambda abstraction and application are complementary. They form the heart of the lambda calculus which underlies all the mainstream functional languages.
square == Lx : x x * square == Ls : x dup *For a compostional (and hence for concatenative) language the right hand side has to be read as "the stack function for stacks in which there is a top element x and which for stacks without that top element yields the same result as x dup *". But one might also write without the explicit lambda abstraction as
x square == x x * x square == x dup *
In the last of these both sides start with the formal paramater x, and otherwise there are no further occurrences of x on either side. Would it be possible for the two occurrences on the left and right to "cancel out", so to speak? Yes indeed, and now the definition looks loke this:
square == dup *
The full evaluation of the running example now looks like this:
(8) [11 22 33] rest size square [22 33] size square 2 square 2 dup * 2 2 * 4Note how in line four the substitution of the right hand side of the definition is a simple textual substitution.
The mainstream imperative languages have a state of associations between assignable variables and their current values. The values are changed by assignments during the run of the program. These languages also have an environment of formal / actual parameter associations that are set up by calls of defined functions or procedures. Purely functional languages have no state, but at least the mainstream applicative functional languages invariably have an environment. Compositional functional languages and hence concatenative functional languages have no state and need no environment. The concatenative language Joy has neither.
[1 2 3] [square] map [1 2 3] [dup *] mapBoth lines are concatenations of three parts: (a) "[1 2 3]" which denotes a stack function to push a list, (b) "[square]" or "[dup *]" which denotes a stack function to push a "quoted" program without executing it, and (c) "map" which denotes a stack function to use the program from (b) on each member of the list from (a) to produce a list of the same size. Note that the second version was obtained from the first by simple textual substitution in accordance with the definition of "square".
The map function in Joy does all the work of a second order function, but actually it is a first order stack funnction like all others in Joy. It expects a stack whose top two elements are a list and a quoted program and it leaves behind a new list. The program is protected from execution by being enclosed in square brackets, and in this form it is called a quotation.
Because the mapping function is only first order, it is possible to write
[1 2 3] [ [dup *] [dup dup * *] ] [map] mapwhich leaves [ [1 4 9] [1 8 27] ] on top of the stack, and below that the original [1 2 3].
Another common word for higher order function is "combinator", but in Joy it is used for what are really first order functions. Apart from "map", Joy has a large number of combinators, and in programming they are used more often that in other languages.
Lists are passive data structures that can be manipulated for eample by the rest operation. There are quite a few other well known list manipulation operations for building up lists, combining lists, and for taking them apart.
Quotations are potentially active programs that can be passed as parameters to be eventually activated by combinators such as map. There are many other combinators in Joy. Some of them are similar to well known counterparts in other languages. But many of them are unique to Joy and do not make much sense elsewhere.
So, why use the same notation for lists and quotations? The reason is that fundamentally they really are the same.
On the one hand consider the program
[1 2 3] [4 5] mapThe first list is used as the passive data structure, and at the very least its size, 3, determines the size of the result list of the program. The second list is the quotation. When activated by the map combinator three times, it will ignore the three arguments 1 or 2 or 3, and in each case simply push 4 and 5 on top. Whatever is on top will be the element of the result list, and that is the same on all three occasions. So the result list is [5 5 5].
On the other hand, and more usefully, any list processing operation can be used on quotations. Consider
[1 2 3] [dup * dup *] mapwhich will compute the fourth powers of the elements of the list. Removing the first two parts of the quotation first,
[1 2 3] [dup * dup *] rest rest mapwill compute the second powers of the elements of the list.
Instead of taking a quotation apart, with the rest operation, a more likely scenario is that a quotation is first constructed, possibly in several steps, and then used by a combinator. Many Joy programs do just that.
The following two programs compute the same function:
[dup *] map [square] mapbecause the quotations compute the same function. At the same time, of course,
[dup *] size [square] sizegive different results, 2 and 1, because as lists they are different.
So it is useful to speak of lists as passive data structures and quotations as inactive programs that might be activated by a combinator.
Apart from what is in this FAQ, what else does Joy have?
How does one think about Joy programs? There are three useful styles:
Any questions?
Back to homepage for Manfred von Thun