Lecture 14: Subtyping, Inheritance, and Polymorphism (PDF)

23. Subtyping, Inheritance and Polymorphism The following slides of this chapter are not relevant for the exam Expression Trees, Separation of Concerns and Modularisation, Type Hierarchies, Virtual Functions, Dynamic Binding, Code Reuse, Concepts of Object-Oriented Programming...

23. Subtyping, Inheritance and Polymorphism The following slides of this chapter are not relevant for the exam Expression Trees, Separation of Concerns and Modularisation, Type Hierarchies, Virtual Functions, Dynamic Binding, Code Reuse, Concepts of Object-Oriented Programming 620 Quick Presentation: Expression Trees Goal: Represent arithmetic expressions, e.g. 2 + 3 * 2 Arithmetic expressions form a tree structure + 2 ∗ 3 2 q literals (e.g. 2), binary Expression trees comprise different nodes: operators (e.g. +), unary operators (e.g. ), function applications (e.g. cos ), etc. 621 One single Node Type Expression trees implemented via a single node type: Value left operand struct tnode { operator right operand char op; // Operator ('=' for literals) + ⋆ ⋆: unused double val; // Literal's value tnode* left; // Left child (or nullptr) tnode* right; //... = 2 ⋆ ⋆ ∗ ⋆... }; Observation: tnode is the “sum” of all required nodes (constants, addition,... ) ⇒ memory wastage, inelegant... 622 Disadvantages...and every function must “dissect” this “sum”, e.g.: double eval(const tnode* n) { if (n->op == '=') return n->val; // n is a constant double l = 0; if (n->left) l = eval(n->left); // n is not a unary operator double r = eval(n->right); switch(n->op) { case '+': return l+r; // n is an addition node case '*': return l*r; //...... ⇒ Complex, and therefore error-prone 623 Disadvantages struct tnode { double eval(const tnode* n) { char op; if (n->op == '=') return n->val; double val; double l = 0; tnode* left; if (n->left) l = eval(n->left); tnode* right; double r = eval(n->right);... switch(n->op) { }; case '+': return l+r; case '*': return l*r;... This code isn’t modular – we’ll change that today! 624 New Concepts Today 1. Subtyping Type hierarchy: Exp represents general Exp expressions, Literal etc. are concrete expression Every Literal etc. also is an Exp Literal Addition Times (subtype relation) That’s why a Literal etc. can be used everywhere, where an Exp is expected: Exp* e = new Literal(132); 625 New Concepts Today 2. Polymorphism and Dynamic Dispatch A variable of static type Exp can “host” expressions of different dynamic types: Exp* e = new Literal(2); // e is the literal 2 e = new Addition(e, e); // e is the addition 2 + 2 Executed are the member functions of the dynamic type: Exp* e = new Literal(2); std::cout eval(); // 2 e = new Addition(e, e); std::cout eval(); // 4 626  New Concepts Today 3. Inheritance Certain functionality is shared among Exp type hierarchy members E.g. computing the size (nesting depth) of binary expressions (Addition, Times): Literal Addition Times 1 + size(left operand) + size(right operand) ⇒ Implement functionality once, and let Exp subtypes inherit it Literal BinExp Addition Times 627 Advantages Subtyping, inheritance and dynamic Exp binding enable modularisation through spezialisation Literal BinExp Inheritance enables sharing common code across modules Addition Times ⇒ avoid code duplication Exp* e = new Literal(2); std::cout eval(); e = new Addition(e, e); std::cout eval(); 628 Syntax and Terminology Exp struct Exp { BinExp Note: Today, we focus on the new... concepts (subtyping,... ) and ig- } Times nore the orthogonal aspect of en- capsulation (class, private vs. struct BinExp : public Exp {... public member variables) } struct Times : public BinExp {... } 629 Syntax and Terminology Exp struct Exp { BinExp BinExp is a subclass1 of Exp... Exp is the superclass2 of BinExp } Times BinExp inherits from Exp struct BinExp : public Exp { BinExp publicly inherits from Exp... (public), that’s why BinExp is a } subtype of Exp struct Times : public BinExp { Analogously: Times and BinExp... Subtype relation is transitive: Times is } also a subtype of Exp 1 derived class, child class 2 base class, parent class 630 Abstract Class Exp and Concrete Class Literal struct Exp {... that makes Exp an abstract class virtual int size() const = 0; virtual double eval() const = 0; }; Enforces implementation by de- Activates dynamic dispatch rived classes... struct Literal : public Exp { Literal inherits from Exp... double val; Literal(double v); int size() const;... but is otherwise just a regular class double eval() const; }; 631 Literal: Implementation Literal::Literal(double v): val(v) {} int Literal::size() const { return 1; } double Literal::eval() const { return this->val; } 632 Subtyping: A Literal is an Expression A pointer to a subtype can be used everywhere, where a pointer to a supertype is required: Literal* lit = new Literal(5); Exp* e = lit; // OK: Literal is a subtype of Exp But not vice versa: Exp* e =... Literal* lit = e; // ERROR: Exp is not a subtype of Literal 633 Polymorphie: a Literal Behaves Like a Literal struct Exp { virtual member function: the dynamic... (here: Literal) type determines the virtual double eval(); member function to be executed }; ⇒ dynamic binding Without Virtual the static type (hier: double Literal::eval() { Exp) determines which function is return this->val; executed } We won’t go into further details Exp* e = new Literal(3); std::cout eval(); // 3 634 Further Expressions: Addition and Times struct Addition : public Exp { struct Times : public Exp { Exp* left; // left operand Exp* left; // left operand Exp* right; // right operand Exp* right; // right operand...... }; }; int Addition::size() const { int Times::size() const { return 1 + left->size() return 1 + left->size() + right->size(); + right->size(); } } Separation of concerns Code duplication 635 Extracting Commonalities... : BinExp struct BinExp : public Exp { Exp* left; Exp* right; BinExp(Exp* l, Exp* r); int size() const; }; BinExp::BinExp(Exp* l, Exp* r): left(l), right(r) {} int BinExp::size() const { return 1 + this->left->size() + this->right->size(); } Note: BinExp does not implement eval and is therefore also an abstract class, just like Exp 636... Inheriting Commonalities: Addition Addition inherits member vari- struct Addition : public BinExp { ables (left, right) and functions (size) from BinExp Addition(Exp* l, Exp* r); double eval() const; }; Addition::Addition(Exp* l, Exp* r): BinExp(l, r) {} double Addition::eval() const { Calling the super constructor (con- return structor of BinExp) initialises the member variables left and right this->left->eval() + this->right->eval(); } 637... Inheriting Commonalities: Times struct Times : public BinExp { Times(Exp* l, Exp* r); double eval() const; }; Times::Times(Exp* l, Exp* r): BinExp(l, r) {} double Times::eval() const { return this->left->eval() * this->right->eval(); } Observation: Additon::eval() and Times::eval() are very similar and could also be unified. However, this would require the concept of functional programming, which is outside the scope of this course. 638 Further Expressions and Operations Further expressions, as classes derived from Exp, are possible, e.g. −, /, √ , cos, log A former bonus exercise (included in today’s lecture examples on Code Expert) illustrates possibilities: variables, trigonometric functions, parsing, pretty-printing, numeric simplifications, symbolic derivations,... 639 Mission: Monolithic → Modular ✓ struct Literal : public Exp { struct tnode { double val; char op;... double val; double eval() const { tnode* left; return val; tnode* right; }... }; } struct Addition : public Exp { double eval(const tnode* n) {... if (n->op == '=') return n->val; double eval() const { double l = 0; return left->eval() + right->eval(); if (n->left != 0) l = eval(n->left); } double r = eval(n->right); }; switch(n->op) { case '+': return l + r; struct Times : public Exp { case '*': return l * r;... case '-': return l - r; double eval() const { case '/': return l / r; return left->eval() * right->eval(); default: } // unknown operator } assert (false); } struct Cos : public Exp { } +... double eval() const { int size (const tnode* n) const {... } return std::cos(argument->eval()); }... } 640 And there is so much more... Not shown/discussed: Private inheritance (class B : public A) Subtyping and polymorphism without pointers Non-virtuell member functions and static dispatch (virtual double eval()) Overriding inherited member functions and invoking overridden implementations Multiple inheritance... Good news: today’s chapter (23. Subtyping, Inheritance and Polymorphism) is not exam relevant 641 Object-Oriented Programming In the last 3rd of the course, several concepts of object-oriented programming were introduced, that are briefly summarised on the upcoming slides. Encapsulation (weeks 10-13): Hide the implementation details of types (private section) from users Definition of an interface (public area) for accessing values and functionality in a controlled way Enables ensuring invariants, and the modification of implementations without affecting user code 642 Object-Oriented Programming Subtyping (week 14): Type hierarchies, with super- and subtypes, can be created to model relationships between more abstract and more specialised entities A subtype supports at least the functionality that its supertype supports – typically more, though, i.e. a subtype extends the interface (public section) of its supertype That’s why supertypes can be used anywhere, where subtypes are required...... and functions that can operate on more abstract type (supertypes) can also operate on more specialised types (subtypes) The streams introduced in week 7 form such a type hierarchy: ostream is the abstract supertyp, ofstream etc. are specialised subtypes 643 Object-Oriented Programming Polymorphism and dynamic binding (week 14): A pointer of static typ T1 can, at runtime, point to objects of (dynamic) type T2 , if T2 is a subtype of T1 When a virtual member function is invoked from such a pointer, the dynamic type determines which function is invoked I.e.: despite having the same static type, a different behaviour can be observed when accessing the common interface (member functions) of such pointers In combination with subtyping, this enables adding further concrete types (streams, expressions,... ) to an existing system, without having to modify the latter 644 Object-Oriented Programming Inheritance (week 14): Derived classes inherit the functionality, i.e. the implementation of member functions, of their parent classes This enables sharing common code and thereby avoids code duplication An inherited implementation can be overridden, which allows derived classes to behave differently than their parent classes (not shown in this course) 645 24. Conclusion 646 Purpose and Format Name the most important key words to each chapter. Checklist: “does every notion make some sense for me?” M motivating example for each chapter C concepts that do not depend from the implementation (language) L language (C++): all that depends on the chosen language E examples from the lectures 647 Kapitelüberblick 1. Introduction 2. First C++ Program 3. Integers 4. Booleans 5./6. Control Statements 7./8. Floating Point Numbers 9./10. Functions 11. Vectors 12. Reference Types 13. Texts and Strings 14./15. Recursion 16./17. Custom Data Types 18. Containers, Iterators and Algorithms 19.-22. Dynamic Memory and Pointers 23. Subtyping, Polymorphism and Inheritance 648 1. Introduction M Euclidean algorithm C algorithm, Turing machine, programming languages, compilation, syntax and semantics values and effects, fundamental types, literals, variables L include directive #include main function int main(){...} comments, layout // Kommentar types, variables, L-value a , R-value a+b expression statement b=b*b; , declaration statement int a;, return statement return 0; 649 2. First C++ Program M Simple computation of a8 C Elements of the programming language L Comments and layout Include directive main function Values, effects Types, functionality Literals,Variables, Constants Identifiers, names Expressions L- and R-values Operators Command E First program 650 3. Integers M Celsius to Fahrenheit C associativity and precedence, arity expression trees, evaluation order arithmetic operators binary representation, hexadecimal numbers signed numbers, twos complement L arithmetic operators 9 * celsius / 5 + 32 increment / decrement expr++ arithmetic assignment expr1 += expr2 conversion int ↔ unsigned int E Celsius to Fahrenheit, equivalent resistance 651 4. Booleans C Boolean functions, completeness DeMorgan rules L the type bool logical operators a && !b relational operators x < y precedences 7 + x < y && y != 3 * z short circuit evaluation x != 0 && z / x > y the assert-statement, #include E Div-Mod identity. 652 5./6. Control Statements M linear control flow vs. interesting programs C selection statements, iteration statements (avoiding) endless loops, halting problem Visibility and scopes, automatic memory equivalence of iteration statement L if statements if (a % 2 == 0) {..} for statements for (unsigned int i = 1; i 1) {...} blocks and branches if (a < 0) continue; Switch statement switch(grade) {case 6: } E sum computation (Gauss), prime number tests, Collatz sequence, Fibonacci numbers, calculator, output grades 653 7./8. Floating Point Numbers M correct computation: Celsius / Fahrenheit C fixpoint vs. floating point holes in the value range compute using floating point numbers floating point number systems, normalisation, IEEE standard 754 guidelines for computing with floating point numbers L types float, double floating point literals 1.23e-7f E Celsius/Fahrenheit, Harmonic Numbers 654 9./10. Functions M Computation of Powers C Encapsulation of Functionality functions, formal arguments, arguments scope, forward declarations procedural programming, modularization, separate compilation Stepwise Refinement L declaration and definition of functions double pow(double b, int e){... } function call pow (2.0, -2) the type void E powers, perfect numbers, minimum, calendar 655 11. Vectors M Iterate over data: sieve of erathosthenes C vectors, memory layout, random access (missing) bound checks vectors vectors of vectors typedefs and auto L vector types std::vector a {4,3,5,2,1}; E sieve of Erathosthenes Lower triangle sum 656 12. Reference Types M Swap C value- / reference- semantics, pass by value, pass by reference, return by reference lifetime of objects / temporary objects constants L reference type int& a call by reference, return by reference int& increment (int& i) const guideline, const references, reference guideline E swap, increment 657 13. Characters and Strings M Caesar cipher C characters: ASCII, UTF8, texts, strings L characters and texts, the type char char c = ’a’;, Konversion nach int E Caesar-code 658 14./15. Recursion M recursive math. functions, the n-Queen problem, a command line calculator C recursion call stack, memory of recursion correctness, termination, recursion vs. iteration Decrease and Conquer vs. Divide and Conquer E factorial, GCD, sudoku-solver, command line calculator, vector sum 659 16./17. Custom Data Types M build your own rational number C heterogeneous data types function and operator overloading Encapsulation of data, Construction, Member Functions L struct definition struct rational {int n; int d;}; member access result.n = a.n * b.d + a.d * b.n; initialization and assignment, function overloading pow(2) vs. pow(3,3);, operator overloading classes class rational {... }; access control public: / private: member functions int rational::denominator () const The implicit argument of the member functions E rational numbers, complex numbers 660 18. Containers, Iterators and Algorithms M vectors are containers C iteration with pointers containers and iterators algorithms L Iterators std::vector::iterator Algorithms of the standard library std::fill (a, a+5, 1); implement an iterator iterators and const E output a vector, a set 661 19. Dynamic Memory and Pointers M Our own data structure C linked list, allocation, deallocation, dynamic data type L The new statement pointer int* x;, Null-pointer nullptr. address and derference operator int *ip = &i; int j = *ip; pointer and const const int *a; E linked list, stack 662 20.-22. Dynamic Data Structures and Memory Management M Stack Linked List Vector C Guideline ”dynamic memory“ Pointer sharing Dynamic Datatype L new and delete Destructor stack::~stack() Copy-Constructor stack::stack(const stack& s) Assignment operator stack& stack::operator=(const stack& s) Rule of Three E Stack, linked list, vector 663 23. Subtyping, Polymorphism and Inheritance M extend and generalize expression trees C Subtyping polymorphism and dynamic binding Inheritance L base class struct Exp{} derived class struct BinExp: public Exp{} abstract class struct Exp{virtual int size() const = 0...} polymorphie virtual double eval() E expression node and extensions 664 The End End of the Course 665