You are looking at historical revision 17956 of this page. It may differ significantly from its current revision.

yasos

Description

"Yet another Scheme Object System"

A very simple OOP system with multiple inheritance, that allows mixing of styles and separates interface from implementation. There are no classes, no meta-anything, simply closures.

Author

Kenneth Dickey

ported to CHICKEN by Juergen Lorenz

Version

1.2

Usage

(require-extension yasos)

Scheming with Objects

There is a saying--attributed to Norman Adams--that "Objects are a poor man's closures." In this article we discuss what closures are and how objects and closures are related, show code samples to make these abstract ideas concrete, and implement a Scheme Object System which solves the problems we uncover along the way.

The Classical Object Model

Before discussing object oriented programming in Scheme, it pays to take a look at the classical model so that we have something to compare with and in order to clarify some of the terminology. One of the problems that the OO movement created for itself was the use of new terms to get away from older concepts and the confusion this has caused. So before going further I would like to give some of my own definitions and a simple operational model. The model is not strictly correct as most compiled systems use numerous short cuts and special optimization tricks, but it is close enough for most practical purposes and has been used to implement OO programming in imperative languages.

An object "instance" consists of local (encapsulated) state and a reference to shared code which operates on its state. The easy way to think of this is as a C struct or Pascal record which has one field reserved for a pointer to its shared code environment and other slots for its instance variables. Each procedure in this shared environment is called a "method." A "class" is code which is can generate instances (new records) by initializing their fields, including a pointer to the instance's shared method environment. The environment just maps method names to their values (their code). Each method is a procedure which takes the record it is operating on as its first, sometimes hidden, argument. The first argument is called the "reciever" and typically aliased to the name "self" within the procedure's code.

In order to make code management easy, object oriented systems such as Actor or Smalltalk wish to deal with code as objects and the way this is done is by making each class an object instance as well. In order to manipulate the class's code, however a "meta-class" is typically defined and in some cases a meta-meta... Well, you get the idea. Many people have spent a great deal of time in theories of how to "ground" such systems without infinite recursion. To confuse things further, many object systems have an object named "object" and a class object named "class"--so that the class of the "class" object is `class'.

By making every data object an instance of the OO system, uniformity demands that numbers are added, e.g. 1 + 2 by "sending the message" + to the object 1 with the argument 2. This has the advantage that + is polymorphic--it can be applied to any data object. Unfortunately, polymorphism also makes optimization hard in that the compiler can no longer make assumptions about + and may not be able to do constant folding or inlining.

The set of methods an object responds to is called a "protocol". Another way of saying this is that the functions or operations that are invokeable on an object make up its interface. More than one class of object may respond to the same protocol--i.e. many different types of objects have the same operation names available.

Object Based Message Passing

So how can this "message passing" be implemented with lexical closures? And what are these closure things anyway?

References within a function to variables outside of the local scope--free references--are resolved by looking them up in the environment in which the function finds itself. When a language is lexically scoped, you see the shape of the environment when you read--lex--the code. In Scheme, when a function is created it remembers the environment in which it was created. Free names are looked up in that environment, so the environment is said to be "closed over" when the function is created. Hence the term "closure."

An example may help here:

 (define (CURRIED-ADD x) (lambda (y) (+ x y))
 (define ADD8 (curried-add 8))
 (add8 3)	-> 11

When add8 is applied to its argument, we are doing ((lambda (y) (+ x y)) 3)

The function add8 remembers that X has the value 8. It gets the value Y when it is applied to 3. It finds that + is the addition function. So (add8 3) evaluates to 11.

(define ADD5 (curried-add 5)) makes a new function which shares the curried-add code (lambda (y) (+ x y)), but remembers that in its closed over environment, X has the value 5.

Now that we have a way to create data objects, closures, which share code but have different data, we just need a "dispatching function" to which we can pass the symbols we will use for messages:

 (define (MAKE-POINT the-x the-y)
   (lambda (message)
      (case message
  ((x)  (lambda () the-x)) ;; return a function which returns the answer
  ((y)  (lambda () the-y))
  ((set-x!) 
       (lambda (new-value)
	       (set! the-x new-value)  ;; do the assignment
		the-x))                ;; return the new value
  ((set-y!) 
       (lambda (new-value)
	       (set! the-y new-value)
		the-y))
 (else (error "POINT: Unknown message ->" message))
 ) )  )
 (define p1 (make-point 132 75))
 (define p2 (make-point 132 57))
 ((p1 'x))		-> 132
 ((p1 'set-x!) 5)	-> 5

We can even change the message passign style to function calling style:

 (define (x obj) (obj 'x))
 (define (set-x! obj new-val) ((obj 'set-x!) new-val))
 (set-x! p1 12) 	-> 12 
 (x p1) 		-> 12
 (x p2)		-> 132	;; p1 and p2 share code but have different local data

Using Scheme's lexical scoping, we can also define make-point as:

 (define (MAKE-POINT the-x the-y)
   (define (get-x) the-x)	;; a "method"
   (define (get-y) the-y)
   (define (set-x! new-x) 
      (set! the-x new-x)
      the-x)
   (define (set-y! new-y) 
      (set! the-y new-y)
      the-y)
   (define (self message)
      (case message
  ((x)   	  get-x) ;; return the local function
  ((y)  	  get-y)
  ((set-x!) set-x!)
  ((set-y!) set-y!)
  (else (error "POINT: Unknown message ->" message))))
   self	 ;; the return value of make-point is the dispatch function
 )

Adding Inheritance

"Inheritance" means that one object may be specialized by adding to and/or shadowing another's behavior. It is said that "object based" programming together with inheritance is "object oriented" programming. How can we add inheritance to the above picture? By delegating to another object!

 (define (MAKE-POINT-3D a b the-z)
   (let ( (point (make-point a b)) )
    (define (get-z) the-z)
    (define (set-z! new-value)
(set! the-z new-value)
the-z)
    (define (self message)
      (case message
   ((z) 		get-z)
   ((set-z!) 	set-z!)
   (else (point message))))
   self
 )
 (define p3 (make-point-3d 12 34 217))
 (x p3)		-> 12
 (z p3)		-> 217
 (set-x! p3 12)	-> 12
 (set-x! p2 12)	-> 12
 (set-z! p3 14)	-> 14

Note that in this style, we are not required to have a single distinguished base object, "object"--although we may do so if we wish.

What Is Wrong With The Above Picture ?

While the direct strategy above is perfectly adequate for OO programming, there are a couple of rough spots. For example, how can we tell which functions are points and which are not? We can define a POINT? predicate, but not all Scheme data objects will take a 'point? message. Most will generate error messages, but some will just "do the wrong thing."

 (define (POINT? obj) (and (procedure? obj) (obj 'point?)))
 (point? list)         -> (point?)  ;; a list with the symbol 'point?

We want a system in which all objects participate and in which we can mix styles. Building dispatch functions is repetitive and can certainly be automated--and let's throw in multiple inheritance while we are at it. Also, it is generally a good design principle to separate interface from implementation, so we will.

One Set Of Solutions

The following is one of a large number of possible implementations. Most Scheme programmers I know have written at least one object system and some have written several. Let's first look at the interface, then how it is used, then how it was implemented.

In order to know what data objects are "instances", we have a predicate, INSTANCE?, which takes a single argument and answers #t or #f.

For each kind of object is also useful to have a predicate, so we define a predicate maker: (DEFINE-PREDICATE <opname?>) which by default answers #f.

To define operations which operate on any data, we need a default behavior for data objects which don't handle the operation: (DEFINE-OPERATION (opname self arg ...) default-body). If we don't supply a default-behavior, the default default-behavior is to generate an error.

We certainly need to return values which are instances of our object system: (OBJECT operation... ), where an operation has the form: ((opname self arg ...) body). There is also a LET-like form for multiple inheritance:

  (OBJECT-WITH-ANCESTORS ( (ancestor1 init1) ...) 
    operation ...).

In the case of multiple inherited operations with the same identity, the operation used is the one found in the first ancestor in the ancestor list.

And finally, there is the "send to super" problem, where we want to operate as an ancestor, but maintain our own self identity {more on this below}: (OPERATE-AS component operation composite arg ...).

Note that in this system, code which creates instances is just code, so there there is no need to define "classes" and no meta-<anything>!

Examples

O.K., let's see how this fits together. First, another look at points.

 (define P2 (make-point 123 32131))
 (define P3 (make-point-3d 32 121 3232))
 (size "a string")	-> 8
 (size p2)		-> 2
 (size p3)		-> 3
 (point? p2)		-> #t
 (point? p3)		-> #t
 (point? "a string")	-> #f
 (x p2)			-> 123
 (x p3)			-> 32
 (x "a string")		-> ERROR: Operation not handled: x "a string"
 (print p2 #t)		#<point: 123 32131>
 (print p3 #t)   	#<3D-point: 32 121 3232>
 (print "a string" #t) 	"a string"

Things to notice...

Now lets look at a more interesting example, a simplified savings account with history and passwords.

(See below for the example code)

 (define FRED  (make-person "Fred" 19 "573-19-4279" #xFadeCafe))
 (define SALLY
   (make-account "Sally" 26 "629-26-9742" #xFeedBabe 263 bank-password))
 (print fred #t)		#<Person: Fred age: 19>
 (print sally #t)	#<Bank-Customer Sally>
 (person? sally)		-> #t
 (bank-account? sally)	-> #t
 (ssn fred  #xFadeCafe)	-> "573-19-4279"
 (ssn sally #xFeedBabe)	-> "629-26-9742"
 (add sally 130) 	New balance: $393
 (add sally 55)		New balance: $448
 ; the bank can act in Sally's behalf
 (get-account-history sally bank-password)  		--> (448 393 263)
 (withdraw sally 100 (get-pin sally bank-password))	New balance: $348
 (get-account-history sally bank-password)          	--> (348 448 393 263)
 ;; Fred forgets
 (ssn fred 'bogus)	Bad password: bogus	;; Fred gets another chance
 ;; Sally forgets
 (ssn sally 'bogus)	CALL THE POLICE!!	;; A more serious result..

Now we see the reason we need OPERATE-AS. The when the bank-account object delegates the SSN operation to its ancestor, person, SELF is bound to the bank-account object--not the person object. This means that while the code for SSN is inherited from person, the BAD-PASSWORD operation of the bank-account is used.

This is an important behavior to have in an object system. If there were no OPERATE-AS, code would have to be duplicated in order to implement the stricter form of BAD-PASSWORD. With OPERATE-AS, we can safely share code while keeping operations localized within the inheritance hierarchy.

Our Implementation

Given the sophisticated behavior of our object system, the implementation is surprisingly small.

Unlike some other languages, Scheme does not have a standard way of defining opaque types. In order to distinguish data objects which are instances of our object system, we just uniquely tag a closure. As we are only introducing one new datatype it is not much work to hide this by rewriting Scheme's WRITE and DISPLAY routines.

In order to allow lexical scoping of objects and operations, the values of operations, rather than their names, are used in the dispatch functions created for objects. Those of you who have used languages such as Smalltalk or Actor may have been bitten by the inadvertant name collisions in the single, global environment.

Note that there are no global tables. A general rule of thumb is that for less than 100 elements, linear search beats hashing. While we can speed up operation dispatch by some simple caching, the general performance for this system will be pretty good up through moderately large systems. Also, we can optimize the implementation with no change to the interface. If our systems start getting too slow, its time to smarten the compiler.

How This Compares To The Classical Model

It is time to compare this implementation to the model given at the beginning of this article.

One thing you may notice right away is the power of closures. The object system is small and simpler than the class model. There are no grounding problems. No "Meta". I find it interesting that Whitewater's Actor 4.0 implements code sharing between classes (which they call multiple inheritance) in an attempt to get more of the benefits that closures provide directly.

The Scheme solution is also more general. It keeps lexical scoping, and one can freely mix OO with functional & imperative styles.

Programming Environment work still has to be done for code management & debugging (e.g. doing an object inspector), but OO helps here just as in other OO systems.

Separating the interface from the implementation is a better software engineering solution than the classical model. We can define our "protocols" independently of their implementation. This helps us hide our implementation. One might think that object oriented programming in general would solve the problems here, but this has not been the case because people still use inheritance to share code rather than just to share abstractions. An example of this is the complex behavior of Smalltalk dictionaries because they inherit the implementation of Sets. While code sharing is a benefit of OO it is still considered bad form when your code breaks because of a change in the implementation of an inherited abstraction.

Finally, I would like to point out that one can implement other OO models directly in Scheme, including smaller, simpler ones! You can also implement the classical model (e.g. see D. Friedman, M. Wand, & C. Haynes: _Essentials of Programming Languages_, McGraw Hill, 1992).

Remember, your programming language should be part of the solution, not part of your problems. Scheme for success!

Examples

 ;;;===============
 ;;;file yasos-examples.scm
 ;;;===============
 
 (require-extension yasos format)
 
 ;;----------------------------
 ;; general operations
 ;;----------------------------
 
 (define-operation (print-obj obj port)
   (format port
     ;; if an instance does not have a print-obj operation..
     (if (instance? obj) "#<INSTANCE>~%" "#<NOT-AN-INSTANCE: ~s>~%") obj))
 
 (define-operation (size-obj obj)
   ;; default behavior
   (cond
     ((vector? obj) (vector-length obj))
     ((list? obj) (length obj))
     ((pair? obj) 2)
     ((string? obj) (string-length obj))
     ((char? obj) 1)
     (else
       (error "Operation not supported: size-obj" obj))))
 
 ;;----------------------
 ;; point interface
 ;;----------------------
 
 (define-predicate point?) ;; answers #f  by default
 (define-operation (x obj))
 (define-operation (y obj))
 (define-operation (set-x! obj new-x))
 (define-operation (set-y! obj new-y))
 
 ;;--------------------------------
 ;; point implementation
 ;;--------------------------------
 
 (define (make-point the-x the-y)
   (object
     ((point? self) #t) ;; yes, this is a point object
     ((x self) the-x)
     ((y self) the-y)
     ((set-x! self val)
       (set! the-x val)
       the-x)
     ((set-y! self val)
       (set! the-y val)
       the-y)
     ((size-obj self) 2)
     ((print-obj self port)
       (format port "#<point: ~a ~a>~%" (x self) (y self)))))
 
 ;;-----------------------------------------
 ;; 3D point interface additions
 ;;-----------------------------------------
 
 (define-predicate point-3d?) ;; #f by defualt
 (define-operation (z obj))
 (define-operation (set-z! obj new-z))
 
 ;;------------------------------------
 ;; 3D point implementation
 ;;------------------------------------
 
 (define (make-point-3d the-x the-y the-z)
   (object-with-ancestors ( (a-point (make-point the-x the-y)) )
     ((point-3d? self) #t)
     ((z self) the-z)
     ((set-z! self val) (set! the-z val) the-z)
     ;; override inherited size-obj and print-obj operations
     ((size-obj self) 3)
     ((print-obj self port)
       (format port "#<3d-point: ~a ~a ~a>~%" (x self) (y self) (z self)))))
 
 ;;;-----------------------
 ;; person interface
 ;;------------------------
 
 (define-predicate person?)
 (define-operation (name obj))
 (define-operation (age obj))
 (define-operation (set-age! obj new-age))
 (define-operation (ssn obj password)) ;; Social Security # is protected
 (define-operation (new-password obj old-passwd new-passwd))
 (define-operation (bad-password obj bogus-passwd)
   ;; assume internal (design) error
   (error (format #f "Bad Password: ~s given to ~a~%"
           bogus-passwd
           (print-obj obj #f))))
 
 ;;----------------------------------
 ;; person implementation
 ;;----------------------------------
 
 (define (make-person a-name an-age a-ssn the-password)
   (object
     ((person? self) #t)
     ((name self) a-name)
     ((age self) an-age)
     ((set-age! self val) (set! an-age val) an-age)
     ((ssn self password)
       (if (equal? password the-password)
         a-ssn
         (bad-password self password)))
     ((new-password self old-passwd new-passwd)
       (cond
         ((equal? old-passwd the-password) (set! the-password new-passwd) self)
         (else (bad-password self old-passwd))))
     ((bad-password self bogus-passwd)
       (format #t "Bad password: ~s~%" bogus-passwd)) ;; let user recover
     ((print-obj self port)
       (format port "#<Person: ~a age: ~a>~%" (name self) (age self)))))
 
 ;;;---------------------------------------------------------------
 ;; account-history and bank-account interfaces
 ;;----------------------------------------------------------------
  
 (define-predicate bank-account?)
 (define-operation (current-balance obj pin))
 (define-operation (add obj amount))
 (define-operation (withdraw obj amount pin))
 (define-operation (get-pin obj master-password))
 (define-operation (get-account-history obj master-password))
 
 ;;----------------------------------------------
 ;; account-history implementation
 ;;----------------------------------------------
 
 ;; put access to bank database and report generation here
 (define (make-account-history initial-balance a-pin master-password)
   ;; history is a simple list of balances -- no transaction times
   (letrec 
     ((history (list initial-balance))
      (balance (lambda () (car history))) ; balance is a function
      (remember
        (lambda (datum) (set! history (cons datum history)))))
     (object
       ((bank-account? self) #t)
       ((add self amount) ;; bank will accept money without a password
         (remember (+ amount (balance)))
         ;; print new balance
         (format #t "New balance: $~a~%" (balance)))
       ((withdraw self amount pin)
         (cond
           ((not (equal? pin a-pin)) (bad-password self pin))
           ((< (- (balance) amount) 0)
             (format 
               #t
               "No overdraft~% Can't withdraw more than you have: $~a~%"
               (balance)))
           (else
             (remember (- (balance) amount))
             (format #t "New balance: $~a~%" (balance)))))
       ((current-balance self password)
         (if (or (eq? password master-password) (equal? password a-pin))
           (format #t "Your Balance is $~a~%" (balance))
           (bad-password self password)))
       ;; only bank has access to account history
       ((get-account-history self password)
         (if (eq? password master-password)
           history
           (bad-password self password))))))
 
 ;;;------------------------------------------
 ;; bank-account implementation
 ;;-------------------------------------------
 
 (define (make-account a-name an-age a-ssn a-pin initial-balance master-password)
   (object-with-ancestors
     ((customer (make-person a-name an-age a-ssn a-pin))
      (account (make-account-history initial-balance a-pin master-password)))
     ((get-pin self password)
       (if (eq? password master-password)
         a-pin
         (bad-password self password)))
     ((get-account-history self password)
       (operate-as account get-account-history self password))
     ;; our bank is very conservative...
     ((bad-password self bogus-passwd)
       (format #t "~%CALL THE POLICE!!~%"))
     ;; protect the customer as well
     ((ssn self password)
       (operate-as customer ssn self password))
     ((print-obj self port)
       (format port "#<Bank-Customer ~a>~%" (name self)))))
 
 ;;; eof yasos-examples.scm
 
 ;;;============
 ;;; file: yasos-test.scm
 ;;;============
 (require-extension yasos)
 
 (define main
   (lambda ()
     (let
       ((p2 (make-point 1 2))
        (p3 (make-point-3d 4 5 6))
        (fred  (make-person  "Fred"  19 "573-19-4279" 'FadeCafe))
        (sally (make-account "Sally" 26 "629-26-9742" 'FeedBabe 263 'bank-password)))
       (printf "(size-obj p2) => ~a (size-obj p3) => ~a~%" (size-obj p2) (size-obj p3))
       (print-obj 'mist #t)
       (print-obj p2 #t)
       (printf "(point? p2) => ~A (point-3d? p2) => ~A~%" (point? p2) (point-3d? p2))
       (print-obj p3 #t)
       (printf "(point? p3) => ~A (point-3d? p3) => ~A~%" (point? p3) (point-3d? p3))
       (print-obj fred #t)
       (printf "Fred's ssn: ~a~%" (ssn fred 'FadeCafe))
       (printf "Fred: person? ~a bank-account? ~a~%" (person? fred) (bank-account? fred))
       (print-obj sally #t)
       (printf "Sally's  ssn: ~a~%" (ssn sally 'FeedBabe))
       (printf "Sally: person? ~a bank-account? ~a~%" (person? sally) (bank-account? sally))
       (current-balance sally 'FeedBabe)
       (add sally 200)
       (add sally 300)
       (withdraw sally 400 'FeedBabe)
       (printf "Account history of Sally: ~a~%" (get-account-history sally 'bank-password))
       (withdraw sally 150 (get-pin sally 'bank-password))
       (printf "Account history of Sally: ~a~%" (get-account-history sally 'bank-password))
       (printf "Bad password for Fred:~%")
       (ssn fred 'bogus)
       (printf "Bad password for Sally:")
       (ssn sally 'bogus)
       (void) 
 ) ) )   
 (main)
 
 ;;; eof yasos-test.scm

Changelog

License

 COPYRIGHT (c) 1992,2008 by Kenneth A Dickey, All rights reserved.
 
 Permission is hereby granted, free of charge, to any person obtaining
 a copy of this software and associated documentation files (the
 "Software"), to deal in the Software without restriction, including
 without limitation the rights to use, copy, modify, merge, publish,
 distribute, sublicense, and/or sell copies of the Software, and to
 permit persons to whom the Software is furnished to do so, subject to
 the following conditions:
 
 The above copyright notice and this permission notice shall be
 included in all copies or substantial portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,WHETHER IN AN ACTION
 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.