- Scheming with Objects
- Module yasos
- Module yasos-stacks
- Module yasos-queues
- Module yasos-points
- Module yasos-collections
"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.
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.
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.
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
"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.
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.
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:
(operate-as component operation composite arg ...),
or, in curried form
((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>!
- yasos symprocedure
documentation procedure: Lists the exported symbols, if run as a thunk, or the documentation of the exported sym.
- protocol objprocedure
- protocol obj symprocedure
if run as thunk, returns the list of operations, obj accepts, otherwise the signature of sym.
This operation is available for each yasos object without intervention of the client.
- show objprocedure
- show obj argprocedure
prints obj with format to stdout, if no optional arg is given, or to the first format argument. To be updated in operations.
- size objprocedure
returns the size of an object. To be updated in operations.
- (define-predicate name)syntax
defines a predicate.
- (define-operation (name obj . args) . default-body)syntax
defines an operation, obj should accept, with arguments args and default-body in case, no name is defined within operations.
- (operations ((ancestor init) ...) ((name self . args) . body) ...)syntax
defines the list of operations, the object self will accept, possibly inheriting ancestor ...
- (operate-as super operation)syntax
- (operate-as super operation self . args)syntax
operation is send to super. The first is a curried version of the second.
The following two macros are deprecated but still exported. They are superseded by operations.
- (object ((name self . args) . body) ...)syntax
same as (operations () ((name self . args) . body) ...)
- (object-with-ancestors ((ancestor init) ...) ((name self . args) . body) ...)syntax
same as operations.
(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 (show obj #f))))
(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 ((show self port) (format port "#<Person: ~a age: ~a>~%" (name self) (age self)))))
(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))
;; 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))))))
(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)) ((show self port) (format port "#<Bank-Customer ~a>~%" (name self)))))
(import yasos) (define main (lambda () (let ( (fred (make-person "Fred" 19 "573-19-4279" 'FadeCafe)) (sally (make-account "Sally" 26 "629-26-9742" 'FeedBabe 263 'bank-password)) ) (show 'mist) (show fred) (printf "Fred's ssn: ~a~%" (ssn fred 'FadeCafe)) (printf "Fred: person? ~a bank-account? ~a~%" (person? fred) (bank-account? fred)) (show sally) (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)
An implementation of random-acces stacks
creates an empty stack.
creates an empty random access stack.
- stack? xprprocedure
- ra-stack? xprprocedure
random access stack predicate.
- push! obj valprocedure
pushes val onto the stack.
- top objprocedure
returns the top of the stack.
- down obj kprocedure
returns the result of stepping down the ra-stack k times.
- pop! objprocedure
pops the stack.
- empty? objprocedure
is stack empty?
- clear! objprocedure
empties the stack.
an implementation of queues with amortized constant time access.
creates an empty queue.
- queue? xprprocedure
- enq! obj valprocedure
enqueues val onto the tail of the queue.
- front objprocedure
returns the first item of the queue.
- deq! objprocedure
dequeues the the first item from the queue.
- empty? objprocedure
is queue empty? q
- clear! objprocedure
empties the queue.
an implementation of flat points.
- make-point-cartesian x yprocedure
creates a point from cartesian coordinates.
- make-point-polar rho thetaprocedure
creates a point from polar coordinates.
- point? xprprocedure
- distance obj otherprocedure
computes the distance between the two points obj and otern.
The following four procedures return the respective coordinates:
- x objprocedure
- y objprocedure
- rho objprocedure
- theta objprocedure
The following three commands do what their names suggest:
- scale! obj factorprocedure
- rotate! obj angleprocedure
- translate! obj dx dyprocedure
Generic interface to finite-size collections.
- collection? objprocedure
Predicate -- true for lists, vectors, strings, and hash tables.
- empty? collectionprocedure
Returns true if collection is empty, false otherwise.
- size collectionprocedure
Returns the size of the collection.
- do-elts proc collection ...procedure
Applies procedure element-wise to collections. Return value is unspecified.
- do-keys proc collection ...procedure
Applies procedure element-wise to collection indices or keys. Return value is unspecified.
- map-elts proc collection ...procedure
Applies procedure element-wise to collections and maps to new collection.
- map-keys proc collection ...procedure
Applies procedure element-wise to collection indices or keys and maps to new collection.
- for-each-key proc collectionprocedure
- for-each-elt proc collectionprocedure
Applies proc to single collection (more efficient).
- gen-keys collectionprocedure
- gen-elts collectionprocedure
Returns generators for collection indices/keys and values, respectively.
- reduce proc seed collection ...procedure
Fold iterator for collections.
- reduce* proc collection ...procedure
Fold iterator for collections where the first element of the collection is the seed.
- random-access? collectionprocedure
Returns true if collection permits random access, i.e. if elt-ref and elt-set! are defined operations, false otherwise.
- elt-ref collection iprocedure
- elt-set! collection i vprocedure
Random-access collection get and set, respectively.
- sort elt< collectionprocedure
Merge sort for collections.
Kenneth Dickey Ken(dot)Dickey(at)Whidbey(dot)Com
ported to CHICKEN and enhanced by Juergen Lorenz
COPYRIGHT (c) 1992,2008 by Kenneth A Dickey, All rights reserved. COPYRIGHT (c) 2013-2014 by Juergen Lorenz, 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.
- removed lseq-specific procedures from yasos-collections and added dependency on srfi-127
- added g-zip (generator zip) utility to module yasos-collections
- additional operations and generator combinators in module yasos-collections
- renamed yasos-based modules to yasos-<name> to avoid collisions with other eggs
- extensions to collections to allow concurrent iteration over keys and values
- ported to CHICKEN 5
- tests with define-test instead of simple-test
- operations and protocol added, define-operation with arbitrary lambda-lists, examples stacks, queues and points added
- fixes in the setup script and simplification of the set of files
- initial import