Ex-3.18

(define (has-cycle? list)
  (define (already-in-list? x l)
    (cond
     ((null? l) #f)
     ((eq? (car l) x) #t)
     (else (already-in-list? x (cdr l)))))
  (let ((cache nil))
    (define (has-cycle-aux? list)
      (cond
       ((null? list) #f)
       ((already-in-list? (car list) cache)
        #t)
       (else
        (set! cache (cons (car list) cache))
        (has-cycle-aux? (cdr list)))))
    (has-cycle-aux? list))) 

Ex-3.17

(define (count-pairs x)
  (define (stored-in-list? x l)
    (cond
     ((null? l) #f)
     ((eq? (car l) x) #t)
     (else (stored-in-list? x (cdr l)))))
  (let ((cache nil))
    (define (count-pairs-aux x)
      (cond
       ((not (pair? x)) 0)
       ((stored-in-list? x cache)
        (+ (count-pairs-aux (car x))
           (count-pairs-aux (cdr x))))
       (else
        (set! cache (cons x cache))
        (+ (count-pairs-aux (car x))
           (count-pairs-aux (cdr x))
           1))))
    (count-pairs-aux x))) 

Ex-3.16

;returns 3
(define l1 (cons 1 (cons 2 (cons 3 nil))))

;returns 4
(define p (cons 1 2))
(define l2 (cons p (cons p 3)))

;returns 5
(define p (cons 1 2))
(define l3 (cons p (cons p p)))

;returns 7
(define p (cons 1 2))
(define p1 (cons p p))
(define l4 (cons p1 p1))

;never return at all
(define p (cons 1 2))
(define l5 (cons 1 (cons 2 p)))
(set-cdr! p l5)

Ch3, Section - 3.2 , some notes

Here I noticed two important things...

1. Once we introduce assignment, we can't consider a variable simply a name for a value, instead a variable must somehow designate a *place* where value is stored and with assignment value stored at that place can change.
For this reason, there is a difference between defining a variable and binding it to a value(storing value in the *place*).. in some languages like Oz, variables can exist without a binding and are called *unbound* variables.. and dataflow variables are another special variables which can be bound only once and if unbound then the calling thread waits unless that variable gets a binding.

2. A scheme procedure consists of 3 parts. A parameter list, code in the body and a pointer to the environment where its created. When it is applied *this* is the environment that is extended with bindings for parameters to arguments and not the one in which execution is happening.

Ex-3.8

(define y 1)
(define (f x)
  (set! y (* y x))
  y)
;trying on MIT/GNU Scheme      
1 ]=> (+ (f 0) (f 1))
;Value: 1

;so arguments are evaluated right to left

We need to set y back to 1 if we want to re-run.

Ex-3.7

(define (make-joint acc passwd another-passwd)
  ;check if passwd is correct
  (if (equal? "Incorrect Password" ((acc passwd 'deposit) 0))
      "Incorrect Password"
      (lambda (p m)
         (if (eq? p another-passwd)
             (acc passwd m) "Incorrect Password")))) 

Chapter-3 prologue

I found this very interesting...

When we design a large program, its dictated by our perception of the system to be modeled. And, there are two organization strategies arising from two different world views of the system.
The first concentrates on objects, viewing a large system as collection of objects changing with time. For each object we create a corresponding computational object and for each action a symbolic operation in our computational model.
The second strategy concentrates upon the streams of information that flow in the system.

In fact this chapter is all about representing the "change" and hence time in computations. And, the two views described above result in two different programming paradigms to deal with time called object oriented programming and stream based programming.


A friend often says, as these are just two views of the system so it should be possible to look at any system using any one of the two views and that in turn means that we should be able to take a system modeled with collection of objects and remodel it using the streams and viceversa.