Re: [boost] Template metaprogramming libraries

Subject: Re: [boost] Template metaprogramming libraries
From: David Sankel (camior_at_[hidden])
Date: 2011-09-15 12:31:50

On Tue, Sep 13, 2011 at 1:44 PM, Dave Abrahams <dave_at_[hidden]> wrote:
>
> > A while ago someone suggested (on the developers' list) adding de Bruijn
> > indices [1] to Boost.Bind and/or Boost.MPL (and may have provided at
> least a
> > sample implementation for one or the other, I'm not sure), which ( I
> think)
> > would allow you to do what you want to do.
>
> That was David Sankel, IIRC.
>

Thus invoked...

On Sun, Sep 11, 2011 at 9:22 AM, Larry Evans <cppljevans_at_[hidden]>wrote:

> On 09/11/11 02:30, Jeffrey Lee Hellrung, Jr. wrote:
> > On Sun, Sep 11, 2011 at 12:01 AM, Ábel Sinkovics <abel_at_[hidden]> wrote:
> >
> >> Hi Larry,
> >>
> >>> Are you saying that using the existing mpl, one cannot embed
> >>> lambda expressions inside other lambda expressions?  Is that
> >>> mpl problem an example of name capture:
> >>>
> >>>   http://dictionary.reference.com/browse/name+capture
> >>>
> >>> ?
> >>
> >> You can embed MPL lambda expressions inside other ones. I couldn't find
> >> a way of accessing the arguments of the outer lambda expression from the
> >> inner one, because the names _1, _2, etc were referring to the arguments
> >> of the inner expression, not the outer one (they were shadowing the
> >> outer ones).
> >>
> >> I'd express it with "\x.\x.x" in lambda calculus. Inside the inner
> >> lambda abstraction "x" refers to the argument of the inner, not the
> >> outer one.
> >>
> >
> > A while ago someone suggested (on the developers' list) adding de Bruijn
> > indices [1] to Boost.Bind and/or Boost.MPL (and may have provided at
> least a
> > sample implementation for one or the other, I'm not sure),
>
> I attempted an implementation, but was not successful, as indicated in
> this post:
>
>  http://lists.boost.org/Archives/boost/2010/09/171123.php
>
> > which ( I think) would allow you to do what you want to do.
> >
> > There might be some protect and bind combination of contortions to do
> what
> > you want, but I'd certainly agree that, even if it could be done, it
> > probably wouldn't be pretty.
>
> I remember doing something with those templates to workaround a problem
> that *seemed* like it was a name capture problem; so, I'd agree with
> Jeffrey here that it might work with some combination of bind protect
> (I also think I used lambda).
>
>
I'm the one who designed the DeBruijn bind syntax and implementation that
Dave A and Larry referenced. The DeBruijn bind syntax would work for compile
time or run time. The sample implementation was for run time.

DeBruijn bind syntax can represent strictly *more* functions than the
traditional bind syntax, even with protect. Furthermore, the functions that
DeBruijn bind can define, that traditional bind cannot, are useful and
interesting.

An example is the flip function:

haskell syntax:

flip :: ((a,b) -> c) -> ((b,a) -> c)
flip f (x,y) = f (y,x)

intuition:

flip is a function that takes in a two-argument function and returns a
two-argument function that is essentially the same, but the arguments are
reversed.

lambda syntax:

λf.λ(a,b). f (b,a)

De Bruijn syntax (any lambda expression can be transformed into this
syntax):

λ₁λ₂2₁(1₂, 1₁)

De Bruijn Bind syntax (any De Bruijn syntax can be transformed into this
syntax):

lam<1>( lam<2>( app( _2_1, _1_2, _1_1 ) ) )

Now lets see why flip can never be defined with traditional bind syntax.

First, we give a meaning to traditional bind expressions in order to
understand what we're talking about.

Consider boost::function<blah> = bind(_1, bind( _2, protect( bind( _2, _1
)))).

For that top level bind expression, wrap it in a protect. This doesn't
change the meaning and will aid our translation.

boost::function<blah> = protect( ... ).

Each protect has a given size. This size is defined as the largest _x that
is underneath it, but not underneath another sub-protect. Annotate each
protect with its size.

protect[2]( bind(_1, bind( _2, protect[3]( bind( _3, _1 ))))).

Now, for each protect, generate a list of "size" globally unique identifiers
and replace every _x underneath (that isn't within a sub-protect) with the
appropriate identifier. In this example, first we do this to the outer
protect:

protect[2,x,y]( bind(x, bind( y, protect[3]( bind( _3, _1 ))))).

And then the inner protect

protect[2,x,y]( bind(x, bind( y, protect[3,z,a,b]( bind( z, a ))))).

Now rename protect to λ and bind(a,b,c...) to a(b,c...)

λ(x,y). x( y( λ(z,a,b). z(a)))

What we have here is a translation from any bind expression into its
corresponding lambda expression (extended with multiple arguments in the
expected way).

Given this meaning, it is easy to see that a given lambda (introduced by
protect), can never reference any arguments but its own. Another limitation
is that a given lambda (introduced by protect) must always return
the application of some function (so things like λx.44 can't be defined).

<rant>
Unfortunately traditional bind syntax and it's inherent design flaws has
been replicated in several other libraries like mpl, lambda, phoenix, and
C++-0x (arg!). It should be noted though that phoenix users can get around
this somewhat by using _identifier syntax.
</rant>

My implementation adds some more goodies (like recursive functions, and
TCO), but the main benefit is it fills in the holes of traditional bind and
is easier to understand (by understand I mean having a grasp on the
underlying meaning of the expressions).

David

-- 
David Sankel
Sankel Software
www.sankelsoftware.com
585 617 4748 (Office)