Embed or link this publication
Description
Short and helpful tutorials for the newbies in programming
Popular Pages
p. 1
what is object-oriented programming 1991 revised version bjarne stroustrup at&t bell laboratories murray hill new jersey 07974 abstract object-oriented programming and data abstraction have become very common terms unfortunately few people agree on what they mean i will offer informal definitions that appear to make sense in the context of languages like ada c modula2 simula and smalltalk the general idea is to equate support for data abstraction with the ability to define and use new types and equate support for object-oriented programming with the ability to express type hierarchies features necessary to support these programming styles in a general purpose programming language will be discussed the presentation centers around c but is not limited to facilities provided by that language 1 introduction not all programming languages can be object oriented yet claims have been made to the effect that apl ada clu c loops and smalltalk are object-oriented programming languages i have heard discussions of object-oriented design in c pascal modula-2 and chill could there somewhere be proponents of object-oriented fortran and cobol programming i think there must be object-oriented has in many circles become a high-tech synonym for good and when you examine discussions in the trade press you can find arguments that appear to boil down to syllogisms like ada is good object oriented is good ada is object oriented this paper presents one view of what object oriented ought to mean in the context of a general purpose programming language §2 distinguishes object-oriented programming and data abstraction from each other and from other styles of programming and presents the mechanisms that are essential for supporting the various styles of programming §3 presents features needed to make data abstraction effective §4 discusses facilities needed to support object-oriented programming §5 presents some limits imposed on data abstraction and object-oriented programming by traditional hardware architectures and operating systems examples will be presented in c the reason for this is partly to introduce c and partly because c is one of the few languages that supports both data abstraction and object-oriented programming in addition to traditional programming techniques issues of concurrency and of hardware support for specific higherlevel language constructs are ignored in this paper.[close]
p. 2
-2 2 programming paradigms object-oriented programming is a technique for programming a paradigm for writing good programs for a set of problems if the term object-oriented programming language means anything it must mean a programming language that provides mechanisms that support the object-oriented style of programming well there is an important distinction here a language is said to support a style of programming if it provides facilities that makes it convenient reasonably easy safe and efficient to use that style a language does not support a technique if it takes exceptional effort or exceptional skill to write such programs it merely enables the technique to be used for example you can write structured programs in fortran write type-secure programs in c and use data abstraction in modula-2 but it is unnecessarily hard to do because these languages do not support those techniques support for a paradigm comes not only in the obvious form of language facilities that allow direct use of the paradigm but also in the more subtle form of compile-time and/or run-time checks against unintentional deviation from the paradigm type checking is the most obvious example of this ambiguity detection and run-time checks can be used to extend linguistic support for paradigms extra-linguistic facilities such as standard libraries and programming environments can also provide significant support for paradigms a language is not necessarily better than another because it possesses a feature the other does not there are many example to the contrary the important issue is not so much what features a language possesses but that the features it does possess are sufficient to support the desired programming styles in the desired application areas [1 all features must be cleanly and elegantly integrated into the language [2 it must be possible to use features in combination to achieve solutions that would otherwise have required extra separate features [3 there should be as few spurious and special purpose features as possible [4 a feature should be such that its implementation does not impose significant overheads on programs that do not require it [5 a user need only know about the subset of the language explicitly used to write a program the last two principles can be summarized as what you don t know won t hurt you if there are any doubts about the usefulness of a feature it is better left out it is much easier to add a feature to a language than to remove or modify one that has found its way into the compilers or the literature i will now present some programming styles and the key language mechanisms necessary for supporting them the presentation of language features is not intended to be exhaustive 2.1 procedural programming the original and probably still the most commonly used programming paradigm is decide which procedures you want use the best algorithms you can find the focus is on the design of the processing the algorithm needed to perform the desired computation languages support this paradigm by facilities for passing arguments to functions and returning values from functions the literature related to this way of thinking is filled with discussion of ways of passing arguments ways of distinguishing different kinds of arguments different kinds of functions procedures routines macros etc fortran is the original procedural language algol60 algol68 c and pascal are later inventions in the same tradition a typical example of good style is a square root function it neatly produces a result given an argument to do this it performs a well understood mathematical computation double sqrtdouble arg the code for calculating a square root }[close]
p. 3
-3 void some_function double root2 sqrt2 from a program organization point of view functions are used to create order in a maze of algorithms 2.2 data hiding over the years the emphasis in the design of programs has shifted away from the design of procedures towards the organization of data among other things this reflects an increase in the program size a set of related procedures with the data they manipulate is often called a module the programming paradigm becomes decide which modules you want partition the program so that data is hidden in modules this paradigm is also known as the data hiding principle where there is no grouping of procedures with related data the procedural programming style suffices in particular the techniques for designing good procedures are now applied for each procedure in a module the most common example is a definition of a stack module the main problems that have to be solved for a good solution are [1 provide a user interface for the stack for example functions push and pop [2 ensure that the representation of the stack for example a vector of elements can only be accessed through this user interface [3 ensure that the stack is initialized before its first use here is a plausible external interface for a stack module declaration of the interface of module stack of characters char pop void pushchar const stack_size 100 assuming that this interface is found in a file called stack.h the internals can be defined like this #include stack.h static char v[stack_size static char p v static means local to this file/module the stack is initially empty char pop check for underflow and pop void pushchar c check for overflow and push it would be quite feasible to change the representation of this stack to a linked list a user does not have access to the representation anyway since v and p were declared static that is local to the file/module in which they were declared such a stack can be used like this:[close]
p. 4
-4 #include stack.h void some_function char c poppush c if c c error impossible pascal as originally defined doesn t provide any satisfactory facilities for such grouping the only mechanism for hiding a name from the rest of the program is to make it local to a procedure this leads to strange procedure nestings and over-reliance on global data c fares somewhat better as shown in the example above you can define a module by grouping related function and data definitions together in a single source file the programmer can then control which names are seen by the rest of the program a name can be seen by the rest of the program unless it has been declared static consequently in c you can achieve a degree of modularity however there is no generally accepted paradigm for using this facility and the technique of relying on static declarations is rather low level one of pascal s successors modula-2 goes a bit further it formalizes the concept of a module making it a fundamental language construct with well defined module declarations explicit control of the scopes of names import/export a module initialization mechanism and a set of generally known and accepted styles of usage the differences between c and modula-2 in this area can be summarized by saying that c only enables the decomposition of a program into modules while modula-2 supports that technique 2.3 data abstraction programming with modules leads to the centralization of all data of a type under the control of a type manager module if one wanted two stacks one would define a stack manager module with an interface like this class stack_id stack_id is a type no details about stacks or stack_ids are known here stack_id create_stackint size make a stack and return its identifier destroy_stackstack_id call when stack is no longer needed void pushstack_id char char popstack_id this is certainly a great improvement over the traditional unstructured mess but types implemented this way are clearly very different from the built-in types in a language each type manager module must define a separate mechanism for creating variables of its type there is no established norm for assigning object identifiers a variable of such a type has no name known to the compiler or programming environment nor do such variables do not obey the usual scope rules or argument passing rules a type created through a module mechanism is in most important aspects different from a built-in type and enjoys support inferior to the support provided for built-in types for example void f stack_id s1 stack_id s2 s1 create_stack200 oops forgot to create s2 char c1 pops1,pushs1 a if c1 c error impossible[close]
p. 5
-5 char c2 pops2,pushs2 a if c2 c error impossible destroys2 oops forgot to destroy s1 in other words the module concept that supports the data hiding paradigm enables this style of programming but it does not support it languages such as ada clu and c attack this problem by allowing a user to define types that behave in nearly the same way as built-in types such a type is often called an abstract data type the programming paradigm becomes decide which types you want provide a full set of operations for each type where there is no need for more that one object of a type the data hiding programming style using modules suffices arithmetic types such as rational and complex numbers are common examples of userdefined types class complex double re im public complexdouble r double i re=r im=i complexdouble r re=r im=0 float complex conversion friend friend friend friend friend complex complex complex complex complex operator complex complex operator complex complex operator complex operator complex complex operator complex complex binary minus unary minus the declaration of class that is user-defined type complex specifies the representation of a complex number and the set of operations on a complex number the representation is private that is re and im are accessible only to the functions specified in the declaration of class complex such functions can be defined like this complex operator complex a1 complex a2 return complexa1.re+a2.re,a1.im+a2.im and used like this complex a 2.3 complex b 1/a complex c a+bcomplex1,2.3 c a/b 2 most but not all modules are better expressed as user defined types for concepts where the module representation is desirable even when a proper facility for defining types is available the programmer can declare a type and only a single object of that type alternatively a language might provide a module i prefer the term user-defined type those types are not abstract they are as real as int and float doug mcilroy an alternative definition of abstract data types would require a mathematical abstract specification of all types both built-in and userdefined what is referred to as types in this paper would given such a specification be concrete specifications of such truly abstract entities.[close]
p. 6
-6 concept in addition to and distinct from the class concept 2.4 problems with data abstraction an abstract data type defines a sort of black box once it has been defined it does not really interact with the rest of the program there is no way of adapting it to new uses except by modifying its definition this can lead to severe inflexibility consider defining a type shape for use in a graphics system assume for the moment that the system has to support circles triangles and squares assume also that you have some classes class point class color you might define a shape like this enum kind circle triangle square class shape point center color col kind k representation of shape public point where return center void movepoint to center to draw void draw void rotateint more operations the type field k is necessary to allow operations such as draw and rotate to determine what kind of shape they are dealing with in a pascal-like language one might use a variant record with tag k the function draw might be defined like this void shape draw switch k case circle draw a circle break case triangle draw a triangle break case square draw a square this is a mess functions such as draw must know about all the kinds of shapes there are therefore the code for any such function grows each time a new shape is added to the system if you define a new shape every operation on a shape must be examined and possibly modified you are not able to add a new shape to a system unless you have access to the source code for every operation since adding a new shape involves touching the code of every important operation on shapes it requires great skill and potentially introduces bugs into the code handling other older shapes the choice of representation of particular shapes can get severely cramped by the requirement that at least some of their representation must fit into the typically fixed sized framework presented by the definition of the general type shape 2.5 object-oriented programming the problem is that there is no distinction between the general properties of any shape a shape has a color it can be drawn etc and the properties of a specific shape a circle is a shape that has a radius is drawn by a circle-drawing function etc expressing this distinction and taking advantage of it defines object-oriented programming a language with constructs that allows this distinction to be expressed and[close]
p. 7
-7 used supports object-oriented programming other languages don t the simula inheritance mechanism provides a solution first specify a class that defines the general properties of all shapes class shape point center color col public point where return center void movepoint to center to draw virtual void draw virtual void rotateint the functions for which the calling interface can be defined but where the implementation cannot be defined except for a specific shape have been marked virtual the simula and c term for may be re-defined later in a class derived from this one given this definition we can write general functions manipulating shapes void rotate_allshape v int size int angle rotate all members of vector v of size size angle degrees for int i 0 i size i v[i rotateangle to define a particular shape we must say that it is a shape and specify its particular properties including the virtual functions class circle public shape int radius public void draw void rotateint yes the null function in c class circle is said to be derived from class shape and class shape is said to be a base of class circle an alternative terminology calls circle and shape subclass and superclass respectively the programming paradigm is decide which classes you want provide a full set of operations for each class make commonality explicit by using inheritance where there is no such commonality data abstraction suffices the amount of commonality between types that can be exploited by using inheritance and virtual functions is the litmus test of the applicability of object-oriented programming to an application area in some areas such as interactive graphics there is clearly enormous scope for object-oriented programming for other areas such as classical arithmetic types and computations based on them there appears to be hardly any scope for more than data abstraction and the facilities needed for the support of object-oriented programming seem unnecessary finding commonality among types in a system is not a trivial process the amount of commonality to be exploited is affected by the way the system is designed when designing a system commonality must be actively sought both by designing classes specifically as building blocks for other types and by examining classes to see if they exhibit similarities that can be exploited in a common base class however more advanced mathematics may benefit from the use of inheritance fields are specializations of rings vector spaces a special case of modules.[close]
p. 8
-8 for attempts to explain what object-oriented programming is without recourse to specific programming language constructs see nygaard[13 and kerr[9 for a case study in object-oriented programming see cargill[4 3 support for data abstraction the basic support for programming with data abstraction consists of facilities for defining a set of operations for a type and for restricting the access to objects of the type to that set of operations once that is done however the programmer soon finds that language refinements are needed for convenient definition and use of the new types operator overloading is a good example of this 3.1 initialization and cleanup when the representation of a type is hidden some mechanism must be provided for a user to initialize variables of that type a simple solution is to require a user to call some function to initialize a variable before using it for example class vector int sz int v public void initint size vector v don t use v here v.init10 use v here call init to initialize sz and v before the first use of a vector this is error prone and inelegant a better solution is to allow the designer of a type to provide a distinguished function to do the initialization given such a function allocation and initialization of a variable becomes a single operation often called instantiation instead of two separate operations such an initialization function is often called a constructor in cases where construction of objects of a type is non-trivial one often needs a complementary operation to clean up objects after their last use in c such a cleanup function is called a destructor consider a vector type class vector int sz int v public vectorint ~vector int operator int index number of elements pointer to integers constructor destructor subscript operator the vector constructor can be defined to allocate space like this vector vectorint s if s 0 error bad vector size sz s v new int[s allocate an array of s integers the vector destructor frees the storage used vector vector delete v deallocate the memory pointed to by v c does not support garbage collection this is compensated for however by enabling a type to maintain[close]
p. 9
-9 its own storage management without requiring intervention by a user this is a common use for the constructor/destructor mechanism but many uses of this mechanism are unrelated to storage management 3.2 assignment and initialization controlling construction and destruction of objects is sufficient for many types but not for all it can also be necessary to control all copy operations consider class vector vector v1100 vector v2 v1 v1 v2 make a new vector v2 initialized to v1 assign v2 to v1 it must be possible to define the meaning of the initialization of v2 and the assignment to v1 alternatively it should be possible to prohibit such copy operations preferably both alternatives should be available for example class vector int v int sz public void operator vector vectorvector assignment initialization specifies that user-defined operations should be used to interpret vector assignment and initialization assignment might be defined like this vector operator vector a check size and copy elements if sz a.sz error bad vector size for for int i 0 i[close]
p. 10
10 3.3 parameterized types why would you want to define a vector of integers anyway a user typically needs a vector of elements of some type unknown to the writer of the vector type consequently the vector type ought to be expressed in such a way that it takes the element type as an argument class vector[close]
p. 11
11 passed to the subscript operator the designer of the vector class should be able to provide a default behavior for this for example class vector except vector_range define an exception called vector_range and specify default code for handling it error global vector range error exit99 instead of calling an error function vector operator can invoke the exception handling code raise the exception int vector operator int i if 0[close]
p. 12
12 3.5 coercions user-defined coercions such as the one from floating point numbers to complex numbers implied by the constructor complexdouble have proven unexpectedly useful in c such coercions can be applied explicitly or the programmer can rely on the compiler to add them implicitly where necessary and unambiguous complex a complex1 complex b 1 a b+complex2 a b+2 implicit 1 complex1 implicit 2 complex2 coercions were introduced into c because mixed mode arithmetic is the norm in languages for numerical work and because most user-defined types used for calculation for example matrices character strings and machine addresses have natural mappings to and/or from other types one use of coercions has proven especially useful from a program organization point of view complex a 2 complex b a+2 b 2+a interpreted as operator a,complex2 interpreted as operator complex2 a only one function is needed to interpret operations and the two operands are handled identically by the type system furthermore class complex is written without any need to modify the concept of integers to enable the smooth and natural integration of the two concepts this is in contrast to a pure objectoriented system where the operations would be interpreted like this a+2 2+a a.operator 2 2.operator a making it necessary to modify class integer to make 2+a legal modifying existing code should be avoided as far as possible when adding new facilities to a system typically object-oriented programming offers superior facilities for adding to a system without modifying existing code in this case however data abstraction facilities provide a better solution 3.6 iterators it has been claimed that a language supporting data abstraction must provide a way of defining control structures[11 in particular a mechanism that allows a user to define a loop over the elements of some type containing elements is often needed this must be achieved without forcing a user to depend on details of the implementation of the user-defined type given a sufficiently powerful mechanism for defining new types and the ability to overload operators this can be handled without a separate mechanism for defining control structures for a vector defining an iterator is not necessary since an ordering is available to a user through the indices i ll define one anyway to demonstrate the technique there are several possible styles of iterators my favorite relies on overloading the function application operator class vector_iterator vector v int i public vector_iteratorvector r i 0 v r int operator return i[close]
p. 13
13 vector vsz vector_iterator nextv int i while i=next printi more than one iterator can be active for a single object at one time and a type may have several different iterator types defined for it so that different kinds of iteration may be performed an iterator is a rather simple control structure more general mechanisms can also be defined for example the c standard library provides a co-routine class[15 for many container types such as vector one can avoid introducing a separate iterator type by defining an iteration mechanism as part of the type itself a vector might be defined to have a current element class vector int v int sz int current public int next return current sz v[current 0 int prev return 0 current v[current 0 then the iteration can be performed like this vector vsz int i while i=v.next printi this solution is not as general as the iterator solution but avoids overhead in the important special case where only one kind of iteration is needed and where only one iteration at a time is needed for a vector if necessary a more general solution can be applied in addition to this simple one note that the simple solution requires more foresight from the designer of the container class than the iterator solution does the iterator-type technique can also be used to define iterators that can be bound to several different container types thus providing a mechanism for iterating over different container types with a single iterator type 3.7 implementation issues the support needed for data abstraction is primarily provided in the form of language features implemented by a compiler however parameterized types are best implemented with support from a linker with some knowledge of the language semantics and exception handling requires support from the run-time environment both can be implemented to meet the strictest criteria for both compile time speed and efficiency without compromising generality or programmer convenience as the power to define types increases programs to a larger degree depend on types from libraries and not just those described in the language manual this naturally puts greater demands on facilities to express what is inserted into or retrieved from a library facilities for finding out what a library contains facilities for determining what parts of a library are actually used by a program etc for a compiled language facilities for calculating the minimal compilation necessary after a change become important it is essential that the linker/loader is capable of bringing a program into memory for execution without also bringing in large amounts of related but unused code in particular a library/linker/loader system that brings the code for every operation on a type into core just because the programmer used one or two operations on the type is worse than useless 4 support for object-oriented programming the basic support a programmer needs to write object-oriented programs consists of a class mechanism with inheritance and a mechanism that allows calls of member functions to depend on the actual type of an object in cases where the actual type is unknown at compile time the design of the member function calling mechanism is critical in addition facilities supporting data abstraction techniques as described[close]
p. 14
14 above are important because the arguments for data abstraction and for its refinements to support elegant use of types are equally valid where support for object-oriented programming is available the success of both techniques hinges on the design of types and on the ease flexibility and efficiency of such types object-oriented programming simply allows user-defined types to be far more flexible and general than the ones designed using only data abstraction techniques 4.1 calling mechanisms the key language facility supporting object-oriented programming is the mechanism by which a member function is invoked for a given object for example given a pointer p how is a call p farg handled there is a range of choices in languages such as c and simula where static type checking is extensively used the type system can be employed to select between different calling mechanisms in c two alternatives are available [1 a normal function call the member function to be called is determined at compile time through a lookup in the compiler s symbol tables and called using the standard function call mechanism with an argument added to identify the object for which the function is called where the standard function call is not considered efficient enough the programmer can declare a function inline and the compiler will attempt to inline expand its body in this way one can achieve the efficiency of a macro expansion without compromising the standard function semantics this optimization is equally valuable as a support for data abstraction [2 a virtual function call the function to be called depends on the type of the object for which it is called this type cannot in general be determined until run time typically the pointer p will be of some base class b and the object will be an object of some derived class d as was the case with the base class shape and the derived class circle above the call mechanism must look into the object and find some information placed there by the compiler to determine which function f is to be called once that function is found say d f it can be called using the mechanism described above the name f is at compile time converted into an index into a table of pointers to functions this virtual call mechanism can be made essentially as efficient as the normal function call mechanism in the standard c implementation only five additional memory references are used in languages with weak static type checking a more elaborate mechanism must be employed what is done in a language like smalltalk is to store a list of the names of all member functions methods of a class so that they can be found at run time [3 a method invocation first the appropriate table of method names is found by examining the object pointed to by p in this table or set of tables the string f is looked up to see if the object has an f if an f is found it is called otherwise some error handling takes place this lookup differs from the lookup done at compiler time in a statically checked language in that the method invocation uses a method table for the actual object a method invocation is inefficient compared with a virtual function call but more flexible since static type checking of arguments typically cannot be done for a method invocation the use of methods must be supported by dynamic type checking 4.2 type checking the shape example showed the power of virtual functions what in addition to this does a method invocation mechanism do for you you can attempt to invoke any method for any object the ability to invoke any method for any object enables the designer of general purpose libraries to push the responsibility for handling types onto the user naturally this simplifies the design of libraries for example:[close]
p. 15
15 class stack assume class any has a member next any v void pushany p p next v v p any pop if v 0 return error_obj any r v v v next return r it becomes the responsibility of the user to avoid type mismatches like this stack[close]
Comments
no comments yet