Search code examples
schemelispsicpdelayed-execution

scheme simple stream-map will not work in SICP example


An excerpt from SICP book, For the last line given there is problem with scheme code compilation, As I see it, the functions sqr and shower are both functions of single argument that return a single value. And hence should work. For the below given code in scheme:

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

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

;; cons-stream needs to be a macro

(define-syntax cons-stream
  (syntax-rules ()
    [(_ a b) (cons a (delay b))]
    ))

(define the-empty-stream '())

(define stream-null? null?)

;; define stream-for-each
;; run a procedure on each element of stream
(define (stream-for-each proc stream)
  (if (stream-null? stream)
      'done
      (begin (proc (stream-car stream))
             (stream-for-each proc (stream-cdr stream)))))

(define test-stream (cons-stream 2 (cons-stream 3 (cons-stream 4 '()))))

;; displays passed argument but with a newline
(define (display-line x)
  (newline)
  (display x))

(define (display-stream stream)
  (stream-for-each display-line stream))

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

(define (sqr x)
  (* x x))

(define (stream-enumerate-interval low hi)
  (if (> low hi)
      '()
      (cons-stream low (stream-enumerate-interval (+ 1 low) hi))))

(define (shower x)
  (display-line x)
  x)

;; this works
(define yyy (stream-map sqr (stream-enumerate-interval 1 10)))


;; reason why below wont work?
;; (define xxx (stream-map shower (stream-enumerate-interval 1 10)))

Also as per SICP book, it defines a different version of stream-map that allows procedures that accepts procedures that can take multiple arguments.

I fail to understand the need for a different stream-map and why above stream-map code on the last line won't work


Solution

  • Both of them work, but since stream-map is lazy you won't get them computed in full unless you do something to force it. Eg. lets make stream->list:

    (define (stream->list stream)
      (if (stream-null? stream)
          '()
          (cons (stream-car stream)
                (stream->list (stream-cdr stream)))))
    
    (stream->list yyy)
    ; ==> (1 4 9 16 25 36 49 64 81 100)
    
    (stream->list zzz)
    ; ==> (1 2 3 4 5 6 7 8 9 10) (and as a side effect prints then one line at a time)
    

    The fact is the actual computation on the rest of the list is never ever done unless you try to access the value. stream->list forces the computation of the whole stream so then it gets computed.

    Notice that the sicp streams always force the first value regardless. This is a simplification that other stream libraries have fixed so in SRFI-41 you don't have any side effect unless you access the result.

    #!r6rs
    (import (rnrs)
            (srfi :41))
    
    ;; nothing is displayed after this expression is evaluated 
    (define squares (stream-map (lambda (x) (shower (* x x)))
                                (stream-from 0)))
    
    (stream-car squares)
    ; ==> 0 (displays "\n0")
    
    (stream->list 4 squares)
    ; ==> (0 1 4 9) 
    ; (displayes "\n1\n4\n9" since "0" is already calculated.)