有多少科班毕业的时候还不会递归？

captivated

回复 18# OwnWaterloo


    嗯, 这个明白了, TKS

OwnWaterloo

回复 19# captivated

UPDATE: 我去。。。 又有文字被替换成笑脸了。。。


>> 是后面的内容还是(scheme的)不同的解释器实现?

defn那些是clojure。

如果用scheme(sicp用的语言)，可以试试racket。。。 因为它有各种变体。。。 比如上面的代码（尤其后面那段）
#lang scheme
就会死循环

#lang lazy
#lang lazy/scheme ;不记得是哪个了
就不会


不过实际使用中racket各种坑爹。。。  实际使用中scheme也各种坑爹。。。
如果只是为了sicp， 可以继续mit/racket。。。
如果打算实际使用lisp， 可以学学clojure。。。  反正lisp都差不多。。。


>> 第一章里面有讲Applicative order versus normal order, 就是说应用序是一般的顺序(先求值再替换), normal order就是先替换, 最后归约, 所以一般所说的惰性求值是不是就是normal order?

至于applicative和normal。。。 （我又忘记哪个是哪个了。。。） outer 优先的还不是lazy。
你看前面举的例子里有很多重复求值的地方。

比如， (square (double 3)) ; (* (double 3) (double 3)) ; (* (+ 3 3) (+ 3 3)) ; (* 6 6) ; 36
lazy的话， square被展开后， 两个(double 3)是同一个thunk。。。 可以避免(double 3)被重复计算。。。
文字表现这里不太容易。。。  有图形会清楚些。。。


>>不过书上似乎也说解释器使用何种求值顺序是没关系的, 只要能得到正确结果 -- 所以有个问题, 确实保证不管如何定义函数, 这两种求值序都能得到相同的结果?

使用inner优先的策略能得到结果（而不是死循环）的那些计算， 那outer优先一定也能得到结果（无论是否share，都不会死循环），并且结果相同。 比如(square (double 3))。
反之对outer优先能得到结果的那些计算， inner优先可能就化简不出来。。。 比如(if (* 2 6) (g 0) (+ 1 2))。

嗯，前提是没有副作用。。。
(square (begin (display "!" (double 3)))
(square (begin (display "!" ) (double 3))) ， 显然不同的策略会有不同的输出。。。
不过直到那一章，都是在说纯函数的计算。。。


>> 求解释... 同时书上也提

所以sicp这个例子就没举好。 最好是 (test (- 12 12) (p)) 。
这样从"文本"上就能区别 test 的参数x是求值得到的0，还是未求值的表达式(- 12 12)。
然后你再化简看看吧。。。 只能帮到这里了

OwnWaterloo

回复 20# captivated

同上，把(test 0 (p)) 改成 (test (- 12 12) (p)) 会更清楚一些。。。

UPDATE:， 再改， 把p改成18楼的g那样， 这样过程会更清楚一些， 可以从"文字上"区分出表达式本身与表达式化简的过程。

captivated

回复 22# OwnWaterloo


    嗯. 我了解了, 就是说, Lazy是normal-order(就是先展开, 最后才化简, outer优先). 但是Lazy同时又能够避免重复计算(outer优先的还不是Lazy), 是这样子吗?

    update: outer优先还不是"先展开 最后才化简"这种简单描述. inner优先还是outer优先, 是说先展开"函数", 还是先展开"参数". 先展开"参数"是inner优先. 先展开"函数"是outer优先. 所以inner优先和outer优先是更精确的表述.

    update: --> 希望OwnWaterloo说一声: "you got it!"(前提是我确实got it), o(∩_∩)o 哈哈

   update:

1. (define (double x) (+ x x))
   
2. (define (square x) (* x x))
   
3. (square (double 3))

复制代码

可以优先化简inner (square (+ 3 3)) ; (square 6) ; (* 6 6) ; 36
--> 即先求值参数后应用, (double 3)是(+ 3 3) --> 6, (square 6) --> (* 6 6) --> 36, 这个是书上的applicative-order

也可以优先化简 outer (* (double 3) (double 3)) ; (* (+ 3 3) (+ 3 3)) ; (* 6 6) ; 36
--> 这个是normal-order

OwnWaterloo

回复 24# captivated

差不多是这样吧。。。
说差不多是因为我每次都要忘记那些术语是怎么说的。。。 applicative, normal一点都不形象啊。。。
也有可能也有可能是这些术语诞生的数学背景我不知道的原因。。。


总之， inner/outer是化简的"顺序"方面的区分。
lazy是在outer这种顺序的基础上，再增加了share，避免重复计算。
而normal是否仅仅指顺序？ 即，只要是outer优先，无论是否share，都算normal？ 还是outer并且重复计算的才叫normal？
这个我也没把握。。。  应该是outer+重复计算才叫normal， outer+share好像叫call-by-name（你看这名字。。。 形象么。。。）
不过反正是术语嘛。。。 对自己理解含义影响不大，知道有这么回事就行。。。 大的影响发生在与人交流的时候。。。 双方用同一词说的却是不同事。。。

captivated

回复 25# OwnWaterloo


    http://mitpress.mit.edu/sicp/ful ... 10.html#%_sec_1.1.3

    里面的Applicative order versus normal order一节.


    嗯, 我想applicative order和normal order只是指顺序, 没有理会share. Lazy就是normal order加上share.


    update: 果然还是OwnWaterloo的解释更地道. TKS.
    update: inner和outer形象得多, 也更容易记住. Lazy就是outer + share. 嗯.

OwnWaterloo

回复 15# starwing83

如果要更仔细的说的话。。。 得区分"递归边界"到底是指 1) 定义上是否有边界 2) 化简时是否有边界。。。

fib在定义上是没有递归边界的。
但整个化简是从(take ...)开始的， take是有边界的， 无论是take的定义，还是(take 10 ...)的化简都有边界， 所以计算能得到一个结果。

如果像你说的那样要取无限个，即从(fib)开始化简。。。  而fib的定义是没有边界的。。。 就死翘翘了。。。


反之如果是strict， 如果定义上无边界， 化简也从它开始， 那化简时也就无边界， 怎么都死翘翘。。。 区分两者没什么意义。。。
而non-strict可以把递归边界从函数定义（定义处不一定全都需要边界）处移走， 让它的直接或间接调用者去考虑边界（有些函数的定义需要有边界）。。。  并且还是要保证整个计算时有边界的（得从那些定义处有边界的开始）。。。

OwnWaterloo

回复 24# captivated

>> you got it!
out了。。。  现在的流行句式不是：XXX只能帮你到这了么。。。  我又忍不住笑了。。。


回复 26# captivated

因为scheme（甚至大多数lisp）都不是lazy的。。。
所以lisp社区对lazy带来的consequence。。。 感觉普遍理解不够。。。
比如他们都很看重宏(macro) 。。。

嗯，以前我也是这样，把macro看成一个很牛叉的工具。
不过因为C++的经验，我知道有些东西是应该作为最后手段的。。。
不像那些不知天高地厚的动不动就"it can be solved by macro!"


但在一个使用lazy求值的lisp里， macro的作用会被进一步缩小。。。 缩小到只有"运行前"求值是必须由macro做的。
而现在很多macro的使用，其实仅仅是在strict中局部模拟lazy而已。。。

因为macro可以做到lazy能做到的所有事（延迟求值），但lazy不能做到macro能做到的所有事（运行前求值），所以只有macro的语言比macro+lazy的语言更简练干净纯粹？ 很多lispor就是这样想的。。。
但macro其实做不到。。。 因为macro（在大部分lisp里都）不是first class value。。。


举个例子的话。。。 比如(set-timer 12 compuation)。

如果是lazy， 那就是这样了。
set-timer将 compuation这个unevaluated thunk记录在某个地方。
当timer触发的时候， compuation才会被求值。

而如果是strict，显然compuation的计算应该被延迟，否则在set-timer函数之前compuation就被计算了。
所以应该是(set-timer 12 (lambda () compuation))， 用函数将compuation延迟。
很多时候。。。 lispor就会将set-timer搞成一个宏。。。
(setTimer 12 compuation) 展开为 (set-timer 12 (lambda () compuation))。。。

但set-timer和(lambda ...)都是first class value， setTimer（在大多数lisp里都）不是。 前者可以被这样用：

1. 
   
2. (let ((xs (range 12)))
   
3.   (map set-timer xs (map (lambda (x) (lambda () (display x) (newline))) xs)))
   

复制代码

这里产生了12个compuation， 依次是输出1-12和换行。

如果写timer库的人同时暴露set-timer和setTimer接口都还好。。。 问题是有些人只暴露setTimer， set-timer他自己内部用。。。

BTW： lambda缩写就很重要了。。。  可以很轻易的将一个compuation包裹到一个0参函数里。
clojure是fn和#()read-macro， haskell 的匿名函数是 \ x -> ... （但其实haskell不需要，因为它是non-strict)。
而scheme社区依然认识不到这点。。。 新加入的cut就是坨屎。。。

pandaiam

cl不是惰性求值..
宏的话不知道,还没接触过..

"惰性求值"这玩意真的这么强大(不到需要的时候不求值,执行变快?...)?
我知道好像就haskell是.

另外,racket这个东西感觉真的很好玩,目前看htdp2e,用drracket

nizvoo

避免递归 。