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