Modularity through lazy evaluation

The problem

The problem is easily illustrated. Consider the following code:

  (define (read-evaluate-print-loop)
    (display (eval (read) (scheme-report-environment 5)))
    (newline)
    (read-evaluate-print-loop))

  (read-evaluate-print-loop)

As written, this code is not modular. We can identify three separate concerns: Data is generated by *read*, transformed by *eval* and consumed by *display*. What if we want to plug in different transformations instead of *eval*, or if we want to change the way we generate or consume the data? The way it stands, we cannot reuse the parts we do not change.

The solution

Solution: Separate concerns using lazy evaluation.

In the code below, these three concerns are separated into three independent composable procedures. A lazy list is used as intermediate data structure. This list is generated on demand and may be garbage collected at any point leaving one active cons-cell. The algorithm therefore needs only slightly more active memory than the above iterative solution. We follow the convention that lazy procedures and data structures are prefixed by $.

  ; Concern: Generating data:
  ; $generate: () -> $list
  
  (define ($generate)
    (delay (cons (read) ($generate))))

 
  ; Concern: Transforming data:
  ; $transform: $list -> $list

  (define ($transform $lst)
    (lazy
     (match (force $lst)
       [()       (delay '())]
       [(h . $t) (delay (cons (eval h) ($transform $t)))])))

  ; Concern: Consuming data:
  ; consume: $list -> 'done

  (define (consume $lst)
    (match (force $lst)
      [()       'done]
      [(h . $t) (begin (display h) 
                       (newline)
                       (consume $t))]))

We can now plug these together as follows: Notice how easy it would be, for example, to replace or add transformations in the middle, or to send data to a file with a different consumer, or to plug in a generator that provides a test dataset.

  (consume ($transform ($generate)))

Abstracting recursion patterns

We can further modularize the code by abstracting the recursion patterns in the above code, leading to more concise, reliable and more easily optimizable code. In fact, the above is a simple example of a very common and general pattern of the form fold-map-unfold, where the lazy map, fold and unfold procedures are defined as follows:

  ; Apply f to each element of a lazy list:

  (define ($map f $lst)
    (lazy 
      (match (force $lst)
        [()       (delay '())]
        [(h . $t) (delay (cons (f h) ($map f $t)))])))

  ; Generate a lazy list given a generating function f and seed.
  ; $unfold : (b -> ('() | (cons (a | 'skip) b)) b -> $list a

  (define ($unfold f seed)
    (lazy 
      (match (f seed)
        [()          (delay '())]
        [(h . seed*) (if (eq? h 'skip)
                         ($unfold f seed*)
                         (delay (cons h ($unfold f seed*))))])))

  ; Consumes a lazy list from left.   

  (define ($foldl f base $lst)
    (lazy 
      (match (force $lst)
        [()       (delay base)]
        [(h . $t) ($foldl f (f h base) $t)])))

Our producer, transformer and consumer procedures above may now be conventionally expressed as follows:

  (define ($generate)
    ($unfold (lambda (seed) (cons (read) 'dummy))
             '()))

  (define ($transform $lst)
    ($map (lambda (exp) (eval exp (scheme-report-environment 5)))
          $lst))

  (define ($consume $lst)
    ($foldl (lambda (x base) (display x) (newline))
            'done
            $lst))

  (force ($consume ($transform ($generate))))

Dependencies

The above code relies on the following primitives for lazy evaluation, described in SRFI-45:

  (define-syntax lazy
    (syntax-rules ()
      ((lazy exp) (cons 'suspension (lambda () exp)))))

  (define (strict x) (cons 'value x))

  (define-syntax delay
    (syntax-rules ()
      ((delay exp) (lazy (strict exp)))))

  (define (force promise)
    (case (car promise)
      ((value)      (cdr promise))
      ((suspension) (let ((val ((cdr promise))))
                      (set-car! promise (car val))
                      (set-cdr! promise (cdr val))
                      (force promise)))))

It also relies on the following macro for pattern matching on lists:

  (define-syntax match
    (syntax-rules ()
      ((match exp 
         (()      exp1)
         ((h . t) exp2))
       (let ((lst exp))
         (cond ((null? lst) exp1)
               ((pair? lst) (let ((h (car lst))
                                  (t (cdr lst)))
                              exp2))
               (else 'match-error))))))