1

I am brushing up on my low Racket knowledge and came across this streams in racket excellent post. My question is about this snip:

(define powers-of-two
    (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2)))))])
        (lambda () (f 2))))

I understand the reason for the 'inner lambdas' but why did the OP use a lambda for the whole function? Couldn't it be done like this just as effectively?

(define (powers-of-two)
    (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2)))))])
       (f 2)))

I experimented and see no difference. My question is whether this is just a matter of style, or if there is some reason that the former is preferable.

Community
  • 1
  • 1
GregT
  • 1,300
  • 3
  • 16
  • 25

2 Answers2

3

There is no difference. Since f in the second example doesn't close over anything, it can be lifted outside the powers-of-two function, which is equivalent to the first example.

One reason why the first might be preferable is that there is only ever one f function that needs to be created. With the second one, a new f function would be created every time someone called (powers-of-two).

I tried timing them both though, and neither was significantly faster than the other.

Alex Knauth
  • 8,133
  • 2
  • 16
  • 31
2
(define (name arg)
   arg)

This is the short form of writing:

(define name 
   (lambda (arg)
      arg))

So what happens with the first example is that the letrect happens right away and the function returned would be (lambda () (f 2)) with f in it's closure.

The second makes a procedure called powers-of-two that , when applied (powers-of-two) will return the same as the first powers-of-two is.. Think of it as a powers-of-two-generator.

Thus:

(define powers-of-two
    (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2)))))])
        (lambda () (f 2))))

(define (powers-of-two-generator)
    (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2)))))])
       (f 2)))

(powers-of-two) ; ==> (2 . procedure)

(define powers-of-two2 (powers-of-two-generator)) ; ==> procedure

(powers-of-two2) ; ==> (2 . procedure)

Do you see the difference?

Sylwester
  • 47,942
  • 4
  • 47
  • 79
  • Excellent explanation. Thanks for taking the time. – GregT Oct 31 '13 at 00:00
  • Sylwester, That's not what I get when I evaluate your example. I get `(powers-of-two)` -> `'(2 . #)` like you do, but calling `(powers-of-two-generator)` gives me `'(2 . #)`, not `#`. So then `powers-of-two2` is not a function, and it raises an error when called. – Alex Knauth Jan 23 '16 at 16:51
  • @AlexKnauth You are right. Looking at the text it seems I assume the same lambda expression as body of `letrec` even when it isn't. As your answer suggests it's just an optimization. Some implementations might constant fold these so they turn into the exact same code. I'll upvote your answer and delete this tomorrow. – Sylwester Jan 25 '16 at 15:24