Geek asks and answers

Fixed point components

I am new to the world of fixed-point compilers , and I assume that they are used for recursion on anonymous lambdas, but I don’t know, I really could use them, or even could completely wrap my head around myself.

I saw an example in Javascript for Y-combinator , but could not run it successfully.

The question is can someone give an intuitive answer:

  • What are fixed-point combinators (not only theoretically, but also in the context of some example, to show what exactly is a fixed-point in this context)?
  • What are other kinds of fixed-point combinators besides Y-combinator?

Bonus points: . If the example is not only in one language, preferably in Clojure .

UPDATE:

I managed to find a simple example in Clojure , but it's still hard to understand Y-Combinator itself:

(defn Y [r]
  ((fn [f] (f f))
   (fn [f]
     (r (fn [x] ((f f) x))))))

Although this example is brief, it’s hard for me to understand what is going on inside the function. Any help provided would be helpful.

+5
source share
2 answers

Suppose you wanted to write a factorial function. Usually you write it something like

function fact(n) = if n=0 then 1 else n * fact(n-1)

But this uses explicit recursion. If you want to use Y-combinator instead, you can first abstract away from the fact somehow like

function factMaker(myFact) = lamba n. if n=0 then 1 else n * myFact(n-1)

(myFact), , "" , . "Y-ready", , Y-combinator.

Y-combinator factMaker -, .

newFact = Y(factMaker)

? . : , "" Y-combinator.

- . memoization . , , . , , -

loggingFact = LoggingY(factMaker)

LoggingY Y combinator, . , factMaker!

, Y-combinator , , Y ( Y).

+11

, Y. , fix,

fix f = f (fix f)

,

fix f = f (f (fix f))

... , - . . - , . http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes

+3

More articles:


All Articles