Problem with (force (lazy (delay expr))) Alejandro Forero Cuervo (11 Jun 2004 07:08 UTC)
Re: Problem with (force (lazy (delay expr))) John Shutt (11 Jun 2004 12:44 UTC)

Problem with (force (lazy (delay expr))) Alejandro Forero Cuervo 11 Jun 2004 07:08 UTC
Hello, Andre.

There is  a problem  with your  proposal as  it is:  doing (force
(lazy  (delay expr)))  does not  update the  promise returned  by
(delay  expr)  to  cache  the  results  of  evaluating  expr,  so
subsequent forces will need to reevaluate it.

The following example ilustrates this problem:

(let ((s (delay (begin (format #t "Eval~%") '()))))
  (force (lazy s))
  (force s))

This  will print  "Eval" twice,  showing that  the expresion  was
evaluated two times.

This is a problem because, according to your transformation rules
(section  "Correct Usage"),  the bodies  of procedures  returning
promises  should  be wrapped  with  lazy  (instead of  delay  and
force).

To write a function that removes the first N elements of a stream
one would thus do:

(define (stream-drop str n)
  (lazy
    (if (zero? n)
        str
        (stream-drop (cdr (force str)) (- n 1)))))

The  result is  a (lazy  (delay expr))  that, when  forced, won't
cause the original  stream to cache the result.   You can rewrite
my  first example  replacing  the call  to lazy  with  a call  to
(lambda (str) (stream-drop str 0)) to see the same bug.

The problem is easy to find.  (lazy (delay expr)) expands to:

  (cons 'lazy
        (lambda () (cons 'lazy
                         (lambda () (cons 'eager expr)))))

Unfortunately, forcing  this expresion only updates  the external
pair,,  so  future forces  of  the  internal  pair will  need  to
evaluate expr again.

This bug  obviously affects its current  reference implementation
for streams, making it problematic  to work with streams that are
built  reading from  ports,  for example.   SRFI-40 makes  things
worse by specifying no function for forcing the streams directly.
In consequence,  I'm posting this  message to both lists,  I hope
that's ok.

Any thoughts on how to solve this problem?

I  *think* you  could specify  that  lazy should  only be  passed
forced  promises (created  by means  of (eager  expr) or,  if you
don't want eager to be  part of your specification, (force (delay
expr))) or promises created by  lazy itself and you wouldn't lose
your safe-for-space properties.

Thank you!

Alejo.
http://bachue.com/alejo

Ps: Please  CC to  me  in your  reply, as  I  haven't managed  to
subscribe  to the  lists (waiting  for  a reply  to my  subscribe
message for hours...).

---=(  Comunidad de Usuarios de Software Libre en Colombia  )=---
---=(  http://bachue.com/colibri )=--=( xxxxxx@bachue.com  )=---