Re: Some Questions Andre van Tonder 01 Oct 2003 17:15 UTC

On Tue, 30 Sep 2003, Phil Bewig wrote:

> Good job!  In fact, I have already appropriated your delay/force
> primitives for my SRFI-40 streams reference implementation, and
> all seems to be working well.  I have some questions:

Thank you very much for your insightful post.  I'll try to answer the
points you raised below:

>
> 1)  Given the minimalist spirit of Scheme, why did you decide to
> make lazy a primitive?  It doesn't have to be.  You could define
> delay and force by inlining the definitions of lazy and strict
> into delay:
>
>     (define-syntax delay
>       (syntax-rules ()
>         ((delay exp)
>           (cons 'suspension
>             (lambda () (cons 'value exp))))))
>
>     (define (force promise)
>       (case (car promise)
>         ((value)      (cdr promise))
>         ((suspension) (let ((val ((cdr promise))))
>                         (set-car! promise (car val))
>                         (set-cdr! promise (cdr val))
>                         (force promise)))))
>
> Then (lazy ...) is just the composition of delay and force, as in
> Wadler's transformation, and is no longer primitive.

Unfortunately this would not work - with this suggested solution in
MzScheme the (loop) example runs out of memory quickly, and for the same
reason that the R5RS (delay (force ...)) does.  If you follow the
execution of *force*, all the recursion would happen in the first line of
the *let* form, which is not a tail call.  The nested calls to ((cdr
promise)) would never return, so the heap would just keep growing.

So I still cannot see a way of avoiding the need for an "atomic" (lazy
...).

>
> 2)  R5RS suggests that calling force on an object that is not a
> promise may simply return the object instead of causing an error.
> In the reference implementation, something will eventually break
> if force is applied to an object that is not a promise, though
> the error may be signaled in a non-obvious way.  Did you consider
> allowing force to simply return if passed an object that is not a
> promise?  The advantage is that it eliminates a potential error
> message; the disadvantage is that it admits imprecision in dealing
> with types.

A previous version that I had written worked this way (in fact, if we
allow this, we can get away with just the two primitives *lazy* and
*force* instead of three, which was a nice bonus).  I discarded it because
the typing was not so pretty.  Also, even though the suggestion is not
against the letter of R5RS, the Scheme implementations that I am familiar
with, as well as the R5RS reference implementation, do not work this way.

Improved error checking is probably a good idea.

>
> 3)  Since you have created a new data type of promises (or maybe
> it is better to say you have re-created an old type of promises),
> would you perhaps like to specify a (promise? obj) function that
> takes an object and returns #t if the object is a promise and #f
> otherwise?  Would you also perhaps like to specify two additional
> predicates (forced-promise? obj) and (suspended-promise? obj)
> that can distinguish between a forced promise and a suspended
> promise?  Note that given your current reference implementation
> it is possible to distinguish a promise from its forced value,
> which R5RS says is not necessary for a conforming implementation,
> though it allows the possibility.

This could be added.  However, I was hesitant to add features not in
R5RS and that were not directly related to the problem of iterative
behavior which the SRFI addresses.  Regarding this feature in particular,
I was hesitant to try to address the question of type
opaqueness/disjointness, which is somewhat othogonal this SRFI, and
to which I don't know the right answer.  Also, some Scheme implementations
have a promise? predicate and others don't.  I'm curious about the
reasons.

>
> For purposes of your reference implementation you could create
> these predicates using SRFI-9 records.  In fact, you could even
> replace the cons-pairs in your implementation with the fields of
> records:
>

True, but there may be some value in avoiding a dependency
on another SRFI.  Also, since each Scheme has its own native way
of marking disjoint types and since various Schemes have their own
native records with different syntaxes, maybe the issue is better left to
implementors.

> 4)  Could you please state explicitly how you have extended the
> semantics of R5RS force?  In particular, I am looking for a
> specific example where SRFI-45 force would give a different
> answer than R5RS force.

(force (lazy exp)) -> (force exp) iteratively.

Otherwise (if program does not contain "lazy") no difference.

> This is a hard question because different
> Scheme implementations give different semantics for R5RS force, as
> in the SRFI-40 discussion of my first reference implementation
> which worked in some Scheme implementations but not others (which
> of course begs the question of *exactly* what is the semantics of
> R5RS force).  When you answer, assume a Scheme implementation like
> scheme48 where my first reference implementation actually worked.

This is very interesting.  I don't have access to Scheme48 but I would
be very interested to know if the infinite loop benchmarks I provide are
passed by Scheme48 using the native (delay (force ...)) instead of lazy.
If someone has the time to run a couple of them, I would be grateful to
hear about the results.

> A corollary to this question is: would any program that uses the
> R5RS definitions of delay and force break if replaced by the
> SRFI-45 definitions of delay and force?
>

No.  They shouldn't.

> 5)  In your Benchmarks, why did you decide to delay the result of
> stream-ref?

In previous attempts to solve the problem I had had unexpected leaks
appear when composing lazy functions as in my version of the
times3 example.  So I kept stream-ref lazy for the purpose of testing this
issue.

>
> 6)  Why did you decide to order the arguments to stream-ref as
> (stream-ref index s) instead of (stream-ref s index)?  In SRFI-40,

Since it is only a test suite, I didn't worry about this inconsistency.
Initially I had it the other way around, but got tired of getting the
nesting level of the 3 wrong in e.g.
   (..... (stream-ref ( .....
                        nontrivial expression
                        ......)...)
                      3)....)

By the way, it does seem inconsistent to me that the order in
stream-filter would differ from that in stream-ref.  To
me they are morally similar... :-)

Best regards
Andre