Strange behavior with delayed objects

Strange behavior with delayed objects

[user8472]

I am currently working through SICP using Guile. I have found some strange
behavior when doing the exercises in chapter 3.5. I am running Guile 1.4
installed via Fink on Mac OS X 10.6, all latest patches installed. The
problem also exists in Guile 1.8.6.

This code works fine (and computes e):
  (define y (integral (delay dy) 1 0.001))
  (define dy (stream-map (lambda (x) x) y))
  (stream-ref y 1000)

The following code *should* be identical:
  (define (solve f y0 dt)
    (define y (integral (delay dy) y0 dt))
    (define dy (stream-map f y))
    y)
  (solve (lambda (x) x) 1 0.001)

But it yields the error message:
standard input:7:14: While evaluating arguments to stream-map in expression
(stream-map f y):
standard input:7:14: Unbound variable: y
ABORT: (unbound-variable)

So when embedded in a procedure definition, the (define y ...) does not
work, whereas outside the procedure it works fine.

What am I doing wrong here? I can post the auxiliary code (i.e., the
definitions of integral, stream-map etc.) if necessary, too.
-- 
View this message in context: http://old.nabble.com/Strange-behavior-with-delayed-objects-tp28443452p28443452.html
Sent from the Gnu - Guile - User mailing list archive at Nabble.com.

Re: Strange behavior with delayed objects

[Linas Vepstas]

On 4 May 2010 01:32, user8472 <head_over_heels@freenet.de> wrote:
>
> I am currently working through SICP using Guile. I have found some strange
> behavior when doing the exercises in chapter 3.5. I am running Guile 1.4
> installed via Fink on Mac OS X 10.6, all latest patches installed. The
> problem also exists in Guile 1.8.6.
>
> This code works fine (and computes e):
>  (define y (integral (delay dy) 1 0.001))
>  (define dy (stream-map (lambda (x) x) y))
>  (stream-ref y 1000)
>
> The following code *should* be identical:
>  (define (solve f y0 dt)
>    (define y (integral (delay dy) y0 dt))
>    (define dy (stream-map f y))
>    y)
>  (solve (lambda (x) x) 1 0.001)
>
> But it yields the error message:
> standard input:7:14: While evaluating arguments to stream-map in expression
> (stream-map f y):
> standard input:7:14: Unbound variable: y
> ABORT: (unbound-variable)

You should use let*, not define, for this.

The problem is that when using define like this, there is no
gaurentee that th defines will be done in the order that
you typed them in.  This is the reason why let* exists -- so
that definitions can be done in the order in which they are
listed.  (it is not enough to use let, you must use let*)

I believe that SICP explains this somewhere ...

--linas

Re: Strange behavior with delayed objects

[user8472]

Thanks for your reply. Yes, SICP introduces "let*" in chapter 4.1. The
current exercise is in chapter 3.5, though ;^)

Your suggestion is definitely a step in the right direction. However, it
does not yet solve the problem. The code
  (define (solve f y0 dt)
    (let* ((y (integral (delay dy) y0 dt))
           (dy (stream-map f y)))
      y))
  (stream-cdr (solve (lambda (x) x) 1 0.001))

still produces the error message:
streams.scm:609:21: In expression (force delayed-integrand):
streams.scm:609:21: Unbound variable: dy
ABORT: (unbound-variable)

According to R5RS (quote) "the 'let*' is similar to 'let', but the bindings
are performed sequentially from left to right [...] Thus the second binding
is done in an environment in which the first binding is visible, and so on."
To my understanding, this implies that the binding of "y" is done in an
environment visible to "dy", but not vice versa. (Equivalent to nested "let"
blocks.)

R5RS talks about another method named "letrec" which appears to do what I
want. However, when replacing "let*" by "letrec" above, the error message of
  (solve (lambda (x) x) 1 0.001)

becomes
streams.scm:601:14: While evaluating arguments to stream-map in expression
(stream-map f y):
streams.scm:601:14: Variable used before given a value: y
ABORT: (unbound-variable)

So something is still not quite right.



Linas Vepstas-3 wrote:
> 
>> This code works fine (and computes e):
>>  (define y (integral (delay dy) 1 0.001))
>>  (define dy (stream-map (lambda (x) x) y))
>>  (stream-ref y 1000)
> [...]
> 
> You should use let*, not define, for this.
> 
> The problem is that when using define like this, there is no
> gaurentee that th defines will be done in the order that
> you typed them in.  This is the reason why let* exists -- so
> that definitions can be done in the order in which they are
> listed.  (it is not enough to use let, you must use let*)
> 
> I believe that SICP explains this somewhere ...
> 
> --linas
> 

-- 
View this message in context: http://old.nabble.com/Strange-behavior-with-delayed-objects-tp28443452p28450337.html
Sent from the Gnu - Guile - User mailing list archive at Nabble.com.

Re: Strange behavior with delayed objects

[Linas Vepstas]

On 4 May 2010 11:59, user8472 <head_over_heels@freenet.de> wrote:

>
> becomes
> streams.scm:601:14: While evaluating arguments to stream-map in expression
> (stream-map f y):
> streams.scm:601:14: Variable used before given a value: y
> ABORT: (unbound-variable)
>
> So something is still not quite right.

My bad, I completely failed to notice that delayed evaluation
was a part of the problem.  Can you simplify the example to
its barest elements that still provoke the error? Hopefully,
this will provide a clue to what the true as to what the
problem is. (Not having seen the definition of "integral",
I'm wondering whether some failure to initialize y to y0
might have something to do with it ... some missing force
somewhere ...  but that's a wild and probably wrong guess).

--linas

Re: Strange behavior with delayed objects

[user8472]

Please find the code for streams and the integration below. The macro
definition of cons-stream is not from SICP since it is implementation
dependent (for this reason I have also not tried the code on other Scheme
implementations except Guile). So this could be buggy.

I don't think it is only an issue of delay/force mismatch - the strange
thing is that the code *works* at the REPL, but does *not work* inside a
procedure definition.

<code>
;; Basic stream operations
(define-macro (cons-stream a b)
  `(cons ,a (delay ,b)))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define the-empty-stream '())
(define stream-null? null?)
(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

;; Other generic stream operations
(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))
(define (add-streams s1 s2)
  (stream-map + s1 s2))
(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

;; Integral with delayed integrand
(define (integral delayed-integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (let ((integrand (force delayed-integrand)))
                   (add-streams (scale-stream integrand dt)
                                int))))
  int)

;; The troublesome procedure
(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)

;; This works
(define y (integral (delay dy) 1 0.001))
(define dy (stream-map (lambda (x) x) y))
(stream-ref y 1000)

;; This doesn't work
;(stream-ref (solve (lambda (x) x) 1 0.001) 1000)
</code>



Linas Vepstas-3 wrote:
> 
> On 4 May 2010 11:59, user8472 <head_over_heels@freenet.de> wrote:
> [...]
>> streams.scm:601:14: While evaluating arguments to stream-map in
>> expression
>> (stream-map f y):
>> streams.scm:601:14: Variable used before given a value: y
>> ABORT: (unbound-variable)
>>
>> So something is still not quite right.
> 
> My bad, I completely failed to notice that delayed evaluation
> was a part of the problem.  Can you simplify the example to
> its barest elements that still provoke the error? Hopefully,
> this will provide a clue to what the true as to what the
> problem is. (Not having seen the definition of "integral",
> I'm wondering whether some failure to initialize y to y0
> might have something to do with it ... some missing force
> somewhere ...  but that's a wild and probably wrong guess).
> 

-- 
View this message in context: http://old.nabble.com/Strange-behavior-with-delayed-objects-tp28443452p28483371.html
Sent from the Gnu - Guile - User mailing list archive at Nabble.com.

Re: Strange behavior with delayed objects

[Linas Vepstas]

On 7 May 2010 03:09, user8472 <head_over_heels@freenet.de> wrote:
>
> Please find the code for streams and the integration below.
> ;; The troublesome procedure
> (define (solve f y0 dt)
>  (define y (integral (delay dy) y0 dt))
>  (define dy (stream-map f y))
>  y)
>
> ;; This works
> (define y (integral (delay dy) 1 0.001))
> (define dy (stream-map (lambda (x) x) y))
> (stream-ref y 1000)
>
> ;; This doesn't work
> ;(stream-ref (solve (lambda (x) x) 1 0.001) 1000)
> </code>

Well, you modified your code enough so that let* now works fine,
at least for me:

guile> (define (solve f y0 dt)
... (let* ((y (integral (delay dy) y0 dt))
... (dy (stream-map f y))
... )
... y))
guile> (stream-ref (solve (lambda (x) x) 1 0.001) 1000)
2.7169239322359

Superficially, I want to say "this is why let* was invented, to
ensure ordering of definitions".  In practice, I see that dy is
used in both, so there's a circular reference going on here.
The thing that saves you, and allows the  let* to work, is the
(delay dy) which avoids evaluating dy (which is undefined,
at the time its encountered).  Without the delay, the circular
references would cause the whole thing would fall apart,
and not even letrec would save you.

As proof of this, here's another example, without let*, which
does enforce ordering (and which depends on the (delay dy)
to avoid the "use of variable dy before its defined" error):

guile> (define (solve f y0 dt)
... (define y (integral (delay dy) y0 dt))
... (let ((dy (stream-map f y)))
... y))
guile> (stream-ref (solve (lambda (x) x) 1 0.001) 1000)
2.7169239322359
guile>


I'm an amateur at scheme, but I beleive what I say is more
or less correct ...

--linas

Re: Strange behavior with delayed objects

[Linas Vepstas]

BTW, this is guile version 1.8.7, for me.

--linas

On 10 May 2010 11:26, Linas Vepstas <linasvepstas@gmail.com> wrote:
> On 7 May 2010 03:09, user8472 <head_over_heels@freenet.de> wrote:
>>
>> Please find the code for streams and the integration below.
>> ;; The troublesome procedure
>> (define (solve f y0 dt)
>>  (define y (integral (delay dy) y0 dt))
>>  (define dy (stream-map f y))
>>  y)
>>
>> ;; This works
>> (define y (integral (delay dy) 1 0.001))
>> (define dy (stream-map (lambda (x) x) y))
>> (stream-ref y 1000)
>>
>> ;; This doesn't work
>> ;(stream-ref (solve (lambda (x) x) 1 0.001) 1000)
>> </code>
>
> Well, you modified your code enough so that let* now works fine,
> at least for me:
>
> guile> (define (solve f y0 dt)
> ... (let* ((y (integral (delay dy) y0 dt))
> ... (dy (stream-map f y))
> ... )
> ... y))
> guile> (stream-ref (solve (lambda (x) x) 1 0.001) 1000)
> 2.7169239322359
>
> Superficially, I want to say "this is why let* was invented, to
> ensure ordering of definitions".  In practice, I see that dy is
> used in both, so there's a circular reference going on here.
> The thing that saves you, and allows the  let* to work, is the
> (delay dy) which avoids evaluating dy (which is undefined,
> at the time its encountered).  Without the delay, the circular
> references would cause the whole thing would fall apart,
> and not even letrec would save you.
>
> As proof of this, here's another example, without let*, which
> does enforce ordering (and which depends on the (delay dy)
> to avoid the "use of variable dy before its defined" error):
>
> guile> (define (solve f y0 dt)
> ... (define y (integral (delay dy) y0 dt))
> ... (let ((dy (stream-map f y)))
> ... y))
> guile> (stream-ref (solve (lambda (x) x) 1 0.001) 1000)
> 2.7169239322359
> guile>
>
>
> I'm an amateur at scheme, but I beleive what I say is more
> or less correct ...
>
> --linas
>

Re: Strange behavior with delayed objects

[user8472]

Thanks for your response. I have tried both of your suggestions and they
don't work on Guile 1.4 and Guile 1.8.6. I have installed them using Fink on
MacOS X 10.6, all latest patches installed. Guile 1.8.7 is not yet
distributed with Fink, so I used Ubuntu Linux 10.4 with Guile 1.8.7 to test
your suggestion. I also checked Guile 1.8.6 on OpenSUSE Linux.

On all of these systems the code you have posted always returns an error
"Unbound variable: dy".

To my understanding in your construction "dy" is defined in an environment
INSIDE the environment where "y" is defined. This *should* result in "dy"
being undefined when you refer to it in the definition of "y". As far as I
can see "y" and "dy" *must* be defined in the same environment, otherwise
the circular reference cannot work.

Is it possible that you first typed the (define y ...) and (define dy ...)
things at the REPL (thereby defining them in the global environment)? In
that case, the procedures you have defined would not work, but the
definition of "y" would simply refer to the definition of "dy" in the global
environment, thereby masking the true problem.



Linas Vepstas-3 wrote:
> 
> Well, you modified your code enough so that let* now works fine,
> at least for me:
> [...]
> guile> (stream-ref (solve (lambda (x) x) 1 0.001) 1000)
> 2.7169239322359
> 
> Superficially, I want to say "this is why let* was invented, to
> ensure ordering of definitions".  In practice, I see that dy is
> used in both, so there's a circular reference going on here.
> 

-- 
View this message in context: http://old.nabble.com/Strange-behavior-with-delayed-objects-tp28443452p28517284.html
Sent from the Gnu - Guile - User mailing list archive at Nabble.com.

Re: Strange behavior with delayed objects

[Linas Vepstas]

On 10 May 2010 16:36, user8472 <head_over_heels@freenet.de> wrote:

> Is it possible that you first typed the (define y ...) and (define dy ...)
> things at the REPL (thereby defining them in the global environment)?

Yes. Stupid me.  I admit, I just cut-n-pasted your code
into the terminal, without really thinking about what it
does ... maybe its time I shut up & let someone else
chip in.

--linas
.

Re: Strange behavior with delayed objects

[user8472]

OK, I have found a solution. The point is that in section 4.2.2 of R5RS it is
explicitly stated that mutually recursive defines must not refer to those
variables. The solution is thus to wrap the defines in (lambda () ...)s.

<code>
(define (solve f y0 dt)
  (define (y) (integral (delay (dy)) y0 dt))
  (define (dy) (stream-map f (y)))
  (y))

(debug-set! stack 2000000)
(stream-ref (solve (lambda (x) x) 1 0.001) 1000)
</code>

will produce the correct answer. The downside is that the function calls
will be wrapped recursively which necessitates increasing the stack size.
Plus, it's much slower this way. But it works.
-- 
View this message in context: http://old.nabble.com/Strange-behavior-with-delayed-objects-tp28443452p28564620.html
Sent from the Gnu - Guile - User mailing list archive at Nabble.com.

Re: Strange behavior with delayed objects

[Andy Wingo]

Hello,

On Tue 04 May 2010 17:21, Linas Vepstas <linasvepstas@gmail.com> writes:

> On 4 May 2010 01:32, user8472 <head_over_heels@freenet.de> wrote:
>>
>> This code works fine (and computes e):
>>  (define y (integral (delay dy) 1 0.001))
>>  (define dy (stream-map (lambda (x) x) y))
>>  (stream-ref y 1000)
>>
>> The following code *should* be identical:
>>  (define (solve f y0 dt)
>>    (define y (integral (delay dy) y0 dt))
>>    (define dy (stream-map f y))
>>    y)
>>  (solve (lambda (x) x) 1 0.001)
>
> You should use let*, not define, for this.

Incidentally, R6RS would expand out these internal defintions using
letrec*, which would be equivalent to let* in this case.

Andy
-- 
http://wingolog.org/

Re: Strange behavior with delayed objects

[Andy Wingo]

Hello,

On Fri 14 May 2010 23:53, user8472 <head_over_heels@freenet.de> writes:

> The solution is thus to wrap the defines in (lambda () ...)s.
>
> <code>
> (define (solve f y0 dt)
>   (define (y) (integral (delay (dy)) y0 dt))
>   (define (dy) (stream-map f (y)))
>   (y))
>
> (debug-set! stack 2000000)
> (stream-ref (solve (lambda (x) x) 1 0.001) 1000)
> </code>
>
> will produce the correct answer. The downside is that the function calls
> will be wrapped recursively which necessitates increasing the stack size.
> Plus, it's much slower this way. But it works.

The fact that it's slow is an implementation detail. Lambda expressions
are simply abstractions over scope -- they do not necessitate the
creation of closures. Guile 2.0 is already much faster for this case,
I believe, and with a proper inliner, y and dy would not actually be
implemented with functions.

Andy
-- 
http://wingolog.org/