bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / phoenix / doc / lazy_list.qbk

[/==============================================================================
    Copyright (c) 2000-2003 Brian McNamara and Yannis Smaragdakis
    Copyright (C) 2001-2010 Joel de Guzman
    Copyright (C) 2001-2005 Dan Marsden
    Copyright (C) 2001-2010 Thomas Heller
    Copyright (C) 2014-2015 John Fletcher

    Distributed under the Boost Software License, Version 1.0. (See accompanying
    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
===============================================================================/]

[section Lazy List]

[h1 Summary]
Phoenix now has a lazy list implementation which is very similar but not identical to the implementation provided by __fcpp__. This provides a set of objects defined by list<type>, for example this which defines an empty list of type int.

     list<int> example;

A list can contain zero or more elements of the same type. It can also be declared using a function returning values of the correct type. Such lists are only evaluated on demand. A set of functions are defined which enable many ways of manipulating and using lists. Examples are provided for the features available.

Exceptions are provided to deal with certain cases and these can be turned off if desired. There is a check on the maximum list length which has a default of 1000 which can be changed by the user.

This is an extension to Boost Phoenix which does not change the public interface except to define new features in the namespace

    boost::phoenix

It has to be explicitly included using the header

    boost/phoenix/function/lazy_prelude.hpp

[/section Introduction]
[h1 Introduction]

Boost Phoenix provides many features of functional_programming. One of the things which has been missing until now is a lazy list implementation.  One is available in the library __fcpp__ which although not part of Boost has many similarities. It has been possible to reimplement the strategy of the __fcpp_list__ using the facilties in Phoenix. This provides something which has up until now not been available anywhere in Phoenix and probably not anywhere else in Boost. This new implementation is very well integrated with other features in Phoenix as it uses the same mechanism. In turn that is well integrated with Boost Function.

There is a great deal of material in __fcpp__ and it is not proposed to replicate all of it. A great deal has changed since __fcpp__ was written and many things are already available in Phoenix or elsewhere. The emphasis here is to add to Phoenix in a way which will make it easier to implement functional_programming.

Progress is being made in implementing both the basic list<T> and the functions needed to manipulate lists.

[/endsect]

[section Background]

The original code of __fcpp__ was developed by Brian McNamara and Yannis Smaragdakis between 2000 and 2003. One of the aims of their work was to implement as mich as possible of the Haskell prelude in C++. In the end they achieved a very large part of that and went on to implement other similar things not in the Haskell prelude. This was made up of a large amount of code written very carefully in a consistent style which made it easy to extend it to provide more facilities.

At the end of that time, two versions of it existed, FC++ 1.5 and __boost_fcpp__ which was proposed for inclusion in Boost and rejected. Both are documented on __fcpp__.

After 2003 John Fletcher spent a lot of time developing both these versions and adding new features to them. One of the reasons intially was that the existing versions could handle only a small number of function arguments. He was able to inclrease the limit on the number of arguments and use the new version to implement a number of new ideas. No new release has ever been made although a draft release 1.5.2 exists. Much of his activity is documented by __functoids_in_cpp__ where some discussion took place with other people about this work.

John discussed with Joel de Guzman how to make __fcpp__ compatible with Phoenix. Joel suggested using Phoenix as a basis for a new version of __fcpp__.

In 2014 John became the maintainer of Phoenix and after spending time getting to know it he has now started to fulfil his idea of a new version of __fcpp__. What is emerging is significantly different from __fcpp__ in the detail of the implementation. In some ways it will be more powerful as it is well integrated with the facilities of Phoenix. In other ways it will lack some features of __fcpp__ as they can now be implemented in other ways.

[endsect]

[section What is provided]

Functions are provided to build and manipulate objects of the list type

    list<T>

[h2 Namespace and header]

The functions are in the namespace

    boost::phoenix

defined by the header file

    boost/phoenix/function/lazy_prelude.hpp

which includes all other needed headers. It is not currently included in 

    boost/phoenix/function.hpp

so it must be explicitly included to use these types and functions.

[h2 Integration with Boost Phoenix]

The functions are defined by boost::phoenix::function which means that they work with phoenix arguments such as 'arg1'. They have been defined in such a way that when needed they can be passed as arguments to other functions.

[h1 Lazy List Type]

     list<T> (where T is the element type)

[h1 Functions]

The functions are grouped as follows:

[h2 Arithmetic functions]

     plus
     minus
     multiplies
     divides
     modulus
     negate
     
[h2 Boolean functions]

     equal
     not_equal
     greater
     less
     greater_equal
     less_equal

[h2 Logical functions]

     logical_and
     logical_or
     logical_not

[h2 Operational functions]

     apply
     until
     until2
     max
     min
     inc
     dec
     make_pair

[h2 Logical predicates]

     odd
     even

[h2 List Functions]

     cons
     cat
     take
     drop
     last
     all_but_last
     at
     length
     filter

[h3 List Generation Functions]

     enum_from
     enum_from_to
     list_with

[h2 Futher functions]

Further functions are in development from the resources available in __fcpp__.

[endsect]

[section Tutorial with examples]

These examples require the following header:

    boost/phoenix/function/lazy_prelude.hpp

The following statements should be in the execution code:

    using boost::phoenix::arg_names::arg1;
    using boost::phoenix::arg_names::arg2;
    using namespace boost::phoenix;


[section Arithmetic functions]

Assume the values

    int a = 123;
    int b = 256;

The following are all valid expressions returning a+b

    plus(arg1, arg2)(a, b)
    plus(arg1, b)(a)
    plus(a, arg2)(a,b)
    plus(a, arg1)(b)
    plus(a, b)()

The expressions can be combined like this

    plus(minus(a, b),b)()
    plus(minus(arg1, b),b)(a)
    plus(minus(arg1, arg2),b)(a,b)
    plus(minus(arg1, arg2),arg2)(a,b)

Other numerical operators can be used like this

    multiplies(arg1,arg2)(3,6)
    divides(arg2,arg1)(3,6)
    modulus(arg2,arg1)(4,6)
    min(arg1,arg2)(4,6)
    max(arg1,arg2)(4,6)
    inc(arg1)(a)
    dec(arg1)(a)
    negate(arg1)(a)

[endsect]

[section List Generation]

One of the most interesting capabilities of __fcpp__ is the generation of infinite lazy lists which are evaluated only at need. The most simple example of this is 

    enum_from(1)

which returns the generator for integers 1,2,3,..... infinity.

    take(4,enum_from(1))

returns a list of the first 4 of the list.

    at(enum_from(1),3)

returns the fourth member using zero indexed access. Both of the lists returned are lazy and only evaluated when the list members are accessed.

[endsect]

To be developed.

[endsect]

[section Exceptions]

Exceptions are used when there is a danger of a runaway or illegal operations on an empty list.

The key example is to take the length of a non-terminating list, e.g.

    length(enum_from(1))

This is protected using an exception:

    lazy_exception

Note that this is implemented such that defining

    BOOST_PHOENIX_NO_LAZY_EXCEPTIONS

will enable the user to turn off the exceptions at their own risk.

    BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH

is currently defined as 1000 and again the user can define their own value.

In the length function this how it is implemented:

          struct Length {
            template <typename Sig> struct result;

            template <typename This, typename L>
            struct result<This(L)>
            {
               typedef size_t type;
            };

            template <class L>
            size_t operator()( const L& ll ) const {
              typename L::delay_result_type l = delay(ll);
              size_t x = 0;
              while( !null(l)() ) {
                  l = tail(l);
                  ++x;
                  if (x > BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH)
                     break;
              }
  #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
              if (x > BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH)
                   throw lazy_exception("Your list is too long!!");
  #endif
              return x;
            }
          };

[endsect]

[section Implementation Details]

[h2 Introduction]
The implementation has depended on close study of the existing code of __fcpp__. The __fcpp_list__ is a carefully crafted code which allows for efficient processing of a number of different cases. In particular it makes use of the __fcpp_reusers__ for processing of repetitive evaluations.

__fcpp__ uses a combination of polymorphic and single type functions which can be passed as arguments to other functions.

The implementation of list<T> has needed new implementations of the strategy using the facilities of Boost Phoenix and also Boost Function. It turns out that a combination of both can be used to meet the needs of list<T>.

The fact that the functions are defined by boost::phoenix::function means that they work with phoenix arguments such as 'arg1'. This is the fact which ensures the flexibility needed for the user to build new functions as needed.

[h2 FC++ legacy]

The __fcpp_list__ and the __fcpp_reusers__ have been followed very closely in building this code. The version used as the starting point was the __boost_fcpp__ version.

[h2 Polymorphic Function Types]

Functions are implemented as a struct within namespace impl. For an example funcion 'x' the type is defined like this:

    typedef boost::phoenix::function<impl::X> X;
    X x

This alternative will work to provide a function 'x' but it is not then possible to pass it as an argument.

    BOOST_PHOENIX_ADAPT_CALLABLE(x, impl::X, 1)

[h3 Implementation Example]

This example implements id() which simply returns its argument:

    namespace impl {

      struct Id
      {
        template <typename Sig>
        struct result;

        template <typename This, typename A0>
        struct result<This(A0)>
           : boost::remove_reference<A0>
        {};

        template <typename A0>
        A0 operator()(A0 const & a0) const
        {
            return a0;
        }

      };

    }

    typedef boost::phoenix::function<impl::Id> Id;
    Id id;

[h2 Functions with defined return type]

Sometimes it is necessary to define a function using a templated struct, where the template parameter type defines the return type.

[h3 Example with one argument]

  namespace impl {

    template <typename Result>
    struct what {

      typedef Result result_type;

      Result operator()(Result const & r) const
      {
        return r;
      }
    };

  }

  boost::function1<int, int > what_int = impl::what<int>();
  typedef boost::function1<int,int> fun1_int_int;
  typedef boost::phoenix::function<fun1_int_int> What_arg;
  What_arg what_arg(what_int);

[h3 Example with zero arguments]

  namespace impl {
    template <typename Result>
    struct what0 {

      typedef Result result_type;

      Result operator()() const
      {
        return Result(100);
      }

    };
  }

  typedef boost::function0<int> fun0_int;
  boost::function0<int> what0_int = impl::what0<int>();
  typedef boost::phoenix::function<fun0_int> What0_arg;
  What0_arg what0_arg(what0_int);

[h2 List Generation Implementation]

The implementation of the function

    enum_from(1)

requires a functor which will evaluate the successive numbers on demand. The code from __fcpp__ has been reimplemented using internal functors as follows.

This code has to carefully manipulate the input type T to construct the result type which is a list.

The code in EFH is used to build a series of objects which each add one element to the list and return the function which will add the next element. That only gets called when it is needed.

          template <class T>
          struct EFH
          {
              mutable T x;
              EFH( const T& xx) : x(xx) {}
              template <typename Sig> struct result;

              template <typename This, class TT>
              struct result<This(TT)>
              {
                typedef typename boost::phoenix::UseList::template
                        List<TT>::type LType;
                typedef typename boost::phoenix::result_of::
                        ListType<LType>::delay_result_type type;
              };
              typename result<EFH(T)>::type operator()() const {
                typedef typename UseList::template List<T>::type LType;
                typedef typename result_of::ListType<LType>::
                        delay_result_type result_type;
                typedef boost::function0<result_type> fun1_R_TTT;
                ++x;
                fun1_R_TTT efh_R_TTT = EFH<T>(x);
                typedef boost::phoenix::function<fun1_R_TTT> EFH_R_T;
                EFH_R_T efh_R_T(efh_R_TTT);
    #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
                if (x > BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH)
                     throw lazy_exception("Running away in EFH!!");
    #endif
                return cons( x-1, efh_R_T() );
              }
          };

          struct Enum_from {
             template <typename Sig> struct result;

             template <typename This, typename T>
             struct result<This(T)>
             {
               typedef typename boost::remove_reference<T>::type TT;
               typedef typename boost::remove_const<TT>::type TTT;
               typedef typename UseList::template List<TTT>::type LType;
               typedef typename result_of::ListType<LType>::
                       delay_result_type type;
             };

             template <class T>
             typename result<Enum_from(T)>::type operator()
                (const T & x) const
              {
                typedef typename boost::remove_reference<T>::type TT;
                typedef typename boost::remove_const<TT>::type TTT;
                typedef typename UseList::template List<T>::type LType;
                typedef typename result_of::ListType<LType>::
                        delay_result_type result_type;
                typedef boost::function0<result_type> fun1_R_TTT;
                fun1_R_TTT efh_R_TTT = EFH<TTT>(x);
                typedef boost::phoenix::function<fun1_R_TTT> EFH_R_T;
                EFH_R_T efh_R_T(efh_R_TTT);
                //std::cout << "enum_from (" << x << ")" << std::endl;
                return efh_R_T();
              }
          };
 
Similar code is used in the related functors

          enum_from_to
          filter

[h2 Conclusion]

These implementation mechanisms have been carried through consistently in the implementation.

[endsect]

[section Testing]

Several tests are currently on develop and master in time for Boost 1.58.0.

[endsect]

[section Where Next?]

Further functions are going to be implemented and more examples provided.

[endsect]


[endsect]