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:- Implement for headquarters a
get-recordprocedure 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? - Implement for headquarters a
get-salaryprocedure 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? - Implement for headquarters a
find-employee-recordprocedure. 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. - When Insatiable takes over a new company, what changes must be made in order to incorporate the new personnel information into the central system?
find-employee-record returns only the first record encountered in all of the divisions' files, despite there being employees in different divisions with the same name.Human Resource Management Systems (HRMS) that have had even the smallest amount of thought put into their data model will uses something like an employee ID or a government-issued ID (such as a social security number or national insurance number) as a key. Such IDs are intended to be unique, and so avoid the collisions.
Anyway, we'll run with employee name as the key since that's what the exercise states...
(a) Retrieving an Employee's Record for a Given Division
Before we start to address
get-record itself, we should first have a think about the general problem. We have a potentially large number of divisions, each of which structures its data file in a different way. We wish to expose a common interface for accessing this data, regardless of which division the data is from, and so abstract away these differences. In order to do this we will need to be able to apply operations (such as get-record) to any of the divisions' files and successfully navigate the data structures and perform the appropriate processing.As noted in the exercise, a strategy based upon data-directed programming can be used to achieve this without ending up with a large amount of per-data structure logic (and a large maintenance headache!) embedded in each procedure in our common interface. Instead we can install operations on a per-type basis in a table, tag each data structure with an appropriate type tag and then use the tag embedded in a particular piece of data to retrieve the appropriate version of an operation we wish to apply.
In section 2.4.3 the authors provide us with two procedures for installing and retrieving operations:
get and put respectively (and, if you're using DrRacket, I gave the appropriate magic for getting these working in the last exercise). These two procedures have a pair of common operands: the name of the operation and the type of the data the operation is applied to. Given this, it seems obvious that the name of the operation should correspond to the operation we are trying to apply (such as get-record), while the type of the data should be a unique per-division identifier. If we continue with the "names as keys" theme then this could be as simple as the division's name.Section 2.4.3 also shows us that, provided the data is tagged with the type, we can then extract the type from the data and use that to retrieve operations appropriate to the data type. This then answers the question posed in the exercise: "what type information must be supplied?" Each division's file must be tagged with the division's identifier under which its operations are registered. We can perform the tagging and extract both the tag and the data using the procedures
attach-tag, type-tag and contents, which were introduced in section 2.4.2.Now let's start thinking about implementing
get-record...First let's extend the statement from the previous paragraph a bit further. Not only must each division's file must be tagged with the division's identifier under which its operations are registered, but any data structure returned by our common interface to which further data-directed operations may be applied must be tagged with the division's identifier.
For example,
get-record is going to return a record to which get-salary may be applied. In order for get-salary to find the appropriate per-division operation to apply to retrieve the salary the record itself must be tagged with the division's identifier. Rather than requiring each division's implementation of get-record to perform this tagging we can actually move the tagging into the common get-record implementation, simplifying the process.We also need to think about what we want the actual interface to be. Let's make it a requirement that each division's
get-record operation returns the record (untagged) if it's present, and returns #f if it's not. That way we can try to retrieve the record, check to see if we've got it and, if so, tag it with the division's tag.That should give us enough to implement
get-record:
(define (get-record employee-name personnel-file)
(let ((record ((get 'get-record (type-tag personnel-file))
employee-name
(contents personnel-file))))
(if record
(attach-tag (type-tag personnel-file) record)
#f)))
We'll test these out at the end, where I'll also introduce a couple of divisions' personnel files and some extensions.(b) Retrieving an Employee's Salary from their Employee Record
It's worth noting that we've already answered the question posed in this part of the exercise: "How should the record be structured in order to make this operation work?" We previously stated that "...any data structure returned by our common interface to which further data-directed operations may be applied must be tagged with the division's identifier" and ensured that the implementation of
get-record applied the tag for us automatically.Given that employee records returned by the common interface are tagged in this way we can then similarly use the tag to retrieve a pre-installed per-division operation with the appropriate name (i.e.
'get-salary) and then apply that to retrieve the employee's salary. In this case, however, get-salary doesn't need to tag it with the division's identifier, as the salary is not a "data structure returned by our common interface to which further data-directed operations may be applied" - it's simply a numeric value.All we need to do then for
get-salary is to use the tag from the record to get the appropriate operation to apply to extract the salary and then apply this operation to the content of the record:
(define (get-salary record) ((get 'get-salary (type-tag record)) (contents record)))We can similarly produce a
get-address procedure:
(define (get-address record) ((get 'get-address (type-tag record)) (contents record)))
(c) Finding an Employee Across Multiple Divisions
For this part we're told to assume that the
find-employee-record procedure we implement takes not only the employee name, but also a list of all the divisions' files as arguments. Personally I'd prefer it if the latter argument weren't necessary and that part of installing a division's procedures were also registering the file. If I've got some spare time I'll post a followup showing how this could be achieved. However, in the meantime, we've got a list of files...Now we've already written a procedure,
get-record, that retrieves a employee's record by employee name from a specified division's file or, by our definition, returns #f if the record is not present. So finding an employee's record across a list of divisions' files should just be a case of iterating through the files, trying to find the employee's record in each one, returning it as soon as we find it or returning #f if it's not present in any of the divisions' files.Here's one implementation that will achieve this:
(define (find-employee-record employee-name personnel-files)
(if (null? personnel-files)
#f
(let ((record (get-record employee-name (car personnel-files))))
(if record
record
(find-employee-record employee-name (cdr personnel-files))))))
(d) Insatiable Ingesting Another CompanyGiven the framework we've put in place this should provide a fairly low bar for Insatiable Enterprises, Inc. to incorporate the personnel files of a newly acquired company into its systems... Assuming, of course, that they happen to have implemented their HRMS in Scheme, or in a way that is easily interfaced to Scheme. All that should be required is to:
- Define a unique division ID under which procedures specific to the division can be installed.
- Write the set of procedures that comply with the common interface requirements and that retrieve the required information from the division's personnel file.
- Write a procedure to install these procedures as operations under the appropriate keys.
- Invoke this procedure, installing the operations.
- Update the list of division files to include the new division's file, suitably tagged.
find-employee-record.
Putting it Into Practice
Okay, that's the common interface defined and we've also specified a set of steps for adding a newly acquired company's personnel file into the system. Let's put it into practice. We'll define a couple of divisions' personnel files using different data structures, give the divisions IDs, produce the required common interface procedures, install them as operations, build a list of divisions' files and try it out...
For our first division's representation we can take the binary search tree set representation introduced in the subsection Sets as binary trees, and the lookup mechanism introduced in the subsection Sets and information retrieval, and modify it so that it supports Scheme String keys (using the
string=?, string<? and string>? comparators):
(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 (list->tree elements)
(car (partial-tree elements (length elements))))
(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
(let ((left-size (quotient (- n 1) 2)))
(let ((left-result (partial-tree elts left-size)))
(let ((left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1))))
(let ((this-entry (car non-left-elts))
(right-result (partial-tree (cdr non-left-elts)
right-size)))
(let ((right-tree (car right-result))
(remaining-elts (cdr right-result)))
(cons (make-tree this-entry left-tree right-tree)
remaining-elts))))))))
(define (key record)
(car record))
(define (lookup given-key set-of-records)
(if (null? set-of-records)
#f
(let ((entry-key (key (entry set-of-records))))
(cond ((string=? given-key entry-key) (entry set-of-records))
((string<? given-key entry-key)
(lookup given-key (left-branch set-of-records)))
((string>? given-key entry-key)
(lookup given-key (right-branch set-of-records)))))))
Using this we can unveil to the world Unquenchable Industries, which uses a tree keyed on employee name to hold each record, with each record consisting of a tree where the fields are keyed by field name (i.e. "address" and "salary"):
(define unquenchable-industries-employees
(list->tree (list (cons "John Doe"
(list->tree (list (cons "address" "55 Ghetto Grove")
(cons "salary" 100))))
(cons "Myddle Mann"
(list->tree (list (cons "address" "24 Suburb Street")
(cons "salary" 40000))))
(cons "Ritchie Rich"
(list->tree (list (cons "address" "1 Park Avenue")
(cons "salary" 250000)))))))
We'll give our division the following ID:
(define unquenchable-industries-id 'unquenchable-industries)Now let's implement our common interface procedures. There are just three of these in our definitions above:
get-record, get-salary and get-address. The functionality we require of the 'get-record operation is provided directly by lookup - it looks up an entry by its key, returning the entry if it's present or #f if it's not. Note that lookup returns a pair with the key as the first element and the data as the second. This means that our 'get-salary and 'get-address operations will need to first extract the tree holding the record, lookup the appropriate field and, if it's present, extract the data it holds. We'll need to wrap all these up in a procedure that installs them under the appropriate operation and division keys.Here's the procedures defined and installed:
(define (install-unquenchable-industries)
(define (get-salary record)
(let ((salary (lookup "salary" (cdr record))))
(if salary
(cdr salary)
#f)))
(define (get-address record)
(let ((address (lookup "address" (cdr record))))
(if address
(cdr address)
#f)))
; Install the procedures
(put 'get-record unquenchable-industries-id lookup)
(put 'get-salary unquenchable-industries-id get-salary)
(put 'get-address unquenchable-industries-id get-address))
(install-unquenchable-industries)
As noted above, the last step is to tag the division's file and create the list of divisions' files:
(define personnel-files (list (attach-tag unquenchable-industries-id unquenchable-industries-employees)))Using this we can find employee records and extract information about them:
> (get-salary (find-employee-record "Ritchie Rich" personnel-files)) 250000 > (get-address (find-employee-record "John Doe" personnel-files)) "55 Ghetto Grove"Now in a dramatic and stock-market unsettling move, Insatiable Industries, Inc. acquires Rapacious Ventures. Rapacious Ventures happen to also use a Scheme-based HRMS but, being a bit more forward thinking, they use nested R6RS hashtables. Here's Rapacious Ventures' personnel file:
(require rnrs/hashtables-6)
(define rapacious-ventures-employees (make-hashtable string-hash string=?))
(hashtable-set! rapacious-ventures-employees
"Fred Blogs"
(let ((h (make-hashtable string-hash string=?)))
(hashtable-set! h "salary" 12345)
(hashtable-set! h "address" "123 Wibble Street")
h))
(hashtable-set! rapacious-ventures-employees
"John Smith"
(let ((h (make-hashtable string-hash string=?)))
(hashtable-set! h "salary" 30000)
(hashtable-set! h "address" "42 Nowhere Road")
h))
(hashtable-set! rapacious-ventures-employees
"Jack Copper"
(let ((h (make-hashtable string-hash string=?)))
(hashtable-set! h "salary" 25000)
(hashtable-set! h "address" "99 Letsbee Avenue")
h))
Let's bring Rapacious Ventures into the Insatiable Enterprises, Inc. fold...First we give the new division an ID:
(define rapacious-ventures-id 'rapacious-ventures)Next we implement and install the common interface procedures. We can look up entries in their personnel file using
hashtable-ref, which takes the hashtable to use, the key we want to lookup and a default value to return if the key is not present. If we're happy with the employee record missing the employee's name then this is pretty close to the 'get-record operation, so we can simply wrap this in a procedure that wires through the appropriate operands, and fixing #f as the default value. Similarly, our implementations for the 'get-salary and 'get-address operations can simply call hashtable-ref with the appropriate key:
(define (install-rapacious-ventures)
(define (get-record employee-name personnel-file)
(hashtable-ref personnel-file employee-name #f))
(define (get-salary record)
(hashtable-ref record "salary" #f))
(define (get-address record)
(hashtable-ref record "address" #f))
; Install the procedures
(put 'get-record rapacious-ventures-id get-record)
(put 'get-salary rapacious-ventures-id get-salary)
(put 'get-address rapacious-ventures-id get-address))
(install-rapacious-ventures)
Finally, we extend the tag the division's file and add it in to the the list of divisions' files:
(define personnel-files (list (attach-tag unquenchable-industries-id unquenchable-industries-employees) (attach-tag rapacious-ventures-id rapacious-ventures-employees)))Using this we should still be able to access Unquenchable Industries' employee records and access Rapacious Ventures employee records:
> (get-salary (find-employee-record "Myddle Mann" personnel-files)) 40000 > (get-address (find-employee-record "Ritchie Rich" personnel-files)) "1 Park Avenue" > (get-salary (find-employee-record "John Smith" personnel-files)) 30000 > (get-address (find-employee-record "Jack Copper" personnel-files)) "99 Letsbee Avenue"
Sweet post!
ReplyDelete