Content deleted Content added
syntaxhighlight & fix lint |
|||
| (49 intermediate revisions by 19 users not shown) | |||
Line 1:
{{WikiProject
{{WikiProject Computer science|importance=high}}
}}
{{To do}}
==Language Support table==
The [[First-class function#Language support|language support table]] is excellent and reasonably detailed. However, it's missing the following languages:
* [[R (programming language)|R]]
* [[F Sharp (programming language)|F#]] (under "Functional Languages") <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:BryanFrazar|BryanFrazar]] ([[User talk:BryanFrazar|talk]] • [[Special:Contributions/BryanFrazar|contribs]]) 20:35, 6 January 2015 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
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. --[[User:Hierarchivist|Hierarchivist]] ([[User talk:Hierarchivist|talk]]) 21:51, 7 May 2014 (UTC)
==Analog in C==
"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 [[
::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. --[[User:MarkSweep|MarkSweep]] 07:08, 13 Nov 2004 (UTC)
Line 32 ⟶ 43:
: 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:
<syntaxhighlight lang="C">
void EvalFuncOnGrid( float(^block)(float) ) {
int i;
Line 49 ⟶ 60:
Caller();
}
</syntaxhighlight>
: 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
: [[Special:Contributions/75.143.82.88|75.143.82.88]] ([[User talk:75.143.82.88|talk]]) 03:29, 3 August 2009 (UTC)
Line 59 ⟶ 70:
Are these requirements met in Apple`s C extension ? If not,- then that C extension clearly does not introduced first-class functions. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/84.32.222.96|84.32.222.96]] ([[User talk:84.32.222.96|talk]]) 08:19, 22 February 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:Yes, you can have a pointer to a block. https://developer.apple.com/library/ios/documentation/cocoa/Conceptual/Blocks/Articles/bxOverview.html. ---- [[User:CharlesGillingham|CharlesGillingham]] ([[User talk:CharlesGillingham|talk]]) 01:08, 1 November 2014 (UTC)
== Does PHP really have first class functions? ==
So this is a classic "proof" of first class functions in php:
<syntaxhighlight lang="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
</syntaxhighlight>
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:
<syntaxhighlight lang="text">
$cos = makeDerivative('sin', 0.00000001);
</syntaxhighlight>
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. [[Special:Contributions/72.235.55.215|72.235.55.215]] ([[User talk:72.235.55.215|talk]]) 09:36, 15 June 2012 (UTC)
== Does Ruby really have first class functions? ==
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:
<syntaxhighlight lang="text">
def f(x)
Line 71 ⟶ 112:
g(2)
</syntaxhighlight>
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.[[User:88.96.214.6|88.96.214.6]] 12:26, 20 March 2007 (UTC)
Line 78 ⟶ 119:
:: However you can access them by calling their containing module and asking for the function. Like:
<syntaxhighlight lang="text">
def f(x) # global functions are contained in the Kernel
x + 4
Line 88 ⟶ 129:
g.class #=> 'Method'
proc = g.to_proc # returns the method as a Proc
</syntaxhighlight>
:: 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.
:: [[Special:Contributions/75.143.82.88|75.143.82.88]] ([[User talk:75.143.82.88|talk]]) 03:07, 3 August 2009 (UTC)
Line 96 ⟶ 137:
IMO Python ''has'' unlimited function literals; it is possible to create any function (not limited to an expression like <tt>lambda</tt> functions) by creating a string and executing it; example:
<
>>> code="""def myfunc(a):
Line 109 ⟶ 150:
>>> myfunc(3.0)
3.0 is not an integer number
>>></
(just tested using Python 2.5.2) --[[User:TobiasHerp|Tobias]] ([[User talk:TobiasHerp|talk]]) 09:55, 19 August 2008 (UTC)
Line 115 ⟶ 156:
And what about this? ->
<
import math
Line 129 ⟶ 170:
# cos(math.pi/2) ~> 0.0
</syntaxhighlight>
== Regarding runtime generation ==
Line 166 ⟶ 207:
: [[User:Pohta ce-am pohtit|Pcap]] [[User_talk:Pohta ce-am pohtit|<small>ping</small>]] 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
::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
::: Did you read my summary of the references [[Talk:First-class_object#In_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. [[User:Pohta ce-am pohtit|Pcap]] [[User_talk:Pohta ce-am pohtit|<small>ping</small>]] 05:32, 24 August 2009 (UTC)
Line 176 ⟶ 217:
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) <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/84.32.222.96|84.32.222.96]] ([[User talk:84.32.222.96|talk]]) 09:04, 22 February 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
I agree with [[Special:Contributions/84.32.222.96|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. [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 16:26, 25 August 2010 (UTC)
== Higher-order functions in Perl ==
(see M.J. Dominus. Higher Order Perl, 2005. pp 325, 333)
<
$lambda = sub {$_[0] + 4};
print $lambda->(2), "\n"; # => 6
</syntaxhighlight>
[[User:Psilva|Psilva]] ([[User talk:Psilva|talk]]) 09:35, 26 September 2009 (UTC)
Line 192 ⟶ 235:
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:
<syntaxhighlight lang="text">
// imports first_class dll.
Line 217 ⟶ 260:
}
</syntaxhighlight>
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).
Line 233 ⟶ 276:
I think this new section should be trimmed. --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|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. —''[[User:Ruud Koot|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. —''[[User:Ruud Koot|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. --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|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. --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|talk]]) 11:34, 13 February 2011 (UTC)
==Does Haskell allow functions as keys in a map?==
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:
<syntaxhighlight lang="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'></syntaxhighlight>
: 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? —''[[User:Ruud Koot|Ruud]]'' 07:46, 17 February 2011 (UTC)
<syntaxhighlight lang="python">>>> 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</syntaxhighlight> --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|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. --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|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. —''[[User:Ruud Koot|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. —''[[User:Ruud Koot|Ruud]]'' 10:54, 17 February 2011 (UTC)
: For your peace of mind: Python has first-class functions and reference equality:
<syntaxhighlight lang="python">
>>> 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
</syntaxhighlight>
: —''[[User:Ruud Koot|Ruud]]'' 11:32, 17 February 2011 (UTC)
: Also Pythons nested functions seem crippled compared to Scheme:
<syntaxhighlight lang="python">
>>> 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
</syntaxhighlight>
: but only artificially and not fatally:
<syntaxhighlight lang="python">
>>> 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
</syntaxhighlight>
: —''[[User:Ruud Koot|Ruud]]'' 11:57, 17 February 2011 (UTC)
Hi Ruud, Python 3 addressed the access to outer variables issue with the nonlocal keyword:
<syntaxhighlight lang="python">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
>>> </syntaxhighlight> --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|talk]]) 14:36, 17 February 2011 (UTC)
== Partial Function Application in C++ ==
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 [http://www.dreamincode.net/forums/topic/264061-c11-fun-with-functions/ 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.
[[Special:Contributions/63.232.147.98|63.232.147.98]] ([[User talk:63.232.147.98|talk]]) 01:14, 22 February 2012 (UTC)
== Partial Function Application in JavaScript ==
[http://ejohn.org/blog/partial-functions-in-javascript/ Partial Application in JavaScript]
[http://osteele.com/archives/2007/07/functional-javascript Partial function application] in the functional js library.
--[[User:Widged|Widged]] ([[User talk:Widged|talk]]) 21:12, 13 March 2012 (UTC)
== C has first-class functions (revisited) ==
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 [https://developer.apple.com/library/ios/documentation/cocoa/Conceptual/Blocks/Articles/00_Introduction.html#//apple_ref/doc/uid/TP40007502-CH1-SW1 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. ---- [[User:CharlesGillingham|CharlesGillingham]] ([[User talk: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. --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|talk]]) 15:09, 12 November 2014 (UTC)
== Section "Case study: function composition" is not worth having. ==
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. --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|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. [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 22:42, 29 November 2014 (UTC)
== Language support breakdown of languages by taxonomy is misleading and irrelevant ==
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. <!-- Template:Unsigned --><small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Rahab rx|Rahab rx]] ([[User talk:Rahab rx|talk]] • [[Special:Contributions/Rahab rx|contribs]]) 18:36, 3 September 2016 (UTC)</span></small> <!--Autosigned by SineBot-->
: 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. —''[[User:Ruud Koot|Ruud]]'' 19:42, 6 September 2016 (UTC)
== I disagree that Python has partial application. ==
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. [[Special:Contributions/131.252.226.117|131.252.226.117]] ([[User talk:131.252.226.117|talk]]) 19:23, 8 November 2016 (UTC)
== External links modified ==
Hello fellow Wikipedians,
I have just modified 2 external links on [[First-class function]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=803238201 my edit]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:
*Added archive https://web.archive.org/web/20120319071329/http://common-lisp.net/project/bknr/static/lmman/fd-clo.xml to https://common-lisp.net/project/bknr/static/lmman/fd-clo.xml
*Added archive https://web.archive.org/web/20110720102933/http://lambda.uta.edu/cse5317/l12.ppt to http://lambda.uta.edu/cse5317/l12.ppt
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
{{sourcecheck|checked=false|needhelp=}}
Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 09:27, 1 October 2017 (UTC)
== link doesnt work ==
the first link in the first note leads to "page not found" <!-- Template:Unsigned --><span class="autosigned" style="font-size:85%;">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:2001:7c7:2051:195:e1ce:11c7:dd2e:fd8b|2001:7c7:2051:195:e1ce:11c7:dd2e:fd8b]] ([[User talk:2001:7c7:2051:195:e1ce:11c7:dd2e:fd8b#top|talk]] • [[Special:Contributions/2001:7c7:2051:195:e1ce:11c7:dd2e:fd8b|contribs]]) 09:07, 27 September 2021 (UTC)</span>
:Thanks, I fixed the link in the article. [[User:Johnuniq|Johnuniq]] ([[User talk:Johnuniq|talk]]) 11:04, 27 September 2021 (UTC)
| |||