Object-Oriented TypesCOMS W4115Prof. Stephen A. EdwardsSpring 2002Columbia UniversityDepartment of Computer ScienceObject-Oriented Types“The important thing about a language is what programs itcan’t describe.”—Nicklas WirthInventor of PascalThree Attributes of OO Langauges1. EncapsulationHides data and procedures from other parts of theprogram.2. InheritanceCreates new components by refining existing ones.3. Dynamic Method DispatchThe ability for a newly-refined object to display newbehavior in an existing context.EncapsulationHow do you keep a large program partitioned?Running Example: Linked List Stacktypedef 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: ProblemsImplementation exposed:Malloc must be called explicitly every time node created.Code that creates a node needs to knowimplementation of node.Easy to forget part of the initialization of a node.Difficult to change implementation: much code toupdate.Global variable used for list: can’t have two.Advantage: fast.Linked List: Second TryPut 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 2Advantages:Easier-to-use: push operation free of implementationdetails.Changes lead to less code to update.Disadvantages:Other program code can still create and modify listnodes.Still using a global variable for the list.Difficult to reuse this code.Slower.Linked List: Third Trynode *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 3Advantages: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 listnodes: really want to hide the node type more.Implementation not completely hidden.“push” is probably too popular an identifier.Slow.EncapsulationA 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 modifiedwithout 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 4List l;l.push(3);l.push(2);int a = l.pop(); // 2int b = l.pop(); // 3Linked List 4Advantages:Implementation hidden: other parts of the program can’tsee Node.Push, pop operations inextricably bound to the Listclass.“Constructor” guarantees List objects always initializedcorrectly.Disadvantages:Implementation tied to integers.Adding functionality appears to require copying andrewriting.Managers vs. TypesList *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.InheritanceHow do you modify reused code?InheritanceSay you want to use the linked list as a queue, not just astack.Common problem: have something almost, but not quite,what you need.In C++, classes are closed: can’t be amended oncedefined.Manager approach may or may not have this problem.(e.g., Java’s packages can be extended)Inheritanceclass 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; }};Inheritanceclass 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; while (t) {++c; t=t->next; }return c;}};InheritanceThis doesn’t work:class List {struct Node {...}; // private: by default...public:};class CountedList : public List {int count(){ int c = 0; Node * t = head; ... }};Inheritance and EncapsulationElements of a class can beprivate visible only to members of the classprotected visible to class members and derived classespublic visible to everybodyEncapsulationclass Ex { int pri1; // Private by defaultprivate: int pri2;protected: int pro;public: int pub;void foo() { pri1=1; pri2=2; pro=3; pub=4; }};Ex e;e.pri1 = 3; // Error: privatee.pri2 = 4; // Error: privatee.pro = 2; // Error: protectede.pub = 1; // OKEncapsulationclass Ex { int pri1; // Private by defaultprivate: 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: privatepro=3; // OK: protectedpub=2; // OK}};FriendsC++ 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 Parentsclass Parent {public: int x;};class PubChild : public Parent {};PubChild puc;puc.x = 1; // OKclass PrivChild : private Parent {};PrivChild pvc;pvc.x = 1; // Error: x is privateDynamic Method DispatchHow do you mix new code with old?Dynamic Method DispatchSay 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 objectderived from the List class.The only difference would be the functions called byl->empty()l->pop()Method DispatchWhat happens when you writeclass 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 likevoid Foo_bar(Foo* this) { ... };Foo f;Foo_bar(&f);Method Dispatchvoid print_list(List *l) {while ( !( l->empty()) ) {printf("%d ", l->pop() );}}becomesvoid print_list(List *l) {while ( ! List_empty(l) ) ) {printf("%d ", List_pop(l) );}}Dynamic Method DispatchIf 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
View Full Document
Unlocking...