#FP #Continuation #tech #PL #CS

https://epsil.github.io/gll/#continuation-passing-style-section

#FP #scheme #parser 想了解 continuation-passing-style （没有 return 如何编程？）的大佬们可以看看这人的文章，我觉得相当好。实用性，王垠那几十行代码不就是 CPS 优化吗。

照例个人观点：
0. 上文定义了 success/failure 的 union ，以及 (successed val rest) failure ，还有添加回调的 (bind p f)，基本是 (match (p s) [(success v rest) (+ v 1)] [failure failure]) 这么用的。
实现的解析器不支持流，支持 substring 。传递方式是 backtrace (比如 (string "abc") 在 (seq) 里成功则 (cons "abc" (cont "")) 失败就只是 failure 单值，所以要利用 memo 函数)

1. PKT 是不需要这种“优化”的（顶多比过程式慢 50倍的纯函数式框架要用），因为我们的 Seq 明白一解析器失败不考虑后面就 return notParsed ，不需要玩 p1(p2(p3 { })) 这种耗栈的游戏。Kotlin 不支持 CPS 优化，编程也不是智商测试。

2. CPS 也是有一定价值的，虽然它会损失一定性能，但能够拿到调用者的句柄（比如在有 Decide 的模式里，就可以后继操作遍历所有分支了，或者进行异步回调"thunk"函数）。和非 CPS 一样可作为 suspend fun 协程

3. 即便这篇文章相对易懂 #Lisp #Racket ，我不建议大家认真用 Racket ，原因是括号的表现力不够

比如文中 (let (result (apply op args)) (entry (mcons args result)) (set! alist (mcons entry alist)) (m=map)一大堆括号，有没有注意到 (let (a v) expr) 只是为可读性而加的，量定义可以内联…… 只是表达 alist = args to op(args) : alist 甚至 alist[args] = result 的意思呢（这例还是SICP里的呢，多余命名量本身就可能意味着语言性能缺失😢，比如『文言文』里甲乙丙丁一大堆OK么）…… 函数式那么多年修成正果了，开始从“无副作用”往“看起来像过程式”靠，草生(*￣m￣)

4. 从解决实际问题而言我觉得 ParserKt 更贴近，但这个文章所创建的解析组合子用更少的代码定义了更广义的实现方法，非常有意思（最后也用左递归和 regex 创建了计算器，缓存和穷举最长匹配问题如此有意思以至于我开始可惜PKT不用处理它了😳），而且也易懂的讲解了 CPS/trampoline 以及“穷举所有可能结果”的正统函数式思路 #Learn

刚才说完这个我突然想到关于这个 CPS(continuation-passing-style) 的一点不对…… #functional
看起来要么然之前在那篇文章上看的说法是错的，要么然 CPS 是一个类 longjmp() 的控制流概念，不是函数式概念

刚才说的 listE("item", ) = <items>$=<item> op($)</items> 是这样定义的(#Python 的压行技巧，不过之前说的 walrud operator 发现根本不能用)：

def listE(tag, op, xs): e = E(tag+"s" if tag[-1]!='y' else tag[:-1]+"ies"); [lets(E(tag), lambda ee: op(ee,x), e.append) for x in xs]; return e

如果

lets(E(tag), lambda ee: op(ee,x), e.append)

是 cps call-site ，那交给 callee 调用前的 continuation 应该是从 lets() 的头部(？)
程序可组合性的关键点在于，op “返回”后要能覆盖 x 才能算够用，但此例 op 也得能覆盖（而且要实现仅改 gavTo(e,coord) 的“单至多项展开”，这还远远不够吧）
如果不知道 return-side 的 type (接收什么变量)，就是说这种 cps 式编程，必须显式定义回转方类型，或类型不安全(形式参数列表意义--)
看来只有 yield/resume continuation 是好的（

不对啊， CPS 哪里来的 forEach 😂？看来我还不够了解真正纯的函数式……

https://zhuanlan.zhihu.com/p/34064655 #zhihu #fp 这是个物理爱好者18年的 CPS 解释器实现文

这个代码质量.. 其实我是讨厌看lisp 系的，非常讨厌嵌套括号，而且这个人似乎在代码里插debug print ，以C的方法写Racket .. ，那我就把要点挑出来看看

函数式除了伪递归也可做尾调用优化，当 f=()=>g(), g=()=>1 时g可return 到f.retAddr ，类似函数内联。CPS也是尾调用
显然return/即 callstk.pop() 两次不叫优化，那么我们就需要 pop 外的方式使用调用栈，即保存 continuation程续 。(call/cc setAs-f) 抓住了调用后的步骤, (f) 就能跳回原位(可用ES6 func* 体验)；在工业语言里程续被用于断续执行一个函数，意味它可yield暂时回交执行权， call/cc 也一样，不过能替换调用栈。 这样调用栈就变调用图了，因为你可 longjmp() 到之前的栈帧..

call/cc 可在 generator 里实现yield ,乃至throwcc-恢复 (不过认为Lisp throw更高科技真的不现实。
想实现程续可不容易，因为解释器的执行是不可暂停的，而我们还要替换调用栈 ，于是要手写新的..

cps 解释器可以实现 callcc 。考虑 "1".eval() 时要等待、更大的 "1+2.." 要等待，若碰到 "(call/cc f)" 也等待，f 就拿不到 callcc f后的程续，因为callcc 是立即执行f的?

他是用了 handle-decision-tree , 一个 (eval exp env cont) 扩展，x[0](res=>res? only(decision=x[1])? exec(d=decision) : decide(d) : decide(tail))
eval-continuation-call 简单让 eval 的 cont=被闭包状态 ，因为[接下来的步骤 回调] cont 本身就是解释器状态

CPS化 eval() 就能保存状态..我之前只想过 func* 化，确实对 #PLT 了解不够。 比如 a+1 里 add: lit(v=> a,b=v) , cont(a+b) ，那如果 lit 把 add() 闭包保留住，确实就留住了当前程续，如果env 参数也在内，就是整个状态副本…… 不过没看懂单步操作为啥需 decision-tree (好像说 eval-fcall 的没这个就不能在 callcc 函数内运行

文末说要点是 callcc f 创建了 continuation 喂给 f，我只看到 cps 使得后序树遍历 Expr>Add>Lit 变成 Lit>Add>Expr 的反向形式，因此可回馈值 而非等待值，就能suspend ；我之前设计的 tvr 求值步骤模型里 r(treeRes) 好像也是这个效果，能保留树路径。从自顶向下组合 到自底向上化简,碰到callcc抓callback..我好像明白下面那个GLL 是什么意思了
eval-conti-call 则把包住的 env ,cont 重设，就替换了调用栈和当前 scope
如果 f=(k)=>的程续k没被恢复，callcc f 的值就是f()值。 callcc的eval(里cont= "call f" ) ，就指定此默认值

不过说起来函数式解释器 env 表全复制也挺高明的，就没有什么继承综合语法的破事了，解析期都构造好的深先序
以前那些人都说得太复杂…… 之前还有个CPS写解析组合子的，能实现memo..用了什么CPS特性? tramp(循环转化)和memo? GLL文法? 代码太长.. 就没发现CPS有啥特殊技巧的说

🥲我想起了去年冰封说”Kotlin coroutine 的 Context 就是CPS Context“ ( runBlocking{ launch{ delay(1000) } } 两个suspend调用里啥算内部协程,还是两个孤立调度的)，然后我一脸蒙蔽- 断续函数就是可暂断回调度器的函数，和CPS有啥关系？ ES6 里也只和 __awaiter 自动.then(resume) 有关啊，现在才知道 Kt coro 是自动callback:Continuation{suspend,resume} 化suspend fun，内部调用等待，完成后交给最外层...

函数式妙……实在是妙啊, callback 这么的土，Kt 竟然用它实现协程？它竟是CPS? 真的大跌眼镜。看来相同的东西，动手操作不同，名词也就不同了

解释器，我自己也在写一篇。
http://www.yinwang.org/blog-cn/2012/08/01/interpreter
王某这个racket 再定解释器就是S-expr 系非常经典的写法了， 变量/常量和env, lambda/call, (eval expr env) ，但其实要说短也有更短的：好像删了..
😐坏耶，只是个后序遍历还藏那么深，殊不知Lisp系解释器作用域是代码最低的... 改天我写一个

看到这里，其实这些人除了S-表达式看起来很牛逼，代码质量真的不行；不是我讨厌圆括号，而是 (def prechk(x) (if (not (ok x))(err "fxxk") 正常逻辑 ) ) 还占缩进这种写法真的难看，我最讨厌平铺直叙的程序 🙏
许多人尽管是大佬，但写的代码仍不敢恭维，或者有改进空间；而因为他的思想正确、领域牛逼，言辞有特性，就觉得他什么都好， 我大可不必。错就是错，风格是慢慢改进的。 尽管牛逼，如果言不及义，也只能说他不善表达..意识到才有改进空间

除了PLT，我也在发展一些其他的API见闻，在我眼里什么领域都是平等的，表达只有目的和废话，没有谁更牛逼的说法。