[racket] Lambda, object identity & streams
In the process of toying with streams & memoization (more below), I've
tripped over the question: when does Racket consider two lambdas to be
identical?
The reference mentions re-use of procedure objects, but omits (gory?)
details. Can you shed some light, or does this question prod the wrong
direction?
I'd also be glad for some high-level insight if this is too
implementation-specific.
(define (test) (lambda () #t))
(define foo (test))
(define bar (test))
(eq? foo bar)
;; => #t
(define (test/2 x) (lambda () x))
(define baz (test/2 'same))
(define qux (test/2 'same))
(eq? baz qux)
;; => #f
(define (test/3 x)
x
(lambda () #t))
(define doh (test/3 'something))
(define reh (test/3 'else))
(eq? doh reh)
;; => #t
What got me started on this: I'm currently trying to grok streams as
explained in SICP.
Their implementation relies on the delayed (and optimized) evaluation of
a streams cdr. This is readily achieved using simple lambda-wrapping macros.
Of course, the optimization (memoization) only really works if recurrent
access of the same stream element actually points to 'the same thing'.
That condition can be hard to tell (for the programmer) when streams are
defined recursively / in terms of themselves.
Most specifically, I believe Exercise 3.63 puts the finger on it (below
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.3).
I'm confused wether the crux here is 'just' the environment (the
function binds arguments, this creates a new environment for every
procedure object, memoization becomes ineffectual) or if some nuances
regarding lexical scope, macros and phase times are present, too.
;; naive stream implementation, for completeness
(define (stream-car x)
(car x))
(define (stream-cdr x)
(force (cdr x)))
(define-syntax-rule (cons-stream a b)
(cons a (delay b)))
(define-syntax-rule (delay x)
(memo-proc (lambda () x)))
(define (memo-proc proc)
(let ([already-run? #f]
[result #f])
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? #t)
result)
result))))
(define (force x) (x))