2y ago

40 Views

4 Downloads

603.43 KB

184 Pages

Transcription

Advanced Functional Programming with C TemplatesRoy H. StognerThe University of Texas at AustinFeb 29, 2012Roy H. StognerGenericFeb 29, 20121 / 56

Stuff We Covered Last TimeData TypesOutline1Stuff We Covered Last TimeData TypesMulti-precision VerificationArray OperationsAutomatic DifferentiationFunctional Metaprogramming with Templates2Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesFunctional Data StructuresSparse Data StructuresPhysics as a Graph ProblemEvaluations on the GraphDifferentiation on the Graph3Stuff We’ll Cover Next TimeRoy H. StognerGenericFeb 29, 20122 / 56

Stuff We Covered Last TimeData TypesData Type Independence: Generic ProgrammingExample Template arguments can beintegral or data typestemplate int size, typename T classNumberArray {.T dot(const NumericVector T & v)const {T r 0;for(int i 0; i ! size; i)r data[i] * v[i];return.r;T* data;}; Class data members candepend on template argumentNumericVector float floatvec;NumericVector complex double complexdoublevec;NumericVector NumericVector float floatmatrix;Roy H. StognerGeneric Class methods can depend ontemplate argument Templated classes can beinstantiated with plain datatypesI . or with other instantiatedtemplated typesI . or with other instantiationsof themselves!Feb 29, 20123 / 56

Stuff We Covered Last TimeMulti-precision VerificationOutline1Stuff We Covered Last TimeData TypesMulti-precision VerificationArray OperationsAutomatic DifferentiationFunctional Metaprogramming with Templates2Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesFunctional Data StructuresSparse Data StructuresPhysics as a Graph ProblemEvaluations on the GraphDifferentiation on the Graph3Stuff We’ll Cover Next TimeRoy H. StognerGenericFeb 29, 20124 / 56

Stuff We Covered Last TimeArray OperationsOutline1Stuff We Covered Last TimeData TypesMulti-precision VerificationArray OperationsAutomatic DifferentiationFunctional Metaprogramming with Templates2Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesFunctional Data StructuresSparse Data StructuresPhysics as a Graph ProblemEvaluations on the GraphDifferentiation on the Graph3Stuff We’ll Cover Next TimeRoy H. StognerGenericFeb 29, 20125 / 56

Stuff We Covered Last TimeAutomatic DifferentiationOutline1Stuff We Covered Last TimeData TypesMulti-precision VerificationArray OperationsAutomatic DifferentiationFunctional Metaprogramming with Templates2Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesFunctional Data StructuresSparse Data StructuresPhysics as a Graph ProblemEvaluations on the GraphDifferentiation on the Graph3Stuff We’ll Cover Next TimeRoy H. StognerGenericFeb 29, 20126 / 56

Stuff We Covered Last TimeAutomatic Differentiation“Dual Numbers”For each simple operation s(x, y), s ss(a b , c d ) s(a, c) b (a, c) d (a, c) x yExtending to division, algebraic functions, transcendental functions, etcalso gives: for any function f (x),f (a b ) f (a) bf 0 (a) Composition of functions preserves these properties, so with independentvariable x R, we set X x and get:f (X) f (x) f 0 (x) Recursion gives us gradients, “hyper-duals”, etc.Roy H. StognerGenericFeb 29, 20127 / 56

Stuff We Covered Last TimeAutomatic DifferentiationOperator-Overloaded Forward DifferentiationExampletypedef double RawType// typedef ShadowNumber double, long double RawType;typedef DualNumber RawType,RawType FirstDerivType;const FirstDerivType x(pi/6,1);//const FirstDerivType sinx sin(x);//const FirstDerivType y sinx*sinx;//const double raw y raw value(y); //double deriv raw value(y.derivatives());assert(deriv 2*sin(pi/6)*cos(pi/6)); //Roy H. StognerGenericInitializing independent varCaching just like normalSmart pow would work tooNo implicit down-conversions!FP ops match hand-code!Feb 29, 20128 / 56

Stuff We Covered Last TimeAutomatic DifferentiationMASA PDE ExamplesManufactured Solution// Arbitrary manufactured solutionU.template get 0 () u 0 u x * sin(a ux * PI * x / L) u y * cos(a uy * PI * y / L);// Why not U[0] and U[1]? To be explained in this talkU.template get 1 () v 0 v x * cos(a vx * PI * x / L) v y * sin(a vy * PI * y / L);ADScalar RHO rho 0 rho x * sin(a rhox * PI * x / L) rho y * cos(a rhoy * PI * y / L);ADScalar P p 0 p x * cos(a px * PI * x / L) p y * sin(a py * PI * y / L);Roy H. StognerGenericFeb 29, 20129 / 56

Stuff We Covered Last TimeAutomatic DifferentiationMASA PDE ExamplesEuler// Gas stateADScalar T P / RHO / R;ADScalar E 1. / (Gamma-1.) * P / RHO;ADScalar ET E .5 * U.dot(U);// Conservation equation residualsScalar Q rho raw value(divergence(RHO*U));RawArray Q rho u raw value(divergence(RHO*U.outerproduct(U)) P.derivatives());Scalar Q rho e raw value(divergence((RHO*ET P)*U));Roy H. StognerGenericFeb 29, 20129 / 56

Stuff We Covered Last TimeAutomatic DifferentiationMASA PDE ExamplesNavier-Stokes// Gas stateADScalar T P / RHO / R;ADScalar E 1. / (Gamma-1.) * P / RHO;ADScalar ET E .5 * U.dot(U);// Constitutive lawsTensor GradU gradient(U);Tensor Tau mu * (GradU transpose(GradU) 2./3. * divergence(U) * RawArray::identity());FullArray q -k * T.derivatives();// Conservation equation residualsScalar Q rho raw value(divergence(RHO*U));RawArray Q rho u raw value(divergence(RHO*U.outerproduct(U) - Tau) P.derivatives());Scalar Q rho e raw value(divergence((RHO*ET P)*U q - Tau.dot(U)));Roy H. StognerGenericFeb 29, 20129 / 56

Stuff We Covered Last TimeFunctional Metaprogramming with TemplatesOutline1Stuff We Covered Last TimeData TypesMulti-precision VerificationArray OperationsAutomatic DifferentiationFunctional Metaprogramming with Templates2Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesFunctional Data StructuresSparse Data StructuresPhysics as a Graph ProblemEvaluations on the GraphDifferentiation on the Graph3Stuff We’ll Cover Next TimeRoy H. StognerGenericFeb 29, 201210 / 56

Stuff We Covered Last TimeFunctional Metaprogramming with TemplatesTemplates as “Functions” Classes take constant integers as template arguments Classes can “return” static const integers as membersExampletemplate unsigned int N struct Factorial {static const unsigned int value // Each valueN * Factorial N-1 ::value;// is constant};template struct Factorial 0 {static const unsigned int value 1;};// Zero FP ops, zero tests/branches at runtimeunsigned int twelve Factorial 4 ::value;Roy H. StognerGenericFeb 29, 201211 / 56

Stuff We Covered Last TimeFunctional Metaprogramming with TemplatesTemplates as “Functions” Classes take constant integers or types as template arguments Classes can “return” static const integers or typedef’ed types asmembersExampletemplate typename T, typename S struct CompareTypes {};template unsigned int size, typename T, typename T2, typename S2 struct CompareTypes NumberArray size,T ,ShadowNumber T2,S2 {typedef NumberArray size,typename CompareTypes T,ShadowNumber T2,S2 ::supertype supertype;};Roy H. StognerGenericFeb 29, 201211 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesOutline1Stuff We Covered Last TimeData TypesMulti-precision VerificationArray OperationsAutomatic DifferentiationFunctional Metaprogramming with Templates2Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesFunctional Data StructuresSparse Data StructuresPhysics as a Graph ProblemEvaluations on the GraphDifferentiation on the Graph3Stuff We’ll Cover Next TimeRoy H. StognerGenericFeb 29, 201212 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesType Function Examples: “IfElse”Exampletemplate bool Condition, typename TrueResult, typename FalseResult struct IfElse {typedef TrueResult type;};template typename TrueResult, typename FalseResult struct IfElse false, TrueResult, FalseResult {typedef FalseResult type;};Roy H. StognerGenericFeb 29, 201213 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesType Function Examples: “IfElse”Exampletemplate bool Condition, typename TrueResult, typename FalseResult struct IfElse {typedef TrueResult type;};template typename TrueResult, typename FalseResult struct IfElse false, TrueResult, FalseResult {typedef FalseResult type;};const bool imprecise true; // compile-time constantIfElse imprecise,float,long double ::type one third 1.L/3.L;Roy H. StognerGenericFeb 29, 201213 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesType Function Examples: “TypesEqual”Exampletemplate typename T1, typename T2 struct TypesEqual {static const bool value false};template typename T struct TypesEqual T,T {static const bool value true};Roy H. StognerGenericFeb 29, 201214 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesType Function Examples: “enable if” We partially specialized CompareTypes to handle combinations ofclasses and built-in typesExampletemplate unsigned int size, typename T, typename T2 struct CompareTypes NumberArray size,T ,T2 {typedef NumberArray size,typename CompareTypes T,T2 ::supertype supertype;};Roy H. StognerGenericFeb 29, 201215 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesType Function Examples: “enable if” We partially specialized CompareTypes to handle combinations ofclasses and built-in types But we need to limit those specializations to built-in typesExampletemplate unsigned int size, typename T, typename T2 structCompareTypes NumberArray size,T , T2,typename boost::enable if c IsBuiltin T2 ::value ::type {typedef NumberArray size,typename CompareTypes T,T2 ::supertype supertype;};Roy H. StognerGenericFeb 29, 201215 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesType Function Examples: “enable if”Examplenamespace boost {template bool B, class T void struct enable if c {typedef T type;};template class T struct enable if c false, T {};enable if c true,double ::type one third 1.L/3.L;Roy H. StognerGenericFeb 29, 201216 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesType Function Examples: “enable if”Examplenamespace boost {template bool B, class T void struct enable if c {typedef T type;};template class T struct enable if c false, T {};enable if c true,double ::type one third 1.L/3.L;enable if c false,double ::type compile error 0;Roy H. StognerGenericFeb 29, 201216 / 56

Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesType Function Examples: “enable if”Examplenamespace boost {template bool B, class T void struct enable if c {typedef T type;};template class T struct enable if c false, T {};enable if c true,double ::type one third 1.L/3.L;enable if c false,double ::type compile error 0;template typename T enable if c IsBuiltin T ::value,T SFINAE(T& x) { return x*x; }}Roy H. StognerGenericFeb 29, 201216 / 56

Numeric Functional ProgrammingFunctional Data StructuresOutline1Stuff We Covered Last TimeData TypesMulti-precision VerificationArray OperationsAutomatic DifferentiationFunctional Metaprogramming with Templates2Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesFunctional Data StructuresSparse Data StructuresPhysics as a Graph ProblemEvaluations on the GraphDifferentiation on the Graph3Stuff We’ll Cover Next TimeRoy H. StognerGenericFeb 29, 201217 / 56

Numeric Functional ProgrammingFunctional Data StructuresData Structures with Templates: Type ContainerExampletemplate typename HeadType,typename TailContainer NullContainer,typename Comparison ValueLessThan struct Container{typedef HeadTypehead type;typedef TailContainer tail set;typedef Comparisoncomparison;// These may be empty types or may have dataHeadTypehead;TailContainertail;.};struct NullContainer{.};Roy H. StognerGenericFeb 29, 201218 / 56

Numeric Functional ProgrammingFunctional Data StructuresData Structures with Templates: Type ContainerExampleContainer IntType 1 no data one static int;Roy H. StognerGenericFeb 29, 201219 / 56

Numeric Functional ProgrammingFunctional Data StructuresData Structures with Templates: Type ContainerExampleContainer IntType 1 no data one static int;Container IntType 1 ,Container IntType 4 no data two static ints;Roy H. StognerGenericFeb 29, 201219 / 56

Numeric Functional ProgrammingFunctional Data StructuresData Structures with Templates: Type ContainerExampleContainer IntType 1 no data one static int;Container IntType 1 ,Container IntType 4 no data two static ints;Container IntType 1,float ,Container IntType 4,float float data two static ints;Roy H. StognerGenericFeb 29, 201219 / 56

Numeric Functional ProgrammingFunctional Data StructuresData Structures with Templates: Type ContainerExampleContainer IntType 1 no data one static int;Container IntType 1 ,Container IntType 4 no data two static ints;Container IntType 1,float ,Container IntType 4,float float data two static ints;Container IntType 1,double ,Container IntType 4 ,NumberArray 3,double heterogenous data;Roy H. StognerGenericFeb 29, 201219 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting into a NullContainer is easy: If we’re inserting null, we’re still left with a NullContainerRoy H. StognerGenericFeb 29, 201220 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting into a NullContainer is easy: If we’re inserting null, we’re still left with a NullContainer If not, we have a one-element container with the inserted element.Roy H. StognerGenericFeb 29, 201220 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting into a NullContainer is easy: If we’re inserting null, we’re still left with a NullContainer If not, we have a one-element container with the inserted element.Roy H. StognerGenericFeb 29, 201220 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting into a NullContainer is easy: If we’re inserting null, we’re still left with a NullContainer If not, we have a one-element container with the inserted element.Examplestruct NullContainer{.template typename ValueType, typename NewComparison struct Insert{typedeftypename IfElse (TypesEqual ValueType,NullContainer ::value),NullContainer,Container ValueType, NullContainer, NewComparison ::type type;};.};Roy H. StognerGenericFeb 29, 201220 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting in nonempty sorted sets is trickier:Roy H. StognerGenericFeb 29, 201221 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting in nonempty sorted sets is trickier: If we’re inserting null, we return our same setRoy H. StognerGenericFeb 29, 201221 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting in nonempty sorted sets is trickier: If we’re inserting null, we return our same set If we’re inserting something smaller than our set head, then itbecomes the new head and our set becomes the new tailRoy H. StognerGenericFeb 29, 201221 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting in nonempty sorted sets is trickier: If we’re inserting null, we return our same set If we’re inserting something smaller than our set head, then itbecomes the new head and our set becomes the new tail If we’re inserting something larger than our set head, then the headstays unchanged and we insert into the tailRoy H. StognerGenericFeb 29, 201221 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertInserting in nonempty sorted sets is trickier: If we’re inserting null, we return our same set If we’re inserting something smaller than our set head, then itbecomes the new head and our set becomes the new tail If we’re inserting something larger than our set head, then the headstays unchanged and we insert into the tail If we’re inserting something equivalent to our set head, then the headmay get “upgraded”Roy H. StognerGenericFeb 29, 201221 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: InsertExamplestruct Container {.template typename ValueType, typename NewComparison struct Insert {typedeftypename IfElse (TypesEqual ValueType,NullContainer ::value),Sorted,typename IfElse (Comparison::template LessThan ValueType,typename Sorted::head type ::value),Container ValueType,Sorted ,typename IfElse (Comparison::template LessThan typename Sorted::head type,ValueType ::value),Container typename Sorted::head type,typename Sorted::tail set::template Insert ValueType,NewComparison ::type ,Container typename CombinedType ValueType, typename Sorted::head type ::type,typename Sorted::tail set ::type ::type ::type type;};.};Roy H. StognerGenericFeb 29, 201222 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Union Union with an empty container is trivial.Roy H. StognerGenericFeb 29, 201223 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Union Union with an empty container is trivial. With a non-empty container, Insert makes things easy. We justinsert “one element at a time” recursively:Roy H. StognerGenericFeb 29, 201223 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Union Union with an empty container is trivial. With a non-empty container, Insert makes things easy. We justinsert “one element at a time” recursively:Roy H. StognerGenericFeb 29, 201223 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Union Union with an empty container is trivial. With a non-empty container, Insert makes things easy. We justinsert “one element at a time” recursively:Exampletemplate typename Set2 struct Union {typedef typenametail set::Sorted::template Union typename Set2::Sorted::template Insert head type ::type ::type type;};Roy H. StognerGenericFeb 29, 201223 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Intersection Intersection with an empty container is trivial.Roy H. StognerGenericFeb 29, 201224 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Intersection Intersection with an empty container is trivial. With a non-empty container, Contains makes things easy. Weselectively build a new set “one element at a time” recursively:Roy H. StognerGenericFeb 29, 201224 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Intersection Intersection with an empty container is trivial. With a non-empty container, Contains makes things easy. Weselectively build a new set “one element at a time” recursively:Roy H. StognerGenericFeb 29, 201224 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Intersection Intersection with an empty container is trivial. With a non-empty container, Contains makes things easy. Weselectively build a new set “one element at a time” recursively:Exampletemplate typename Set2 struct Intersection {typedef typenameIfElse Set2::template Contains head type ::value,Container typename SymmetricCompareTypes head type,typename Set2::template Contains head type ::type ::supertype,typename tail set::template Intersection Set2 ::type ,typename tail set::template Intersection Set2 ::type ::type type;};Roy H. StognerGenericFeb 29, 201224 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Difference Subracting from an empty container is trivial.Roy H. StognerGenericFeb 29, 201225 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Difference Subracting from an empty container is trivial. With a non-empty container, Contains makes things easy. Weselectively build a new set “one element at a time”, recursively:Roy H. StognerGenericFeb 29, 201225 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Difference Subracting from an empty container is trivial. With a non-empty container, Contains makes things easy. Weselectively build a new set “one element at a time”, recursively:Roy H. StognerGenericFeb 29, 201225 / 56

Numeric Functional ProgrammingFunctional Data StructuresSet Operations: Difference Subracting from an empty container is trivial. With a non-empty container, Contains makes things easy. Weselectively build a new set “one element at a time”, recursively:Exampletemplate typename Set2 struct Difference{typedef typenameIfElse Set2::template Contains head type ::value,typename tail set::template Difference Set2 ::type,Container head type,typename tail set::template Difference Set2 ::type,Comparison ::type type;};Roy H. StognerGenericFeb 29, 201225 / 56

Numeric Functional ProgrammingFunctional Data StructuresRuntime Operations: ForEach Applying a standard functor to every set element Recursive compile-time metaprogram generates a simple linearrun-time program f receives a non-compile-time-const vExamplestruct RuntimeForEach{template typename Functor void operator()(const Functor &f) {// f might want a reference, so we pass in a non-static copyconst typename head type::value type v head type::value;f(v);typename tail set::RuntimeForEach()(f);}};Roy H. StognerGenericFeb 29, 201226 / 56

Numeric Functional ProgrammingFunctional Data StructuresRuntime Operations: ForEach Applying a “template functor” to every set element Recursive compile-time metaprogram generates a simple linearrun-time program f receives a compile-time-const HeadTypeExamplestruct ForEach{template typename Functor void operator()(const Functor &f) {f.operator() HeadType (v);typename tail set::ForEach()(f);}};Roy H. StognerGenericFeb 29, 201227 / 56

Numeric Functional ProgrammingSparse Data StructuresOutline1Stuff We Covered Last TimeData TypesMulti-precision VerificationArray OperationsAutomatic DifferentiationFunctional Metaprogramming with Templates2Numeric Functional ProgrammingAdvanced Functional Programming with TemplatesFunctional Data StructuresSparse Data StructuresPhysics as a Graph ProblemEvaluations on the GraphDifferentiation on the Graph3Stuff We’ll Cover Next TimeRoy H. StognerGenericFeb 29, 201228 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vectors An IndexSet lists sparse indices with potentially non-zero data e.g. the vector [0 0 1 0 2 0] will have {3, 5} or a superset as index setExampletemplate typename T, typename IndexSet class SparseNumberArray {public:typedef IndexSet index set;static const unsigned int size IndexSet::size;.T& raw at(unsigned int i){ return data[i]; }.private:T data[size];};Roy H. StognerGenericFeb 29, 201229 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vectors An IndexSet lists sparse indices with potentially non-zero data Variable-index component access via runtime search through indicesExampletemplate typename T, typename IndexSet class SparseNumberArray {public:typedef IndexSet index set;static const unsigned int size IndexSet::size;.T& operator[](index value type i){ return data[IndexSet::runtime index of(i)]; }.private:T data[size];};Roy H. StognerGenericFeb 29, 201229 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vectors An IndexSet lists sparse indices with potentially non-zero data Variable-index component access via runtime search through indices Const-index O (1) access via template argumentsExampletemplate typename T, typename IndexSet class SparseNumberArray {public:typedef IndexSet index set;static const unsigned int size IndexSet::size;.template unsigned int i typename entry type i ::type& get() {return data[IndexSet::template IndexOf i ::index];}.private:T data[size];};Roy H. StognerGenericFeb 29, 201229 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vector OperationsSome operations are easily defined, no index set operations needed:Roy H. StognerGenericFeb 29, 201230 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vector OperationsSome operations are easily defined, no index set operations needed: Multiplication by a constant: for loop over all data, multiply datumRoy H. StognerGenericFeb 29, 201230 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vector OperationsSome operations are easily defined, no index set operations needed: Multiplication by a constant: for loop over all data, multiply datumRoy H. StognerGenericFeb 29, 201230 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vector OperationsSome operations are easily defined, no index set operations needed: Multiplication by a constant: for loop over all data, multiply datumOther operations require simple set operations:Roy H. StognerGenericFeb 29, 201230 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vector OperationsSome operations are easily defined, no index set operations needed: Multiplication by a constant: for loop over all data, multiply datumOther operations require simple set operations: Element-wise addition takes a Union of index sets Element-wise multiplication takes an Intersection of index sets Element-wise division takes the numerator’s index set, but asserts(compile-time!) that the divisor’s is a superset.Roy H. StognerGenericFeb 29, 201230 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vector OperationsSome operations are easily defined, no index set operations needed: Multiplication by a constant: for loop over all data, multiply datumOther operations require simple set operations: Element-wise addition takes a Union of index sets Element-wise multiplication takes an Intersection of index sets Element-wise division takes the numerator’s index set, but asserts(compile-time!) that the divisor’s is a superset.Others require repeated set operations:Roy H. StognerGenericFeb 29, 201230 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vector OperationsSome operations are easily defined, no index set operations needed: Multiplication by a constant: for loop over all data, multiply datumOther operations require simple set operations: Element-wise addition takes a Union of index sets Element-wise multiplication takes an Intersection of index sets Element-wise division takes the numerator’s index set, but asserts(compile-time!) that the divisor’s is a superset.Others require repeated set operations: Consider a typical binary function, max(a,b) , applied element-wise totwo sparse vectors: For each element in the intersection of the index sets, we apply thefunction to the corresponding pair of vector data. For each element in each asymmetric difference of the index sets, weapply the function to a pair of the present vector datum and 0.Roy H. StognerGenericFeb 29, 201230 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse Vector FunctionsExampletemplate typename T, typename T2, typename IndexSet, typename IndexSet2 inlineSparseNumberArray typename SymmetricCompareTypes T,T2 ::supertype,typename IndexSet::template Union IndexSet2 ::type funcname (const SparseNumberArray T, IndexSet & a, const SparseNumberArray T2, IndexSet2 & b){typedef typename SymmetricCompareTypes T,T2 ::supertype TS;typedef typename IndexSet::template Union IndexSet2 ::type IndexSetS;SparseNumberArray TS, IndexSetS returnval;typename IndexSet::template Intersection IndexSet2 ::type::ForEach()(BinaryArrayFunctor std::binary function TS,TS,TS ,IndexSet,IndexSet2,IndexSet,T,T2,TS (a.raw data(), b.raw data(), returnval.raw data(), std::ptr fun(std::funcname TS )));typename IndexSet::template Difference IndexSet2 ::type::ForEach()(UnaryArrayFunctor std::unary function TS,TS ,IndexSet,T,TS (a.raw data(), returnval.raw data(), std::bind2nd(std::ptr fun(std::funcname TS ),0)));typename IndexSet2::template Difference IndexSet ::type::ForEach()(UnaryArrayFunctor std::unary function TS,TS ,IndexSet,T2,TS (b.raw data(), returnval.raw data(), std::bind1st(std::ptr fun(std::funcname TS ),0)));return returnval;}Roy H. StognerGenericFeb 29, 201231 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse StructuresConsider recursion with dual numbers, for automatic differentiationRoy H. StognerGenericFeb 29, 201232 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse StructuresConsider recursion with dual numbers, for automatic differentiation x is only non-constant w.r.t. x; y is only non-constant w.r.t. y DualNumber x and y are given unit vector gradients Their sums, products, etc. then all have optimally sparse gradients.Roy H. StognerGenericFeb 29, 201232 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse StructuresConsider recursion with dual numbers, for automatic differentiation x is only non-constant w.r.t. x; y is only non-constant w.r.t. y DualNumber x and y are given unit vector gradients Their sums, products, etc. then all have optimally sparse gradients.We now have excellent sparse vectors-of-T!Roy H. StognerGenericFeb 29, 201232 / 56

Numeric Functional ProgrammingSparse Data StructuresOperator-Overloaded Sparse StructuresConsider recursion with dual numbers, for automatic differentiation x is o

Numeric Functional Programming Functional Data Structures Outline 1 Stuff We Covered Last Time Data Types Multi-precision Veriﬁcation Array Operations Automatic Differentiation Functional Metaprogramming with Templates 2 Numeric Functional Programming Advanced Functional Programming with Templates Functional Data Structures Sparse Data Structures

Related Documents: