Page 162 - Textos de Matemática Vol. 40

150 Appendix In fact, we easily may implement Hilbert’s paradoxical function in a type-
free functional programming language. In scheme it would read like this:
(define (f x) (if (= (x x) 0) 1 0))
The syntax of the if expression is a little bit dense, but its meaning is straight- forward: if has three arguments, the first one—(= (x x) 0)—is the test, the second one—1—the result in the case that the test is positive, and the third one (the “else”-case)—0—which is returned in the case that the test is negative. But note, that in the case of x x ̸= 0 the “else”-case is only reached under the proviso that x x is terminating.
This is a meaningful function. Defining a function which is constantly 0 by (define (g x) 0), the evaluation of (f g) returns 1 (since (f g) equals (if (= (g g) 0) 1 0), with (g g) equal to 0, so the expression reduces to 1). However, if we try to evaluate the self-application (f f) we run into a computation which will not terminate (at least theoretically), since the computer will call again and again (f f) in the attempt to evaluate the condition of the if expression.56
Now, we would like to look closer at the application operation which is used, at least implicitly, in combinatory logic (and λ-calculus). Curry mentioned it referring to Scho¨nfinkel’s work: “In it [[Sch24]] Sch¨onfinkel introduced a bi- nary operation since called application. He wrote the application of an object f to an object a as (fa).” [Cur80, p. 86].57 The possibility of recasting juxtapo- sition in combinatory logic by use of a binary operator was—with reference to JanLukasiewicz(1878–1956)—observedbyWillardVanOrmanQuine (1908–2000) in his introduction to the English translation of Scho¨nfinkel’s paper: “But, if we want to get rid of parentheses, we can easily do so by adapt- inganideathatwasusedelsewhereinlogicbyLukasiewicz(1929,footnote1, pp. 610–612, 1929a; 1958; 1963). Instead of using mere juxtaposition to ex- press the application of functions, we can use a preponent binary operator ‘o’. Thus ‘xy’, ‘x(yz)’, and ‘(xy)z’ give way to ‘oxy’, ‘oxoyz’, and ‘ooxyz’.” [Qui67, p.356](thecitedreferencestoLukasiewiczare[Luk29b,Luk29a,Luk58,Luk63], respectively).
56In practice, many implementations will demand additional memory for each of the calls. When we tested the application of f to f with the scheme implementation guile (version 1.6.7) under linux, we received the following error message:
guile> (f f)
ERROR: Stack overflow
ABORT: (stack-overflow)
57With some goodwill one can even find an early “definition” of function application in the quotation of Hilbert from 1905, [Hil05a, S. 214]:
Wir definieren nun eine gewisse Funktion, das ist wieder ein Ding f, und der ”Wert dieser Funktion fu¨r das Argument x“ ist die Combination der beiden Dinge f x.
(“Now, we define a certain function, which is again a thing f, and the “value of this function for the argument x” is the combination of the two things f x.”)