CTTL Lambda Expression: CTTL lambda expression documentation

Early release of the text transformation library supported limited interaction between grammar expressions and other components of the parser program. The library focused primarily on construction of formal grammars, coupled with unrestricted transformations of input text via semantic actions. In the early stages of the project, for reasons of portability, the library implementation had been limited to basic C++ template features. Starting with release 2.07, the library employs significantly wider range of template features, including template recursion and partial specialization of class templates. Latest version supports lambda expressions, higher-order functions, and closures. In some cases, CTTL lambda expressions could prolong compile time of the program, caused by deep recursion of templated code.

Although CTTL does not support automatic generation of syntax trees, proposed lambda expression engine facilitates direct distribution of parsed tokens from units of grammar to structures that represent symbol tables, syntax trees, or other types of storage containers of user's choice. The notion of in-line semantic action is critical for writing grammars intended for annotation of syntax trees. Together with lambda expressions, latest CTTL release supports in-line data structures named lambda composites, closely imitating homogeneous binary trees and multi-dimensional arrays.

CTTL places no limits or requirements on the coding style of the programmer. Using CTTL lambda features is optional, since the same results can be achieved by semantic actions, described as individual functions. However, a program has a good potential for improvement in places where short, specific, and, often, non-reusable code should be written in-line, directly in scope of grammar definition. Essentially, lambda expression may help to reduce the crowd of little functions with small amount of code.

CTTL relies on expression templates to define C++ objects on the fly, bypassing ordinary class declarations. Code with expression templates generally has good runtime performance, although sometimes at the expense of increased time, required to compile the program.

Lambda implementation is encapsulated within lambda/lambda.h header, which relies on the presence of cttl/cttl.h header. Therefore, a program should include both of these headers in each translation unit in order to use lambda functionality:

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

In essence, lambda expressions allow C++ expressions to be attached to CTTL grammars. This task is carried out by overloaded operators and scalar primitives, representing expression operands. Scalars encapsulate access to C++ constants, variables, and objects.

To communicate with outer environment, lambda expression may directly invoke free standing functions and member functions of objects. Such calls are made possible by closures, otherwise known as delayed function calls.

CTTL closure (delayed function call) is delineated by call to overloaded cttl::action() helper functions, as well as calls to prefabricated functions defined within cttl::alias namespace. For programmer's convenience, all function names in alias namespace are made synonymous to the names of member functions of STL and CTTL components.

lambda requirements

In summary, functional requirements for CTTL lambda implementation may be abstracted as follows:

lambda expression

The following code sample is using in-line scalar encapsulating reference to an integer variable. The variable, passed by address to scalar() helper function, causes instantiation of reference-based scalar:

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

    using namespace cttl;

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

    void g()
    {
        int var = 0;
        f( scalar( &var ) = 5 ); // delayed expression "var = 5"
        assert( var == 5 );
    }

Lambda expressions are unnamed functions, also called lambda functions, described as small in-line functions, defined on the fly by single expression. C++ result type of expression constitutes the type of lambda function. One distinctive property of lambda expression is its delayed evaluation, known also as lazy evaluation. Incidentally, CTTL grammar expressions also fit description of lambda expressions, since their evaluation is delayed. However, design semantics of grammar expressions are tailored specifically for symbol matching against some input text. In contrast, general-purpose lambda functions permit interaction between grammar units and the outside world. Such interaction includes data flow in multiple directions: parsed tokens can be stored for future use by the program, or input text itself can be transformed from within lambda expression. In addition, lambda function could enclose an integer expression that returns result back to the accommodating grammar rule, thus, forming an autonomous grammar unit.

Result of expression, or modified boundaries of parseable universe could instantly change the flow of grammar evaluation.

example of data deposit

Evidently, most common use of lambda functions originates from the idea of depositing parsed input tokens into data structures defined by user program. The following sample demonstrates grammar rule that pushes substrings of characters on the stack:

    std::stack< std::string > str_stack;

    size_t grammar( edge<>& universe_ )
    {
        return
            (
                *(
                    symbol( isalpha )
                    &
                    *(
                        scalar( &str_stack ) = scalar( &universe_ )
                    )
                )
            ).match( universe_ );
    }

example of subscript access to values

Lambda functions can update positions of CTTL nodes directly. Combined with subscript access to characters pointed by nodes, this type of lambda expressions permits reading and writing of individual characters:

void f()
{
    input<> inp( "abcdef" );
    lambda< char >::scalar ch;
    lambda< node<> >::scalar n1( new_node( inp ) );
    lambda< node<> >::scalar n2( new_node( inp ) );
    (
        // update node positions:
        alias::offset( &n1, size_t( 0 ) ),
        alias::offset( &n2, size_t( 1 ) ),
        // swap characters:
        ch = n1[ const_scalar( 0 ) ],
        n1[ const_scalar( 0 ) ] = n2[ scalar( 0 ) ],
        n2[ const_scalar( 0 ) ] = ch
    ).evaluate();
    assert( inp.text() == "bacdef" );
}

example of text transformation

During grammar evaluation, lambda expressions can modify content of input by inserting and replacing arbitrary fragments of text encapsulated by CTTL substrings. This technique yields inline text transformations:

    size_t match_and_replace( edge<>& universe_ )
    {
        return
            (
                *(
                    symbol( "target" )
                    &
                    *(
                        scalar( &universe_ ) = scalar( std::string( "source" ) )
                    )
                )
            ).match( universe_ );
    }

Here, CTTL grammar rule match_and_replace() transforms substrings containing word "target" by replacing them with word "source". The replacement is made possible by cttl::edge class, which overloads assignment operator for strings. Alternatively, assignment could be replaced by explicit call to cttl::edge::text(), which replaces the underlying substring:

    size_t match_and_replace( edge<>& universe_ )
    {
        lambda< edge<> >::scalar_reference scalar_universe( &universe );
        return
            (
                *(
                    symbol( "target" )
                    &
                    *(
                        alias::text( &scalar_universe, std::string( "source" ) )
                    )
                )
            ).match( universe_ );
    }

example of closure (delayed function call)

Another, slightly longer example, demonstrates conversion of individual alphabetical characters to their uppercase equivalents. The grammar updates position of node scalar in a loop, and then invokes closure object (delayed function call) to update value of each character:

void f()
{
    input<> inp( "abc" );
    const_edge<> universe( new_edge( inp ) );
    lambda< char >::scalar ch; // temp character value
    lambda< node<> >::scalar character( new_node( inp ) );

    size_t result = (
        *(  // for each character,
            character.top()( first( isalpha ) ) // match single character
            +
            *(
                ch = character[ 0 ],            // get character value
                character[ 0 ] = *scalar(
                    CTTL_STATIC_ACTION(         // convert to UPPERCASE
                        std::ptr_fun( &toupper ),
                        ch.top()
                    )
                )
            )
        )
    ).match( universe );

    assert( result != std::string::npos );
    assert( inp.text() == "ABC" );
}

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.

CTTL lambda expression documentation