Continuation + Y Combinator

December 21, 2007 – 12:30 pm

我在介绍 Continuation 的文章中提到了一个 create_iterator 的实现,它接受一个函数名,内部去调用这个函数而实现 iterator 。最初我是想让它接受一个 block 的,但是后来却改成了函数名,正是在做二叉树的遍历时出了问题:二叉树遍历是一个经典的递归程序,而 block 没有名字,无法做递归,只好作罢。

不过在前一篇文章中我又介绍了 Y Combinator (其实我也是在一边学习的)正好可以用来做匿名递归,刚好可以把这两者结合在一起啦!

原来的 create_iterator 是这样的:

15
16
17
18
19
20
21
22
23
24
25
26
  def create_iterator(travel_method)
    caller = nil
    travel = lambda do
      self.send(travel_method) do |val|
        callcc do |cont|
          travel = cont
          caller.call(val)
        end
      end
      callcc { |cont| travel = cont }
      caller.call(nil)
    end

现在做一个 create_iterator_brk ,接受 block 而不是函数名作为参数,并把 create_iterator 做成它的浅包装:

15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
  def create_iterator_brk(brk)
    caller = nil
    travel = lambda do
      brk.call(lambda do |val|
                 callcc do |cont|
                   travel = cont
                   caller.call(val)
                 end
               end)
      callcc { |cont| travel = cont }
      caller.call(:end)
    end
 
    Iterator.new do
      callcc do |cont|
        caller = cont
        travel.call
      end
    end
  end
  def create_iterator(travel_method)
    create_iterator_brk(lambda { |brk|
                          self.send(travel_method, &brk)
                        })
  end

这样就 OK 了,来测试一下 Y Combinator :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  def y_comb(f)
    lambda { |*args| f.call(y_comb(f)).call(*args) }
  end
  def test_y_comb
    @tree.extend(ContinuationIterator)
    it = @tree.create_iterator_brk(lambda { |b|
                                     y_comb(lambda { |me|
                                              lambda { |b, tree|
                                                me.call(b, tree.left) unless tree.left.nil?
                                                b.call(tree.value)
                                                me.call(b, tree.right) unless tree.right.nil?
                                              }
                                            }).call(b, @tree)
                                   })
    seq = @inorder_seq.dup
    until seq.first.nil? and it.value.nil?
      assert_equal seq.first, it.value
      seq.shift
      it.inc
    end
  end

测试通过!通过 Y Combinator 来构造匿名递归函数,并通过 Currying 包装一下初始的 @tree 参数,就可以正常工作了!确实很有趣哦! :D

  1. 2 Responses to “Continuation + Y Combinator”

  2. 我只是觉得越来越Lisp了
    粗粗看了一下,没看懂 =.=

    By Jack on Dec 27, 2007

  3. 恩,我是觉得跟着步骤来,每一步都能看明白,可是最后突然发现已经得出结论了,有些大惊失色!就好象一个语句一个语句地看,都能认识,到最后却不知道这些平凡的语句怎么就成了一个精妙的程序了! :p

    By pluskid on Dec 27, 2007

Post a Comment