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 ()

(define (force 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?


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 ()

(define-syntax stream
  (syntax-rules ()
    ((stream a b)
     (cons a (delay b)))))
  • 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. – Stefan Hanke May 28 '12 at 12:07

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


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: 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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