higher-order functions

---

CTTL on         SourceForge

Download         Latest

Documentation         Index

Library         News

CVS         Repository

Other        Links

---

Higher-order function takes other functions as an argument, together forming a set of "nested functions". In C++, higher-order functions can be expressed through functional composition F(G(x)). However, environment supporting lazy evaluation requires a placeholder object that captures addresses of all nested functions and a variable to store the result. In practice, higher-order function is a mechanism to perform data conversions and store pieces of information in user structures. Parser program could use nested functions to populate syntax trees and symbol tables as a result of successful grammar evaluation.

Lambda library reserves overloaded binary operator^ to devise in-line hierarchical objects supporting implementation of higher-order functions and lambda composite structures (discussed later.) For example,

int F( int x_ )
{
    return x_ * 2;
}

int G( int x_ )
{
    return x_ * 3;
}

template< typename LambdaT >
void f( LambdaT lambda_ )
{
    lambda_.evaluate(); 
}

void g()
{
    int var = 0;
    f( scalar( &var )^F^G = 5 ); // delayed "var = F( G( 5 ) )"
    assert( var == 30 );
}

For direct application of logical exclusive OR operator, implementation defines helper function named cttl::operator_xor().

Connected by ^ operators, which hold property of left-to-right associativity, lambda expression scalar( &var )^F^G formulates binary tree with three terminal nodes,

                ^
               / \
              ^   G
             / \
  scalar(&var)  F

Each internal component of this tree is represented by template class

    cttl_impl::xst_translator< LambdaT, TranslatorT >  // HOF placeholder

Template parameter LambdaT specifies left-hand-side type of lambda primitive used in expression higher-order function expression. Parameter TranslatorT specifies the type of nested function on the right-hand-side. Template class xst_translator is adaptable by generic placeholder class

    cttl_impl::xst_lambda_wrap< LambdaT >  // generic variable

Combination of these two templates yields an object that behaves exactly as scalar primitive. The resulting object itself can be passed as LambdaT template parameter for another xst_translator. This arrangement of template hierarchy makes possible to devise objects representing nested functions. Expression

    S^f^g^h^...^m

implements higher-order function, composed of lambda primitive S, and a set of nested functions f, g, h,... m. Compiled expression constitutes a binary tree:

                    ^
                   / \
                 ...  m
                 / \
                ^   h
               / \
              ^   g
             / \
            S   f

Rightmost terminal S is a lambda primitive which receives return value of the higher-order function. Library implementation class xst_translator overloads assignment operator, permitting compile-time expression format

   S^f^g^h^...^m = x

Run-time evaluation of this delayed assignment expression triggers a chain of function calls,

   S.push( f( g( h( ... m( x ) ... ) ) )

Ultimately, return value of of the outermost function f is pushed into lambda primitive S, by push() member function. If primitive S happens to be scalar, its value is replaced. If S is a stack primitive, the new element is pushed on the stack.

If T represents composition of nested functions S^f^g^h^...^m, and S is a lambda primitive to store return value of expression

    f( g( h( ... m( x ) ... ) )

then the following lambda expression formats become available:

Overloaded operators for higher-order functions

Expression	Description
T = x	Delayed T.push( x ), which translates to S.push( f( g( h( ... m( x ) ... ) ) ) where x is an object acceptable as argument of innermost nested function m. Such value translation can be used to convert data from one type to another. For example, #include "cttl/cttl.h" #include "lambda/lambda.h" #include "utils/itos.h" using namespace cttl; int main(int argc, char* argv[]) { lambda< std::string >::scalar str; ( (str^itos) = 123, // convert integer to string CTTL_LAMBDA_ASSERT( str == scalar( std::string( "123" ) ) ) ).evaluate(); return 0; }
++T	Same as T = true. Implements delayed T.push( true ), which translates to S.push( f( g( h( ... m( true ) ... ) ) )
--T	Same as T = false. Implements delayed T.push( false ), which translates to S.push( f( g( h( ... m( false ) ... ) ) )

---

pre-defined higher-order function expressions

---

Higher-order functions are assembled from nested addresses of free functions, closure objects, and function objects with overloaded function call operator(). Lambda library also includes a number of pre-defined function objects, created by specific kinds of higher-order function expressions. Resulting pre-defined functors facilitate transformations between data types, commonly encountered in parser programs:

• cttl_impl::xst_literal_translator <CharT>: stores constant pointer to a character literal, which becomes an argument for higher-order function.
  

• cttl_impl::xst_edge_translator <PolicyT,StringT>: converts value of CTTL substring to a null-terminated array of characters, used as higher-order function argument.
  

• cttl_impl::xst_sequence_translator <SequenceT>: when invoked as a function, converts its argument to integral type by inserting new element into symbol table represented by STL sequence container. Returns corresponding array index of newly inserted element.
  

• cttl_impl::xst_dictionary_translator <SequenceT,MapT> converts value to integral type by storing it in a sequence, paired with an associative container. Two containers together represent a dictionary, which serves as a symbol table with unique values.
  

Translators are instantiated by expressions T^X, where T is a higher-order function, and X is an object of the following types:

Pre-defined higher-order function expressions

Type of X	Result of T^X
char const* wchar_t const*	Value translator for literal constant on left-hand side of higher-order function expression. Resulting function object includes specified character literal, passed as an argument to the innermost nested function, such as atof in the following sample: void f() { double var = 0.0; ( ++( scalar( &var )^atof^"3.14159" ) ).evaluate(); assert( var == 3.14159 ); } Version for wide characters is also provided.
const_edge< PolicyT, StringT > const& edge< PolicyT, StringT > const&	Value translator for CTTL substring, specified on the far left side of the expression. which defines higher-order function. CTTL substring is converted to null-terminated array of characters and passed as an argument to the innermost nested function, such as atoi in the following sample: void f( const_edge<>& edge_ ) { int var = 0; ( ++( scalar( &var )^atoi^edge_ ) ).evaluate(); }
std::pair< SequenceT, int >& std::pair< SequenceT*, int >& std::vector< ValueT >&	Value translator implementing algorithm to convert input value to integral type by inserting the value into a sequence container, and returning its array index as the result: void f() { int var = 123; std::vector< std::string > vect; ( ++( scalar( &var )^vect^"abc" ) ).evaluate(); assert( var == 0 ); assert( vect[ var ] == "abc" ); } Object of std::string type is constructed automatically from null-terminated sequence of characters "abc". On the other hand, expression scalar( 0 )^vect = scalar( "abc" ) // *** will not compile would be illegal, since scalar primitives cannot accommodate pointer types. To use assignment, the string has to be constructed explicitly: scalar( 0 )^vect = scalar( std::string( "abc" ) )
std::pair< SequenceT, MapT >& std::pair< SequenceT*, MapT* >&	Dictionary translator, which includes sequence and associative container. The algorithm translates function argument from MapT::key_type to MapT::data_type. The algorithm compares argument value with existing keys, and inserts new element into both containers, if necessary. The value for MapT::data_type is generated automatically from the array index of element, inserted into the sequence container. For example, void f() { // User can construct a dictionary using default // constructors for sequence and associative container: std::pair< std::vector< std::string >, std::map< std::string, int > > symbol_table_a; // Alternatively, parts of the dictionary can be // individually constructed: std::vector< std::string > symbol_vector; std::map< std::string, int > symbol_map; // A pair of pointers represents a dictionary: std::pair< std::vector< std::string >*, std::map< std::string, int >* > symbol_table_b( &symbol_vector, &symbol_map ); ( ++( scalar( 0 )^symbol_table_a^"one" ), ++( scalar( 0 )^symbol_table_b^"two" ) ).evaluate(); assert( symbol_table_a.first[ 0 ] == "one" ); assert( symbol_table_a.second.find( "one" ) != symbol_table_a.second.end() ); assert( ( *symbol_table_a.second.find( "one" ) ).second == 0 ); assert( symbol_vector[ 0 ] == "two" ); assert( symbol_map.find( "two" ) != symbol_map.end() ); assert( ( *symbol_map.find( "two" ) ).second == 0 ); }

---

Copyright © 1997-2006 Igor Kholodov mailto:cttl@users.sourceforge.net.

Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.

---