Content deleted Content added
→Article is unintelligible: new section |
|||
| (36 intermediate revisions by 15 users not shown) | |||
Line 1:
{{summary in|Lambda calculus}}
{{WikiProject
{{WikiProject Computer science|importance=Mid}}
{{WikiProject Mathematics|priority=low}}
}}
{{To do}}
Line 12 ⟶ 15:
:I don't think anybody did try it. Should've just removed it when I did a big cleanup a while back, I suppose. Thanks for the fix. —<tt>[[User:donhalcon|donhalcon]]</tt><sup>[[User talk:donhalcon|╤]]</sup> 14:52, 7 March 2006 (UTC)
:For those who will be searching for this in the future: the error comes from Klop’s original article, where this combinator has 28 Ls. [[User:Kirelagin|Kirelagin]] ([[User talk:Kirelagin|talk]]) 11:29, 16 September 2015 (UTC)
==Dumbing Down==
Line 21 ⟶ 26:
I suspect that some of that stuff is graffiti, but I'm not expert enough to say for sure. Will someone please check on it? --unknown
This article certainly doesn't explain things very well except to people who already know the information in the article. I have a bachelor's degree with a double major in computer science and mathematics, one of the courses I took mentioned the Y combinator one day in class, and while I did fairly well in both my majors as well as that class, that particular day in class the material made no sense to anybody and none of the other students understood it either. I still have no idea what on Earth a fixed-point combinator is, as it is described here using very technical language that is so technical you'd probably have to be taking graduate-level courses to understand what any of this means.
Pretty much none of the other programming-related articles on Wikipedia are anywhere near this hard to understand. Somebody really ought to fix this, I still don't have a clue about anything this article is saying and I studied this stuff in college and got good grades in it, at a university that at the time was classified as having one of the top 5 computer science departments in the United States! Could somebody please translate this article from ultra-technical language back into English so that it is readable by people who are not Ph.Ds or in Ph.D programs? I am actually of above average intelligence but even for me this article is way too hard to understand and I agree with the people from 12 years ago back in 2005, it needs to be dumbed down somehow so that people with IQs under 150 and people who did not go to graduate school can understand it. Yes, it's a great article for people who have a Ph.D in computer science and an IQ of 180 but some of us only have IQs in the 140s and only have bachelor's degrees, so please at least dumb it down enough for people like me. --[[User:Yetisyny|Yetisyny]] ([[User talk:Yetisyny|talk]]) 11:17, 18 July 2017 (UTC)
==Y Combinator==
Line 29 ⟶ 38:
::excellent argument. "Y combinator" is a term I have run into three times in the past few weeks, and I found better explanations of it elsewhere. Thanks wiki. You suck. More nerds talking to themselves rather than being informative. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/72.92.6.251|72.92.6.251]] ([[User talk:72.92.6.251|talk]]) 05:20, 8 September 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
:::There is nothing magic about Wikipedia (except possibly the magic put into it by generous people donating their knowledge and editing skills). There are certainly articles here that are just plain unhelpful to many readers. If you have found better explanations elsewhere, and don't bother to point to them, then you are not being at all helpful in making WP better (which is at the heart of your own criticism). Sorry that I am posting this four years later, when you are no doubt gone, but I share your frustration when reading unhelpful articles. I only wish you had chosen to help us instead of limiting yourself to criticism. [[User:David spector|David Spector]] ([[User Talk:David spector|talk]]) 01:12, 16 April 2016 (UTC)
== Example ==
Line 73 ⟶ 84:
: and then you can define your f as
f' x = (fix plus') x 1
:[[User:jbolden1517|jbolden1517]]
Hmmmm. So, if I read you right, you're basically saying what I was figuring at first: that fix (by which I assume you mean Y) can only be defined on functions like plus' which are specially written in such a way as to receive a (fix whatever) function as a first argument? And not on functions like plus which are not?
Line 94 ⟶ 105:
Maybe we could try to improve it a little / make it more readable (at least add proper indendation) and then incorporate it into the article.
<
y = lambda { |f| (lambda { |x| lambda { |*args| (f.call(x.call(x))).call(*args) }}).call(lambda { |x| lambda { |*args| (f.call(x.call(x))).call(*args) }})}
b = y.call(lambda { |f| lambda {|i| if i == 0 then 1 else i * (f.call(i-1)) end }})
puts(b.call 5) # 120
</syntaxhighlight>
[[User:Subwy|Subwy]] ([[User talk:Subwy|talk]]) 10:58, 10 December 2008 (UTC)
Line 148 ⟶ 159:
[[Fixed point combinator]] → {{no redirect|1=Fixed-point combinator}} –
Per WP:HYPHEN and a good proportion of sources.
*'''Support''' in accord with Wikipedia's style guidelines – the appropriate point of reference for, um, ... points of style on Wikipedia. <
*'''<s>Meh</s>''' '''Weak support''' In my experience "fixed point combinator" is more common than "fixed-point combinator". Google Scholar seems to confirm this [http://scholar.google.com/scholar?hl=en&q=%22fixed-point+combinator%22&btnG=Search&as_sdt=0%2C5&as_ylo=&as_vis=0], although the margins are not very wide. I would have to consult a few standard references first to form a strong opinion, as those would carry more weight. English is not my native language, but isn't there are rule for (not) using a hyphen for words of the form "(''adjective'' ''noun'') ''noun''" where (''adjective'' ''noun'') is used as an adjective? —''[[User:Ruud Koot|Ruud]]'' 12:07, 20 October 2011 (UTC)
**Your opinion is no less valid as a second-language speaker, Ruud. Where minority usage out there accords with WP's in-house style, we usually go with it, favouring internal consistency over inconsistency with ''some'' external sources. Here, there's a good reason to hyphenate, especially for non-experts: is it a point combinator that is fixed? And it's a compound adjective, isn't it, qualifying "combinator" the noun? "Point" might be a noun on the second "rank", but that's within the compound adjective.
*** I checked the indexes of a few of the books on my shelf and found one instance of "fixed-point combinator" and two of "[[fixed point theorem]]". The hyphenated could possibly be less ambiguous for some people. You might want to check with [[Wikipedia:WikiProject Mathematics]] before (or after ;) moving all the theorems, though. Common spellings of obscure names don't always agree with common sense. —''[[User:Ruud Koot|Ruud]]'' 19:54, 20 October 2011 (UTC)
****Most of the articles are already correctly punctuated. I updated [[Fixed-point theorem]] to reflect that. [[User:Dicklyon|Dicklyon]] ([[User talk:Dicklyon|talk]]) 20:59, 20 October 2011 (UTC)
* '''Support''' – when the hyphen is grammatically correct and useful, it is WP style to use it, other styles notwithstanding. [[User:Dicklyon|Dicklyon]] ([[User talk:Dicklyon|talk]]) 20:34, 20 October 2011 (UTC)
* '''Support''' It's not a "point combinator" that happens to be fixed; it's a combinator that has something to do with fixed points. A hyphen leaves no ambiguity. It is true that present-day usage often omits it, and I actually suspect that's because they've stopped teaching it. But it's still in standard use in many media. I'd normally use a hyphen for something like this. [[User:Michael Hardy|Michael Hardy]] ([[User talk:Michael Hardy|talk]]) 14:08, 21 October 2011 (UTC)
:''The above discussion is preserved as an archive of a [[WP:RM|requested move]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.''</div><!-- Template:RM bottom -->
== Can we set out the field at the beginning? ==
Line 173 ⟶ 184:
There are two fix point combinators in Haskell, one is code-replicating, another is through sharing:
<
fix f = f (fix f)
fix f = x where x = f x
</syntaxhighlight>
The second one lends itself naturally to corecursive definitions, like
<
fibs = fix ((0:) . (1:) . next)
where
next (a:t@(b:_)) = (a+b):next t
</syntaxhighlight>
Used w/ the first fix, it still works though runs in quadratic time.
Line 208 ⟶ 219:
Here's a tested PHP 5.4 implementation for the Y Combinator function:
<
function Y(callable $f)
{
Line 221 ⟶ 232:
return $funcA($funcA);
}
</syntaxhighlight>
And the factorial example applied to it:
<
$factorial = Y(
function ($fac)
Line 240 ⟶ 251:
$result = $factorial(5); // 120
</syntaxhighlight>
[[User:Jazzer7|Jazzer7]] ([[User talk:Jazzer7|talk]]) 06:51, 6 June 2012 (UTC)
Line 377 ⟶ 388:
::::::: I think an intuitive (informal) notion of "value" that might work for you is that lambda terms are their own values so long as "equals" is expanded to convertibility as per the usual axioms of LC. This is a bit like providing semantics for lambda calculus using a term algebra generated by the usual formation rules for lambda terms. A better notion of value is a Bohm tree, which makes explicit the value of a non-normalising term (it still has a value). [[User:Haklo|Haklo]] ([[User talk:Haklo|talk]]) 04:40, 15 January 2014 (UTC)
:::::::: I think a Bohm tree is OK for me as a value for LC. As I understand it, a bohm tree allows you to access parts of the value (like a record where some fields are given but not others). Does that help you in giving me a value for x = not x? Regards [[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 06:42, 15 January 2014 (UTC)
::::::::: I've revised the [[Bohm tree]] page, although I haven't put references in yet and the phrasing is awkward because I've tried to keep it non-mathematical (and so I didn't quote Barendregt). It may help giving "values" for terms that do not have normal forms, but I don't think you need it for the "not" example; I think the fixed point I gave for that earlier should serve? [[User:Haklo|Haklo]] ([[User talk:Haklo|talk]]) 12:45, 16 January 2014 (UTC)
:::::::::: The point is; your right and I was wrong. The Y combinator applied to a function must represent a single value in the LC ___domain. Its a definitional thing. The ___domain of LC is not necessarily the same as the ___domain of the function. Crow must be eaten. I have added a section Values and domains, but of course feel to rewrite or modify. Your changes to the Bohm tree are good and make it more understandable. I get the motivation but I dont fully understand yet. [[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 14:09, 16 January 2014 (UTC)
==Its not magic==
Line 416 ⟶ 433:
[[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 07:26, 10 January 2014 (UTC)
==Minor changes==
I have done a little bit of editorial work mainly moving stuff around and trying to organize things. If something important to you has been lost add a note here. I hope the changes are acceptable for everybody.
[[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 05:06, 16 January 2014 (UTC)
A somewhat clumsy introduction section, but I wanted to cover the misunderstandings I have seen in the past.
[[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 04:58, 20 January 2014 (UTC)
==Recursion / Corecursion==
fix :: (a -> a) -> a
fix f = f (fix f) -- non-sharing fixed-point, for recursive definitions
-- alternative:
-- fix f = let x = f x in x -- sharing fixed-point, for corecursive definitions
Are the comments correct??? From my reading, the two forms have nothing to do with recursion and corecursion. Both are recursive definitions; one is the lifted form of the other.
[[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 03:41, 4 February 2014 (UTC)
==Another C++ example==
I don't see enough merit in having yet another C++ example. This is not a collection of different implementations of the Y combinator. See [[rosettacode.org]] for that. So I have taken it out.
If I was to be picky I would say.
* Y combinator should be templated (not int -> int).
* Dont need main (so remove iostream, cassert)
But you do all that and it still adds nothing to the understanding of the Y combinator. Sorry.
<syntaxhighlight lang="cpp">
#include <functional>
#include <iostream>
#include <cassert>
using std::function;
// Y-combinator compatible factorial
int fact(function<int(int)> f,int v)
{
if(v == 0)
return 1;
else
return v * f(v -1);
}
// Y-combinator for the int type
function<int(int)>
y(function<int(function<int(int)>,int)> f)
{
return [=](int x) {
return f(y(f), x);
};
}
int main(void)
{
function<int(int)> factorial = y(fact);
assert(y(fact)(5) == fact(y(fact), 5));
std::cout << factorial(5) << std::endl;
return 0;
}
</syntaxhighlight>
[[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 05:39, 30 October 2014 (UTC)
== Wolfram example ==
I think this example does not add anything. Perhaps you would like to add it to,
* http://rosettacode.org/wiki/Y_combinator
''For example, a Y-combinator implementation of factorial in the [[Wolfram Language]] would be''
<syntaxhighlight lang=ocaml>Y = Function[f, #[#]&[Function[g, f[g[g][##]&]]]];
factorial = Y[Function[f, If[# < 1, 1, # f[# - 1]] &]];
factorial[6] (*Yields 120*)</syntaxhighlight>
[[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 02:20, 26 May 2015 (UTC)
== External links modified ==
Hello fellow Wikipedians,
I have just modified 2 external links on [[Fixed-point combinator]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=774009465 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/20110822202348/http://mvanier.livejournal.com/2897.html to http://mvanier.livejournal.com/2897.html
*Added archive https://web.archive.org/web/20110822202348/http://mvanier.livejournal.com/2897.html to http://mvanier.livejournal.com/2897.html
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> 19:07, 5 April 2017 (UTC)
== Needs to be rewritten, or a very good review ==
I fixed some parts, later I saw here, some comments proposing similar fixes.
I think that the main problem of this article is that it seems to be based in some notes about scheme.
Scheme is based on lambda calculus, it is not lambda calculus.
In lambda calculus nor combinator logic, one can't write recursive definitions like fact x = if x=0 then 1 else x*fact (x-1)
that is the reason for a fixed point combinator. <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/201.124.239.99|201.124.239.99]] ([[User talk:201.124.239.99#top|talk]]) 13:25, 25 April 2017 (UTC)</small> <!--Autosigned by SineBot-->
== Values and domains section is obscure ==
I can not understand what is this section about, it has some misconceptions repeated along all the article, let's see what I mean.
:Every expression has one value. This is true in general mathematics and it must be true in lambda calculus. This means that in lambda calculus, applying a fixed point combinator to a function gives you an expression whose value is the fixed point of the function.
Lambda calculus is a theory of computable functions, a function is a relation between to sets, i.e. it has one input and one output.
Higher order functions, may have functions in their ___domain and codomain. Fixed point combinators are higher order functions.
# fac : (Int -> Int) -> (Int -> Int)
# fix : (t -> t) -> t with [t := (Int -> Int)]
--------
:3. fix fac :: Int -> Int
:However this is a value in the [[Deductive lambda calculus#Domain of lambda calculus|lambda calculus ___domain]], it may not correspond to any value in the ___domain of the function, so in a practical sense it is not necessarily a fixed point of the function, and only in the lambda calculus ___domain is it a fixed point of the equation.
What does it mean? Should I have to read the whole lambda calculus ___domain to know what is going on?
:For example, consider,
:: <math> x^2 = -1 \Rightarrow x = \frac{-1}{x} \Rightarrow f\ x = \frac{-1}{x} \land \textsf{Y}\ f = x</math>
:[[Church encoding#Division|Division]] of [[Church encoding#Signed numbers|Signed numbers]] may be implemented in the Church encoding, so ''f'' may be represented by a lambda term. This equation has no solution in the real numbers. But in the ___domain of the [[complex number]]s ''i'' and ''-i'' are solutions. This demonstrates that there may be solutions to an equation in another ___domain. However the lambda term for the solution for the above equation is weirder than that. The lambda term <math>Y\ f</math> represents the state where x could be either ''i'' or ''-i'', as one value. The information distinguishing these two values has been lost, in the change of ___domain.
What does this mean? What does the formulas refer to?
Church numerals are a representation for natural numbers with lambda expressions to establish a correspondence with primitive recursive functions can be represented in lambda calculus.
There are not divisions between naturals, 1/2 = 0.5, a rational.
there are no subtractions among naturals 1-2=-1, a negative integer number. There are quotient and reminder of natural numbers, and a monus, not minus operator 1 monus 2 = 0. One can build representations for integers and rationals within lambda calculus, but those are not Church numerals.
:For the lambda calculus mathematician, this is a consequence of the definition of lambda calculus. For the programmer, it means that the beta reduction of the lambda term will loop forever, never reaching a normal form.
The reduction order depends on the profession of the reader?
For this reasons this section should be deleted! <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/201.124.239.99|201.124.239.99]] ([[User talk:201.124.239.99#top|talk]]) 23:33, 25 April 2017 (UTC)</small> <!--Autosigned by SineBot-->
: See the wiki page on Church encoding. In fact negative numbers may be represented in lambda calculus. Also division may be implemented.
: In fact any data type can be.
: Pure mathematicians are interested in lambda calculus as a system with it's own ___domain. Computer programmers just want to use lambda expressions.
: [[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 01:08, 19 May 2017 (UTC)
== External links modified ==
Hello fellow Wikipedians,
I have just modified 4 external links on [[Fixed-point combinator]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=803338098 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/20140408014716/http://cs.anu.edu.au/courses/COMP3610/lectures/Lambda.pdf to http://cs.anu.edu.au/courses/COMP3610/lectures/Lambda.pdf
*Added archive https://web.archive.org/web/20090113202334/http://www.latrobe.edu.au/philosophy/phimvt/joy/j05cmp.html to http://www.latrobe.edu.au/philosophy/phimvt/joy/j05cmp.html
*Added archive https://web.archive.org/web/20061110043130/http://use.perl.org/~Aristotle/journal/30896 to http://use.perl.org/~Aristotle/journal/30896
*Added archive https://web.archive.org/web/20090314203740/http://bc.tech.coop/blog/070611.html to http://bc.tech.coop/blog/070611.html
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> 22:11, 1 October 2017 (UTC)
== External links modified (January 2018) ==
Hello fellow Wikipedians,
I have just modified one external link on [[Fixed-point combinator]]. Please take a moment to review [[special:diff/821673604|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/20160304101809/http://osdir.com/ml/lang.haskell.cafe/2003-10/msg00211.html to http://osdir.com/ml/lang.haskell.cafe/2003-10/msg00211.html
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> 23:08, 21 January 2018 (UTC)
== Confusing/contradictory claims about lambda calculus semantics ==
This is mostly about the "values and domains" section, but there are also various other comments scattered throughout the article that I think need clearing up.
I'm not an expert, but it seems to me that there are at least two ways to think about the semantics of untyped lambda calculus. One is the "___domain" approach, explained (though not very clearly) in the linked [[Deductive lambda calculus]] article. In this interpretation every lambda expression has a value, even the non-halting ones. But there is also the more obvious semantics where each lambda expression is a partial function. It has a value if it beta reduces to a normal form, but otherwise it doesn't have a value. I believe that both of these are consistent and it's really a matter of choice which one to use.
The issue is that the article sometimes talks in terms of one and sometimes in terms of the other. For example, in the lede it states
: a fixed-point combinator (or fixpoint combinator) is a higher-order function that returns some fixed point of its argument function, if one exists.
This sounds like it's taking the partial function view: the argument function might not have a fixed point, and in that case the fixed-point combinator doesn't return a value.
(Though now I come to think of it, this statement is not actually correct. Consider the Y combinator applied to the identity function. It's easy to see that no value is returned in this case, even though any lambda term at all is a fixed point of the identity function. I guess the correct statement would be that it returns some fixed point of its argument function if it halts.)
On the other hand the article also makes statements like
: In the classical untyped lambda calculus, every function has a fixed point
which seems to me to be true in the ___domain interpretation but not in the partial function interpretation. (Although I could be wrong about that.) It also makes statements like
: Every expression has one value. This is true in general mathematics and it must be true in lambda calculus.
Which seems like it's trying to justify the ___domain semantics as the only true semantics of the lambda calculus. But really it's just a false statement, since there's nothing to stop you defining a system where an expression might have many or no values, and the partial function semantics is such a system (I think).
So it seems to me that the article has sort of mixed up two different views about the semantics of the lambda calculus and also tried to present one of them as the only semantics, without flagging up that this is a choice. I would try to fix this myself but I don't feel I have the expertise to be sure I'm getting it right - I'm just mentioning this because I think it needs attention from someone who knows what they're doing.
[[User:Nathanielvirgo|Nathaniel Virgo]] ([[User talk:Nathanielvirgo|talk]]) 04:28, 17 October 2023 (UTC)
== Article is unintelligible ==
The article, as currently written, is unintelligible to anybody who isn't already an expert in the field.
The article needs to be rewritten from the beginning, in such a way as to answer the question "What is a fixed-point combinator?" '''in terms that can be understood by somebody who does not already know the answer.'''
[[User:Geoffrey.landis|Geoffrey.landis]] ([[User talk:Geoffrey.landis|talk]]) 20:05, 21 May 2025 (UTC)
| |||