Content deleted Content added
Notification of altered sources needing review #IABot (v1.3beta4) (DragonflySixtyseven) |
→Article is unintelligible: new section |
||
| (19 intermediate revisions by 11 users not shown) | |||
Line 1:
{{summary in|Lambda calculus}}
{{WikiProject
{{WikiProject Computer science|importance=Mid}}
{{WikiProject Mathematics|priority=low}}
}}
{{To do}}
Line 23 ⟶ 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 77 ⟶ 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 98 ⟶ 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 152 ⟶ 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 177 ⟶ 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 212 ⟶ 219:
Here's a tested PHP 5.4 implementation for the Y Combinator function:
<
function Y(callable $f)
{
Line 225 ⟶ 232:
return $funcA($funcA);
}
</syntaxhighlight>
And the factorial example applied to it:
<
$factorial = Y(
function ($fac)
Line 244 ⟶ 251:
$result = $factorial(5); // 120
</syntaxhighlight>
[[User:Jazzer7|Jazzer7]] ([[User talk:Jazzer7|talk]]) 06:51, 6 June 2012 (UTC)
Line 500 ⟶ 507:
''For example, a Y-combinator implementation of factorial in the [[Wolfram Language]] would be''
<
factorial = Y[Function[f, If[# < 1, 1, # f[# - 1]] &]];
factorial[6] (*Yields 120*)</
[[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 02:20, 26 May 2015 (UTC)
Line 519 ⟶ 526:
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)
| |||