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表达式等。
函数既可以作为传入参数、也可以作为返回值。
网友评论