Fixed point combinator usage? Why a stack overflow here?

Question

I am confused about something. I wanted to generate an example (in Clojure) demonstrating how a fixed point combinator could be used to evaluate the fixed point of a sequence that mathematically converges after an infinite number of applications but would, in fact, converge after a finite number of steps due to finite precision of floating points. I am apparently missing something here.

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

(defn simple-convergent [func]
  (fn [x]
    (if (zero? x)
      0.0
      (* 0.5 (func x)))))

I can then get

user=> ((Y simple-convergent) 0.)
0.0
user=> ((Y simple-convergent) 0.2)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

I don't understand this stack overflow. More generally, related to my earlier post, I am wondering if someone can present a "correct" version of a fixed point combinator which can be used to approximate fixed points of sequences in this fashion.

Should the last line perhaps be (func (* 0.5 x))? It looks like it's recurring with the same x forever. — Brian Carper
– Brian Carper, Commented Jul 13, 2010 at 23:30

Brian Carper · Accepted Answer · 2010-07-14 15:50:46Z

3

Thanks to Brian Carper for his (correct) answer as a comment. The corrected code

(defn simple-convergent [func]
  (fn [x]
    (if (zero? x)
      0.0
      (func (* 0.5 x)))))

behaves as I expected. My next project is to try to build a fixed point combinator which find unstable fixed points. I don't believe the Y combinator implemented above can do this.

edited Jul 14, 2010 at 15:50

Brian Carper

73.4k28 gold badges171 silver badges169 bronze badges

answered Jul 14, 2010 at 1:44

Gabriel Mitchell

9796 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Fixed point combinator usage? Why a stack overflow here?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related