Ex-3.47

A mutex is an object that supports two operations - aquire and release. Once a mutex is aquired, no other process can aquire it unless it has been released. mutex is implemented using an *atomic* operation test-and-set! that tests value in a cell, returns true if cell value is already set to true or else sets the cell value to true and returns false.

A semaphore (of size n) is a generalization of a mutex. Like a mutex, a semaphore supports acquire and release operations, but it is more general in that up to n processes can acquire it concurrently. Additional processes that attempt to acquire the semaphore must wait for release operations.

(a) - semaphore implementation using mutex

(define (make-semaphore n)
(let ((m (make-mutex))
   (count 0)
   (result false))
(define (aquire)
 (m 'aquire)
 (if (> count 0)
     (set! count (- count 1)))
 (m 'release))
(define (dispatch msg)
 (cond
  ((eq? msg 'aquire) (aquire))
  ((eq? msg 'release) (release))
  (else "Unknown msg to SEMAPHORE: " msg)))
dispatch))

(b) - semaphore implementation using test-and-set

(define (clear! cell)
(set-car! cell false))

(define (make-semaphore n)
;makes a list of n cells
(define (make-cells n)
  (define (iter n a)
    (if (= n 0) a
        (iter (- n 1) (cons (list false) a))))
  (iter n '()))

(let ((cells (make-cells n)))
  (define (aquire)
    (define (iter cells)
      (cond
       ((null? cells) (aquire))
       ((not (test-and-set! (car cells)))
        true)
       (else (iter (cdr cells)))))
    (iter cells))
  (define (release)
    (define (iter cells)
      (cond
       ((null? cells)
        ;all the cells are already in released state
        ;nothing to do
        'ok)
       ((caar cells)
        (clear! (car cells)) 'ok)
       (else (iter (cdr cells)))))
    (iter cells))
  (define (dispatch msg)
    (cond
     ((eq? msg 'aquire) (aquire))
     ((eq? msg 'release) (release))
     (else "Unknown msg to SEMAPHORE: " msg)))
  dispatch))

Serializer Implementation..

Serializer is implemented in terms of another primitive called "mutex", that has two operations to "aquire" and "release" it. At one time only one process can aquire the mutex, other processes trying to aquire it at that time will block untill the mutex is released by the process that has the mutex aquired.
BTW, if multiple processes were waiting for the mutex to be released.. which of those processes get to aquire the mutex depends upon a component called scheduler.

event-driven simulation

In section 3.3.4, SICP presents a digital circuit simulator that implements it using a design called event-driven programming. In such designs basically actions("events") triggers further events that happen at a later time and those in turn trigger further events and so on.
To be particular about the example given in the book, Wire is the main object where we can set signal and can add any number of events(no-arg procedures). Whenever a signal changes(event of signal change happens), it triggers all the events added to it and those events when happen change signal on other wires which in turn trigger more events and so on... that is how the signal propagates.

I also wrote a port of this example in scala here.

functions and relations

Usually, we create programs that do one directional computations, which performs operations on given quantities to produce desired output. In some models, we don't have such one directional operations but we know the relation among quantities like the relation between celsius and fahrenheit, 9C = 5(F - 32). Translating this equation into a traditional computer language will force us to calculate one in terms of another instead of specifying the relation and measuring one when other changes. Programming paradigm where we can specify relations is called logic programming.

Ex-3.19

Method-1:
We basically keep on visiting next pair in the list. Whenever we visit a pair, we tag it saying that it was visited before. Moreover when we visit a pair, we check if it is already visited and if we find an already visited pair before reaching the list end then it is cyclic. The issue with this algorithm is that it is destructive in nature that is it will change the input list.

(define (visit-car list)
  (set-car! list (cons '*visited* (car list))))
(define (visited? x)
  (and (pair? x) (eq? (car x) '*visited*)))
(define (has-cycle? list)
  (cond
   ((null? list) #f)
   ((visited? (car list)) #t)
   (else (visit-car list)
         (has-cycle? (cdr list))))) 

Method-2:
This is a partial implementation of idea of Floyd's cycle finding algorithm aka tortoise and the hare algorithm, where we maintain two pointers(tortoise, hare), second(hare) moving twice as fast the first(tortoise) one and keep comparing them in each iteration. List has cycles if pointers become equal before encountering end of list.

(define (has-cycle? list)
  (define (has-cycle-aux? l1 l2)
    (cond
     ((eq? l1 l2) #t)
     (else
      (if (not (pair? (cdr l2))) #f
          (has-cycle-aux? (cdr l1) (cddr l2))))))
  (if (null? list) #f
      (has-cycle-aux? list (cdr list)))) 

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.

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.

Ex-2.76

I'm going to present views on all three strategies with respect to adding new data type and operations.

Explicit dispatch programming:
Adding new Data Type:
We must put appropriate code to support new data type in *all* generic operation definitions and write constructor for it.
Adding new Operation:
Implement it for all data types and We must create a generic operation for it that does type dispatch on all the data types.

Data directed programming:
Adding new Data Type:
No change to generic operation, but need to put all the operations for this data type into operation-type table.
Adding new Operation:
Put the new operation definitions for all data types into operation-type table and Need to create a generic operation which is very simple in this case, that will just do a get on the table to find appropriate procedure.

Message passing style programming:
Adding new Data Type:
We just need to create a new constructor for it(that returns dispatch procedure).
Adding new Operation:
We have to modify all the constructors to include this new operations.

Most appropriate organization for frequent addition of new data types would be the message passing style and same for frequent addition of operations would be data directed programming.

Ex-2.73

a:
We moved from dispatch on type way of programming to data directed programming that helps bring modularity into the program that is it makes easier to change one part of the program independent of the others. We can't put number, variable into same data directed dispatch as they really don't have type tags and can't be put in operation-type table.

b:

(define (deriv-sum exp)
  (make-sum (deriv (addend exp) var)
            (deriv (augend exp) var)))
(define (deriv-product exp)
  (make-sum
   (make-product (multiplier exp)
                 (deriv (multiplicand exp) var))
   (make-product (deriv (multiplier exp) var)
                 (multiplicand exp))))
;aux code to put them in table
(put 'deriv '(+) deriv-sum)
(put 'deriv '(*) deriv-product)

c:

(define (deriv-exponent exp)
  (make-product
   (exponent exp)
   (make-product
    (make-exponentiation (base exp)
                         (- (exponent exp) 1))
    (deriv (base exp) var))))
(put 'deriv '(**) deriv-exponent) 

d: none

Ex-2.64

;a
Once again, this demonstrates the power of wishful thinking. (partial-tree elt n) assumes that a left-sub-tree with first (quotien (- n 1) 2) elements of elt and a right-sub-tree of last (- n (+ left-size 1)) elements of elt is available and then it just constructs the tree using left-sub-tree, right-sub-tree and this-entry(the middle entry thats not included in any of the sub-trees).

1 ]=> (list->tree '(1 3 5 7 9 11))
;Value 19: (5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

;b
t(n) = 2t(n/2), hence O(n)

Section-2.3.2;Ex-2.56,2.57,2.58

This section is dedicated to create a symbolic differentiation program that demonstrates the concept of data-abstraction. The main derivation algorithm works on the abstract objects such as sum, variable and product with no knowledge of how they are represented, so we can change their representation any time without touching derivation algorithm.
Another thing to notice is the power of the lisp-notation, author first describes the rules of derivation and then translates them into scheme using cond and that translation into scheme just looks straight forward. What I'm saying is that how easy it was to convert math rules into working scheme program.

;code from book  to run the examples
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (make-sum a1 a2) (list '+ a1 a2))
(define (make-product m1 m2) (list '* m1 m2))
(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (product? x)
  (and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list '+ a1 a2))))
(define (=number? exp num)
  (and (number? exp) (= exp num)))
(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2)))) 

;Ex-2.56

(define (make-exponentiation base exponent)
  (cond
   ((= exponent 0) 1)
   ((= exponent 1) base)
   (else
    (list '** base exponent))))
(define (exponentiation? exp)
  (eq? (car exp) '**))
(define (base exp)
  (cadr exp))
(define (exponent exp)
  (caddr exp))

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp))))
        ((exponentiation? exp)
         (make-product
          (exponent exp)
          (make-product
           (make-exponentiation (base exp)
                                (- (exponent exp) 1))
           (deriv (base exp) var))))
        (else
         (error "unknown expression type -- DERIV" exp))))

;Ex-2.57

(define (make-sum a1 a2 . a)
  ;find sum of all the numbers in given args
  (define (number-sum args sum)
    (cond
     ((null? args) sum)
     ((number? (car args))
      (number-sum (cdr args) (+ sum (car args))))
     (else (number-sum (cdr args) sum))))
  ;list only the symbols from given list of args
  (define (symbols-only args)
    (filter (lambda (x) (not (number? x))) args))
  
  (let ((sum (number-sum (cons a1 (cons a2 a)) 0))
        (symbols (symbols-only (cons a1 (cons a2 a)))))
    (cond
     ((and (= 0 sum)
           (= 0 (length symbols))) 0)
     ((and (= 0 sum)
           (= 1 (length symbols))) (car symbols))
     ((and (= 0 sum)
           (apply list (cons '+ symbols))))
     ((= (length symbols) 0) sum)
     (else (apply list (cons '+ (cons sum symbols)))))))

(define (addend exp)
  (cadr exp))
(define (augend exp)
  (if (> (length (cddr exp)) 1)
      (apply make-sum (cddr exp))
      (caddr exp)))
;tests for make-sum
(make-sum 1 2) ;3
(make-sum 1 'a) ;(+ 1 a)
(make-sum 1 -1 'a) ;a
(make-sum 1 -1) ;0
(make-sum 1 -2 'a 'b)  ;(+ -1 a b)
(make-sum 1 'a 'b 'c '3) ;(+ 4 a b c)

(define (make-product a1 a2 . a)
  ;find sum of all the numbers in given args
  (define (number-prod args prod)
    (cond
     ((null? args) prod)
     ((number? (car args))
      (number-prod (cdr args) (* prod (car args))))
     (else (number-prod (cdr args) prod))))
  ;list only the symbols from given list of args
  (define (symbols-only args)
    (filter (lambda (x) (not (number? x))) args))
  
  (let ((prod (number-prod (cons a1 (cons a2 a)) 1))
        (symbols (symbols-only (cons a1 (cons a2 a)))))
    (cond
     ((= prod 0) 0)
     ((and (= 1 prod)
           (= 0 (length symbols))) 1)
     ((and (= 1 prod)
           (= 1 (length symbols))) (car symbols))
     ((and (= 1 prod)
           (apply list (cons '* symbols))))
     ((= 0 (length symbols)) prod)
     (else
      (apply list (cons '* (cons prod symbols)))))))

(define (multiplier exp)
  (cadr exp))
(define (multiplicand exp)
  (if (> (length (cddr exp)) 1)
      (apply make-product (cddr exp))
      (caddr exp)))
;tests for make-product
(make-product 1 2) ;2
(make-product 1 'a) ;a
(make-product 1 -1 'a) ;(* -1 a)
(make-product 1 -1 'a 'b) ;(* -1 a b)
(make-product 1 'a 'b 'c 3) ;(* 3 a b c)
(make-product 1 'a 'b 'c 3 0) 0 

;Ex-2.58
;a

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))
(define (=number? exp num)
  (and (number? exp) (= exp num)))
(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))
(define (sum? x)
  (and (pair? x)
       (pair? (cdr x))
       (eq? (cadr x) '+)))
(define (addend s) (car s))
(define (augend s) (caddr s))
(define (product? x)
  (and (pair? x)
       (pair? (cdr x))
       (eq? (cadr x) '*)))
(define (multiplier p) (car p))
(define (multiplicand p) (caddr p))

;b - TODO

Ex-2.38

Result from fold-left and fold-right is same only when op is such that (op x y) is equal to (op y x), mathematically its called the commutative property.

Ex-2.32

(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
        (append rest
                (map (lambda (x)
                       (cons (car s) x)) rest)))))

Why it works?
Wishful thinking :)
we assumed that we got subsets of (cdr s), now all we need to think is how to get additional subsets of s that contain (car s) and the answer is simply to include (car s) in all the subsets of (cdr s).

Ex-2.29

;a

(define (left-branch m)
  (car m))
(define (right-branch m)
  (cadr m))
(define (branch-length b)
  (car b))
(define (branch-structure b)
  (cadr b))

;b

;total weight of a mobile
(define (total-weight m)
  (+ (branch-total-weight (left-branch m))
     (branch-total-weight (right-branch m))))


;find total weight of a branch
(define (branch-total-weight b)
  (if (pair? (branch-structure b))
             (total-weight (branch-structure b))
             (branch-structure b)))

;test
(define b1 (make-branch 1 2))
(define b2 (make-branch 1 3))
(define m1  (make-mobile b1 b2))
(define b3 (make-branch 1 5))
(define b4 (make-branch 1 m1))
(define m (make-mobile b3 b4))
(total-weight m)
;Value: 10 

;c

(define (balanced? m)
  (let ((lb (left-branch m))
        (rb (right-branch m)))
    (and
     (branch-balanced? lb)
     (branch-balanced? rb)
     (=
      (* (branch-length lb) (branch-total-weight lb))
      (* (branch-length rb) (branch-total-weight rb))))))
;see if a branch has a mobile structure and its
;balanced, if it has weight then return true
(define (branch-balanced? b)
  (if (pair? (branch-structure b))
             (balanced? (branch-structure b))
             #t))

;test
(define b1 (make-branch 1 2))
(define b2 (make-branch 1 3))
(define m1  (make-mobile b1 b2))
(define b3 (make-branch 1 5))
(define b4 (make-branch 1 m1))
(define m (make-mobile b3 b4))
(balanced? m)
;Value: #f
(define b2 (make-branch 1 2))
(define m1  (make-mobile b1 b2))
(define b4 (make-branch 1 m1))
(define m (make-mobile b4 b4))
;value: #t 

;d
Since we abstracted out the details of how we select various component of mobile and branch, so only selectors need to change.

(define (left-branch m)
  (car m))
(define (right-branch m)
  (cdr m))
(define (branch-length b)
  (car b))
(define (branch-structure b)
  (cdr b))

Ex-2.28

(define (fringe tree)
  (cond
   ((null? tree) '())
   ((pair? tree)
    (append (fringe (car tree)) (fringe (cdr tree))))
   (else (list tree)))) 

Used wishful thinking here. I thought like this, If we knew the fringes of left and right subtree then the answer would be to just append them and this does the trick :).

Takeaways from chapter 1 and 2 of SICP

find it here