计算机程序的构造与解释（过程抽象）

1.1程序设计的基本元素

当我们去了解一门新语言时，我们首先应该注意三个方面：

• 基本表达形式，用于表示语言所关心的最简单的个体

• 组合的方法，通过它们可以从较简单的东西出发构造出复合的元素

• 抽象的方法，通过它们可以为复合对象命名，并将它们当做单元去操作

这是对所有的语言的一种通用的框架体系。我们首先要关注就是这些东西。

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

这节考察了计算过程消耗各种重要计算资源的（时间和空间的速率）。

首先提出了尾递归的概念。

def factorial_1(n):

    if n == 1:

        return 1

    else:

        return n*factorial(n-1)

def factorial_2(n, s=1):

    if n == 1:

        return s

    else:

        return factorial_2(n-1, n*s)

（假设解释器或者编译器支持尾递归优化）

这两个函数完成一样的工作，然而从过程上讲第一个是递归，第二个是迭代。

再来看一个初学者经常写的程序。

def fibonacci(n):

    if n == 1:

        return 1

    elif n == 2:

        return 2

    else:

        return fibonacci(n-1) + fibonacci(n-2)

这个过程是树形递归的，效率极低，用迭代来写会好很多。

记得CSAPP里面有一节讲过这么一个例子：

for(int i = 0; i < strlen(s); i++)

{

    if(lower(s[i]))

    upper(s[i]);

}

实际上这个过程的时间复杂度是O(n²)，因为strlen这个过程本身是有O(n)的时间复杂度，可能很多人不会注意到这个细节。

这些问题是我们必须要面对的，面对抽象过程，我们可能没法直接通过观察看出其效率高低。有些时候正是这些问题导致了程序的效率低下。

1.3用高阶函数做抽象

一般来说，程序设计语言总会对计算元素的使用方式加上某些限制。带有最少限制的元素被称为具有第一级的状态。第一级的元素的某些“权利或者特权”包括：

• 可以用变量命名

• 可以提供给过程作为参数

• 可以由过程作为结果返回

• 可以包含在数据结构中

函数式语言中，函数是一等公民。

观察计算过程我们会发现有很多重复的模式，我们也可以将其抽象出来。例如Python中的map( )把一个函数作用到一个可迭代对象的所有元素上，这就是一个公共基础模式。

在构造这些过程时为了简化过程我们可以使用一些语法糖，例如Python中可以使用列表生成式、lambda表达式等。

函数既可以作为传入参数、也可以作为返回值。