Archive for the ‘Lambda’ Category

Ruby 1.9.0 is released

Wednesday, December 26th, 2007

rubyRuby 1.9 在圣诞节如期发布啦!

Hi,

We are happy to announce of the release of the 1.9.0 the development
release. You can fetch it from:

ftp://ftp.ruby-lang.org/pub/ruby/1.9/ruby-1.9.0-0.tar.bz2
407cc7d0032e19eb12216c0ebc7f17b3

ftp://ftp.ruby-lang.org/pub/ruby/1.9/ruby-1.9.0-0.tar.gz
b20cce98b284f7f75939c09d5c8e846d

ftp://ftp.ruby-lang.org/pub/ruby/1.9/ruby-1.9.0-0.zip
78b2a5f9a81c5f6775002c4fb24d2d75

We hope this helps you to enjoy hacking. Happy Holidays.

matz.

虽然没有通过所有的测试,不过也是 Hard Working ,始终是辛苦了,也算是给大家的一个圣诞大礼了!

Hi,

For your information, here’s the test result from the released Ruby
1.9.0:

sample/test.rb
858 tests 0 failed

bootstraptest/
821 tests 0 failed

test/ruby/test_*.rb
849 tests 1935064 assertions 1 failures 0 errors

test-all
3263 tests 2275950 assertions 8 failures 6 errors

We couldn’t make it error free, but it’s fairly good, we hope.

matz.

Continuation + Y Combinator

Friday, December 21st, 2007

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

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

原来的 create_iterator 是这样的:

Read the rest of this page »

the Y Combinator

Thursday, December 20th, 2007

今天看到 A Use of the Y Combinator in Ruby 这篇文章,却被他的代码搞晕了,半天看不明白,于是只好另辟蹊径,不看他的代码,却自己来写一下,如果我写出来的代码和他一样,那自然就明白了,如果不一样,也好对比一番,相信也更容易理解了。

这里要解决的问题大致就是“匿名递归函数”的问题。递归函数大家都知道了,例如经典的阶乘函数:

1
2
3
4
5
6
7
def fact(n)
  if n == 0
    1
  else
    n*fact(n-1)
  end
end

匿名函数也没啥,在许多语言里,函数就和普通的值没有什么区别,不一定非要有一个名字,例如 lambda 就可以创建一个匿名函数:

func = lambda { puts "hello" }

那“匿名递归函数”又是什么呢?首先它是匿名的,哦,那么用 lambda 好了,其次它是递归的,这也好办,自己调用自己嘛。问题就出在这“自己”上!看那个阶乘函数代码的第五行 n*fact(n-1) ,原来函数有 fact 这个名字,可以直接调用,现在匿名了,如何调用这个“自己”呢? thisself ?可惜都不是!必须要有一个变量来引用到这个“自己”才行,如果没有一个全局(或在某个作用域里)的名字,那么至少要作为一个参数。用 Y combinator 正好可以解决这个问题,于是程序可以这样写了:

1
2
3
4
5
6
7
8
9
fact = y_comb do |me|
  lambda { |x|
    if x == 0
      1
    else
      x*me.call(x-1)
    end
  }
end

这里“自己”(也就是第二行的那个 lambda 产生的匿名函数)被作为参数 me 传递进来。这个 y_comb 究竟是如何做的呢?你可以自己尝试实现一下,如果实在迫不及待或者一时想不出来,就跟我一起来探索神奇的 Y combinator 吧!

Read the rest of this page »

Write a Scheme Interpreter in Ruby(2): THE Interpreter

Sunday, December 16th, 2007

leaf.gif上一篇文章中我们实现了对 scheme 代码的 parse 和 analyze 过程,并得到了一些可以直接 eval 的对象(String ,Symbol ,Number 和 Cons ),可是光凭这些并不足以让我们的解释器跑起来。这次我们要添加必要的代码,实现一个真正可运行的解释器。

在前面的代码中,我们已经实现了 scheme 中的几个基本对象的求值:作为 atom 的 String 、Symbol 和 Number 以及作为 list 的 Cons 都已具体实现了 eval 方法。事实上 atom 的求值已经不需要加什么其他代码了,但是 Cons 类却是耍了一个把戏,仔细看 Cons 类的 eval 方法:

    def eval(binding)
      func = @car.eval(binding)
      args = @cdr
      func.call(binding, args)
    end

其实把责任推脱给了 func 对象的 call 方法。那么 func 应该是一个什么对象呢?一个 scheme 解释器要能跑起来,至少需要一些内置的基本过程(primitive-procedures),并且要让用户能够自定义过程(compound-procedure)。要内置哪些基本过程?如何表示?它们的 call 方法如何工作?自定义过程的 call 方法又是如何表示和工作的?这些就是本文需要解决的问题了。

Read the rest of this page »

Write a Scheme Interpreter in Ruby(1): Parser & Analyser

Saturday, December 15th, 2007

leaf.gif也算是突然心血来潮吧,就想写一个 Scheme 的解释器,其实也是心血来潮了许多次了,只是一直都只是一个想法,最主要的原因还是因为自己对编译原理一无所知吧,也许明年上过编译原理课之后就好写了。不过这次真是心血来潮了,拦都拦不住,怕是等不到明年了。

不管写得出来写不出来,也都先试试吧!多次见石老师演示过 boost::spirit ,计算理论课上也学过了上下文无关文法,似乎还是知道个大概。于是我就开始找 Ruby 的 parser 库。

好像 parser 也有许多种,什么 Recursive Descent 之类的术语我也不懂,所以即使想去邮件列表里面问也不知道如何描述的好。找了半天似乎没有发现一个像 boost::spirit 那种级别的 parser 库,不过找到了 Peter Cooper 写的一个 Recursive Descent parser 实现(只有 255 行代码)。便下载下来,准备开工了!

Read the rest of this page »

Multiton

Friday, December 14th, 2007

Multiton 类似于 Singleton ,目的是要保证某种单一性。但是和 Singleton 的一个区别就是:Singleton 对于一个类只可能有一个对象,而 Multiton 则可能有多个对象,仅当用于构造的参数相同时,才保证唯一性。有许多地方都有这种模式的应用,例如 Lisp 或者 Ruby 里的 symbol ,同名的 symbol interned symbol 总是同一个对象。还有 Java 里的 String 也是这样的。

最近心血来潮在用 Ruby 做一个玩具级别的 Scheme 解释器,要表示 Scheme 里的 symbol 、number 和 string 的类,为了不过于浪费空间,决定把它们都做成 Multiton 这种模式。这里其实已经有了一个 Ruby 的 Multiton 实现,不过我决定自己实现一个简单一些的。

Read the rest of this page »

More on Continuation

Monday, December 10th, 2007

我在前一篇文章中用构造二叉树的 iterator 的例子来介绍了一下 Continuation 。Jack评论中向我提了两个问题:

  1. many people know about the CPS transformation, and callcc as a means to get hold of the implicit continuation (”the rest of the computation”), but we often have a hard time using continuations: there’s a large gap between understanding code which uses callcc and the ability to actually synthesize a solution to a problem using callcc. We lose easy-understanding in using callcc, what we get? If we get a lot, how?
  2. When should we adopt callcc and how can we express callcc idea using pencil and paper easily.

我发现我好像是自己沉醉在了 Continuation 的奇妙之中,却没有把事情说清楚。在这篇文章中我会回答他提出的这两个问题,并希望借此推广 Continuation 的思想。 :)

Read the rest of this page »

Continuation

Tuesday, December 4th, 2007

Continuation 是什么?简而言之,就是代码执行状态,利用它可以把当前的执行状态保存起来,以供以后调用。Scheme 应当是最早支持完整的 Continuation 的语言了,事实上从理论上来说,任何支持 Closure 的语言都能手工实现 Continuation ,不过许多语言还是提供了现成的 Continuation 的支持,例如 Ruby 就有一个类似于 Scheme 的 call/cc(call-with-current-continuation) 的函数 callcc (因为“/”在 Ruby 里面不能作为变量名,所以最多只能做到这么像了 ;) )用于支持 Continuation 。

说了半天,到底 Continuation 是个什么东西?它能用来干什么?事实上如果限制到词法作用域之内,goto 也可以算作一个简化版的 Continuation 。一个更高级一点的例子是 setjmp/longjmp 或者是大多数人更熟悉的“异常(Exception)”都可以算作“只出不进”的 Continuation 。而真正意义上的 Continuation 比它们都有趣得多。下面让我们通过一个例子来发现它的神秘之处。

Read the rest of this page »

memoize in Ruby

Tuesday, August 14th, 2007

Common Lisp 的经典书《On Lisp》的 5.3 节叫做 Memoizing 。书中讲到了将函数调用的返回值缓存起来的一种技术。这本来是一种非常常见的技术,但是《On Lisp》让我看到了动态语言的精练之处,这样的一种技术被抽象成一个通用的函数,将任意一个函数传入 memoize ,就会得到一个经过包装的函数,并且它已经具备了缓存的能力:

1
2
3
4
5
6
7
8
(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
  (multiple-value-bind (val win) (gethash args cache)
    (if win
        val
        (setf (gethash args cache)
        (apply fn args)))))))

下面是一个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
CL-USER> (setf (symbol-function 'memoized)
         (memoize #'(lambda (x)
          (sleep 5)
          x)))
#<closure (LAMBDA (&REST ARGS)) {B7B80F5}>
CL-USER> (time (memoized 1))
Evaluation took:
  5.0 seconds of real time
  0.004 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
1
CL-USER> (time (memoized 1))
Evaluation took:
  0.0 seconds of real time
  0.0 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
1
</closure>

Read the rest of this page »

Ruby 里的元编程

Sunday, August 12th, 2007

关于元编程

Wikipedia 上关于元编程的定义说元编程就是将程序作为数据进行处理。“用程序来处理程序”,这就是“元”的来源了,这本身是一个容易产生混淆的地方,就像“用语言来描述语言”一样,数学上的许多悖论就来自于此呢。幸好我们用的编程语言比自然语言要简单许多,并且都有严格的定义规范,有兴趣的人可以尝试在自己喜欢的编程语言里面构造一下 “This statement is false” 这个经典悖论。

回到元编程,程序处理程序可以分为“处理其他程序”和“处理自己”,对于前者,有我们熟悉的 lex 和 lacc 作为例子。而对于后者,如果再细分,可以分为“宏扩展”、“源代码生成”以及“运行时动态修改”等几种。

宏扩展从最简单的 C 语言的宏到复杂的 Lisp 的宏系统,甚至 C++ 的“模板元编程”也可以包含在这一类里面,我在这里对它们进行了一些介绍。

源代码生成则主要是利用编程语言的 eval 功能,对生成出来的源代码(除了在 Lisp 这样的语言里面以外,通常是以字符串的方式)进行求值。有一类有趣的程序 quine ,它们运行的结果就是把自己的源代码原封不动地打印出来,通常要证明你精通某一门语言,为它写一个 quine 是绝佳的选择了,这里有我搜集的一些相关资料。

最后是运行时修改,像 Lisp 、Python 以及 Ruby 之类的语言允许在运行时直接修改程序自身的结构,而不用再经过“生成源代码”这一层。当然对源代码进行 eval 的方法也许是最灵活的,但是它的效率却不怎么样,所以相来说并不是特别流行。这里主要介绍的是这种方式的元编程在 Ruby 里面的应用,如果对元编程的其他方面感兴趣,前面的几个链接应该都是很好的去处。

Read the rest of this page »