Object Oriented Types COMS W4115 Prof Stephen A Edwards Spring 2002 Columbia University Department of Computer Science Object Oriented Types The important thing about a language is what programs it can t describe Nicklas Wirth Inventor of Pascal Three Attributes of OO Langauges 1 Encapsulation Hides data and procedures from other parts of the program 2 Inheritance Creates new components by refining existing ones 3 Dynamic Method Dispatch The ability for a newly refined object to display new behavior in an existing context Encapsulation How do you keep a large program partitioned Running Example Linked List Stack typedef struct node int val struct node next node t node t list node t n node t malloc sizeof node t n val 3 n next list list n Linked List Problems Implementation exposed Malloc must be called explicitly every time node created Code that creates a node needs to know implementation of node Easy to forget part of the initialization of a node Difficult to change implementation much code to update Global variable used for list can t have two Advantage fast Linked List Second Try Put node creation into a function void push int v node t n node t malloc sizeof node t n val v n next list push 3 Linked List 2 Advantages Easier to use push operation free of implementation details Changes lead to less code to update Disadvantages Other program code can still create and modify list nodes Still using a global variable for the list Difficult to reuse this code Slower Linked List Third Try node new list void push node list int v void destroy list node list node l new list push l 3 destroy list l Linked List 3 Advantages Even easier to use More flexible can manage multiple lists Changes lead to less code to update Disadvantages Other program code can still create and modify list nodes really want to hide the node type more Implementation not completely hidden push is probably too popular an identifier Slow Encapsulation A key technique for complexity management is isolation Put a simple interface on a complex object Reduces conceptual load easier to think of the interface Provides fault containment when something goes wrong it s easier to isolate Provides independence implementation can be modified without affecting the rest of the program Linked List Fourth Try in C class List struct Node Node int v Node n val v next n int val Node next Node head public List head 0 void push int v head new Node v head int pop int v head val head head next return v Linked List 4 List l l push 3 l push 2 int a l pop 2 int b l pop 3 Linked List 4 Advantages Implementation hidden other parts of the program can t see Node Push pop operations inextricably bound to the List class Constructor guarantees List objects always initialized correctly Disadvantages Implementation tied to integers Adding functionality appears to require copying and rewriting Managers vs Types List new list void push list List int int pop list List class List public List List void push int int pop Constructors destructors made explicit Operations implicitly bound to objects Inheritance How do you modify reused code Inheritance Say you want to use the linked list as a queue not just a stack Common problem have something almost but not quite what you need In C classes are closed can t be amended once defined Manager approach may or may not have this problem e g Java s packages can be extended Inheritance class List struct Node Node head public List void push int int pop class CountedList public List int count public CountedList count 0 void push int v List push v count int pop int v count return List pop v int count return count Inheritance class List struct Node Node head public List void push int int pop class CountedList public List public CountedList int count int c 0 Node t head whi c t t next return c Inheritance This doesn t work class List struct Node public private by default class CountedList public List int count int c 0 Node t head Inheritance and Encapsulation Elements of a class can be private visible only to members of the class protected visible to class members and derived classes public visible to everybody Encapsulation class Ex int private int protected int public int void foo pri1 Private by default pri2 pro pub pri1 1 pri2 2 pro 3 pub 4 Ex e e pri1 3 e pri2 4 e pro 2 e pub 1 Error private Error private Error protected OK Encapsulation class Ex int pri1 Private by default private int pri2 protected int pro public int pub void foo pri1 1 pri2 2 pro 3 pub 4 class Ex2 public Ex public void bar pri1 1 pri2 2 Error private pro 3 OK protected pub 2 OK Friends C has a friend mechanism for bending the rules class Ex friend class Foo int priv private class Foo public Foo Ex e e priv 1 OK class Bar public Bar Ex e e priv 0 Error priv is private Access Control over Parents class Parent public int x class PubChild public Parent PubChild puc puc x 1 OK class PrivChild private Parent PrivChild pvc pvc x 1 Error x is private Dynamic Method Dispatch How do you mix new code with old Dynamic Method Dispatch Say we had a routine that we wanted to use void print list List l while l empty printf d l pop The code would be the same if we passed it an object derived from the List class The only difference would be the functions called by l empty l pop Method Dispatch What happens when you write class Foo public void bar Foo f f bar The type of f is the class Foo Lookup member bar which is a method Generated code looks like void Foo bar Foo this Foo f Foo bar f Method Dispatch void print list List l while l empty printf d l pop becomes void print list List l while List empty l printf d List pop l Dynamic Method Dispatch If we had a derived class class List class Queue public List void print list List l while List empty l Queue empty l printf d List pop l Queue pop l Actual type of l object should determine this Virtual Functions The Trick Add a virtual table pointer to each object struct A B s Vtbl A s Vtbl int x B Foo virtual void Foo A Foo A Bar A Bar virtual void Bar B Baz a1 struct B A vptr int y x b1 virtual void Foo virtual void Baz vptr a2 x vptr A a1 a2 B b1 x y Virtual Functions struct A int x virtual void Foo virtual void Bar do something struct B A int y virtual void Foo virtual void Baz A a new B a Bar B s Vtbl B Foo A Bar B Baz a vptr x y Virtual Functions struct A int x virtual void Foo …
View Full Document
Unlocking...