IDP - kernelchina

the Set Theory in C++
Andrew Zhuang
[email protected]
Aug.7, 2008
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
1
Outline
 the Concept of a Class in C++ and a Set in the Set Theory
 Commonality of a Set vs. Public Members of a Class
 Empty Set vs. an Abstract Class
 Single Element Set vs. Singleton
 the Partition of a Set vs. Single Inheritance of a Class
 Multiple Inheritances vs. Intersection of Multiple Sets
 Modulization vs. Union of Sets
 Single Inheritance of an Abstract Class vs. Template Class
 Summary
 Reference
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
2
the Concepts of a class in C++ and a Set in the Set Theory
 The most fundamental notion of objected-oriented design and
programming is that the program is a model of some aspects of reality.
The classes in the program represent the fundamental concepts of the
application and in particular, the fundamental concepts of the ‘reality’
being modeled. [1]
- Bjarne Stroustrup
 A set represents a group of the objects with the same character.
 A set is usually described in one of the two following ways [4]:
• By enumeration, e.g. {1, 2, 3} denotes the set consisting of the
number 1,2,3 and nothing else;
• By a defining property or commonality (sentential functional) p(x).
Here it is important to define a universe U to which all the x have
to belong. We then write P = {x : x U and p(x) is true} or simply P =
{x: p(x)}.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
3
Commonality of a Set vs. Public Members of a Class
 A class is discerned or classified by its public members: public data
members and public member functions.
• Normally the data member is always declared as private one.
 The public (or visible) interfaces of a class represent the commonality
of a set.
 Equal Sets
• Two sets P and Q are equal, denoted by P = Q, if they contain the
same elements. [4]
 Equal Classes in C++
• There is no statement to judge whether the two arbitrary classes
can be treated as same or duplicate.
• It is meaningless to define the duplicate classes each of which
presents the same interfaces or characters to the general users.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
4
Commonality of a Set vs. Public Members of a Class

Normally any two arbitrary classes with no derivation relationship are different from each
other, for each of them has the public construction/destruction member function whose
name is same as the class name.

Considering the below two classes:
• class A and class B present the same public interfaces to the general users.
class A {
private:
static int a;
protected:
A();
public:
static int init();
static int draw();
};
class B {
private:
static int b;
protected:
B();
public:
static int init();
static int draw();
};
• From the above declarations of class A and class B, we can see it is unnecessary to
declare the duplicate classes.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
5
Commonality of a Set vs. Public Members of a Class

Access Control [1]

A member of a class can be private, protected, or public:
a) If it is private, its name can be used only by member functions and friends of the
class in which it is declared.
b) If it is protected, its name can be used only by member functions and friends of
the class in which it is declared and by member functions and friends of classes
derived from this class.
c) If it is public, its name can be used by any function.

This reflects the view that there are three kinds of functions accessing a class: functions
implementing the class (its friends and members), functions implementing a derived
class (the derived class’ friends and members), and other functions.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
6
Commonality of a Set vs. Public Members of a Class

Access to Base Classes [1]

Like a member, a base class can be declared private, protected, or public. For example:
class X: public B { /* …*/ };
class Y: protected B { /*…*/ };
class Z: private B { /*…*/ };

Access specifier for a base class controls the access to members of the base class and the conversion
of pointers and references from the derived class type to the base class type. Consider a class D
derived from a base class B:
a) If B is a private base, its public and protected members can be used only by member functions
and friends of D. Only friends and members of D can convert a D * to a B *.
b)
If B is a protected base, its public and protected members can be used only by member
functions and friends of D and by member functions and friends of classes derived from D.
Only friends and members of D and friends and members of classes derived from D can
convert a D * to a B *.
c)
If B is a public base, its public members can be used by any function. In addition, its protected
members can be used by members and friends of D and members and friends of classes
derived from D. Any function can convert a D * to a B *.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
7
Commonality of a Set vs. Public Members of a Class

The Visible Level of Member Functions in a Class to Other Guys than Himself
a)
Low: private members can only been seen by his friends.
b)
Medium: protected members can only been seen by his friends, his derived classes, and the friends
of his derived classes.
c)
High: public members can be seen by anyone.

Class D is derived from class B.

The visible level of the public and protected members in B can be maintained as before, or
downgraded to the lower.
a)
When B is a private base, both the visible levels of the public and protected members are
downgraded from high/medium to low as private ones.
b)
When B is a protected base, both the visible levels of the public and protected members are
downgraded from high/medium to medium as protected ones.
c)
When B is a public base, both the visible levels of the public and protected members are
maintained as before.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
8
Commonality of a Set vs. Public Members of a Class

B is private base
class B {
private:
int a;
protected:
int b;
int foo();
public:
int c;
int B();
int goo();
};
class D1: private B {
public:
D1():B() { }
int koo();
};
Copyright © 2004 Juniper Networks, Inc.

Just considering only the public and protected members of B, D1 can
be supposed as below.
class D1 {
… // something handling with B’s private members that can be seen or
// used by member functions and friends of B.
private:
int b;
int c;
int B();
int foo();
int goo();
public:
D1() { B(); }
int koo();
};
Class E1 is derived from D1 with public inheritance, or protected
inheritance or protected inheritance.
Proprietary and Confidential
www.juniper.net
9
Commonality of a Set vs. Public Members of a Class

B is private base
The public interfaces of D1 are presented differently to the different guys.
Someone can use or see the same public interfaces of D1 as those of B, like c, B(), and goo()
in this case, he thinks D1 is a kind of B; otherwise, he thinks D1 is not a kind of B.

The friends of B think D1 is not a kind of B.

The friends of D1 think D1 is a kind of B.

The classes derived from D1, like E1, and the friends of the classes derived from D1, like
the friends of E1, think D1 is not a kind of B.

The general users think D1 is a not kind of B.
Conclusion: Only the friends of D1 think D1 is a kind of B which is the private base of D1.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
10
Commonality of a Set vs. Public Members of a Class

B is protected base

class B {
private:
int a;
protected:
int b;
int foo();
public:
int c;
int B();
int goo();
Just considering only the public and protected members of B, D2 can
be supposed as below.
class D2 {
… // something handling with B’s private members that can be seen or
// used by member functions and friends of B.
protected:
int b;
int c;
int B();
int foo();
int goo();
public:
D1() { B(); }
int loo();
};
class D2: protected B {
public:
D2():B() { }
int loo();
};
Copyright © 2004 Juniper Networks, Inc.
};
Class E2 is derived from D2 with public inheritance, or protected
inheritance or protected inheritance.
Proprietary and Confidential
www.juniper.net
11
Commonality of a Set vs. Public Members of a Class
 B is protected base
 The friends of B think D2 is a not kind of B.
 The friends of D2, the classes derived from D2, like E2, and the friends
of the classes derived from D2, like the friends of E2, think D2 is a kind
of B.
 The general users think D2 is a not kind of B.
 Conclusion: Only the friends of D2, the classes from D2 and the friends of
the classes derived from D2 think D2 is a kind of B which is the protected
base of D2.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
12
Commonality of a Set vs. Public Members of a Class

B is public base

class B {
private:
int a;
protected:
int b;
int foo();
public:
int c;
int B();
int goo();
Just considering only the public and protected members of B, D2 can
be supposed as below.
class D3
{
… // something handling with B’s private members that can be seen or
// used by memnber functions and friends of B.
protected:
int b;
int foo();
public:
int c;
B();
D3() { B(); }
int goo();
int moo();
};
class D3: public B {
public:
D3():B() { }
int moo();
};
};
Class E3 is derived from D3 with public inheritance, or protected
inheritance or protected inheritance.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
13
Commonality of a Set vs. Public Members of a Class
 B is public base
 The friends of B think D3 is a kind of B.
 The friends of D3, the classes derived from D3, like E3, and the friends
of the classes derived from D2, like the friends of E2, think D3 is a kind
of B.
 The general users think D3 is a kind of B.
 Conclusion: Everyone think D3 is a kind of B which is the public base of D3.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
14
Commonality of a Set vs. Public Members of a Class
 B is public base
 The friends of B think D3 is a kind of B.
 The friends of D3, the classes derived from D3, like E3, and the friends
of the classes derived from D2, like the friends of E2, think D3 is a kind
of B.
 The general users think D3 is a kind of B.
 Conclusion: Everyone think D3 is a kind of B which is the public base of D3.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
15
Commonality of a Set vs. Public Members of a Class

An Example on Class Hierarchies
class A {
private:
int a1;
protected:
int a2;
int aoo_1();
public:
int a3;
int A();
int aoo_2();
};
class B : public A {
private:
int b1;
protected:
int b2;
int boo_1();
public:
int b3;
B():A() { };
int boo_2();
};
class C : private B {
private:
int c1;
protected:
int c2;
int coo_1();
public:
int c3;
C():B() { };
int coo_2();
};
class D : protected C {
private:
int d1;
protected:
int d2;
int doo_1();
public:
int d3;
D():C() { };
int doo_2();
};
class D : {
private:
…
int d1;
protected:
int c2;
int c3;
int d2;
int C():B() { };
int coo_1();
int coo_2();
int doo_1();
public:
int d3;
D():C() { };
int doo_2();
};

Everyone thinks B is a kind A.

Only the friends of C think 1) C is a kind of B and 2) C is a kind of A.

The friends of D, the derive classes of D, and the friends of the derived classes of D think that D is a kind C,
however D is not a kind of B or A.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
16
Commonality of a Set vs. Public Members of a Class
 Virtual Member Function
 A class that declares or inherits a virtual function is called a
polymorphic class.
 It provides a way to define the commonality across the base class
and its derived classes.
 Pure Virtual Member Function
 An abstract class is a class that is designed to be specifically used
as a base class. An abstract class contains at least one pure virtual
function. You declare a pure virtual function by using a pure
specifier (= 0) in the declaration of a virtual member function in
the class declaration.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
17
Empty Set vs. an Abstract Class

Empty Set


The set with no elements is called empty set and denoted by Ø [4].
Abstract Class

An abstract class contains at least one pure virtual function.

An abstract class is a class that is designed to be specifically used as a
base class.

You declare a pure virtual function by using a pure specifier (= 0) in the
declaration of a virtual member function in the class declaration.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
18
Single Element Set vs. Singleton

A single emelment set can have only one element.

Singleton [3]
class Singleton {
public:
static Singleton* Instance();
protected:
Singleton();
private:
static Singleton* _instance;
};

Conclusion: A single element corresponds to
the pattern of singleton.
Singleton* Singleton::_instance = 0;
Singleton* Singleton::Instance()
{
if (_instance == 0) {
_instance = new Singleton;
}
return _instance;
}
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
19
the Partition of a Set vs. Single Inheritance of a Class
class A0 { };
class A1: public A0 { };
class A2: public A1 { };

a0 is an instance of A0.

a1 is an instance of A1.

a2 is an instance of A2.
A0
A1
A2
a2
a1
a0 A0, a0 A1, a0 A2
a1 A0, a1 A1, a1 A2
a2 A0, a2 A1, a2 A2

a0
A0  
A2  A1  A0
Conclusion: A new derived class inherited from its base class means that a new
partition/subset is created inside its base set.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
20
the Partition of a Set vs. Single Inheritance of a Class

Split a base class into 2 derived classes with the opposite semantics
class A_0 { };
class A_1 : public A_0 {
public:
A_1
A_2
move();
};
class A_2 : public A_2 {
A_0
public:
unmove();
};
A_ 0  
A _ 0 A _ 1 A _ 2

If A_1 has N more public member functions compared to A_0, then the number
of all his sibling classes is (2**N-1).

For example, N = 2,
Copyright © 2004 Juniper Networks, Inc.
A _ 0  A _1  A _ 2  A _ 3  A _ 4
Proprietary and Confidential
www.juniper.net
21
the Partition of a Set vs. Single Inheritance of a Class

Two derive classes sharing the same semantic as their base one
class A_0 { };
class A_1 : public A_0 { };
class A_2 : public A_2 { };
A_0 = A_1 = A_2

Putting aside the public construction/destruction functions of A_1, we can think
A_1 is same as A_0, and same to A_2.

According to the above reason, it is meaningless to define A_1 and A_2 like
above.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
22
Multiple Inheritances vs. Intersection of Multiple Sets
class A { … };
class B { … };
A
class C: public A, public B { … };
C
c0
B
A  , B  
c 0  A, c 0  B, c 0  C
C  A B

c0 is an instance of C.

c0 is an instance of A while c0 is an instance of B as well.

C has multiple features/commonalities from A and B.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
23
Multiple Inheritances vs. Intersection of Multiple Sets

DAG (Directed Acyclic Graph) Inheritance from [2]
window
A
window_with_menu
window_with_border
B
D
C
window_with_menu_and_border
class window { … };
class window_with_menu: public virtual window { … };
class window_with_border: public virtual windw { … };
class window_with_menu_and_border:
public window_with_menu, public window_with_border { … };
A
B  A, C  A
B C  D
A: window
B: window_with_menu, C: window_with_border
D: window_with_menu_and_border
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
24
Multiple Inheritances vs. Intersection of Multiple Sets

Template Class
template <class U, class V> class A : public U, public V { … };
U
A
V
a0
U   ,V  
A  U V

It is a general representation of the intersection among multiple arbitrary
sets.

U or V represents a set of the arbitrary classes.

A represents a set of the sets each of which is a class derived from the
instance class of U and the instance class of V. And a0 is an instance or
element of A.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
25
Modulization vs.Union of Sets

When we combines the different classes into a file, or combines the different
classes scattered over the different files into a module, actually the file or the
module constitutes a union of the different sets.

For example, namespace in C++.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
26
Single Inheritance from an Abstract Class

Single Inheritance of a Class

Here is an example from [1].
class Shape {
public:
virtual void rotate(int) = 0;
virtual void draw() = 0;
virtual bool is_closed() = 0;
// …
};
class Circle : public Shape {
public:
void rotate(int) { }
void draw();
bool is_closed() { return true;}
Circle(Point p, int r);
private:
Point Center;
int radius;
};
class Polygon : public shape {
public:
bool is_closed() { return true;}
// … draw and rotate not
overriden…
};
Copyright © 2004 Juniper Networks, Inc.

We create the concrete classes having infinite instances
from an abstract class or an empty set.

无,名天地之始；有,名万物之母。
故常无欲，以观其妙；常有欲，以观其徼。此两者，
同出而异名，同谓之玄。玄之又玄，众妙之门。
(老子道德经：第一章)
Heaven and Earth began from the nameless (Tao),
but the multitudes of things around us were
created by names.
We desire to understand the world by giving names to
the things we see, but these things are only the
effects of something subtle. When we see beyond
the desire to use names, we can sense the
nameless cause of these effects. The cause and
the effects are aspects of the same, one thing.
They are both mysterious and profound.
At their most mysterious and profound point lies
the "Gate of the Great Truth". (Lao Tzu - Tao Te
Ching: Chapter 1)
Proprietary and Confidential
www.juniper.net
27
Single Inheritance from an Abstract Class

Template Class

Here is an example from [1].
template <class T> class Stack {
T* v;
int max_size;
int top;
public;
class Underflow { };
class Overflow() { };
Stack(int s); // constructor
~Stack(); // destructor
void push(T);
T pop();
};
typedef Stack<char> Stack_char;
typedef Stack<dog *> Stack_pdog;
typedef Stack<list<int>> Stack_li

Stack_pdog
Stack_char
Stack_x
Stack
Stack_li
Stack_y
Stack _ x  Stack _ y  
Stack  Stack _ char  Stack _ pdog  Stack _ li  ...Stack _ x  Stack _ y

Stack is the union of all the instance of this template:
Stack_char,Stack_pdog, and Stack_li and the other ones.

Stack_x is an arbitrary instance of Stack and same to Stack_y. And
there is no common elements between Stack_x and Stack_y.
With the template class, we do not need to write the duplicate codes for different kinds of types
managed by stacks.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
28
Summary

This article adds nothing new to C++ and the set theory, but builds a concept bridge
between them.

Here are the benefits from reading this article.

It gives the mapping relationship between the core ideas of objected-oriented
programming and the set theory so it is a great benefit to object-oriented
design, analysis and programming. Actually object-oriented programming
means the definitions and operations in the set theory.

Object-oriented programming should reflect the semantic in the real world,
not on the programming language level. That is to say that programming
should reflect the semantics of the reality.

It frees the C++ programmers from the heavy syntax of C++, for a programmer
should not be a salve of the complex syntax of any programming language.

It can speed up the learning curve for the C++ novices, and unfolds a new
scenario and thinking way to the advanced C++ programmers.
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
29
References

[1] Bjarne Stroustrup, 2000, The C++ Programming Language, special edition,
Addison-Wesley, Reading, Mass.

[2] Bjarne Stroustrup, 1994, The Design and Evolution of C++, Addison-Wesley,
Reading, Mass.

[3] Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, 1995, Design
Patterns: Elements of Reusable Object-Oriented Software, 1st ed, Addison-Wesley,
Reading, Mass.

[4] William Chen, 2008, Discrete Mathematics, Available at
http://www.maths.mq.edu.au/~wchen/lndmfolder/lndm.html
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
30
Thank You!
Copyright © 2004 Juniper Networks, Inc.
Proprietary and Confidential
www.juniper.net
31

Download Report