my attempt to do the exercises in sicp.

Monday, August 4, 2008

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


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



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

(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

(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.

No comments: