Scheme

在scheme中实现product函数

published on

在tspl3书上见到的一个习题,简单写一下,就是实现一个product函数,给出一个list,求出它们的乘积。有一个要求是,如果list中有元素0,则不进行乘法。

实现,首先定义下我们用的乘法,统计被调用的次数

(define cnt 0)
(define my-* 
  (lambda (x y) (set! cnt (+ cnt 1)) (* x  y)))

然后思路很简单,我们先检查list有没有0,如果有则直接返回0,否则返回不需要考虑0product,实现如下:

(define (product-1 ls)
  (letrec ((product/without-check 
            (lambda (ls)
              (if (null? ls) 
                  1
                  (my-* (car ls) (product/without-check (cdr ls)))))))
    (if (memq 0 ls)
        0
       (product/without-check ls))))

测试的代码:

(display (product-1 '(1 2 3 4 5))) (newline) ;=> 120
(display cnt) (newline) ;=> 5
(display (product-1 '(7 3 8 0 1 9 5))) (newline) ; => 0
(display cnt) (newline) ;=> 5 (保持不变)

当然这个代码还有另外一种写法,就是使用cps的形式,我们传两个回调,一个代表继续执行,一个用来break迭代过程:

(define (product-2 ls)
  (letrec ((product& (lambda (ls k break)
                       (cond
                         ((null? ls) (k 1))
                         ((= (car ls) 0) (break 0))
                         (else (product& (cdr ls)
                                         (lambda (v)
                                            (k (my-* (car ls) v))) 
                                         break)))))
            (id (lambda (x) x)))
    (product& ls id id)))

同样测试的代码:

(display (product-2 '(1 2 3 4 5))) (newline) ;=> 120
(display cnt) (newline) ;=> 5
(display (product-2 '(7 3 8 0 1 9 5))) (newline) ; => 0
(display cnt) (newline) ;=> 5 (保持不变)

这样就少了一轮迭代过程。

Read More...

书籍推荐 《Programming Languages: Application and Interpretation》

published on

正好赶上劳动节要放假了,在网上转悠的时候发现这本书。用来讲述编程语言特性的一门课程。这本书可以在线阅读,用plai作为关键词google一下就可以找到。

按照一般的作风,这里应该放一张封面的靓照,我就省去了。

今天简单的看了一下,非常喜欢,很快看到了第15章。书中的代码都是用的scheme实现的,不过为了教学目的,对scheme做了扩展,形成了专门为这个教学使用的语言。如果没有scheme经验的同学可以先看看《SICP》打打底。

书中的主要内容就是介绍语言的各种特性。方法就是通过编写具有这各种特性的语言的解释器。了解多种语言的特性可以帮助你理解在各种语言中,那些设计为什么要做成那样,哪些地方是好的设计,哪些地方实际上应该可以更合理。

说明: 后面关于书的内容的介绍是基于07版的,其网站上有2007版和 2012版两个版本的下载,而我是拿着07版在看,预计看完之后快速过一下新版的修改的内容完事了。

最开始,先是做了一些基本的介绍,说我们研究的不是具体的语法,而是语义。也就是区分不同语言的关键不在于看起来写成什么样,而是其具体有什么作用。所以用lisp有一个巨大的方便之处就在于不用在语法这件事情上纠结了,可以方便的得到ast,然后在上面做工作。

第二部分先实现了一个具有基本功能的语言,包括基本的计算和函数调用。同时会介绍static scopedynamic scope的区别。

第三部分讲惰性求值,举了两个例子,其一是Haskell,这个是很标准的惰性求值的语言。不多说,另一个是unix的管道的设计。管道的作用是将一个程序的输出作为另一个程序的输入。而输出会造成阻塞,只有另一个程序将这写输入了之后,前一个程序才会继续运算,所以这个设计就和惰性求值有着一样的特性:可以处理无限。例子比如命令 yes | head -n 5 就会输出5个y,而仅仅是yes的话,就会产生无穷的y,可以你要多少给多少。比如用在yes | rm * 这样的命令中就会很方便。

这里面提到unix的一个设计的哲学就是为10个元素提供10种工具,不如为1种元素提供100种工具,然后将这些工具组合起来就得到非常强大的力量。在unix中这个东西就是stream,但是最后这个东西有个缺陷,就是不便于表达结构化的数据,一切都为了内容是可读的。

这里其实隐含这再说lisp才是最牛逼的,这里什么都是用s表达式表示的,有大量操作s表达式的操作,所有的运算的输入和输出都是s表达式。多么美好啊。当然如果看前缀的算术表达式能习惯的话,是挺不错的。

这里扯多了,第四部分讲递归是怎么实现的。为了构造循环的Env,使用了初次使用了box功能。也就是说引入了非pure functional的部分,对已有的值进行了修改,否则很难想象怎么构造一个环:1.A引用B,2.而B引用A,1要求在你构造A的时候B已经构造好了,而2相反,所以只能先构造一个再改了。

第五部分简单的讲了一下我们不一定要用原生的类型来表示新语言中的值,比如你用C写一个解释器,解释的语言的整数在C中也可能是个string或者和struct什么的。在scheme里面我们甚至可以完全就靠闭包来当作数据结构使用,模拟各种值的行为(当然性能就很微妙了)

这只是一个简单的过场

第六部分开始为我们要解释的语言加入了副作用。显示加入了box和unbox这样的功能,类似C里面的指针,虽然没有赋值,指针不能变,但是我们可以改变指针指向的东西了。

之后要允许变量直接赋值了,修改变量的值相当于取出变量对应的地址,然后改对应地址的值。

出现变量赋值后,就又提出了一个问题,函数调用的时候就产生了两种方式传值和传引用。

整体来看这里已经涉及了比较丰富的概念了内容了。

后面的内容我还没有看,只是简单的过一下目录,下面概括一下,有机会以后再展开讨论。

第七部分讲延续(Continuations),通过web程序的特点引入的。然后提到了CPS转化,再引入延续,最后将怎么实现。不了解的同学或者听说过协程(Coroutines),其和延续关系非常大,具体不多转述。CPS的话可以参看一些node.js的资料应该会有个大致的印象。

第八部分讨论内存管理的思路,比较像C那样显式malloc free和函数式语言那样自动分配的区别。

第九部分专门讨论语义,具体看后再说。

第十部分类型系统,最后会涉及自动类型推导,目测会比较有意思。

第十一部分搜索,实现一个prolog那样工作的语言

第十二部分DSL和metaprogramming,元编程,让人疯狂的宏

Read More...

Y-combinator的推导

published on

今天花费了巨大的努力,自己推导了一遍Y-combinator。发现结果蛮简单的,就是中间遇到了几个障碍消耗了很久,作此文记录一下。

下文代码均使用scheme,不过对其要求不高,本来我对scheme知道的也不多。

引入:什么是Y-combinator

这里直接讲这玩意做什么的吧,历史上是怎么产生的我就没追溯了。

一句话来描述就是,我们可以通过这个玩意编写匿名递归函数。

先看例子吧,举个简单的递归函数:计算阶乘(好像大家都喜欢用这个例子)

(define fact
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (fact (- n 1))))))

注意如果我们要将其写成一个匿名函数,那么我们不可能在函数里面使用fact,那么通过加一个self参数可以解决这个问题。

(define fact
  (lambda (self)
    (lambda (n)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

这样调用的时候写成: ((fact fact) 6),可惜这样写是错的…., 因为上面最后一行需要写成 (* n ((self self) (- n 1)))))))

这样就编写出来了可以匿名递归的函数,但是有一个麻烦的地方是你程序里面要写成(self self),别人调用的时候也要写两遍函数名,这样就还有改进的空间。下面开始改进,我们用F表示这个函数,我们自己希望写成(不包括define F的部分):

(define F
  (lambda (self)
    (lambda (n)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

然后有一个运算符Y,只要执行(Y F),就得到了我们想要的内容。比如

(define fact (Y F))
(fact 6) ;=> this return 720

那么主要的工作就是这个Y长什么样了

Y的推导

注意到由于F的新写法,我们必须把正确的函数传进去,而不是传F自身,而正确的函数就是我们想要的(Y F),我们从这里开始。

(define Y
  (lambda (F)
    (F (Y F))))

这里的Y出现了递归,我们利用上文已经实现过的匿名递归技术来解决这个难题(写起来麻烦没关系,只要这次麻烦过了,呵呵~),将这个东西的名字叫做self-Y好了,于是代码演化成下面这样:

(define Y
  (let ((self-Y (lambda (self)
                  (lambda (F)
                    (F ((self self) F))))))
    (self-Y self-Y)))

哦,我们居然把Y写出来了,可惜这里面还有一点小问题,仔细看一下你会发现这简直就直接死循环了啊… 问题在于这个问题是个递归的,而你想把它展开却没有边界条件…… 这就变成无限循环了。

于是有意思的地方来了,我们可以借用Lazy计算的思路,等到我要用到这个函数了,我再做这个运算,于是变成:

(define Y
  (let ((self-Y (lambda (self)
                 (lambda (F)
                   (lambda (n)
                     ((F ((self self) F)) n))))))
    (self-Y self-Y)))

这样只有当我们给出了F的参数之后,相应的展开工作才会进行,我们的fact函数可以完美运作了。

至此,我们就成功的推导出来了Y的实现。可喜可贺,可喜可贺。当然,对于我来说,只支持一个参数的F函数当然不够满意,利用scheme的语法特性,我们可以改成下面这样。

(define Y
  (let ((self-Y (lambda (self)
                  (lambda (F)
                    (lambda n
                      (apply (F ((self self) F)) n))))))
        (self-Y self-Y)))

使用的例子

最后给一个使用匿名的递归函数的例子, 下面的语句计算了1到7的阶乘:

(map (Y (lambda (self)
          (lambda (n)
            (if (equal? n 0)
                1
                (* n (self (- n 1)))))))
     '(1 2 3 4 5 6 7))
Read More...