[racket] Lambda, object identity & streams

From: J. Ian Johnson (ianj at ccs.neu.edu)
Date: Mon Apr 14 16:35:52 EDT 2014

Function equality is undecidable, so Racket makes no promises about when two function values will be considered equal. AFAIK, pointer-equality is as far as it goes.
Your first example illuminates where Racket performs some reasoning about necessary allocation. It turns out that thunk can be lifted out of the body of test. All invocations of test will point to that lifted value. Thus you get eq? values.
Your second example introduces a free variable that the function will have to close over. It cannot be lifted out of the body, so all calls will allocate a closure, producing different values.

Pointer equality is an abstraction-breaking yet necessary-for-performance feature of a high-level language. The best advice I can give you is to not depend on it for correctness -- only performance.
-Ian
----- Original Message -----
From: "Philipp Dikmann" <philipp at dikmann.de>
To: "Racket Users" <users at racket-lang.org>
Sent: Monday, April 14, 2014 4:20:43 PM GMT -05:00 US/Canada Eastern
Subject: [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))
____________________
  Racket Users list:
  http://lists.racket-lang.org/users

Posted on the users mailing list.