9

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.

Improve this question
2
  • 1
    You mean Moses Schönfinkel? Then you must be wrong about him in 1967. He died in poverty in 1942.
    – Petr
    Commented Feb 5, 2013 at 23:36
  • Nor is 1967 before LISP. :-)
    – jimwise
    Commented Feb 6, 2013 at 0:41

2 Answers 2

Reset to default
9

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.

Improve this answer
8
  • 1
    great cite! of course it would be frege.
    – sclv
    Commented Feb 6, 2013 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
    Commented Feb 6, 2013 at 8:21
  • The typechecker still reminds me when I mix it up, @ChrisTaylor :)
    – Ingo
    Commented Feb 6, 2013 at 8:55
  • 1
    Functions are things too, my friend. (To paraphrase Mitt Romney.)
    – augustss
    Commented Feb 6, 2013 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
    Commented Jun 21, 2014 at 17:24
3

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/

Improve this answer
2
  • 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
    Commented Feb 5, 2013 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
    Commented Feb 5, 2013 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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