1.1程序設(shè)計的基本元素

當(dāng)我們?nèi)チ私庖婚T新語言時，我們首先應(yīng)該注意三個方面：

• 基本表達(dá)形式，用于表示語言所關(guān)心的最簡單的個體

• 組合的方法，通過它們可以從較簡單的東西出發(fā)構(gòu)造出復(fù)合的元素

• 抽象的方法，通過它們可以為復(fù)合對象命名，并將它們當(dāng)做單元去操作

這是對所有的語言的一種通用的框架體系。我們首先要關(guān)注就是這些東西。

1.2過程與它們所產(chǎn)生的計算

這節(jié)考察了計算過程消耗各種重要計算資源的（時間和空間的速率）。

首先提出了尾遞歸的概念。

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)

（假設(shè)解釋器或者編譯器支持尾遞歸優(yōu)化）

這兩個函數(shù)完成一樣的工作，然而從過程上講第一個是遞歸，第二個是迭代。

再來看一個初學(xué)者經(jīng)常寫的程序。

def fibonacci(n):

    if n == 1:

        return 1

    elif n == 2:

        return 2

    else:

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

這個過程是樹形遞歸的，效率極低，用迭代來寫會好很多。

記得CSAPP里面有一節(jié)講過這么一個例子：

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

{

    if(lower(s[i]))

    upper(s[i]);

}

實際上這個過程的時間復(fù)雜度是O(n2)，因為strlen這個過程本身是有O(n)的時間復(fù)雜度，可能很多人不會注意到這個細(xì)節(jié)。

這些問題是我們必須要面對的，面對抽象過程，我們可能沒法直接通過觀察看出其效率高低。有些時候正是這些問題導(dǎo)致了程序的效率低下。

1.3用高階函數(shù)做抽象

一般來說，程序設(shè)計語言總會對計算元素的使用方式加上某些限制。帶有最少限制的元素被稱為具有第一級的狀態(tài)。第一級的元素的某些“權(quán)利或者特權(quán)”包括：

• 可以用變量命名

• 可以提供給過程作為參數(shù)

• 可以由過程作為結(jié)果返回

• 可以包含在數(shù)據(jù)結(jié)構(gòu)中

函數(shù)式語言中，函數(shù)是一等公民。

觀察計算過程我們會發(fā)現(xiàn)有很多重復(fù)的模式，我們也可以將其抽象出來。例如Python中的map( )把一個函數(shù)作用到一個可迭代對象的所有元素上，這就是一個公共基礎(chǔ)模式。

在構(gòu)造這些過程時為了簡化過程我們可以使用一些語法糖，例如Python中可以使用列表生成式、lambda表達(dá)式等。

函數(shù)既可以作為傳入?yún)?shù)、也可以作為返回值。