3

After working my way through SICP I decided to work though some Project Euler problems using scheme. In this particular problem I am trying to generate an infinite stream of integers however I am recieving an error from the MIT Scheme interpreter.

;Aborting!: maximum recursion depth exceeded

This leads me to believe my stream implementation is incorrect however after comparing my code against that in the book I can not find any errors.

(define (delay x)
  (lambda ()
    (x)))

(define (force x)
  (x))

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

(define (car-stream s)
  (car s))

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

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

The error occurs when I run the following code:

(define n (integers-starting-from 1))

Where have I gone wrong?

EDIT:

Thanks to Chris Jester-Young below I have it working now. The correct implementation of delay and stream are as follows.

(define-syntax delay
  (syntax-rules ()
    ((delay expr)
     (lambda ()
       (expr))))

(define-syntax stream
  (syntax-rules ()
    ((stream a b)
     (cons a (delay b)))))
1
  • Fyi, the book assumes that both cons-stream and delay be special forms. Another possibility is to run that code in an evaluator with normal-order evaluation. May 28 '12 at 12:07
6

Both delay and cons-stream need to be macros; otherwise your recursive call wouldn't really be delayed.

3

Another way to fix your code is to embed the recursive call to integers-starting-from in a lambda:

    (define (integers-starting-from n)
      (cons-stream n (lambda () (integers-starting-from (+ n 1)))))

This allows you to keep the definitions of delay and cons-stream as they are in SICP.

1
  • +1: AFAIU this is the only option in a language that does not have macros or lazy evaluation, e.g. Python.
    – Giorgio
    Jun 3 '14 at 21:16
-1
(define-syntax delay
  (syntax-rules ()
    ((delay expr)
     (lambda ()
       (expr))))

is wrong. Parens around expr will cause an error. Should be:

(define-syntax delay
    (syntax-rules ()
        ((delay exp)  (lambda() exp))))

Check out https://www.lvguowei.me/post/sicp-goodness-stream-1/ for a version that includes memo-proc.

Not the answer you're looking for? Browse other questions tagged or ask your own question.