[plt-scheme] Lazy Evaluation -- Even Streams Eli Barzilay eli@barzilay.org Mon, 3 Feb 2003 00:34:32 -0500 * Previous message: [plt-scheme] possibly useful new arity-checking tool: no-brainer * Next message: [plt-scheme] DrScheme vs. multiple collections directories * Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] This is the result of a discussion I had with Phil who is working on his streams SRFI (he's not on this list so I CCd him). The beginning of all this is in the "How to add laziness to a strict language without even being odd" paper. The main idea they present, and that Phil used following that, is that an even lazy data structure should always be a delayed object, instead of the standard cons of something and a promise which cause off-by-one errors since they always require evaluation of one extra object. The solution is to always use functions that do this: (define (foo ...) (delay (force ...random-code...))) which is what Phil used for a `stream-define' macro that translates to this kind of a definition. But I think that this could be improved even further. The standard solution follows the basic philosophy that the random-code is something that uses the arguments to compute a new stream value -- which is always a promise, but this computation itself needs to be lazy which is why the body is wrapped in a `delay'. The next thing to see is that if we leave it this way, we will have a promise containing a promise which is no longer a stream as defined, so the contents of the delay is further wrapped in a `force'. The complexity which I think is easy to get rid of, is that the actual body (random-code in the above) still needs to know what arguments are streams and use only stream functions with them. What I'd want instead, is to magically know what arguments are lazy and force them before using them. This means that the random-code will have to handle standard Scheme objects, like lists in the stream example. In other words, the original solution strips a promise level on the result of the computation which handles lazy objects, and the new solution strips a promise level from input values on entry and delays the result which was achieved using simple strict code -- resulting in functions that look even more similar to their strict equivalents since they use the same functions. This can be implemented by wrapping the body in code that will bind any argument variable v to (maybe-force v) where `maybe-force' is: (define (maybe-force x) (if (promise? x) (force x) x)) which should work reasonably well if all lazy inputs are promises which you'd expect them to be. But there is another problem introduced by this approach -- some of the arguments might not be needed for the computation so you don't want to force them. The solution for this is to use a syntax binding that will bind every input variable `v' to the *syntax* `(maybe-force v)'. This is simple using my `letsubst' thing from Swindle, resulting in this macro to create such bindings for a possibly dotted list of arguments: (define-syntax force-args (syntax-rules () ((force-args "REV" (arg ...) (a . rest) body0 body1 ...) (force-args "REV" (arg ... a) rest body0 body1 ...)) ((force-args "REV" (arg ...) () body0 body1 ...) (force-args "DONE" (arg ...) body0 body1 ...)) ((force-args "REV" (arg ...) rest body0 body1 ...) (force-args "DONE-R" (arg ...) rest body0 body1 ...)) ((force-args "DONE" (arg ...) body0 body1 ...) (letsubst ((arg (maybe-force arg)) ...) body0 body1 ...)) ((force-args "DONE-R" (arg ...) rest body0 body1 ...) (letsubst ((arg (maybe-force arg)) ... (rest (map maybe-force rest))) body0 body1 ...)) ((force-args args body0 body1 ...) (force-args "REV" () args body0 body1 ...)))) which can be be used to make the final syntax bits: `strict-lambda', which is like a normal `lambda' except it forces things as above. `strict-define' uses that for defining a named function. `strictify' turns a normal function to a strict one (I don't know if it's useful for anything), and `strict' is a convenient shorthand for maybe-forcing stuff -- either value, or applying a function of forced values. It's a syntax only for symmetry with `lazy' below, and its usage will be cleared below. Then there are `lazy' versions of all this which are wrapped in a `delay'. This is the code: (define-syntax strict-lambda (syntax-rules () ((strict-lambda args body0 body1 ...) (lambda args (force-args args body0 body1 ...))))) (define-syntax strict-define (syntax-rules () ((strict-define (name . args) body0 body1 ...) (define name (strict-lambda args body0 body1 ...))))) (define (strictify func) (strict-lambda args (apply func args))) (define-syntax strict ; doesn't need to be a macro (syntax-rules (:) ((strict : val) (maybe-force val)) ((strict func x ...) (func (maybe-force x) ...)))) (define-syntax lazy-lambda (syntax-rules () ((lazy-lambda args body0 body1 ...) (lambda args (delay (force-args args body0 body1 ...)))))) (define-syntax lazy-define (syntax-rules () ((lazy-define (name . args) body0 body1 ...) (define name (lazy-lambda args body0 body1 ...))))) (define (lazify func) (lazy-lambda args (apply func args))) (define-syntax lazy (syntax-rules (:) ((lazy : val) (delay val)) ((lazy func x ...) (delay (func x ...))))) Now, implementing even streams with this is very simple, and doesn't even require a special syntax... * instead of stream-null, you use (lazy : '()), but (delay '()) would do just as well. Repeating what I said above, the goal is for stream functions to be written as if they operate on normal pairs, the inputs get forced, and the output gets delayed. This is why (delay '()) is the same as stream-null. * instead of (stream-null? x), you use (strict null? x), this will call null?, after forcing x (if its a promise). * The same goes for all functions that take something from the lazy world into the normal one, some examples are (strict pair? x), (strict car x), (strict cdr x). But (strict cadr x) won't work since we're handling lazy *pairs* -- there is no way to force the cdr of the stream automatically, so all functionality relies only on Scheme pairs. But note that force is conditional, so a `list->stream' becomes redundant -- you could just delay the list, or even use it as is which will work the same. * As for a lazy constructor -- instead of (lazy-cons x y), all you need is (lazy cons x y) which is simple enough to not even requiring an additional macro. But you rarely need this, since you'll usually create streams in a lazy function (which will be delayed automatically), or for streams that are literally specified, you just use them. So the quick summary is that lazy functions operate completely in the lazy side, strict functions work from the lazy to the strict side, and you don't need functions that go from the strict to the lazy since it is automatically a subset of it, but `lazy' is a nice thing to have when you want to have delayed computations to build your stuff. To show how this works, I go back to the "reference problem" from the above paper. First, I have stream-map, which I called lazy-map since I consider this to be a generically lazy thing: (lazy-define (lazy-map func list) (if (null? list) '() (cons (func (car list)) (lazy-map func (cdr list))))) As you can see there is no difference between this and a simple recursive map... `countdown' (an infinite stream counting down from a number) is also very simple, just like an equivalent simple version (except that such a version would never halt): (lazy-define (countdown n) (cons n (countdown (- n 1)))) `cutoff' (returning a list of the first n elements from a stream) is again defined as if it is a normal function. It is defined as a strict function because it returns a value to the real world. Note that here we don't want to evaluate the `list' argument if n is zero which will work since it is bound to a "symbol macro". (strict-define (cutoff n list) (if (or (zero? n) (null? list)) '() (cons (car list) (cutoff (- n 1) (cdr list))))) And finally, the following works as expected (not raising the error that would occur with an odd stream): (define (12div n) (/ 12 n)) (cutoff 4 (lazy-map 12div (countdown 4))) There is no promise-level problem, everything is kept at a single delay level, the same as with the standard implementation. To see this, I did the following: (cutoff 4 (lazy cons (delay 1) (lazy cons (delay 2) (lazy cons (delay 3) (lazy : '()))))) and the expected result was a list of the three promises. The only level problem is if you want a strict argument to hold a promise value, but I can't think of any realistic example for that. -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://www.barzilay.org/ Maze is Life! * Previous message: [plt-scheme] possibly useful new arity-checking tool: no-brainer * Next message: [plt-scheme] DrScheme vs. multiple collections directories * Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]