sicp exercise 2.78

;; Exercise 2.78.  The internal procedures in the scheme-number package are essentially nothing more than calls to the primitive procedures +, -, etc. It was not possible to use the primitives of the language directly because our type-tag system requires that each data object have a type attached to it. In fact, however, all Lisp implementations do have a type system, which they use internally. Primitive predicates such as symbol? and number? determine whether data objects have particular types. Modify the definitions of type-tag, contents, and attach-tag from section 2.4.2 so that our generic system takes advantage of Scheme's internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as Scheme numbers rather than as pairs whose car is the symbol scheme-number.


(define (attach-tag tag oper)
(if (number? oper) oper
     (list tag oper)))

(define (type data)
  (if (number? data) 'scheme-number
      (car data)))

(define (contents data)
  (if (number? data) data
      (cadr data)))

sicp exercise 2.77

;; Exercise 2.77.  Louis Reasoner tries to evaluate the expression (magnitude z) where z is the object shown in figure 2.24. To his surprise, instead of the answer 5 he gets an error message from apply-generic, saying there is no method for the operation magnitude on the types (complex). He shows this interaction to Alyssa P. Hacker, who says ``The problem is that the complex-number selectors were never defined for complex numbers, just for polar and rectangular numbers. All you have to do to make this work is add the following to the complex package:''

;; (put 'real-part '(complex) real-part)
;; (put 'imag-part '(complex) imag-part)
;; (put 'magnitude '(complex) magnitude)
;; (put 'angle '(complex) angle)

;; Describe in detail why this works. As an example, trace through all the procedures called in evaluating the expression (magnitude z) where z is the object shown in figure 2.24. In particular, how many times is apply-generic invoked? What procedure is dispatched to in each case?


;; Answer
;; this works because magnitude is defined for complex to inturn invoke magnitude for rectangular.

;; The apply generic is invoked twice. once for complex->magnitude and once for rectangular->magnitude

sicp exercise 2.76

;; Exercise 2.76.  As a large system with generic operations evolves, new types of data objects or new operations may be needed. For each of the three strategies -- generic operations with explicit dispatch, data-directed style, and message-passing-style -- describe the changes that must be made to a system in order to add new types or new operations. Which organization would be most appropriate for a system in which new types must often be added? Which would be most appropriate for a system in which new operations must often be added?


;; explicit dispatch
;; Need to add a dispatch for every type and operation pair

;; data-directed style
;; since this style is additive, the new set of types and its operations can be added seperately from others. the changes are local to the set of new types being added.

;; message-passing style
;; the type takes care of its own operations. the changes are localised to the new type being added.

;; for a system where new types must be often added, message passing is better

;; for a system where new operations must be often added, data directed is better

sicp exercise 2.75

;; Exercise 2.75.  Implement the constructor make-from-mag-ang in message-passing style. This procedure should be analogous to the make-from-real-imag procedure given above.


(define (make-from-mag-ang x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) (* x (cos y)))
          ((eq? op 'imag-part) (* x (sin y)))
          ((eq? op 'magnitude) x)
          ((eq? op 'angle) y)
          (else
           (error "Unknown op -- MAKE-FROM-REAL-IMAG" op))))
  dispatch)

sicp exercise 2.74

;; Exercise 2.74.  Insatiable Enterprises, Inc., is a highly decentralized conglomerate company consisting of a large number of independent divisions located all over the world. The company's computer facilities have just been interconnected by means of a clever network-interfacing scheme that makes the entire network appear to any user to be a single computer. Insatiable's president, in her first attempt to exploit the ability of the network to extract administrative information from division files, is dismayed to discover that, although all the division files have been implemented as data structures in Scheme, the particular data structure used varies from division to division. A meeting of division managers is hastily called to search for a strategy to integrate the files that will satisfy headquarters' needs while preserving the existing autonomy of the divisions.

;; Show how such a strategy can be implemented with data-directed programming. As an example, suppose that each division's personnel records consist of a single file, which contains a set of records keyed on employees' names. The structure of the set varies from division to division. Furthermore, each employee's record is itself a set (structured differently from division to division) that contains information keyed under identifiers such as address and salary. In particular:

;; a.  Implement for headquarters a get-record procedure that retrieves a specified employee's record from a specified personnel file. The procedure should be applicable to any division's file. Explain how the individual divisions' files should be structured. In particular, what type information must be supplied?

;; b.  Implement for headquarters a get-salary procedure that returns the salary information from a given employee's record from any division's personnel file. How should the record be structured in order to make this operation work?

;; c.  Implement for headquarters a find-employee-record procedure. This should search all the divisions' files for the record of a given employee and return the record. Assume that this procedure takes as arguments an employee's name and a list of all the divisions' files.

;; d.  When Insatiable takes over a new company, what changes must be made in order to incorporate the new personnel information into the central system?



;; Answer a., b., c.
;; Lets assume that there are 2 divisions, named bangalore and shenzhen.
;;
;; Bangalore Division
;; the bangalore division's file contains set of records realized as balanced binary tree
;; the employee record in bangalore division is an unordered list
;;
;; ShenZhen Division
;; the shenzhen division's file contains set of records realized as an unordered list
;; the employee record in shenzhen division is a pair of pairs
;; moreover there are two addresses for every shenzhen employee


(define *op-table* (make-hash-table 10))
(define (put op type proc)
  (hash-set! *op-table* (list op type) proc))
(define (get op type)
  (hash-ref *op-table* (list op type) '()))


(define (attach-type type data) (cons type data))
(define (type data) (car data))
(define (contents data) (cdr data))

(define (apply-generic oper data)
((get oper (type data)) (contents data)))

(define (install-bangalore-division)
  ;; bangalore record system
  (define (entry tree) (car tree))
  (define (left-branch tree) (cadr tree))
  (define (right-branch tree) (caddr tree))
  (define (make-tree entry left right)
    (list entry left right))

  (define (get-record empname file)
    (cond ((null? file) '())
          ((string=? (get-name (entry file)) empname) (entry file))
          ((string>? (get-name (entry file)) empname) (get-record empname (right-branch file)))
          ((string<? (get-name (entry file)) empname) (get-record empname (left-branch file)))))

  (define (make-record empname address salary)
    (list empname address salary))
  (define (get-name record)
    (car record))
  (define (get-address record)
    (cadr record))
  (define (get-salary record)
    (caddr record))

  (define (insert-file record file)
    (cond ((null? file) (make-tree record '() '()))
          ((string=? (get-name record) (get-name (entry file))) file)
          ((string>? (get-name record) (get-name (entry file)))
           (make-tree (entry file)
                      (insert-file record (left-branch file))
                      (right-branch file)))
          ((string<? (get-name record) (get-name (entry file)))
           (make-tree (entry file)
                      (left-branch file)
                      (insert-file record (right-branch file))))))

  (define (make-file records)
    (define (iter file recs)
      (cond ((null? recs) file)
            (else (iter (insert-file (car recs) file) (cdr recs)))))
    (iter '() records))


  ;; interface to the rest of the system
  (define (type oper) (attach-type 'bangalore oper))
  (put 'make-record   'bangalore (lambda(x y z) (type (make-record x y z))))
  (put 'get-name      'bangalore get-name)
  (put 'get-address   'bangalore get-address)
  (put 'get-salary    'bangalore get-salary)
  (put 'make-file     'bangalore (lambda(x) (type (make-file (map contents x)))))
  (put 'get-record    'bangalore (lambda(x y) (type (get-record x y))))

  'bangalore-done)


(define (install-shenzhen-division)
  (define (make-record name addr1 addr2 salary)
    (cons (cons name salary)
          (cons addr1 addr2)))

  (define (get-name record)
    (caar record))
  (define (get-salary record)
    (cdar record))
  (define (get-address record)
    (cadr record))
  (define (get-address-2 record)
    (cddr record))

  (define (get-record empname file)
    (cond ((null? file) '())
          ((string=? empname (get-name (car file))) (car file))
          (else (get-record empname (cdr file)))))

  (define (make-file records) records)

  ;; interface to the rest of the system
  (define (type oper) (attach-type 'shenzhen oper))
  (put 'make-record   'shenzhen (lambda(w x y z) (type (make-record w x y z))))
  (put 'get-name      'shenzhen get-name)
  (put 'get-address   'shenzhen get-address)
  (put 'get-salary    'shenzhen get-salary)
  (put 'make-file     'shenzhen (lambda(x) (type (make-file (map contents x)))))
  (put 'get-record    'shenzhen (lambda(x y) (type (get-record x y))))

  (put 'get-address-2 'shenzhen get-address-2)

  'shenzhen-done)

(install-bangalore-division)
(install-shenzhen-division)


;; central employee system
(define (make-record-bangalore name addr salary)
  ((get 'make-record 'bangalore) name addr salary))
(define (make-record-shenzhen name addr1 addr2 salary)
  ((get 'make-record 'shenzhen)  name addr1 addr2 salary))

(define (make-file-bangalore . records)
  ((get 'make-file   'bangalore) records))
(define (make-file-shenzhen . records)
  ((get 'make-file   'shenzhen)  records))

(define (get-record  name file)
  ((get 'get-record (type file)) name (contents file)))

(define (get-name    record) (apply-generic 'get-name    record))
(define (get-address record) (apply-generic 'get-address record))
(define (get-salary  record) (apply-generic 'get-salary  record))
(define (get-address-2 record) (apply-generic 'get-address-2 record))

(define (find-employee-record emp all-files)
  (define (iter files)
    (cond ((null? files) '())
          (else (let ((rec (get-record emp (car files))))
                  (cond ((null? (contents rec)) (iter (cdr files)))
                        (else rec))))))
  (iter all-files))

;; testing
(define bang-rec-1 (make-record-bangalore "shiv"   "whilefield"    100))
(define bang-rec-2 (make-record-bangalore "vimal"  "malleshpallya" 200))
(define bang-rec-3 (make-record-bangalore "rahul"  "jp-nagar"      300))
(define bang-rec-4 (make-record-bangalore "jayant" "btm-layout"    400))
(define bang-file  (make-file-bangalore bang-rec-1
                                        bang-rec-2
                                        bang-rec-3
                                        bang-rec-4))

(define shen-rec-1 (make-record-shenzhen "yukai"  "bai-cao"  "office"  100))
(define shen-rec-2 (make-record-shenzhen "jgwen"  "d-town"   "office"  200))
(define shen-rec-3 (make-record-shenzhen "sunxu"  "bai-cao"  "office"  300))
(define shen-rec-4 (make-record-shenzhen "xulai"  "nanshan"  "office"  400))
(define shen-file  (make-file-shenzhen shen-rec-1
                                       shen-rec-2
                                       shen-rec-3
                                       shen-rec-4))


(define test-bang (get-record "shiv" bang-file))
(display (get-address test-bang)) (newline)
;(display (get-address-2 test-bang)) (newline) ;; this method is defined for only shenzhen branch
(display (get-salary test-bang)) (newline)

(define test-shen (get-record "xulai" shen-file))
(display (get-address test-shen)) (newline)
(display (get-address-2 test-shen)) (newline)
(display (get-salary test-shen)) (newline)

(display (find-employee-record "jayant" (list bang-file shen-file))) (newline)
(display (find-employee-record "jgwen"  (list bang-file shen-file))) (newline)
(display (find-employee-record "tatha"  (list bang-file shen-file))) (newline)


;; d.
;; if Insatiable aquires another company, then its personnel system needs to be added to the type table and installed in the central system. The methods in the central system need not change at all.

sicp exercise 2.73

;; Exercise 2.73.  Section 2.3.2 described a program that performs symbolic differentiation:

;; (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))))
;;         <more rules can be added here>
;;         (else (error "unknown expression type -- DERIV" exp))))

;; We can regard this program as performing a dispatch on the type of the expression to be differentiated. In this situation the ``type tag'' of the datum is the algebraic operator symbol (such as +) and the operation being performed is deriv. We can transform this program into data-directed style by rewriting the basic derivative procedure as

;; (define (deriv exp var)
;;    (cond ((number? exp) 0)
;;          ((variable? exp) (if (same-variable? exp var) 1 0))
;;          (else ((get 'deriv (operator exp)) (operands exp)
;;                                             var))))
;; (define (operator exp) (car exp))
;; (define (operands exp) (cdr exp))

;; a.  Explain what was done above. Why can't we assimilate the predicates number? and variable? into the data-directed dispatch?

;; b.  Write the procedures for derivatives of sums and products, and the auxiliary code required to install them in the table used by the program above.

;; c.  Choose any additional differentiation rule that you like, such as the one for exponents (exercise 2.56), and install it in this data-directed system.

;; d.  In this simple algebraic manipulator the type of an expression is the algebraic operator that binds it together. Suppose, however, we indexed the procedures in the opposite way, so that the dispatch line in deriv looked like

;; ((get (operator exp) 'deriv) (operands exp) var)

;; What corresponding changes to the derivative system are required?


;; a.
;; because the consitions number? and variable? do not call deriv. whereas other numerical conditions call deriv.

;; b.

(define (deriv-sum operands var)
  (make-sum (deriv (car operands) var)
            (deriv (cadr operands) var)))

(define (deriv-product operands var)
  (make-sum (make-product (cadr operands) (deriv (car operands) var))
            (make-product (car operands) (deriv (cadr operands) var))))


(define (install-deriv)
  (put 'deriv '+ deriv-sum)
  (put 'deriv '* deriv-product)
  'done)

;; c.

(define (deriv-exponentiation operands var)
  (make-product (cadr operands)
                (make-product (make-exponentiation (car operands)
                                                   (- (cadr operands) 1))
                              (deriv (car operands) var))))


(define (install-deriv)
  (put 'deriv '** deriv-exponentiation)
  'done)

;; d. the derivative system will change as follows. the order of operator and procedure name shall be reversed while installing the derivative system

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get (operator exp) 'deriv) (operands exp)
                                            var))))


(define (install-deriv)
  (put '+ 'deriv deriv-sum)
  (put '* 'deriv deriv-product)
  'done)

sicp exercise 2.72

;; Exercise 2.72.  Consider the encoding procedure that you designed in exercise 2.68. What is the order of growth in the number of steps needed to encode a symbol? Be sure to include the number of steps needed to search the symbol list at each node encountered. To answer this question in general is difficult. Consider the special case where the relative frequencies of the n symbols are as described in exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed to encode the most frequent and least frequent symbols in the alphabet.

;; Answer.
;; If the relative frequencies are 1, 2, 4, ..., 2^n-1 , the order of growth is O(n^2)