Subject: Lazy MPL, strictness analysis
From: David Abrahams <[email-masked]>
To: Aleksey Gurtovoy <[email-masked]>, Vesa Karvonen <[email-masked]>
Date: Wed, 22 Oct 2008 16:02:38 -0400

Hi Both,

I got interested in the sieve recently, since I had such trouble
translating the classical algorithm to TMP... so I searched around and
found

http://www.haskell.org/pipermail/haskell-cafe/2007-February/022666.html

and then decided to try my hand at a Vesa-style "Lazy MPL"
implementation.  It's a lot of fun programming this way!  I came up with
the enclosed, which I've explicitly made strict by adding ::type in
several places.  However, it's still "too slow."  I never found an
easily-comprehensible explanation of how to do strictness analysis as
described by Vesa in
http://listarchives.boost.org/Archives/boost/2004/11/75057.php, so my attempts
are addmittedly shots in the dark.  It's certainly possible to hurt the
performance by making the wrong things strict, as I found out (try
replacing top<X> by X::type::top).

Anyway, I would love to get any insights you may have.

Regards,

// Copyright David Abrahams 2008. 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)

template <bool x>
struct bool_
{
    static const bool value = x;
    typedef bool_ type;
};

typedef bool_<false> false_;
typedef bool_<true> true_;

template <long x>
struct int_
{
    static const long value = x;
    typedef int_ type;
};

template <class X, class Y>
struct plus
    : int_<(X::type::value + Y::type::value)>
{};

template <class X, class Y>
struct multiplies
    : int_<(X::type::value * Y::type::value)>
{};

template <class X>
struct square
    : int_<(X::type::value * X::type::value)>
{};

template <class X>
struct inc
    : int_<(X::type::value + 1)>
{};

template <class X, class Y>
struct equal
    : bool_<(X::type::value == Y::type::value)>
{};

template <class X>
struct equal<X,X>
    : true_
{};

struct nil
{
    typedef nil type;
};

template <class C, class T, class F = void>
struct if_
    : if_<bool_<C::type::value>, T, F>
{};

template <class T, class F>
struct if_<true_,T,F>
    : T
{
};

template <class T>
struct if_<true_,T,void>
{
    template <class>
    struct else_ : T {};

    template <class, class, class = void>
    struct elif : T {};
};

template <class T, class F>
struct if_<false_,T,F>
    : F
{
};

template <class T>
struct if_<false_,T,void>
{
    template <class F2>
    struct else_ : F2 {};

    template <class C, class T2, class F2 = void>
    struct elif : if_<C,T2,F2> {};
};

template <class A, class B>
struct less
    : bool_<(A::type::value < B::type::value)>
{};

template <class V, class L = nil, class R = nil>
struct heap
{
    typedef heap<typename V::type, typename L::type, typename R::type> type;
    typedef V top;
    typedef L left;
    typedef R right;
};

#if 0  // never used
template <class Heap>
struct left : Heap::type::left {};

template <class Heap>
struct right : Heap::type::right {};
#endif

template <class Heap>
struct top : Heap::type::top {};

template <class T, class U>
struct same_ : false_ {};

template <class T>
struct same_<T,T> : true_ {};

template <class T, class U>
struct same
    : same_<typename T::type, typename U::type>
{};

template <class A, class B>
struct or_
    : if_<A,A,B> {};

template <class A>
struct not_
    : if_<A,false_,true_> {};

template <class A, class B>
struct and_ : if_<A,B,false_> {};

template <class Heap>
struct pop
    : pop<typename Heap::type> // Decode the structure of the heap type
{
};

template <class V>
struct pop<heap<V,nil,nil> >
    : nil {};

template <class V, class L>
struct pop<heap<V,L,nil> >
    : L {};

template <class V, class R>
struct pop<heap<V,nil,R> >
    : R {};

template <class V, class L, class R>
struct pop<heap<V,L,R> >
    : if_<
          less<typename L::type::top, typename R::type::top >
        , heap<typename L::type::top, pop<L>, R>
        , heap<typename R::type::top, L, pop<R> >
      >
{};
          
template <class T, class U>
struct min : if_<less<U,T>, U, T>::type {};

template <class T, class U>
struct max : if_<less<U,T>, T, U>::type {};

template <class Heap, class Value>
struct push
    : push<typename Heap::type, Value>::type
{};

template <class Value>
struct push<nil, Value>
    : heap<Value,nil,nil>
{};

template <class Top, class Value>
struct push<heap<Top,nil,nil>, Value>
    : heap<
          min<Top,Value>
        , heap<max<Top,Value> >
      >
{};

template <class Top, class L, class Value>
struct push<heap<Top,L,nil>, Value>
    : heap<
          typename min<Top,Value>::type
        , push<L, typename max<Top,Value>::type>
      >
{};

template <class Top, class R, class Value>
struct push<heap<Top,nil,R>, Value>
    : heap<
          typename min<Top,Value>::type
        , nil
        , push<R, typename max<Top,Value>::type>
      >
{};

template <class Top, class L, class R, class Value>
struct push<heap<Top,L,R>, Value>
    : if_<
          less<typename L::type::top,typename R::type::top >
        , heap<
              typename min<Top,Value>::type
            , push<L, typename max<Top,Value>::type >
            , R
          >
        , heap<
              typename min<Top,Value>::type
            , L
            , push<R, typename max<Top,Value>::type >
          >
      >
{};

template <
    class Value,
    class Increment
>
struct iterator : Value
{
    typedef iterator type;
    typedef Value val;
    typedef Increment incr;
};

template <class Iter>
struct deref
    : Iter::type::val {};

template <class Iter>
struct get_incr
    : Iter::type::incr {};

template <class Iter>
struct iter_increment
    : iterator<
          plus<deref<Iter>, get_incr<Iter> >
        , get_incr<Iter>
      >
{};

template <class A, class B>
struct pair
{
    typedef pair type;
    typedef A first;
    typedef B second;
};

template <class P>
struct second
    : second<typename P::type>
{};

template <class A, class B>
struct second<pair<A,B> >
{
    typedef B type;
};

template <class P>
struct first
    : first<typename P::type>
{};

template <class A, class B>
struct first<pair<A,B> >
{
    typedef A type;
};

template <class A, class B>
struct list
{
    typedef list type;
    typedef A head;
    typedef B tail;
};

template <class P>
struct tail
    : tail<typename P::type>
{};

template <class A, class B>
struct tail<list<A,B> >
{
    typedef B type;
};

template <class P>
struct head
    : head<typename P::type>
{};

template <class A, class B>
struct head<list<A,B> >
{
    typedef A type;
};

// An infinite list from 
template <long start = 0, long incr = 1>
struct count
    : list< int_<start>, count<start+incr,incr> >
{};

template <class Heap>
struct bump_top
    : push<pop<Heap>, iter_increment<top<Heap> > >
{};

template <class V, class Heap>
struct equal_top
    : equal_top<V, typename Heap::type>
{};

template <class V>
struct equal_top<V, nil>
    : false_
{};

template <class V, class T, class L, class R>
struct equal_top<V, heap<T,L,R> >
    : equal<V,T>
{};

template <class V, class Heap>
struct bump_equal
    : if_<
          equal_top<V, Heap>
        , bump_equal<V, bump_top<Heap> >
        , Heap
      >
{};

#if 0
template <class V = int_<2>, class Heap = nil>
struct sieve
    : if_<
          equal_top<V, Heap>
        , sieve<inc<V>, bump_equal<V, bump_top<Heap> > >
        , list<
              V
            , sieve<
                  inc<V>,
                  push<Heap, iterator<square<V>, V> >
              >
          >
      >
{};

#else
// Optimization
template <class V = int_<2>, class Heap = nil, bool NotPrime = equal_top<V, Heap>::value>
struct sieve;

template <class V, class Heap>
struct sieve<V, Heap, true>
    : sieve<inc<V>, bump_equal<V, bump_top<Heap> > >
{};

template <class V, class Heap>
struct sieve<V, Heap, false>
    : list<
          V
        , sieve<
              inc<V>,
              push<Heap, iterator<square<V>, V> >
          >
      >
{};
#endif

// push<push<push<push<nil,int_<3> >, int_<-2> >, int_<7> >, int_<9> >::type x= 0;

typedef sieve<> s;
s::head::type p0 = 0;
s::tail::head::type p1 = 0;
s::tail::tail::head::type p2 = 0;
s::tail::tail::tail::head::type p3 = 0;
s::tail::tail::tail::tail::head::type p4 = 0;
s::tail::tail::tail::tail::tail::head::type p5 = 0;
s::tail::tail::tail::tail::tail::tail::head::type p6 = 0;
s::tail::tail::tail::tail::tail::tail::tail::head::type p7 = 0;
s::tail::tail::tail::tail::tail::tail::tail::tail::head::type p8 = 0;
s::tail::tail::tail::tail::tail::tail::tail::tail::tail::head::type p9 = 0;
s::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail::head::type p10 = 0;

#if 0
s
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::tail::tail::tail::tail::tail::tail::tail::tail::tail::tail
::head::type p9 = 0;
#endif 

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com