Some Questions Phil Bewig 30 Sep 2003 21:35 UTC

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:

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.  In fact,
(delay (force ...)) is so easy to write you may not even feel
the need to provide lazy as derived syntax.  You also don't need
to change your recipe.

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.

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.

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:

    (define-record-type promise
      (make-promise promise-status promise-value)
      promise?
      (promise-status get-promise-status set-promise-status!)
      (promise-value get-promise-value set-promise-value!))

    (define-syntax delay
      (syntax-rules ()
        ((delay exp)
          (make-promise 'suspension
            (lambda () (make-promise 'value exp))))))

    (define (force promise)
      (if (not (promise? promise))
        promise ; or else raise an error
        (case (get-promise-status promise)
          ((value)      (get-promise-value promise))
          ((suspension) (let ((val ((get-promise-value promise))))
                          (set-promise-status! promise
                            (get-promise-status val))
                          (set-promise-value! promise
                            (get-promise-value val))
                          (force promise))))))

    (define (forced-promise? obj)
      (and (promise? obj)
           (eq? (get-promise-status obj) 'value)))

    (define (suspended-promise? obj)
      (and (promise? obj)
           (eq? (get-promise-status obj) 'suspension)))

    ; (define-syntax lazy
    ;   (syntax-rules ()
    ;     ((lazy exp)
    ;       (delay (force exp)))))

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.  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.
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?

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

    (define (stream-ref n s)
      (cond ((null? (force s)) 'error)
            ((zero? n) (car (force s)))
            (else (stream-ref (- n 1) (cdr (force s))))))

then you don't need to force the results of the expressions in your
tests 6 and 7:

    (stream-ref 0 (stream-filter zero? (from 0))) ==> 0

    (times3 7) ==> 21

By the way, although I generally like the combination of testing
and variable binding that is done by pattern matchers, I think
that in this particular case pattern matching harms more than
helps by obscuring the simple fact that stream-ref has three
possible outcomes; match makes me think it has two, and I have
to read further -- to the if -- to see that it has three.  Of
course, both versions of stream-ref ignore the possibility that
n is negative.

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,
I struggled quite a while with the proper order of the arguments
to this function.  (stream-ref index s) seems more natural, with
the index parameter first and the stream last; most functions that
operate on concrete data types write the parameters first and the
data-type argument last.  But R5RS defines (list-ref list index)
in the opposite order, and I decided in my SRFI to be consistent
with the R5RS function.  The choice would matter more in a
language like ML or Haskell that provides a more natural syntax
for curried functions than Scheme does; there, you would have to
decide between:

    ref n s makes it easy to write a function that always
    returns a specific n'th element of any stream s -- think
    of the lisp functions first, second, third, and so on

    ref s n makes it easy to write a function that always
    returns any n'th element of a specific stream s -- think
    of repeatedly indexing into the same stream

I don't think there is any particularly right or wrong answer to
this question, I'm just curious what other people think.

Phil