4 ms·
Fixed-point combinator
- konstantinua00 3y agoI don't get it example shows that it's y(g)->g(y(g)), not the opposite...
- toxik 3y agoNo, it shows that `Y g = g (Y g)`, so both ways.
- ted_dunning 3y agoTo clarify for people who are sloppy readers like me, the important difference here is the difference between `=` and `=>`, not the difference in notation between `Y(g)` and `Y g`.
- youzicha 3y agoIndeed. I think this something that people are often confused about, e.g. one blogger[0] comments: > The key to understanding the fixpoint theorem, for me anyway, was realizing that when it says FG=G, it does not mean that for every F there is a G such that by calling F with parameter G one can get back G. I mention this in the blog post, above. The equality operator in FG=G is the equivalence relation induced by the calculus rewriting relation: that is, it's the symmetric reflexive transitive closure of the rewriting step relation. When you look at the proof of the theorem, it actually works by constructing an expression G such that evaluating G produces, as an intermediate result, FG. There is no need for F to even be a function, and if F is a function it doesn't matter what, if anything, F would actually do when called, because the proof of the theorem doesn't involve calling F. I think the name "fixpoint combinator" is kindof bad, it it was called e.g. the "recursion combinator" I think people would find it more intuitive. [0] https://fexpr.blogspot.com/2013/07/bypassing-no-go-theorems.html?showComment=1385649732798#c4614180298503254427 https://fexpr.blogspot.com/2013/07/bypassing-no-go-theorems....
- genezeta 3y agoThe name, fixed point, is a more generic or general concept in mathematics. Given a function f, we say that an element c in the domain of f is a fixed point for f if it satisfies that f(c) = c. In a different nomenclature, if you consider f a "transformation", then c satisfies that it "remains fixed through the transformation". The fixed-point combinator is called so, because it "produces fixed-points for a function". That is, given a function f, then FPC(f) is a fixed-point for f. So, if we call c = FPC(f), then f(c) = c. Or, more classically f(FPC(f)) = FPC(f) or f(Y(f)) = Y(f). --- Note that when talking about fixed points in general, the domain of the f function is whatever -but usually you may have studied it with numbers-. But when talking about the fixed-point combinator the domain is functions themselves.
- youzicha 3y agoSure I understand that, but nevertheless I have seen at least 3 people who were confused in the same way. (c.f. https://youzicha.tumblr.com/post/728810860450136065 https://youzicha.tumblr.com/post/728810860450136065). I think the issue is that if you see an equation f(c) = c you think about trying to evaluate the function f at the point c, since that's what you do in almost all other situations involving a function call.
- svat 3y agoWhat do you mean by "the opposite"? In your notation, the example shows that Y(g) = g(Y(g)) which by the definition of the equals sign (A=B and B=A say the same thing), is the same as: g(Y(g)) = Y(g) — so Y(g) is a fixed point of g. What is the confusion?
- konstantinua00 3y agoconfusion in that if you treat lambda calculus as computation instead of "mathematical truths", then following the proof in the opposite direction requires conjuring out of thin air a complicated construction that isn't obvious from the state you'd have
- tromp 3y agoCuriously, Freek Wiedijk implemented a fixed point combinator in pure portable C99 in his 2014 IOCCC entry [1] that computes 10 factorial with no loops, as explained in [2]. [1] https://www.ioccc.org/2014/wiedijk/prog.c https://www.ioccc.org/2014/wiedijk/prog.c [2] https://www.ioccc.org/2014/wiedijk/hint.html https://www.ioccc.org/2014/wiedijk/hint.html
- bendsawyer 3y agoI had not realized that's where Y Combinator comes from... Recursion without self reference. Cool.
- ridiculous_fish 3y agoI have no background in combinatory logic, and so I've predictably never understood fixed-point combinators: 1. Every function has a fixed point. 2. A fixed-point combinator will compute it. So what is the fixed point of f(x) = x + 1? Also why doesn't this give us mathematical superpowers? Define f(x) = x iff x is a non-trivial zero of the Riemann zeta function...
- LudwigNagasena 3y agoEvery function in untyped lambda calculus has a fixed point. The fixed point of f(x) = x + 1 is garbage that cannot be decoded back into a number.
- ridiculous_fish 3y agoWe often extend arithmetic with new sorts of numbers to solve previously unsolvable equations like sqrt(-1) - is finding a fixed point of f(x) = x + 1 in this tradition? Does it point to an extension of arithmetic? Also I find this confusing: "Applied to a function with one variable, the Y combinator usually does not terminate" What does it mean for a function to terminate? Is it like the limit of a series?
- LudwigNagasena 3y ago> Does it point to an extension of arithmetic? Well, the fixed point of f(x)=x+1 can be interpreted as infinity. So kind of yes? > What does it mean for a function to terminate? Lambda calculus is a formal system that describes computation. So it literally means termination like when a computer program finishes running / halts. You have text which describes your program and you apply a few rewriting rules until you can’t. If at some point you can’t apply any more rewriting rules, you’ve reached a final state, your program has terminated. I suppose, when you apply Y combinator eg to f(x)=x+1 then you are just going to get x+1+1+… and so on as you keep applying rewriting rules.
- defrost 3y ago1. No. - https://en.wikipedia.org/wiki/Fixed-point_combinator https://en.wikipedia.org/wiki/Fixed-point_combinator In a generic context a fixed point combinator will only return a fixed point of a function if one exists. 2. No. (see: 1. above) Your confusion stems from the usual domain of application to function spaces where every function has a fixed point (ie. not all function spaces, just those that are made up of functions with at least one fixed point). From the link above: In the classical untyped lambda calculus, every function has a fixed point.
- stevefan1999 3y agoI had a feeling that Y combinator just sounds like recursion but with lazy evaluation...please correct me if I'm wrong.
- mrkeen 3y agoI don't think the laziness is as important as the namelessness. It's for when you want to recurse (a function calling its own name) in an environment where you don't have names (the lambda calculus).