(Previous discussion continued)
Re: Multiple values Eli Barzilay 17 Oct 2006 00:03 UTC

Re: Multiple values Eli Barzilay 17 Oct 2006 00:03 UTC

On Oct 16, Eli Barzilay wrote:
> On Oct 15, Eli Barzilay wrote:
> >
> > FWIW, here is an implementation of lazy/eager/delay/force that
> > works with multiple values.  [...]
> Another implementation.  This one uses a different solution than the
> srfi code.  The main idea is adding a `force*' operation, that
> intuitively has the meaning of an iterated `force': [...]

And one more solution.  (Sorry for the bombardment, this is a result
of a discussion that has went on for some time, and I'd like to
document things in the srfi archive.)

The problem in the above solution, is that there is an additional
level of promise implementation on top of the built in one -- the code
for both is similar, but there is no sharing of code.  (This is why it
avoided the observable change: because it is a wrapper, it cannot make
any imperative changes to built in promise values.)  This solution is
an alternative: take a standard implementation of promises, and extend
the promise type so it has a flag attached.  The flag identifies the
promise as a plain promise (a 'delay promise), a promise type that
gets flattened to a plain promise (a 'lazy promise, used with the
previous promise types in the srfi), or an already forced value.

The implementation follows.  Again -- it's written for PLT but doesn't
use any special features.  It passes all tests -- except for the last
one which leaks in the default MzScheme and works fine in MzScheme 3m
(the precise collector version).  I think that the issue is that the
really long list is actually constructed but not being held, which
usually leads to a conservative GC disaster (one bad guess, and you
end up holding the whole list).

I'm posting this implementation for completeness: I started doing it
trying to get rid of the duplication of functionality in the last
implementation, but the body of `force-promise' clearly has the same
kind of duplication, with two sections for forcing 'delay and 'lazy

  ;; flag is: 'delay (plain), 'lazy (flattenable), #f: forced value
  (define-struct promise (flag p))

  (define-syntax delay
    (syntax-rules ()
      [(lazy exp) (make-promise 'delay (lambda () exp))]))

  (define-syntax lazy
    (syntax-rules ()
      [(lazy exp) (make-promise 'lazy (lambda () exp))]))

  ;; internal
  (define (force-promise p)
    ;; mark the promise forced, set and return the value
    (define (set-value! v) (set-promise-p! p v) (set-promise-flag! p #f) v)
    (case (promise-flag p)
      [(#f) (promise-p p)]
       (let ([v ((promise-p p))])
         (if (eq? 'delay (promise-flag p))
           (set-value! v)
           ;; otherwise, it must be a flat value
           (promise-p p)))] ; already forced
       ;; forcing a lazy promise flattens it destructively
       (let loop ([v ((promise-p p))])
         (case (promise-flag p)
            (if (promise? v)
              (if (eq? 'lazy (promise-flag v))
                ;; got a 'lazy promise => flatten (swap pointers)
                (begin (set-promise-p! p (promise-p v))
                       (set-promise-p! v p)
                       (loop ((promise-p p))))
                ;; got a plain promise => force it and cache result
                (set-value! (force-promise v)))
              ;; got a plain value
              (set-value! v))]
           [(delay) (force p)] ; got flattened to a 'delay promise
           [else (promise-p p)]))])) ; already forced

  ;; wrapper for force-promise that always assumes a promise input
  (define (force x)
    (if (promise? x)
      (force-promise x)
      ;; can throw an error here to make force work only on promises
      ;; (raise-type-error 'force "promise*" x)

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