Back from exams, and skime

July 4, 2008 – 2:40 am

stopwatch终于结束了一段痛苦的考试时间。考试确实非常痛苦,但是另一方面大学里的考试也是很重要吧,至少在计算机专业,普遍存在的现象就是很多课程大部分学到的知识其实是在考试前一周恶补出来的,至少如果整体现状不改变的话,应该是没有可能丢掉考试的吧。

考完试就是暑假了,仿佛一下子就空下来了。其实是非常不习惯吧,因为好多人都走了,有毕业的,有临时回家的。虽然我喜欢在校园里逛的时候只有稀稀落落的几个人的感觉,但是我不喜欢每天睁眼闭眼都是同样的电脑同样的只有我一个人。非常空也是假的,只是有太多的事情要做而不知道要做什么,或者根本是什么都不想做的一种感觉吧。太过浮躁,做什么事情总想着很快看到效果,结果却是很快就崩溃了。

另外,今天去班搓了,似乎是在紫金港的最后几天吧,虽然离毕业还有不少时间,但是也挺有种要毕业的感觉,毕竟是要搬家。不过我竟然去班搓了,我以为我是一定不会去的呢,看来我也还不够了解自己。回来之后很多人都说我喝醉了,因为我眼睛很红。当然我没有喝醉,因为我是不喝酒的。也许是因为我讨厌那些喝醉酒的人的样子吧。有人说酒后才是最真的,可是最真的并不一定是最好的,且不论人的本性是善是恶,人类区别于普通的动物很重要的一点正是因为人的理性吧。不过眼睛红也许是说我需要休息了,虽然考试期间我的睡眠一直都是很健康的(至少比平时健康得多),但是确实有些累了。不过今天我还想说一说 skime

skime 是一个 Python 写的 Scheme 实现。我以前曾经用 Ruby 写过一个 Scheme 的解释器: [1], [2], [3] ,并不难,但那终究只能是一个玩具。而且这次我想尝试一些我一直比较感兴趣但又没有机会尝试的东西——做一个 bytecode VM 。

是 Scheme 而不是其他更 modern 的语言;是 Python 而不是 Ruby ,其实都是和 Schemepy 相关的,因为 Schemepy 里需要的 pure-Python 的 Scheme 实现目前的两个候选:pyscheme 实现得很不完全,而且效率有些低;PyPy Scheme 似乎对 PyPy 的 Parser 有很深的依赖,不好移植。如果 skime 做得好的话,正好可以用到 Schemepy 中。

一个 Scheme VM 吧,执行 bytecode 的话,就相当于一个虚拟的 CPU 了,但是程序语言的指令集和普通 CPU 的指令集相比其实各自有各自的特点,包括执行环境以及目标等各个方面都是不同的,正好这个学期学习体系结构,了解到流水线以及 Cache 等优化 CPU 的技术,也觉得这些技术是不能照搬到 VM 的实现里来的。而且,虽然 register machine 最近越来越受到关注,为了简单起见,我还是先从 stack machine 做起。

然而也是抬起手却不知如何按键,我虽然一直比较感兴趣,但是对这方面的了解其实非常零散,而且也比较皮毛,根本不知道如何下手。纠结了很久,最后还是决定以 ad hoc 的方式,先用最 trivial 的方式实现一个可以工作的 prototype 吧。

于是我选择了一个最简单的计算阶乘的例子,用这样一段代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Foo
  def fact(n)
    res = 1
    while n != 0
      res *= n
      n -= 1
    end
 
    res
  end
end
 
puts Foo.instance_method(:fact).compiled_method.decode

来打印出了 Rubinius 实现的 bytecode :

0000:  check_argcount             1, 1
0003:  set_local_from_fp          :n, 0
0006:  meta_push_1
0007:  set_local                  :res
0009:  pop
0010:  meta_push_0
0011:  push_local                 :n
0013:  meta_send_op_equal
0014:  goto_if_true               35
0016:  push_local                 :n
0018:  push_local                 :res
0020:  send_stack                 #<sendSite:0x71 name=* hits=0 misses=0>, 1
0023:  set_local                  :res
0025:  pop
0026:  meta_push_1
0027:  push_local                 :n
0029:  meta_send_op_minus
0030:  set_local                  :n
0032:  pop
0033:  goto                       10
0035:  push_nil
0036:  pop
0037:  push_local                 :res
0039:  sret

这是我为自己的 VM 手工写的 bytecode :

["push_local", 0,
 "push_1",
 "equal",
 "goto_if_true", 21,
 "push_local", 1,
 "push_local", 0,
 "multiply",
 "set_local", 1,
 "push_1",
 "push_local", 0,
 "minus",
 "set_local", 0,
 "goto", 0,
 "push_local", 1]

逐步地实现这些 opcode ,现在总算是能把这个阶乘给计算出来了。这可以算是一个非常有效的方法了,现在大致的 VM 形状也差不多有了:Stack 、Context、Procedure、bytecode codec 等部件也都有了大致的框架,应该往下就不会像一开始那么抓狂了,还是万事开头难啊! :p 其实这种迭代式的开发方式也时常听到说起,真正体验一下才发现帮助怎么大!要不然我到现在肯定也还没有写出一行代码来。下一步希望让 Context switch 工作起来,支持一个递归版的阶乘试试。 :D

ps: 如果感兴趣的话,代码可以在这里找到。

Post a Comment