Scheme – Stream Implementation in Scheme

scheme

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

Best Answer

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

Related Topic