Functional Streams in Lisp Explained

I have been wanting to comment on jcs’s post on streams in lisp, and his take on what I did. But, I was traveling and having too much fun playing with Collatz sequences.

He is correct in that transporting the streams code from scheme to lisp is almost trivial, and jcs did that nicely and concisely in his post. As he also noticed, what I was trying to do was different. Probably, this is a good opportunity to explain.

Streams as purely functional data structures

In SICP, Abelson and Sussman conceive them as potentially infinite lazy lists. And they use the same interface as the regular lists. So, they have a car and a cdr which obey the same algebraic rules as the regular lists:

x = (cons (car x) (cdr x))

If one would like to develop streams from ground up as a functional data structure, one option is to think of them as objects with two specific functions: an iterator and an extractor. An iterator receives a head for the stream and returns another head, this time for the iterated stream. An extractor receives a head and returns a single element which you’d like to construct out of the stream and the head at the hand.

To make things clear: when I say the head I mean the whole sequence of elements constructed at a moment. Also, in the implementations below they are in the reverse order: from the last to the first. Don’t blame me: car is cheaper than (lambda (x) (car (reverse x))).

In this picture, a stream is purely functional: whoever has the head has the stream. No locks or semaphores. They are immutable, efficient, and with clever use of memoization for the iterators and extractors they are really fast.

The interface

The code for the interface consisted of three functions only. I had a take function:

(defun s-take (stream n &optional head)
   (destructuring-bind
       (iterator . extractor) stream
     (do* ((x head (funcall iterator x))
           (y nil (cons (funcall extractor x) y))
           (i n (1- i)))
          ((zerop i) y))))
S-TAKE

which would take from the stream a specific number of items; a map function which would apply a sequence of functions to the values after we extract them:

(defun s-map (stream &rest fns)
   (destructuring-bind
       (iterator . extractor) stream
     (cons iterator
           (lambda (x)
              (let ((y (funcall extractor x)))
                 (dolist (fn fns y)
                    (setf y (funcall fn y))))))))
S-MAP

and finally; a filter function which would filter the values extracted according to a list of predicates:

(defun s-filter (stream &rest preds)
   (destructuring-bind
       (iterator . extractor) stream  
     (cons (lambda (x)
              (do* ((y (funcall iterator x) (funcall iterator y))
                    (z (funcall extractor y) (funcall extractor y)))
                   ((every (lambda (pred) (funcall pred z)) preds) y)))
           extractor)))
S-FILTER

Some examples

For simple streams such as the natural numbers or arithmetic progressions, the extractor returns the last element of the head and the iterator increases this value and affixes to the head.

(defvar natural-numbers
   (cons (lambda (x)
            (if (null x)
               (list 1)
               (cons (1+ (car x)) x)))
         #'car))
NATURAL-NUMBERS

(s-take natural-numbers 10)
(10 9 8 7 6 5 4 3 2 1)

(defun arithmetic-progression (a b)
   (cons (lambda (x)
            (if (null x)
               (list b)
               (cons (+ a (car x)) x)))
         #'car))
ARITHMETIC-PROGRESSION

(s-take (arithmetic-progression 12 3) 10)
(111 99 87 75 63 51 39 27 15 3)

For the Fibonnacci sequence, the extractor is the same, but the iterator takes the last two values and affixes the sum to the head.

(defvar fibonacci
   (cons (lambda (x)
            (cond
               ((null x) (list 1))
               ((= 1 (length x)) (list 1 1))
               (t (cons (+ (car x) (cadr x)) x))))
         #'car))
FIBONACCI

(s-take fibonacci 10)
(55 34 21 13 8 5 3 2 1 1)

During the course of my experiments (2015-01-01-functional_streams.html) here and here I gave several examples (some of which I reproduced here), but today I will give a new one: I’d like to construct a stream of integers which will give the sums of squares of the first \(n\) integers. In that case, the iterator takes the last value of the list, adds one to it and then affixes to the head. The extractor on the other hand, takes the whole list and finds the sum of the squares.

(defvar sums-of-squares
   (cons (lambda (x)
            (if (null x)
               (list 1)
               (cons (1+ (car x)) x)))
         (lambda (x) (reduce #'+ (mapcar (lambda (i) (* i i)) x)))))
SUMS-OF-SQUARES
(s-take sums-of-squares 10)
(385 285 204 140 91 55 30 14 5 1)

Of course, we can get the same stream from natural-numbers using a map:

(s-take 
   (s-map 
      natural-numbers 
      (lambda (x) (* x (1+ x) (1+ (* 2 x)) (/ 6)))) 
   10)
(385 285 204 140 91 55 30 14 5 1)

but I was trying to make a point in saying that the extractor is an integral part of the stream, and in practice, may need to know the full head of the stream at the time of extraction, not just the last element.

Now, we can filter and map this stream to get new stream(s):

(defun binary-palindrome-p (x)
   (string-equal
      (format nil "~b" x)
      (reverse (format nil "~b" x))))
BINARY-PALINDROME-P

(s-take
   (s-map 
      (s-filter
         sums-of-squares
         #'oddp
         #'binary-palindrome-p)
      (lambda (x) (format nil "~b" x)))
   4)
(110011000101101000110011 1100110011 101 1)

Addendum

I forgot: there is also room for a reducer in the s-take interface which can easily obtained by changing the reducer from cons to any other reducer:

(defun s-take (stream n &optional head (reducer #'cons))
   (destructuring-bind
        (iterator . extractor) stream
     (do* ((x head (funcall iterator x))
           (y nil (funcall reducer (funcall extractor x) y))
           (i n (1- i)))
          ((zerop i) y))))

and one can call it as

(s-take 
   (s-map 
      natural-numbers
      (lambda (x) (* x x))
   10
   nil
   (lambda (x y) (+ (or x 0) (or y 0))))

385