首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
宝塔
V2EX  ›  程序员

看 SICP 不如先看 The Little Schemer

  •  1
     
  •   ChristopherWu · 55 天前 · 1975 次点击
    这是一个创建于 55 天前的主题,其中的信息可能已经有所发展或是发生改变。

    来自 https://mp.weixin.qq.com/s/EYVCyQVoUNsWF6ltxXisYw

    好东西不怕分享对不对

    函数式入门圣经——王垠力荐《 The Little Schemer 》

    除了在知乎看到过一两次,首次正式得知《 The Little Schemer 》此书则是来自王垠的博客:

    Dan Friedman 是 Indiana 大学的教授,程序语言领域的创始人之一。他主要的著作《 The Little Schemer 》(前身叫《 The Little Lisper 》) 是程序语言界最具影响力的书籍之一。现在很多程序语言界的元老级人物,当年都是看这本 “小人书” 学会了 Lisp/Scheme,才决心进入这一领域。

    怼天怼地的王垠,在 GTF - Great Teacher Friedman 不遗余墨的表达了对 Dan Friedman 敬重与感激,文中满是对这位好老师的感激之情与知遇之恩。

    恰逢我又在重新看 SICP,对,就是那本看起来不厚,习题多得要命的那本 Structure and Interpretation of Computer Programs(计算机程序的构造和解释)。当然这本书的赞誉满如繁星:https://www.zhihu.com/question/26549715/answer/34336593

    过多的习题实在没有耐心,难以坚持,于是就先试试看《 The Little Schemer 》。

    我在寒假中已把《 The Little Schemer 》看完,收获良多,如今重温一下,顺便写本书评。

    相对于 SICP,我更推荐各位先看《 The Little Schemer 》打打基础,当这是一个 tutorial,其一问一答式的写作方法会令你耳目一新的-------讲的更加循循善诱,鞭辟入里,而且没什么习题 - -。你可以很快就了解到怎么样写 scheme,递归的威力,以及了解怎么样写一个 scheme 解释器,顺带了解了 丘奇计数,y 组合子等。

    我顺带在这里整理下这本书讨论了啥:

    玩具总动员

    引入 scheme 中基本元素atom(原子), list(列表), car(取列表的第一项),cdr(取列表除第一项的余下作为列表),cons(把 a 元素加到 b 列表中),null?(判断是否为空) , eq?(是否相等)。

    以上就是全部了,之后的所有东西就靠以上关键字实现,包括 sheme 解释器,y 组合子,删除列表第 x 项元素。

    处理,处理,反复处理。。。

    引入函数lambda以及or 关键词( if lese 作用),引入递归概念,实现函数lat?(判断列表里是否全为atom 原子),member ?(列表是否包含 xx )等为例子。

    用 cons 构筑恢宏

    通过实现 rember(删除列表某元素)引入 cons 构建 /拼接列表,实现 first(取列表第一项),实现 insertR(在列表的某项后插入一个元素),multiinsertR(在列表的某项后插入一个列表内所有元素——听到这个用递归做是否就有点不习惯了呢)。

    此章主要通过实现更多的函数,让读者更加熟悉递归实现函数的思维,以及如何写递归终止条件。

    数字游戏

    实现数字中的 +-*/等方法,就是自己来做数字的这些功能,可能这样说对没有接触过丘奇计数的人有点奇怪,我举一个我在阿里校招中出过的一道面试题为例子:

    以下 C 语言程序的输出是什么?

    #include <stdio.h>
    int lambda(a, b) {
        if(a == 0) {
            return b;
        }else {
            a = a - 1;
            b = b + 1;
            return lambda(a, b);
        }
    }
    
    int mull_r(a, b) {
        if(a == 0) {
            return 0;
        }else {
            a = a - 1;
            return lambda(b, mull_r(a, b)) ;
        }
    }
    
    int main()
    {
        int a = 88888;
        int b = 11111;
        printf("%d\n", lambda(a, b));
    
        int c = 300;
        int d = 400;
        printf("%d\n", mull_r(c, d));
        return 0;
    }
    

    A. 77777 120400

    B. 99999 120000

    C. 99998 120100

    D. 99999 119600

    答案是 B,以上 C 语言就是简单的实现了 + , - 功能(某种程度上)。

    同理还实现了=<以及>,无非就是 a,b 同时递归-1,看谁先为 0 之类。

    接着就是实现 len(列表长度),all-nums(提取列表中所有数字),one?(判断 n 是否为 1 )等。

    我的天!都是星星

    此章中重新实现以前实现过的函数的泛化版本(都在函数名后加一个*,所以说都是星星)。

    比如rember*(这次接受的第二个参数不是原子了,是列表,列表中出现过的都要删掉);insertR*(同理)等, eqlists(判断两个列表是否全等)。就是参数都为列表了,让递归来的更猛烈一些。

    如影随形

    引入算术表达式,如 1+33*4+12 等并写算术表达式解释器,算出结果。

    另外,值得一提的是又提了一遍丘奇数,如:

    4 代表概念上的四。因为人们更习惯阿拉巴表示法,所以我们选择了这个符号。

    但,(() () () ())也有同样效果,(I V)也可以。

    我们可以用() 代表 0,1 就是 ( () ),2 就是(()())

    那么加法就可以用 cons 做列表拼接 (cons (quote()) (quote()) ) 结果就是(())也就是 1。

    作者最后用了一个函数 lat 来说明在做高级抽象时应该注意不适用的陷阱(阴影),也就是本章标题的含义。

    朋友及关系

    写一个 set?函数(判断列表是否为 set 也就是没有重复出现的元素),makeset(从列表中构建一个 set),subset( b 是否 a 的子集),eqset?interset?等。

    示例了如何抽象出一个子过程(函数),来增强代码的表达能力。

    lambda 终结者

    在把函数当做数据类型,作为参数传入函数使用时,引入 Curry-ing (柯里化)的概念:

    (lambda (a)
        (lambda (x)
          (eq? x z))
    )
    

    如上,传入参数 apple 的时候,会返回函数

        (lambda (apple)
          (eq? apple z))
    

    如上就可以构造出一个函数,传给 rember函数(根据条件删除列表中元素)作为参数使用。

    接着用这个抽象更高一层的函数,因为年代久远,我有些忘了。。这里描述不了了。

    。。。。周而复始。。。

    这一章,作者从无到有的推导出在没有定义函数名字的时候,怎么样实现递归,也即是 Y conbinator ( Y 组合子)的来由,然而实在让人头大,我看了好多遍,也只是似是而非,不能鞭辟入里的讲解出来,所以我算是不懂的。

    值是什么

    有了递归,有了之前写过的数字表达式解释器,而 scheme 本来就很简单,于是这一章就可以总结之前学到的所有东西,写一个 scheme 解析器了。


    以上就是《 The Little Schemer 》的内容,对于一个刚入门学计算机的,没有接触过函数式编程的,我是极力推荐的。

    努力学完理解完,一周时间勉强可以解决了,之后两章可能需要花比较长的时间去理解——难度暴涨。。。需要自己去多看看其他书了。

    其实理解完除了最后两章的内容,上手 SICP 就非常简单了,只不过习题还需多加努力。

    14 回复  |  直到 2019-09-27 14:21:46 +08:00
        1
    lalalakakaka   55 天前
    大概三年前~我也在 WY 安利下看了《 the little schemer 》,正准备磨刀霍霍向《 SICP 》,就听说《 the little schemer 》出第二本了。后来就再也没看《 SICP 》了。
        2
    lalalakakaka   55 天前
    我操,是六年前的事了,时间过得真快
        3
    mimzy   55 天前
    看了下豆瓣…原来我 2014 年就想读了 结果到现在还没看…🤣
        4
    yijuechen   55 天前
    我是从 CS61A 开始,没看 SICP,总感觉 scheme 以后也用不上,王垠大魔那种高度也到不了
        5
    secondwtq   55 天前   ♥ 2
    The Little 其实是一个系列,用不上 Scheme 也可以看看别的:
    The Little LISPer
    The Little MLer
    The Little Schemer
    The Seasoned Schemer
    The Reasoned Schemer
    A Little Java, A Few Patterns
    The Little Typer
    The Little Prover
        6
    mikukonai   55 天前
    这本书的讲述方式很“怪”,有人说像是《论语》。无所谓好坏,只能说是萝卜白菜各有所爱吧。
    后续作品也值得一读。
    分享一点笔记,主要是摘抄代码: https://mikukonai.com/article.html?id=The-Little-Schemer-%E9%98%85%E8%AF%BB%E7%AC%94%E8%AE%B0
        7
    agagega   55 天前 via iPhone
    楼上总结得精辟😂确实像论语一样,不太能读下去。这本书好像出中文版了
        8
    azuki   55 天前 via Android   ♥ 1
    可是,sicp 的目的不是为了学 lisp/scheme 啊?
    不是讲大型系统如何用抽象来控制复杂度么。
        9
    Mistwave   55 天前 via iPhone
    先看的 sicp 再看的 schemer 三剑客 三剑客第三本好难😵
        10
    ech0x   55 天前 via iPhone   ♥ 1
    SICP 又不是叫你 schemer 的书……SICP 是教你怎么抽象的书,你看 SICP 第二版都不用 schemer 了。
        11
    reself   55 天前 via Android
    SICP 又不是用来学具体语言的,不要总想搞事情。
        12
    zhuangzhuang1988   55 天前
    little 虽然不错
    但是知识密度太低了。
        13
    FrankHB   55 天前   ♥ 1
    这个系列的特色就是对话体,不需要你阅读的时候同时自己另外组织思路。
    好处主要是降低入门难度,只要读者能习惯。
    坏处是这种体裁根本没法 hold 住所有重要的主题(知识密度低算是个次要的副作用),放纵读者习惯到处都是 hint 的环境而欠缺自己观察的能力,无助于积累经验,思维不够自觉发散的会少看到很多东西(虽然这个比较吃天赋,还是能训练的)。一旦容易的东西都讲得差不多了,背景知识难度一上去,可能就会被隐藏的难度卡壳。
    Scheme 本身比较水,问题应该还不大。我见到过看 The Little Typer 然后没看出某个变换实质讲的是 beta reduction 但没明确指出来,结果读起来一下子觉得直接云里雾里了的读者。

    另外关于 Scheme,有几个特别的这里提到的这些书都不会提的点:
    如果要知道实际在用的东西是什么,应该看 RnRS (反正也不长)。看个大概再回来对比 INTRODUCTION,然后会发现一些设计意义上根本的矛盾。
    可以再试着去理解 R6RS 的反复,编译和解释阵营的分裂之类的“社会问题”。因为其它语言的学习过程中基本都会欠缺这样的例子,这种经验可能比熟悉怎么用具体的语言更重要。

    如果要搞 PL 想测试自己天赋的:
    你应该能总结出就 Scheme 的 lambda the ultimate... 的 flavor 本身,实际还是有很多水的地方,比如 undelimited continuation 为什么无论如何都不实用;不管是 lambda 还是 Scheme 暴露的 first-class continuation,实际上显然不够 ultimate ……
    你还能应该隐约认识到至少传统 LISP 表面上看起来简明的设计(如 quote 和过度依赖 alist )在语用上有一些无法避免的不自然的问题,这不是用户的错。
    (具体文献的位置就不列了,省得影响学习效果。)

    @yijuechen 跟用不用得上语言没多少关系。
    @ech0x 虽然目的是这样没错,但真这样想你就上当了。

    为什么都 9102 了还要强调用 Scheme 的 SICP ?
    关键是用其它语言讲的入门读物相比起来实在比它屎得太多了,包括不用 Scheme 的 SICP (这个例子也说明作者的知识背景的影响可能没多数人想象中的那么大)。
    #%E6%96%87%E7%8C%AE%E7%9B%B8%E5%85%B3
        14
    ChristopherWu   55 天前
    @FrankHB 我居然没多少看懂的。。。。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4353 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 32ms · UTC 06:27 · PVG 14:27 · LAX 22:27 · JFK 01:27
    ♥ Do have faith in what you're doing.