Higher-order functions

<<< Kleene plus adaptor ( direct parser )

Common Text Transformation Library http://cttl.sourceforge.net/

Higher-order functions

higher_order_function.cpp
Higher-order function interface
Higher-order function example: itos
integer_2_string_conversion.cpp

Higher-order function takes another function as an argument. Together, the two functions are forming a set of nested functions. In C++, higher-order functions can be expressed through function composition:
```
    F( G( x ) )
```
However, in the environment of a lambda expression, support of lazy evaluation is absolutely required. Not an immediate, but a delayed function call execution capability is expected. This, in turn, requires a placeholder object that captures the addresses of all nested functions, along with a variable of the appropriate type to store the result.
In practice, a combination of higher-order functions can perform data conversion, or store pieces of information in a user-defined data structure. In progression of grammar evaluation, a parser program could use a set of nested functions to populate syntax trees and symbol tables (discussed later.)
CTTL lambda library overloads ^(*) binary operator^ to devise a set of inline hierarchical objects in support of
1. implementation of higher-order functions, and
2. definition of lambda composite structures (discussed later.)
- _________________
  ^(*) Note: For direct application of the logical exclusive OR ( XOR ) operation, the library defines
  helper function named cttl::operator_xor( arg1, arg2 ).
Consider higher_order_function.cpp sample program:


// higher_order_function.cpp
// Program demonstrates higher-order function and composition of functions.

#include "cttl/cttl.h"
#include "lambda/lambda.h"

using namespace cttl;

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

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

int main(/*int argc, char* argv[]*/)
{
    int var = 0;

    (
        scalar( &var )^F^G = 5

    ).evaluate();

    assert( var == 30 );

    return 0;
}

Connected by ^ operators, which associate left-to-right, the lambda expression
```
    scalar( &var )^F^G
```
is equivalent to
```
    (scalar( &var )^F)^G
```
and formulates a binary tree with three terminal nodes:
```
                ^
               / \
              ^   G
             / \
  scalar(&var)  F
```
Each internal component of the above tree is represented by the template class
```
    // Higher-order function placeholder:
    cttl_impl::xst_translator< LambdaT, TranslatorT >
```
where
- Template parameter LambdaT specifies the type of a left-hand-side lambda primitive used in expression of the higher-order function expression;
- Template parameter TranslatorT specifies the type of the nested function on the right-hand-side.
Template class xst_translator is adaptable by the generic placeholder class
```
    cttl_impl::xst_lambda_wrap< LambdaT >  // model of a general-purpose operand
```
A combination of the above two templates yields a new class with scalar interface. As such, the resulting object itself can be passed as LambdaT template parameter to another xst_translator, using C++ template recursion. This arrangement yields a template hierarchy devising objects representing all required nested functions. An expression
```
    S^f^g^h^...^m
```
implements higher-order function, composed of lambda scalar S, and a set of nested functions f, g, h, ..., and m. Compiled expression constitutes a binary tree:
```
                    ^       // tree encapsulated by xst_translator class
                   / \
                 ...  m
                 / \
                ^   h
               / \
              ^   g
             / \
            S   f
```
The leftmost terminal node S represents a lambda primitive, which receives the return value of the higher-order function.
How can higher-order function be invoked inside a lambda expression? The class xst_translator overloads assignment operator=, which permits a compile-time lambda expression format
```
    ( S^f^g^h^...^m ) = x
```
At run-time, the execution of this delayed assignment expression triggers a chain of the desired function calls:
```
    S.push( f( g( h( ... m( x ) ... ) ) ) )
```
where S.push() is the member function of the uniform scalar interface, discussed later. Ultimately, the return value of the entire chain of calls is assigned to the lambda scalar primitive S by the push() member function:
```
    S = f( g( h( ... m( x ) ... ) ) )
//    |
//    `-- internally: S.push( f( g( h( ... m( x ) ... ) ) ) )
```
The reason for "push" is a product of two possibilities:
- If primitive S is a primitive scalar, its value is replaced (that is, assigned.)
- If S is a stack, the new element is pushed on the stack.
The intrface and types of scalar primitives are discussed later.

Higher-order function interface

```
    S = f( g( h( ... m( x ) ... ) ) )
```
and H is
- (a) an instance of scalar S, or
- (b) an instance of the function composition
```
    S^f^g^h^...^m
```
then public interface of higher-order function H becomes available via a set of the following overloaded operators:

Expression	Description
Assignment H = x	Compiles to a delayed call `H.push( x )`, which triggers a chain of nested calls S.push( f( g( h( ... m( x ) ... ) ) ) ) where `x` is an object acceptable as an argument of the innermost nested function `m()`.
Prefix Increment ++H	Same as `H = true`. Compiles to a delayed `H.push( true )`, which triggers S.push( f( g( h( ... m( true ) ... ) ) ) )
Prefix Decrement --H	Same as `H = false`. Compiles to a delayed `H.push( false )`, which triggers S.push( f( g( h( ... m( false ) ... ) ) ) ) Note: the implementation of prefix decrement operator for literal translators, for example, --( scalar( 0 )^atoi^"123" ) is customized to act as an internal adaptor of `CTTL_LAMBDA_ASSERT` debugging macro. As such, prefix decrement of a literal translator should be avoided in application programs, because it always triggers `assert( false );` (unless `NDEBUG` is defined.)

Higher-order function example: itos

A chained nested calls are useful for converting from one data type to another.
The integer_2_string_conversion.cpp sample demonstrates how a numerical value 123 gets assigned to a string. cttl::itos() function converts int to std::string:

Keywords: integer_2_string_conversion.cpp, CTTL_TRACE_DEPOSITS, CTTL_LAMBDA_ASSERT


// integer_2_string_conversion.cpp
// Program demonstrates value translation and data type conversion
// from int to std::string.

#define CTTL_TRACE_DEPOSITS // turns on tracing of lambda expressions

#include "cttl/cttl.h"
#include "lambda/lambda.h"
#include "utils/itos.h"

using namespace cttl;

int main(/*int argc, char* argv[]*/)
{
    // This is a workaround for microsoft compiler;
    // GNU compiler won't need it:
    typedef CTTL_STD_STRING ( *function_T ) ( int );

    lambda< std::string >::scalar str;
    (
        ( str^function_T( &itos<int> ) ) = 123,   // convert integer to string
        CTTL_LAMBDA_ASSERT( str == scalar( std::string( "123" ) ) )
    ).evaluate();

    return 0;
}

Permission to copy 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.

<<< Kleene plus adaptor ( direct parser )

Lambda Home

Value translators >>>