On Tue, Sep 13, 2011 at 1:44 PM, Dave Abrahams <dave@boostpro.com> 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@suddenlink.net>wrote:
On 09/11/11 02:30, Jeffrey Lee Hellrung, Jr. wrote:
On Sun, Sep 11, 2011 at 12:01 AM, Ábel Sinkovics <abel@elte.hu> 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)