Stack primitive

<<< Scalar primitive

Lambda Home

Scalar interface >>>

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

Stack primitive

Stack primitive typedefs
stack_typedefs.cpp
Inline instantiation of stack primitives
make_stack_demo.cpp
Overloaded stack operators
lambda_stack_primitive.cpp
Stack operator semantics
lambda_stack_decrement.cpp

Often, stack model becomes the first choice for a data structure to store intermidiate results in a recursive-descent parser program. A special type of lambda primitive, named stack primitive, is supported by the CTTL lambda library. At present time, the implementation is limited to std::stack STL container.

Stack primitive typedefs

Similar to the scalar , the stack primitive can be independently instantiated by templated typedefs


template< typename ValueT >
struct lambda {
  //...
  typedef xst_lambda_wrap< xst_stack< std::stack< ValueT > > >  stack;
  typedef xst_lambda_wrap< xst_stack< std::stack< ValueT >& > > stack_reference;
  //...
};  // struct lambda

where ValueT is

a C++ built-in type
an std::pair type
an adaptable compound type, such as STL container, or iterator.

For example,


    std::stack< size_t > st;
    lambda< std::stack< size_t > >::scalar_reference stack_var;
    lambda< std::stack< size_t > >::scalar_reference stack_ref( &st );

The above fragment highlights the fact that the initializer object for the reference-based stack primitive must be passed to the constructor by its address.
The stack_typedefs.cpp sample declares two primitives,
- an instance-scalar storing a copy of int(), and
- a stack-instance primitive accommodating a stack of size_t values.
The program also creates two of the corresponding reference-based primitives. The code uses overloaded operators to read and write values, including the value on top of the stack:

Keywords: stack_typedefs.cpp, type conversion translator, make_reference


// stack_typedefs.cpp
// Program demonstrates usage of a standalone stack primitives
// in lambda expressions.

#define CTTL_TRACE_RULES // automatically turns lambda tracing on

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

using namespace cttl;

size_t int_2_size_t( int value_ )
{
    return value_;
}

int main(/*int argc, char* argv[]*/)
{
    cttl::lambda< int >::scalar Variable;
    cttl::lambda< size_t >::stack Stack;

    cttl::lambda< int >::scalar_reference VariableRef( &Variable.top() );
    cttl::lambda< size_t >::stack_reference StackRef( Stack.make_reference() );
    (
        VariableRef = 1234,
        StackRef^int_2_size_t = VariableRef,

        CTTL_LAMBDA_ASSERT( Variable == 1234 ),
        CTTL_LAMBDA_ASSERT( *Stack == scalar( 1234u ) ),

        Variable = 5678,
        StackRef^int_2_size_t = Variable, // "type conversion" translator

        CTTL_LAMBDA_ASSERT( VariableRef == 5678 ),
        CTTL_LAMBDA_ASSERT( *StackRef == scalar( 5678u ) )

    ).evaluate();

    return 0;
}

Notice that declaration
```
    cttl::lambda< size_t >::stack_reference  StackRef( Stack.make_reference() );
```
requires make_reference() member function to produce a reference-primitive for already existing lambda stack primitive. The reason for this requirement is that there is no constructor for reference-based lambda primitive that takes an instance-based primitive as an argument. Instead, the make_reference() member function is part of the uniform scalar interface. It is available for all types of lambda primitives representing expression operands.

Inline instantiation of stack primitives

Similar to the scalar, a stack primitive can be instantiated in line. Helper functions scalar() and make_stack() return instances of the corresponding lambda primitives as follows:


// A code fragment from lambda/xst_helpers.h:
// ...
// Creates stack-instance primitive:
template<typename ValueT>  
xst_lambda_wrap< xst_stack< std::stack< ValueT > > >
scalar( std::stack< ValueT > const &stack_ );


// Creates stack-reference primitive:
template<typename ValueT>  
xst_lambda_wrap< xst_stack< std::stack< ValueT > & > >
scalar( std::stack< ValueT > *pstack_ );


// Creates stack-instance primitive:
template< typename ValueT >
xst_lambda_wrap< xst_stack< std::stack< ValueT > > >
make_stack( ValueT const& value_ )

These helpers are important for constructing lambda composites.

The last helper, make_stack(), instantiates an empty stack object inside the lambda primitive. Input parameter is a constant reference to an object that can be stored on the stack. However, no values are pushed into the stack; the actual argument is not used.
The make_stack() helper creates a stack without the need to reference an existing stack. Under the future C++0x standard, when the auto keyword becomes available, the variables can be declared by getting their types from the initializer:
```
    auto int_stack = make_stack( int() );
    auto size_t_stack = make_stack( size_t() );
```
A demo program make_stack_demo.cpp uses a surrogate function named auto_Cpp0X() to emulate the described behavior:


// make_stack_demo.cpp
// Program demonstrates usage of make_stack()
// helper function for the lambda stack primitive.

#define CTTL_TRACE_RULES // automatically turns lambda tracing on

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

using namespace cttl;

template< typename StackPrimitiveT >
typename StackPrimitiveT::value_T
auto_Cpp0X(
           StackPrimitiveT stack_,
           typename StackPrimitiveT::value_T value_
           )
{
    stack_.push( value_ );
    return stack_.top();
}

int main(/*int argc, char* argv[]*/)
{
    cttl::lambda< int >::scalar var = auto_Cpp0X( make_stack( 0 ), 5678 );
    assert( var.top() == 5678 );
    return 0;
}

Overloaded stack operators

CTTL lambda implementation for stack operands includes a few additional operators, overloaded specifically for the stack operations, preparing the stack for a simple in-line manipulation. For comparison of different ways to access a stack, consider the following three short programs that parallel similar stack operations:

A program using std::stack directly:

Lambda stack primitive handled by the overloaded operators:

Similar manipulation via std::stack member functions accessed by closures:


#include <stack> 


int main(/*int argc, char* argv[]*/)
{
    int Variable;
    std::stack< int > Stack;
    size_t StackSize;

    Stack.push( 4 );
    Variable = Stack.top();
    Stack.top() = 5;
    Stack.pop();
    StackSize = Stack.size();


    return 0;
}


#include "cttl/cttl.h" 
#include "lambda/lambda.h"
using namespace cttl;
int main(/*int argc, char* argv[]*/)
{
    lambda< int >::scalar Variable;
    lambda< int >::stack Stack;
    lambda< size_t >::scalar StackSize;
    (
        Stack = 4,
        Variable = *Stack,
        *Stack = 5,
        Stack--,
        StackSize = +Stack
    ).evaluate();

    return 0;
}


#include "cttl/cttl.h" 
#include "lambda/lambda.h"
using namespace cttl;
int main(/*int argc, char* argv[]*/)
{
    lambda< int >::scalar Variable;
    lambda< std::stack< int > >::scalar Scalar;
    lambda< size_t >::scalar StackSize;
    (
        alias::push( &Scalar, 4 ),
        Variable = alias::top( Scalar ),
        alias::top( &Scalar ) = 5,
        alias::pop( &Scalar ),
        StackSize = alias::size( Scalar )
    ).evaluate();

    return 0;
}

Another program, lambda_stack_primitive.cpp, demonstrates that the interface of the stack primitive is similar to the scalar interface:


// lambda_stack_primitive.cpp
// Program demonstrates functionality of the lambda stack primitive.

#define CTTL_TRACE_RULES // automatically turns lambda tracing on #include

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

using namespace cttl;

int main(/*int argc, char* argv[]*/)
{
    lambda< int >::scalar Variable;     // instantiate integer scalar
    lambda< size_t >::scalar StackSize; // instantiate size_t scalar
    lambda< int >::stack Stack;         // instantiate std::stack< int >

    assert( Stack.size() == 0 );        // no elements exist so far
    Stack.push( 3 );                    // push new element
    //<top>3<bottom>
    assert( Stack.top() == 3 );         // verify result
    Stack.top() = 2;                    // write access to top element 
    //<top>2<bottom>
    assert( Stack.top() == 2 );         // verify result

    // overloaded stack operators              
    (
        Stack = 4,                      // Stack.push( 4 )
        //<top>4,2<bottom>
        Variable = *Stack,              // Variable = Stack.top()
        *Stack = 5,                     // Stack.top() = 5
        //<top>5,2<bottom>
        StackSize = Stack--,            // Variable = Stack.size (), Stack.pop()
        //<top>2<bottom>                // stack size before pop:
        CTTL_LAMBDA_ASSERT( StackSize == scalar( 2u ) ),
        StackSize = +Stack              // StackSize = Stack.size()
        //<top>2<bottom>
        ).evaluate();

    assert( StackSize.top() == 1 );
    assert( Stack.size() == 1 );
    assert( Stack.top() == 2 );

    return 0;
}

Stack operator semantics

If S is an instance of lambda stack primitive, and x is a scalar encapsulating an object that can be stored on the stack,
```
    lambda< type-name >::stack S;
    lambda< type-name >::scalar x;
```
then the following lambda expression formats become available:

Expression	Description
S = x	Overloaded assignment `operator=` pushes right-hand-side value x on the stack and returns a copy of x as the result of the assignment.
S = (x^y^z)	If right-hand-side expression is lambda composite, then multiple elements are pushed on the stack. The content of lambda composite enters the stack in left-to-right order. Value of the rightmost terminal node (such as z in `x^y^z`) is pushed last. Copy of the last pushed value becomes the result of the assignment.
x = *S	Overloaded dereference operator returns copy of the value on top of the stack and has the same meaning as x = S.top() Precondition: stack must not be empty.
x = S	Returns copy of the top stack element. Same as x = *S Precondition: stack must not be empty.
*S = x	Dereference `operator` provides mutable access to the top element of the stack. Result of expression S = x is a copy of x. Precondition: stack must not be empty.
--S	Overloaded prefix decrement `operator--` pops top element from the stack. Expression --S returns the stack size after pop. Result of `--S` can be dereferenced: x = --S // 1. pops element from the stack; // 2. assigns the top value to x. --S = x // 1. pops element from the stack; // 2. assigns x to the top element. Precondition: stack must not be empty.
S--	Overloaded postfix decrement `operator--` pops top element from the stack. Expression S-- returns the stack size before pop. Result of `S--` can be dereferenced: x = S-- // 1. assigns top stack value to x; // 2. pops top element from stack. S-- = x // not very practical: // 1. assigns x to the stack top; // 2. pops the top element. Precondition: stack must not be empty.
+S	Overloaded unary plus `operator+` returns the size of the stack.

For example, program lambda_stack_decrement.cpp demonstrates overloaded prefix and postfix decrement operators for the stack primitive:

Keywords: lambda_stack_decrement.cpp, overloaded prefix postfix decrement operators, stack, const_scalar


// lambda_stack_decrement.cpp
// Program demonstrates usage of overloaded prefix and
// postfix decrement operators for lambda stack primitive.

#define CTTL_TRACE_RULES // automatically turns lambda tracing on

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

using namespace cttl;

int main(/*int argc, char* argv[]*/)
{
    lambda< int >::scalar Variable;// instantiate integer scalar
    lambda< int >::stack Stack;    // instantiate std::stack< int >
    (
        Stack = const_scalar( 2 )^3^4^5,
        //<top>5,4,3,2<bottom>
        CTTL_LAMBDA_ASSERT( +Stack == scalar( 4u ) ),
        CTTL_LAMBDA_ASSERT( *Stack == 5 ),
        Variable = *Stack--,
        //<top>4,3,2<bottom>
        CTTL_LAMBDA_ASSERT( Variable == 5 ),
        CTTL_LAMBDA_ASSERT( +Stack == scalar( 3u ) ),
        CTTL_LAMBDA_ASSERT( *Stack == 4 ),
        Variable = *--Stack,
        //<top>3,2<bottom>
        CTTL_LAMBDA_ASSERT( Variable == 3 ),
        CTTL_LAMBDA_ASSERT( +Stack == scalar( 2u ) ),
        CTTL_LAMBDA_ASSERT( *Stack == 3 ),
        *--Stack = 7, // pop, then assign new value to top element
        CTTL_LAMBDA_ASSERT( +Stack == scalar( 1u ) ),
        CTTL_LAMBDA_ASSERT( *Stack == 7 ),
        //<top>7<bottom>
        // first, the top of stack gets assigned new
        // value of 6, then it is thrown away by postfix decrement:
        *Stack-- = 6,
        //<top><bottom>
        CTTL_LAMBDA_ASSERT( +Stack == scalar( 0u ) )
    ).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.

<<< Scalar primitive

Lambda Home

Scalar interface >>>