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-02 23:38:51

On 7/2/2010 9:00 PM, Manjunath Kudlur wrote:
> I was playing with the idea of having the user declare functions
> (polymorphic, possibly recursive) in a lambda like language, and the
> capability to later call that function with different types of
> arguments. Here is an example of what I am thinking about.
> 
> function fib = if_(_1<2) [ _1 ].else_[fib(_1-1) + (_1-2)];
> int x = fib.eval(10);

Careful here. You are using fib in the initializer of fib itself. That
is, you're calling a member function of an object not yet constructed.
That's undefined behavior. Instead, you'll need something like this:

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

This *can* be made to work, with some difficulty, by turning fib into a
handle and fib(x) returns something that references the (initially
empty) body. Note that two or more mutually recursive functions need to
keep each others' bodies alive, so you need reference counted bodies
with something akin to garbage collection. Xpressive's regex objects are
designed precisely this way, and it's devilishly complicated. If you go
this route, have a look at how xpressive's basic_regex type uses
xpressive's tracking_ptr class. There is even documentation about how
this collection works: http://tinyurl.com/35t2kgy.

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.

> How should I define the "function" class? My first attempt at a
> solution was to use "boost::any" like class for function, I overloaded
> operator() in that class so that it returns a proto expression. I am
> attaching some source code that has a function class and a phoenix
> like language. Now, I am not able to come up with a solution for
> defining a polymorphic eval() for the function class. Since "function"
> has to be able to store any type inside it, it has to do type erasure.

Yeppers.

> All methods in "function" has to be delegated to value_base class but
> that cannot delegate a polymorphic eval() function down to value_type.
> I can templatize "function" class and get monomorphic functions
> defined in this language. But that is less interesting. I would
> greatly appreciate any advice and suggestions on other solutions to
> this problem. I realize that this is not entirely proto specific and
> maybe it is a general C++ language question, but I am hoping proto
> users might have faced similar problems and provide guidance.

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)];

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.

It's an interesting problem!

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com