在度过了今年的最爽假期也是最后假期之后的星期六,又看到了qsc更新视频的我是很欣喜的,但是看完之后的我是懵逼的:怎么难度一下从天堂到了地狱~~,当然了,最后卿学姐也说了,这是一个导论性质的介绍,那么就让我再总结一下吧.

先放上视频的地址:机器学习算法讲堂(4):Explore and exploit算法 LinUcb《Bandits in Recommendation》

从老虎机开始

让我们来想象这样一个情景:

一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么每次该选择哪个老虎机可以做到最大化收益呢？

这就是多臂赌博机问题(Multi-armed bandit problem, K-armed bandit problem, MAB),也就是我们需要在有限的回合内找出一个系统的最大收益,而之所以用MAB问题来举例的原因也是因为,这个问题的抽象可以套在很多推荐系统的问题之上,例如:

• 假设一个用户对不同类别的内容感兴趣程度不同，那么我们的推荐系统初次见到这个用户时，怎么快速地知道他对每类内容的感兴趣程度？
• 假设我们有若干广告库存，怎么知道该给每个用户展示哪个广告，从而获得最大的点击收益？是每次都挑效果最好那个么？那么新广告如何才有出头之日？
• ….

可以发现,这些问题都跟老虎机是一样的:我们需要在有限的回合内找到老虎机的最大收益==>我们需要在有限次数内找到推荐广告的最大收益

而在推荐系统领域对于这类问题有一个统一的说法,叫做Explore-Exploit问题,也就是如何来最大化探索和利用的价值的问题,比如:

• Explore(探索):我们需要探索用户的兴趣点而且需要不断地探索新的兴趣来保证用户对系统的新鲜度,这是一个长期的,挖掘潜在价值的,成长型的需求
• Exploit(利用):当我们探索出最大价值的时候我们需要利用,这是一个贪婪的,短期的,需要奖励来反馈激励的需求

就像是在玩老虎机:我们发现一个老虎机吐钱很多,那肯定需要用它来赚钱啊,但是我们也不能保证它就是最赚钱的,我们也得去探索其他的老虎机的赚钱能力,而如何来协调探索和利用的关系来使得我们的系统产生出最大的价值,也就是需要研究的地方了.

Bandits in Recommendation

知识准备-累积遗憾

当然这一点在qsc的视频中没有着重讲,但是在看其他博客的时候还是觉得需要补充一下.

累积遗憾也就是Bandits算法中用来量化一个策略好坏的指标,用公式写出来是这样的:
$$
R_A(T) = E\left[\sum_{t=1}^Tr_t,a_t^*\right]-E\left[\sum_{t=1}^Tr_t,a_t\right]
$$

这里t表示轮数,r表示回报.公式右边的第一项表示第t轮的期望最大收益，而右边的第二项表示当前选择的arm获取的收益，把每次差距累加起来就是总的遗憾.显然的,累积遗憾越小,算法的效果也就越好.

$\epsilon$-greedy algorithm(贪心策略)

我们来看一种最简单的贪心的策略,方法如下:
在每一步:

• 使用一个我们选择的概率$\epsilon$,随机的选择一个手臂去摇老虎机(探索)
• 其他的(1-$\epsilon$)概率下,我们选择当前最赚钱的老虎机摇一下(利用)

然后我们观察最后的回报来调整概率达到最优解,然而这个算法的问题在于:我们的选择是随机的,但是实际上,我们在摇了很多下老虎机之后是知道哪些比较赚钱那些不怎么赚钱,而这个信息没有被利用起来.我们的改进思路也就变成了从随机选择去寻找更加聪明的选择方法.

Thompson sampling

Beta Distribution(Beta分布)

关于beta分布几乎是没有了解的,但是在这只需要知道它是一种概率分布就可以了,这里先给出分布的公式:
$$
f(x;\alpha,\beta) = constant \cdot x^{\alpha-1}(1-x)^{\beta-1}=\frac {1} {B(\alpha,\beta)} x^{\alpha-1}(1-x)^{\beta-1}
$$

这里我们需要关注的是beta分布的方差的计算(实验的次数越少方差就越大):
$$
var(X)=E[(X-\mu)^2]=\frac {\alpha\beta} {(\alpha+\beta)^2(\alpha+\beta+1)}
$$

算法解释

而这个方差的特征正是我们所希望的,比如我们摇了一个老虎机10000次,它赚的钱是500块而另一个老虎机我们只摇了100次赚的钱是5块,如果我们在这两个老虎机之间做抉择的话,肯定会选择后一个,因为它的上限比前者高,因为前者我们几乎以及可以肯定它就是10000次赚500,而后者可能比它更赚钱,虽然现在来看它们的平均收益是一样的.下面是ppt中对beta分布的可视化:

item-b和item-c就是上面的摇了10000次的老虎机和摇了100次的老虎机.
而Thompson sampling算法的思路就和上面的想法一样,假设每个老虎机的吐钱概率符合beta分布,跟随机选择手臂的贪心算法比起来,优化的地方就在于:用每个手臂的beta分布生成一个随机数,选择这些随机数中最大的那个手臂摇一下.下面给出贪心算法和Thompson sampling算法伪代码的比较:

UCB:Upper Confidence Bound(置信区间上界)

在之前我们也提到了,贪心算法的缺点就在于没有利用前面已经摇了的老虎机的信息,上面的Thompson sampling算法给出了一种利用的思路,而UCB(置信区间上界)则是另一种利用的方式.
大致的思路是:我们假设每一个老虎机的吐钱概率
$$
Q(a)\leq \hat{Q_t}(a)+\hat{U_t}(a)
$$
这里的$\hat{Q_t}(a)$就是每个老虎的收益的均值,而$\hat{U_t}(a)$可以认为是这个老虎机的赚钱潜力,而这个潜力也能够使得很少被摇到的但是很赚钱的老虎机被发掘出来.那么现在的问题就是要对$\hat{U_t}(a)$来确定一个上界,也就是它的极限赚钱能力是多少,而这个上界在1963年被Hoeffding找到了并且命名为Hoeffding Inequality,其中的上界的解是:
$$
\hat{U_t}(a) = \sqrt{\frac {-\log p} {2N_t(a)}}
$$
其中的p是我们假设的概率,$N_t(a)$则是实验的次数

Bayesian UCB

虽然我们已经可以通过上面的公式来计算每个老虎机的置信区间上界从而选择摇那个老虎机,但是缺陷是这个上界太大了,也就是说实际的效果并不会很好,而其中的一个解决方案就是假设$Q(a)$服从贝叶斯分布,这样我们就可以直接根据公式来算出上界,至于效果的话,直接引用paper中的一个比较,可以看到优化的效果是比较好的.

这是上面提到的几种算法的效果的比较图:

LinUCB–UCB算法的一次进化

算法的优化还在继续,上面的UCB算法的最大问题在于它是context-free(上下文无关)的,这怎么行呢(滑稽),所以我们的算法优化的下一步就是给UCB算法插上特征的翅膀.也就是我们给每一个手臂都加上一个上下文的特征,当然这里再举老虎机似乎不是很贴切了,可以把手臂变成替用户挑选商品的手臂.那么与此对应的,我们给每个手臂能够获得的期望收益一个定义:
$$
E[r_{t,a}|x_{t,a}] = x_{t,a}^\top \bf {\theta}_{a\cdot}^*
$$
假设手机到了m次反馈，特征向量可以写作Da(维度为md)，假设我们收到的反馈为Ca(维度为m1)，那么通过求解下面的loss，我们可以得到当前每个手臂的参数的最优解：
$$
loss = (C_a-D_a\theta_a)^2+\lambda\begin{Vmatrix} \theta_a \end{Vmatrix}
$$
然后我们可以使用ridge-regression(岭回归)得到explicit solution(闭式解):
$$
\theta_a = (D_a^TD_a+I)^-1D_a^Tc_a
$$
而根据UCB方法,我们除了需要一个均值之外,还需要找到一个置信上界,而这个置信上界也被人找出来了.反正最后我们需要训练的函数就可以确定下来,就是下面这一坨了(实在不行了,mathjax真难写):

给出LinUCB算法的伪代码:

优点

• 是上下文相关的
• 上下文特征的回报函数是线性的
• 是一个岭回归==>是有解析解的
• 服从高斯分布==>有UCB上界
• 是一个在线的算法(个人认为是:有新的数据进来不需要重新训练模型)

优化方向

下面就是一些比较简短的优化的方向了

• CoLin:协同过滤,引入了用户之间的关系(这个还是挺重要的特征)
• hLinUCB:加入了hidden-feature(隐向量)
• FactorUCB=hLinUCB+CoLin

最后的最后,放上一个Bandit算法的进化路径的图吧:

可以看到进化的方向就是从随机选择到更加聪明的选择,从上下文无关到上下文相关,也是越来越能够贴近推荐系统的核心需求了.

参考博客

专治选择困难症——bandit算法
UCB算法升职记——LinUCB算法
推荐系统遇上深度学习(十三)–linUCB方法浅析及实现
推荐系统遇上深度学习(十二)–推荐系统中的EE问题及基本Bandit算法

论文引用

LinUCB
CoLinUCB
CLUB
hLinUCB
FactorUCB

总结

因为是一个导论性质的小讲堂所有内容还是有点多的,消化起来也有点慢也有点吃力,但是还是很开拓眼界的.

吾尝终日而思矣,不如须臾之所学也

March comes in like a lion, and goes out like a lamb

国庆长假时突感无聊就找了一个补番推荐,然后就打开了这部番,谁知一看就不可收拾,一口气就看完了两季44集,以及很久没有这种感觉了,每一集都看的很舒服而且停不下来,上一次这么完整的看一部番剧应该是看钢炼的时候了吧.回到这部番,虽然讲的是主角下将棋的故事,一开始我是这么认为的,但是随着故事的发展才发现,将棋只是一部分,最重要的还是主角的成长和其他人的故事.

可以说零是不幸的,因为他自幼失去双亲和妹妹,虽然被父亲的朋友收养但是在新家里不受”姐姐”和”弟弟”的尊敬,最终害怕养父和子女的关系继续恶化而自己搬出来住,在学校中也因为研究将棋而没有同龄玩伴而被孤立.但是也可以说零是幸运的,而且比大多数人都幸运,因为有川本这样一个耀眼的”家”和川本三姐妹,二海堂这样的好友和林田这样关心学生的班主任.但这也就是人生吧,苦难和快乐总是交织的,而只有经历了深沉的苦难的人,才能更好的把握那仅有的幸福.

虽然很多人都说这部番节奏太慢了,但是我觉得就这样,就很好,像流水一样慢慢地慢慢地将每一个人的故事都讲了出来,这也是我觉得这部番好的一个原因,每一个人物都塑造的很成功,有为了不辜负乡亲们的期待而慢慢变强的岛田师兄,有因为身体原因而想在将棋上和别人公平对决的二海堂,有被挚友们托付了将棋愿望而66岁还坚守在A级的柳原棋匠,有二十多年容颜不变但患了听觉障碍的棋鬼宗谷名人,等等等等…每一个故事,每一个人都在为了生活而奋斗,这样不是就很好吗

这部番让我感到喜欢的还有画风,虽然一开始有点接受不能,但是在习惯之后,这种鲜明的用画面来表达情绪的画风反而变得很好,并且作画很跳跃,到最后甚至很喜欢这种画风,快乐时一切都是花样的,悲伤时又是如此的萧条和黑暗,而那无时不在的写成文字并讲出来的声音,也令人印象深刻.

零从一开始的”没有拼搏的理由”,到最后开始全力以赴,生活也从孤零零的阴暗的房间变成了多彩的世界,生活不易,每个人都在用自己的方式和生活斗争着,就算是零,从小就独自一人,在故事的最后,身边也有这么多人在相互扶持,我觉得这就是这部番给我最大的温暖吧.

给我印象很深的是在chapter 21中零的独白:

难道都是我的错吗？！
那么你告诉我该怎么办啊？！
开什么玩笑！
你弱你有理吗？！
因为弱才会输啊！
拜托你去学习啊！
我知道你在偷懒啊！
不要说什么，道理我懂，但我做不到，之类的话啊！
既然这样，那干脆别来啊！
我可是赌上了全部啊！
除了将棋，我一无所有啊！
不要借酒来逃避现实啊！
我对弱者没兴趣啊！

是啊,这个故事不仅是讲给零听的啊,而当零被岛田拍醒的那一刹那,我知道也知道了:

虽然嘴上说没有战斗的理由，但我知道自己体内住着一头野兽，就算把周围东西咬碎也要只为生存而奔走的野兽
不论让谁变得不幸，无论世界变成什么样子

可能也就是三月的狮子这个名字的由来吧:青春如同狮子一般咆哮着降临，最也难免以柔和的方式度过余生.

这个故事是讲的如此之好,没有煽情也没有夸大,而是把故事摆在你面前,无论是快乐还是伤心,无论是光明还是黑暗,都是如此的直击人性,令人难以忘怀,而在这个故事仍没有结束的夜晚,在我心中也流淌着一丝的温暖.

最后放一首ED,是米津玄師的orion.

あなたの指が その胸が その瞳が
眩しくて少し 眩暈がする夜もある
それは不意に落ちてきて
あまりにも暖かくて
飲み込んだ七色の星
弾ける火花みたいに
ぎゅっと僕を困らせた
それでまだ歩いてゆけること
教わったんだ
神様どうかどうか
声を聞かせて
ほんのちょっとでいいから
もう二度と離れないように
あなたと二人あの星座のように
結んで欲しくて
夢の中でさえどうも
上手じゃない心具合
気にしないでって嘆いたこと
泣いていたこと
解れた袖の糸を引っぱって
ふっと星座を作ってみたんだ
お互いの指を星として
それは酷くでたらめで
僕ら笑いあえたんだ
そこにあなたがいてくれたなら
それでいいんだ
今ならどんなどんな
困難でさえも
愛して見せられるのに
あんまりに柔くも澄んだ
夜明けの間ただ眼を見ていた
淡い色の瞳だ
真白でいる陶器みたいな
声をしていた冬の匂いだ
心の中静かに荒む
嵐を飼う闇の途中で
落ちてきたんだ僕の頭上に
煌めく星泣きそうなくらいに
触れていたんだ
神様どうかどうか
声を聞かせて
ほんのちょっとでいいから
もう二度と離れないように
あなたと二人この星座のように
結んで欲しくて
結んで欲しくて

你的手指 你的胸口 还有你的眼眸
如此的闪耀 在这夜里让人眩晕
不经意间落下的
如此温暖的
将我吞噬的七色之星
宛如四射的火花
让我无比困扰
不过我也因此受益匪浅
明白了我还能继续前进
神啊 怎么办啊 怎么办啊
让我听到你的声音
哪怕只有一瞬也没关系
为了让我们再也不分开
希望你我二人 就像那互相连接的星座
永生相随
就算是在梦中的世界
好像还是会屡屡受挫
叹着气说不要在意
眼泪也落了下来
将袖口脱落的线
试着做成一个星座
将你我的指尖当做星星
这样太过离谱
我们看着对方笑了起来
其实只要你一直在那里的话
我就很心满意足了
现在
不论有多大的困难在眼前
为了你我都会甘之如饴
可这黎明实在是 过于柔和澄澈
所以我只能 一直望着你的眼眸
那双有着淡淡色彩的眼眸
犹如陶器一般 纯白无暇
就像围绕在耳边的 冬天的气息
在心中 静静肆虐的暴风雨
在那漆黑一片的途中
降临在我的头顶
无数明暗闪烁的星 如今就近在指尖
让我有想哭的冲动
神啊 怎么办啊 怎么办啊
让我听到你的声音
哪怕只有一瞬也没关系
为了让我们 再也不分开
希望你我两人 就像那互相连接的星座
永生相随
永生相随

Continuations 对于程序设计的意义，就像达芬奇密码对人类历史的意义：即对人类最大秘密的惊人揭示。也许不是，但他在概念上的突破性至少和负数平方根的意义等同

看到CPS变换却不是在SICP学习的时候,而是在国庆前一天翻看王垠的GTF-Great Teacher Friedman时,当看到:

一个例子就是课程进入到没几个星期的时候，我们开始写解释器来执行简单的 Scheme 程序。然后我们把这个解释器进行 CPS 变换，引入全局变量作为”寄存器” (register)，把 CPS 产生的 continuation 转换成数据结构（也就是堆栈）。最后我们得到的是一个抽象机 (abstract machine)，而这在本质上相当于一个真实机器里的中央处理器（CPU）或者虚拟机（比如 JVM）。所以我们其实从无到有，“发明”了 CPU！从这里，我才真正的理解到寄存器，堆栈等的本质，以及我们为什么需要它们。我才真正的明白了，冯诺依曼体系构架为什么要设计成这个样子。

的时候,被兴趣吸引然后顺手搜索了一下CPS是个什么东西,结果便在这之上消磨了2天的时光,也是做一下总结罢.

What:什么是CPS?

在讨论CPS变换的时候我们在讨论什么,那就要从CPS开始讲起,既然(CPS)被称为一种style,那么可以认为它就是一种编码风格,而CPS变换也就是把我们的代码格式化成_Continuation-passing style_的过程.下面是一个关于CPS的解释:

CPS，是Continuation Passing Style的缩写，它是一种编码风格，函数执行完以后，并不通过返回值，而是调用它自己的Continuation来完成计算。

How:怎么做CPS(变换)

知道了定义之后,就可以开始做CPS变换了,虽然定义很抽象但是在看了几个例子之后还是可以理解这种书写代码的风格的.

下面是一个简单的例子(并不对特定的语言讨论,可以看成是伪代码):

1
2
3
4
5
6
7

// 一般的写法
func add(x, y) = x + y
print add(a,b)

// CPS风格的写法
func add(x, y, fun) = fun(x+y)
add(a, b, print)

对上面代码的解释:在一般的写法中我们定义了一个相加函数然后向控制台打印了a+b的结果.而CPS风格的写法是将一个print函数传递给函数add,在执行完add之后将结果传递给打印函数然后输出.也可以理解为add函数做完了自己的活之后将结果和控制权交到了print手里然后print输出了结果并返回了,但是print也可以继续传递这个结果给别人.

再举一个阶乘的例子:

1
2
3
4
5

// 一般写法
func f(x) = x == 1 ? 1 : x * f(x-1)f(4)

// CPS风格写法
func f(x, k) = x == 1 ? k(1) : f(x-1, lamdba(v):k(v*x))f(4, lamdba(v):v)

因为CPS约定：每个函数都需要有一个参数kont，kont是continuation的简写，表示对计算结果的后续处理,而对kont的约定是:kont为一个单参数输入，单参数输出的函数(假定print符合要求).

Why:为什么需要CPS变换

在例子中可以看到CPS的主要的功能就是:在一个函数执行结束之后,将返回值交给下一个函数,但是到现在为止,有一个很明显的问题是显而易见的,那就是我们可能会写出一个很长的函数调用串.也就是说这个看上去只是花哨了一点的代码风格在没有优势的情况下还带来了缺点,所以下面就整理一下我在浏览时看到的CPS的使用和优势(这个缺点其实不致命因为可以通过语法糖来解决).

执行顺序

来考虑这样一个问题,现在我们有2行代码:

1
2

print "enter something"
getInput()

很简单,在终端产生一个提示并且获取用户的下一个输入,但是问题是:我们不能保证代码执行的顺序,它们执行的顺序完全取决于编译器怎么安排.那么让我们来用CPS重写一下:
print ("enter something", getInput())

结果是很明显的,我们可以用这种方法来强制决定函数的执行顺序,这一点在函数式编程中是很重要的.当然在并发中,这也可能会有点用(没深究).

堆栈

来考虑一下阶乘函数的调用链:

1
2
3
4
5
6
7
8
9

// 一般写法
f(4) ==> 4*f(3) ==> 4*3*f(2) ==> 4*3*2*f(1) ==> 4*3*2*1

// CPS风格写法
f(4) = f(3, lamdba(v):(v*4))     
     = f(2, lamdba(v):(lamdba(v):(v*4)(v*3)))     
     = ...

改写之后可以化简为:v = 1 ==> 2*v ==> 3*v ==> 4*v ==> v

可以看到,第一种递归就是经典的递归模型,每次递归调用自己的时候都需要将当前的函数状态入栈然后进入到下一个函数中直到到递归终止情况然后逐一向上返回结果最后得出答案.但是在第二种CPS风格中,我们可以看到状态是顺序的,计算是从1开始向后乘到4然后返回,这是因为k承载了每次计算的结果并向后传递,也就是说我们不需要保存函数当前的状态而可以直接调用下一个函数,也就是说CPS变换将普通递归函数变成了尾递归.可以这么理解:递归中的保存状态的栈和kont函数是等价的,并且kont函数还有一个优势:因为kont函数可以被显示调用,也就是说我们可以在任意时刻任意情况下,调用函数的某一时刻的状态,只要它是CPS风格的!!

下面给出一段博客的引用,可能解释的更清楚:

这样我们就知道了什么是“当前 continuation”。它有什么意义？一旦我们得到了当前的 continuation 并将它保存在某处，我们就最终将程序当前的状态保存了下来——及时地冷冻下来。这就像操作系统进入休眠状态。一个 continuation 对象里保存了从我们获得它的地方重新启动程序的必要信息。操作系统在每次发生线程间的上下文切换时也是如此。唯一的区别是它保留着全部控制。请求一个 continuation 对象（在 Scheme 里，可以调用 call-with-current-continuation 函数）后，你就会获得一个包括了当前 continuation 的对象，也就是堆栈信息（在 CPS 程序里就是下一个要调用的函数），可以把这个对象保存在一个变量（或者是磁盘）里。当你用这个 continuation “重启”程序时，就会转回到你取得这个对象的那个状态，这就象切换回一个被挂起的线程或唤醒休眠的操作系统，区别是用 continuation，你可以多次地重复这一过程，而当操作系统被唤醒时，休眠信息就被销毁了，如果那些信息没有被销毁，你也就可以一次次地将它唤醒到同一点，就象重返过去一样。有了 continuation 你就有了这个控制力！

应用:消除JS回调地狱

虽然还没有完整的学过JS和前端的技术,但是在学Django的过程中接触到的一些简短的JS也觉得这门语言”似乎”有很多的缺陷(个人感觉,主要是感觉各种{({()})}嵌套确实不够优雅),但是JS又确实是一门经常被拿来讨论一些FP问题的语言(可能因为JS支持函数作为first-class还能在浏览器直接运行的原因吧).在看CPS的过程中也看到了关于JS回调地狱的问题.

回调地狱

先来丢一段js代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

fs.readdir(source, function (err, files) {  
    if (err) {    
        console.log('Error finding files: ' + err)  
    } else {    
        files.forEach(function (filename, fileIndex) {      
            console.log(filename)      
            gm(source + filename).size(function (err, values) {        
                if (err) {          
                    console.log('Error identifying file size: ' + err)        
                } else {          
                    console.log(filename + ' : ' + values)          
                    aspect = (values.width / values.height)          
                    widths.forEach(function (width, widthIndex) {            
                        height = Math.round(width / aspect)            
                        console.log('resizing ' + filename + 'to ' + height + 'x' + height)            
                        this.resize(width, height).write(dest + 'w' + width + '_' + filename, function(err) {              
                            if (err) console.log('Error writing file: ' + err)            
                        })          
                    }.bind(this))        
                }      
            })    
        })  
    }
})

解决方案

当然这一堆括号和大括号看着很让人抓狂而且也很难马上掌握执行的顺序,当然这里不会来优化这段代码(我不会,哈哈),来看一个简单的例子:

1
2
3
4
5
6
7
8
9

// 第一次ajax，查询出id
$.get('http://xxx/user?name=jxy', function(data){  
    var id = data.id;  
    // 第二次ajax，根据id查询出需要的数据  
    $.get('http://xxx/another?id='+id, function(data){    
        // 这里才是真正的处理逻辑    
        // do something...    
    });
});

用async/await优化之后可以变成(据说是终极解决方案):

1
2
3
4
5
6
7
8
9
10
11

// 伪代码
// 用async修饰一个函数
async function getData(){  
    // 用await标记异步操作，会自动等待异步操作执行完毕之后再继续向下执行  
    const user = await $.get('http://xxx/user?name=jxy');  
    const id = user.id;  
    const data = await $.get('http://xxx/another?id='+id);  
    // 真正处理data  
    // do something...
};
getData();

关于async/await或者说协程,讨论起来又是无止境的了,但是基本的思想和CPS很吻合,也就是我们需要在切换上下文的时候如何来保存状态和恢复之前的状态.而js的async/await其实也只是function*+yield的一个语法糖而已,其核心就是不断的将 yield 的 next 值追加到 promise 链中，达到“一步接一步”执行的效果.

在看资料的时候还看到github上有一个Continuation.js项目,是直接使用CPS来解决回调地狱问题的,给出的例子如下:

原始js代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function textProcessing(callback) {  
    fs.readFile('somefile.txt', 'utf-8', function (err, contents) {    
        if (err) return callback(err);    
        //process contents    
        contents = contents.toUpperCase();    
        fs.readFile('somefile2.txt', 'utf-8', function (err, contents2) {      
            if (err) return callback(err);      
            contents += contents2;      
            fs.writeFile('somefile_concat_uppercase.txt', contents, function (err) {        
                if (err) return callback(err);        
                callback(null, contents);      
            });    
        });  
    })
;}
textProcessing(function (err, contents) {  
    if (err)    
    console.error(err);
});

使用Continuation.js之后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function textProcessing(ret) {  
    fs.readFile('somefile.txt', 'utf-8', cont(err, contents));  
    if (err) return ret(err);  
    contents = contents.toUpperCase();  
    fs.readFile('somefile2.txt', 'utf-8', 
    cont(err, contents2));  
    if (err) return ret(err);  
    contents += contents2;  
    fs.writeFile('somefile_concat_uppercase.txt', contents, cont(err));  
    if (err) return ret(err);  
    ret(null, contents);
}
textProcessing(cont(err, contents));
if (err)  
    console.error(err);

至少,看起来确实优雅了很多.

应用:Web应用

试想这么一个场景:用户向服务器请求了一张表单比如是注册,然后用户在网页上进行了一系列的操作之后提交了这张表单,注册成功.

在开发的过程中,一般来说我们要写一个getForm的方法来响应请求表单和postFrom的方法来响应提交表单.但是如果我们用CPS来思考这个问题呢?就会变成下面这样:用户申请了一张表单,我们生成一个函数来处理它,然后将这个函数保存起来,等到用户提交的时候,我们再调用这个函数将参数给它就可以完成注册.

在这个场景中的优势就是,我们不需要分离get和post逻辑,因为这其实都是属于用户注册这个过程中的事,而且,因为continuation可以在任何时候被调用而且不止调用一次(只要被保存了),那么优势就很明显了,我们只要缓存continuation环境,就可以节省很多的服务器性能.

我相信在web上,这个理念迟早会流行,毕竟计算机中十年不变的东西就是各种语言正在发布的新特性(hhh).

应用:JavaFlow

这只是在Google的过程中搜到的一个算是副产物吧,但是也在这里记录一下,大致就是可以在Java里使用JavaFlow来实现continuation.

1 2 3 4 5 6 7 8 9 10 11 12 13

class MyRunnable implements Runnable { public void run() { System.out.println("started!"); for( int i=0; i<10; i++ ) echo(i); } private void echo(int x) { System.out.println(x); Continuation.suspend(); } } Continuation c = Continuation.startWith(new MyRunnable()); System.out.println("returned a continuation");

然后就可以调用c了:

1 2	Continuation d = Continuation.continueWith(c); System.out.println("returned another continuation");

自动CPS变换

之所以将其放在最后,是因为我也还没有时间将其搞懂,而且似乎对于理解CPS变换来说影响并不大,这里就先暂时用一张图来代替吧(王垠40行代码的注释版)

参考博客

GTF - Great Teacher Friedman

CPS变换与CPS变换编译

CPS的地位

基于CPS变换的尾递归转换算法

函数式编程与Continuation/CPS

用 continuation 开发复杂的 Web 应用程序

时间倏忽而逝

还有一篇文章先留个档,有时间再消化:
Representing Control—A Study of the CPS transformation