Archive for the ‘Lambda’ Category

The Implementation of Scheme Hygienic macro

Saturday, July 26th, 2008

我在很早的时候曾经写过一篇叫做“Play with macro”的文章,介绍了 Common Lisp 式的 macro ,那是一个很基本但又很强大的工具,比较容易理解。相比之下,Scheme 的 macro 就不一样了,虽然我很早就知道 Scheme 的 macro 是一种叫做 Hygienic macro 的东西,但是直到最近才明白它是怎么一回事,因为我要实现这样一个系统。

Common Lisp 的 macro 其实就是一段 Common Lisp 代码——一段操控代码的代码。因为在 Lisp 里程序的结构本身就是以一种类似于语法树的形式存在的,很好处理,所以宏的存在和广泛应用也理所当然了,而在 C/C++ 甚至于 Ruby、Python 这种语法复杂的语言里做这样的事情就很麻烦。C 提供了一个基于文本替换的宏,能完成不少事情。相比之下,Scheme 的那种基于模式匹配的宏反而更像 C 语言的预处理宏一些。然而 hygienic 并不是表示模式匹配的意思,而是指“保证宏展开的时候不与现有的符号冲突”,只是碰巧 Scheme 采用了模式匹配的方式罢了。

Read the rest of this page »

Multiton again, in Python

Sunday, May 18th, 2008

I have introduced Multiton in one of my previous blog post. Multiton is just like Singleton, except that there will be multiple instance when the init parameters are different. One example is the Lisp symbol:

  • Different symbol object for different symbol name.
  • Identical symbol object for identical symbol name.

The last time I was implementing a Multiton is when I wrote my Scheme interpreter in Ruby. It is fairly easy in Ruby, I wrote a Multiton module, just include that module, your class becomes a Multiton.

But now (when doing Schemepy) I have to do the same thing again in Python. In Ruby the relationship between instance and its class, class and its class (class’s class) is identical. However, there are metaclass in Python, I’m some what confusing about that currently. I know both __init__ and __new__ is not enough for such a task. But I don’t know how to deal with metaclass.

Read the rest of this page »

Inside the {C++, Java, Lisp, Python, Ruby} Object Model

Sunday, May 18th, 2008

We just held a technical salon today named "template<language L> Inside the L Object Model". When I was looking at some code of Ruby, I found the object model is very different to a static language like C++. So I suggested the idea of discussing various object model of different languages. Finally, our amazing MSTC staffs made it happen in the form of a salon.

We finally selected 5 languages and invited 5 people to talk about their object model:

  • C++: shifan, the board manager of C++ board of freecity BBS. An interesting person, know C++ very well, commonly known as "模教教主". :)
  • Java: gbb, the board manager of Programming Technique board of cc98 forum. A very enthusiastic person. WARNING: he might become extremely exciting when discussing about any technical topic. :p
  • Lisp: binghe, the board manager of Computer Language board of freecity BBS. THE Lisp hacker of our school. He always think Lisp (especially Common Lisp) is the ultimate super cool and powerful language ever exists. :)
  • Python: Mike, the board manager of Linux board of cc98 forum. Still a freshman but already has a very good knowledge of Linux, Open Source and programming. Bright future! :)
  • Ruby: me. I’m also board manager of cc98 forum and freecity BBS. :p I’m interested in various languages.

We gave about 20 minutes to each speaker to introduce the object model. The remained time is for discussing. The salon is held in the office of MSTC. We have many people there.

DSC_0730

Read the rest of this page »

Trampolined-style Programming

Thursday, May 15th, 2008

今天在 pyscheme 的代码里看到许多诸如 pogo.pogopogo.landpogo.bounce 之类的调用,感觉特别奇怪,不过它的注释写得很详细,做这样的东西是为了解决 Python 没有尾递归优化的问题。

在有尾递归优化的语言里(Scheme 是最典型的一个例子,因为它甚至把尾递归作为语言的一个重要特性放在语言规范中了),如果一个函数的最后一个动作(除了 return)是调用另一个函数的话,就直接用那个函数的栈帧替换当前的栈帧,省去了 call and return 的麻烦,还避免了栈溢出,时间空间都有优势。

作为一个最简单的例子,下面是“正常”的求阶乘和尾递归版本的阶乘:

Read the rest of this page »

A Better method_missing

Thursday, February 28th, 2008

method_missing 是 Ruby 用于实现其动态性的一个重要成员。简而言之就是在调用一个对象的某个方法的时候发现这个方法不存在,于是会触发 method_missing ,进而做一些事情,比如转发这个方法,甚至根据需要定义那个方法让下次调用的时候不会产生 method_missing ,另外这也是制作 DSL 的一个重要工具。

下面是一个简单的 DSL 的例子:

Read the rest of this page »

We read Knuth so you don’t have to

Wednesday, February 20th, 2008

来自 Python Cookbook (第 5 章:Searching and Sorting)的 Quote :

We read Knuth so you don’t have to.

所以在 Python 中,如果要排序,尽量使用内置的 sort 方法;如果要做搜索,尽量使用内置的 dictionary 工具,因为它们集中了 Knuth 先生的经典砖头里面的近 800 页的关于排序和搜索的详细讨论。当然,在 Ruby 中肯定也是差不多的。 ;)

混乱过的 C 语言 Hello World 程序

Wednesday, February 20th, 2008

相信不少人都听说过国际 C 语言混乱大赛吧?里面有不少看起来千奇百怪的代码,但却都是完整的 C 程序并且不少是非常有用并且高效的程序。今天我在这里又看到几个混乱过的 Hello World 程序,例如:

#define _________ }
#define ________ putchar
#define _______ main
#define _(a) ________(a);
#define ______ _______(){
#define __ ______ _(0x48)_(0x65)_(0x6C)_(0x6C)
#define ___ _(0x6F)_(0x2C)_(0x20)_(0x77)_(0x6F)
#define ____ _(0x72)_(0x6C)_(0x64)_(0x21)
#define _____ __ ___ ____ _________
#include<stdio .h>
_____
</stdio>

如果我不说,你能看出来它是一个打印 Hello World 的程序吗?还有这个(据说只能用 C++ 编译器编译)看起来是不是有点 Brainfuck 语言的味道?

Read the rest of this page »

Coroutines and Semi-Coroutines

Tuesday, February 19th, 2008

Ruby 1.9 中引入了 Fiber 用于支持 Coroutine 。事实上 Fiber 并不是一个 Coroutine ,而是 Semi-Coroutine ,或者叫做 Asymmetric Coroutine 。因为它只能将执行权返回给调用者,而完整的 Coroutine 可以自由转移运行权。 Ruby 1.9 也提供了 Fiber::Core 用于支持“正宗”的 Coroutine 。关于 Semi-Coroutine 和 Coroutine 的等价性似乎有些争论。下面是一个 Fiber 的例子:

fib = Fiber.new do
  x, y = 0, 1
  loop do
    Fiber.yield y
    x,y = y,x+y
  end
end
20.times { puts fib.resume }

Read the rest of this page »

A 3rd-order Quine: Haskell -> Python -> Ruby

Wednesday, February 6th, 2008

我曾经在我的 Wiki 笔记 中介绍过 Quine ,就是能打印自身的程序。今天在这里看到一个很厉害的 Quine :

q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']
main=q "q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']" "def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'" "def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end"

这是一个 Haskell 程序,运行它会输出一个 Python 程序,再运行这个 Python 程序会输出一个 Ruby 程序,再运行这个 Ruby 程序会得到一个 Haskell 程序,对了!就和最开始那个 Haskell 程序一模一样的! :D

RubyConf 2007 video 释出!

Wednesday, December 26th, 2007

rubyconf-logo2

RubyConf 2007 演讲的全部视频最近由 Confreaks 公司公布(Creative Commons Attribution-ShareAlike license)出来,可以在这里在线观看或者下载 AVI 格式(H.264)的视频。

这么多牛人的怎么多精彩的演讲,真是令人激动啊!我把他们下载下来了,这样离线的时候也可以看。我还把他们传到了 88 CompLang 版的 FTP 上,校内的朋友们可以直接去那里下载。 :)

我虽然还没有来得及看所有的演讲,但是随便看了几个都是非常有趣的(当然,也是非常精彩的),我这里随便介绍一两个,相信你一定也会喜欢的!

Hurting Code for Fun and Profit

Ryan Davis 带来的精彩演讲,他的 slides 很多都是手绘的,从下图可以看到:

hurt_code

演讲的开始他先讲了一个故事,这是一个关于 Legacy Code 的故事,一个程序员到了一家公司,开始处理一堆 Legacy Code ,找出他们的依赖关系,最后是一团糟,于是程序员生气了,干掉了创造这些 Legacy Code 的人(如上图),然后自己进了监狱。这个结局不好,另一个方法是什么呢?

Read the rest of this page »