1[/==============================================================================
2    Copyright (c) 2000-2003 Brian McNamara and Yannis Smaragdakis
3    Copyright (C) 2001-2010 Joel de Guzman
4    Copyright (C) 2001-2005 Dan Marsden
5    Copyright (C) 2001-2010 Thomas Heller
6    Copyright (C) 2014-2015 John Fletcher
7
8    Distributed under the Boost Software License, Version 1.0. (See accompanying
9    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
10===============================================================================/]
11
12[section Lazy List]
13
14[h1 Summary]
15Phoenix 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.
16
17     list<int> example;
18
19A 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.
20
21Exceptions 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.
22
23This is an extension to Boost Phoenix which does not change the public interface except to define new features in the namespace
24
25    boost::phoenix
26
27It has to be explicitly included using the header
28
29    boost/phoenix/function/lazy_prelude.hpp
30
31[/section Introduction]
32[h1 Introduction]
33
34Boost 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.
35
36There 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.
37
38Progress is being made in implementing both the basic list<T> and the functions needed to manipulate lists.
39
40[/endsect]
41
42[section Background]
43
44The 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 much 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.
45
46At 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__.
47
48After 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 increase 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.
49
50John 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__.
51
52In 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.
53
54[endsect]
55
56[section What is provided]
57
58Functions are provided to build and manipulate objects of the list type
59
60    list<T>
61
62[h2 Namespace and header]
63
64The functions are in the namespace
65
66    boost::phoenix
67
68defined by the header file
69
70    boost/phoenix/function/lazy_prelude.hpp
71
72which includes all other needed headers. It is not currently included in
73
74    boost/phoenix/function.hpp
75
76so it must be explicitly included to use these types and functions.
77
78[h2 Integration with Boost Phoenix]
79
80The 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.
81
82[h1 Lazy List Type]
83
84     list<T> (where T is the element type)
85
86[h1 Functions]
87
88The functions are grouped as follows:
89
90[h2 Arithmetic functions]
91
92     plus
93     minus
94     multiplies
95     divides
96     modulus
97     negate
98
99[h2 Boolean functions]
100
101     equal
102     not_equal
103     greater
104     less
105     greater_equal
106     less_equal
107
108[h2 Logical functions]
109
110     logical_and
111     logical_or
112     logical_not
113
114[h2 Operational functions]
115
116     apply
117     until
118     until2
119     max
120     min
121     inc
122     dec
123     make_pair
124
125[h2 Logical predicates]
126
127     odd
128     even
129
130[h2 List Functions]
131
132     cons
133     cat
134     take
135     drop
136     last
137     all_but_last
138     at
139     length
140     filter
141
142[h3 List Generation Functions]
143
144     enum_from
145     enum_from_to
146     list_with
147
148[h2 Futher functions]
149
150Further functions are in development from the resources available in __fcpp__.
151
152[endsect]
153
154[section Tutorial with examples]
155
156These examples require the following header:
157
158    boost/phoenix/function/lazy_prelude.hpp
159
160The following statements should be in the execution code:
161
162    using boost::phoenix::arg_names::arg1;
163    using boost::phoenix::arg_names::arg2;
164    using namespace boost::phoenix;
165
166
167[section Arithmetic functions]
168
169Assume the values
170
171    int a = 123;
172    int b = 256;
173
174The following are all valid expressions returning a+b
175
176    plus(arg1, arg2)(a, b)
177    plus(arg1, b)(a)
178    plus(a, arg2)(a,b)
179    plus(a, arg1)(b)
180    plus(a, b)()
181
182The expressions can be combined like this
183
184    plus(minus(a, b),b)()
185    plus(minus(arg1, b),b)(a)
186    plus(minus(arg1, arg2),b)(a,b)
187    plus(minus(arg1, arg2),arg2)(a,b)
188
189Other numerical operators can be used like this
190
191    multiplies(arg1,arg2)(3,6)
192    divides(arg2,arg1)(3,6)
193    modulus(arg2,arg1)(4,6)
194    min(arg1,arg2)(4,6)
195    max(arg1,arg2)(4,6)
196    inc(arg1)(a)
197    dec(arg1)(a)
198    negate(arg1)(a)
199
200[endsect]
201
202[section List Generation]
203
204One 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
205
206    enum_from(1)
207
208which returns the generator for integers 1,2,3,..... infinity.
209
210    take(4,enum_from(1))
211
212returns a list of the first 4 of the list.
213
214    at(enum_from(1),3)
215
216returns the fourth member using zero indexed access. Both of the lists returned are lazy and only evaluated when the list members are accessed.
217
218[endsect]
219
220To be developed.
221
222[endsect]
223
224[section Exceptions]
225
226Exceptions are used when there is a danger of a runaway or illegal operations on an empty list.
227
228The key example is to take the length of a non-terminating list, e.g.
229
230    length(enum_from(1))
231
232This is protected using an exception:
233
234    lazy_exception
235
236Note that this is implemented such that defining
237
238    BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
239
240will enable the user to turn off the exceptions at their own risk.
241
242    BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH
243
244is currently defined as 1000 and again the user can define their own value.
245
246In the length function this how it is implemented:
247
248          struct Length {
249            template <typename Sig> struct result;
250
251            template <typename This, typename L>
252            struct result<This(L)>
253            {
254               typedef size_t type;
255            };
256
257            template <class L>
258            size_t operator()( const L& ll ) const {
259              typename L::delay_result_type l = delay(ll);
260              size_t x = 0;
261              while( !null(l)() ) {
262                  l = tail(l);
263                  ++x;
264                  if (x > BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH)
265                     break;
266              }
267  #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
268              if (x > BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH)
269                   throw lazy_exception("Your list is too long!!");
270  #endif
271              return x;
272            }
273          };
274
275[endsect]
276
277[section Implementation Details]
278
279[h2 Introduction]
280The 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.
281
282__fcpp__ uses a combination of polymorphic and single type functions which can be passed as arguments to other functions.
283
284The 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>.
285
286The 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.
287
288[h2 FC++ legacy]
289
290The __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.
291
292[h2 Polymorphic Function Types]
293
294Functions are implemented as a struct within namespace impl. For an example funcion 'x' the type is defined like this:
295
296    typedef boost::phoenix::function<impl::X> X;
297    X x
298
299This alternative will work to provide a function 'x' but it is not then possible to pass it as an argument.
300
301    BOOST_PHOENIX_ADAPT_CALLABLE(x, impl::X, 1)
302
303[h3 Implementation Example]
304
305This example implements id() which simply returns its argument:
306
307    namespace impl {
308
309      struct Id
310      {
311        template <typename Sig>
312        struct result;
313
314        template <typename This, typename A0>
315        struct result<This(A0)>
316           : boost::remove_reference<A0>
317        {};
318
319        template <typename A0>
320        A0 operator()(A0 const & a0) const
321        {
322            return a0;
323        }
324
325      };
326
327    }
328
329    typedef boost::phoenix::function<impl::Id> Id;
330    Id id;
331
332[h2 Functions with defined return type]
333
334Sometimes it is necessary to define a function using a templated struct, where the template parameter type defines the return type.
335
336[h3 Example with one argument]
337
338  namespace impl {
339
340    template <typename Result>
341    struct what {
342
343      typedef Result result_type;
344
345      Result operator()(Result const & r) const
346      {
347        return r;
348      }
349    };
350
351  }
352
353  boost::function1<int, int > what_int = impl::what<int>();
354  typedef boost::function1<int,int> fun1_int_int;
355  typedef boost::phoenix::function<fun1_int_int> What_arg;
356  What_arg what_arg(what_int);
357
358[h3 Example with zero arguments]
359
360  namespace impl {
361    template <typename Result>
362    struct what0 {
363
364      typedef Result result_type;
365
366      Result operator()() const
367      {
368        return Result(100);
369      }
370
371    };
372  }
373
374  typedef boost::function0<int> fun0_int;
375  boost::function0<int> what0_int = impl::what0<int>();
376  typedef boost::phoenix::function<fun0_int> What0_arg;
377  What0_arg what0_arg(what0_int);
378
379[h2 List Generation Implementation]
380
381The implementation of the function
382
383    enum_from(1)
384
385requires a functor which will evaluate the successive numbers on demand. The code from __fcpp__ has been reimplemented using internal functors as follows.
386
387This code has to carefully manipulate the input type T to construct the result type which is a list.
388
389The 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.
390
391          template <class T>
392          struct EFH
393          {
394              mutable T x;
395              EFH( const T& xx) : x(xx) {}
396              template <typename Sig> struct result;
397
398              template <typename This, class TT>
399              struct result<This(TT)>
400              {
401                typedef typename boost::phoenix::UseList::template
402                        List<TT>::type LType;
403                typedef typename boost::phoenix::result_of::
404                        ListType<LType>::delay_result_type type;
405              };
406              typename result<EFH(T)>::type operator()() const {
407                typedef typename UseList::template List<T>::type LType;
408                typedef typename result_of::ListType<LType>::
409                        delay_result_type result_type;
410                typedef boost::function0<result_type> fun1_R_TTT;
411                ++x;
412                fun1_R_TTT efh_R_TTT = EFH<T>(x);
413                typedef boost::phoenix::function<fun1_R_TTT> EFH_R_T;
414                EFH_R_T efh_R_T(efh_R_TTT);
415    #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
416                if (x > BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH)
417                     throw lazy_exception("Running away in EFH!!");
418    #endif
419                return cons( x-1, efh_R_T() );
420              }
421          };
422
423          struct Enum_from {
424             template <typename Sig> struct result;
425
426             template <typename This, typename T>
427             struct result<This(T)>
428             {
429               typedef typename boost::remove_reference<T>::type TT;
430               typedef typename boost::remove_const<TT>::type TTT;
431               typedef typename UseList::template List<TTT>::type LType;
432               typedef typename result_of::ListType<LType>::
433                       delay_result_type type;
434             };
435
436             template <class T>
437             typename result<Enum_from(T)>::type operator()
438                (const T & x) const
439              {
440                typedef typename boost::remove_reference<T>::type TT;
441                typedef typename boost::remove_const<TT>::type TTT;
442                typedef typename UseList::template List<T>::type LType;
443                typedef typename result_of::ListType<LType>::
444                        delay_result_type result_type;
445                typedef boost::function0<result_type> fun1_R_TTT;
446                fun1_R_TTT efh_R_TTT = EFH<TTT>(x);
447                typedef boost::phoenix::function<fun1_R_TTT> EFH_R_T;
448                EFH_R_T efh_R_T(efh_R_TTT);
449                //std::cout << "enum_from (" << x << ")" << std::endl;
450                return efh_R_T();
451              }
452          };
453
454Similar code is used in the related functors
455
456          enum_from_to
457          filter
458
459[h2 Conclusion]
460
461These implementation mechanisms have been carried through consistently in the implementation.
462
463[endsect]
464
465[section Testing]
466
467Several tests are currently on develop and master in time for Boost 1.58.0.
468
469[endsect]
470
471[section Where Next?]
472
473Further functions are going to be implemented and more examples provided.
474
475[endsect]
476
477
478[endsect]
479
480