1.1 程序设计的基本元素

作者: 勤劳的悄悄 | 来源:发表于2016-07-13 14:58 被阅读57次

1.1 程序设计的基本元素
200915.《Python语言程序设计》-1.1-程序设计基本
计算机程序的构造与解释（过程抽象）
SICP 第1章 1.2节笔记
HTML快速恢复之 HTML基础
Python 基础学习笔记
第1章 python基本语法元素
《JavaScript 高级程序设计》学习笔记
HTML+CSS 学习笔记 02
Java基础知识梳理

1.1.1 表达式

数

数是一种最基本的表达式

> 486
486

过程

过程（内置运算符或函数）是另一种基本表达式，例如：

组合式

过程和数可以组合成组合式
组合式中的第一个元素（最左边）总是过程：

(+ 137 349)

嵌套表达式

如果组合式的元素也是组合式，他就是嵌套表达式

(+ (* 3 5) (- 10 6))

代码格式

书写代码的时候要注意换行和缩排

(+  (* 3
    (+  (* 2 4)
        (+ 3 5)))
    (+ (- 10 7)
    6))

1.1.2 命名和环境

命名

命名将一个名字和一个对象关联起来，命名是一种最基本的抽象

;将名字 size 和数字 2 关联起来
> (define size 2)

> size
2

> (* 5 size)
10

环境

名字保存在环境中，不同环境中的名字互不干扰

1.1.3 组合式求值

求值过程

对组合式求值是一个递归过程

先求值各个子表达式
将求出的值作为参数应用到过程
如果子表达式也是组合式，重复这一流程

如下表达式

(* (+ 2 (* 4 6))
    (+ 3 5 7))

可用下图中的树表示，递归特别适合处理像树这样的层次性结构

表达式也可以用树表示

环境和求值的关系

内置运算符也是一种名字，和普通名字没太大区别，只不过他们是存在于全局环境中，并且已经关联到对应的指令序列上而已

环境为求值提供了上下文，没有环境，求值就没有意义

特殊形式 `define`

define 是一种特殊的形式，和一般的求值规则有所不同

1.1.4 复合过程

定义复合过程

所谓的复合过程就是创建自定义的新过程

> (define (square x) (* x x))

上面的 define 创建了一个过程对象，并将这个对象和名字 square 相关联

使用复合过程

我们可以像使用内置过程一样使用复合过程：

> (square 21)
441

> (square (+ 2 5))
49

> (square (square 3))
81

用复合过程定义复合过程

对解释器来说，复合过程和内置过程完全一样，因此可以用复合过程继续定义新的复合过程

> (define (sum-of-squares x y)
    (+ (square x) (square y)))
    
> (sum-of-squares 3 4)
25

继续复合

> (define (f a)
    (sum-of-squares (+ a 1) (* a 2)))
    
> (f 5)
136

1.1.5 过程求值的代换模型

过程求值有两种代换模型：

应用序
正则序

下面让我们分析一下组合式 (f 5) 求值的代换过程

应用序代换

总是先求值参数
全部参数求值为基本表达式（即数值）后，开始求值过程名
如果参数是一个组合式，则对其求值过程同样遵循应用序代换

应用序代换过程

正则序代换

总是现求值过程名
过程名求值为基本过程（即内置运算符）后，开始求值参数。
如果参数是一个组合式，则对其求值过程同样遵循正则序代换

正则序代换过程

1.1.6 条件表达式和谓词

到目前为止，我们能够自定义的复合过程表达能力还非常有限，我们需要条件表达式

条件表达式


(cond   (p1 e1)
        (p2 e2)
        ......
        (pn en)
        (else e))

条件表达式也是一种特殊形式，因为他不会对全部参数求值。只要检测到了为真的条件，他就会返回条件对应的表达式，之后的参数不会再检测

谓词

谓词就是返回真或者假的过程，常见的谓词有：

if 语句

if 语句只有一个判断条件，为真返回表达式 1，为假返回表达式 2

逻辑运算

(and e1 e2 ...... en)，检测到一个为假，则返回假；否则返回最后一个表达式的值
(or e1 e2 ...... en) 返回第一个检测到的为真的表达式的值，如果全部为假则返回假
(not e)

注意：and 和 or 是特殊形式，因为他们没有对所有的参数进行求值

练习 1.1

按顺序求值下面的表达式

> 10
10


> (+ 5 3 4)
12


> (- 9 1)
8


> (/ 6 2)
3


> (+ (* 2 4) (- 4 6))
6


> (define a 3)


> (define b (+ a 1))


> (+ a b (* a b))
19


> (= a b)
#f


> (if (and (> b a) (< b (* a b)))
      b
      a)
4


> (cond ((= a 4) 6)
        ((= b 4) (+ 6 7 a))
        (else 25))
16


> (+ 2 (if (> b a) b a))
6


> (* (cond ((> a b) a)
           ((< a b) b)
           (else -1))
     (+ a 1))
16

练习 1.2

将下面的数学公式转化成前缀表达式

> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
 (* 3 (- 6 2) (- 2 7)))
 
-37/150

练习 1.3

定义一个过程，他有三个参数，返回其中较大的两个数的平方和


;;;求两个数的平方和
(define (sum-of-squares x y)
  (+ (* x x) (* y y)))


;;;计算三个数中两个较大的数的平方和
(define (bigger-sum-of-squares x y z)
  (cond ((and (< x y) (< x z)) (sum-of-squares y z))
        ((and (< y x) (< y z)) (sum-of-squares x z))
        (else (sum-of-squares x y))))
        
        
        
>  (bigger-sum-of-squares 6 3 4)
52


> (bigger-sum-of-squares 1 2 3)
13


> (bigger-sum-of-squares 3 7 5)
74

sumOfSquares x y = x*x + y*y

biggerSumOfSquares  x y z
  | (x > y) && (y > z) = sumOfSquares x y
  | (x > y) && (z > y) = sumOfSquares x z
  | otherwise          = sumOfSquares y z

练习 1.4

描述下面这个自定义过程的求值步骤

;;;过程定义
(define (a-plus-abs-b a b)
    ((if (> b 0) + -) a b))

下面是求值步骤：

 ;;;调用
(a-plus-abs-b 10 99)
109



;;;参数已经是基本表达式了，求值过程名得到
((if (> 99 0) + -) 10 99)
109


 ;;;参数已经是基本表达式了,求值过程表达式得到
(+ 10 99)
109

练习 1.5

下面的过程可以判断出你的解释器是正则序还是应用序，解释其中的原理


;;;定义 1
(define (p) (p))

;;;定义 2
(define (test x y)
  (if (= x 0)
      0
      y))

解释如下：

;;;求值表达式 (test 0 (p))



;;;对于应用序 -----------------------------
> ;;;首先求值参数，得到
(test 0 (p))
;;;接下来会不断的求值 (p)，导致死循环



;;;对于正则序 -----------------------------
> ;;;首先求值过程名，得到
(if (= 0 0)
    0
    (p))
0

;;;if 语句：因为条件满足，所以只求值第一个表达式，返回 0；表达式 (p) 不会被求值

1.1.7 实例：采用牛顿法求平方根

到目前为止，我们学习的内容已经可以完成一些简单的工作，比如下面求平方根的程序：

核心算法是不断迭代改进猜测值，直到足够好
将算法中一些小的计算分离出来，作为辅助函数
没有其他语言中的循环语句，但是仍然完成了迭代

#lang racket

;;;开方
(define (sqrt x)
  (sqrt-iter 1.0 x))


;;;开方算法：
;;;1. 如果猜测值足够好，则返回猜测值；
;;;2. 否则改进猜测值，然后迭代该过程
;;;参数：猜测值和开方数
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))


;;;判断足够好的算法
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))


;;;改进猜测值的算法
(define (improve guess x)
  (average guess (/ x guess)))


;;;下面是辅助函数-------------------------

;;;求平均数
(define (average x y)
  (/ (+ x y) 2))


;;;求平方
(define (square x)
  (* x x))

习题 1.6

下面是一个模仿 if 的自定义过程，但是他会导致死循环，为什么？

;; 6-new-if.scm
(define   (new-if predicate then-clause else-clause)
    (cond  (predicate then-clause) 
                (else else-clause)))

解答：

因为内置的 if 是一种特殊形式，特殊形式有自己的求值规则，if 的求值规则如下：

只有条件为假，if 才会求值第二个表达式，导致递归调用
如果条件为真，if 会求值第一个表达式，整个过程可以退出

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess ;;;条件为真时会从这里退出
      (sqrt-iter (improve guess x) x)))

而自定义的 new-if 是一个函数，因此

按照函数求值规则，无论条件是真是假，他都会先对所有参数求值。而第二个表达式在这里仅仅是函数的一个参数
求值第二个表达式会导致递归调用，又会再次求值 new-if，导致死循环

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
      guess 
      (sqrt-iter (improve guess x) x))) ;;;无论条件是真是假，都会求值这个表达式，导致死循环

习题 1.7

之前求平方根的算法，对于非常大或者非常小的数可能会出错：

出错的原因是什么？
怎么改进？

解答：

首先看看 good-enough? 过程

;;;判断足够好的算法
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

这个算法认为，猜测数的平方与被开方数之间的差值小于 0.001 就是足够好，但是可能有下面两种情况：

对于非常小的被开方数，比如 0.0001，其本身已经小于判定差值，导致任意猜测数都是足够好
对于非常大的被开方数，比如 100000000000000000000000000000000000000 ，由于精度问题，永远不可能满足足够好的条件，导致死循环

改进算法

猜测数的改变量与旧的猜测数的比值小于一定范围，则认为是足够好

;;; 新的足够好算法
(define (good-enough? old-guess new-guess)
    (> 0.01
       (/ (abs (- new-guess old-guess))
          old-guess)))
          
          
;;;由于足够好算法的参数发生了变化，因此主过程也要进行相应的改变    
(define (sqrt-iter old-guess x)
    (let ((new-guess (improve old-guess x)))
        (if (good-enough? old-guess new-guess)
            new-guess
            (sqrt-iter new-guess x))))

练习 1.8

设计一个求立方根的过程，下面这个公式可以改进的猜测值

解答：

题目中给出的公式是改进猜测数的公式，有了这个公式，我们可以模仿求平方根的算法进行设计


;;;题目给出的公式就是改进猜测数的公式
(define (improve guess x)                   
    (/ (+ (/ x (square guess)) (* 2 guess))
       3))
       
;;;给用户使用的接口   
(define (cube-root x)
    (cube-root-iter 1.0 x))

;;;主过程
(define (cube-root-iter guess x)            
    (if (good-enough? guess x)              
        guess
        (cube-root-iter (improve guess x)
                        x)))

;;;检测足够好的过程
(define (good-enough? guess x)              
    (< (abs (- (cube guess) x))
       0.001))

1.1.8 过程作为抽象黑箱

对于一个计算问题，我们一般都可以将他分解为若干个子问题，例如之前的求平方根算法：

但是，定义过程的目的不仅仅是为了分解，而是为了抽象，过程也是一种抽象。

为什么过程是抽象的？

黑箱

过程的使用者不会考虑过程内部的细节和使用的名字，这是一种抽象，也是一种隔离机制。

例如下面两个求平方根的过程，虽然内部使用了不同的算法，但是对使用者来说是没有区别的

(define (square x) (* x x))

(define (square x) (exp (double (log x))))

局部名

过程内部定义的名字（包括形参）都是局部的，其作用域只在过程体中，不会对外部造成影响。如果改变过程内部某个名字，过程的功能不会有任何改变。

下面的两个过程，参数名不同，但是对解释器来说，他俩是相同的：

(define (square x) (* x x))

(define (square y) (* y y))

约束变量和自由变量

过程内部的名字会被过程约束，因此这些名字也叫做约束变量。

而被过程使用，但是不被过程约束的名字就称作自由变量。例如：+ - * 这些全局名字

在过程内部使用自由变量，就说明过程对外部产生了依赖。因此，应该尽量少使用不标准的外部名字

内部定义和块结构

除了变量可以被约束在过程内部，辅助过程也可以被约束在主过程内部，这样的程序内聚性更好

下面改写求平方根的程序，将辅助过程定义在主过程内部

(define (sqrt x)
  
  ;;;是否足够好
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))


  ;;;改进猜测值
  (define (improve guess x)
    (average guess (/ x guess)))


  ;;;核心算法
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))

  ;;;迭代开始
  (sqrt-iter 1.0 x))

注意观察上面的代码，主函数传入的参数 x 会被所有辅助函数使用

其实可以不用传来传去，直接使用即可。改进代码如下：

(define (sqrt x)
  
  ;;;是否足够好
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))


  ;;;改进猜测值
  (define (improve guess)
    (average guess (/ x guess)))


  ;;;核心算法
  (define (sqrt-iter guess)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))

  ;;;迭代开始
  (sqrt-iter 1.0))

注意：参数 x 在这里成为了词法作用域（即主过程作用域）下的自由变量，辅助过程都会对 x 产生依赖，因此不要改变 x （外部依赖）的值

1.1 程序设计的基本元素
1.1.1 表达式数数是一种最基本的表达式过程过程（内置运算符或函数）是另一种基本表达式，例如： + - ...
200915.《Python语言程序设计》-1.1-程序设计基本
《Python语言程序设计》-1.1-程序设计基本方法本节概述计算机与程序设计编译和解释程序的基本编写方法...
计算机程序的构造与解释（过程抽象）
1.1程序设计的基本元素当我们去了解一门新语言时，我们首先应该注意三个方面：基本表达形式，用于表示语言所关心的...
SICP 第1章 1.2节笔记
过程与它们所产生的计算 1.1节描述了程序设计的基本元素并聚焦在过程上，因此1.2就开始讨论过程与他们所产生的计算...
HTML快速恢复之 HTML基础
1. HTML 简介基本语法 1.1 head元素 title元素 base元素 meta元素 link元素 s...
Python 基础学习笔记
基于《Python语言程序设计基础（第2版）》第一部分初识Python语言第1章程序设计基本方法 1.1 ...
第1章 python基本语法元素
1.课程导学 1.1.前课复习 1.2.本章概要2. 程序设计基本方法2.1 计算机与程序设计 2.2 编译和...
《JavaScript 高级程序设计》学习笔记
javascript 高级程序设计在HTML中使用javascript 基本概念 1、语法1.1 区分大小写1...
HTML+CSS 学习笔记 02
一.网页的基本元素 1.1 一个完整的html(网页)包含哪些基本元素呢? 文档定义声明(ddt)HTML文档说...
Java基础知识梳理
Java 基础知识梳理 1、Java的基本程序设计结构 1.1:数据类型 java中存在8中基本数据类型，其中有四...