CS107 Programming Paradigms (Stanford University) by Jerry C

Lecture22

寫一個名為power_set的函數, 它將生成包含輸入集合所有子集的集合.

例:

> ( power_set '(1 2 3) )

( () (2) (3) (2 3) (1) (1 2) (1 3) (1 2 3)) // 注意:　是組合, 不是排列.

以上結果可以看成是由兩部分組成：cons '(() (2) (3) (2 3)) '((1) (1 2) (1 3) (1 2 3))

另 外：

> (power_set '())

(())

定義：

(define (ps set)

( if (null?set) '(())

( append ( ps (cdr set ) ) // 1

( map ( lambda ( subset)

( cons (car set) subset ) )　　// lambda中的函數用於map 操作時, 對列表中每個元素進行運算．

( ps ( cdr set ) ) ) ) ) ) // 2 本行產生map操作的列表

以上代碼中, 1/2兩處的set指向同一個集合對象 Scheme中通過變量名來向對象是唯一的方法．

//--------------------------------------------------------

寫遞歸函數的技巧：

A. 最簡值中抽出規則：1. 尾元素+ 剩余元素 2. 列出幾個頭元素的具體生成

B. 給出最簡時的值：初值．　采用A中獲得的遞歸規則進行疊加．

C. 寫遞歸函數時往往是從給定的n開始，反向遞減．

在Scheme語言中, 沒有循環, 一般用遞歸函數來代替循環．

//--------------------------------------------------------

( define ( ps set )

( if ( null ? set) '(())

( let ( ( ps_rest ( ps ( cdr set ) ) ) ) // 使得只作一次cdr運算, 運算結果可以在let 范圍內各處使用, 從而節省時間.

( append ps_rest

( map ( lambda ( subset)

( cons ( car set) subset ) )

ps_rest ) ) ) ) )

此定義與上定義等價，但運行效率高許多.

//--------------------------------------------------------

let 表達式：

( let ( ( x expv1)

( y expv2)

( z expv3) )

... )

實際上：

( let ( ( x ...)

( y ...) )

( a x y ) )

等價於：

(( lambda ( x y )

( a x y )) ... ...)

let 是換一種不同的方式將一些應用函數表示成一些有待評估的表達式．

//------------------------------------------------------------------------

寫一個名為permate 的函數．它能輸出列表的全部6種排列．

> (permate '( 1 2 3))

( ( 1 2 3 ) ( 1 3 2 ) // 以1 打頭

( 2 1 3 ) ( 2 3 1)　 // 以2打頭

( 3 1 2 ) ( 3 2 1) )　// 以3打頭

接收一個長度為n的列表，輸出的是一個長度為 n! 的列表．

( define ( permate items)

( if ( null?items ) '(())

( apply append

( map ( lambda (elem)

( map ( lambda ( permatation )

( cons elem permatation ) )

( permatation ( remove items elem ) ) ) )

items ) )

//------------------------------------------------

Scheme程序編寫技巧：

其程序可看作由一部分一部分拼起來，在寫的過程中，可以不按程序運算的邏輯順序來寫．( 可以先寫後面的再寫前面的, 先寫中間的再寫兩頭的等等. )

Scheme的許多內置函數後面都維護著一個數據結構，因此用戶只需要調用內置函數，而無需自已再根據應用來分配、調度和管理內存；無需用戶自已來維護相應的數據結構。

Scheme的程序運行的執行過程，可以分為三個步驟：輸入－評估－打印.

不論用戶輸入的數據是什麼類型，Scheme都會在後台產生一個鏈表，接收輸入的數據後將其填寫到鏈表相應的結點中，並標明數據類型，最後返回這個鏈表的首地址，為後面的評估過程作准備。

> '(1 2 3)

( 1 2 3 )

> ( cons 1 ( cons 2 ( cons 3 '() ) ) )

( 1 2 3 )

以上兩段代碼是等價的。

cons作為Scheme的一個符號是依附在一段代碼上的，解釋器很熟悉，解釋器遇到cons後就知道怎麼分配一段內存給相關的數據，分配好後，它還要知道在各已分配內存空間中需要放入什麼數據。

以上為Scheme的基本工作原理，可以用C++模擬寫一個min版的Scheme解釋器。

Lecture23

Scheme的內存分配和管理

> ( define seq '(1 2 3) ) // 此定義將名為seq的變量與結點值域分別為1, 2, 3的鏈表關聯起來. seq 為一個全局變量.

> ( car seq ) // car 評估並獲取全局變量seq 所指身的鏈表的首結點的數據域的值.

> ( cons '(1 2 3) '(4 5 6) )

((1 2 3 ) 4 5 6)

在cons運算之前, 系統會生成兩個鏈表,一個鏈表的結點分別為: 1 2 3. 另一個鏈表的結點分別為 : 4 5 6. cons運算後, 會生成一個新結點. 結點的值域保存鏈表 1 2 3 的首地址, 結點的指針域保存鏈表 4 5 6 的首地址.

> ( cons '(1 2) '(1 2) ) // 1

( ( lambda (x) ( cons x x ) ) '( 1 2 ) ) // 2

由於打印函數對內存管理視若無睹. 打印函數只簡單地要求打印列表的car部分和cdr部分. 所以以上兩個函數的打印結果是一樣的. 但實際上,兩個函數的內存分布是不一樣的.第二個函數產生的只有三個結點的鏈表,第二和第三個結點分別保存值1 2. 而首結點的值域和指針域同時指向第二結點.

//--------------------------------------------------------------

> ( map car '( (1 2) (3 4) (5 6 7) ) ) // map 可帶任意個參數

(1 3 5)

> ( map + '(1 2) '(10 20) '(100 400) )

(111 422)

> ( map * '(1) '(2) '(3) '(4) '(5) )

(120)

實現:

( define ( unary-map fn seq ) ) // 比較Lecture21中的my_unary_map

( if ( null ? seq) ()

( cons ( fn (car seq) )

( unary-map fn ( cdr seq ) ) ) ) )

因為:

( define ( bar a b c . d)

( list a b c d ) )

> ( bar 1 2 3 4 5 6 )

( 1 2 3 ( 4 5 6 ))

> ( bar 1 2 3 )

( 1 2 3 ())

也就是說點"." 表示其後無論有多少個參數, 都將被收集起來放到參數列表中.

所以map的定義為:

( define ( map fn first-list other-list)

( if ( null ? first-list) '()

( cons ( apply fn

( cons ( car first-list )

( unary-map car other-list ) ) )

( apply map

( cons fn

( cons ( cdr first-list )

( unary-map cdr other-list ) ) ) ) ) ) )

map 底層是依靠cons來幫助它分配空間的. cons調用時Scheme會自動生成一個cons區域.

當打印輸出完成後, 之前cons分配得到的cons內存區域就會被回收.

例子:

>( define x '(1 2 3) ) // 變量x與鏈表( 1 2 3 )關聯起來了.

>( define y (cdr x) )

>( define x '(4 5) ) // 這樣一來結點結點 1 就無變量指向了. 某些系統會給每個結點設一個計數器, 當計數器為0時, 由垃圾回收器自動回收.

Scheme的垃圾回收機制:

所有變量(如: x, y)放在Symbal map集中, 系統自動生成的鏈表結點放在mast cons set集中, 每個單元結點都可以被單獨釋放. 然後根據define的定義將變量與鏈表結點關聯起來.

系統會根據算法, 在需要的時候對Symbal map中的所有變量作一次搜索. 對mast cons set中與之有關聯的結點作上標記. 然後令mast cons set收回其集中所有未做標記的結點.

//-----------------------------------------------------------------

ML 是Scheme的增強版

Harkll

Erlang 優勢: 並行處理

Lecture24
C語言是由寫unix的人發明的, 目的是使寫操作系統更容易.
C++在70年代末~80年代初開始出現.
Python從2000年開始流行.
循環的一輪被稱為一次迭代, 所謂用迭代來代替遞歸, 就是用循環來代替遞歸. 反過來, 遞歸也可以用來替換迭代. 如scheme語言所示.
"hello there".statswith("...")
"hello there".capitalize()
"Hello There".istitle()
"[ ]" 表列表且此列表可變.
//--------------------------------
smallnum = [ 1, 2, 3, 4, 5, 6]
len( smallnum )
smallnum[ -2 ]
smallnum[ len( smallnum ) - 1 ]
smallnum[ 1 : 3 ]
smallnum[ 0 : 3 ]
smallnum[ 0 : 0 ]
smallnum[ -2 : ]
smallnum[ 1 : -1 ]
smallnum[ 1 : 0 ]
smallnum[ 1 : ]
"hello there"[ 4 : 7 ]
//--------------------------------
seq = [ 0, 1, 2, 3, 5, 6, 7, 8]
seq[ 4 : 4 ] = [ 4 ]
seq
//--------------------------------
seq = [ 5, 9, 2, 0 ]
seq
seq[ 0 ] = 14
seq
//--------------------------------
seq = ( 1, 2, 3, 4 )
seq[ 1 ] = 14
//--------------------------------
seq = [ "a", "b", "c"]
seq.append( "d" )
seq
//----------------------------------------------
在名為 divisors.py 的文件中作如下定義:
def getherDivisors( number ) :
divisors = []
for div in range( 1, number+1 ) :
if number % div == 0:
divisors.append( div )
return divisors
每一行的縮進靠制表符設定.
三重引號對表注釋字符串將出現在多行中.
在其它模塊中引用函數getherDivisors的方式有兩種.
方法1:
>>> import divisors
>>> divisors.getherDivisors( 24 )
方法2:
>>> from divisors import getherDivisors
>>> getherDivisors( 24 )
//--------------------------------------------------
字典
>>> student = {} // 大括號對描述一個字典常量的所有內容.
>>> student
{}
>>> student["name"] = "Linda"
...
>>> student["gpa"] = 3.56
>>> student
...
>>> student["gpa"]
...
>>> student["gpa"] = 4.5
...
Python中的所有對象( 如: 列表, 字典等 )都是通過引用傳遞的.
>>> student["friends"] = ["aa", "bb", "cc"]
>>> student
...
>>> student["ideas"] = {}
>>> student
...
>>> playground = { }
>>> playground[ 4 ] = "think"
>>> playground
...

Lecture25

字典是Python的基礎

grammar = { '' : [ [ 'This', '