可可熊的窝

花了差不多两周的时间读完了Lua Programming in Lua (first edition) ，没找到pdf格式的，一直在官网在线看的，不是很舒服。看的似乎有点慢，里面的英文很简单，讲的内容难点也不多，也没有太多的代码去动手实践，似乎是受别人打击了:-)（看到人家博客里写道：“花两天的时间过了一遍PIL”）。

Lua作为一个脚本语言在很多地方与Python有相似之处，不过小巧了很多，数据类型、表达式、语句等都很精简，但是这并不影响Lua成为一个流行的脚本语言，灵活的table成就了Lua的强大，table可以演化出list,dict，更强大的是table可以实现OO，Lua并没有在语言级提供OO的实现，不过Lua的作者在PIL中展示了使用table完全可以实现近乎完美的OO编程，我觉得这是对整天鼓吹OO思想的人一个极大讽刺，OO其实没什么，C语言中使用结构体，函数指针也可以有模有样的进行OO编程。

Lua中也有很多函数式编程语言的影子，所以很多人把Lua和Scheme归为了近亲，不过俺不了解Scheme，对函数式编程也是一知半解，只能凑个热闹。

Lua之所以在游戏中使用比较广泛，是因为它可以很好的和C/C++结合在一起，可以很方便的互操作，通过使用Stack的方式。还有一个很重要的原因，Lua提供的是搭积木的原料，而不是搭好的建筑，所以你可以很灵活的用自己的方式去写程序。比如你可以用table实现一个完整的OO系统，然后在OO上面写程序(这里有一点很重要，基于table实现OO是很轻量的，而不是语言级的OO)；你也可以用metatable来实现Python中很强大的filter,map,reduce。

Lua中的table有点类似道家学说里面的”道”,”道生一，一生二，二生三，三生万物”，而table就是Lua中的“道”。

还得提一点Lua是完全用ANSI C编写的。

cocobear@0-0 /home/cocobear/Codes/lua-5.1.4/src $ wc *.c *.h -l | tail -1
17002 total

>     function foo (n)
>>       if n > 0 then return foo(n - 1) end
>>     end
> foo(100)
> foo(1000)
> foo(10000)
> foo(100000)
> foo(1000000)

如果函数最后一句是return g(…)这样的形式，Lua将会把这句解释为goto g(x)，因为这里除了对g函数调用，再没有别的事做，也不需要保存堆栈里调用函数的信息。因此上面即使调用很多次也没有出现堆栈溢出的问题，把上面的代码转换为Python:

>>> def foo(n):
...     if n>0: return foo(n-1)
...
>>> foo(100)
>>> foo(1000)
...
  File "<stdin>", line 2, in foo
  File "</stdin><stdin>", line 2, in foo
  File "</stdin><stdin>", line 2, in foo
RuntimeError: maximum recursion depth exceeded

很快出就现了堆栈溢出的问题，在这里表现为达到了递归调用的最大限制。Python自身没有实现尾部调用优化，不过也可以通过实现一个decorator办法来实现:

#!/usr/bin/env python2.4
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.

import sys

class TailRecurseException:
  def __init__(self, args, kwargs):
    self.args = args
    self.kwargs = kwargs

def tail_call_optimized(g):
  """
  This function decorates a function with tail call
  optimization. It does this by throwing an exception
  if it is it's own grandparent, and catching such
  exceptions to fake the tail call optimization.

  This function fails if the decorated
  function recurses in a non-tail context.
  """
  def func(*args, **kwargs):
    f = sys._getframe()
    if f.f_back and f.f_back.f_back
        and f.f_back.f_back.f_code == f.f_code:
      raise TailRecurseException(args, kwargs)
    else:
      while 1:
        try:
          return g(*args, **kwargs)
        except TailRecurseException, e:
          args = e.args
          kwargs = e.kwargs
  func.__doc__ = g.__doc__
  return func

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.

代码来自http://code.activestate.com/recipes/474088/

在这段代码里tail_call_optimized是一个decorator，在执行factorial函数前，这个decorator先执行，tail_call_optimized中通过sys._getframe()这个方法会返回一个frame对象，包含了堆栈顶部的信息，当发现当前调用是一个递归调用:

   if f.f_back and f.f_back.f_back
        and f.f_back.f_back.f_code == f.f_code:

则抛出一个异常，下面的代码则截获异常，继续执行，这样就避免了堆栈的使用，很巧妙的一种方式。

在python-dev的邮件列表里，有人曾经做过一个Python的尾调用优化的补丁，不过Guido拒绝了这个补丁:

I’m not interested in adding this to the official Python release.

One reason is that if an exception happens in such a tail-recursive
call, the stack trace will be confusing.

Another reason is that I don’t think it’s a good idea to try to
encourage a Scheme-ish “solve everything with recursion” programming
style in Python.

But feel free to maintain this as an independent modification, a la
Stackless — I’m sure there are people who would like to try this
out.

–Guido van Rossum (home page: http://www.python.org/~guido/)

Lua:

>   function newCounter ()
>>     local i = 0
>>     return function ()   -- anonymous function
>>              i = i + 1
>>              return i
>>            end
>>   end
>
>   c1 = newCounter()
> print(c1())
1
> print(c1())
2

Lua同Python类似，也可以嵌套定义函数，不过Lua嵌套函数可以访问上层闭包函数的局部变量，而在这个内嵌函数中这些变量不是全局变量，也不是局部变量，而是一种upvalue，与C语言中的static修饰的变量类似，所以在这里可以利用这个特性完成这个计数器。

Python:

  >>> def counter(last=[1]):
  ...     next = last[0] + 1
  ...     last[0] = next
  ...     return next
  ...
  >>> counter()
  2
  >>> counter()
  3

今天看Lua的时候觉得Python也应该有比较简单的办法写个计数器，找到一篇文章介绍这个小技巧，其中有一句话：

However, if named parameters are given mutable default values, the parameters can act as persistent memories of previous invocations. Lists, specifically, are handy mutable objects that can conveniently even hold multiple values.

Lua作为一个嵌入式（嵌入到其它语言中）的脚本语言，在很多地方与Python类似，这几天在看Programming in Lua 。