Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
You mean Moses Schönfinkel? Then you must be wrong about him in 1967. He died in poverty in 1942. –  Petr Pudlák Feb 5 '13 at 23:36
    
Nor is 1967 before LISP. :-) –  jimwise Feb 6 '13 at 0:41
add comment

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
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
    
@augustss, indeed, nevertheless, we have a nice hierarchy here: values (taking no argument), functions that take values, functions that take functions that take values, and so forth. If Frege says "grundverschieden" he probably means that with regard to this hierarchy. –  Ingo Feb 6 '13 at 11:40
show 3 more comments

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/

share|improve this answer
    
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
1  
"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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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