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

Subject: Re: [Boost-users] [proto] : Recursive functions in a lambda like language
From: Eric Niebler (eric_at_[hidden])
Date: 2010-07-03 01:17:55

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<int(int)> 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