CS212 HandoutsThe key principle of object oriented programming is that objects with common properties or operations are collected together in classes, and the classes are arranged in a hierarchy that specifies subclass/superclass relationships. A class c1 is a subclass of another class c2 (and c2 is a superclass of c1) if all operations that apply to objects of c2 also apply to objects of c1, but the objects of c1 satisfy some special property or admit some extra operation that does not apply to objects of c2 in general.
A subclass can inherit operations or information from its superclasses, but can modify these inherited operations to take advantage of the special properties of the subclass. For example, one might have a class of objects called vehicles and another more specific class called automobiles. Automobiles would inherit certain operations from vehicles, such as the ability to move from one location to another, but might have other operations particular to automobiles, such as polluting the environment. This ability to build a hierarchy of classes that share certain operations makes object oriented programming an excellent framework for managing the otherwise overwhelming complexity of large systems.
The use of slots makes object oriented programming a good way to manage the complexity of reasoning about state. It allows state variables to be packaged up safely, so that they can only be changed by certain procedures.
Object oriented programming makes heavy use of generic functions. A generic function may have a large array of method specializers, several of which may be applicable in a given situation. We discussed earlier in the semester the mechanism by which Swindle determines which of a possibly large set of applicable methods to apply in a given situation. We will revisit this issue here, since it is best understood in terms of inheritance.
The slots of a given class, and the applicable methods for that class, are derived using an inheritance mechanism. Each class has a list of one or more superior classes called its direct superclasses, which are specified when the class is created. If a given slot is not defined for a given class, then its direct superclasses are searched to see if they have that slot, and then the direct superclasses of the superclasses, and so on. Similarly, if some generic function is called with a given instance, and it has no method applicable to objects of that class, it looks for a method applicable to the superclasses of the object, and so on. We say that a class inherits all the slots and methods of its superclasses. Inheritance provides a lot of power and flexibility in organizing large systems. (Much more on this below.)
The manner in which a class inherits slots and methods from its superclasses is a big part of any object oriented programming system. We will start with single inheritance, in which each class (except the topmost) has exactly one direct superclass. The resulting hierarchy of classes thus forms a tree; the unique superclass of a class is its parent in the tree, and the topmost class is the root of the tree (in Swindle, this is always <top>). The methods and instance variables are looked up in order from a class to its parent, to its parent's parent, and so on. After we have discussed single inheritance, we will look at multiple inheritance, where a given class can have several direct superclasses (more than one parent). In this case the inheritance hierarchy is a directed acyclic graph (DAG) rather than a tree.
We now turn to a discussion of the syntax for defining classes, making instances of a given class, and referencing and changing the values of slots in an instance. Remember that a class is a "kind of thing'' and an instance of a class is a "particular thing'' of that kind.
In Swindle, a class is defined using the special form defclass:
(defclass <name> (<superclass1> <superclass2> ...) slot-spec1 slot-spec2 ...)where <name> is the symbol that names the class, the <superclassi> are the names of zero or more direct superclasses of the class, and the slot-speci are slot specifications.
Each slot specification is a list of either of the following two forms:
(slot-name :type <type>) (slot-name :type <type> :initvalue default-value :initarg :slot-init)
The <type> is the type of the slot and defaults to <top> if not specified. The default-value is the default value to be given to a slot if no value is specified when the instance is created. It is an error to create an instance that does not have some value for each of its slots, so if values will not be provided when instances are created, they must be given as defaults using the second form. The :slot-init is used when calling make to create an instance of the class. You may also wish to define accessors (:accessor), readers (:reader), and writers (:writer).
By convention, the name of a class is a symbol that begins with < and ends with >.
If a class has more than one superclass, then it inherits slots and methods from all of them. This is called multiple inheritance. We will not cover multiple inheritance until later, so for now assume that there is only one superclass specified in the class definition.
A class definition consists of two parts: its direct superclasses and its direct slots. Each instance of a given class has not only the slots of the class, but also the slots of the direct superclass(es), the slots of their superclasses, and so on.
For example, the definitions
(defclass <animal> () (name :type <string> :initarg :name) (location :type <string> :initarg :location) (hunger :type <number> :initarg :hunger)) (defclass <person> (<animal>) (job :type <string> :initarg job) (home :type <string> :initarg home))define two new classes, <animal> and <person>. The class <animal> has one direct superclass, namely <top>, and three slots called name, location and hunger. The first two will be <string>s and the third will be a <number>. In Swindle, there is a root of all classes, namely the class <top>. When no superclasses are specified in a class definition, the class becomes a direct subclass of <top>.
The class <person> is defined to be a direct subclass of <animal>, therefore has all the slots of <animal>, as well as two new slots job and home of its own.
Having defined these two classes, we can use make to make instances of them. Each instance of a class will have its own copy of the slots of the specified class, as well as the slots of all of its superclasses.
The general form of a call to make is
(make <classname> slot-names-and-values ...)where <classname> is the name of the class to create an instance of, and slot-names-and-values is one or more pairs :initarg value. The :initarg is a slot name associated with one of the slots of the class as specified in the class definition. The value is an ordinary Scheme expression, which is evaluated and assigned to the slot at the time the instance is created. The value should be an instance of the type of the slot as specified in the class definition.
For example,
(define joe-bob
(make <person>
:name "joe-bob"
:where "here"
:hunger 10
:job "computer-geek"
:home "Ithaca"))
defines an instance of the class <person>. To
determine if an object is an instance of some particular class, we can
use the Swindle primitive instance-of?:
(instance-of? joe-bob <person>) ==> #t (instance-of? joe-bob <animal>) ==> #tIn this example it was necessary to specify a value for each of the slots in creating the instance, because none of the slots had default values.
The object joe-bob has slots name, where, and hunger that it inherits from its superclass <animal>, as well as slots job and home that are specific to the class <person>. Every instance of a class normally has its own copy of all the slots of its class and all superclasses. This is a simple form of inheritance: a class inherits slots from its superclasses.
A generic function is just a collection of methods, all with the same name. When a generic function is called, the types of the parameters of the various methods associated with the generic function are compared with the types of the arguments in the call. For each method, if the arguments are all instances of the parameter types of the method, then that method is said to be applicable. The generic function dispatches the applicable method with the most specific parameter list.
A generic function may have some methods associated with it at the time it is created, but it can also have other methods added to it later. A new generic function can be created using the special form defgeneric. For example,
(defgeneric (silly x))creates a generic function with the name silly. This generic function has no methods yet, so a call (silly x) at this point will result in an error "silly: no methods added yet".
We can add methods to the generic function silly using the special form add-method.
(defmethod (silly (x <person>)) "Gee, what a surprise.") (defmethod (silly (x <animal>)) "Maybe, maybe not.")If we now evaluate
(silly joe-bob)it will return "Gee, what a surprise." Both methods of silly are applicable to joe-bob, since joe-bob is an instance of both <person> and <animal>. However, since <person> is a subclass of <animal>, it is the first method that is dispatched, because it is the most specific.
The call
(silly 1)will give an error "No applicable methods", because the generic function silly does not have any methods whose parameter type matches the number 1.
A good way to understand the process of method dispatch in generic functions is in terms of inheritance. Simply put, a class inherits all the methods that apply to its superclasses. This makes sense because a method that applies to all instances of a class should also apply to all instances of any subclass of the class, since they are just special cases.
As noted above, every class except <object> has at least one direct superclass. A class inherits all the slots and methods of its superclasses. The inheritance of methods is much more interesting than the inheritance of slots, because by shadowing methods we can create classes that modify the behavior of other classes.
The idea of shadowing is that a class can have a method for some generic function that applies only to instances of that class, and that effectively causes the method(s) of its superclass(es) not to be run, or to be run only at its discretion. Consider the following simple class hierarchy:
(defclass <vehicle> ()
(location :type <string>
:initarg :location
:writer location-set!
:initvalue "here")
(speed :type <number>
:initarg :speed
:writer speed-set!
:initvalue 0))
(defclass <car> (<vehicle>)
(fuel :type <number>
:initarg :fuel
:writer fuel-set!
:initvalue 0))
(defclass <rocket> (<vehicle>)
(fuel :type <number>
:initarg :fuel
:writer fuel-set!
:initvalue 0)
(altitude :type <number>
:initarg :altitude
:writer altitude-set!
:initvalue 0))
(defclass <bicycle> (<vehicle>))
In this example, every class has at most one superclass, thus the
class hierarchy forms a tree:
<object>
|
<vehicle>
____/|\_____
/ | \
<car> <rocket> <bicycle>
We might define a generic function accelerate as follows:
(defgeneric (accelerate v a))
(defmethod (accelerate (v <vehicle>) (a <number>))
(speed-set! v (+ (speed v) a)))
(defmethod (accelerate (r <rocket>) (a <number>))
(cond ((> (fuel r) 0) (print "Whoosh...") (next-method r a))
(else (print "No gas. You lose."))))
(defmethod (accelerate (b <bicycle>) (a <number>))
(print "Dream on."))
The first method uses the special form speed-setter, which
accesses and changes the value of the speed slot in an
instance.When the writer functions (e.g., speed-set!) are applied to a parameter of a method specializer of a generic function, the writer must be associated with a slot in the class of that parameter as specified in the parameter list, or one of its superclasses. For example, the first method in the generic function accelerate above has a parameter v of class <vehicle>. It is all right to apply speed-set! to v in the body of the method, since speed is a slot associated with the class <vehicle>. However, it would not be all right to apply altitude-set! to v in the body of this method, even if the argument passed happened to be an instance of the class <rocket>. This is because for a <vehicle> in general, it does not make sense to access the slots of a <rocket> (or any other class that is not a superclass of <vehicle>), so it is disallowed.
If we define some instances of these classes
(define schwinn (make <bicycle>)) (define saturn-v (make <rocket> :fuel 10 :altitude 100000)) (define chevy (make <car> :fuel 10 :location "there"))then we can call the generic function accelerate on these instances. The rule for applying a method to an instance is to find the most specific method for that instance, where specificity is determined by the class hierarchy. If there is a method that specifies the class of the instance that the generic function was called with, that method is applied (which we saw above with silly). If there is no such method, and if there is a method for the direct superclass of the instance, then that one is applied. If there is no method for the direct superclass, then we check the superclass of the superclass, and so on. Eventually, when class <top> is reached, if there is still no applicable method, an error is signalled.
For example, if we evaluate
(accelerate chevy 10)there is no method for accelerate with a first parameter of the class <car>, thus we look for a method for the superclass of <car>, which is <vehicle>. There is such a method, and it is invoked. The code for this method simply adds the specified amount to the speed slot of the object. The object chevy does have a speed slot, since it is an instance of <car>, so it inherits the speed slot from the superclass <vehicle>. In this example the speed slot would be incremented by the given value 10, and since it was originally 0, its new value is 10.
On the other hand, if we evaluate
(accelerate schwinn 10)there is a method associated with accelerate that has a first parameter of class <bicycle>. Since schwinn is an instance of that class, that method is applicable, and it is the most specific method that is applicable. It simply prints out
Dream on.and returns. Thus the general method for <vehicle> is never invoked for objects of class <bicycle>. We say that the accelerate method for <bicycle> shadows the one for <vehicle> because it prevents the more general <vehicle> method from being invoked on objects in the class <bicycle>.
Finally, if we evaluate
(accelerate saturn-v 10)the method with the first parameter of type <rocket> gets invoked. It checks to see if the value of fuel is greater than zero. If it is, then it prints out
Whoosh...and calls the special procedure next-method. It invokes the next applicable method (if it exists). In this case that is the method for <vehicle>, because the direct superclass of <rocket> is <vehicle>. If there had been no method for <vehicle>, then the next method would be one for the superclass of <vehicle>. In this example, there is none, so an error would be signalled that there is no applicable method.
Intuitively, the next method that is called using next-method is the one that would have been called if the currently executing method had not existed. That is, think of a generic function without the currently executing method, and of calling that generic function.
The ability to call the next most applicable method is a very powerful technique. It allows classes not only to replace (shadow) the behavior of their superclasses, but also to modify that behavior.
There are three common patterns of usage for calling call-next-method. One is to do some processing and then call call-next-method; this is known as a before method. The second is to call call-next-method, then do some additional processing after it returns; this is referred to as an after method. The final pattern is a combination of the two: do some processing, call call-next-method, then do more processing afterwards; this is called an around method. These three patterns of invoking superclass methods add greatly to the power of abstraction in object-oriented programs.
A class can have more than one direct superclass. If more than one superclass is specified in a class definition, the inheritance hierarchy will no longer be a tree, but rather a directed acyclic graph (dag). The idea behind multiple inheritance is that it sometimes makes sense for a given class to inherit methods and slots from more than one superclass. For certain problems, this can considerably reduce the amount of code that must be written. On the other hand, it also complicates the process of determining the slots and the ordering of applicable methods.
In general, it is confusing when an instance has multiple slots with the same name, and it is a good idea to avoid this when designing the class hierarchy. With multiple inheritance, it is sometimes difficult to avoid such name conflicts. The rule (for any class hierarchy, even single inheritance) is that if there are multiple slots with the same name, the slot lowest in the hierarchy is the one that is accessible. Recall, however, that when a method is called with an object, that object is "cast'' to the class specified by the corresponding parameter of the method (e.g., when an instance of <car> above was passed to a function with a parameter of type <vehicle>, only the slots of class <vehicle> and its superclasses could be accessed). When there are multiple slots with the same name, this casting can cause a slot that was previously hidden to become accessible. This is why it can be quite confusing to have instances with more than one slot of the same name. It's best to avoid it if at all possible.
The ordering of the the applicable methods of a generic function is used to determine which method to dispatch. This ordering is determined by the ordering of the argument's class and superclasses. With single inheritance, the ordering of superclasses is a total order, since there is a unique path in the class hierarchy from a given class up to the root <top>. With multiple inheritance, however, the class hierarchy is no longer a tree, therefore the superclasses of a class are no longer necessarily totally ordered, but only partially ordered. This means that there may be two superclasses of the same class that are incomparable. In this case, Swindle just picks a total order on the superclasses that is consistent with the partial order, and uses this to order the methods. There may be several total orders consistent with a given partial order, and it is unspecified which will be used (but it is most likely the one you don't want).
To illustrate this phenomenon, consider the following class definitions:
(defclass <agent> () (name :type <string> :initvalue "me") (loc :type <string> :initvalue "here")) (defclass <animal> (<agent>) (eats-people? :type <boolean> :initvalue #f)) (defclass <person> (<agent>) (home :type <string> :initvalue "here") (possessions :type <list> :initvalue empty)) (defclass <martian> (<agent>) (stuff :type <list> :initvalue empty)) (defclass <pet> (<animal>) (owner :type <top> :initvalue 'none)) (defclass <feeb> (<person> <pet>))
This defines a class hierarchy with the following structure:
<agent>
___________|___________
| | |
<animal> <person> <martian>
| |
<pet> |
|___________|
|
<feeb>
If we make an instance of class <feeb>
(define zoid (make <feeb>))then this instance has slots owner, home, posessions, eats-people?, name, and loc.
Now consider the generic function
(defgeneric (foo x)) (defmethod (foo (x <agent>)) (print "agent")) (defmethod (foo (x <feeb>)) (print "feeb") (call-next-method x)) (defmethod (foo (x <pet>)) (print "pet") (call-next-method x)) (defmethod (foo (x <person>)) (print "person") (call-next-method x)) (defmethod (foo (x <animal>)) (print "animal") (call-next-method x))and suppose we call (foo zoid). All methods of foo are applicable, because zoid is an instance of all five classes. The most specific of these is <feeb>; however, the ordering of the classes above <feeb> is not a total order, but only a partial order. In other words, there are incomparable elements in the graph between the class <feeb> and the class <agent>.
Since foo has a method specializer for the class <feeb>, that method is the most specific, so that is the method that is dispatched. But note that that method calls call-next-method. What happens now? There are method specializers for both <pet> and <person>, and either one of these could be the next method. In this case Swindle will pick one of them, and it is unspecified which one. Let's say it picks the one for <pet>. Note that that method also calls call-next-method, and this time is could be either the method for <person> (which wasn't chosen last time), or <animal>. Either one could be chosen.
The ordering of the classes that is used to dispatch methods can be any ordering that is consistent with the partial order of the class hierarchy above the class of the argument to the generic function. Here "consistent'' means that any subclass relationships that exist in the partial order must also hold in the total order; i.e., if c1 is a subclass of c2 in the partial order, then it must also be in the total order. Other than that there are no constraints. For example, in the call (foo zoid), any of the following three total orders on the classes above <feeb> could be used:
<agent> <agent> <agent> | | | <person> <animal> <animal> | | | <animal> <person> <pet> | | | <pet> <pet> <person> | | | <feeb> <feeb> <feeb>The call (foo zoid) will run all of the methods in this generic function, because they are all applicable to the argument, and all except the one for <agent> call call-next-method. The method for <feeb> will run first, and the method for <agent> will run last, and the three remaining methods will run in between in some unspecified order that respects the fact that the method for <pet> must precede the method for <animal>. This yields three possible results:
"feeb" "feeb" "feeb" "pet" "pet" "person" "animal" "person" "pet" "person" "animal" "animal" "agent" "agent" "agent"The one that actually occurs depends on the Swindle implementation.