How to modularize programs 
Author Message
 How to modularize programs

Scheme offers an abundance of ways to povide interface to functions
and objects.  Unfettered abundance makes it difficult to acheive
interchangablility between packages in a library like SLIB.  So I
would like to try to standardise the interface in SLIB if possible.

Lets take databases in SLIB as an example.

Hash tables calls are organized according to predicate so that
functions are returned which operate on the hash table as the first
argument.

make-hash-table K
predicate->hash-asso PRED
hash-inquirer PRED
hash-associator PRED
hash-remover PRED
  I suppose these last 2 could have returned mapper functions as well.
hash-map PROC HASH-TABLE
hash-for-each PROC HASH-TABLE

Association lists are similar but the returned functions which modify
alists return the new alist to which the variable holding the alist
must be set.

predicate->asso PRED
alist-inquirer PRED
alist-associator PRED
alist-remover PRED
alist-map PROC ALIST
alist-for-each PROC ALIST

The standard scheme support for alists is to just give names to the
association function for each variety of predicate, equal? => assoc,
eqv? => assv, and eq? => assq.  This would lead to a large number of
procedures if extended to the other alist database functions.

Red-black trees have an order which is visible to the user.  Also, the
rb-tree carries information in it sufficient to use generic
procedures, rather than ones generated given the predicate.

make-rb-tree LEFT-ROTATION-FIELD-MAINTAINER
          RIGHT-ROTATION-FIELD-MAINTAINER INSERTION-FIELD-MAINTAINER
          DELETION-FIELD-MAINTAINER PRIOR?
rb-delete! TREE NODE
rb-node-successor NODE
rb-node-predecessor NODE
rb-node-maximum NODE
rb-node-minimum NODE
rb-tree-maximum TREE
rb-tree-minimum TREE
rb-insert! TREE NODE
make-rb-node DATA

Here is a object-based set of calls for fibonacci heaps:

  (MakeFHeap)               Returns new heap
  (h 'insert <item> <key>)  Inserts new item according to key
  (h 'find-min)             Returns item with minimal key
  (h 'delete-min)           Deletes and returns item with min. key
  (n 'decrease-key <dec> h) Decreases key of node n in heap h
  (n 'delete h)             Deletes arbitrary node n in heap h

I think I have also seen a system where calls of the form
(h 'inserter) returned procedures to operate on the objects.

====================

It is desirable to be able to switch between database types fairly
easily.  In Jacal for instance, I have code which I would like to be
able to use either alists or hash-tables depending on how much memory
I have available (Jacal is getting very tight in 600k).

One solution might be to have just one set of database calls visible
at once.  However, having alists and hash-tables and other database
type systems (PROVIDE 'DATABASE) is not sufficient for other
applications because it doesn't distinguish between the database
capabilities which other applications might need (ordering, deletion,
persistence, ...)  and I don't think a database capabilities can be
organized into a simple chain.

The OOP (h 'insert <item> <key>) form probably adds a large overhead
to simple databases like hash tables and alists.  The ((h 'inserter)
<item> <key>) form does eliminate the overhead problem but seems
dangerous in that it doesn't enforce that the inserter is used for the
table for which it was designed.

Alists are not the only formalism which can benefit from the idiom
(set! db (db-associate db <key> <value)).  If hash tables were done
the same way then resizing the hash table could be done easily.
However, The set! idiom would conflict with the RB-DELETE!'s usefully
returning the deleted node.  Having to explicitly allocate nodes (in
RB) is another variation to deal with.

ARGGH!



Sat, 19 Oct 1996 06:26:53 GMT  
 How to modularize programs
#
# Scheme offers an abundance of ways to povide interface to functions
# and objects.  Unfettered abundance makes it difficult to acheive
# interchangablility between packages in a library like SLIB.  So I
# would like to try to standardise the interface in SLIB if possible.
#

The logical resolution to this problem (IMHO) is the adoption of a
standard object system for SLIB.  I vote for Meroon.  This would allow
us to have a collection class with a standard interface based on
generic functions.  For example:

(define-class collection object ())
(define-generic (element (c collection) key))
(define-generic (element-set! (c collection) key value))
(define-generic (remove! (c collection) key))
(define-generic (coll-map proc (c collection)))
(define-generic (coll-for-each proc (c collection)))

Each type of collection would provide methods for the agreed upon
interface.  That way, you only need to change the call to the
constructor to change which kind of collection your code uses.  

I would be willing to spend some time reworking the collections in
SLIB if there is a general consensus that this is a good thing.

--
Brent Benson                    
Harris Computer Systems



Sat, 19 Oct 1996 21:54:57 GMT  
 How to modularize programs
I noticed the problem of the plethora of interfaces when I tried to
use the database utilities available in SLIB.  In my work on
corpus-based linguistics I found I was constructing a variety of
tables, some of which become quite large.  I wanted to be able to move
from general-purpose procedures, such as association-lists, to more
specialized ones, such as hash tables, balanced binary trees, tries,
etc., without having to do any code rewriting.  Also, I wanted the
implementation to be reasonably efficient (at least in Chez Scheme, the
version of Scheme I am using).  The implementation described below
seems to largely achieve these goals.

For example, the first version of a program might use association lists,
but later for performance reasons we might want to use e.g. balanced
binary trees.

Here's a simple program that counts the words in a list, which uses
association lists:

(define (count-words words)
  (let* ((word-table-maker (alist-maker equal?))         ; define the table type
         (word-table-inc! (word-table-maker 'inc!))      ; define a table incrementor
         (word-table-reduce (word-table-maker 'reduce))  ; define a table reducer
         (word-table ((word-table-maker 'make))))        ; make one table
    (let loop ((remaining-words words))
      (if (null? remaining-words)
          (word-table-reduce word-table
                             (lambda (word count sofar)
                               (cons (list word count) sofar))
                             '())
          (begin
            (word-table-inc! word-table (car remaining-words) 1)
            (loop (cdr remaining-words)))))))

To make this use hash tables instead of association lists, all that
need be done is replace the expression (alist-maker equal?) with
(hash-maker equal?).

Here's the header for the file,

Mark

;;; associators.ss

(eval-when (compile) (optimize-level 3))

;;; Mark Johnson, April 1993.
;;;
;;; An associator is a suite of functions for manipulating a finite function  
;;; from keys to values. This file contains associators based on avl trees
;;; (which are balanced binary trees) and tries (which extend an associator
;;; from keys of type T to keys of type list-of-T), as well as associators
;;; based on association lists, hash tables and vectors.
;;;
;;; At the bottom of this file there are predefined associators for atoms
;;; and for lists of atoms.
;;;
;;; Because all associators have the same interface, it should be possible
;;; to e.g., develop a program using simple, general associators (e.g.,
;;; the associators based on association lists), and substitute more
;;; efficient, specialized associators if needed.
;;;
;;; An associator-maker is a function which maps keywords into appropriate
;;; associator manipulation functions.  Here are the keywords an associator
;;; should understand:
;;;
;;; ((associator-maker 'make)) returns a new associator that associates
;;;               #f with every value.
;;; ((associator-maker 'ref) associator key) returns value associated with key
;;;              in associator.
;;; ((associator-maker 'set!) associator key value) destructively changes the
;;;              value associated with key in associator to be value, and
;;;              returns the old value.
;;; ((associator-maker 'update!) associator key update-fn) destructively
;;;              changes the value associated with key to (update-fn key
;;;              old-value), where old-value was the value that the associator
;;;              previously associated with value.
;;; ((associator-maker 'push!) associator key elt) destructively changes the
;;;              value associated with key to (cons elt elts), where elts is
;;;              '() if the value associated with key was #f, and the value
;;;               associated with key otherwise.
;;; ((associator-maker 'inc!) associator key inc) destructively changes the
;;;              value associated with key to (+ inc value), where value is 0
;;;              if the value associated with key was #f, and the value
;;;              associated with key otherwise.
;;; ((associator-maker 'map) associator fn) returns a new associator that
;;;              assigns (fn key value) to each key where associator
;;;              assigned a non-#f value value to key.
;;; ((associator-maker 'map!) associator fn) is the same as map, except
;;;              that associator is destructively updated.
;;; ((associator-maker 'for-each) associator fn) calls (fn key value) on
;;;              each key-value pair in associator such that value =/= #f.
;;; ((associator-maker 'reduce) associator fn start) calls
;;;              (fn key value so-far) on each key-value pair in associator,
;;;              where so-far is the value returned from the previous fn
;;;              call (so-far in the first fn call is start).
;;;
;;; The idea is that given an associator-maker, the various associator
;;; manipulation functions will be assigned to local variables, rather than
;;; obtained by associator-maker each time the manipulation functions are used.
;;;
;;; Often a particular type of associator needs additional parameters, e.g.,
;;; an ordering or equality predicate.  The avl-maker, for example, takes an
;;; ordering predicate and returns an associator-maker.

--
Mark Johnson,
Cognitive and Linguistic Sciences, Box 1978
Brown University, Providence, RI 02912
(401) 863 1670, fax (401) 863 2255



Sat, 19 Oct 1996 22:35:11 GMT  
 How to modularize programs


   #
   # Scheme offers an abundance of ways to povide interface to functions
   # and objects.  Unfettered abundance makes it difficult to acheive
   # interchangablility between packages in a library like SLIB.  So I
   # would like to try to standardise the interface in SLIB if possible.
   #

   The logical resolution to this problem (IMHO) is the adoption of a
   standard object system for SLIB.  I vote for Meroon.  This would allow
   us to have a collection class with a standard interface based on
   generic functions.  For example:

   (define-class collection object ())
   (define-generic (element (c collection) key))
   (define-generic (element-set! (c collection) key value))
   (define-generic (remove! (c collection) key))
   (define-generic (coll-map proc (c collection)))
   (define-generic (coll-for-each proc (c collection)))

   Each type of collection would provide methods for the agreed upon
   interface.  That way, you only need to change the call to the
   constructor to change which kind of collection your code uses.  

As I stated before, scheme has no shortage of ways to do this.  Does
Meroon dispatch for every operation on objects?  If so, then I think
the overhead is too high.

   I would be willing to spend some time reworking the collections in
   SLIB if there is a general consensus that this is a good thing.

How big would Meroon be if all the ports other than SLIB were removed?



Wed, 23 Oct 1996 08:06:46 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Compartmentalize and Modularize Tk GUI's

2. CALL FOR IDEAS: How to modularize ?

3. Call HLASM program from COBOL MVS program

4. J Programming FAQJ Programming FAQ

5. An Awk Program to Create an Awk Program [Long]

6. how to make my program to receive parameter from another program

7. Windows program call DOS program

8. cw programs as cgi programs

9. TOOLS program available on the Web (Re: Final Program - TOOLS USA 95)

10. Calling FoxPro program from within Clipper program

11. I need a program to convert clipper programs to vb

12. When do you need to use other programming langauge instead of pure labview programming

 

 
Powered by phpBB® Forum Software