llscheme – 3 – interpreter

qhe 同学为 llscheme 加 了一个 interpreter 接口，安装好之后 `llscheme -i’ 即可进入解释器。然而在开发过程中间碰到了一个有趣的问题：我们有个lsrt_error()，调用它会导致进程结束。这对于编译出来的代码是没问题的， 然而对于解释器，大家可能希望它打印错误信息后能继续工作。

解决该问题的办法是在lsrt_error()调用exit(-1)之前插入一个钩子函数，并且该钩子函数式个弱符号(weak symbol)，我们只在调用解释器的时候定义该钩子函数：

extern "C" void lsrt_exit_hook() { throw Error(""); }

函数lsrt_exit_hook()假模假式的抛了个异常，避免了对exit(-1)的调用，而解释器只要捕获改异常，然后继续REPL即可。完整补丁：

git diff 1a6bd0..6749de

llscheme - 2 - profiling

本文谈谈怎样对llscheme生成出来的代码进行性能剖析。假设有个示例程序fib.scm，它会算出第一千个斐波那契数。我想到两种方法：

1. 利用传统的gprof工具链
   
   • CFLAGS='-lpg' ./autogen.sh --prefix=/usr (保证运行时库是以'-lpg'编译的)
   • sudo make install
   • llscheme -S -o fib.ll <>
   • llc fib.ll (得到 fib.s 本地CPU汇编代码)
   • gcc -pg fib.s -o fib -llsrt -lgc -lgmp
     这样运行./fib确实会得到gmon.out，但接下来跑 gprof 却得不到任何剖析数据。具体原因有待分析。
     
2. 利用LLVM自己的profiler - llvm-prof，它需要一个LLVM bitcode文件作为输入。为此，我们得先把llscheme的运行时库打包成LLVM字节码，而不是用autotools那一套生成出来的共享库liblsrt.so。
   
   • cd llscheme/src/runtime
   • clang -emit-llvm -c *.c -I./include -I../include
   • llvm-ar rcs liblsrt.bca *.o
   • llvm-as fib.ll
   • llvm-ld fib.bc liblsrt.bca -lgmp -lgc -o fib (这一步会生成可执行文件fib，以及对应的字节码文件fib.bc - 会把老的覆盖掉)
   • perl profile.pl fib.bc -load /usr/lib/libgmp.so -load /usr/lib/libgc.so 这样就能输出详细的剖析数据。

profile.pl 来自 LLVM 的 subversion 仓库，不过这个脚本有点问题。我有一个小补丁：
--- profile.pl.old 2007-09-12 01:09:54.000000000 +0800
+++ profile.pl 2010-07-07 13:13:55.282462603 +0800
@@ -65,10 +65,10 @@
my $libdir = `llvm-config --libdir`;
chomp $libdir;

-my $LibProfPath = $libdir . "/profile_rt.so";
+my $LibProfPath = $libdir . "/libprofile_rt.so";

system "opt -q -f $ProfilePass $BytecodeFile -o $BytecodeFile.inst";
system "lli -fake-argv0 '$BytecodeFile' -load $LibProfPath " .
- "$BytecodeFile.inst $ProgramOpts " . (join ' ', @ARGV);
+ (join ' ', @ARGV) . " $BytecodeFile.inst $ProgramOpts";
system "rm $BytecodeFile.inst";
system "llvm-prof $LLVMProfOpts $BytecodeFile $ProfileFile";

llscheme - 1 - intro

5月12号在github上创建了 llscheme 项目，目标是写一个 Scheme 编译器， 输出为 LLVM 汇编。到今天为止，Python 实现已经支持四则运算，算是前进了第一小步。由于我和 qhe 同学对 LLVM 的 C++ API 都不熟悉，所以 C++ 实现的进度稍微落后一点。

我的下一步计划是支持 `define’ ，以及 lambda 表达式，这样基本上可以编译一些简单的数学应用了，而且暂时还不需要考虑GC。

感谢一下 qhe 同学的帮忙，统计了一下 git blame 的结果，你贡献了 45% 的代码。有一个朋友互相交流是一件幸事，使我免于三分钟热度，免于在遇到困难的时候打退堂鼓。

Guile Scheme Macro Bug?

syntax-rules是R5RS Scheme中规定的标准hygienic macro system，不过Guile Scheme中的实现似乎有点问题。

(define-syntax dotimes
  (syntax-rules ()
    ((_ n body ...)
     (let loop ((counter n))
       (if (> counter 0)
           (begin
             body ...
             (loop (- counter 1))))))))

上面定义了一个宏dotimes。理论上说，作为hyginic macro，外部环境对于宏里面的内部符号应该没有任何影响：

> (let ((loop 2)) (dotimes 4 (display loop)))
2222
> (let ((n 2)) (dotimes 4 (display n)))
2222
> (let ((counter 2)) (dotimes 4 (display counter)))
2222
> (let ((- 'minus)) (dotimes 4 (display -)))
minusminusminusminus

MIT-scheme, Gambit以及PLT中都是上面的行为，唯独Guile过不了最后一关：

guile> (let ((- 'minus)) (dotimes 4 (display -)))
minus<unnamed port>: In expression (- syntmp-counter-21 1):
<unnamed port>: Wrong type to apply: minus

明显的是，宏内部变量名都已被转换，比如counter变成了syntmp-counter-21，但'-'还是引用了外部let环境下的'-'。这该是个bug。

Sierpinski Triangle

下面的图形被称为"Sierpinski Triangle"：


生成它的代码很简单，比如用guile (需要guile-cairo)：

(use-modules (cairo))

(define (polygon cr p1 p2 p3)
  (let ((x1 (car p1))
        (y1 (cdr p1))
        (x2 (car p2))
        (y2 (cdr p2))
        (x3 (car p3))
        (y3 (cdr p3)))
    (cairo-move-to cr x1 y1)
    (cairo-line-to cr x2 y2)
    (cairo-line-to cr x3 y3)
    (cairo-line-to cr x1 y1)))

(define (fill-tri cr x y size)
  (polygon cr (cons x y)
           (cons (+ x size) y)
           (cons x (- y size))))

(define min-size 8.0)

(define (sierpinski-tri cr x y size)
  (if (<= size min-size)
      (fill-tri cr x y size)
      (let ((new-size (/ size 2)))
        (sierpinski-tri cr x y new-size)
        (sierpinski-tri cr x (- y new-size) new-size)
        (sierpinski-tri cr (+ x new-size) y new-size))))

(define surf (cairo-svg-surface-create 300 300 "foo.svg"))
(define ctx (cairo-create surf))

(cairo-set-source-rgba ctx 1 0.2 0.2 0.6)
(cairo-set-line-width ctx 2.0)

(sierpinski-tri ctx 25 275 255)

(cairo-stroke ctx)
(cairo-surface-finish surf)

如上，结果会保存在文件foo.svg中。

A Tale of Two Cats

每学一门语言首先想做的是用它写一个类UNIX下cat命令的东西，简单但至少涉及命令行处理和文件I/O。

Scheme版本：

(define (cat . arg)
  (let ((port (if (null? arg)
                  (current-input-port)
                  (car arg))))
    (let loop ((c (read-char port)))
      (if (not (eof-object? c))
          (begin
            (display c)
            (loop (read-char port)))))))

(define (main args)
  (if (null? (cdr args))
      (cat)
      (for-each (lambda (port) (cat port) (close-input-port port))
                (map open-input-file (cdr args)))))

Haskell版本：

import System.Environment

cat :: String -> IO ()
cat fn = do
  contents <- readFile fn
  putStr contents

main = do args <- getArgs
          if null args then interact id else mapM_ cat args

学了Haskell之后才知道Python里面的缩进、List Comprehension等似乎是从Haskell学来的。上面两个cat功能一样，区别是Haskell cat比较懒一点，那是因为Haskell是惰性求值的。勤快一点的版本只需要bytestring重新实现cat函数：

import qualified Data.ByteString.Lazy as B

cat :: String -> IO ()
cat fn = do
  bs <- B.readFile fn
  B.putStr bs

cset-100

今天向自己的hg仓库检入了第一百个changeset，初步完成了自己的第一个代码生成工具。回头在看看这五百行Scheme代码，我确信自己很不喜欢它们 -- 直白但流于杂乱。

这几天读cgia才豁然发现，在聪明的程序员手中，很多枯燥的工作都能以优美的方式解决。问题是，很多时候，自己缺乏那种视角，所谓``不识庐山真面目，只缘身在此山中''。

如果让我重写，我可能会用ERB来解决之。Template System的好处是数据和逻辑分离，而我现在的Scheme代码中直接hard-code了目标代码。

非确定性计算

1961年，Lisp语言的发明者John McCarthy提出了非确定性程序设计的思想。设想一下，如果我们有一个算子称为amb(iguous)，它的行为如下：

1. 有参数的时候不确定地返回其中一个参数；
2. 没有参数的时候对它的求值则将导致失败；
3. 如果其子表达式有一个可达，则表达式必须有返回值。

所以：

1. 求值(amb 1 2) 将返回1或者2；
2. 求值(amb)将导致失败；
3. 求值(amb 1 (amb))必然返回1。

这里有对amb的解释、示例和一个在scheme语言中的简单实现。有了amb后，我们可以思考下面一个简单的数学问题：如果 2 <= x, y, z <=9，有哪些x, y, z可以使得x的平方是y和z的平方和？

(define (require p)
(if (not p) (amb)))

(define in-range
(lambda (a b)
  (require (< a b))
  (amb a (in-range (+ a 1) b))))

(let ((x (in-range 2 9))
    (y (in-range 2 9))
    (z (in-range 2 9)))
(require (= (* x x)
            (+ (* y y) (* z z))))
(list x y z))

对上面的表达是求值，将会得到（5 3 4)，再求值(amb)将得到(5 4 3) ，再次求值则会得到错误报告：(error "amb tree exhausted")。这两组数正是我们需要的结果。

Wish list

离过生日还有八个多月，不过我却想好了我的wish list, 那就是我垂涎已久却始终没有找到电子版的两本经典书籍：

1. The Little Schemer - 4th Edition
2. The Seasoned Schemer

Amazon上两本书加起来是49.5美刀。

Metalinguistic Abstraction

本文的标题其实是SICP第四章的标题，这一章的内容是迷人的，让人心醉。我们可以看到如何用Scheme实现一个Scheme解释器，如何实现惰性求值，如何在解释器内部实现非确定性计算，以及如何实现一个查询语言。收获知识的喜悦，突然想起陶潜的一句诗：“此中有真意，欲辩已忘言。”

这里有一些有趣的程序，类似SICP第五章，将Scheme代码翻译成C代码，甚至llvm汇编。

Q1的MBO也终于设定，我的英语IDP目标是技术写作 -- 内容为Lisp和Ruby中的DSL特性。

Scheme笔记 -- 6

Lisp之特殊之处在于过程和数据之间其实没有什么区别，过程可以作为数据，数据也可以作为数据。当然这归功于该语言中过程实际上是一等公民，这再其它动态语言如Python, Ruby中也很常见。但Lisp的数据和过程都可以用List来表示，这种惊人的统一性在看似古怪的表面之下有着及其迷人的魅力。

Scheme只有一个很小的内核，除了最基本的求值规则之外几乎没有任何强加的规则。语言的设计者意识到，任何一门语言都不可能实现所有程序员都希望的特性，于是他们为程序员提供了扩展该语言的手段 -- 程序员可以自定义语法，最大程度的重用解释器内核。

Lisp在诞生50年之后仍然在不断进化，并形成一个大家族。这也足以证明该语言强大的生命力。学Lisp后会对以下概念有更深入的理解：
1. 过程、数据
2. closure，tail call, FP
3. macro

Lisp macro是其魅力的主要源泉之一，它提供了强大的抽象表达方式，并很容易用来书写Code Generator等等。至于Scheme中特有的continuation，可以用来实现任意的流程控制。或许太过强大，但绝对是Scheme语言里一颗璀璨的明珠。

Scheme笔记 -- 5

偶尔看到一篇文章，The Swine Before PERL[pdf|ppt]，来自MIT的lightweight language workshop，相当精彩，读了数遍仍然意犹未尽。其中有一段代码，放在Chez Scheme, MzScheme，UCB STk，MIT-Scheme以及Guile 1.6下都能跑，唯独Guile 1.8总是报错，让我开始怀疑这是否是它的bug，结果却出乎意料：只有Guile 1.8才是做了该做的事 -- 从源代码eval.c的997到1003行可以看出端倪。

这里是各种Scheme解释器中运行的结果：
;; STk interpreter version 4.0.1-ucb1.3.6
(case 'x (x 1) (else 0)) ;; 1
(case 'x ((x) 1) (else 0)) ;; 1
(case 'x ('x 1) (else 0)) ;; 1
(case 'x ('x 1) ('y 2) (else 0)) ;; 1

;; MzScheme v4.0
(case 'x (x 1) (else 0)) ;; bad syntax
(case 'x ((x) 1) (else 0)) ;; 1
(case 'x ('x 1) (else 0)) ;; 1
(case 'x ('x 1) ('y 2) (else 0)) ;; 1

;; MIT-Scheme 7.7.90.+
(case 'x (x 1) (else 0)) ;; Ill-formed clause
(case 'x ((x) 1) (else 0)) ;; 1
(case 'x ('x 1) (else 0)) ;; 1
(case 'x ('x 1) ('y 2) (else 0)) ;; 1

;; Guile 1.6.7
(case 'x (x 1) (else 0)) ;; bad or missing clauses
(case 'x ((x) 1) (else 0)) ;; 1
(case 'x ('x 1) (else 0)) ;; 1
(case 'x ('x 1) ('y 2) (else 0)) ;; 1

;; Guile 1.8.3
(case 'x (x 1) (else 0)) ;; bad or missing clauses
(case 'x ((x) 1) (else 0)) ;; 1
(case 'x ('x 1) (else 0)) ;; 1
(case 'x ('x 1) ('y 2) (else 0)) ;; Duplicate case label

因为Scheme中'x等价于(quote x)，于是最后一个语句等价于：
(case (quote x)
((quote x) 1) ;; A
((quote y) 2) ;; B
(else 0))
显然分支A和B中含有相同标号quote，这就是错误的根源。改成：

(case 'x ((x) 1) ((y) 2) (else 0))

就行了。

早晨搜到一个难兄难弟：链接。

Scheme笔记 - 4

这一个礼拜以来写了近千行Scheme代码，其中包含一个Scheme解释器，以及对L-99中部分题目的解答。第一次，我写出了自己的求解排列、组合问题的程序，以前的源代码其实都是网上淘来。明天开始继续在SICP的指导之下改进解释器。

有点犯困，没有半点写代码的热情。想起下午和头儿one/on/one时丢给我的一句话：你的写作水平很好，但要多练习口语，随时准备和老美交流。汗，我差点以为随时要把我丢米国去。不过，实话说，我练就的确确实实是哑巴英语。

上周末用png2html处理了一张照片，也放在了Hg仓库。还有一句话，放在磁盘占用一个文件不大划算，贴这里吧：``Misunderstandings are not the user's but the designer's fault.''

Scheme笔记 -- 3

趁着最近比较闲，写完了关于符号处理，这里是编译出来的pdf文档：
http://live4thee.googlepages.com/scheme-intro.pdf.gz

另外，在sharesource的Hg仓库里保存着最新的LaTeX源文件：
http://hg.sharesource.org/sysnotes/

下一章介绍约束传播系统。以电路系统为例，因为方程V = IR始终成立，于是一条线路上，当电压、电阻和电流中有两者确定时，第三个元素的值便也随之确定。

虽然在数学中，只要一个方程便能描述。但在编程语言中往往不得不写三个过程，知道两个元素后求解第三个元素。因为传统上计算机程序总是被组织成一种单向的计算，对于给定参数给出所需要的结果。

约束传播系统通过组合各种基本约束，构造出约束网络，动态生成各种元素的状态。

PLT Scheme 4.0 Released!

PLT-Scheme的4.0版本终于发布了！首页也焕然一新，官方主页下载之：
http://plt-scheme.org/

PLT Scheme是个极具现代化的Scheme编程环境。主页上有一个介绍视频的链接还有一篇有趣的简介，实在不能错过。其实这俩份资料之前在reddit上已经释出，但是需要新版的plt-scheme才能演示。

另外，plt-sheme也被用在livecoding中，比如fluxus，有兴趣的伙子们不妨一试。

scheme笔记 - 2

Scheme笔记中又添加了一节，关于continuation。

Continuation是scheme语言中进行流程控制的一个强大机制。区区几行，或者几十行代码就可以实现其它语言中的跳转，异常，生成器等。同样给出了一些参考读物以帮助理解。

下一节讨论符号处理。Lisp之所以广泛用于人工智能，和其强大的符号处理能力是分不开的。

Sheme笔记 - 1

这段时间稍微有点忙，没有太多时间继续写Scheme笔记，目前已经完成四部分内容：

1. Scheme简介
2. 求值器模型
3. 递归和尾递归
4. 高阶函数

人说RERO，于是放至主页，共勉。

continuation

直到今天才弄懂continuation大概是啥意思。C程序员可以将其理解为setjmp/longjmp，但前者更强大且灵活。

Scheme(当然也包括其它Lisp变体)的迷人之处在于它不限制程序员思想的自由，它并未在业界风靡却存活了近半个世纪。C也快40岁了，它灵活、直观，并给予程序员充分的自由和信任，其成功之处在于它提供了一层恰到好处的抽象。

Guile是个GNU的Scheme解释器，它提供了一个library用于C和Scheme的交互，不错的想法。

Y-combinator的推导

这两天稍微有空了一点。正开小差的时候，xuan哥踱步进来，说好久没来关心俺了， 视察了一番丢下一句“没事休息休息，有空补补文档。”两眼泪汪汪啊！于是一气呵成，翻译了一篇文章，关于Y-combinator的推导过程。

--[节选]--
本文试图推导Y-combinator，递归函数理论的基本硕果之一。或许你已经知道，某些情况下给函数绑定一个名字并非必要之举，例如：

((lambda (x) (+ x 1)) 6)

对6进行增一操作，但并未给进行该操作的函数命名。对于递归函数，情况又是如何呢？例如：

(define fact
 (lambda (n)
  (if (zero? n)
    1
    (* n (fact (- n 1))))))

函数fact计算数值n的阶乘，并且看起来它需要一个名字`fact'，这样在最后一行可以递归调用自身。然而我们将会发现这不是必需的。

--[全文]--
http://live4thee.googlepages.com/ycomb.pdf.gz

Y-combinator

;; Scheme 版的 Y-combinator
(define (Y f)
 ((lambda (g) (lambda (h) ((f (g g)) h)))
  (lambda (g) (lambda (h) ((f (g g)) h)))))

;; 6 的阶乘
((Y (lambda (fn) (lambda (x)
      (if (zero? x) 1 (* x (fn (1- x ))))))) 6)