整数数组M的不动点a定义为 M[a] = a, 一个数组中可能有一个或者多个不动点, 也可能一个也没有,  因为不知道数组的函数分布, 无法判断是否停机,  如果采用跌代法尽可能的求出不动点可以如下代码
def fixpoint0(a):
    if a <= len(M) and a >= 0:
        if M[a] == a:
            return a
        return fixpoint0(a)
    return -1

以上使用递归的方法处理跌代, 比较容易理解, 但是可能造成栈溢出, 遂改为循环跌代
def fixpoint1(a):
    while a <= len(M) and a >= 0:
        if M[a] == a:
            return  a
        a = M[a]
    return -1
这样就运行良好了. 可是虽然不会栈溢出, 却可能出现无限循环,  例如当 M = [1,6,4, 3, 0, 2, 1, 1], 不动点是3, a可能重复的为1, 6, 1, 6, …
如图

可见虽然有不动点存在,  死循环造成的不能停机是个大问题, 如果能够检测到死循环并返回, 即便不能找到不动点,也可以避免无意义的消耗.
曾经有个著名的判断单向琏表的方法: 使用两个指针p, q, p 每次向前走两部, q 走一步, 当p==q的时候, 则可认为,此处是个环, 既放弃继续探索.  此方法也可以应用到本问题的跌代中来,  a =M[a] 同 q= q.next类似. 代码如下
def fixpoint2(a):
    b = a
    while 1:
        if a <= len(M) and a >= 0:
            if M[a] == a: return a
            a = M[a]
        else:
            return -1
        if a == b:return -1 #环判断

        if a <= len(M) and a >= 0:
            if M[a] == a: return a
            a = M[a]
        else:
            return -1
        if a == b:return -1  # 环判断

        b = M[b]
    return -1
其中if a == b:return -1 可以检测出死循环的出现并返回-1.  应用该方法于上面的M, 果然发现可以终止死循环

However, 从上面的M看到 不动点是存在的, M[3] = 3, 能否尽可能的找到该点呢? 可以修改一下上述代码, 当检测到环时, 加一个扰动, 看看能否跳出此环. 当然不能保证一定找到, 但是本着实用主义的观点, 多尝试一些, 机会更多一些. 为了防止新的环出现, 可以规定尝试的次数, 比如设定最多允许尝试10次
def fixpoint3(a):
    b = a
    t = 10 #最多尝试次数
    while 1:
        if a <= len(M) and a >= 0:
            if M[a] == a: return a
            a = M[a]           
        else: return -1

        if a == b:
            if t <= 0: return -1 #尝试次数多了
            t -= 1
            a = a > 1 and a – 1 or a + 1 #扰动
            b = a

        if a <= len(M) and a >= 0:
            if M[a] == a: return  a
            a = M[a]
        else: return -1

        if a == b:
            if t <= 0: return -1 #尝试次数多了
            t -= 1
            a = a > 1 and a – 1 or a + 1 #扰动
            b = a           
        b = M[b]       
    return -1

Ok, 就这么多了

月亮躲避疯狂的士兵
律师打败急切的金银
程序吞咽曾经的声音
大米遍历笨拙的感情

寒冷打开放荡的森林
美女躲避拼命的地球
雄狮拒绝苍凉的山羊
大豆检查辽阔的声音

在啄木鸟社区上有篇文章 http://wiki.woodpecker.org.cn/moin/PyIgoJudger， 使用python语言作围棋死活子的判断。代码行数229行。我觉得用ruby写可能会更短一些。所以我用Ruby语言，使用同样的算法和相似的数据结构，重写了这段代码。 代码行数113行，约是python代码的一半左右。我想这可以作为语言比较的参考之一（也许仅仅参考，没有更多意义）. 相关说明，请看那篇文章吧，我这里就不重复了


require ’set’

class Board
  SIZE = 19
  def initialize
    @stones = [nil] * SIZE * SIZE  
    @black_block = Set.new
    @white_block = Set.new
  end
  def each_stone
    @stones.each {|stone|
      yield(stone) if stone
    }
  end 
  def add_stone(stone)
    return if not [BlackStone, WhiteStone].include?(stone.class)
    c = c = stone.x * SIZE + stone.y
    @stones[c] = stone if inboard?(stone.x, stone.y) && (@stones[c] == nil)
  end
  def inboard?(x, y)
    return (x>=0 and x <SIZE and y>=0 and y<SIZE)
  end
  def get_stone(x, y)
    return @stones[x * SIZE + y] if inboard?(x, y)
  end
  def available?(x, y)
    return (inboard?(x,y)) && (@stones[x * SIZE + y] == nil)
  end
  def new_block(stone)   
    stone.block = Block.new([stone])
    if stone.class == BlackStone
      @black_block << stone.block
    else
      @white_block << stone.block
    end
  end
  def merge_block(stone, b1, b2)
    b1.merge b2
    b2.each { |stone|  stone.block = b1 }
    if stone.class == BlackStone
      @black_block.delete b2
    else
      @white_block.delete b2
    end
  end
  def print_breath
    puts "Black"
    @black_block.collect {|block| puts block.get_breath.size }
    puts "White"
    @white_block.collect {|block| puts block.get_breath.size }
  end
end

class Block < Set
  def get_breath
    a = Set.new
    each {|stone|
      stone.available_neighbour(a)
    }
    return a
  end
end

class Stone
  attr_reader , :y
  attr_accessor :block
  def initialize(board, x, y)
    @board = board
    @x = x
    @y = y
    @board.add_stone(self)
  end
  def each_neighbour
    [[@x, @y - 1], [@x + 1, @y], [@x, @y + 1], [@x -1, @y]].each {|x, y|
      stone = @board.get_stone(x, y)
      yield(stone) if stone
    }
  end
  def available_neighbour(s)
    [[@x, @y - 1], [@x + 1, @y], [@x, @y + 1], [@x -1, @y]].each {|x, y| 
        s << [x, y] if @board.available?(x, y)
    }
  end
  def scan_block
    @board.new_block(self) if @block == nil
    has_naighbour = false
    each_neighbour { |stone|
      has_naighbour = true
      if stone.class == self.class       
        @board.merge_block(self, @block, stone.block)  if @block !=stone.block && (stone.block != nil)       
      end
    }
  end
end

class BlackStone < Stone
end
class WhiteStone < Stone
end

if __FILE__ == $0
  board = Board.new
  [[4,5], [4,6], [18,7]].each {|x, y|
    stone = BlackStone.new(board, x, y)
  }
  [[5,5], [5,6], [17,7]].each {|x, y|
    stone = WhiteStone.new(board, x, y)
  } 
  board.each_stone {|stone|
    stone.scan_block
  }
  board.print_breath
end

Python 2.5 alpha 1 发布了，里面有支持partial function的部分， 不过在我看来，只是伪的partial对象, 这恐怕也是partial function不敢称partial evaluation的意思吧. 其实是把参数和函数先暂存起来包装成一个对象 ,等全部参数给齐了再一起计算.真正的partial 应该是,函数中一个表达式所需要的操作数给了以后就可以立刻运算了,这样的partial才能被编译用来优化.
def abc(a, b, c):
    print b, c
    return a + b + c

当给abc函数 b, c 参数的值以后, 就可以计算print b, c 输出了. 不用给a的值也可以.而且得到的是一个新的函数
def abc1(a):
    return a + 10
假设 b + c的值已经为10

现在的结果

>>> s = functional.partial(abc, b = 3, c = 7)
>>> s.keywords
{‘c’:7, ‘b’:3}
>>> s.func
<function abc at 0xb7f289cc>
>>> abc
<function abc at 0xb7f289cc>

还不如我以前些的用decorator来作的curry方便

b = 1
c = 2
a = b
b = c
那么a 是多少？ 当然是1了，一般的程序语言执行，都得到这样的结果。但是通过 lazy evaluation,你将得到不同的结果： a = 2,  因为a依赖于b,而b依赖于c。 我用python语言实现了一个lazy evaluation的上下文，实例如下.

le = LazyContext()
# 使用decorator lazilize, 函数也可以Lazy化.
@le.lazilize
def myadd(a, b):
    print "now calculate"
    return a + b
le.b = 1
le.c = 2
le.a = le.b * 8
print "a is", le.evaluate(le.a)
le.d = myadd(9, 12)
le.f = le.b  
le.b = le.c
   
print "a is", le.evaluate(le.a)  
print "d is ", le.evaluate(le.d)
print "f is ", le.evaluate(le.f )

得到的结果是
a is 8
a is 16
d is  now calculate
21
f is  2

支持多种运算符号 +, -, *, /, neg, and , or not, ….. 但是限制是，一个二元运算符号，必须lazy变量放在前面。 如 le.a + 8 是合法的，8 + le.a就不合法了. 如果仔细照料，应该不是一个大问题。后附代码
#lazy.py
import operator

supported_ops = ['__abs__', '__add__', '__and__', '__concat__',
                     '__contains__', '__delitem__', '__delslice__',
                     '__div__', '__eq__',  '__floordiv__', '__ge__', '__getitem__',
                     '__getslice__', '__gt__', '__inv__', '__invert__',
                     '__le__', '__lshift__', '__lt__', '__mod__', '__mul__',
                     '__ne__',  '__not__', '__or__',
                     '__pos__', '__pow__', '__repeat__', '__rshift__',
                     '__setitem__', '__sub__', '__setslice__',  ]

def call_object(name):
    return lambda self, *args: Lazy_M(self.context, name, self, *args)

def set_ops(cls):
    global suported_ops
    for fname in supported_ops:
        setattr(cls, fname, call_object(fname))

class LazyObj:
    name = ""  
class NameRef(LazyObj):
    def __init__(self, ref_name):
        self.ref_name = ref_name  
   
class Lazy_SimpleObj(LazyObj):
    def __init__(self, context, value):
        self.value = value
        self.context = context      
    def evaluate(self):       
        return self.context.evaluate(self.value) 
   
class Lazy_M(LazyObj):
    def __init__(self, context, funcname, opj, *args, **kwargs):
        self.args, self.kwargs = args, kwargs
        self.opj = opj
        self.funcname = funcname
        self.context = context
       
    def evaluate(self):
        tv = self.context.evaluate(self.opj) 
        f = getattr(tv, self.funcname)
        if callable(f):
            a, b = [self.context.evaluate(t) for t in self.args], dict([(k, self.context.evaluate(v))  for k, v in self.kwargs.items()])
            return f(*a, **b)

class Lazy_F(LazyObj):
    def __init__(self, context, func, *args, **kwargs):
        self.args, self.kwargs = args, kwargs
        self.func = func
        self.context = context      
    def evaluate(self):
        return self.func( *[self.context.evaluate(t) for t in self.args], **dict([(k, self.context.evaluate(v))  for k, v in self.kwargs.items()]))
           
class LazyContext:
    def __init__(self):
        self.__lazy_objs = {}
        set_ops(LazyObj)
    def lazy_objs(self):
        return self.__lazy_objs
    def evaluate(self, obj):       
        if obj.__class__ == NameRef:
            return self.evaluate(self.__lazy_objs[obj.ref_name])
        elif isinstance(obj, LazyObj):
            return obj.evaluate()       
        else:
            return obj  
    def __setattr__(self, name, value):
        if name.find("__") < 0:
            if isinstance(value, LazyObj):
                if value.name: value = NameRef(self, value.name)                   
            else:
                value =  Lazy_SimpleObj(self, value)
                value.context = self              
            value.name  = name               
            self.__lazy_objs[name] = value
        else:
            self.__dict__[name] = value

    def __getattr__(self, name):       
        if name in self.__lazy_objs:
            obj =  self.__lazy_objs[name]
            nr = NameRef(self, name) 
            return nr
        else:
            return self.__dict__[name]
       
    def lazilize(self,func):
        def __lazy_call(*args, **kwargs):
            m = Lazy_F(self, func, *args, **kwargs)
            return m
        return __lazy_call

The best program source editor is the editor on abstract syntax trees. It walks among tree nodes instead of text lines.

感觉：
慢， 只一个man sh命令， 打印了数分钟，ls命令也是， 如果这就是pdp11的真实速度，那么能体会到当初程序员的辛苦, 这也是要把命令设置成ls, cd, rm这种超短格式的原因吧。 不过当建立用户dmr并login进去后，速度就变快了。
很多方便的命令行工具都没有，less , more, vi. 编辑只能用ed, shell也只有两种, Bourne sh和osh两种. 基本的用户访问控制则已经比较完备, UNIX的设计思想基本体现出来了. 作为1979年的老家伙，已经很不错了。

我来从历史角度对比一下Perl和Python语言的产生和发展, 尽量客观不带个人好恶
Perl 的前身语言：C, awk, sed, sh, 以系统管理为目标, 强调使用性而不是美观(Perl最早的man page里提到); Python来源于ABC, 一种同BASIC目标类似的语言，属于学习曲线比较平缓的那种。
Perl 直接创始自工作任务， Python是作者工作经验的总结.
Perl 早期属于UNIX文化；Python 建立在Amoeba这种实验性系统上.
Wall 是个有激情的基督徒, 所受的教育是语言学专业. Guido 是CS专业毕业, 没有听说有异常的宗教信仰.
Perl 的兴起是80末-90初, 到95年以后发展进入成熟阶段, 标志是CPAN和perl 5, 此时正是UNIX发展的一个高潮, linux, bsd还有许多商业系统大都从那时候开始, perl作为unix系统管理的便利工具，自然也得到了发展的机会，其应用领域和社区也得到扩展. WEB应用的发展，CGI使用perl. Python的兴起则晚的多， 属于90年代末期发展，到2000年以后才比较成熟, 但是适用的范围比较广泛，具有后发的优势. 不幸的是，python 遇见了java，即使在现在现在python和java所覆盖的应用领域（除了嵌入系统）都是差不多的， java以其简洁的语法和模型在sun, oracle, ibm等大公司的推介下迅速成为网络程序设计的主流。 python在这个阶段只能作为非主流的语言存在, 和其他数百个程序设计语言的地位没有什么两样，当然程序界历来是主流和非主流并存发展，python的社区仍然在不断的扩大（可谓韬光养诲？）。 等人们疲倦了java以及java和c#（.net)的争执，语言的多样化浮上前台(语言多样化在技术上的原因应该是组件技术和虚拟机的发展，使得一个工程可以用多种语言实现)，python, ruby, lua, lisp/scheme, ocaml等待都能吸引人们的眼光，python更因其简洁的语法和丰富的功能得到更多的青睐, 欣欣向荣。而此时perl的进展一直比较平缓。

Dennis Ritchie 设计C语言的时候, 认为赋值语句的使用频率多于相等判断，所以用比较短的=当作赋值语句，比较长的==当作等号判断。 这样可以少敲几个键盘增加程序源代码的信息量。而pascal则相反， 赋值用:=两个字符表示，判断则用一个=字符表示, 不知从何理由, 也许是=对应数学上的表示而:=代表有副作用 。