CODEWITHSUNDEEP
emacselispsicp
quicoju
quicoju

Reputation: 1711

Implementing streams with elisp

I'm reading section 3.5 of the SICP book, and I'm trying to implement streams using Elisp. The book implements streams using the Scheme language as follows:

The core structure of a stream is a pair whose car is the current value of the sequence and its cdr is the promise of evaluating the next item, which is achieved with the following construction:

(define (cons-stream a b) (cons a (delay b)))

Where (delay b) is equivalent to (lambda () b).

When the cdr of this pair is evaluated, it forces the evaluation of the delayed element of the stream so we can get the next element and the implementation is as follows:

(define (stream-cdr stream) (force (cdr stream)))

Where (force delayed-object) is just the execution of (delayed-object).

With this construction we can now easily build recursive procedures with streams transparently as if they were regular lists like in map:

(define (stream-map proc stream)
    (if (stream-null? stream)
        the-empty-stream
      (cons-stream (proc (stream-car s))
                   (stream-map p (stream-cdr s)))))

I'm trying to write a similar stream implementation using Elisp, but I haven't found a way to implement delay so that it allows me to write recursive procedures in a similar fashion as with Scheme, currently my workaround is to put the delay as a lambda expression inside the recursive procedure like this:

(defun stream-map (proc stream)
  (lexical-let ((p proc)
                (s stream))
    (if (stream-null? stream)
        the-empty-stream
      (cons-stream (funcall p (stream-car s))
                   (lambda ()
                     (stream-map p (stream-cdr s)))))))

Which obviously doesn't look as nice as the Scheme implementation.

These are my Elisp version of the core functions for creating streams:

(defun cons-stream (a b) (cons a b))
(defun stream-cdr (stream) (sicp-force (cdr stream)))
(defun sicp-force (exp) (funcall exp))

How can I do to write the delay and the other stream functions so I don't have to put the lambda inside the recursive procedure?

Upvotes: 3

Views: 248

Answers (1)

quicoju
quicoju

Reputation: 1711

Thanks to @Gerstmann's suggestion I was able to write the construction I was looking for. The new implementation now looks like: 

(setq the-empty-stream nil)
(defun stream-null? (s) (eq s the-empty-stream))
(defun my/sicp-delay (exp) `(lambda () ,exp))
(defun my/sicp-force (exp) (funcall exp))

(defmacro my/cons-stream (a b) (list 'cons a (my/sicp-delay b)))
(defun my/stream-car (stream) (car stream))
(defun my/stream-cdr (stream) (my/sicp-force (cdr stream)))

Now I can write procedures that look just as clean as the Scheme implementation: 

(defun my/stream-enumerate-interval (low high)
  (lexical-let ((l low)
                (h high))
    (if (> l h)
        the-empty-stream
      (my/cons-stream low
                      (my/stream-enumerate-interval (1+ l) h)))))

; this returns 12
(my/stream-car (my/stream-cdr (my/stream-cdr (my/stream-enumerate-interval 10 20))))

Upvotes: 2

Related Questions