《ruby元编程》有奖试读中！（获奖名单已公布）

OwnWaterloo

回复 86# starwing83

关于缓式求值。在默认缓式求值的语言中，缓式求值是普遍深入的。

C（generator本来就只是模拟缓式求值的机制，而C连模拟generate都困难）里，只能一边产生组合，一边剪枝。
你给的第2个lua版本，是将产生所有组合的方式利用generator缓式化，对么？ 当需要一个组合时，就resume得到一个， 再判断它与3的关系。

但在默认缓式求值的语言中， 连产生一个组合 —— bit32.totable —— 都是缓式的。
当你需要某个组合中的某个元素时，它的计算才会被求值。


缓式求值显然是有代价的，肯定需要计算本身（相对于计算结果）记录在某些地方。

但一个显然的好处是它将原先的产生组合的过程从整个dfs中剥离了出来。 这部分就可以复用。
也许这些函数式的可复用代码拼凑在一起后可能达到手工拼凑dfs的效果 —— 手工dfs也需要自己记录一些，比如i， selected， 递归也是利用函数调用栈。

能达到手工拼凑的例子有。比如count_if(elems, pred)。
haskell里 count_if 可以用 filter 与 length 定义， 并且filter 产生的中间list可以被消除。
http://stackoverflow.com/questio ... the-given-predicate
在其他语言里通常就不能这么干。

用缓式的totable拼出一个组合， 再缓式拼出所有组合， 这部分是范化的通用代码； 最后在它们的基础上编写逻辑相关的剪枝 —— 我不能肯定是否能达到手工将3者全写在一起的效率。
我觉得对你举的这个例子应该没戏……  至少在空间效率方面肯定败了。  需要保存的中间结果太小， 就一个N大小的数组……
而对一些逻辑更复杂的，并且是有经验的haskell程序员， 也许就可以。


BTW： 这也是bench不好做的一个例子。
haskell其实效率很高， 但需要有很深入的了解才知道它那些机制会产生怎样的代价， 这种代价与手写是否相同， 或者即使差一点也值得用运行时间来换开发时间？
haskell的效率很难估计， 它的抽象层次与机器相差太远了， 很容易写出低效的代码。

你前面举的那个gambit慢的文章， 就也许类似我看到过的一个说haskell慢的文章。 你猜他怎么比的……
它用一个不纯的而且是严格求值的函数式语言， 命令式地建一个大的hash表。 然后将这代码直译到haskell……

starwing83

回复 91# OwnWaterloo


    要不对这个问题你给个haskell代码？我也很好奇这是怎么做的。

缓式缓式，但是缓式也得有被求值的时候。这里最麻烦的是次序问题。缓式求值只能避过不必要的求值，却没有办法改变求值的逻辑顺序。这里的问题是。组合是**早就产生**的，我们是在已经产生后的组合上进行**筛选**，而dfs的情况下，组合是**延后产生**的，我们是确定产生的组合无效的前提下进行**剪枝**，这里的逻辑次序都不一样。一个是产生组合->验证组合，还有一个是验证组合->产生组合。就算是缓式求值，在第二个方案中，你也必须在列出组合以后再验证是不是合法组合，而合格验证过程对其后的产生、验证过程毫无好处。因此即使是缓式求值我也认为**完全**没有作用，这是算法上的问题，不是写法上的问题。

这就是我说的第二个算法完全没有价值的原因：它在**算法**上就杜绝了所有**实现**上的优化。因为它的顺序错了（先产生后验证，验证udi产生没有好处），一个相似的例子是朴素求素数和筛法，一个是产生并验证，效率低，一个直接跳，其实就是验证再产生。

我认为lisp是相同的问题，是先理论在实现，最后发现实现有问题，没法和计算机模型匹配。而其他语言是先考虑实现复杂度再抽象出理论。这样就和计算机模型兼容了，对计算机来说自然。但是这样就很考验一个人的理论水平了，不然就会变成ruby或者python式的patch语言。

这就是我举这个例子的含义。

对了，这个题你试着用haskell写写看哈，就当是教教我怎么写haskell呗。

OwnWaterloo

回复 90# starwing83

比如我举的那个 define/set!(scheme), defun(common lisp/emacs lisp)与 set(emacs lisp)的比较。
这样吧…… 就举set/setq， 貌似cl与el都支持的。

有两种需求：
1. 需要设置某个变量的值， 该变量编译时可知
2. 需要设置某个变量的值， 该变量只有运行时才知道

set可以完成两种。

1. 
   
2. (set 'x 12) ; x => 12
   
3. (set v 26) ; (eval v) => 26
   

复制代码

而setq就只能完成前一种。 在这个层面来说， 它是一种特殊化的set —— 编译时必须可知的set。
如果对一种范化机制的专门化使用， 能达到特殊机制的效率， 为什么还要提供那种特殊机制？


理由依然也有。 但其实是两种看待问题的方式。
例如scheme与lua支持尾调用优化， 而clojure不支持。 对一个纯函数式语言不支持尾调用优化是很要命的事， 所以它支持一种特殊的loop/recur， 然后将它翻译为goto。

如果换另一种角度看待loop/recur。
假设某种语言的尾调用优化支持并不完善， 但该语言依然鼓励程序员去使用， 因为总有一天这东西可以被完善。
而对那些必须不增长栈的尾调用， 可以将loop/recur当作一种询问： 这地方我确实需要它被优化， 编译器你能保证么？

还是以scheme与lua为例（支持尾调用优化的语言不多……），但它们都不支持：

1. 
   
2. (define factorial
   
3.   (lambda (x)
   
4.     (if (> x 0) (* x (factorial (- x 1))) 1)))
   

复制代码

必须得显式地写出那个accumulator。
这确实不算是尾调用， 但这种模式实在是太常见， 为什么要程序员一次又一次去自己写那个accumulator？ 编译器不能帮助翻译吗？

这时就可以让loop/recur作为一种询问，假设这样：

1. 
   
2. (define factorial
   
3.   (lambda (x)
   
4.     (if (> x 0) (recur (* x (factorial (- x 1)))) 1)))
   

复制代码

编译器能将代码进行某种转换后，保证recur可以复用栈空间吗？ 如果可以，就执行； 如果不可以， 那我人工转换， 直到某个版本支持这种转换。


这是两种看待问题的方式： 优先考虑程序员表达与优先考虑编译器实现 —— lisp与Fortran。
set比setq更范化， 所以优先提供前者， 并尽量让前者的专门化使用能达到后者的效率。
如果暂时没能达到， 可以让setq作为一种优化的hint。
如果这目标达到了无论是一开始就达到还是后续达到了再将setq废弃， 至少后续程序员就不需要了解setq这个东西。

而如果优先提供setq， 程序员就需要去找set， 或者根本就限制了程序员， 让他根本就想不到原来还可以这样。

用set/setq做类比， lisp已经在考虑setq的事情了。
r6rs里对翻译到C/JVM/CLI的实现方式来说， 要高效地实现尾调用优化确实很困难， 依然坚持将尾调用优化作为强制要求只是为了维持向后兼容。
类似的还有mutable/immutable cons/string。


最后， 即使添加了许多限制， 也依然没能伤害到lisp的精髓。
而且这种从一开始就考虑范化/通用化的设计的语言， 肯定比那些从一开始就只考一种又一种特殊化/专门化的设计的语言更简练。
它只在不得不特殊化的地方才做妥协。
lua的coroutine相比python的generator的例子你也清楚……

OwnWaterloo

回复 92# starwing83

你说的次序可以包含在产生内。
我都忘了你说的是要找=3还是找>=3的……  假设是找>=3吧。

你所说的剪枝是否是[1,1,1,?,?]后面4种组合肯定满足，不需要在验证了，直接产生？
[0,0,0,?,?]后面的4种组合肯定不满足，直接丢弃。

而如果一次产生一个完整的排列，比如[1,1,1,?,?]就被重复验证了4次，[0,0,0,?,?]同样？

可以不产生每个完整的排列，而直接产生决策树嘛……
不是验证一个完整的排列的序列， 而是验证产生排列的树， 如果没达到要求，直接放弃整个子树。
依然可以将产生与决策剥离。


嗯，产生完整排列的序列确实没希望了……

zhlong8

紧急召唤瓜瓜来把你们两个禁言了，都歪到第10页了

starwing83

回复 94# OwnWaterloo


    是吧……

我说的第二种方式就是产生整个组合，而产生决策树说白了就是dfs。

2gua

歪题就此打住！继续者禁言！

2gua

回复 92# starwing83


    歪题就此打住！继续者禁言！

2gua

回复 94# OwnWaterloo


    歪题就此打住！继续者禁言！

ning_lianjie

帖子中给的链接 点不进去了.