David Udell comments on David Udell’s Shortform

• In the 1920s when and CL began, logicians did not automatically think of functions as sets of ordered pairs, with domain and range given, as mathematicians are trained to do today. Throughout mathematical history, right through to computer science, there has run another concept of function, less precise at first but strongly influential always; that of a function as an operation-process (in some sense) which may be applied to certain objects to produce other objects. Such a process can be defined by giving a set of rules describing how it acts on an arbitrary input-object. (The rules need not produce an output for every input.) A simple example is the permutation-operation defined by

.

Nowadays one would think of a computer program, though the ‘operation-process’ concept was not originally intended to have the finiteness and effectiveness limitations that are involved with computation.

Perhaps the most important difference between operators and functions is that an operator may be defined by describing its action without defining the set of inputs for which this action produces results, i.e., without defining its domain. In a sense, operators are ‘partial functions.’

A second important difference is that some operators have no restriction on their domain; they accept any inputs, including themselves. The simplest example is , which is defined by the operation of doing nothing at all. If this is accepted as a well-defined concept, then surely the operation of doing nothing can be applied to it. We simply get

.

Of course, it is not claimed that every operator is self-applicable; this would lead to contradictions. But the self-applicability of at least such simple operators as , , and seems very reasonable.

The operator concept can be modelled in standard ZF set theory if, roughly speaking, we interpret operators as infinite sequences of functions (satisfying certain conditions), instead of as single functions. This was discovered by Dana Scott in 1969 (pp. 45-6).

--Hindley and Seldin, Lambda-Calculus and Combinators (2008)