DATA ABSTRACTION and OBJECT ORIENTATION (Dec. 6 and 11, 2012) Last project (templates) due 5pm Friday Dec. 14 Final exam in the official University slot, Tuesday Dec. 18, 7:15-10:15 pm PLEASE BE SURE TO FILL OUT THE ON-LINE COURSE EVALUATION ---------- We talked about data abstraction some back in the unit on naming and scoping. Recall that we traced the historical development of abstraction mechanisms: static set of variables Basic locals Fortran statics Fortran, Algol 60, C modules Modula-2, Ada 83 module types Euclid objects Smalltalk, C++, Eiffel, Java, C#, Ruby, Python object-based Self, JavaScript type extensions Oberon, Modula-3, Ada 95 Statics allow a subroutine to retain values from one invocation to the next, while hiding the name in-between. Modules allow a collection of subroutines to share some statics, still with hiding. If you want to build an abstract data type, though, you have to make the module a manager. Module types allow the module to *be* the abstract data type -- you can declare a bunch of them. This is generally more intuitive. It avoid explicit object parameters to many operations. One minor drawback: If you have an operation that needs to look at the innards of two different types, you'd define both types in the same manager module in Modula-2. In C++ you need to make one of the classes (or some of its members) "friends" of the other class. Objects add inheritance and dynamic method binding. Simula 67 introduced these, but didn't have data hiding. ---------------------------------------- The 3 key factors in OO programming (as codified by Wegner): encapsulation (data hiding) inheritance dynamic method binding ---------------------------------------- Visibility rules Public and Private parts of an object declaration/definition. (Recall that a *declaration* introduces a name, and enough information about it to allow it to be *used*, at least in limited contexts. A *definition* provides enough information for the compiler to implement the object.) 2 reasons to put things in the declaration so programmers know how to use the object so the compiler knows how to generate code for uses of the object At the very least the compiler needs to know how to invoke the methods of the object. If it must allocate space for the object it also needs to know its size. To figure out the size, the compiler will often need to know information that the programmer does *not* need to know, such as the types (sizes) of private data members. Many module-based languages separate modules into pieces: one for the declaration and one for the definition, usually placed in separate files for the purpose of separate compilation. Declaration modules may be compiled into symbol table data, or they may be textually "included" into user and definition modules. The latter option is a more structured, formal version of the typical ".h" and ".c" files of C. Typically if you modify a definition module you have to recompile only that definition module. If you change the private portions of a declaration module (the parts the compiler depends on), you have to recompile both the definition module and the user modules, but you don't have to change the *source* of user modules. ---------- Several recent languages, including Java and C#, dispense with separate declaration and implementation modules. The compiler peruses the single body of code and extracts what users of it need. If you want teams to develop in parallel, you start by creating skeleton versions, which each team uses as an interface specification while they flesh out their own part. ---------- C++ distinguishes among public visible to anybody protected visible only to this class and its descendants private visible only to this class Default is public for structs and private for classes. C++ base classes can also be public, private, or protected. E.g. class circle : public shape { ... anybody can convert (assign) a circle* into a shape* class circle : protected shape { ... only members and friends of circle or its derived classes can convert (assign) a circle* into a shape* class circle : private shape { ... only members and friends of circle can convert (assign) a circle* into a shape* Java rules are slightly different: public: visible to anybody (package) visible only to this class and classes in the same package protected visible only to this class, its descendants, and classes in the same package private visible only to this class Package is the default; it's what you get with no specifier. 'package' isn't a keyword. ---------------------------------- A few C++ and Java features you may not have learned: destructors These are the opposite of constructors. Mostly they're needed for explicit space management. Java can get by without them because it has garbage collection. Given the availability of destructors, C++ programmers have invented other clever uses for them, e.g. for locking: // here is some non-critical code { mutex m(my_lock); // mutex is a dummy object whose constructor acquires // the lock passed as an argument, and then keeps a // pointer to this lock in a private data member. // code that we'd like to have executed atomically // at end of scope, mutex destructor automatically releases // my_lock } initialization v. assignment not the same in C++! foo::operator=(&foo) v. foo::foo(&foo) foo b; // calls no-arg constructor foo f = b; // calls one-arg "copy constructor". // This is syntactic sugar for // foo f(b); foo b, f; // calls no-arg constructor f = b; // calls operator= C++ requires that every object be initialized by a call to an constructor. The rules for doing this for expanded objects are quite complex. objects as members foo::foo(args) : base(args0), member1(args1), member2(args2) { ... args0, args1, args2, &c need to be specified in terms of args. The reason these things end up in the header of foo is that they get executed *before* foo's constructor does, and the designers consider it good style to make that clear in the header of foo::foo. Commonly the arg lists are singletons (for copy constructors), and the code foo::foo(a, b, c) : member1(a), member2(b) { ... might be replaced with foo::foo(a, b, c) { member1 = a; member2 = b; but this is NOT the same: the latter option calls zero-arg constructors for member1 and member2 *before* calling foo::foo(), and *then* calls operator=. Note that the constructors for base classes are called *before* the constructors for children (with multiple inheritance, they're called in the order the specified in the header of the child). Destructors for base classes are called *after* the destructors for children. Life is easier in Java because there isn't multiple inheritance, and because all object-typed variables are references. Data members of object types are simply initialized to null; you specify arguments to the constructors when you call new, explicitly. Arguments for the superclass constructor, if any, can be provided in a pseudo-call, which must be the first statement of the constructor: public child(a, b, c) { super(a, b); ... If you don't provide the super() call, the compiler inserts a call to the zero-arg constructor (which must exist). classes as members Called "inner" classes in Java. Q: if /Inner/ is a member of /Outer/, can /Inner/'s methods see /Outer/'s members, and if so, which instance do they see? class A { int i; class B { method foo() i := 3 // is this allowed? C++ and C# say no, inner classes can see only static fields of parent. Java says yes, instances of inner class belong to an instance of the outer class, and can access data members of that class. This capability provides much (most?) of the power of nested subroutines, which C++ and Java lack. Java can be thought of as having four kinds of inner classes. Static inner classes aren't really inner, because they don't need an outer class instance to exist. Member classes (a class within a class) contain a hidden reference to the parent object. Local classes (a class within a method) contain the hidden reference AND copies of the method's parameters and final locals (but *not* non-final locals -- so there's still no static chain). Anonymous inner classes are like local classes, but can have only one instance. virtual functions Virtual functions provide C++'s dynamic method binding: you don't know at compile time what type the object referred to by a variable will be at run time. Simula also had virtual functions (all of which are abstract). In Smalltalk, Eiffel, Modula-3, and Java *all* member functions are virtual, so you don't need the keyword. Key question: if child is derived from parent and I have a parent* p (or a parent& p) that points (refers) to an object that's actually a child, what member function do I get when I call p->f (p.f)? By default in C++ I get p's f, because p's type is parent*. But if f is a virtual function, I get c's f. In Java all methods are virtual. Also note: If a C++ virtual function has a "0" body in the parent class, then the function is said to be a "pure" virtual function and the parent class is said to be "abstract". In Java you prepend the method declaration with the "abstract" keyword. You can't declare objects of an abstract class; you have to declare them to be of derived classes. Moreover any derived class *must* provide a body for the pure virtual function(s) (unless it too is supposed to be abstract). Note that virtual functions make it much harder to in-line function calls. multiple inheritance in Standard C++, Eiffel, Python, Perl (sorta) see below mix-in inheritance in Java, C#, Ruby, PHP single inheritance in Simula, Smalltalk friends functions classes namespaces (similar to packages in Java) These are good old-fashioned modules, except that they can span multiple files. They have a simple import/export mechanism: everything is exported with a "qualified" name (namespace::object). This avoids name conflicts in user modules. To get around the nuissance of using fully qualified names, users can import them: using foo::my_object; // Within current scope I can now simply refer to my_object. using namespace foo; // import eveything from foo, unqualified ---------------------------------- BTW: note that inheritance does not obviate the need for generics. You might think: hey, I can define an abstract list class and then derive int_list, person_list, etc. from it, but the problem is you won't be able to talk about the elements because you won't know their types. That's what generics are for: abstracting over types. Java 2 doesn't have generics, but it does have (checked) dynamic casts. Java 5 has generics. ---------------------------------- Implementation of classes Data members of classes are implemented just like structs (records). With (single) inheritance, derived classes have extra fields at the end. A pointer to the parent and a pointer to the child contain the same address -- the child just knows that the struct goes farther than the parent does. Non-virtual functions require no space at run time; the compiler just calls the appropriate version, based on type of variable. Member functions are passed an extra, hidden, initial parameter: 'this' (called 'current' in Eiffel and 'self' in Smalltalk). Virtual functions are the only thing that requires any trickiness. They are implemented by creating a dispatch table ("vtable") for the class and putting a pointer to that table in the data of the object. Objects of a derived class have a different dispatch table. In the dispatch table, functions defined in the parent come first, though some of the pointers point to overridden versions. You could put the whole dispatch table in the object itself. That would save a little time, but potentially waste a LOT of space. C++ philosophy is to avoid run-time overhead whenever possible. (Sort of the legacy from C). That's why non-virtual functions are the default. Languages like Smalltalk have (much) more run-time support. Note that if you can query the type of an object, then you need to be able to get from the object to run-time type info. The standard implementation technique is to put a pointer to the type info at the beginning of the vtable. Of course you only have a vtable in C++ if your class has virtual functions. That's why you can't do a dynamic_cast on a pointer whose static type doesn't have virtual functions. Terminology: reflection. Java, C#, Ruby, and Python have extensive reflection mechanisms. ---------------------------------- Multiple Inheritance | in C++, you can say | | class professor : public teacher, public researcher { | ... | } | | Here you get all the members of teacher *and* all the members of researcher. | If there's anything that's in both (same name and argument types), then calls | to the member are ambiguous; the compiler disallows them. You can of course | create your own member in the merged class: | | professor::print () { | teacher::print (); | researcher::print (); | // other stuff | } | | Or you could get both: | | professor::tprint () { | teacher::print (); | } | professor::rprint () { | researcher::print (); | } | | ---------- | | Virtual base classes | | In the default case if you inherit from two classes that are both derived | from some other class B, your implementation includes two copies of B's | data members. That's often fine, but other times you want a *single* copy | of B. For that you make B a virtual base class. | | From Stroustrup's book: | | class window { | } | class window_w_border : public virtual window { | } | class window_w_menu : public virtual window { | } | class window_w_border_and_menu : | public virtual window, | public window_w_border, | public window_w_menu { | } | | This last class has only one instance of the window stuff beneath it. | If there's a member foo in window that is overridden in one of | window_w_border and window_w_menu, but not the other, then | window_w_border_and_menu gets the overridden version. If both the | middle classes override foo, then the compiler will complain if you | try to derive window_w_border_and_menu from both of them. | | There are a bunch of other subtle issues involved with virtual base classes; | see sec. 6.5.3 of Stroustrup's book. | | Eiffel gives the effect of virtual base classes by default; you have to | explicitly ask for multiple copies of a method to be included when the | inheritance tree re-merges. Because Eiffel allows the choice to be made when | the derived class is defined (the base class doesn't say), the implementation | is messier than in C++; I don't describe the details here. | | ---------- | | Implementation of multiple inheritance -- messy! | | First consider case without repeated inheritance (immediate ancestors have | no common ancestor). | | A B C D -> A -> +------+ | \ | / | | | ----------> +-------+ | D | dB |------| | | | A methods | | | | A | |---|---| | | | | | | | | D methods | | | | | +---|---+ | dC B -> |------| | | | ----------> +---|---+ | | |------| | | | B methods | | | B | +---|---+ | C ------> |------| | | ----------> +---|---+ | |------| | | | C methods | | C | +---|---+ | +------+ | | If you assign a D pointer into a B or C variable, the compiler has to execute | some code. Specifically, it has to add to the pointer the displacement | within D where B or C's members appear. Fortunately, the compiler knows this | offset. Unfortunately, the same problem arises in a case where the | compiler doesn't know the offset. Specifically, suppose D overrides a | virtual function f originally provided in C. Now suppose we assign | a D pointer into a C variable (or via a C variable into an A variable). | When we call f we're supposed to get D's version, but how do we set the | initial (this) parameter? We don't know what our C or A was embedded inside | of. Answer: entries in method (virtual function) tables have to include two | things: a function pointer and an offset ("this" correction) to add to | "this". In the picture above, methods in the top method table will have | zero offsets. Methods in the lower tables will have zero offsets if they | belong to B or C, but they'll have an offset of d if they were overridden | by D. Note that the cost of offsets in virtual function tables is borne | by *all* virtual functions when we add multiple inheritance to the | language; we can't avoid it for objects with single inheritance. | | Next consider case repeated inheritance *without* virtual base classes | (replicated inheritance). | | A A D -> B -> +------+ | | | | ----------> +-------+ | B C | |------| | | | A/B methods | \ / d | A | | | | | D | |------| |---|---| | | | +B | | | | D (only) methods | | | +-------+ | C -> |------| | | ----------> +-------+ | |------| | | | A/C methods | | A | | | | | |------| | | | | | +C | +-------+ | +------+ | | +D | | +------+ | | Note that A members aren't directly visible using a D pointer, due to | ambiguity. But if you assign a D pointer into a B or C variable, then | you can access the (appropriate set of) A members. | | The compiler knows that D is derived from both B and C. Given a D pointer, | the pointer will use the first method table to find virtual functions for | B and B::A, as well as virtual function introduced by D. But it will use the | second method table to find virtual functions of C and C::A. | In all cases it uses the 'this correction' defined above. | | ---------- | | Now consider virtual base classes (shared inheritance). | | A | / \ | B C | \ / | D | | Because A is a part of both B and C, we can't make both B and C | contiguous in memory. Fortunately, we always know when something is | derived from a virtual base class, so we can implement it specially and | use the more conventional (and cheaper) implementation for everything | else. | | The idea is: if you have a virtual base class, then you have to keep a | pointer to the vtable and data members of that base class among your own | data members: | | D--> B --> +------+ +---------+ | | ----------> | | | B methods | |------| +---------+ | ,------ &A | | | | D (only) methods | | |------| | | | | | | | +---------+ | | | +B | | | | | | C--+--> |------| +---------+ | | | ----------> | | | C methods | | |------| | | | | |,----- &A | +---------+ | | |------| | | | | | | | +C | | | | | | | |------| | | | | | | | +D | | | | | | | +------+ +---------+ | A--`--> | ----------> | | | A methods | +------+ | | | | | | +---------+ | | | | +------+ | | Vtables still consist of pairs. | To access a data member of a virtual base class, you first indirect through | the pointer, which follows your vtable pointer. | If you need a virtual method of a base class, you first find the appropriate | base class view, using known offset or indirection, then access vtable, then | apply 'this' correction to base class view to get parameter to pass to | (correct version of) method. | | To call the nth virtual method originally defined in A, starting with a | D view: | | r1 := my_D_view -- original pointer | r1 := *(r1 + 4) -- A view | r2 := *r1 -- address of A part of D vtable | r3 := *(r2 + (n-1)x8) -- subroutine address | r2 := *(r2 + (n-1)x8+4) -- 'this' correction | r1 := r1 + r2 -- 'this' | call *r3 ---------- Mix-in inheritance Comparatively simple to implement. Each class can have one "real" parent and an arbitrary number of *interfaces*, each of which is fully abstract: no data members (other than statics); no non-pure-virtual methods. Now you create an extra vtable for each interface your object supports, and you embed pointers to these vtables among the data of each object. Each interface vtable begins with a field that gives the offset back from the vtable pointer to the beginning of the object in which that pointer appears: class widget {... interface sortable {... interface graphable {... interface storable {... class named_widget extends widget implements sortable { ... class augmented_widget extends named_widget implements graphable, storable {... augmented widget object widget -----> +------+ +------+ view ||| | ----------> | | augmented_widget ||a |------| | | part of vtable |b| | | +------+ ||| | | sortable -++--> |------| +------+ sortable part view || | ----------> | a | of vtable c| |------| +------+ || | name | graphable -+---> |------| +------+ view | | ----------> | b | graphable part storable -+---> |------| +------+ view | ------, |------| \ +------+ | more | '-> | c | storable part | data | +------+ +------+ The augmented_widget part of the vtable includes the (non-interface) methods of widget and named_widget. If the compiler needs to pass an augmented_widget to a method that expects a 'graphable', it passes the graphable view. The method assumes the thing it was passed begins with a vtable pointer. It dereferences this pointer to find the vtable, then pulls the offset out of the first word of the vtable and subtracts it from the provisional 'this' it was passed, to get the "real" 'this', which it can pass to other methods. ======================================== SMALLTALK The canonical object-oriented language. Has all three of the characteristics listed above. Based on the thesis work of Alan Kay at Utah in the late 1960's. Went through 5 generations at Xerox PARC, where Kay worked after graduating. Smalltalk-80 is the current (long-standing) standard. Smalltalk is interesting in its own right, and also for historical reasons. It's the language that carried the OO torch from the Simula of the 60s to the C++ of the 80s and 90s and the Java, C#, Python, Ruby, etc. of the 90s and 00s. Smalltalk is HEAVILY integrated into its programming environment. Things like typefaces are part of the syntax of the language. Everything in Smalltalk is anthropomorphized. "3 + 4" is syntax for sending the message "+ 4" to the object 3, which returns a reference to the object 7. Even control flow is conceptualized as messages. For example: total = 0 ifTrue: [average <- 0] ifFalse: [average <- sum // total] sends an "= 0" mesasage to the object total, which returns a reference to either the object TRUE or the object FALSE, which is then passed an "ifTrue: ... ifFalse ..." message. Similarly count <- 0. sum <- 0. [count <= 20] whileTrue: [sum <- sum + count. count <- count + 1] sends a "whileTrue: ..." message to a block that would return TRUE or FALSE if sent a "value: ..." message. Similarly 3 timesRepeat: [...] 1 to: 100 by: 10 do: [:i | total <- total + (a at: i)] A simple example method for factorial, understood by integers: factorial self = 0 ifTrue: [^1]. self < 0 ifTrue: [self error 'Factorial not defined'] ifFalse: [^ self * (self-1) factorial] ------------------------- The OO syntax (and semantics) of Objective C and Ruby is highly reminiscent of Smalltalk. In Ruby the expression 4 * 3 < 16 is equivalent to 4.*(3).<(16) which in turn is equivalent to 4.send('*', 3).send('<', 16) that is, send a "'*', 3" message to 4 then send a "'<', 16" message to t, where t is what you got back from the first send Note, however, that this is more than syntactic sugar: message notation evaluates left-to-right, without regard to traditional notions of precedence. So 16 > 4 * 3 is equivalent to 16.>(4).*(3) or 16.send('>', 4).send('*', 3) which groups as (16.>(4)).*(3) or (16.send('>', 4)).send('*', 3) which produces a run-time type error ("undefined method `*' for true:TrueClass"). If you want the equivalent of the infix evaluation order, you have to parenthesize explicitly: 16.>(4.*(3)) or 16.send('>', 4.send('*', 3)) More interestingly, Ruby has true Smalltalk-like iterators: sum = 0 => 0 [ 1, 2, 3 ].each { |i| sum += i } => [1, 2, 3] # array itself sum => 6 Here the (parameterized) brace-enclosed block is passed to the each method as a parameter. There's also more conventional-looking syntax: sum = 0 for i in [1, 2, 3] do # 'do' is optional sum += i end sum The for loop is syntactic sugar for a call to each. Here's a more OO alternative: sum = 0 1.upto 3 {|i| sum += i} sum or instead of using braces: sum = 0 i.upto 3 do |i| sum += i end sum You can write your own iterators using 'yield'. class Array def find for i in 0...size value = self[i] return value if yield(value) end return nil end end ... [1, 3, 5, 7, 9].find {|v| v*v > 30 } => 7 Think of yield as invoking the block that was juxtaposed ("associated") with the call to the iterator. Notice that we've defined a new method of the built-in Array class. (Actually, Array already has a find method, but we can redefine it, and it probably looks like this anyway.) Blocks can also be turned into first-class closures, with unlimited extent: def nTimes(aThing) # note lack of type declaration -- dynamically typed, as in Lisp return proc { |n| aThing * n } end In recent Ruby, -> is a synonym for proc p1 = nTimes(3) p2 = nTimes("foo") p1.call(4) => 12 p2.call(4) => "foofoofoofoo" Here's a mind-bender. Reduction for arrays. class Array def inject(n) each { |value| n = yield (n, value) } # that's self.each # yield invokes (just once) the block associated # with the call to inject n end def sum inject(0) { |n, value| n + value } end def product inject(1) { |n, value| n * value } end end [2, 4, 6].sum => 12 [2, 4, 6].product => 48 All in all Ruby is pretty cool. Check it out. (I do wish it let you associate more than one block with a call.) ------------------------- Object orientation in Perl 5 is kind of a kludge; Perl 6 is supposed to be better JavaScript has a very strange system based on "prototype objects". It's an "object-based" language, as opposed to object-oriented. (The original object-based language was Self.) JavaScript, Python, and Ruby all allow new fields to be added to an object at run time. JavaScript and Ruby allow new methods to be added. Python and Ruby allow class bodies to be elaborated -- conditional compilation. In Ruby: class My_class def initialize(a, b) @a = a; @b = b; end if expensive_function() def get() return @a end else def get() return @b end end end ------------------------- type extensions build on structs/records language already has modules Ada 95, Modula-3, Oberon single inheritance no constructors or destructors explicit 'this' parameter all methods virtual in Modula-3 (also Oberon, I think) static by default in Ada 95; virtual when desired; but not a property of the method; rather, determined by access through "class-wide" parameter or pointer Fortran 2003 Exist OO extensions to Common Lisp (CLOS), Rexx (Object Rexx), Tcl (Incr Tcl)