共有回帖数 0 个
-
1 今昔东途
——我如何组织故事，故事如何改变我
1.1 例：Perl5 - 按名克里化的失败
曾经有名Perl僧人给出了这么个悲剧——他试图按名字对Perl函数施行克里化（currying. 余谈，姬海棠羽立曾经提出过「克里化米饭」——明确地说是「对米饭施行克里化」——的概念，虽然我认为被克里化的主要是除了米饭之外的其他材料）的等作用行为，即允许函数的部分应用。勇气可嘉，不过结果实在不尽人意。
实际生成克里化的代码很简短：
sub curry { my $f = shift; my $args = @_; sub { $f-(@$args, @_) } }
函数curry生成一个被克里化的包装，但使用起来并不显然。对待变换的函数f, 考虑施行一次curry的情况：
curry($f, @args) = sub { $f-(@args) }
但是这显然不是我们所需要的样子。直觉上curry这个包装应当是迭代的，每次抽出下一个调用留待施行，并提供对应的参数。如果读者对CPS(Continuation-Passing Style)有印象的话，大概可以更方便地理解这里构造迭代的方式——实际上我们需要传递续延（continuation）。
原例试图构造这样的调用：
$g = curry(&curry, $f)
考虑这里的结果。生成的包装是
$g = sub { curry($f, @_) }
我们试图对$g多次应用参数：
$g-($a) = sub { curry($f, @_) }-($a) = sub { $f-($a, @_) }
危险、危险、危险。至此我们已经失去了curry期望的不变式，或者说进入了演算的收束阶段，应当对施行于f的应用进行求值了。如果读者仍然没有看出下面的发展，可以再进行两次应用：
$g-($a)-($b) = $f-($a, $b)
$g-($a)-($c) = $f-($a, $b)-($c)
最后一式已经没有救赎。如同我们在看到curry的实现之后所期望的那样，施行三次应用就可以毁掉克里化包装：因为这里并没有持续传递续延，或者说没有真正迭代下去。或许读者会反射性地意识到这里可以试着用call-by-value Y combinator( namely, f.(x y.f (x x)) (x y. f (x x)) )施行匿名递归，不过我们没法声明递归的终止条件。重新审视克里化的情况——每个函数被表为一元函数或是一元函数的复合，但函数本身是被明确给出的。或者说，即使不限定类型，也限定了自变量的数目。
对于Perl 5来说，很难做到这样的事情——函数不具有类型，也不严格限定其抽象，换言之没有严格的在应用时将自由变量替换成绑定变量的要求。在没有任何契约或是缺乏完整抽象的情况下施行部分应用，无异于用参数填满不定参数列表并决定施行最终的调用。这已经不是无类型λ演算的问题了（λ演算假定函数是一元的，并且明确给出抽象），而是语言天生的pitfall. 当然，在函数具有确定参数列表但语言不缺省提供部分应用支持的情况下，也不见得能写出合适的克里化或是等作用替代品——尤其是在希望避开反射的情况下。虽说拒绝把类型抽象带入运行时并不是应当提倡的做法，但在运行时大张旗鼓地对类型加以判断仍然是在引入奇怪的分支，致使控制流进一步奇葩化——我们试图用多态性或/和模式匹配避免引入的东西死灰复燃，直觉上看来这并不好；另一方面，过量控制流的引入似乎也容易让语言在需求上失去对rest of the program的表述能力——或者说，以肉眼看来，强调步骤和分支的东西相对更不在乎「演算」的意义：这不见得是坏事，因为这样的表述不见得是迫切需要的，但不代表不该列入考虑。
1.2 例：C实现 - 手操闭包的失败
另一个例子来自C. 这里我们试图给出一个仿闭包实现，虽然没法做到完整的一等函数，但至少要求实现自动捕获。单纯从C语义上的解法我并没有完整考虑过，或者说应该是不可行的——宏没法探测它之外的实体或是试图了解其中的实体。给出的实现使用了gcc的nested function扩展、标识符命名扩展、类型反射扩展以及内嵌汇编。
#define _closure ({
#define _lambda(_rt_, ...)
_rt_ $(__VA_ARGS__)
#define _closure_end
void *_rsp_, *_rbp_, *_cntx_;
asm volatile ("movq %%rsp, %0" : "=r" (_rsp_));
asm volatile ("movq %%rbp, %0" : "=r" (_rbp_));
char *_tramp_ = (char *) malloc(sizeof(char) * (19 + (unsigned long) (_rbp_-_rsp_)));
memcpy(_tramp_, $, 19);
_cntx_ = *((void **) (&_tramp_[8]));
memcpy(_tramp_ + 19, _cntx_, (unsigned long) (_rbp_ - _cntx_));
*((void **) (&_tramp_[8])) = (void *) (_tramp_ + 19);
(typeof(&$)) ((void *) _tramp_); })
#define _closure_free(_x_) free(_x_)
实际的用法比如：
#include stdio.h
#include closure_gcc.h
int (*make_adder(int base, int base2))(int, int) {
int a = 1;
char arr[] = "hello";
int (*adder)(int, int) =
_closure
_lambda(int, int arg1, int arg2) {
puts(arr);
return arg1 + arg2 + a + base;
}
_closure_end;
return adder;
}
int main(void) {
int a = 1, b = 2;
int (*adder)(int, int) = make_adder(3, 2);
puts("ayayaya?");
printf("%dn", adder(a, b));
_closure_free(adder);
return 0;
}
单纯一层的捕获没有问题，栈帧也还存活。不过实际上在下面的例子上就会崩溃：
#include stdio.h
#include closure_gcc.h
typedef int (*functype1_t)(int);
typedef functype1_t (*functype2_t)(int);
functype2_t f(int x) {
functype2_t g =
_closure
_lambda(functype1_t, int y) {
functype1_t h =
_closure
_lambda(int, int z) {
return x + y + z;
}
_closure_end;
return h;
}
_closure_end;
return g;
}
void testfunc(functype1_t func) {
printf("%dn", func(5));
}
int main(void) {
puts("some test");
printf("%dn", ((f(1))(2))(3));
functype1_t g = (f(1))(2);
testfunc(g);
return 0;
}
gcc/x86-64在不优化的情况下可能存活，因为生成的代码会把参数复制到栈上。在调用够早的情况下，这些超出作用域和生存期的东西仍然没有被覆写，使得实现的函数仍然能拿到旧有的值。-O2的话会直接崩溃，这其实也悲惨地在预期之内。gcc为nested function生成一段跳板代码并假定栈可执行，从而将这些代码置于栈上，同时为nested function生成常规的代码段落。跳板代码处理的问题主要是外层函数的局部量——或者说内嵌函数的上下文。对这里的64位代码而言，用于索引局部量的基址被填入r10, 此后跳转到实际的函数代码；宏_closure_end则为跳板代码和上下文提供堆上的空间，并改写mov r10, *的第二操作数为堆上的跳板+上下文拷贝。单纯使用r10的话，自然只允许一层的嵌套。——如果允许直接给出捕获以加强条件，仍然没有多少回旋的余地（考虑使用两层作用域和一个中间名字对捕获变量进行中转的情况，同时这里需要使用typeof反射出捕获变量的类型，构造出新的跳板代码和上下文。新跳板代码中应当涉及上下文的重写——也即假定已知caller的上下文位于某处，则将callee的上下文和caller进行合并；到这里读者或许会意识到捕获这个条件可能可以放松，但无论放松与否都涉及到另一个难以回避同时难以克服的问题：函数代码中相对上下文的偏移在编译时将会给定，不作额外hack则无法和新上下文中的偏移同步变化，同时无法预估访存的方式和时机——也即难以明确区分两种上下文的访问，从而不容易通过调整基址来寻址旧上下文中的变量）。
实际上这里我们落入了一个更凄惨的境地。由于无法干预求值，实现者被迫去和实现做妥协式的斗争——这已经使得付出的努力不具有多少意义。Gophers所谓的抽象拆解之所以能成功，是因为他们给出了语义和编译器的实现——而实际上他们并未拆解任何语义抽象，反倒是依旧顺着语义的路走下去，只不过没有一本正经地希望靠中间表示和额外的分析对相应的后端代码生成进行指导；换言之，他们的拆解是实现之直觉——而这个直觉倒是UNIX的传统：由于语义本身并没有吸引多少注意，直觉之实现更容易起到吸引眼球的作用。然而从完全或不完全的第三方看来，他们仍然受制于既定抽象，这同样是抽象没被拆解的证据；语义仍然僵硬，用户仍然能感觉到求值的制约和phase的高墙。而到去年（2012）为止，Go给我的感觉仍然像是Java 1.4的替代品：简单未必带来更多的自由和可用性，或者说自由并非建立在单纯试图被限制起数量的语言特性上——实际上自由会来自抽象的程度而非历史性的需求，一组接近理想的核心抽象较之一系列实现简单的特性重作品更容易从语义上解放用户——同时我们不妨注意到限制数量的尝试不见得是有效的，毕竟粗暴的语义带来的矛盾和对额外规定的需求导致语义逐渐难看地成长的例子之一就是C. 在这个意义上，C并没有承诺多少自由性——虽然用户具有自由实现上层建筑的权利，但如果这些权利都被剥夺了，他们还能剩下什么呢？思考的自由并非建设的自由，语义的抽象并非中间结果（实现）的抽象——不过恰当的抽象也未必是更「高」的抽象……尤其假如邪教徒乃至同袍们试图鼓吹产生自本能之归纳的轻内聚式抽象即为具有表现力的「高层抽象」这一观点的话。不管选择产生抽象还是主推实现特性，总之我们仍然应该抛开成见重读现状。
1.3 薄铁如丝
下面的话题或许不免和后面重复，但是相信读者从自身受到的计算机科学/技术方面的训练大概也能了解到，不那么根源的知识往往纠结在一起，被表现力和需求驱动着回旋前行。这里我要谈论的是语言描写软件系统的方式——更多地是描写而不是描述，是强调细部、细节和可能在控制不当时产生邪恶代码的场合，然而也是真正独立出来时候会富有表现力乃至人情味的部分。考虑一个事件驱动的软件系统——读者可以选择自己熟悉的实现，它可能是libevent, nginx核心，nano, kirno（U酱十五岁！）或者其他样子的东西；考虑其中分用事件的方式，考虑事件驱动框架在其中所扮演的角色。独立的事件驱动框架往往要求注册事件和事件对应的动作，而这些书写上离散的组分构成了软件系统的行为——同时，事件驱动框架和其他基础部件构成了软件系统的机制。这是解耦没错，但是解耦的结果如何呼应我们的直觉呢？回想我们写下hello world这样的c程序的时候——我们书写入口函数，写下输出的调用，并要求入口函数返回——这是一件完整的事情。肌肉和皮肤并不因为独立于骨骼而在体表上显得离散——当然如果你身高五十米还能喷出蒸汽那就是另一回事——相反，因为有骨骼的存在，它们才更有效地构成躯体，显得健壮或是可爱或是可爱到不行。
我们实现机制。我们实现框架。我们实现工作流。然而离散的事件和对应的动作鸟瞰起来更是直觉看来的耦合——它们附着在事件框架上或是其他的机制上，露出框架的形状，但并没能描述它们所刻画的软件系统究竟做了什么——对于一个大系统来说这恐怕难以避免，因为机制的层次并不见得容易确定和区分，但对于不会很大的应用程序呢？会有人为野地里可爱的花朵举行一个仪式，全心全灵为它赐福吗？——倒不如这时候归回到形如泛灵论的地位上，重新以用例来考虑软件，并试图在单独的层次上描绘用例。这可能只是一个简单的自动机抽象和加载——这样的描述甚至不见得能被拣选进入一等对象的天堂——但是它直观地描述了应用程序是什么和做什么。从另一个角度看来，这使得应用程序被容许转瞬即逝，强调框架的可信度并扩大了可编程的范畴。我们是开发者。我们不满足于胡乱点击鼠标或者输入命令，我们同样不满足于给定的配置文件；我们之所以没有对手头的应用软件加以修改是因为它们把业务和协议埋得有点深而我们太累了——然而我们不见得会放弃对软件本身编程的想法，因为编程是我们与软件交互的方式之一……是富有技巧性和表达力的方式。反观前面的两个例子，我们需要做什么呢？确实我们需要一等对象，不过在没有的时候也不要忘记我们在做什么——毕竟阅读和编写代码的经验已经开始破坏直觉了。请谨慎抉择（如果有可能的话）。
2 行礼如仪
——……魔法语言中的「a」……读作/ai/
2.1 单子和推导式
标题虽然泛泛地说了推导式，但我打算主要关注单子推导（后面我们会作出一个列表推导）。考虑类型构造子M, 若M类型的值有两个运算
return :: a - (M a)
bind :: M a - (a - M b) - M b
我们称(M, return, bind)是单子（Monad）。不过我们出于方便考虑，可以导出第三个运算
then :: M a - M b - M b
也即在忽略bind中第一项应用和第二项应用之间的关联，比如下面的定义
then x y = bind x λz.y
项λz.y具有类型a - M b, 假定x具有类型M a而y具有类型M b——但y是自由变量。
同时考虑单子应有的性质：
bind (return v) f = f v
bind f return = f
bind f (λx.bind (g x) h) = bind (bind f g) h
前两条性质是平凡的。单纯的返回——绑定即为平凡的复合，这里的v只需具有类型a. 同时bind和return互逆。第三性质看起来有点晦涩，不过我们可以把它写成中缀式
f `bind` (λx. (g x) `bind` h) = (f `bind` g) `bind` h
这就是结合律。连续的bind操作产生同样的顺序，实际上这保证了在函数式范式当中可以存在严格的一般序（normal order）求值，也给出了单子推导式（Monad Comprehension）的定义。经由分配律的连续复合，我们可以写出
p1 `bind` λx1.p2 `bind` λx2.p3 ... λx(n-1).pn `bind` λxn. return (f x1 x2 ... xn)
这样一个顺接的形式，不妨将其记作
[ f x1 x2 ... xn | x1 - p1, x2 - p2, ..., xn - pn ]
这就是一个只含生成式（generator）的单子推导式。[* 实际上，推导式中也可以含有卫式（guard, 即不产生状态变化的单纯的谓词）]。假如pi具有λz.P（假定P中不含绑定变量z）的形式，那么这里的前后关系会是更宽泛的then. 在这个前提下，如果我们构建列表单子，就很容易使用单子推导式给出求值序受限的列表推导式，比如下面的笛卡尔积
product l1 l2 = [ (x, y) | x - l1, y - l2 ]
实际上是
l1 `bind` λx. l2 `bind` λy. return (x, y)
而l1, l2具有单子类型List
return x = make_list x
bind l f = map_then_concat f l
其中原语map_then_concat将f应用至l的每一元素上并展平结果生成单一的列表，假定f具有类型a - List b而l具有类型List a.
这时候我们对某些隔离IO action的手法加以重新评判——考虑下面的例子。设有类型构造子IO和如下操作
getLine :: IO string
putStrLn :: string - IO ()
其中()表示一个动作（action）。读者应该能意识到这里的M a和a - M b形式，以及顺接结果的M b形式。读者甚至会意识到这是Haskell, 而Haskell实现了使用单子隔离IO的尝试——那么这里到底发生了什么？抛开繁复的想法，单纯考虑静态强类型的类型系统要求。如果我们定义一个值v，它往往具有（意会）「正常」的类型t; 在典型的过程式语言中，我们允许定义函数
getval :: t1 - t
从而书写v = getval u是可行的，不过u往往是隐式的。但是注意到我们为了完整书写非平凡的定义域，引入了一个类型t1, 这可能是所谓的real world或者runtime/io context. 直觉要求我们把getval的类型改写成下面的样子：
getval :: cntx - (type, cntx)
其中(x, y)表示一个有序对。有没有发现这里的context是需要传递的？换言之，在一序列的IO动作A1, A2, ..., An当中，对合适的i, A(i+1)的输入依赖A(i)的结果。那么从朴素的第一考虑出发，构建IO单子并施行单子推导（或是更本愿地，施行bind）就可以统一这样的形式。同时注意到cntx - (type, cntx)这形式，实际上可以是一个关于type的IO类型构造子（泛泛地说，实际上它是关于type和cntx的类型构造子，但假设了IO背景的话cntx是暂时可以视作常量的）——我们可以顺利地把它作成单子。另外一方面，回到getLine和putStrLn的例子：注意到IO string不是string（这显然是两个类型，请不熟悉这类型系统的读者注意），故而偷偷塞进一个算符（Haskell叫它「-」）使得IO string下降为string变得可能（实际上我不觉得说“下降”很合适，因为IO string的责任并不是单纯的string. 如果读者觉得IO的黑盒还是有点迷糊，可以重新参考比较好懂的单子化文法分析组合子(Monadic Parser Combinator)，可能更容易理解单子推导中间结果之类型的意义变化——这里就明显不是「提升」和「下降」的关系，而是表示「分析状态」）。整体来说，用于IO的单子推导首先保证了求值序，同时给出了状态传递的简记法，并使用状态（同时也是类型）隔离了两个世界（缺乏完整状态变化过程的连续IO是无意义的，因而这样的IO被限制在推导中；从IO得到结果的过程在脱离上下文的情况下是无意义的，因而这些过程被「感染」而限制在推导中）。
当然这或许真的是个——如同yinwang指出的一样——理论hack. 我们的出发点是对IO函数加以制约，强迫埋没在幕后的context显现出来并加以演算，但我们避免了什么？实际上的可能是无副作用的代码被嵌在单子推导的过程当中，其结果仍然是难以评估或者复现的。举例而言，典型的情况就是并发和消息机制：同一段无副作用代码会在两个主动成分上表现出难以复现的结果，这和我们书写一般的并发程序差异并不大，最多是从字面上避开了共享内存；但这样的结论并不令人满意，毕竟erlang这种无节操的伪函数式语言已经达到了相当程度的隔离，这里并非单纯的函数式所直白涉及之领域。不过目前至少我们可以通过单子推导将IO整合进静态强类型的函数式语言当中，我并不认为这毫无价值——看上去还是满有趣的。与其说是理论hack, 倒不如调侃地说是理论happens?
楼主 2015-10-10 13:49 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
