Guido hates tail recursion elimination

大叔对尾递归还是有点意见的....或许大叔对 FP 不感冒. 其实对于某某某无比吹捧 FP 还是很反感的, 或许搞技术的大都凌驾吧. 不过侧面能说明一些问题, 如果 python 支持尾递归优化, 那么.... 其实 python 对 lambda 等的支持很有限. 大叔说: 简言之, 为什么 Python 不用呢, 因为不 Pythonic. 具体就是: TRE is incompatible with nice stack traces. Python 不会让程序员写基于 TRE 特性的代码.

Once tail recursion elimination exists, developers will start writing code that dependson it, and their code won't run on implementations that don't provide it: a typical Python implementation allows 1000 recursions, which is plenty for non-recursively written code and for code that recurses to traverse, for example, a typical parse tree, but not enough for a recursively written loop over a large list.

还有更牛的理由

I don't believe in recursion as the basis of all programming. 

; 这个我也想对某些迷信 FP 的人说. 

最后, 它提到了一些 Python 中如果使用 TRE 的后果, 如果实现 TRE, 那么将有更多的问题需要解决. 所以, 既然不是 FP, 就没必要整那么多 FP 的东西. lambda, 方便而已, 不是让你整 FP 的.

欢迎拜见大叔:

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

python 中 lambda 的倒掉

灵感来自: http://math.andrej.com/2009/04/09/pythons-lambda-is-broken/ 长话短说, 先看代码.

>>> fs = [(lambda n: i + n) for i in range(10)]
>>> fs[3](4)
13

不觉得该是 3 + 4 = 7 么?

>>> [f(4) for f in fs]
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13]

.....撞石头上了... 换 def 看:

>>> fs = []
>>> for i in range(10):
...    def f(n): return i+n
...    fs.append(f)
...
>>> [f(4) for f in fs]
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13]

其实这时候已经有点眉目了, 继续看下去:

>>> fs = []
>>> for i in range(10):
...    def f(n, i=i): return i+n
...    fs.append(f)
...
>>> [f(4) for f in fs]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

作者提到 Haskell 是没问题的:

Prelude> let fs = [(\n -> i + n) | i <- [0..9]] 
Prelude> [f(4) | f <- fs] 
[4,5,6,7,8,9,10,11,12,13]

想也是~ Haskell 就是做这个的. 怎么回事呢? 我觉得是 lexical scope(static scope) 和 dynamic scope 的关系. lisp 中一般都会讲到这个. 在 def 使用时就已经可以看出, i 在这里作为全局变量了(或者说是上一级变量), 而调用的时候使用的是当前全局环境中的 i. 而 def f(n, i=i) 中, 局部 i 覆盖了全局的 i, 那么也就是说, def 参数列表中默认值参数在定义后就已经绑定.

python 的 yield

以前只是类似生成器表达式那样使用... 其实有N多牛B用法. 真长见识~! http://www.dabeaz.com/coroutines/index.html 例如:

# grep.py
#
# A very simple coroutine

def grep(pattern):
  print "Looking for %s" % pattern
  while True:
    line = (yield)
    if pattern in line:
         print line,
# Example use
if __name__ == '__main__':
  g = grep("python")
  g.next()
  g.send("Yeah, but no, but yeah, but no")
  g.send("A series of tubes")
  g.send("python generators rock!")

对于生成器函数来说, 有 next() ,send(), throw() 方法.

• next() 比较容易理解.
• send(arg) 向生成器发送参数, 会被 line = (yield) 捕获.
• throw(typ[,val[,tb]]) -> raise exception in generator, return next yielded value or raise StopIteration. 参数分别是, 异常类型, 异常 str, traceback object.

这算是最简单的.... 配合函数修饰符, 相当强大.... yield ...

尝试 git

尝试了下 git ... http://www.projectlocker.com/ 提供免费的 git service, 以及更有名的 github 需要使用 ssh-keygen 生成个 pub key 加到网站里. 某目录下

git init // 初始
git add * // 加入文件/目录
git status // 察看状态
git show
git commit -m "Message here" // commit 提交
git remote add xxxx git://xxxx/xxx.git/   // 加入 remote
git branch   // 分支管理
git branch -r // 察看 remote branch 
git push xxxx master
git fetch // 抓取版本
git checkout // 导出分支内容,切换分支
git-pull = git-fetch + git-merge
等等

数据结构=brainfucking.作业.

设计一个算法,用尽可能少的辅助空间将顺序表前 m 个元素和后 n 个元素进行互换. {a1,a2,a3..am,b1,b2,b3..bn} => {b1,b2,b3..bn,a1,a2,a3..am} 让我想起某单词. brainfucking. now let's fucking. 问题简化到 int 数组吧. 差不多. 函数原型:

void swapSeq(int *lst, int m, int n);

惯例, lst 索引为 1..(m n) "用尽可能少的辅助空间"..... 果然 brainfucking. 函数里定义某数组, 把 b1~bn, a1~am 按顺序复制再拿出来, OK. 不好玩. 直觉告诉我们, 既然是 brainfucking..... Show 实现.

void swapSeq(int *lst, int m, int n)
{
   int i,tmp;
   if(m n<= 1)
         return ;
   for(i=1; i<= m && i<= n; i )
     {
         tmp = lst[i];
         lst[i] = lst[m i];
         lst[m i] = tmp;
     }
   if(m> n)
       return swapSeq(lst n, m-n, n);
   if(n> m)
       return swapSeq(lst m, m, n-m);
}

---

发现可爱的尾递归. OK, 立即抛弃, 上 while~!

void swapSeq(int *lst, int m, int n)
{
   int i,tmp;
   while(m n> 1)
   {
       for(i=1; i<= m && i<= n; i )
         {
             tmp = lst[i];
             lst[i] = lst[m i];
             lst[m i] = tmp;
         }
       if(m> n)
       {
           lst = n;
           m = m-n;
       }
       else if(n> m)
       {
           lst = m;
           n = n-m;
       }
       else
           return ;
   }
}

---

抛弃题目本质. BT 下. BT 无罪.

void swapSeq(int *lst, int m, int n)
{
   int i;
   if(m n<= 1)
         return ;
   for(i=1; i<= m && i<= n; i )
     {
         lst[i]^= lst[m i];
         lst[m i]^= lst[i];
         lst[i]^= lst[m i];
     }
   if(m> n)
       return swapSeq(lst n, m-n, n);
   if(n> m)
       return swapSeq(lst m, m, n-m);
}

---

其实递归未优化的消耗还是很大的, 开优化另说.

void swapSeq(int *lst, int m, int n)
{
   int i;
   while(m n> 1)
   {
       for(i=1; i<= m && i<= n; i )
         {
             lst[i]^= lst[m i];
             lst[m i]^= lst[i];
             lst[i]^= lst[m i];
         }
       if(m> n)
       {
           lst = n;
           m = m-n;
       }
       else if(n> m)
       {
           lst = m;
           n = n-m;
       }
       else
           return ;
   }
}

字符计数

Smalltalk(8063446)  8:58:35 
>>> from collections import Counter 
>>> c=Counter() 
>>> for letter in 'here is a sample of english text':
...   c[letter] += 1 
... 
>>> c
Counter({' ': 6, 'e': 5, 's': 3, 'a': 2, 'i': 2, 'h': 2, 'l': 2, 't': 2, 'g': 1, 'f': 1, 'm': 1, 'o': 1, 'n': 1, 'p': 1, 'r': 1, 'x': 1}) >>> c['e'] 5 >>> c['z'] 0 
;; 其实是个 reduce 过程.  
Feather(85660100)  11:45:28 
>>> reduce(lambda d,s: dict(d, **{s:d.get(s,0)+1}), \
            'here is a sample of english text', {}) 
{'a': 2, ' ': 6, 'e': 5, 'g': 1, 'f': 1, 'i': 2, 'h': 2, 'm': 1, 'l': 2, 'o': 1, 'n': 1, 'p': 1, 's': 3, 'r': 1, 't': 2, 'x': 1} 

其实要说的是.... dict() 很强大很强大. 以及其他 python type 函数.