SICP读书笔记--第1章《构造过程抽象》

一、说明

读完了SICP的第四章,也完成了大部分的习题。是时候来写一点总结和分享一下自己的心得了,这篇博文主要的目的就是写一下对第1章《构造过程抽象》的总结,并且展示自己不成熟的解题代码,同各位爱好者进行交流,希望大家指出其中的不足!

  • 第1章共有3小节内容,分别是:

    • 1.1程序设计的基本元素

    • 1.2过程与它们所产生的计算

    • 1.3用高阶函数做函数

二、总结

1.程序设计的基本元素

  • 最一开始,作者就为我们指出了每一种强有力的语言应该提供的三种机制

    • 基本表达形式:语言里最简单的个体。

    • 组合的方法:允许我们从简单的东西出发构造出复杂的元素。

    • 抽象的方法:允许我们为复合对象命名,并将它们当做单元去操作。
  • 接下来就是本书的又一个重要的概念—-环境,它同时也是一种简单而又强有力的抽象方式

    • define就是上面所说的抽象方法:允许我们用一个名字去引用一个组合运算的结果。

      有了这个方法我们就可以用一个简单的名字去代替复杂的对象和程序,方便我们以后用它们创造更复杂的东西。

    • 为了完成上面的功能,解释器维护了一种存储能力,它保持了有关的名字-值对偶的轨迹。这种存储就被称为环境(更精确地说是全局环境)。

    在我看来define就是一种受限的抽象手段,因为它强制了一种关联,其实就是lambda的一个语法糖衣而已。

  • 接下来就是利用define去完成过程的定义

    1
    (define (<name> <formal parameters>) <body>)

    <name>是一个符号,后面将作为这个过程在环境里的名字,<formal parameters>是一个形参列表,<body>叫过程体,由一系列的表达式(组合式)组成。

  • 对于组合式的求值,解释器将按照下面的过程工作

    • 求值组合式的各个子表达式。
    • 将作为最左子表达式(运算符)的值的那个过程应用于相应的实参,即子表达式的值。

    对于求值子表达式,有下面的规定

    • 数的值就是它们表示的值。

    • 内部运算符的值就是对应的机器指令序列。

    • 其他名字的值就是环境中这个名字关联的对象。

    仔细想想上面的几个小点,将发现这一求值过程是递归的,如果还不清楚的话,请想想(* (+ 2 (* 4 6)) (+ 3 5 7))的求值过程。

  • 过程应用的过程与上面的类似:

    在将过程体中的每个形参用相应的实参取代之后,对这一过程体求值。

    这种计算过程称为过程应用的代换模型,我们需要注意下面的几点

    • 代换模型只给出了求值器求值过程的简单、一般的形式化描述
    • 代换模型只是为了帮助直观理解过程应用的行为。
    • 代换模型不足以解释复杂的求值过程,这在引入的赋值和局部状态之后更加明显。
  • 对于第4点中,求值子表达式把过程应用于得到的实参这两个的先后问题引出了下面的应用序正则序的概念

    • 正则序完全展开而后规约

    • 应用序先求值参数而后应用

    大部分解释器会采用应用序,但是正则序在后面引入惰性求值之后将发挥出巨大的威力。

  • 再回到之前的过程定义,我们将考虑下面的几个概念

    • 形式参数与具体名字的名字无关,它只在过程定义的局部作用域里有效,被称为约束变量

    • 在过程定义的内部可以定义这个过程需要用到的一些子过程,同样满足于局部作用域的限制,这样的嵌套定义称为块结构

2.过程与它们所产生的计算

一个过程就是一种模式,它描述了一个计算过程的局部演化方式。

  • 递归

    1
    2
    3
    4
    (define (fac n)
    (if (= n 1)
    1
    (* n (fac (- n 1)))))

    我们来看一下上面定义的过程的计算过程

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    (fac 5)
    (* 5 (fac 4))
    (* 5 (* 4 (fac 3)))
    (* 5 (* 4 (* 3 (fac 2))))
    (* 5 (* 4 (* 3 (* 2 (fac 1)))))
    (* 5 (* 4 (* 3 (* 2 1))))
    (* 5 (* 4 (* 3 2)))
    (* 5 (* 4 6))
    (* 5 24)
    120

    代换模型为我们揭示了一种先逐步展开而后收缩的形状,展开阶段构造起一个推迟进行的操作形成的链条,收缩阶段表现为运算的实际执行,这样的计算过程称为递归计算过程。这种过程的特点就是用链条去保存中间计算的一些信息,以便收缩时可以回到正确的原点。

  • 迭代

    1
    2
    3
    4
    5
    6
    7
    8
    (define (fac n)
    (define (iter product counter max-count)
    (if (> counter max-count)
    product
    (iter (* counter product)
    (+ counter 1)
    max-count)))
    (iter 1 1 n))

    我们来看一下上面定义的过程的计算过程

    1
    2
    3
    4
    5
    6
    7
    8
    (fac 5)
    (iter 1 1 5)
    (iter 1 2 5)
    (iter 2 3 5)
    (iter 6 4 5)
    (iter 24 5 5)
    (iter 120 6 5)
    120

    我们看到这样的过程是用变量productcountermax-count去保存轨迹,称这样的计算为迭代计算过程。它有下面的特点:

    • 其状态可以用固定数目的状态变量描述。

    • 存在一套固定的规则,描述了计算过程从一个状态到下一状态时变量的更新方式。

    • 存在一个结束检测,描述了计算过程的终止条件

    在迭代计算的任何时间点,状态变量都提供了计算状态的一个完整描述,意味着我们可以轻易地在计算停止之后通过向解释器提供状态变量的值来唤醒它。

3.用高阶函数做抽象

程序语言的必然要求:能为公共的模式命名,建立抽象,而后直接在抽象的层次上工作。

在Scheme中允许我们以过程作为参数,或者以过程作为返回值描述上面的模式,这类能操作过程的过程被称为高阶过程

  • 过程作为参数

    如上面所说的我们可以把一个公共模式提取出来,只考虑它的一般情况,而不是考虑一些具体的表达,建立一般的抽象。在这里我们的参数可能不再只是简单的变量,而可能是一些一般化的过程。

    • 回忆一下求和公式:

      看看这个公式的代码吧

      1
      2
      3
      4
      5
      (define (sum f a next b)
      (if (> a b)
      0
      (+ (f a)
      (sum f (next a) next b))))

      这里的f就是公式里的$f$,只是一个一般化的形式描述,没有具体的定义,next描述的是变量怎么从一个状态到另一个状态,也没有具体的定义。

    可以看到将过程作为参数成功地帮助我们从一些具体的描述里解脱出来,开始可以用一个抽象描述一个更一般化的抽象

  • 用lambda构造过程

    有时候我们没有必要将过程和一个名字绑定起来,那我们就可以使用lambda去定义这个过程,它不需要我们为过程提供名字

    1
    (lambda (<formal-parameters>) <body>)
  • 用let创建局部变量

    一般形式:

    1
    2
    3
    4
    5
    6
    (let ((<var1> <exp1>)
    (<var2> <exp2>)
    :
    :
    (<varn> <expn>))
    <body>)

    它表示令分别具有值,然后带入

    中求值。

  • 过程作为返回值

    有时因为形参和过程的特殊性,最后得到的可能不是具体的值,而是一个中间的过程。

    比如

    1
    2
    (define (average-damp f)
    (lambda (x) (average x (f x))))

    average-damp的形参是一个过程f,返回的是求x(f x)平均值的过程。

  • 抽象和第一级过程

    高阶过程的重要性,在于使我们能显式地用程序设计语言的要素去描述这些抽象,使我们能像操作其他计算元素一样操作它们。

    带有最少限制的元素称为具有第一级的状态,第一级元素具有的“特权”有:

    • 可以用变量命名
    • 可以提供给过程作为参数
    • 可以由过程作为结果返回
    • 可以包含在数据结构中

    最后一点我们会在第2章时领略到,对于Scheme来说,它给了过程完全的第一级状态

    三.我的解题代码

------------- 本文结束 感谢您的阅读 -------------

本文标题:SICP读书笔记--第1章《构造过程抽象》

文章作者:Perry

发布时间:2019年03月18日 - 00:50

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/1cdb23d5.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%