[racket] Lambda, object identity & streams

From: Philipp Dikmann (philipp at dikmann.de)
Date: Mon Apr 14 16:20:43 EDT 2014

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))

Posted on the users mailing list.