Advanced Software Engineering With C Templates

1y ago
29 Views
1 Downloads
576.31 KB
55 Pages
Last View : Today
Last Download : 1m ago
Upload by : Laura Ramon
Transcription

Advanced Software Engineeringwith C TemplatesLecture 4: Separate Compilation and Templates IIIThomas Gschwind thg zurich ibm com atdotdot

Agenda Separate Compilation Introduction (C versus Java)VariablesRoutines (Functions & Operators)Types (Structures, Classes)Makefiles Templates III Design and Implementation (C versus Java versus C#) “Dynamic” Static Algorithm Selection BindersTh. Gschwind. Fortgeschrittene Programmierung in C .2

Separate Compilation Why? Having only one source file is unrealistic Break the code up into its logical structure Reduction of compile time- Only changed parts need to be recompiled How? Use multiple source files Need to know what information about functions and variables“used” from other filesTh. Gschwind. Fortgeschrittene Programmierung in C .3

Separate Compilation in Java Each Java file is compiled into a class file If a Java class invokes a method of another class,the compiler consults that other class file to Determine whether the class provides the requested methodDetermine whether a class file implements a given interfaceetc.Hence, the .class file contains the entire interface That’s why in Java, the compiler needs the class path Finally, all class files are loaded by the Java Virtual Machine(and “linked”) Java source code can be relatively well reconstructed from .class file(see Java Decompiler: jd, jad)Th. Gschwind. Fortgeschrittene Programmierung in C .4

Some Java Trivia Let us write Hello World in Java In order to simplify the reconfiguration (e.g., translation) Put all the constants into one Java file Put the complex application code into anotherpublic class Const {public static final String msg "Hello World!";}public class Cool {public static void main(String[] args) {System.out.println(Const.msg);}}Th. Gschwind. Fortgeschrittene Programmierung in C .5

Some Java Trivia Now compile both Java files and run Coolpublic class Const {public static final String msg "Hello World!";}public class Cool {public static void main(String[] args) {System.out.println(Const.msg);}} Change the msg in Const.java, recompile Const.java, and run CoolTh. Gschwind. Fortgeschrittene Programmierung in C .6

Some Java Trivia Now compile both Java files and run Coolpublic class Const {public static final String msg "Hello World!";}public class Cool {public static void main(String[] args) {System.out.println(Const.msg);}} Change the msg in Const.java, recompile Const.java, and run Cool Cool still prints the old message! Why? javac inlines constants And according to the Java specification that’s legalTh. Gschwind. Fortgeschrittene Programmierung in C .7

Separate Compilation in C By convention, each source file is compiled into an object file Object files provide minimum necessary to execute the code Object files do not provide enough information for the compiler toidentify Functions provided by another compilation unit Layout of a user-defined type Object files are not used during the compilation C and C use “header” files to store the interfaces of the object file These files need to be supplied by the developer In C/C , we have the include path insteadTh. Gschwind. Fortgeschrittene Programmierung in C .8

Header Files C uses so-called header files for separate compilation The header file can be viewed as the object file’s interface Hence, header files are another encapsulation mechanism They describe the interface(s) provided by the object files Describe everything that should be exported to other compilation units What goes into the header file? “Everything” that should be exported (i.e., used in other files) “Nothing” that causes the compiler to immediately generate code Except, for a small number of exceptionsTh. Gschwind. Fortgeschrittene Programmierung in C .9

Header Files: Prevent Multiple Inclusion Header files need protection from being included multiple times Otherwise, this may cause compile errorsif VARS H is notdefined process thefollowing linesdefine VARS Hend the last open#if sectionThis pattern ensuresthat header files won’tbe included multipletimesProcess the file“vars.h”vars.h#ifndef VARS H#define VARS Hextern int my dumb global variable;extern const double e;const double pi 3.141596;#endifvars.cc#include "vars.h"int my dumb global variable 17;const double e 2.718281;Th. Gschwind. Fortgeschrittene Programmierung in C .10

Header Files: Variables Variables Declaration goes into the header(if variable is to be accessed elsewhere) Definition goes into the implementation file (allocates memory) Constant Variables Declaration goes into the header(if variable is to be accessed elsewhere) Definition goes either into the header or the implementation file If in the header, definition may be allocated multiple times- No problems for individual values (constant and small)- Be careful with large constants such as large constant arraysTh. Gschwind. Fortgeschrittene Programmierung in C .11

Header Files: Variables Examplevars.h#ifndef VARS H#define VARS Hextern int my dumb global variable;const double pi 3.141596;extern const int[] primes;#endifUse extern to declare a variable tobe defined elsewhere. No memorywill be allocated for the variableConstants may be defined in theheader or declared like othervariables.Include the header (for consistency checking)vars.cc#include "vars.h"Variables are defined in theimplementation file. Do not repeatconstants defined in the header.int my dumb global variable 17;const int primes[] {2, 3, 5, , 1234567891};Th. Gschwind. Fortgeschrittene Programmierung in C .12

Header Files: Functions Functions The declaration of the function goes into the header Definition goes into the implementation file Inline Functions If they are to be inlined in the corresponding implementation file only,treat them like functions If they are to be inlined globally (typical),declaration and definition go into the header file Necessar for the compiler to knowthe implementation to be use instead of the function callTh. Gschwind. Fortgeschrittene Programmierung in C .13

Header Files: Functions Exampleutil.h#ifndef UTIL H#define UTIL Hinline void swap(int &a, int &b) {int c a; a b; b c;}extern int gcf(int a, int b);inline int lcm(int a, int b) {Inline functions are declared anddefined in the header file.Use extern to declare a function.Extern for function declarations isoptional. If there is no functionbody, it cannot be a definition.return (a/gcf(a,b))*b;}#endifutil.cc#include "util.h"int gcf(int a, int b) {if (a b) swap(a,b);while (b! 0) { a a-b; if (a b) swap(a,b); }return a;Functions are defined in theimplementation file. Do not repeatinline functions defined in theheader.}Th. Gschwind. Fortgeschrittene Programmierung in C .14

Header Files: Types (typedef, struct, class) The type declaration and definition go into the header The layout of the type needs to be known to the compilerin all compilation units that need to allocate the type For members of a type the same rules as for functions apply Member declarations into the header Member definitions (unless it should be inlined) into the implementation file All members of a class even if they should not be visible outside thecompilation unit need to be declared as part of the type definitionTh. Gschwind. Fortgeschrittene Programmierung in C .15

fraction.ccfraction.hHeader Files: class Exampleclass fraction {The complete layout of a type (public, protected,int c; int d;private members) go into the header file.public:fraction(int cntr 0, int denom 1) : c(cntr), d(denom) { /*void*/ }fraction operator*(const fraction &b);fraction operator/(fraction b) {operator/ is an implicitly inlineswap(b.c, b.d); return (*this)*b;member, inline functions go into}the header file.};#include "fraction.h"#include "util.h"fraction::fraction operator*(const fraction &b) {fraction r;int f1 gcf(this- c,b.d), f2 gcf(b.c,this- d);r.c (this- c/f1)*(b.c/f2);r.d (this- d/f2)*(b.d/f1);return r; }Th. Gschwind. Fortgeschrittene Programmierung in C .16

Header Files: Templates The type declaration and definition go into the header The code for a template is generated when it is parameterized Hence, the compiler needs the full code to instantiate the template If the template is only to be parameterized with a small set of types Can treat template functions and template classes like normal functions andclasses Need to instantiate the class in an implementation file that has access to thefull template definitions(for instance, template class pvector string ;)Th. Gschwind. Fortgeschrittene Programmierung in C .17

main program Include header files System header files first allowsto find compile errors in headermore easily Own header files first allows tofind missing definitions inheader more easily Compile each file Put dependencies intoMakefile If implementation file changes,it needs to be recompiled If a header file changes, layoutsof types may have changed, allfiles including it need to berecompiledTh. Gschwind. Fortgeschrittene Programmierung in C .#include#include#include#include#include stdlib.h iostream "fraction.h""util.h""vars.h"void main(int argc, char *argv[]) {int arg atoi(argv[1]);cout arg " 2*pi “ arg*arg*pi endl;cout "e " e endl;cout gcf(atoi(argv[1]),atoi(argv[2])) endl;cout lcm(atoi(argv[1]),atoi(argv[2])) endl; // use of fraction data type}18

Makefileall: mainLink the final executable(could also use ldd)Makefilemain: main.o fraction.o util.o vars.omaing -o main main.o fraction.o util.o vars.omain.o: main.cc fraction.h util.h vars.hg -c main.ccfraction.o: fraction.cc fraction.h util.hg -c on.ccutil.o: util.cc util.hg -c util.ccvars.o: vars.cc vars.hg -c vars.ccutil.outil.hutil.ccvars.ovars.hvars.ccTh. Gschwind. Fortgeschrittene Programmierung in C .19

Useful Build Tools gcc: not only compiles and links files Also analyzes sources and generates dependencies between them(Checkout the –M options) Also allows to analyze java files for the dependencies between them nm: list symbols in an object file or program Defined, undefined, which section, etc. ldd, otool –L: list libraries needed by an object file Simply list the shared libraries the object file is dependent onTh. Gschwind. Fortgeschrittene Programmierung in C .20

Makefiles (made easy) As mentioned before, gcc allows to generate source dependencies This Makefile can be used as a generic starter for your MakefileCFLAGS .CFLAGS -Wall -Wextra -WerrorOBJS main.oOBJS fraction.o .# "main" file# others all: mainclean:rm -f main *.odistclean: cleanrm -f .depend/*.drm -f * .Th. Gschwind. Fortgeschrittene Programmierung in C .21

Makefiles (cont’d).-include (addprefix .depend/, (OBJS:.o .d))%.o: %.cgcc (CFLAGS) -c -o @ *[email protected] -MM (CFLAGS) -c *.c .depend/ *.dmain: (OBJS)ld (LDFLAGS) -o @ (OBJS)Th. Gschwind. Fortgeschrittene Programmierung in C .22

Agenda Separate Compilation Introduction (C versus Java)VariablesRoutines (Functions & Operators)Types (Structures, Classes)Makefiles Templates III Design and Implementation (C versus Java versus C#) “Dynamic” Static Algorithm Selection BindersTh. Gschwind. Fortgeschrittene Programmierung in C .23

C Templates – Implementation C creates a new artifact for each new use of a template(almost all modern C compilers do some optimization to avoidunnecessary code duplication) Similar to advanced C macrosTh. Gschwind. Fortgeschrittene Programmierung in C .24

C Templates – Implementation (cont’d) The code for a template is generated when it is parameterized The compiler needs the full code to instantiate the templatetemplate typename T T min(T a, T b) {return a b?a:b;}const double pi 3.141596;void f() {// create implementation formin(2.718282,1.0); // min double min('a','z');// min char min(1,26);// min int min(pi,2.718282); // already createdmin char ('a',26); // already createdmin(2.718282,1.0); // already created}Th. Gschwind. Fortgeschrittene Programmierung in C .25

C Templates – Consequences C creates a new artifact for each new use of a template Uses “more” memory Templates are typically defined in the header file(Otherwise, the compiler cannot instantiate them when they are used) Can be used in combination with built-in types Can be used in combination with non-typenames(e.g., ints, chars, ) Better optimization since each template instantiation can be optimized forthe corresponding template argument Longer compile times due to higher optimization potentialTh. Gschwind. Fortgeschrittene Programmierung in C .26

C Templates – Question What if we have multiple source files instantiating the sametemplate? file1.cc instantiating vector int file2.cc instantiating vector int Will the code for vector int be generated twice once for each object file? Will the executables be double the size when main.cc uses both of them?Th. Gschwind. Fortgeschrittene Programmierung in C .27

C Templates – Question What if we have multiple source files instantiating the sametemplate? file1.cc instantiating vector int file2.cc instantiating vector int Will the code for vector int be generated twice once for each object file?Yes! Will the executables be double the size when main.cc uses both of them?No! Why? The corresponding code of the templates is put into a COMDATsection of the object file. The linker only uses the first such section with thesame name.Th. Gschwind. Fortgeschrittene Programmierung in C .28

Java Generics – Implementation Java Generics are implemented using type erasure Template parameters are internally replaced with their type bound(Object by default) The compiler inserts casts as necessarySource Code“Generated” Codepublic class Iterator E {E next();boolean hasNext();}public class Iterator {Object next();boolean hasNext();}Iterator String iter ;while (iter.hasNext()) {String s iter.next(); }Iterator iter ;while (iter.hasNext()) {String s (String)iter.next(); }Th. Gschwind. Fortgeschrittene Programmierung in C .29

Java Generics – Consequences Java keeps only one copy of the class Java Generics “cannot” be used with primitive types Need to be encapsulated in the corresponding wrapper class Java does this since quite some time automatic BUTgenerating wrappers requires memory, stresses the garbage collector Allows forward and backward compatibility with existing codepublic String oops(Integer x) {List String ys new LinkedList String ();List xs ys;xs.add(x);// compile-time unchecked warningreturn ys.iterator().next(); // run-time error}Th. Gschwind. Fortgeschrittene Programmierung in C .30

Java Generics – Consequences (cont’d) Java keeps only one copy of the class Uses “more” memory because many dynamic casts need to be inserted Programs can be unsafe although they look safe(but the compiler will warn about it) Allows forward and backward compatibility with existing code Cannot create elements of generic type E- No new E or new E[]- Especially the latter can be annoying, need to use Object[] anda lot of (E) casts which are unsafe (see previous slide) JIT cannot optimize for different parameterizationsTh. Gschwind. Fortgeschrittene Programmierung in C .31

C# Generics – Implementation C# thought about Generics from the start Unlike the Java VM, the CLR is already generic Generics can be parameterized with primitive types CLR JIT can optimize code for different parameterizationsTh. Gschwind. Fortgeschrittene Programmierung in C .32

C# Generics – Consequences Templates are stored as such in the byte-code Can be used for built-in types Can use arrays of type T Cannot be used in combination with non-typenames(e.g., ints, chars, ) Better optimization since the template can be optimized for eachspecific template argument Uses “more” memory Is somewhere between C and JavaTh. Gschwind. Fortgeschrittene Programmierung in C .33

Different Types of Iteratorsbirandomdirectional anRead *p *p *p *pAccess- - - - []*p *p *p -- ! ! ! Write*p Iteration CompareTh. Gschwind. Fortgeschrittene Programmierung in C . - ! - 34

Types of Iterators (cont‘d)InputOutputForwardBidirectionalRandom AccessTh. Gschwind. Fortgeschrittene Programmierung in C .struct input iterator tag {};struct output iterator tag {};struct forward iterator tag :public input iterator tag {};struct bidirectional iterator tag :public forward iterator tag {};struct random access iterator tag :public bidirectional iterator tag {};35

Iterator Tags? Algorithm selection Saves typing overhead Simulation of bound genericityDecide which algorithms you want; parameterizethem so that they work for a variety of suitabletypes and data structures.Bjarne StroustrupTh. Gschwind. Fortgeschrittene Programmierung in C .36

Why Iterator Tags? (cont‘d)iteratortemplate class In iterator traits In ::difference typedistance(In first,In last, input iterator tag dummy) {iterator traits In ::difference type n 0;while(first! last) { first; n; }return n;}template class Ran iterator traits Ran ::difference typedistance(Ran first,Ran last, random access iterator tag dummy) {return last-first;}template class I inlineiterator traits I ::difference type distance(I first,I last) {typedef typename iterator traits I ::iterator category cat;return distance(first,last, cat());}Th. Gschwind. Fortgeschrittene Programmierung in C .37

iterator traits Provide a generic iterator description thatcovers standard iterators and pointersiteratortemplate class Iter struct iterator traits Iter {typedef typename Iter::iterator category iterator category;typedef typename Iter::value type value type;typedef typename Iter::difference type difference type;typedef typename Iter::pointer pointer;typedef typename Iter::reference reference;};template class T struct iterator traits T* {typedef random access iterator tag iterator category;typedef T value type;typedef ptrdiff t difference type;typedef T* pointer;typedef T& reference;};Th. Gschwind. Fortgeschrittene Programmierung in C .38

Binders - Motivation Want to find an element in a container that fulfills a criterion For instance, first element in the container that is greater then agiven value In Java If the container provides this fine (unlikely) If not, we start implementing our own routineTh. Gschwind. Fortgeschrittene Programmierung in C .39

Locating an Element The straight forward solution is to use find if with a helper functionint greater than 17(int x) {return x 17;}void foo(vector int v) {vector int ::iterator b r.begin(), e r.end(), i;i find if(b, e, greater than 17); } Having to write that helper function is bothersome In C 11, a more readable solution would be a lambda function Any ideas how to improve this without using C 11?Th. Gschwind. Fortgeschrittene Programmierung in C .40

Function ObjectsPredicates functional equal to, not equal to greater, greater equal, less, less equal logical and, logical or logical not (unary)Arithmetic Operations functional plus, minus, multiplies, divides, modulus negate (unary)Th. Gschwind. Fortgeschrittene Programmierung in C .41

Locating an Element We say we want that the greater than function is executed Problem greater than takes two arguments Solution, the bind2nd function binds one argument to a given valuevoid foo(vector int v) {vector int ::iterator b r.begin(), e r.end(), i;i find if(b, e, bind2nd(greater int (),17)); }Th. Gschwind. Fortgeschrittene Programmierung in C .42

bind2nd(binop,arg2) Binds the second argument of a function If I have already a function less/2 one would not like to writeanother one less/1 for all

Advanced Software Engineering with C Templates Lecture 4: Separate Compilation and Templates III Thomas Gschwind thg at zurich dot ibm dot com . Fortgeschrittene Programmierung in C . 17 Header Files: Templates .