Juxtaposition in Programming Languages

Juxtaposition is an interesting operator. I’m aware of no language in which this operator can be redefined by the user. I’m referring to simple placement of two tokens next to each other, such as “x y.”

In the vast majority of languages, this operation has no meaning at all. For example, in Python:

>>> 2 + 3
5
>>> 2 3
  File "<stdin>", line 1
    2 3
      ^
SyntaxError: invalid syntax

In a few languages, strings juxtaposed are conjoined. In C this is limited to string constants (a kind of constant folding optimization).

Juxtaposition has a great deal of importance in functional programming languages. One could even argue that the manner in which it is interpreted is the principal differentiator between the three primary families of FP language. Perhaps use of this operator adds significantly to the general sense of FP being difficult. If so, it would be an example of something completely invisible to the FP community blocking adoption.

For the sake of discussion, I’m going to define the three principal orders of functional programming as applicative, concatenative, and array.

Applicative FP

The applicative order is the best known of FP. It contains the Lisp and ML families. In these languages, juxtaposed values are applied to functions on their left. For example, in Scheme or Lisp:

(+ 1 2 3)
6

(* 2 2 (+ 0 3 4))
28

What’s going on here is that the leftmost juxtaposed value at the same precedence level (meaning inside parentheses in the Lisp family) must necessarily name a function, and the remaining values at that level are arguments to that function. So + and * above name functions and the digits are arguments. There’s no restriction that subsequent arguments must not be functions or that the leftmost argument not be, for example, the result of an application. The same basic rules apply in the ML family (assuming the functions named below worked as above):

sum 1 2 3
6

prod 2 2 (sum 0 3 4)
28

In applicative FP, functions are taken to exist which take at least one argument, and may take an arbitrary number, and juxtaposition is applying arguments to functions.

Concatenative FP

In concatenative FP, every function has the same API: take a stack and return a stack. Juxtaposition explicitly is thought of as concatenating two complete programs. The main family under concatenative FP is the Forth-like languages. So, to compute the sum of squares, one could do something like this:

2 3 dup * swap dup * +

This would leave 13 on the stack. What happened here, in terms of stack effects is as follows:

2
2 3
2 3 3
2 9
9 2
9 2 2
9 4
13

An interesting thing about this is that literals are not merely literals, they also push themselves onto the stack.

The winning property of concatenative languages (and the source of the name “Factor”) is that any sequence of juxtaposed words can be extracted (“factored”) into its own word. To wit:

: sum-of-squares dup * swap dup * + ;
4 5 sum-of-squares .
41  ok

: square dup * ;
: sum-of-squares square swap square + ;
3 5 sum-of-squares . 
34  ok

: times-swap * swap ;
: times-plus * + ;
: sum-of-squares dup times-swap dup times-plus ;
4 4 sum-of-squares .
32  ok

Any run of words can be extracted in this fashion, because any run of words truly refers to a complete program which is performed on an input stack and producing an output stack. So every Forth program can be thought of as a pipeline acting on the same root data structure.

Array FP

Array languages provide functions with exactly two arities: 1 or 2 arguments. In general, these are referred to as monads and dyads respectively, but I have been referring to them as unary and binary operators, because this is the conventional name for such a thing.

Interestingly, juxtaposition in APL is how one builds an array of values. Prior to J, juxtaposition of operators had no meaning. In J, value juxtaposition means the same thing as before but operator juxtaposition means something quite novel, which they call “verb trains,” which are interpreted as either “forks” or “hooks” depending on whether or not the “train” is even or odd in length. This is reminiscent of the phenomenon of verb serialization in natural language, in which speakers of certain languages can emit a list of verbs to imply that all took place one-by-one in some order.

A hook is an even number of juxtaposed functions, and produces the following structure:

(f g) x becomes x f (g x)

A fork is an odd number of juxtaposed functions and produces the following structure:

(f g h) x becomes (f x) g (h x)

It isn’t immediately apparent, but what’s happening here is juxtaposition is producing a binary tree of operators. I’d like to go into more detail and produce better examples, but this functionality is a bit over my head still. I’m sure with practice this becomes easy, but I’m quite new.

Juxtaposition and Arity

It’s interesting to me that these three families of FP languages have three different notions of “function” and also three different interpretations of juxtaposition. For example, in the applicative order, functions are generally regarded as taking any number of formal parameters. In the ML family, functions have a minimum arity of 1 (less than that and you have a value) and a maximum arity of 1 as well, with additional parameters faked either by tuples (more common in Standard ML) or by returning functions of decreasing arity. For example, in Haskell a function with type Int -> Int -> Int can be treated either as a function taking two integers or a function taking one integer that returns another function that takes one integer and returns an integer. Here’s a brief summary:

OrderFamilyArityJuxtaposition
MinMax
ApplicativeLisp0NApply items 1–N to function at item 0
ApplicativeML1NApply items 1–N to function at item 0
ConcatenativeForth11Evaluate items left to right on the same stack
ArrayJ12Build a binary tree of operators and evaluate it with arguments on right or left and right

Reflections on OOP

In all conventional procedural and OO languages, functions are defined and called by passing parameters in a comma separated list, as in:

def foo(a, b, c):
  return a + b * c

There is an interesting analogous question in languages that admit side effects: what to do when a function of arity 0 is invoked? Consider a function to return a random number which requires no parameters, say it’s called random. Do you call random by saying random or random() or something else?

The decision comes down to a question of whether or not you consider a function to be an implementation detail or not. Bertrand Meyer formulated the universal access principle which states that the client of an interface should not be able to distinguish between a simple property access and a function call, because the implementation should be able to choose the strategy that works best for it without breaking compatibility. In other words, whether a property of some object is computed on-demand or stored in a variable is an implementation detail. As a result, “getters” in Eiffel and Ruby do not require parentheses on their invocation.

Python and most C-derived languages have adopted the opposite strategy which lacks a sexy name. In Python, the difference between foo and foo() is that the former refers to the function foo as a value and foo() is really a request to evaluate the function named foo and produce the result. The distinction is not meaningless. The Python library makes much less use of anonymous functions than Ruby’s, for example, but coding a higher-order function involves fewer moving parts.

Smalltalk and Ruby still permit the passing of functions as first-class values through a sort of reified function enclosure called a block. Smalltalk and Ruby do not permit direct variable access to objects, so all getters are really function invocations, but object foo in Smalltalk or object.foo in Ruby cannot be used to refer to the methods named foo on object. Both get around it in part by having a method Object#send which takes a method name (“selector”) as an argument for the specific case of wanting to call a method on another object as well as the block functionality. A block in Smalltalk looks like [ :param1 :param2 | code goes here ] and furnishes an object which, when value is called on it, returns the result of evaluating the block. Additional methods on the block permit passing of formal parameters.

This looks like a very similar tradeoff, but it makes somewhat more sense in that it is a property of the language with two alternatives rather than three.