[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: simpler srfi 45 implementation

Here is the code for stream-type, extracted from the latest version of SRFI-45 (at this writing, that version has been submitted to the editors but has not yet appeared on srfi.schemers.org ).

  (define-record-type (stream-type make-stream stream?)
    (fields (mutable box stream-promise stream-promise!)))

  (define-syntax stream-lazy
    (syntax-rules ()
      ((stream-lazy exp) (make-stream (lambda () exp)))))

  (define-syntax stream-delay
    (syntax-rules ()
      ((stream-delay exp) (stream-lazy (make-stream (list exp))))))

  (define (stream-force prom)
    (let ((p (stream-promise prom)))
      (cond ((pair? p)   (car p))
            ((stream? p)
              (let ((x (stream-force p)))
                (let ((content (stream-promise prom)))
                  (if (pair? content) (cdr content)
                      (begin (stream-promise! prom (list x)) x)))))
            ((procedure? p)
              (let ((prom* (p)))
                (if (not (pair? (stream-promise prom)))
                    (if (stream? prom*)
                        (begin (stream-promise! prom (stream-promise prom*))
                               (stream-promise! prom* prom))
                        (stream-promise! prom (list prom*))))
                (stream-force prom)))
            (else (error 'stream-force "invalid promise")))))

On Nov 13, 2007 6:44 AM, Eli Barzilay <eli@xxxxxxxxxxxx> wrote:
On Nov 13, Jos Koot wrote:
> Eli wrote the following version:
> [...]
>   (define (force promise)
>     (let ([p (promise-p promise)])
>       (cond [(procedure? p)
>              (let ([promise* (p)])
>                (unless (pair? (promise-p promise))
>                  (if (promise? promise*)
>                    (begin (set-promise-p! promise (promise-p promise*))
>                           (set-promise-p! promise* promise))
>                    (set-promise-p! promise (list promise*))))
>                (force promise))]
>             [(pair? p)    (car p)]
>             [(promise? p) (force p)] <----
>             [else         (error "Invalid promise, contains" p)]))))
> [...]

Actually, I use a variation of that, which you can see at


(The file has four versions of `force' : the first is like the above,
the second deals with multiple values, the third deals with multiple
values only for the delay/force case, and the last adds exception

The differences between this and the version that you quoted are
mostly technicalities, and the code that I have can still use this
optimization.  I couldn't verify that the version I'm using enjoys the
same speedup -- Phil: do you have the code needed to run Jos's example?

... and there's a "BUT":

I was aware of the possible optimization at the time, but didn't find
any example where it mattered.  However, if you do put it in:

>             [(promise? p)
>              (let* ((v (force p)))
>               (if (not (pair? (promise-p prom)))
>                   (set-promise-p! prom (list v)))
>               (car (promise-p prom)))]

then you do the recursive forcing of `p' in a non-tail conext.  My
(vague, not formal at all) feeling about these "referral promises" is
that they do happen in places where the original code had a tail call,
so it might be a bad idea to break it.

So I don't know whether it should be included or not -- do you see
that it's not doing any damage?

         ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                 http://www.barzilay.org/                 Maze is Life!