huaxiazhihuo

 

scheme下的停机问题和Y组合子

        看过的计算机书中,scheme相关的那几本,好比SICP,the essence of program都很让我爱不释手。而the little schemer更加独特,编程的本质,在这本书小人书上体现得淋漓尽致。窃以为,scheme是语法形式上最为完美的编程语言了,没有之一。少即是多,这样的赞美之言,唯有scheme当之无愧,并且它的确是精简得不能再精简了。至于那个自吹自擂的什么狗语言,不提也罢。当然,完美并不一定代表实用,也并不一定必须流行,曲高一向都是和寡的,但是,完美却一定可以带来赏心悦目般的感受。
        the little schemer全书行云流水,逐渐显露递归的威力,做足了铺垫,到了第8章,真命天子lambda出现,一切变得很有意思了,读完之后,意犹未尽。第9章,难度陡增,突然变得理论性起来,那是自然的。因为,这一章的主题是停机问题和Y组合算子。不引入任何形式化的方法,但是作者举重若轻,依然阐释得如此直白易懂,可以说,只要能看完前面的内容,就一定能看懂这一章。而前八章,据说6岁以上的儿童都能看得明白。
        scheme中的函数是first class,可以作为参数传递给其他函数,也可以作为值从函数中返回。比如,广为流传的一道程序,用以考察语言的表达能力,“编写一个函数,其入参数为n,返回值为新的函数,该函数的参数为x,返回值为之前的n与现在的x的和。”用scheme来表达,牛刀小试。
(define (addn n)
  (lambda (x)
    (+ x n)))
然后,对于((addn 20) 30),scheme解释器上显示其结果为50,很好。相比于那个lisp的版本,这里显得多么的干净。
        函数式的语言对副作用(side effect)很敏感,特别是haskell,更加对副作用赶尽杀绝,压根就不让写出有副作用的函数。因此,正常情况下,函数执行完毕,都有返回值。好比,……,总之很多就是,正常的函数,都可称之为total functions,意思就是对所有的参数,都会有返回结果。但是,也还存在一些病态函数,它们不会返回,一旦调用它,那么将陷入与其中,永远都不会返回了,显然,里面出现死循环了,但是,scheme中没有循环语句,所以不能这么说,总之,这一类是不会有返回值的。很轻易就能写出一个例子。
(define eternity
  (lambda (x)
    (eternity x)))
eternity为不朽的意思。
        自然就有这样的问题,能否实现这样的函数,它能判断函数是否终将返回,或者说,判断函数会不会停止。这个函数作用可大了,当然不会那么容易实现。不过,可以先假设它存在,就叫它will-stop?(别惊讶,scheme中,标识符中可以有+-*等特殊符号)。因此,对于任何函数,(will-stop? afunction)表达式的值,要么为#t,表示函数afunction终将停止返回;要么为#f,则函数不会停止,好比eternity。显然,让will-stop?判断自己,(will-stop? will-stop?)的结果一定是#t了。
        但是,will-stop?是不可能存在的,这不是废话吗,地球人都知道。因为计算机学家精心构造了一个反例,此反例实在巧妙,真难以想象当初是如何构造出来,我等小民只需理解即可。请看代码
(define (last-try x)
  (and (will-stop? last-try) (eternity x)))
last-try,好名字,就叫它最后一击吧。(will-stop? last-try)的结果不外乎#t或#f。
        假如为#f,说明last-try不会返回,意味着有死循环,不会停止。但是,一考察last-try的内部实现,却很容易就知道它马上就返回了。表达式(and (will-stop? last-try) (eternity '()))中,由假设可知(will-stop? last-try)为#f,进而马上可知,(and (will-stop? last-try) (eternity '()))马上必将返回#f,也就是说,虽然一开始假设last-try不会停止,但实际运行中last-try一下子就返回了,矛盾。
        看样子,(will-stop? last-try)只好为#t了。可是,(and (will-stop? last-try) (eternity '())),and表达式的两个分支中,既然(will-stop? last-try)为#t,那么,势必要进一步调用(eternity '()),而eternity老爷,一早就知道他乃不朽之身了,因此,last-try也沾光,一样不朽了。与假设中(will-stop? last-try)为#t为终将停止,又是矛盾。
        因此,will-stop?接受不了last-try的挑战,失败。也就是说,will-stop?这样的函数,不存在。这道反例的高明之处,或者说耍赖吧,就是以will-stop?为基础构造了一个will-stop?无法判断的函数。假如规定,所有被检测函数都不得直接间接的调用will-stop?,免得will-stop?难堪,那么这样的will-stop?能否存在呢?存不存在,我就不知道了,但享受此待遇的Y组合子却是存在的。
        函数直接或间接调用到它自己,递归就产生了。问题来了,函数你自己都还没实现完毕,怎么就可以自己拿来调用呢?这个过程中,编译器解释器肯定做了某些语义上处理,让递归得以实现。逻辑学中,对于下定义的要求是“不得循环”,好比,白色就是一种白色的颜色,这种废话定义就不符合下定义的基本要求了。
        下面来将一条经典的递归函数整成非递归的版本。the little schemer的推导思路非常浅显易懂,我不能做的更好的了,因此借用。
(define length
  (lambda (l)
    (cond ((null? l) 0)
      (else (+ 1 (length (cdr l)))))))
函数length中,虽然调用到了自己,实际上,其实只是调用了一个同样名字的函数而已。意味着,length的实际上的lambda表达式,背地里带多了一个参数,此参数为函数,用以当入参l不为空时来进行使用。因此,可以将整个函数的定义改写成下面的lambda表达式。
(lambda (length)
  (lambda (l)
    (cond ((null? l) 0)
      (else (+ 1 (length (cdr l)))))))
lambda表达式的返回值为一个函数,当然没有名字了。它的入参为一函数,返回一个新的函数,此新函数的入参是列表,返回列表的长度。为了便于后文叙述引用,就用define给它起个名字,叫mk-length。什么,连用define起名字都不会,没救了。
        mk-length不是需要函数入参吗?刚好手头有一个,就用它自己本身,((mk-length mk-length) '()),解释器返回0,太好了。然后,我满怀希望的用((mk-length mk-length) '(a))来测试,结果,解释器报错了,为什么?稍微一想,就明白了。(mk-length mk-length)的确返回计算列表长度的函数,但是,当列表不为空时,只好用表达式(+ 1 (length (cdr l)))做进一步处理,里面的length就是mk-length,而mk-length的入参是函数,不是列表,于是解释器就报错了。怎么办?
        当然,要计算长度为不大于1的列表的长度,还是有办法的。就是,((mk-length (mk-length mk-length)) '(a)),这样就好了。自然,当列表大于1时,解释器必然又将报错了。按照此法,为此,为了求得不大于N个元素的列表长度,必须将mk-length写N次,好比,
((mk-length
  (mk-length
   (mk-length (...))))
 '(a b c d ...))
并且,辛辛苦苦的重复写N遍mk-length,只能计算个数不大于N的列表的长度。这,无论如何都不能让程序猿接受。
那么,为何要写那么多(mk-length (mk-length (mk-length...))),皆因mk-length中(+ 1 (length (cdr l)))的length函数接收的函数参数是列表l。先暂时让它适应环境,就让它知道它接收的length参数是一个跟它自己本身的lambda表达一样,是入参为函数,然后返回一个计算list长度的函数。将mk-length改写成这样。
(define mk-length
  (lambda (length)
    (lambda (l)
      (cond ((null? l) 0)
        (else (+ 1 ((length length) (cdr l))))))))
请注意,代码里面已经不存在递归形式了,因为,mk-length的lambda表达式中,没有用到mk-length这个名字了,当然,它还要用到入参length以计算当l不为空时的长度。再次抱着试试看的态度,验证,((mk-length mk-length) '(a)),返回1,真的可以了。拿更长的列表丢进去,长度为2,为3,为N+1,都OK了,真是神奇。
        它的工作原理是,故事一开始,(mk-length mk-length)生成一个计算列表长度的函数,在其内部中,假如列表l为空,就返回长度为0;否则,就计算l的尾部长度,并加上头结点的长度1,而计算l的尾部的函数,是通过(length length)来生成,其中length就是mk-length,故事就回到原点(mk-length mk-length)了,只是,其返回值在外围中要加1了,然后,在更外围中继续加1,加1,……。
但是,工作还没有完成,因为,mk-length中,((length length) (cdr l))很刺眼,它应该是(length (cdr l))这样的形式。重构,必须重构。必须在将其提炼成一个函数,因此,mk-length就变成
(define mk-length
  (lambda (length-mk)
    ((lambda (length)
    (lambda (l)
      (cond ((null? l) 0)
        (else (+ 1 (length (cdr l)))))))
     (lambda (x)
       ((length-mk length-mk) x)))))
代码似乎变得复杂些了,但效果是一样,并且,语法结构上基本保持一致。但是代码好像的确变得更长了,这也没办发,为了保持最内部length的纯洁性。但是,它也太深了,作为重点,应该放在外面,嗯,应该将两个lambda对调一下。
(define mk-length
  (lambda (length-mk)
    ((lambda (length)
       (length (lambda (x)
         ((length-mk length-mk) x))))
     (lambda (length)
       (lambda (l)
     (cond ((null? l) 0)
           (else (+ 1 (length (cdr l))))))))))
面对着这么多的lambda,实在难以淡定。但必须接收洗礼,方可体会到函数作为一等公民,所带来的强悍的表达能力,简直能撞破习惯命令式编程的眼球。里面的lambda(length)又变回原来的样子,但是,mk-length的主体已经不再是它了,而是一个以的lambda(length)为参数的lambda了。为了保持mk-length的纯洁,继续努力,这一次,是在两个(mk-length mk-length)上做文章,每次都要写两个相同的函数,不如把它做成函数。事情到了这一步,Y组合子已呼之欲出。
(define Y
  (lambda (f)
    (f f)))
((Y mk-length) '(a b c d e))    ;返回5
然后将mk-length中的第一条length的lambda搬过来,并且作为两个f的入参
(define Y
  (lambda (length)
    ((lambda (f)
       (f f))
     (lambda (length-mk)
       (length (lambda (x)
         ((length-mk length-mk) x)))))))
最后,将Y整得更加好看一点,也看来更加的通用,不仅仅是针对length,而是全部的需要递归的函数。
(define (Y f)
  ((lambda (g) (g g))
   (lambda (g)
     (f
      (lambda (x) ((g g) x))))))
再送上一道求和
((Y
  (lambda (sum)
    (lambda (n)
      (cond ((= n 1) 1)
        (else (+ n (sum (- n 1))))))))
 10)
文章已经很长了,打住。以后再发挥吧。

posted on 2013-07-11 14:48 华夏之火 阅读(2767) 评论(2)  编辑 收藏 引用 所属分类: 编程语言杂谈

评论

# re: scheme下的停机问题和Y组合子 2013-07-13 18:47 Quon

Y Combinator的好文要看这篇:http://mvanier.livejournal.com/2897.html
写的很清晰  回复  更多评论   

# re: scheme下的停机问题和Y组合子[未登录] 2013-11-08 16:22 Aaron

博主文采相当不错相当有见地!!!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜