Talk:First-class function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
 
edit·history·watch·refresh Stock post message.svg To-do list for First-class function:
  • Interaction between higher-order and nested functions. Supported in Algol and Pascal. (Andrew Appel. Modern compiler implementation)
  • Raphael A. Finkel. Advanced Programming Language Design
  • Michael Lee Scott. Programming Language Pragmatics
  • Functions as dynamic values in dynamic programming languages (eval)
  • C Sharp 2.0#Anonymous delegates vs. C Sharp 3.0#Lambda expressions
  • Lexical and dynamic scoping
  • Anything to say about recursion? (Anonymous recursion, returning nested recursive functions, tail recursion)
  • Putting it together: function composition, a higher-order function taking two functions as argument and returns an (anonymous or nested) function.
    • Pascal: fails because we cannot return functions
    • Oberon: fails because we cannot return nested functions
    • C: fails because the function we return needs to have access to the (non-local) paramaters
    • Lisp: fails because of dynamic scoping
    • C++0x: fails because closures do not extend lifetime/capture by copy
    • Java: fails because anonymous inner classes cannot capture the non-final parameters
  • Early languages: POP-2
  • parameters/non-local variables/partial application
  • First-class functions and object-oriented languages (scoping of this, fully-featured closures?)
  • Discuss why C is sometimes said to have 1.5-class functions (e.g. in MLS, Prog. Lang. Prag.)
  • Tidy the table (again...); add ref=note
  • Figure out how Algol and Pascal compilers handle passing nested functions as arguments to higher-order function. They probably don't build a closure.
  • Missing from language support table: BASIC, COBOL, PL/I, PL/M, Modula, Modula 2, Modula 3
  • http://c2.com/cgi/wiki?FirstClass
  • Other aspects of first-class entities: equality testing, pattern matching, deriving from Object, etc.
  • Mention and link to closure conversion.

Language Support table[edit]

The language support table is excellent and reasonably detailed. However, it's missing the following languages:

Please add a language to the list if it is missing from the table. Put higher priority languages higher on the list. Please remove a language if it has been added to the table. --Hierarchivist (talk) 21:51, 7 May 2014 (UTC)

Analog in C[edit]

"Most modern programming languages support functions defined statically at compile time. C additionally supports function pointers, which can be stored in data structures and passed as arguments to other functions. Nevertheless, C is not considered to support first class functions, since in general functions cannot be created dynamically during the execution of a program. The closest analog in C is that of a dynamically compiled function created by a just-in-time compiler, which is compiled as an array of machine language instructions in memory and then cast to a function pointer. However, this technique is specific to the underlying hardware architecture and is therefore neither general nor portable."

I have problems with this. The main thing is that the attempt to find an analog in C seems pointless to me. I wouldn't try to find an analog of 'break' in Lisp, although I'm sure I could find something not too dissimilar if I strained hard enough. In turn, I don't think it's conducive to understanding of the first class function to compare it to something like int (*f)(). Of course it is perfectly feasible to write C code to write a bit of C, compile it, put it into a dynamically linked library, open the library and execute it--in fact, this was even easier in BCPL, one of C's percursors, which had extensive dynamic module load and execution capabilities built into its standard library. However this isn't really a first class function, it's just a neat programming trick.
Well, I was trying to pre-empty a potential argument that the presence of function pointers in C is the same as having first class functions. What are the crucial properties a function object has to have in order to qualify as first-class? You can pass function pointers as arguments to other functions, and you can store them in memory and other data structures; in these respects function pointers and first class functions are indeed similar. What distinguishes function pointers from first class functions is that the only values a function pointer can take on are the addressed of functions defined at compile/link time. However, due to the presence of casts (nothing stops you from casting arbitrary pointers to function pointers), this is not literally true, but those casts are really only useful for in-memory compilation. Since C directly supports function pointers and casts in the language, it makes sense to point out that these features don't add up to first class functions, with which they nevertheless share some properties. --MarkSweep 07:08, 13 Nov 2004 (UTC)
I agree with the garbage collector guy. When reading the page, you insintictively have the urge to say "hey but C...", yet the text corrects you in time. Wouter Lievens 21:40, 3 Apr 2005 (UTC)

The notion of "dynamically creating functions" is grossly inaccurate.[edit]

The languages mentioned, for the most part, do not have the explicit ability to create functions but to create closures. Functions consist of code, which is typically not dynamically generated or modified. Closures capture the (usually lexically) contectual environment existing at the time of the closure's creation, along with whatever function is associated with the closure. This is, unfortunately, more than a semantic issue - it is explicitely being confused with dynamic code generation, which is given as a comparative example. This technique has nothing in common whatsoever with first order functions.

Of course, removing this "requirement" from the list also means that C DOES have first class functions. If you don't agree with this, I'd recommend including closures as mentioned (which, IMO, are a somewhat different beast), and perhaps anonymous functions as well.

I'd make these changes myself but I don't want to so majorly overhaul this node without some further input. —The preceding unsigned comment was added by 74.128.168.38 (talk) 22:36, 18 January 2007 (UTC).

I agree here. Maybe a mention of the eval() statement (or equivalents) would help to make the difference more obvious? --80.135.123.126 16:22, 26 January 2007 (UTC)
I think that the definition as given here isn't really accurate. As far as I understand the term, the point is just that there is no difference between a function and a data type in the things you can do. This implies that you can assign local variables to functions, and then call those local variables in exactly the same way as you'd call a function. It implies that you can pass functions as arguments to other functions. Creating a function at runtime seems to me to be a completely different thing. In particular, you can achieve similar effects in every language I know of - even if you have to compile the code yourself into memory. I don't think that passing a function pointer around as in c, or wrapping the code in an inner class (java) or a Proc (ruby) qualifies as first-class functions. The point is that they are 'first-class' - that they don't need special treatment. 88.96.214.6 10:25, 22 March 2007 (UTC)
Clearly there are different interpretations of this term, so just listing the meaning you or I happen to be most familiar with is not going to produce an adequate article. It's better to make a clearer list of individual language features and discuss them separately. Features would at least include:
  • syntactic support for passing functions (or function pointers) as arguments and yielding them as results, such that the function in question can subsequently be invoked (C has that)
  • function types in the type system (C has that)
  • support for closures (see above) (not in C)
I don't think an eval function, Lisp macros, C macros, C++ templates, code generation, or Java / .NET reflection are features that belong in this list. As remarked above it would be good to explicitly make this clear was well. Rp (talk) 08:17, 7 April 2008 (UTC)

IMO a more serious problem here is the fact that AFAIK this statement is not supported by the references. The only reference I see for this article is Scott's Programming Language Pragmatics. I own a copy of that book and I was just reading it the other day. I'm pretty sure Scott says that C *does* have first-class functions. He gives a clear definition of first-class, second-class and third-class objects and none of the definitions makes any reference to whether you can "dynamically" create an object. It does require that in order to be a first-class object, the language must allow you to use it as the return value of a function (which C allows). If anyone objects to this analysis then I suggest they dig up another reference that supports their view. 216.165.132.252 (talk) —Preceding undated comment added 17:46, 24 December 2009 (UTC).

C has closures[edit]

If your using Apple's version of C then you can use their new block syntax which adds closures and runtime blocks to the C language. Apple has submitted their change to the C language to be added to the standard (its currently implemented on the the llvm-gcc and clang C compilers. These blocks/closures work in C, C++ and Objective-C
Here is an example of what they look like in C:
   void EvalFuncOnGrid( float(^block)(float) ) {
       int i;
       for ( i = 0; i < 5 ; ++i ) {
           float x = i * 0.1;
           printf("%f %f", x, block(x));
       }
   }
   
   void Caller(void) {
       float forceConst = 3.445;
       EvalFuncOnGrid(^float(float x){ return 0.5 * forceConst * x * x; });
   }
   
   void main(void) {
      Caller();
   }

These blocks can be treated as first class functions, they have a dynamic binding, can be passed around at run time and automatically track references to variables used inside that are declared outside of their scope, thus they act as true closures. The complete specification can be found here: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1370.pdf
75.143.82.88 (talk) 03:29, 3 August 2009 (UTC)

I don`t see from this example Does Apple extension made first-class functions avialable or not. It just shows that you can pass anonymous function as parameter. To see that it fully supports first-class functions we also have to see that-

1. We can assign anonymous function to variable.

2. We can return anonymous function from other function.

Are these requirements met in Apple`s C extension ? If not,- then that C extension clearly does not introduced first-class functions. —Preceding unsigned comment added by 84.32.222.96 (talk) 08:19, 22 February 2010 (UTC)

Yes, you can have a pointer to a block. https://developer.apple.com/library/ios/documentation/cocoa/Conceptual/Blocks/Articles/bxOverview.html. ---- CharlesGillingham (talk) 01:08, 1 November 2014 (UTC)

Does PHP really have first class functions?[edit]

So this is a classic "proof" of first class functions in php:

   function makeDerivative($fn, $deltaX) {
     return function($x) use ($fn, $deltaX) {
       return ($fn($x + $deltaX) - $fn($x)) / $deltaX;
     };
   }
   
   $cos = makeDerivative(sin, 0.00000001);
   echo $cos(0);        // 1
   echo $cos(pi() / 2); // 0

But there are a few things wrong with it. First, this code actually throws a catchable fatal error. The label 'sin' doesn't refer to the builtin function but rather the constant sin. Since such a constant wasn't defined, php pretends you meant string 'sin'. What you should actually do is:

   $cos = makeDerivative('sin', 0.00000001);

and for all intents and purposes, $fn in the closure is a string. When you use $fn($x), php resolves the value of the string to some function and calls it with the arguments $x, but in no situation can you actually store or pass in a reference to a function. The closure object is actually first class (you can pass it around, assign it to variables), but functions are not. 72.235.55.215 (talk) 09:36, 15 June 2012 (UTC)

Does Ruby really have first class functions?[edit]

It seems to me that if you have to wrap a function in a 'proc' object in order to assign it to a variable, then your functions are second-class citizens. Something else I would expect to be able to do in a language that supports first class functions:

   def f(x) 
       x+4
   end
   g = f
   g(2)

This doesn't work in ruby either. You can't assign a function using = (the normal assignment operator), you have to use def, or wrap the function in an object. That's not first-class.88.96.214.6 12:26, 20 March 2007 (UTC)

I must concur. jsnx (talk) 02:11, 7 December 2007 (UTC)
However you can access them by calling their containing module and asking for the function. Like:
   def f(x) # global functions are contained in the Kernel
       x + 4
   end
   g = Kernel.method :f
   g.call(2) #=> 6
   g[2] #=> 6
   g.(2) #=> 6 (only works in ruby 1.9, its a new syntax) 
   g.class #=> 'Method' 
   proc = g.to_proc # returns the method as a Proc 

Also, in Ruby, a Proc is by definition exactly what a first class function is. Granted, you can't directly assign a method to a variable using the = operator like in other languages, I would still argue that Ruby does indeed have first class functions.
75.143.82.88 (talk) 03:07, 3 August 2009 (UTC)

Function literals in Python[edit]

IMO Python has unlimited function literals; it is possible to create any function (not limited to an expression like lambda functions) by creating a string and executing it; example:

>>> code="""def myfunc(a):
...  if isinstance(a, int):
...   print a**2
...  else:
...   print a, 'is not an integer number'
... """
>>> exec(code)
>>> myfunc(3)
9
>>> myfunc(3.0)
3.0 is not an integer number
>>>

(just tested using Python 2.5.2) --Tobias (talk) 09:55, 19 August 2008 (UTC)

And what about this? ->

import math

def make_derivative(f, deltaX):
    delta=[deltaX]
    function=[f]
    fnc=lambda x: (function[0](x+delta[0])-function[0](x))/delta[0]
    return fnc

cos=make_derivative(math.sin, 0.0000000001)

# cos(0)     ~> 1.0
# cos(math.pi/2)  ~> 0.0

Regarding runtime generation[edit]

I just wanted to state agreement with the anonymous edit [1] removing the statement "A different set of difficulties arises when programs can create functions at runtime; if the program is compiled, this means that the runtime environment must itself include a compiler." Although it is possible for a program to generate another program in source or AST form and subsequently compile it at runtime, it is also possible for a program to directly generate machine code at runtime, and this is common in certain applications e.g. compiled bitmaps. Dcoetzee 12:30, 30 November 2008 (UTC)

Just because you can create a compiled bitmap from C, or embed a compiler in a C program, does not mean that the C language supports creating functions dynamically. Since it allows you to escape the type system through dangerous pointer casts and such, it does allow you to hack in such functionality, or perform any kind of machine-level black magic that you want, but that's quite different from providing language support. Many C compilers support inline assembly instructions but they're not part of the C language either. Contrast this with Common Lisp which does provide a compiler within the runtime environment and does allow you to generate and run Lisp code at runtime. Every Common Lisp implementation is required to have this functionality and it is fully integrated with other language features. 216.165.132.252 (talk) —Preceding undated comment added 17:54, 24 December 2009 (UTC).

Merge anonymous function here[edit]

That article wants to describe the same concept. An anonymous function per se is damn useless. What makes it useful is that it can be passed around. But that article fails to explain this, or pretty much anything, besides giving some examples that largely overlap with this article. Pcap ping 21:35, 20 August 2009 (UTC)

Rather tellingly, that article does not cite a single programming languages theory book, but use plenty of jargon from various implementations as if they were theoretical concepts universally known by that name. Pcap ping 21:46, 20 August 2009 (UTC)
Please don't merge AF here, except maybe a mention that just as say, a number can be passed between/assigned to several variables in a language; the concept of an Anonymous Function is a function that can be assigned to multiple variables or stored in collection types, which aids in making functions as first class as other types in the language. --Paddy (talk) 21:57, 20 August 2009 (UTC)
So what is an anonymous function according to you? Does C have them? You can do all of what you wrote above in C using function pointers, but you cannot have unnamed functions in C. Pcap ping 01:12, 21 August 2009 (UTC)
I come from a Lisp background, so anonymous functions are near and dear to my heart. However, the core semantic issue here is not whether the functions are anonymous, but whether they are first-class objects which can be assigned to variables, passed as arguments, etc. Consider a (non-existent) variant of Lisp, where closures were created by something like (lambda funcname (arg1 arg2) ...) instead of simply (lambda (arg1 arg2) ...). That would be an utterly trivial variant which might allow the printer (for example) to print a closure as #<function funcname> instead of #<function 234234> but would otherwise have no impact on the language.
As for the C case, if you're willing to consider function pointers as functions, then the fact that the only way you can create a function constant within the language (that is, not unsafely converting an untyped pointer to a function pointer) is by binding it to an identifier is again a trivial syntactic detail. Anonymous function should be merged into First-class function. --macrakis (talk) 02:16, 21 August 2009 (UTC)

I am not exactly an expert, but I think having first class functions is neither stronger nor weaker than having anonymous functions:

  • This is probably a stupid and very atypical example, but if you consider Java's reflection subsystem a core part of the language (this is not usually done), then Java arguably has first-class functions, modulo the kludgey syntax. But I don't think it has anonymous functions, since every function is actually a method in a class and must have a name as such. (There may however be a way to have a free name chosen dynamically.) A more straightforward example would be a programming language with a lambda operator that takes an explicit, non-optional parameter that serves as the name of the function. Of course you could work around this with a factory for unique names. This shows that the line is rather blurry, while the previous example shows that there may be real issues. [PS: I see now that Macrakis came up with this idea before me.]
  • Apparently recent versions of Visual Basic support anonymous functions. If this had been added to an earlier version I would be quite sure that these wouldn't be first class. I am not familiar with the .NET version of VB, though, so it's quite possible that they are first class. It's easy to create an artificial example of such a language. Just take a language with first class anonymous functions and add the restriction that functions may be assigned to parameter variables of functions (when calling the function), but not to ordinary variables.

Since the two concepts are closely related it may in fact be best to discuss them in a single article. But it would take a serious effort to get the details right, and we would need really good sources. It's probably easier to keep the articles separate but keep them synchronised. (Basically they should use the same languages as examples, unless a language has one of the properties but not the other, which should then be stated clearly.) Hans Adler 09:06, 21 August 2009 (UTC)

Java is not the best example, but in C++ you can use function objects, which overload the function call operator, (), to simulate first-class functions; you can even implement a fixed point combinator that way in C++ (there's a link on that page). In Java you only get anonymous inner classes, which give you closures, but you have to syntactically invoke a method thereof. Still you can implement a fixed point combinator in Java, with really awful syntax. But you don't need reflection, and if you have reflection but no inner classes to work as closures, you still can implement a fixed point combinator (try). Basically a fixed point combinator is an essential test of first-classness because it needs to return a function that's not "written" anywhere; well, it is defined implicitly. Since you mentioned Java, dynamic class loading is a different concept however, orthogonal to the idea of first-class functions; it's more like an eval as mentioned in this article.

Having said all that, we're not lacking concrete examples here, but rather some non WP:OR definitions of these concepts. I'll try to find some authoritative references (as in not some text on language X, but more principles/theory kinda book). Pcap ping 10:42, 21 August 2009 (UTC)

Just a heads-up. I've summarized some literature I've surveyed at Talk:First-class object. I need to look at a few more sources before coming to a definitive conclusion, but the rough picture is:
  • anonymous function = function literal >= first-class function. So we need separate articles, but both need rewriting.
  • Most authors consider the last relation an equality, but some define first-class function as less hard-to-meet concept. See that page for details.
  • First-class object should probably redirect here as that page is full of WP:OR. The concept is almost never discussed separately, but introduced in the discussion about the first-classness of functions. (I need to have closer look at some type theory stuff first, because one can have first-class type constructors for instance in the calculus of constructions, i.e. you can pass them to functions.)
Pcap ping 03:20, 24 August 2009 (UTC)
First-classness is interesting for many kinds of objects other than functions. For example, in most static languages -- such as Simula 67 (the first object-oriented language) and Ada -- types/classes are not first-class objects; in early versions of C, structs (records) were not first-class objects -- they could not be passed as parameters or returned as values, only pointers to them could be; in early versions of Lisp, arrays were not first-class objects -- they were properties of symbols (we called them 'atoms' then); etc. So I strongly disagree that First-class function and First-class object should be merged.
As for the relationship between first-class functions and function literals, it is surely not an equality. But anonymous function literals are a pretty trivial subject compared to first-class functions, so I think it makes sense to treat them as a section within first-class functions. --macrakis (talk) 05:01, 24 August 2009 (UTC)
Did you read my summary of the references there? Some sources consider functions in C first class, even though C has no function literals. This was actually pointed out repeatedly by multiple editors. Pcap ping 05:32, 24 August 2009 (UTC)
Your references there are all about first-class functions, not about other kinds of first-class objects (types/classes, structs, arrays, etc.), which is what I was talking about in my comment above. --macrakis (talk) 14:07, 24 August 2009 (UTC)
The first reference I gave there defines the notions in general. You are welcome to look for additional references covering topics like first-class types and classes. I gave a rewrite notice at first-class object; see WP:V. Pcap ping 11:14, 27 August 2009 (UTC)

I agree with Macrakis that first-class functions are a lot wider topic than anonymous functions. To show that I can simply mention the fact that function may return ordinary OR anonymous function. So in theory - language can support first-class functions by operating only with ordinary functions. This illustrates that in general first-class functions has nothing to do with anonymous functions. However in practice first-class functions are much more useful when used in conjuntion with anonymous functions. So at most - anonymous functions can be only sub-topic of first-class functions. (Albeit we can`t ignore possibility that mentioning anonymous functions here can obfuscate understanding of first-class functions) —Preceding unsigned comment added by 84.32.222.96 (talk) 09:04, 22 February 2010 (UTC)

I agree with 84.32.222.96, but I do feel that first-class function is an ill-defined concept. At present, the article lists four things a language must be able to do before it can be said to support first-order functions; many languages support the last three, but dynamic function code assembly by treating program code as just regular structured data (which I believe is the first property) is specific to interpreted languages (e.g. in the Lisp or Forth families) and therefore quite different from the other three. Someone who knows only Lisp, or only C#, or only C++, won't see this, of course. So while I'm opposed to this merge, I do think it's important to consider whether the present article describes a well-defined term in the first place. Rp (talk) 16:26, 25 August 2010 (UTC)

Higher-order functions in Perl[edit]

(see M.J. Dominus. Higher Order Perl, 2005. pp 325, 333)

$lambda = sub {$_[0] + 4};
print $lambda->(2), "\n"; #  => 6

Psilva (talk) 09:35, 26 September 2009 (UTC)

There is also this. --Paddy (talk) 16:23, 26 September 2009 (UTC)


Higher-order functions in C/C++[edit]

I disagree with various statements concerning whether or not this is generally available in C - or that it must somehow require specific hardware. Consider the following:

// imports first_class dll.

  1. include <first_class.h>

class dll_data; class first_class;

main (char* args) {

 dll_data *dll_data = new dll_data (int N, args);
 char *new_c_source;
 bool quit = false;
 while (!quit)
 {
        first_class::load_dll ();       
       quit = first_class::run (dll_data);

new_c_source = dll_data->new_source;

   first_class::unload_dll ();
       if (new_c_source!=NULL)

first_class::recomplie_dll (dll_data->new_source);

 }

}

Windows actually has a "LoadModule" function (I think) that allows you to load dlls when you want them or need them, allowing you to do things like have one version of a program that can use different DLL's according to different OS, or whatever. These can then be loaded during execution rather then when the program first starts up (automatically) and thus avoiding the dreaded "required DLL not found error". The process can even be applied recursively, so that DLL's which have various complicated and interacting dependencies can be linked in and out, etc. In my simple example I am suggesting a kind of persistent data block type (which could also be modified if needed by using placement new, casting to a void pointer, and/or realloc as needed).

Then there is the issue of "Active X" and so on. I'm not sure how you would do this in Linux, although I am aware that Linux/Uxix variants to support some kind of _popen (char *filename -- etc) method which allows an application to create a new process and communicate with it via a named pipe and thus incur no more essential performance penalty other than whatever mighg be associated with named pipes. Lots of things could be dynamically modified this way -- such as MPEG encoders, database engines, etc. The pipes in such cases can be used for streaming the otherwise computationally intensive data -- even to the point that it becomes imaginable to create applications that could be run for months or even years (I have seen Linux boxes with uptime over 1 year) —Preceding unsigned comment added by 67.116.237.73 (talk) 08:40, 5 December 2009 (UTC)


Functional languages must support first-class functions BY DESIGN (in language semantics itself),- not recursively/dynamically invoking compiler as in your example or not by doing some other metaprogramming stuff. Otherwise by using your logic we can conclude that ANY compiled language supports functional programming (or any other programming idiom, just by invoking compiler dynamically). Which will sound crazy [and leave language designers unemployed :) ], don`t you think ? So let`s face it - C/C++ was not designed as modern functional language, and it will stay as it is, unless ... will be re-designed by it`s designers :-) —Preceding unsigned comment added by 84.32.222.96 (talk) 17:50, 22 February 2010 (UTC)

New 'Comparison' Section has wrong focus[edit]

It is about what haskel can do with its functions rather than about first class functions. They are not the same thing. The former is a superset of the latter.
Integers would be first class in most languages and whilst you would be able to pass them into and out of functions, you cannot curry an integer or lazily evaluate it, or create a closure on it.

The things you can do with a first class integer include passing it to and from a function; creating new integers from other integers in expressions; and having integers of members of collection datatypes such as lists and sets. If a language has first class integers, and you can do what you can do with integers with its functions, then the functions are every bit as first class as the languages integers. Or would integers in the language be thought of as second class?

I think this new section should be trimmed. --Paddy (talk) 18:43, 13 July 2010 (UTC)

I'm still thinking abut exactly what should and should not be covered in this article and certainly partial application and lazy evaluation would be at the top of the lists of thing being cut. However, the essential difference between languages where functions are first-class and where they are not is whether functions are treated as bare "function pointers" or as closures (dynamically-scoped LISP being the odd, but evolutionary interesting, case). The closure concept can be nicely extended to support partial application and lazy evaluation, the latter truly indicating the is no essential difference between first-class functions and other types.
I'd suggest I first continue writing some more of this down in the article and we can discuss what can stay, needs to be cut or moved to another article afterwards. —Ruud 16:21, 14 July 2010 (UTC)
P.S. Lazy evaluation in Haskell is implemented (naively, modulo compiler optimizations) because closures are created for "primitive" types like integers. Code never has to worry about whether some value is a primitive type or an unevaluated function returning an integer. They are just both "values" than can be obtained by forcing the closure. It think this is nice unifying concept that is not widely known and understood and would therefore be enlightening to include. —Ruud 16:54, 14 July 2010 (UTC)
OK by me Ruud. I like your idea of continuing the discussion when there is more to discuss; and thanks for pointing out that closures are created for other, definitely first class types such as integers. --Paddy (talk) 17:46, 14 July 2010 (UTC)
This leads me to think that what is classed as first class for functions is language dependant. For example, if you can use strings and integers as keys to hash/dictionary, then maybe for a function to be first class in that language a function must be able to be used in that way too. --Paddy (talk) 11:34, 13 February 2011 (UTC)

Does Haskell allow functions as keys in a map?[edit]

Or a member of a set for that matter? I'm just thinking what can you do with a string and an integer that you may not be able to do for a function in some languages, and so limit the first-classness of functions.

In Python:

>>> def a(): pass

>>> def b(): pass

>>> { a:1, b:2 }
{<function b at 0x00000000032669C8>: 2, <function a at 0x0000000003266A48>: 1}
>>> { a:1, b:2 }[a]
1
>>> {a, b}
{<function a at 0x0000000003266A48>, <function b at 0x00000000032669C8>}
>>> type({a, b})
<class 'set'>
In Haskell the keys of a map need to be of a finite type in order to guarantee that the the equality function will terminate (or more pessimistically, you cannot even define and equality function for functions in Haskell). The function type is infinite. Does Python compare function pointers? And does it work in combination with anonymous functions? —Ruud 07:46, 17 February 2011 (UTC)
>>> a = lambda : None
>>> b = lambda : None
>>> type(a)
<class 'function'>
>>> { a:1, b:2 }
{<function <lambda> at 0x000000000327D1C8>: 2, <function <lambda> at 0x0000000003276A48>: 1}
>>> { a:1, b:2 }[a]
1
>>> a == b
False
>>> a == a
True
>>> a is b
False
>>> a is a
True

--Paddy (talk) 08:36, 17 February 2011 (UTC)

It seems as if first classness of functions comes down to:

  • Find out what some 'obviously' first class types in a language can do.
  • Find out what functions in that language can do in those cicumstances.
  • Find out what 'obviously' first class functions in another language can do.
  • Call the languages functions first class or not.
  • Hope that the consensus goes your way.

- Hardly rigourous but very human. --Paddy (talk) 08:54, 17 February 2011 (UTC)

The most common definition you'll find in the literature is that functions can be passed as arguments (higher-order functions, downwards funarg problem) and returned and stored as values (upwards funarg problem).
Now I've thought about it bit more, related to the your question is the concept of function equality (intensional equality vs. extensional equality vs. reference equality, see e.g. http://www.cs.princeton.edu/~appel/papers/conteq.pdf). Its not directly related to first-classness, but as you raised it in this context it might be useful to discuss in the article. —Ruud 10:01, 17 February 2011 (UTC)
I'd prefer to have a simple table comparing language features (support for higher-order function, function types as the return type, anonymous functions, anonymous function that can refer to various outside their body, etc.) over a plain statement that language X has "first-class" functions or not. —Ruud 10:54, 17 February 2011 (UTC)
For your peace of mind: Python has first-class functions and reference equality:
>>> def main():
...    a = 10
...    b = 10
...    f = (lambda ls: map(lambda x: a * x + b, ls))
...    a = 3
...    b = 1
...    return f
...
>>> main()([1,2,3,4,5])
[4, 7, 10, 13, 16]
>>> (lambda x: x) == (lambda x: x)
False
Ruud 11:32, 17 February 2011 (UTC)
Also Pythons nested functions seem crippled compared to Scheme:
>>> def main():
...  x = 1
...  def f():
...   x = x + 1
...   print x
...  return f
... 
>>> o = main()
>>> o()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in f
UnboundLocalError: local variable 'x' referenced before assignment
but only artificially and not fatally:
>>> def main():
...  x = [1]
...  def f():
...   x[0] = x[0] + 1
...   return x[0]
...  return f
... 
>>> o = main()
>>> o()
2
>>> o()
3
>>> o()
4
>>> o()
5
Ruud 11:57, 17 February 2011 (UTC)

Hi Ruud, Python 3 addressed the access to outer variables issue with the nonlocal keyword:

Python 3.1 (r31:73572, Jun 28 2009, 18:34:47) 
[GCC 3.3.4 (pre 3.3.5 20040809)] on linux2
Type "copyright", "credits" or "license()" for more information.
>>> def outer():
    x = 1
    def inner():
        nonlocal x
        x += 1
        print(x)
    return inner

>>> f = outer()
>>> f()
2
>>> f()
3
>>> f()
4
>>>

--Paddy (talk) 14:36, 17 February 2011 (UTC)

Partial Function Application in C++[edit]

I don't understand why C++ isn't listed as supporting partial application of functions. This is exactly what the C++11 std::bind function does, and even in C++03 the std::bind1st and std::bind2nd functions provided for partial application, although in a limited way. I've found a number of web pages (such as one from the Dream in Code web site) that support this view, but I don't know if any of them would be considered definitive.

63.232.147.98 (talk) 01:14, 22 February 2012 (UTC)

Partial Function Application in JavaScript[edit]

Partial Application in JavaScript

Partial function application in the functional js library.

--Widged (talk) 21:12, 13 March 2012 (UTC)

C has first-class functions (revisited)[edit]

Back in 2010 someone pointed out that Apple's C supports anonymous functions called "blocks". I don't know much about all the various versions of C, but Apple writes that "Blocks are available in GCC and Clang as shipped with the OS X v10.6 Xcode developer tools" (See iOS Developer Library:Blocks Programming Topics). So what version of C is this?

Blocks can assigned to variable, passed to functions, returned as values from functions. The block can refer to variables in the scope that they were defined and use persistent storage for the local variables if the function returns. In other words, I think they thought of everything as far as I can see. Thus this version of C has first class functions.

This info should be added to the table and the text, otherwise this article is in error. ---- CharlesGillingham (talk) 01:19, 1 November 2014 (UTC)

If this version of C has functions as well as blocks then no, the article is not in error - it is *not* called first class blocks. These versions of C would have blocks distinct from functions and so it would be correct to omit them. --Paddy (talk) 15:09, 12 November 2014 (UTC)

Section "Case study: function composition" is not worth having.[edit]

This language specific section does not have enough merit to be included as it only states the capabilities and limitations of one language and will only encourage a host of other language specific entries. It is better to delete it. --Paddy (talk) 21:45, 16 November 2014 (UTC)

Agreed, but it may still be worth noting that in languages (e.g. Algol 68, C, C#) which treat functions as values (passing them to and returning them from functions, assigning them to variables and inside data structures) without being able to create new function bodies at runtime (lacking eval), higher order functions such as function composition can still be used to create new functions at runtime. Rp (talk) 22:42, 29 November 2014 (UTC)

Language support breakdown of languages by taxonomy is misleading and irrelevant[edit]

Language support for first class functions should not present a table grouping languages by family. It is not relevant to the topic but it is vague and at best arguable. Furthermore the specific taxonomy used is neither accurate nor intuitive with respect to first class functions. For example, one category is C Family and another is Scripting, while another is Functional.

I suggest we remove the taxonomy from table and restructure the section. — Preceding unsigned comment added by Rahab rx (talkcontribs) 18:36, 3 September 2016 (UTC)

I disagree. Languages within a family typically have similar support for various language features. Simply ordering the table alphabetically or chronologically would make it a lot more messy. —Ruud 19:42, 6 September 2016 (UTC)

I disagree that Python has partial application.[edit]

The source links to the functools library which includes functions common in functional programming. It does indeed have a partial application function, but what it does is just sort of provide a function that can be used in place of partial application. Python doesn't actually implement it on a syntax level. Have a function that takes an argument "x" and returns "x + 1" isn't partial application of "+1", it's just a function that is used instead of actual partial application. If Python has partial application, then every language which has closures also has partial application and you could probably argue that any language that has functions has partial application. 131.252.226.117 (talk) 19:23, 8 November 2016 (UTC)