item #55 - I'd rather be lazy than eager with new primitives
Alex Shinn
not at all convinced there is any need for lazy or eager. As I
understand it, the reference implementations of delay and
force, when used with the reference implementation of SRFI-40,
causes space leaks.
One solution is to fix the delay/force implementations (some
proposals were explored on the list). Another option is to fix
the streams implementation (a CPS-based version which didn't
leak was also posted to the list). One or both of these may
require a certain level of compiler optimization, but that seems
right along the lines of requiring TCO.
It's possible lazy and eager primitives are the best way to
implement a high-level streams library, but it doesn't seem
like enough effort has been put into alternatives (there are
a scant 13 messages from 4 people on the SRFI-45 list).
The proposed primitives also seem very clumsy for everyday
use, and I see no need to expose the low-level details
(especially in WG1).
Could anyone more familiar with the issues correct me
if I'm wrong?
--
Alex
Arthur A. Gleckler
> implement a high-level streams library, but it doesn't seem
> like enough effort has been put into alternatives (there are
> a scant 13 messages from 4 people on the SRFI-45 list).
> The proposed primitives also seem very clumsy for everyday
> use, and I see no need to expose the low-level details
> (especially in WG1).
These are good points. I've revised my vote to leave SRFI-45 as my last choice.
John Cowan
> I've been reviewing SRFI-45 (pertaining to item #55), and am
> not at all convinced there is any need for lazy or eager. As I
> understand it, the reference implementations of delay and
> force, when used with the reference implementation of SRFI-40,
> causes space leaks.
SRFI 40 is only incidental. Rather, the basic transformation of an eager
algorithm into a lazy one by the obvious means (delay all constructors,
force all deconstructors, and wrap all procedure bodies with "delay o
force") will fail to be tail recursive. The simplest example in SRFI
45 is
(define (loop) (loop))
which will loop forever, consuming no space in Scheme itself. But if
we assume it is lazy, then the above transformation (called the "[Wad98]
transformation" in SRFI 45), comes out as:
(define (loop) (delay (force (loop))))
which will create an infinite set of nested promises, none of which are
garbage, until Scheme crashes on an out-of-memory error.
> One solution is to fix the delay/force implementations (some
> proposals were explored on the list). Another option is to fix
> the streams implementation (a CPS-based version which didn't
> leak was also posted to the list). One or both of these may
> require a certain level of compiler optimization, but that seems
> right along the lines of requiring TCO.
It's not enough to fix the streams implementation if you are dealing with
laziness generally. You either write your own delay/force for each case
of laziness you are dealing with, which is hard, or you fix it once and
for all.
> The proposed primitives also seem very clumsy for everyday
> use, and I see no need to expose the low-level details
> (especially in WG1).
We already have delay and force exposed.
--
Normally I can handle panic attacks on my own; John Cowan <co...@ccil.org>
but panic is, at the moment, a way of life. http://www.ccil.org/~cowan
Alex Shinn
>
> SRFI 40 is only incidental. Rather, the basic transformation of an eager
> algorithm into a lazy one by the obvious means (delay all constructors,
> force all deconstructors, and wrap all procedure bodies with "delay o
> force") will fail to be tail recursive.
In existing implementations of delay and force. You don't
need a sufficiently smart compiler to fix this - just rewrite
(delay (force x)) with (lazy x), without the need to expose
lazy to the user. But I suspect there's a more general purpose
optimization that would cover this case.
There are two things I'd need to be convinced of to want to
add these to WG1: 1) that they are generally useful outside
of streams (which is a WG2 topic anyway), and 2) that it's
prohibitively difficult for compilers to make (delay (force x))
tail recursive.
--
Alex
Aaron W. Hsu
> I've been reviewing SRFI-45 (pertaining to item #55), and am
> not at all convinced there is any need for lazy or eager. As I
> understand it, the reference implementations of delay and
> force, when used with the reference implementation of SRFI-40,
> causes space leaks.
I think that we have not had nearly enough discussion to make a good case
for SRFI-45 here, and thus, I am inclined to preclude it from
standardization.
Aaron W. Hsu
--
Programming is just another word for the lost art of thinking.
Alex Shinn
investigate it further myself and provide a more complete summary of
the issue.
A common idiom when working with lazy evaluation is
(delay (force X))
for some computation X, and indeed this specific pattern occurs as a
result of an automated transformation from a strict to lazy language
in [Wad98].
Typically force is implemented along the lines of
(define (force promise)
(cond
((promise-done? promise)
(promise-value promise))
(else
(promise-lock! promise) ;; optional to prevent re-entrancy
(let ((res ((promise-thunk promise))))
(promise-update! promise res)
res))))
where promise-update! sets the value and done? flag and clears the
thunk.
The problem is that in this definition, promise-thunk is not evaluated
in a tail position, even if the original force was. If an iterative
algorithm was translated in this way it would need to be able to keep
the entire call trace of promise in memory until the last one
finished, then update them each in turn before returning. Thus a
simple infinite loop like the following will eventually run out of
memory (if not stack space):
(define (loop) (delay (force (loop))))
(force (loop))
SRFI-45 proposes a new syntax (lazy X) as a substitute for
(delay (force X))
but which is integrated with the definition of force to use a
trampoline, and iteratively update each promise in the chain in a
tail-recursive manner.
This solves and is easy to implement, so it should definitely get
strong consideration for our standard.
My personal concerns are twofold. One, it's not clear that `lazy'
covers all the cases we may want for lazy programming. In my own
code, I couldn't find the (delay (force X)) pattern, but did find
(delay (car (force X)))
for which you can't use `lazy'. In this case, the force isn't being
called in a tail position anyway, but one can conceive of examples
where it is:
(delay (begin (display "hi!") (force X)))
This is admittedly contrived. Since I can't come up with a more
realistic example where `lazy' fails to encode a tail-recursive
computation I don't think this objection holds much water.
The second concern is whether a new primitive is truly necessary. Why
should we burden the programmer with learning a third laziness
primitive and remembering to write
(lazy X)
instead of
(delay (force X))
if the compiler and/or runtime can do it for him?
The most obvious strategy is to have a lazy language to begin with,
the existence of which is already proven by Racket's Lazy Scheme.
This is not pure Scheme, but R5RS does explicitly give us some leeway
with promises, in particular "implicit forcing" is allowed whereby
primitives can force promises without an explicit call to `force'. In
this case, force can be defined as the identify function, and we need
only be sure the implicit forcing is tail recursive. As a
proof-of-concept, the latest development tip of chibi-scheme now has a
compile-time option for this implicit forcing, with which the loops in
question run in constant space.
Of course, we can't require Schemes provide such extensions, this is
just to show that there are multiple strategies to achieve the same
thing.
Another approach is to try to detect the case at runtime. The
attached definitions of `delay' and `force' uses a global parameter to
detect whether we're forcing inside a nested `force', in which case it
returns the equivalent of the `lazy' macro, which is then iteratively
computed. This doesn't work if there are unrelated forces in utility
functions during the force. To make this work properly, you'd need to
generate a unique source tag for each force, and track a list of the
forces currently being called, only returning a `lazy' result if being
called recursively. This is a little hairy, and parameters may be
fairly heavyweight for laziness primitives, but it's at least an
option.
A more appealing approach is with compiler optimizations. The obvious
way that any compiler can do this is with a simple source-to-source
transformation detecting the pattern in question. That sort of
transformation is a strange thing to require compilers to do in a
standard, of course, but it suggests that there may be more general
transformations that we could require, at least as one of several
possible strategies for making `force' tail-recursive. The question
is, how "smart" does a compiler have to be to do this?
If the compiler can prove that a promise is forced only once (as in
the above cases), then it can safely elide the `promise-update!' step,
so the tail of the (inlined) definition of force becomes
(let ((res ((promise-thunk promise))))
;; no need to update
res)
=> ;; after simplification
((promise-thunk promise))
which is a normal tail call.
Detecting that case is tricky though, since it depends on escape
detection, and if the first promise in the chain escapes they all
escape.
After going over these options, all I can say is I'm still unsure.
From my perspective, anything I'm unsure of in WG1 should go into WG2,
so my "no" vote hasn't changed.
--
Alex
[Wad98] Philip Wadler, Walid Taha, and David MacQueen. How to add
laziness to a strict language, without even being odd, Workshop on
Standard ML, Baltimore, September 1998
;;;; implementing non-nested forces safely without needing `lazy'
(define being-forced? (make-parameter #f))
(define (promise? x) (vector? x))
(define (make-promise type thunk value)
(vector type thunk value))
(define (promise-type x) (vector-ref x 0))
(define (promise-thunk x) (vector-ref x 1))
(define (promise-value x) (vector-ref x 2))
(define (promise-set-type! x y) (vector-set! x 0 y))
(define (promise-set-thunk! x y) (vector-set! x 1 y))
(define (promise-set-value! x y) (vector-set! x 2 y))
(define (force x)
(cond
((eq? 'done (promise-type x))
(promise-value x))
((being-forced?)
(promise-set-type! x 'continue)
x)
(else
(let ((res (parameterize ((being-forced? #t))
((promise-thunk x)))))
(promise-set-type! x 'done)
(promise-set-thunk! x #f)
(promise-set-value! x res)
(if (and (promise? res) (eq? 'continue (promise-type res)))
(force res)
res)))))
(define-syntax delay
(syntax-rules ()
((delay x) (make-promise 'lazy (lambda () x) #f))))
Aaron W. Hsu
> The problem is that in this definition, promise-thunk is not evaluated
> in a tail position, even if the original force was. If an iterative
> algorithm was translated in this way it would need to be able to keep
> the entire call trace of promise in memory until the last one
> finished, then update them each in turn before returning. Thus a
> simple infinite loop like the following will eventually run out of
> memory (if not stack space):
> (define (loop) (delay (force (loop))))
> (force (loop))
> SRFI-45 proposes a new syntax (lazy X) as a substitute for
> (delay (force X))
> but which is integrated with the definition of force to use a
> trampoline, and iteratively update each promise in the chain in a
> tail-recursive manner.
I have been pondering this, and I do not understand something. Is the
problem just that ‘force’ as it may be defined will not ensure
tail-recursion when it should, or is the problem that ‘force’ can be made
to be tail-recursive in these cases? Ideally, I would if it is possible to
implement ‘force’ so that this problem does not arise, then I am more
inclined to specify that.