Re: [Boost-users] [proto] : Recursive functions in a lambda like language

On 7/3/2010 12:01 AM, Manjunath Kudlur wrote:

...

Alternatively, you can introduce into your lambda language a special keyword named 'self' to refer to the currently-being-defined function, and define fib as:

function fib = if_(_1<2) [ _1 ].else_[self(_1-1) + (_1-2)];

This can also be made to work.

I too considered this approach, even had the same name "self" in mind :), or _0(), akin to argv[0] holding the current program name.

FWIW, xpressive has 'self' that allows for defining self-referential regular expressions.

...

If you have the luxury of using C++0x features, you can change your lambda language to look like this:

auto fib = if_(_1<2) [ _1 ].else_[self(_1-1) + (_1-2)];

Or BOOST_AUTO is also good enough for pre c++0x compilers. But the problem with this is, how can I write mutually recursive functions? I want to be able to say

function F1; function F2;

F1 = ..refers F2.. F2 = ..refers F1..

This is the main reason I wanted a named type. I am not necessarily married to this syntax. Any other syntax, maybe just using proto mechanism, that allows (mutually) recursive function definitions would be cool..

That's a hard one. But for inspiration, see how Classic Spirit allows subrules: http://www.boost.org/doc/libs/1_33_1/libs/spirit/doc/subrules.html These are statically-bound, mutually recursive grammar rules. You need to pick one to be top-most (the rule). The others are merely placeholders, symbolic names to stand in for rules. The whole thing is composed in one giant expression template.

...

If you *have* to assign it to a named type, you could either (a) give up on polymorphic lambdas and use something like:

function fib = ...;

or (b) give up on static type checking and use boost::any in the internal interfaces.

Can you please elucidate (b)? Making the language only have monomorphic lambdas makes it that much less interesting.

I was afraid you would ask that. I've tried to think of how I might go about implementing something like that. The only thing I can come up with so far is that when building up an expression like _1<2 you must bubble up the requirement that the 0th argument must be less-than-comparable to an int. Later, in your eval function template, you can use the collected requirements on the 0th argument to wrap it polymorphically such that it has a member "virtual boost::any operator<(int)" -- e.g. by inheriting from less_than_comparable<int>: template<class T> struct less_than_comparable { virtual boost::any operator<(T const &) const = 0; }; Note that it returns a boost::any, so these requirements cascade up your expression. The expression _1<2 is such that it has "boost::any eval(less_than_comparable<int> const & x)" that returns "x<2". I know the scheme sketched here won't work as-is, but I hope it nudges you in some beneficial direction. It will also be slow at both runtime and compile-time. Pretty but dumb.

...

It's an interesting problem!

I bet it is. I hope some good ideas come out of discussing this problem.

Don't know yet whether that idea deserves the adjective "good". -- Eric Niebler BoostPro Computing http://www.boostpro.com