lazy-scheme-notes/lazy.org

Laziness using plain lambda expressions

Some prerequisites to make later code more readable:

(define println
  (lambda* (msg #:optional (output-port (current-output-port)))
    (display (simple-format #f "~a\n" msg) output-port)))

We can define lazy lists by making the cdr of a list a lambda expression, which is only applied, when the cdr is needed.

(define lazy-list
  (lambda* (start #:optional (end #f))
    (cond
     [end
      (if (<= start end)
          (cons start
                (λ () (lazy-list (+ start 1) end)))
          '())]
     [else
      (cons start
            (λ () (lazy-list (+ start 1))))])))

(define lazy-car car)

(define lazy-cdr
  (λ (lazy-lst)
    ((cdr lazy-lst))))

Creating a lazy list works as follows:

<<lazy-definition>>

(display
 (simple-format
  #f "~a\n"
  (lazy-list 0 10)))

:RESULTS: (0 . #:11:16 ()>) :END:

Iterating through a lazy list up to a given number:

<<prerequisites>>
<<lazy-definition>>

(let ([infinite-list (lazy-list 0 +inf.0)])
  (let iter ([counter 0] [llst infinite-list])
    (cond
     [(< counter 10)
      (println (lazy-car llst))
      (iter (+ counter 1) (lazy-cdr llst))]
     [else
      'done])))

:RESULTS: 0 1 2 3 4 5 6 7 8 9 :END:

Also higher-order list functions can be defined for lazy lists:

<<lazy-definition>>

(define lazy-filter
  (λ (pred lazy-list)
    (cond
     [(null? lazy-list) '()]
     [(pred (lazy-car lazy-list))
      (cons (lazy-car lazy-list)
            (λ () (lazy-filter pred (lazy-cdr lazy-list))))]
     [else
      (lazy-filter pred (lazy-cdr lazy-list))])))

(define lazy-map
  (λ (proc lazy-list)
    (cond
     [(null? lazy-list) '()]
     [else
      (cons (proc (lazy-car lazy-list))
            (λ () (lazy-map proc (lazy-cdr lazy-list))))])))

:RESULTS: :END:

For usage:

<<prerequisites>>
<<lazy-definition>>
<<lazy-higher-order-list-functions>>

(println "some even numbers:")

(let ([infinite-list
       (lazy-filter (λ (num) (= (remainder num 2) 0))
                    (lazy-list 0 +inf.0))])
  (let iter ([counter 0] [llst infinite-list])
    (cond
     [(< counter 10)
      (println (lazy-car llst))
      (iter (+ counter 1) (lazy-cdr llst))]
     [else
      'done])))

(println "some odd numbers squared:")

(let ([infinite-list
       (lazy-map (λ (num) (* num num))
                 (lazy-filter (λ (num) (= (remainder num 2) 1))
                              (lazy-list 0 +inf.0)))])
  (let iter ([counter 0] [llst infinite-list])
    (cond
     [(< counter 10)
      (println (lazy-car llst))
      (iter (+ counter 1) (lazy-cdr llst))]
     [else
      'done])))

:RESULTS: some even numbers: 0 2 4 6 8 10 12 14 16 18 some odd numbers squared: 1 9 25 49 81 121 169 225 289 361 441 529 625 729 841 961 1089 1225 1369 1521 1681 1849 2025 2209 2401 2601 2809 3025 3249 3481 3721 3969 4225 4489 4761 5041 5329 5625 5929 6241 6561 6889 7225 7569 7921 8281 8649 9025 9409 9801 10201 10609 11025 11449 11881 12321 12769 13225 13689 14161 14641 15129 15625 16129 16641 17161 17689 18225 18769 19321 19881 20449 21025 21609 22201 22801 23409 24025 24649 25281 25921 26569 27225 27889 28561 29241 29929 30625 31329 32041 32761 33489 34225 34969 35721 36481 37249 38025 38809 39601 :END:

Laziness using macros

It is also possible to write some macro, which takes care of transforming an expression into a lazily evaluated expression.

;; Macro expansion is at read time, not at run time, so the expression will not
;; be evaluated here.
(define-syntax my-delay
  (syntax-rules ()
    ;; Match the expression that starts is (delay some-expression)
    [(_ expr)
     ;; Wrap that expression in a lambda, which delays evaluation, until the
     ;; resulting expression is applied.
     (lambda () expr)]))

;; The counterpart ~force~ can be defined as a simple procedure, because it does
;; not need to prevent evaluation. It is supposed to cause evaluation. It
;; receives a promise, which in this case is only a lambda expression taking no
;; arguments and applies it.
(define my-force
  (lambda (promise)
    (promise)))

:RESULTS: :END:

And here is the usage:

<<laziness-using-macros-definition>>

(display
 (simple-format
  #f "~a\n"
  (my-delay (+ 5 6))))

(display
 (simple-format
  #f "~a\n"
  (let ((delayed (my-delay (+ 5 6))))
    (my-force delayed))))

:RESULTS: #:26:2 ()> 11 :END:

Laziness using SRFI-45

There is also an SRFI, which defines an interface for lazy evaluation.

TODO

Laziness and streams

Laziness is also connected to implementation of streams. Streams can be of arbitrary length, so it would be a good idea to not have to keep all data of a stream in memory. This is where laziness comes in.

TODO