I've come to understand that long before Haskell, O'Caml or LISP, higher order functions were an academic research subject and in mathematics, Schönfinkel (in 1967) and Haskell Curry (in 1968) already applied techniques such as currying, but that was before it was available in any programming language.

Scheme, according to Wikipedia, was the first language to introduce proper higher-order functions as first-class citizens, but is there anybody we can attribute the original idea to? Maybe Alonzo Church, who invented lambda calculus in the 1930's? More specifically, who coined the following definition, which I saw in various paraphrases around in several books and online resources?

A function is considered to be of higher order when it takes another function as an argument or when it returns a function. Any function not taking functions as arguments or as return types is called a first order function.


Frege says in "Funktion und Begriff" (1891):

Wie nun Funktionen von Gegenständen grundverschieden sind, so sind auch Funktionen, deren Argumente Funktionen sind und sein müssen, grundverschieden von Funktionen, deren Argumente Gegenstände sind und nichts anderes sein können. Diese nenne ich Funktionen erster, jene Funktionen zweiter Stufe.

In english (my translation):

Like things and functions are different, so are functions, whose arguments are functions radically different from functions whose arguments must be things. I call the latter functions of first order, the former functions of second order.

  • 1
    great cite! of course it would be frege. – sclv Feb 6 '13 at 1:01
  • Interesting that modern functional programming takes the opposite view - as far as possible (or at least, whenever you're working in a closed category) there is no distinction between functions whose arguments are functions, and functions whose arguments must be things. – Chris Taylor Feb 6 '13 at 8:21
  • The typechecker still reminds me when I mix it up, @ChrisTaylor :) – Ingo Feb 6 '13 at 8:55
  • 1
    Functions are things too, my friend. (To paraphrase Mitt Romney.) – augustss Feb 6 '13 at 11:30
  • 1
    I once too a course in logic and we used a definition for domains that made no distinction between constants and functions: a constant (value) is just a function with no arguments, i.e. a function whose value does not depend on any input value, and therefore the co-domain contains only one value. – Giorgio Jun 21 '14 at 17:24

The wikipedia article already attributes the "first-class citizens" terminology to Strachey.

"Higher order function" I would imagine dates back to the distinction between higher order and first order logic.

See https://en.wikipedia.org/wiki/Higher-order_logic and http://plato.stanford.edu/entries/logic-higher-order/

  • I'm not entirely certain whether higher-order logic and higher-order functions are interchangeable so easily. Thanks for pointing out Strachey, I somehow read over that. – Abel Feb 5 '13 at 23:10
  • 2
    "Higher order functions" exist in the work of Frege (functions taking functions as arguments for example), far predating Church's foundational work on the lambda calculus. A predicate in classical first oder logic is exactly a boolean valued function, so I second sclv's suggestion that this may be the source of the terminology. – Philip JF Feb 5 '13 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.