[proto] : Recursive functions in a lambda like language

older
Re: [Boost-users] compiling fboost...

Manjunath Kudlur

3 Jul 2010 3 Jul '10

1 a.m.

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); 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. 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. Thanks, Manjunath

Attachments:

lambda.cpp (text/x-c++src — 2.3 KB)
function.hpp (text/x-c++hdr — 1.5 KB)

Show replies by date

Eric Niebler

3 Jul 3 Jul

3:38 a.m.

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 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

Manjunath Kudlur

4:01 a.m.

...

xpressive's tracking_ptr class. There is even documentation about how this collection works: http://tinyurl.com/35t2kgy.

Thanks, for the pointer. I will take a look.

...

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.

...

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..

...

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.

...

It's an interesting problem!

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

Eric Niebler

5:17 a.m.

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

Larry Evans

9:41 a.m.

On 07/03/10 00:17, Eric Niebler wrote: [snip]

...

...
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.

There's also: http://preview.tinyurl.com/38xrwj3 which refers to code in the vault which does something similar to spirit1 subrules. There's also this post: http://preview.tinyurl.com/2v9eg9b which says something similar to subrules was planned for spirit2; however, I don't know if that ever happened. HTH. -regards, Larry [snip]

5348

Age (days ago)

5348

Last active (days ago)

List overview

Download

4 comments

3 participants

participants (3)

Eric Niebler
Larry Evans
Manjunath Kudlur