- Boost - lists.boost.org

Lazy Metaprogramming Library [UPDATE]
by Vesa Karvonen 01 Nov '04

01 Nov '04

Hi, I have made some optimizations (resulting in an order of magnitude (10x) improvement in compile-time in some cases on GNU g++) to the library and implemented a couple of new metafunctions. The latest snapshot can now be downloaded from the Files Section (both zip and tar.bz for your convenience): http://groups.yahoo.com/group/boost/files/LazyMPL/ Please note that the library is only a proof-of-concept made in about 2 days. It should be quite possible to provide a more comprehensive library of lazy metafunctions and provide facilities like the lambda-facility of Boost MPL. (Also, you shouldn't worry about the upper case naming used in the library.) Lazy template metaprogramming, as shown by the lazy metaprogramming library, eliminates the number one stumbling block of template metaprogramming as described by every introduction or guide to template metaprogramming (e.g. http://www.boost.org/libs/mpl/doc/#applyif and Generative Programming section 10.11.1.3 Taking Advantage of Lazy Behavior (particularly pages 441-443... "You should remember this when writing static code" ;)). In lazy template metaprogramming, invocations (::type) are only needed when a value needs to be explicitly examined (e.g. to extract the head of a list). Use of the typename-keyword can be practically eliminated and forwarding (use of inheritance) is the usual way to implement functions. Explicit invocations can (are) also be used for optimizing lazy metafunctions, but optimizations are just optimizations. There is no need to optimize unless the metaprogram executes too slowly. It is likely that user metacode can rely on optimized library primitives for the most part. Regards, Vesa Karvonen <--- README-file ---> Lazy Metaprogramming Library ============================ Vesa Karvonen vesa_karvonen(a)hotmail.com This is a minimal proof-of-concept library that shows how one can implement lazy template metaprograms. Problem ------- Most contemporary template metaprogramming libraries are strict, which means that the result of a metafunction call is evaluated completely once the metafunction is invoked. Furthermore, metafunctions are written so that the arguments they receive are assumed to be completely evaluated. In addition to strictly evaluated function calls, most strict programming languages provide lazy control structures, such as `if' and `while', that evaluate their subexpressions only when needed. In contemporary template metaprogramming libraries, the separation between lazy control structures and strict metafunctions is often quite fuzzy, which can make programming quite confusing and burdensome. Basically, a programmer using a contemporary template metaprogramming library has to explicitly annotate the evaluation order of the metacode by carefully selecting when to invoke and when not to invoke a metafunction. The invocations can not simply be completely left out, because strict metafunctions do not accept uninvoked arguments. Solution -------- The metaprogramming style used in this library is different. Metafunctions and metadata structures (type lists) in this library are designed to be lazy. In particular, metafunctions assume that the arguments they receive are only delayed promises to compute the value of the argument once explicitly invoked. This change of style eliminates the need to constantly think about evaluation order. Metafunction invocations are only needed when a value explicitly needs to be examined. For example, the metafunction `HEAD<l>' evaluates to the head of the given list `l'. In order to do that, `HEAD' needs to explicitly invoke the parameter `l' to expose the list constructor `CONS' for pattern matching. However, and most importantly, callers of `HEAD' do not need to invoke the actual parameter for `HEAD'. (Explicit invocations can also be used for optimization, but it isn't strictly necessary.) In theory, the style used in this library could be the ideal way to implement template metaprograms, because the C++ standard almost requires template instantiations to be cached, which means that delayed promises are actually computed only once, saving CPU time. In other words, C++ implementations are almost required to perform memoization. In practice, however, the representation of type information may take a lot of memory and access to the instantiation cache isn't necessarily implemented efficiently. This can make lazy metaprograms less efficient in terms of time and space than their strict counterparts. Contents of the package ----------------------- The `inc/lazy_mpl' directory contains the library implementation. Only a minimal core plus a few higher-order functions on lists are provided. The list functions imitate the Haskell 98 standard prelude functions. The `test' directory contains a couple of ad hoc tests demonstrating the lazy programming style and the use of lazy lists. To get most out of the code, you should take a look at the unoptimized implementations of the higher-order list manipulation metafunctions `MAP', `FOLD[R|L]', `APPEND', `TAKE', `DROP', `ITERATE', `FILTER', and `ZIP_WITH'. As you can hopefully see, they are very cleanly expressed. That is how lazy metaprogramming would look like to a casual user. Future work ----------- This library is only a proof-of-concept. The intention is to show that lazy template metaprogramming is not only possible, but can yield both powerful and readable metaprograms. One important remaining issue would be to implement a lambda mechanism of some sort, which would make the use of higher-order metafunctions more convenient. Another issue would be to study how to best optimize lazy metafunctions. Many of the metafunctions in the library have been manually optimized by considering which of their arguments are strict (always invoked) and then making the implementation take advantage of the strictness by invoking the arguments early. The optimizations do not change the way the metafunctions are used (assuming the optimizations are correct), but can have a significant effect (order of magnitude) on performance. (I have not proven that the manually introduced optimizations are correct---I wouldn't be surprised if some of the optimization were incorrect.) Hopefully a good selection of optimized lazy metafunctions can practically eliminate the need for library users to manually optimize their code. At any rate, optimizations are only needed when a metaprogram evaluates too slowly. Copyright --------- (C) Copyright Vesa Karvonen 2004. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE.) _________________________________________________________________ Don't just search. Find. Check out the new MSN Search! http://search.msn.com/

2 1

[filesystem] regressions for operations_test
by JOAQUIN LOPEZ MU?Z 31 Oct '04

31 Oct '04

Hi, msvc, msvc-stlport, iw-7_1-vc6 and iw-7_1-vc6-stlp-4_5_3 currently fail this test (see for instance http://tinyurl.com/4xo4a) I don't know for sure, but I've got the hunch this might be related with the fact that 2004 is a leap year and today we've had a 1-hour adjustment in some countries due to the daylight saving policy. These two facts combined might yield an offset outside the expected range. Just wanted to note this in case it might ring a bell for somebody. Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

[serialization] The problems with CW...
by Rene Rivera 31 Oct '04

31 Oct '04

I took some time to take a closer look at what the current test failures could be about on the cw-8.3 compiler... before I go on vacation. Specifically I looked at the test_exported errors as those seemed to be common to both the 9 and 8 versions of CW. My findings... I managed to get the export tests to *pass* by modifying the test itself (see attached). The problems boils down to the behavior of CW to only instantiate templates when they are used. This not just applies to class templates, but to template methods. In the case of the exported tests it does not instantiate two important things: a) The serialize template method of non-directly referenced derived classes. Specifically for test_exported: polymorphic_derived1::serialize<test_oarchive>, polymorphic_derived1::serialize<test_iarchive>, polymorphic_derived2::serialize<test_oarchive>, and polymorphic_derived2::serialize<test_iarchive>. Forcing those to be instantiated generates all the rest of the self registration code for the derived classes. This still leaves: b) The archive serialization instance for the needed specializations is also not generated as they are not directly reference. Only the ones for the base class, polymorphic_base, are generated as that's the class used in the actual de/serialize calls. I'm not sure anything can be done about fixing this for the release as the only solutions I can come up with would involve changing the serialization interfaces. HTH. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq =================================================================== RCS file: /cvsroot/boost/boost/libs/serialization/test/test_exported.cpp,v retrieving revision 1.4 diff -u -r1.4 test_exported.cpp --- test_exported.cpp 22 Jul 2004 06:39:17 -0000 1.4 +++ test_exported.cpp 29 Oct 2004 19:36:07 -0000 @@ -40,6 +40,7 @@ class polymorphic_derived1 : public polymorphic_base { friend class boost::serialization::access; +public: template<class Archive> void serialize(Archive &ar, const unsigned int /* file_version */){ ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(polymorphic_base); @@ -49,10 +50,19 @@ }; BOOST_CLASS_EXPORT(polymorphic_derived1) +namespace { + void (polymorphic_derived1::* pd1so_p)(test_oarchive &,const unsigned int) = &polymorphic_derived1::serialize<test_oarchive>; + void (polymorphic_derived1::* pd1si_p)(test_iarchive &,const unsigned int) = &polymorphic_derived1::serialize<test_iarchive>; +} +template<> +const boost::archive::detail::pointer_iserializer<polymorphic_derived1, test_iarchive> boost::archive::detail::pointer_iserializer<polymorphic_derived1, test_iarchive>::instance; +template<> +const boost::archive::detail::pointer_oserializer<polymorphic_derived1, test_oarchive> boost::archive::detail::pointer_oserializer<polymorphic_derived1, test_oarchive>::instance; class polymorphic_derived2 : public polymorphic_base { friend class boost::serialization::access; +public: template<class Archive> void serialize(Archive &ar, const unsigned int /* file_version */){ ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(polymorphic_base); @@ -62,6 +72,14 @@ }; BOOST_CLASS_EXPORT(polymorphic_derived2) +namespace { + void (polymorphic_derived2::* pd2so_p)(test_oarchive &,const unsigned int) = &polymorphic_derived2::serialize<test_oarchive>; + void (polymorphic_derived2::* pd2si_p)(test_iarchive &,const unsigned int) = &polymorphic_derived2::serialize<test_iarchive>; +} +template<> +const boost::archive::detail::pointer_iserializer<polymorphic_derived2, test_iarchive> boost::archive::detail::pointer_iserializer<polymorphic_derived2, test_iarchive>::instance; +template<> +const boost::archive::detail::pointer_oserializer<polymorphic_derived2, test_oarchive> boost::archive::detail::pointer_oserializer<polymorphic_derived2, test_oarchive>::instance; // save exported polymorphic class void save_exported(const char *testfile)

4 4

[serialization] Plans for C++ standard style reference docs
by Andreas Huber 31 Oct '04

31 Oct '04

At the risk of asking something that has probably been asked before: Are there any plans to add C++ standard style reference documentation for serialization? The current tutorial & reference are good and probably describing most of what one would like to know about the library. However, at various places I would really have preferred a description of the exact effects of a particular function, complete with pre-/post-conditions and exceptions that could possibly be thrown. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

4 6

Circular log buffer
by Darren Cook 31 Oct '04

31 Oct '04

I'm finding an increasing need for an in-file memory log: specifically when my program asserts I want to see where it has been. There are two problems with normal logging, i.e. appending to a disk file: * The files get very, very big (I've filled my home partition before) * All that writing to disk slows the application down noticeably. I checked log4cpp and John Torjo's logging library and neither seem to offer this, but it seems it could fit as one of the logging targets. I had in mind an object that is a wrapper for e.g. a 1Mb char buffer with the same interface as std::ostream, so I can just write: log_buffer<<"In func1, x="<<x<<", obj="<<obj<<"\n"; And then when my program asserts I can pass log_buffer as a parameter to be output (requires it to have operator<< defined): SMART_ASSERT(y!=1)(y)(log_buffer); Does anyone know of anything along these lines? Does anyone have the same need, or just me? I found some circular buffers that nearly do what I want [1] [2] [3], but they are lower-level as they don't offer the ostream interface. (In my case I don't need thread-safety.) Darren [1]: http://www.codeguru.com/Cpp/Cpp/cpp_mfc/arrays/article.php/c4013/ [2]: http://www.codeguru.com/Cpp/Cpp/cpp_mfc/buffers/article.php/c859/ [3]: Thread-safe circular queue, CUJ, June 2004.

6 12

ATTN: Merging changes to the release branch
by Aleksey Gurtovoy 31 Oct '04

31 Oct '04

Folks, Can I gently ask everybody to be more careful with integration of changes from the main trunk to the release branch? If you have to do it, please double-check everything (in particular, run the diffs) before committing the merged files. We've already got the new "boost/index.html" contents with *1.33.0* section stub in the release branch, and dealing with more of something like this is not going to help the release. Thanks, -- Aleksey Gurtovoy MetaCommunications Engineering

8 7

[1.32 Release] Fixing tabs/links/filenames -- the last round
by Aleksey Gurtovoy 31 Oct '04

31 Oct '04

Dear All, I'd appreciate if you bear with me one more time and find a moment to fix the following issues ASAP (see http://www.meta-comm.com/engineering/boost/issues.html) algorithm --------- libs/algorithm/minmax/index.html: broken link: ../../../../boost/minmax.hpp, broken link: minmax_benchs.html assign ------ libs/assign/test/list_inserter.cpp: tabs in file libs/assign/test/list_of.cpp: tabs in file build ----- tools/build/v2/index.html: broken link: ../../../doc/html/bbv2.installation.html, broken link: doc/html/index.html tools/build/v2/test/railsys/program/Jamfile: tabs in file tools/build/v2/test/test_system.html: unlinked file BoostBook-generated, need to be fixed in sources: doc/html/bbv2/advanced/jamfiles.html: broken link: ../../doc/extending.html#main_target_rules doc/html/bbv2/extender.html: broken link: ../../../example/customization doc/html/bbv2/howto.html: broken link: ../../../../../more/mailing_lists.htm#jamboost doc/html/bbv2/installation.html: broken link: ../../../jam_src/index.html#building_bjam, broken link: ../../jam_src/index.html doc/html/bbv2/tutorial/prebuilt.html: broken link: ../../doc/recipes.html#site_config_targets date_time --------- boost/date_time/local_time/posix_time_zone.hpp: tabs in file boost/index.htm: broken link: libs/date_time/doc/Changes.html BoostBook-generated, need to be fixed in sources: doc/html/date_time/details.html: broken link: ../../../libs/tokenizer/index.htm doc/html/date_time/doxy.html: broken link: ../../../boost/date_time/dst_transition_day_generators.hpp, broken link: ../../../boost/date_time/local_time_base.hpp doc/html/date_time/posix_time.html: broken link: ../../../libs/date_time/doc/time_duration_inherit.png graph ----- boost/graph/adjacency_list.hpp: tabs in file boost/graph/detail/adjacency_list.hpp: tabs in file libs/graph/src/graphviz_digraph_parser.cpp: tabs in file libs/graph/src/graphviz_graph_parser.cpp: tabs in file boost/index.htm: broken link: libs/graph/doc/astar_search.html, broken link: libs/graph/doc/floyd_warshall_shortest.html, broken link: libs/graph/doc/fruchterman_reingold.html iterator -------- libs/iterator/doc/filter_iterator_ref.html: unlinked file libs/iterator/doc/indirect_iterator_ref.html: unlinked file libs/iterator/doc/issues.html: unlinked file libs/iterator/doc/iter-issue-list.html: unlinked file libs/iterator/doc/iterator_adaptor_ref.html: unlinked file libs/iterator/doc/make_filter_iterator.html: unlinked file libs/iterator/doc/ref_problem.html: unlinked file libs/iterator/doc/zip_iterator.html: broken link: ../example/zip_iterator_examples.cpp numeric ------- libs/numeric/conversion/doc/converter.html: broken link: udt_support.html libs/numeric/conversion/doc/converter_policies.html: broken link: udt_support.html python ------ libs/python/doc/new-conversions.html: unlinked file libs/python/doc/tutorial/doc/html/index.html: broken link: ../../index.htm, broken link: ../../more/faq.htm, broken link: ../../more/index.htm, broken link: ../../people/people.htm, broken link: libraries.html libs/python/doc/tutorial/doc/html/python/embedding.html: broken link: ../../../../building.html%20Building, broken link: ../../../index.htm, broken link: ../../../more/faq.htm, broken link: ../../../more/index.htm, broken link: ../../../people/people.htm, broken link: ../../v2/handle.html, broken link: ../../v2/handle.html#allow_null-spec, broken link: ../libraries.html libs/python/doc/tutorial/doc/html/python/exception.html: broken link: ../../../index.htm, broken link: ../../../more/faq.htm, broken link: ../../../more/index.htm, broken link: ../../../people/people.htm, broken link: ../libraries.html libs/python/doc/tutorial/doc/html/python/exposing.html: broken link: ../../../index.htm, broken link: ../../../more/faq.htm, broken link: ../../../more/index.htm, broken link: ../../../people/people.htm, broken link: ../libraries.html libs/python/doc/tutorial/doc/html/python/functions.html: broken link: ../../../index.htm, broken link: ../../../more/faq.htm, broken link: ../../../more/index.htm, broken link: ../../../people/people.htm, broken link: ../libraries.html libs/python/doc/tutorial/doc/html/python/hello.html: broken link: ../../../index.htm, broken link: ../../../more/faq.htm, broken link: ../../../more/index.htm, broken link: ../../../people/people.htm, broken link: ../libraries.html libs/python/doc/tutorial/doc/html/python/iterators.html: broken link: ../../../index.htm, broken link: ../../../more/faq.htm, broken link: ../../../more/index.htm, broken link: ../../../people/people.htm, broken link: ../libraries.html libs/python/doc/tutorial/doc/html/python/object.html: broken link: ../../../index.htm, broken link: ../../../more/faq.htm, broken link: ../../../more/index.htm, broken link: ../../../people/people.htm, broken link: ../libraries.html libs/python/doc/tutorial/doc/html/python/techniques.html: broken link: ../../../index.htm, broken link: ../../../more/faq.htm, broken link: ../../../more/index.htm, broken link: ../../../people/people.htm, broken link: ../libraries.html libs/python/doc/v2/bibliography.html: unlinked file libs/python/doc/v2/errors.html: broken link: ../../../function/doc/reference.html#functionN libs/python/doc/v2/faq.html: broken link: ../tutorial/doc/creating_packages.html, broken link: ../tutorial/doc/reducing_compiling_time.html libs/python/doc/v2/from_python.html: unlinked file libs/python/doc/v2/header.html: unlinked file libs/python/doc/v2/overview.html: unlinked file libs/python/doc/v2/pickle.html: broken link: ../tutorial/doc/extending_wrapped_objects_in_python.html libs/python/doc/v2/rationale.html: broken link: ../../../../../people/dave_abrahams.htm, unlinked file libs/python/pyste/doc/introduction.html: broken link: ../../doc/tutorial/doc/exposing_classes.html libs/python/pyste/doc/policies.html: broken link: ../../doc/tutorial/doc/call_policies.html libs/python/pyste/doc/running_pyste.html: broken link: ../../doc/tutorial/doc/building_hello_world.html libs/python/pyste/index.html: broken link: introduction.html range ----- libs/range/doc/intro.html: unlinked file regex ----- libs/regex/performance/input.html: unlinked file serialization ------------- libs/serialization/doc/contents.html: broken link: definitions.html, broken link: doc/configuration.html, broken link: faq.html, invalid character in URL: overview.html#Other implementations libs/serialization/doc/serialization.html: broken link: ../../../boost/serialization/shared_count.hpp, broken link: bibliograph.html#14 libs/serialization/src/basic_iarchive.cpp: tabs in file libs/serialization/test/Jamfile: tabs in file libs/serialization/test/test_non_default_ctor2.cpp: tabs in file libs/serialization/vc7ide/Boost Serialization Library.sln: nonportable path libs/serialization/vc7ide/Boost Serialization Library.suo: nonportable path signals ------- boost/signals/signal_template.hpp: tabs in file boost/signals/slot.hpp: tabs in file libs/signals/src/signal_base.cpp: tabs in file libs/signals/src/slot.cpp: tabs in file thread ------ libs/thread/src/xtime.cpp: invalid (cr only) line-ending utility ------- boost/utility/base_from_member.hpp: tabs in file libs/utility/generator_iterator.htm: unlinked file libs/utility/operators.htm: broken link: function_output_iterator.htm TIA, -- Aleksey Gurtovoy MetaCommunications Engineering

5 15

guidelines on portable 'catch(...)' usage
by Stefan Seefeld 30 Oct '04

30 Oct '04

hi there, I'v recently run into a problem with 'catch(...)' on MSVC 7.1, where a segmentation fault resulted in a 'first-class exception' (!) that was caught by 'catch(...)' even though the stack wasn't unwound. My first reaction was to abandon the use of 'catch(...)' entirely, replacing it with a more specific equivalent (which I believe to be better practice anyways). However, browsing some boost code I now find other people using such catch-all statements, and so I'd like to get your feedback on how to use it portably. Are my findings false concerning MSVC's highjacked use of C++ exceptions for program errors (i.e. POSIX' equivalent of signals) ? Thanks, Stefan

8 7

teststreams.cpp and VC8.0
by Victor A. Wagner Jr. 30 Oct '04

30 Oct '04

I got tired of getting the exceptions so I fixed time_formatters.hpp which had a logic error in it. It's possible that the test should now be run on all platforms again. Since I don't know how to alter which tests actually run on which platforms I cannot fix that. Victor A. Wagner Jr. http://rudbek.com The five most dangerous words in the English language: "There oughta be a law"

6 11

reverse_iterator_example binaries cleanup
by Aleksey Gurtovoy 30 Oct '04

30 Oct '04

Martin, Could you please remove "reverse_iterator_example" test binaries ("libs/utility/reverse_iterator_example") for the next regression run? I've moved this and other iterator examples over to "libs/iterator/test", not the least so that the report tools have a chance to correctly report their failures. TIA, -- Aleksey Gurtovoy MetaCommunications Engineering

1 0