Recursive Lambda in C++
rockeet febird
的自引用机制。找了半天，除了那些学院派的足以把99%的人搞晕的 Fix Point + Y combinator，一个最实用的解决方案就是把
lambda bind 到 std::function<...>.
我那段需要 recursive lambda 的代码：
void print_output() const { // use recursive lambda
std::string str;
std::function<void(state_id_t,state_id_t,char_t)> lambda =
[&](state_id_t source,state_id_t target,char_t c) {
str.push_back(c);
if (is_term(target))
cout <<str << '\n';
for_each_move(target, lambda);
str.resize(str.size()-1); // pop_back
};
for_each_move(initial_state, lambda);
}
这是以 DFS 顺序打印 Tree Shape Automata 的代码，为了各种原因(内存，速度，简洁)，设计了一个通用的
for_each_move 来遍历指定 state 的每个直接 target。
如果有 recursive lambda，这代码要更简洁高效一点（假定 [[]] 是引用lambda 自身的那个符号）：
void print_output() const { // use recursive lambda
std::string str;
for_each_move(initial_state,
[&](state_id_t source,state_id_t target,char_t c) {
str.push_back(c);
if (is_term(target))
cout <<str << '\n';
for_each_move(target, [[]]);
str.resize(str.size()-1); // pop_back
});
}
yuan zhu
rockeet febird
On Mar 5, 5:53 pm, yuan zhu <zy498...@gmail.com> wrote:
> 为啥不用auto呢？
>
yuan zhu
除非又增加一个例外，让模版爱好者和编译器作者自己去烦恼吧，，呵呵。
yuan zhu
猜测一下，或许这里不能用auto的原因，也就是不支持lambda自引用的原因？
On 3/5/12, rockeet febird <roc...@gmail.com> wrote:
rockeet febird
Mathematic
加一个自引用的符号多容易呀！
借用某人的话：不让你们难受，你们知道谁是老大？
On Mar 5, 6:21 pm, yuan zhu <zy498...@gmail.com> wrote:
> 这auto还真是不能用呢，想了半天，绕不开。
>
> 猜测一下，或许这里不能用auto的原因，也就是不支持lambda自引用的原因？
>
yuan zhu
------------------
首先，假象我们是一个编译器开发团队。Lambda默认的实现显然应该是函数对象。举个例子。
int i = 0;
auto lam = [&]() mutable{
++i;
printf(“%d\n”, i);
};
显然，lam的原型可看成
class uname{
private:
int& _i;
public:
uname (int& i): _i(i){}
operator()(void) {
++this->_i;
printf(“%d\n”, this->_i);
}
}lam;
如果是传拷贝，那么就去掉所有upvalue（Lambda函数对于可视的局部变量的称呼，下同）对应的成员变量的引用符，就如同上文中的_i,
以及构造函数参数中的引用符，其它都一样。
引申：如果我们想玩递归，那么会遇到什么问题呢？
稍微变化一下:
int i = 0;
auto lam = [=]() mutable {
++i;
printf(“%d\n”, i);
lam();
};
lam();
这下lam该如何定义呢？首先面临一个语义上的问题，lam是否upvalue?这个问题我们先不回答，但是不管怎样，如果lam是upvalue，他肯定是无法传拷贝的，因为对象无法持有自己的拷贝（class
A{A a;};非法）。所以将就一下，先别管那个“=”了。
class uname;
class uname{
private:
int _i;
uname& _ref;
public:
uname (int i, uname& ref): _i(i), _ref(ref){}
operator()(void) {
++this->_i;
printf(“%d\n”, this->_i);
this->_ref();
}
}lam;
突然我们遇到了一个很严重的问题，我们怎样构造第一个uname类实例呢？如同我们询问上帝，亚当和夏娃是自己创造出来自己的吗？呵呵，大家找不到上帝，没办法了吧。所以这里，lam绝对不能被视作upvalue。
请允许我这里使用了构造函数来不严格的解释这个问题，实质上这些步骤是由编译器帮我们完成了(自动inline)，编译器会遇到一个问题：递归无法开始！？
好了，如果lam不是upvalue呢？我们再来看看lam的实现。
class uname{
private:
int _i;
public:
uname (int i): _i(i) {}
operator()(void) {
++this->_i;
printf(“%d\n”, this->_i);
(*this)();
}
}lam;
喔，看起来一切都是很圆满的，不是吗？
可惜使用者不满意了，“我要我的‘=’！！”...
好吧，再接再厉
class uname{
private:
int _i;
public:
uname (int i): _i(i) {}
operator()(void) {
++this->_i;
printf(“%d\n”, this->_i);
uname lam0(*this);
lam0 ();
}
}lam;
正当我打算长吁一口气的时候，使用者又开始抱怨，“怎么还在打印01234啊，我要打印无限多的0啊？”
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
我彻底无语了，，。。上文中lam0拷贝的是一个状态已经发生变化了的lam，然而使用者显然不会发觉这个问题，他们认为在自己代码中的lam应该毫无变化，因为他们传的是拷贝！！！！
不得不说，这里如果允许递归的话，会产生非常严重的语义上的混乱。在状态，引用，拷贝等若干术语把我们真正的使用者搞糊涂之前，我们决定：禁止在lambda表达式中的递归调用，以防止使用者对lambda自身状态的混乱认定！
On 3/5/12, rockeet febird <roc...@gmail.com> wrote:
yuan zhu
这里它是否具名，是否左值不影响上面讨论的结果。只是在符号表达和术语上更一般化，以方便更多人理解。
排版不小心有点乱，希望不要介意喔。
On 3/5/12, yuan zhu <zy49...@gmail.com> wrote:
yuan zhu
yuan zhu
正当我打算长吁一口气的时候，使用者又开始抱怨，“怎么还在打印01234啊，我要打印无限多的0啊？”
改为：
正当我打算长吁一口气的时候，使用者又开始抱怨，“怎么还在打印12345啊，我要打印无限多的1啊？”
rockeet febird
调用只是递归 call 这个代码，而不是递归拷贝数据。标准能规定无 capture 的 lambda 可以隐式转化到相应的函数指针，却没有自引
用机制，分明就是傲慢自大和不思进取。
目前的 lambda 在形式上禁止了递归调用，但我们仍然能用 std::function<...> 去 hack 它，虽然比较低效并且丑陋，老
大会却说：看，我们对此是有解决方案的。
> 这下lam该如何定义呢？首先面临一个语义上的问题，lam是否upvalue?这个问题我们先不回答，但是不管怎样，如果lam是upvalue，他肯定是无 法传拷贝的，因为对象无法持有自己的拷贝（class
> A{A a;};非法）。所以将就一下，先别管那个"="了。
> class uname;
> class uname{
> private:
> int _i;
> uname& _ref;
> public:
> uname (int i, uname& ref): _i(i), _ref(ref){}
> operator()(void) {
> ++this->_i;
> printf("%d\n", this->_i);
> this->_ref();
> }
>
> }lam;
>
> 突然我们遇到了一个很严重的问题，我们怎样构造第一个uname类实例呢？如同我们询问上帝，亚当和夏娃是自己创造出来自己的吗？呵呵，大家找不到上帝，没办法 了吧。所以这里，lam绝对不能被视作upvalue。
> 不得不说，这里如果允许递归的话，会产生非常严重的语义上的混乱。在状态，引用，拷贝等若干术语把我们真正的使用者搞糊涂之前，我们决定：禁止在lambda表 达式中的递归调用，以防止使用者对lambda自身状态的混乱认定！
yuan zhu
显然可以，只是不免太无用了吧，lambda的优势完全没体现出来，还不如老实写个static函数更合适，虽然从封装完美主义者的角度来说，作用域大了一点，不过如果老办法很合用，何苦要来玩这些让新人迷惑的语法糖呢。
On 3/5/12, rockeet febird <roc...@gmail.com> wrote:
yuan zhu
这个代码，而不是递归拷贝数据”，但是没法避免别的使用者确实需要拷贝数据的呀，比方说别人要用回溯算法什么的，确实需要复位状态的，结果如同我上面那个例子，i的值再也回不去了。
On 3/5/12, yuan zhu <zy49...@gmail.com> wrote:
achilleus liu
Xinyu LIU
lambda1和lambda2你想达到啥目的？我没有看出这里的语义。
上面有人不建议谈代码风格，希望能专注于问题本身。但是这里不谈代码风格我实在忍不住。
在可读性、效率、通用性等等之间的取舍和平衡（做balance）是程序员的责任。
的确，从丘奇的lambda演算的理论上讲，所有的计算都可以表达为lambda演算。但是如果把一个清晰的高级语言程序全部翻译为lambda演算，其结果和翻译成汇编不会有太大区别：虽然机器都认得他们，但是可读性下降。
lambda可以递归，我们可以用Y变换表达lambda递归。也可以这样(Haskell)
Hugs> let f = \x-> if x >0 then x*f(x-1) else 1 in f(5)
120
我们还可以这样：Hugs> let frac x = if x>0 then x*frac(x-1) else 1 in frac(5)
120
Hugs>
有人把lambda叫匿名函数，这其实暗示了我们使用lambda的情景：
1、当某些简单的计算足够trivial，不值得定义一个带有名称的函数；直接inline到计算中反而增加可读性；
2、当某些计算难以找出一个有意义的名字，如果命名反而奇怪，如：double_and_plus_one；直接把需要的计算嵌入代码反而增加可读性；
如：for_each(first, last, x*2+1)
除此之外，如果定义函数的名称可以增加可读性，就不用把计算dycrypt为lambda，如：
map(first, last, frac)
最后说些我对C++的“偏见”，我一直是C++的铁杆粉丝，直到ISO 98标准，98标准是我忍耐C++的极限。0x之后，
当我发现如果我有100%的精力，但是解决同样一道难题时我发现C++让我分散越来越多的百分比在语言的特性上，而给我留下了越来越少的百分比用于思考问题本身的解法。当我意识到这个问题时，我就毅然而然地抛弃了C++。
同样被我以这个理由抛弃的东西还包括：各种GUI及其Framework，Design Pattern，XML等等。凡是分散我注意力的东西我就不碰它们。
我昨天想了一下这个问题，觉得除了上面 yuan zhu 同学提到的问题以外，还有类型推导方面的问题。如果允许使用lambda自引用或者auto，用户就可以写出以下的“合法”代码：auto lambda1 = [](int i) {return lambda1(i - 1);} 或者 [](int i) {return [[]](i - 1);}auto lambda2 = [](int) {return lambda2;} 或者 [](int) {return [[]];}但是这里lambda1和lambda2的类型都无法确定，这是C++编译器无法容忍的。即使在haskell里面，lambda1还可以，lambda2也是不行的。
Larry, LIU Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY
rockeet febird
auto fac = [](int i)->int { return i<=1? 1 : return [[]](i-1); }
auto devil = [](int i)->int { return [[]](i-1); }
有什么类型推导的问题？
并非所有存在都是合理，如果这样的话，恐龙就不会灭绝了
On Mar 6, 9:05 am, achilleus liu <sanachill...@gmail.com> wrote:
> 我昨天想了一下这个问题，觉得除了上面 yuan zhu 同学提到的问题以外，还有类型推导方面的问题。
> 如果允许使用lambda自引用或者auto，用户就可以写出以下的"合法"代码：
> auto lambda1 = [](int i) {return lambda1(i - 1);} 或者 [](int i) {return
> [[]](i - 1);}
> auto lambda2 = [](int) {return lambda2;} 或者 [](int) {return [[]];}
> 但是这里lambda1和lambda2的类型都无法确定，这是C++编译器无法容忍的。即使在haskell里面，lambda1还可以，lambda2也是不行的。
>
> 在 2012年3月5日 下午9:12，yuan zhu <zy498...@gmail.com>写道：
>
>
>
>
>
>
>
> > 另外楼主的例子确实只需要"递归调用只是递归 call
>
> > 这个代码，而不是递归拷贝数据"，但是没法避免别的使用者确实需要拷贝数据的呀，比方说别人要用回溯算法什么的，确实需要复位状态的，结果如同我上面那个例子，i的值再也回不去了。
>
> > On 3/5/12, yuan zhu <zy498...@gmail.com> wrote:
> > > 嗯，楼主的想法是，没有访问upvalue时，就允许自引用?
>
> > 显然可以，只是不免太无用了吧，lambda的优势完全没体现出来，还不如老实写个static函数更合适，虽然从封装完美主义者的角度来说，作用域大了一点，不过如果老办法很合用，何苦要来玩这些让新人迷惑的语法糖呢。
>
rockeet febird
On Mar 5, 9:12 pm, yuan zhu <zy498...@gmail.com> wrote:
> 另外楼主的例子确实只需要"递归调用只是递归 call
> 这个代码，而不是递归拷贝数据"，但是没法避免别的使用者确实需要拷贝数据的呀，比方说别人要用回溯算法什么的，确实需要复位状态的，结果如同我上面那个例子，i的值再也回不去了。
>
> On 3/5/12, yuan zhu <zy498...@gmail.com> wrote:
>
>
>
>
>
>
>
> > 嗯，楼主的想法是，没有访问upvalue时，就允许自引用?
>
> > 显然可以，只是不免太无用了吧，lambda的优势完全没体现出来，还不如老实写个static函数更合适，虽然从封装完美主义者的角度来说，作用域大了一点，不过如果老办法很合用，何苦要来玩这些让新人迷惑的语法糖呢。
>
yuan zhu
不过楼主想想，怎样让初学者明白
int i = 0;
auto lam = [=]() mutable {
++i;
printf(“%d\n”, i);
lam();
};
lam();
是想打印一12345.....的而不是一大堆1的，如何让别人明白那个“=”没有起到效果的：我的i是传拷贝的啊，怎么回事？？
这里不是不可以，而是太容易把人搞糊涂。
就算编译器强行在函数开始时就产生一个lam的拷贝(每当用到的时候再用这个拷贝做一次拷贝)，那么能够理解上文和编译器工作原理的人反而也容易搞糊涂。总之，这两种理解都好像言之凿凿，太容易out
of expection了。
所以这里，我赞同标准委员会禁止自引用的这个决议。虽然我也对委员会的很多议事流程持保留意见。
yuan zhu
一时随手写的，稍微马虎了一点，歉。
rockeet febird
On Mar 6, 10:42 am, yuan zhu <zy498...@gmail.com> wrote:
> 开始说的回溯的例子确实不对。
>
> 不过楼主想想，怎样让初学者明白
> int i = 0;
> auto lam = [=]() mutable {
> ++i;
> printf("%d\n", i);
> lam();};
>
> lam();
> 是想打印一12345.....的而不是一大堆1的，如何让别人明白那个"="没有起到效果的：我的i是传拷贝的啊，怎么回事？？
>
> 这里不是不可以，而是太容易把人搞糊涂。
> 就算编译器强行在函数开始时就产生一个lam的拷贝(每当用到的时候再用这个拷贝做一次拷贝)，那么能够理解上文和编译器工作原理的人反而也容易搞糊涂。总之，这两种理解都好像言之凿凿，太容易out
> of expection了。
>
> 所以这里，我赞同标准委员会禁止自引用的这个决议。虽然我也对委员会的很多议事流程持保留意见。
>
yuan zhu
我相信不是所有人都像我那样有耐心写上文那么长的一段文字来解释这个现象，也不认为所有人都有耐心去看完的。
yuan zhu
c++ 11加入lambda 本来就是为了简便，如果仅为了正确的使用lambda，却要用户付出理解非常深奥的实现细节的代价，每次写之前还必须揪着脑袋想个半天，那么c++
11的lambda 本身存在的意义，也就不存在了，即使某些时候确实可以少写一点代码量。
On 3/6/12, rockeet febird <roc...@gmail.com> wrote:
rockeet febird
#include <stdio.h>
struct lambda {
int i;
void operator()() {
++i;
printf("%d\n", i);
if (i<10) // avoid devil infinite recursion
(*this)();
}
lambda(int i) : i(i) {}
};
int main() {
int i = 0;
lambda l(i);
l();
return 0;
}
On Mar 6, 11:00 am, yuan zhu <zy498...@gmail.com> wrote:
> 换一种说法，楼主如何让初学者理解，lam函数怎么突然会因为使用了递归，就变得不可重入了呢？这个函数访问外部的变量可都是传拷贝的啊，内部也没有static变量啊，这到底是怎么回事呢？随便加一行代码，怎么就会让函数性质（和输出）大变样呢?
>
> 我相信不是所有人都像我那样有耐心写上文那么长的一段文字来解释这个现象，也不认为所有人都有耐心去看完的。
>
> On 3/6/12, yuan zhu <zy498...@gmail.com> wrote:
>
>
>
>
>
>
>
> > 再说声抱歉，上文中的operator()(void) ....都没有标明返回值为void,。
>
> > 一时随手写的，稍微马虎了一点，歉。
>
> > On 3/6/12, yuan zhu <zy498...@gmail.com> wrote:
> >> 开始说的回溯的例子确实不对。
>
> >> 不过楼主想想，怎样让初学者明白
> >> int i = 0;
> >> auto lam = [=]() mutable {
> >> ++i;
> >> printf("%d\n", i);
> >> lam();
> >> };
> >> lam();
> >> 是想打印一12345.....的而不是一大堆1的，如何让别人明白那个"="没有起到效果的：我的i是传拷贝的啊，怎么回事？？
>
> >> 这里不是不可以，而是太容易把人搞糊涂。
> >> 就算编译器强行在函数开始时就产生一个lam的拷贝(每当用到的时候再用这个拷贝做一次拷贝)，那么能够理解上文和编译器工作原理的人反而也容易搞糊涂。总之，这两种理解都好像言之凿凿，太容易out
> >> of expection了。
>
> >> 所以这里，我赞同标准委员会禁止自引用的这个决议。虽然我也对委员会的很多议事流程持保留意见。
>
> ...
>
> read more >>
achilleus liu
yuan zhu
然而，我相信大多数人在写
int i = 0;
auto lam = [=]() mutable {
++i;
printf("%d\n", i);
lam();};
lam();
的时候，都很容易认为应该输出一大堆1吧。楼主你不能总认为，别人都能像高级使用者（至少包括你）那样，去把语言的每一个细节以极为底层的方式去理解把，他们第一个想法肯定都是最直接而又最简捷的：传拷贝，i值没变，那么都是1。
这里我反复强调的，确实就是：c++想方设法减轻初学者写出正确的代码的负担，而不是加重（写一段代码前还得想想怎么实现的，而且这个实现还颇为不简单）。
On 3/6/12, rockeet febird <roc...@gmail.com> wrote:
achilleus liu
yuan zhu
On 3/6/12, yuan zhu <zy49...@gmail.com> wrote:
yuan zhu
auto x = [&](void){
return x;
};
x()()()()()()()()()()()();
///呵呵开个玩笑，不要介意哈
yuan zhu
auto x = [&](void){
return x();
};
///编译器说，给我一刀吧，你到底想要个啥啊，X.
rockeet febird
struct X{ struct X* link; } x = &x; 是合法并且是 defined behavior.
有这么多"多数情况下导致 undefined behavior" 的规定，增加一个绝大多数情况下是 well defined 的规定，有什么道
德风险？
我说的只是增加自引用功能，并没说必须通过 auto ... 那样的实现，代码示例中我也使用了 [[]] 来表示自引用。看看这个定义：
static struct {
int x;
void f(int a) {
this->x = a;
f(a+1); // devil
}
} y;
//...
y.f();
y 没有一个类型名称，也没导致什么问题吧？如果匿名就一定要禁止自引用，那这个代码应该编译错误才对呀。
On Mar 6, 11:28 am, achilleus liu <sanachill...@gmail.com> wrote:
> 显示声明返回类型肯定行得通，但是标准已经规定如果只有1行return语句，返回类型声明可以省略。所以程序员理论上来说可以写出符合规范但无法编译的代码。 如果要解决这个问题，又要增加更加繁琐的规定比如"当使用auto类型的变量被其自身的lambda表达式capture且return语句中直接返回以某参数 调用此变量的结果时lambda表达式的返回类型声明不能省略。"。而且这也无法解决我刚才提到的lambda2型错误。另外，也无法保证没有更多其它类型的错 误。
> ...
>
> read more >>
rockeet febird
么类型。
1. 如果你使用两个 return 语句来表达这种条件分支，那么就必须显式声明返回类型
2. 如果你在不同的分支将返回值保存起来，统一用一条return语句，那么你保存返回值的那个变量就已经有一个类型了，可以自动推断。
On Mar 6, 11:28 am, achilleus liu <sanachill...@gmail.com> wrote:
> 显示声明返回类型肯定行得通，但是标准已经规定如果只有1行return语句，返回类型声明可以省略。所以程序员理论上来说可以写出符合规范但无法编译的代码。如果要解决这个问题，又要增加更加繁琐的规定比如"当使用auto类型的变量被其自身的lambda表达式capture且return语句中直接返回以某参数调用此变量的结果时lambda表达式的返回类型声明不能省略。"。而且这也无法解决我刚才提到的lambda2型错误。另外，也无法保证没有更多其它类型的错误。
>
> ...
>
> read more >>
yuan zhu
其次，我反复举的那些例子，就是想说明，如果使用自引用来递归，那么极大的违反了最小惊讶原则。你说的那个f递归的例子，没有涉及到upvalue的问题，所以才看不出有什么毛病。
总结一下吧，lambda自引用递归会造成upvalue在传拷贝的时候产生很多奇奇怪怪的现象，很容易让初学者困惑不已，而且在该种情况下很难利用lambda写出自己想要的功能，为了防止此种滥用，否决掉它我认为是一种明智的决定。允许此种自引用的语言，肯定在upvalue传递规则上有一些限制，而不会像c++这样，拷贝与引用并存。
当然，包括我写的那几个大礼包，呵呵，自引用太容易产生一些奇奇怪怪的代码了。
On 3/6/12, rockeet febird <roc...@gmail.com> wrote:
rockeet febird
On 3月6日, 下午5时11分, yuan zhu <zy498...@gmail.com> wrote:
> 楼主，我不是说了吗，这里使用auto所定义的lam和你说的自引用实际是同一个玩意儿。楼主完全可以把我的那些例子里的lam换成你定义的那个符号"[[]] "，我所阐述的事实不会有任何的变化（我只是设法在现有的标准下阐述这个问题，不想定义新符号免得别人看不懂）。这里这个lam是否具名，是否左值，对我们讨论 的问题的过程和结论没有任何影响。
>
> 其次，我反复举的那些例子，就是想说明，如果使用自引用来递归，那么极大的违反了最小惊讶原则。你说的那个f递归的例子，没有涉及到upvalue的问题，所以 才看不出有什么毛病。
>
> 总结一下吧，lambda自引用递归会造成upvalue在传拷贝的时候产生很多奇奇怪怪的现象，很容易让初学者困惑不已，而且在该种情况下很难利用lambd a写出自己想要的功能，为了防止此种滥用，否决掉它我认为是一种明智的决定。允许此种自引用的语言，肯定在upvalue传递规则上有一些限制，而不会像c++ 这样，拷贝与引用并存。
>
> 当然，包括我写的那几个大礼包，呵呵，自引用太容易产生一些奇奇怪怪的代码了。
> ...
>
> 阅读更多 >>