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

Re: Multiple values

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':

  (define (force* x)
    (if (promise? x)
      (force* (force x))

Just as the srfi describes, there are certain infinite computation
chains that lead to holding a a growing linked list of promises in
memory, each promise pointing at the next (p1 -> p2 -> p3 -> ...), and
`force*' is working at the end of this list, and keep extending it.
The srfi-45 solution is (roughly, adapted to `force*') to add another
layer of reference (the box wrapper) so when `force*' gets to p2, it
will set p1 to be an alias of p2, and then the computation continues
with p1 (so if nobody holds on to p2, it will get collected).  (No
infinite list can be generated from these aliases.)

The solution below works without the extra box wrapper.  The idea is
that when `force*' gets to p2, it swaps the contents of the two
promises so that p2 points at p1, and p1 has the thunk with the rest
of the computation.  The same thing happens now: the computation
continues with p1, and if nobody holds on to p2 it can be collected.
Again, all of p2, p3, ... will point at p1, so no infinite list is

  ;; uses a promise implementation with a single thunk/value-list slot `p'
  (define (force* x)
    (if (promise? x)
      (let loop ([v (force x)])
        (if (promise? v)
          (begin (set-promise-p! x (promise-p v))
                 (set-promise-p! v (list x))
                 (loop (force x)))

This is fine behavior for `force*' because it does not distinguish
promises from their values: if force(p1) = p2, then force*(p1) =
force*(p2), and swapping them is not visible if you use only
`force*'.  This is particularly useful for a lazy language
implementation, where distinguishing a promise from its value does not
make sense.  It is, however, not behaving well if you do care to
distinguish promises and values -- for example:

  > (define r (delay 1))
  > (define s (delay r))
  > (force r)
  > (force* s)
  > (force r)
  #<struct:promise>    ; <-- different
  > (force* r)
  1                    ; <-- but ok if you only use `force*'

Other than that, it is a fine solution -- passes all of the srfi tests
(using only `delay', and using `force*' instead of `force').

To implement the functionality of srfi-45, this distinction needs to
be kept.  One way to achieve this is to have a second implementation
of promises that is used to wrap the built-in type.  So the new type
(promise*) is similar to the built in one (promise) and its `force*'
operation works as above -- using `force' for a final built-in
promise.  The result is: a new form for delaying computation
(equivalent to `lazy'), and a new `force*' that flattens such promise
chains as well as `force'ing plain promises (so it's equivalent to
srfi 45's `force').

This is implemented in the following module for PLT (and easily
adapted to other implementations).  The code passes all of the tests
in the srfi document.

(module force* mzscheme
  (provide lazy (rename force* force))

  (define-struct promise* (p))

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

  (define (force-once p)
    (let ([v (promise*-p p)])
      (if (procedure? v)
        (let* ([v (v)] [v* (promise*-p p)])
          (if (procedure? v*)
            (begin (set-promise*-p! p (list v)) v)
            (car v*)))
        (car v))))

  (define (force* x)
    (cond [(promise*? x)
           (let loop ([v (force-once x)])
             (cond [(promise*? v)
                    (set-promise*-p! x (promise*-p v))
                    (set-promise*-p! v (list x))
                    (loop (force-once x))]
                   [(promise? v) (force v)]
                   [else v]))]
          [(promise? x) (force x)]
          [else (raise-type-error 'force "promise*" x)]))


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