«1 MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6.001|Structure and Interpretation of Computer ...»
MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001|Structure and Interpretation of Computer Programs
Reading: Section 4.1
Languages for Object-Oriented Programming
This problem set is probably the most di cult one of the semester, but paradoxically, the one
that asks you to write the least amount of code, and for which you should have to spend the least time in lab, provided that you prepare before you come to lab. Instead of asking you to do a lot of implementation, we are asking you to assume the role of language designer, and to think about and discuss some issues in the design of languages for object-oriented programming. Note especially that there is a signi cant part of this problem set to be completed after you have nished in the lab.
This problem set has been designed so that the interpreter you will be dealing with is an extension of the metacircular evaluator in chapter 4 of the book. The implementation below is described with reference to the programs in the book. In order to understand what is going on, it will be necessary to work through section 4.1 before starting on this assignment.
Although Object-Oriented programming has become very popular, the design of languages to sup- port Object-Oriented programming is still an area of active research. In this problem set, you will be dealing with issues that are not well-understood, and around which there are major disagree- ments among language designers. The questions in this problem set will not ask you to supply \right answers." Instead, they will ask you to make reasonable design choices, and to be able to defend these choices. We hope you will appreciate that, once you have come to grips with the notion of an interpreter, you are in a position to address major issues in language design, even issues that are at the forefront of current research.1 Tutorial exercise 1: Do exercise 4.2 of the notes. Don't actually go to lab to implement this.
Just be able to explain precisely what procedures need to be modi ed, what new procedures need to be written, and what the code must do.
This problem set was developed by Hal Abelson, Greg McLaren, and David LaMacchia. It draws on a Scheme 1 implementation of Oaklisp by McLaren and a Scheme implementation of Dylan by Jim Miller. The organization of the generic function code follows the presentation of the Common Lisp Object System (CLOS) in The Art of the Metaobject Protocol, by Gregor Kiczales, Jim des Rivieres, and Dan Bobrow (MIT Press, 1991).
6.001, Sample assignment|Object-oriented programming 2
1. Issues in object-oriented language design We've already seen two di erent approaches to implementing generic operations. One is datadirected programming, which relies on a table to dispatch based on the types of arguments. The second method, message-passing, represents objects as procedures with local state. As we saw in problem set 5, these objects can be arranged in complex inheritance relationships, such as \a troll is a kind of person."
One drawback with both of these approaches is that they make a distinction between generic operations and ordinary procedures, or between message-passing objects and ordinary data. This makes it awkward, for example, to extend an ordinary procedure so that it also works as a generic operation on new types of data. For instance, we might like to extend the addition operator + so that it can add two vectors, rather than having to de ne a separate vector-add procedure.
Recent experiments with object-oriented languages have attempted to integrate objects into the core of the language, rather than building an object system on top of the language. The idea is that everything in the language is an object, and all procedures are generic operations. Two such languages, both based upon Scheme, are Oaklisp, developed in 1986 by Kevin Lang and Barak Pearlmutter at CMU, and DylanTM (Dynamic Language), currently under development at the Apple Research Center in Cambridge. The language we will implement in this problem set is called MIT TOOL (Tiny Object Oriented Language). It is essentially a (very) simpli ed version of Dylan, designed to make the implementation an easy extension of the metacircular evaluator of chapter 4.
1.1 Classes, instances, and generic functions The framework we'll be using in TOOL (which is the same as in many object-oriented systems) includes basically the same ideas as we've already seen, although with di erent terminology. An object's behavior is de ned by its class|the object is said to be an instance of the class. All instances of a class have identical behavior, except for information held in a set of speci ed slots, which provides the local state for the instance. Following Dylan, we'll use the convention of naming classes with names that are enclosed in angle brackets, for example account or number.2 The define-class special form creates a new kind of class. You specify the name of the class, the class's superclass, and the names for the slots. In TOOL, every class has a superclass, whose behavior (and slots) it inherits. There is a prede ned class called object that is the most general kind of object. Every TOOL class has object as an ancestor. Once you have de ned a class, you use the special form make to create instances of it. Make takes the class as argument, together with a list that speci es values for the slots. The order in which the slots and values are listed does not matter, since each slot is identi ed by name. For example, we can specify that a \cat" is a kind of object that has a size and a breed, and then create an instance of cat. Note the use of the get-slot procedure to obtain the value in a designated slot.
Keep in mind that this use of brackets is a naming convention only|like naming predicates with names that end 2
TOOL== (define garfield (make cat (size 6) (breed 'weird))) *undefined* as in Scheme, define returns the undefined value TOOL== (get-slot garfield 'breed) weird
Procedures in TOOL are all generic-functions, de ned with the special form make-generic-function:
TOOL== (define-generic-function 4-legged?) (defined generic function: 4-legged?) You can think of a newly de ned generic function as an empty table to be lled in with methods.
You use define-method to specify methods for a generic function that determine its behavior on various classes.
TOOL== (define-method 4-legged? ((x cat)) true) (added method to generic function: 4-legged?)
TOOL== (4-legged? garfield) #t TOOL== (4-legged? 'Hal) who-knows?
The list in define-method following the generic function name is called the list of specializers for the method. This is like an argument list, except that it also speci es the class of each argument.
In the rst example above, we de ne a method for 4-legged? that takes one argument named x, where x is a member of the class cat. In the second example, we de ne another method for 4-legged? that takes one argument named x, where x is a member of the class object. Now 4-legged? will return true if the argument is a cat, and will return who-knows? if the argument is an object. Notice that garfield is an object as well as a cat (because object is the superclass of cat). Yet, when we call 4-legged? with garfield as an input, TOOL uses the method for cat, and not the method for object. In general, TOOL uses the most speci c method that applies to the inputs.3 In a similar way, we can de ne a new generic function say and give it a method for cats (and
subclasses of cats):
See the code (below) for a de nition of \most speci c method." This is one of the things that language designers 3
TOOL== (define-method say ((cat cat) (stuff object)) (print 'meow:) print is TOOL's procedure for printing things (print stuff)) (added method to generic function: say) TOOL== (define-class house-cat cat address) (defined class: house-cat) TOOL== (define fluffy note that a house cat is a cat, and therefore (make house-cat has slots for breed and size, as well (size 'tiny))) as for address TOOL== (get-slot fluffy 'breed) *undefined* we never initialized fluffy's breed TOOL== (say garfield '(feed me))
(feed me) TOOL== (say fluffy '(feed me))
(feed me) TOOL== (say 'hal '(feed me)) No method found -- APPLY-GENERIC-FUNCTION In the nal example, TOOL gives an error message when we apply say to the symbol hal. This is because hal is a symbol (not a cat) and there is no say method de ned for symbols.
We can go on to de ne a subclass of cat:
TOOL== (define-class show-cat cat awards) (defined class: show-cat) TOOL== (define-method say ((cat show-cat) (stuff object)) (print stuff) (print '(I am beautiful))) (added method to generic function: say)
TOOL== (say cornelius-silverspoon-the-Third '(feed me)) (feed me) (i am beautiful) TOOL== (define-method say ((cat cat) (stuff number)) (print '(cats never discuss numbers))) (added method to generic function: say) TOOL== (say fluffy 37) (cats never discuss numbers) As the nal example illustrates, TOOL picks the appropriate method for a generic function by examining the classes of all the arguments to which the function is applied. This di ers from the 6.001, Sample assignment|Object-oriented programming 5 message-passing model, where the dispatch is done by a single object.
Notice also that TOOL knows that 37 is a member of the class number. In TOOL, every data object is a member of some class. The classes number, symbol, list, and procedure are prede ned, with object as their superclass. Also, every procedure is a generic procedure, to which you can add new methods. The following generic procedures are prede ned, each initially
with a single method as indicated by the specializer:
+ (number number)
- (number number) * (number number) / (number number) = (number number) (number number) (number number) sqrt (number) cons (object object) append (list list) car (list) cdr (list) null? (object) print (object) get-slot (object symbol) set-slot! (object symbol object)
Multiplying a number times a vector, or a vector times a number, should scale the vector by the number. Adding a vector plus a number is not de ned. Also de ne a generic function length, such that the length of a vector is its length and the length of a number is its absolute value.
2. The TOOL Interpreter A complete listing of the TOOL interpreter is appended to this problem set. This section leads you through the most important parts, describing how they di er from the Scheme evaluator in chapter 4.
New data structures A class is represented by a data structure that contains the class name, a list of slots for that class, and a list of all the ancestors of the class. For instance, in our cat example above, we would have a class with the name house-cat, slots (address size breed), and superclasses (cat object). Note that the slot names include all the slots for that class (i.e., including the slots for the superclass). Similarly, the list of ancestors of a class includes the superclass and all of its ancestors.
A generic function is a data structure that contains the name of the function and a list of the methods de ned for that function. Each method is a pair|the specializers and the resulting procedure to use. The specializers are a list of classes to which the arguments must belong in order for the method to be applicable. The procedure is represented as an ordinary Scheme procedure.
Omitting lambda takes away our ability to have unnamed procedures, as we do in Scheme. You might want to 4 think about how to add such a feature to TOOL.
6.001, Sample assignment|Object-oriented programming 7 An instance is a structure that contains the class of the instance and the list of values for the slots.
See the attached code for details of the selectors and constructors for these data structures.
is handled by the following procedure:
(define (eval-generic-function-definition exp env) (let ((name (generic-function-definition-name exp))) (let ((val (make-generic-function name))) (define-variable! name val env) (list 'defined 'generic 'function: name)))) This procedure extracts the name portion of the expression and calls make-generic-function to create a new generic function. Then it binds name to the new generic function in the given environment. The value returned is a message to the user, which will be printed by the read-evalprint loop.
Eval-define-method handles the special form
for example (define-method say ((cat cat) (stuff number)) (print '(cats never discuss numbers))) In general here, generic-function is the generic function to which the method will be added, paramsand-classes is a list of parameters for this method and the classes to which they must belong, and body is a procedure body, just as for an ordinary Scheme procedure.5 The syntax procedures for this form include appropriate procedures to select out these pieces (see the code).
Eval-define-method rst nds the generic function. Notice that the generic-function piece of the expression must be evaluated to obtain the actual generic function. Eval-define-method disassembles the list of params-and-classes into separate lists of parameters and classes. The parameters, the body, and the environment are combined to form a procedure, just as in Scheme. The classes become the specializers for this method. Finally, the method is installed into the generic function.
The dot before the word \body" signi es that we can put more than one expression in the body|just as with 5
Tutorial exercise 3: Eval-define-method calls paramlist-element-class in order to nd the class for each parameter. Without looking at the attached code, predict whether paramlist-element-class should call tool-eval. Now look at the code and see if you were right. Give a careful explanation of why tool-eval is (or is not) called, and what di erence this makes.