北航程序設(shè)計語言原理教材第04節(jié)-note

1、第4章第4章存儲如前所述，程序世界、機器世界是同一事物的不同層次描述。在每個層次上各有自己的術(shù) 語概念。我們的目標雖然是為程序世界提供表達程序的術(shù)語和語言，因為它們密切相關(guān)。我們 也應(yīng)該了解機器世界里存儲對象有哪些，怎樣工作，可以實現(xiàn)哪些機制。這些工作機制反映到 程序世界是什么？在某種意義上說，越能在上層構(gòu)造出更新、更多的符合軟件工程原理的程序 對象，越要在下層想出更多的實現(xiàn)辦法，如果都能實現(xiàn)，則程序設(shè)計語言就進了一步。有關(guān)存儲對象的基本術(shù)語和機制，我們假定讀者已在匯編語言課程學(xué)過，此處不重復(fù)， 只是在涉及到機器世界術(shù)語和機制時我們才提到它。請注意，我們討論問題的立場是程序世 界。還要注意到，

2、程序?qū)ο蠛痛鎯ο蟛⒎且灰粚?yīng)的，賦初值的簡單常數(shù)一般也是不作為獨 立的存儲對象，直接放在被賦值的變量中。所以研究存儲對象的核心是抓住“變量”。本章主要討論變量的時空特性，第二節(jié)介紹各種實現(xiàn)計算的存貯模型，第三節(jié)討論因時空 關(guān)系而出現(xiàn)的懸掛指升問題，第四節(jié)討論各種語言變量更新機制，第五節(jié)介紹有副作用的表達 式。4.1程序變量的時、空特性如前所述，程序世界中的變量不同于數(shù)學(xué)變量在于它的時、空特性。我們先從空間特性開 始。我們知道，計算機內(nèi)的變量的存儲空間是隨時可變的，它可以在外存磁盤上，也可以在內(nèi) 存的某個地方，而且同一程序兩次加載運行變量也不會在一個地方，即非固定地址。為此， 一般目標程序中都

3、采用相對地址的辦法，絕對地址就不重要了。對于程序，我們要找到某個計 算對象，永遠從該段程序的首地址開始。為了簡化，我們在虛存空間討論存儲對象。'取地址4.1.1 引用和指針由于變量的名值分離，當(dāng)程序操縱變量時，首先尋址再取內(nèi)容。這是兩種操作'（引用）和取值'（遞引用）。命令式語言兩者都要，且有時是隱式的。自從Pascal,C引入指針變量可顯式操縱變量的地址，給程序員帶來極大方便。例如，一個大單位，隨機錄用上千個員 工。每個員工履歷是一復(fù)雜記錄，現(xiàn)登記現(xiàn)錄入無序存放。我們只要按它的某個屬性特征對指 向它們的首地址（指針）排序，即可按排好序的指針表次序打印各種報告，而無需將

4、龐大的記錄 重排多次。指針本身也是程序?qū)ο?，它也有地址，于是C語言允許多級指針的機制。其它語言編譯只允許一級指針，除非指向復(fù)雜數(shù)據(jù)結(jié)構(gòu)內(nèi)嵌的指針。用f（Pascal）和*（C）標記指針變量標識符以識別是操縱指針變量的內(nèi)容（地址），還是操縱指針變量所指對象的內(nèi)容（值）。例4-1 , C程序中的指針int i;第94頁PP P q g q&P*p+1 p+1/P/q/'1'指向整變量i錯誤，p中只放地址值正確，正確，指向i，效果同*p=i , &取地址符 同類型賦值，q, P都指向i此時i已成為i+1僅是名，值取決于所指對象每個單元占多少字節(jié)。q;int * p所謂

5、尋址即要給出編譯(或解釋)時程序變量名與地址的對照表。每當(dāng)給程序?qū)ο蠓峙浯?儲時就在表中填入，這樣就創(chuàng)建了引用(refere nee)。由于程序?qū)ο竺志幾g后不存在，每次4-1 O操縱用的是地址，這個在對照表中有的地址即為該對象的別名。早期語言認為這是屬于內(nèi) 部的事，外叫變量，內(nèi)叫地址碼。而C+語言把這個占據(jù)存儲的存儲對象也上升為程序?qū)ο螅凶鲆?，使用戶直接操縱地址。引用，指針、變量關(guān)系的示意圖如圖P1p22(RA)3113631140 32O(RC)144500488504450(P1)4481361364274.54(A)引用(P2)140 I1443312.27607.01(B)( C

6、)指針圖4-1變量、指針、引用示意圖變量A的地址碼分配為136放在312中，每當(dāng)程序中用 A的左值，查出136即是，若用A的右 值查到136再找136的內(nèi)容。既然312也是存儲單元地址，則把它對應(yīng)為一引用名RA只是一旦給出136再也不許改變，它成了 A的別名，相當(dāng)于常量指針。指針P1, P2既是程序?qū)ο?，它們被分配?48，450存儲單元內(nèi)，地址碼 448，450同樣成為P1, P2的代替物。如果在 448中給予 136地址則P1指向A。給140則指向B。其內(nèi)容是可變的，所以和引用RA不一樣。RA雖然也放一個地址，但更強調(diào)的是引用內(nèi)容。即當(dāng)RA A同時出現(xiàn)在賦值號右邊，其效果完全一樣，這一點和

7、常量指針又不一樣。它和變量A不同之處僅在實現(xiàn)上，效果是相同的，而且引用變量必須賦初值，一旦賦初值則在其作用域在其所在程序單元的范圍內(nèi)不得改動。C+ 和C引入引用主要是用于函數(shù)調(diào)用的傳地址。形、實結(jié)合正好相當(dāng)于引用變量賦初 值。(這在第6章中還要講)。4.1.2 遞引用般說來，通過指針變量引用某變量的內(nèi)容叫做遞引用(derefere nee)。多層指針則多次遞引用。指針用或 * '顯式地表達了它的遞引用。但多數(shù)程序設(shè)計語言都有隱式的 遞引用。例如，下標表達式，除了引用下標變量值再引用該元素的值，即使出現(xiàn)在賦值號的左 邊的下標表達式也是遞引用。我們稱這是自動遞引用。FORT語言是唯一不容許

8、自動遞引用的，它只有顯式遞引用運算符例4-2 FORT H的遞引用運算符1 13 VARIABLE xx2 0 VARIABLE Y3 XX 2 * Y !如果只寫XX 2 *聲明變量XX并賦初值13) 聲明變量丫并賦初值0)相當(dāng)于Y=xx*2)(則為將XX的地址乘以2放在Y之中。4.1.3 變量的時態(tài)除了空間名值分離導(dǎo)出指針、引用、遞引用程序世界的概念之外，變量還有時間特性， 以它的狀態(tài)刻劃：(1) .分配/未分配/除分配為程序?qū)ο蠓峙浯鎯蛣?chuàng)建了存儲對象，程序?qū)ο缶涂梢栽L問了。如果在編譯時做這個工作我們叫靜態(tài)分配，程序中變量多數(shù)如此。如果在程序運行時刻分配存儲，我們叫動態(tài)分 配，程序中的指

9、針(或訪問)類型變量則按動態(tài)分配，一般由程序員顯式指定(用new操作)。若程序?qū)ο舐暶髁说捶峙浯鎯ο蠹赐度脒\行，此程序?qū)ο筇幱谖捶峙錉顟B(tài)。撤消程序?qū)ο蠹闯ヒ逊峙涞拇鎯ο螅覀兘谐峙浠虺?deallocate)。除分配可由程序員顯式指定(用delete操作)，也可以約定由語言的執(zhí)行系統(tǒng)或操作系統(tǒng)自動實現(xiàn)。自動將當(dāng)前無用的程序 對象除配，并收回待用稱無用單元回收(Garbage collectio n)機制。動態(tài)(或無)類型語言一般有此機制，靜態(tài)類型語言雖然也有動態(tài)分配部分，往往不設(shè)此機制(如C語言)(2) .定義/未定義/失去定義分配的存儲單元總是有殘值的(上個程序運行后留下的)，這

10、些值無任何意義(與本程序無 定義變量，除了它的值對本程序計(例如，一個局部塊的末端), 以下舉例說明。關(guān))。我們說，變量 未定義。如果通過賦值或賦初值，就是 算是有意義的。如果該變量執(zhí)行超出了我們指定它有意義的區(qū)域 只要它的存儲沒有撤消，它總是存在，但其內(nèi)容(值)已失去定義。例4-3 變量的狀態(tài)(Ada)P rocedure MAIN is declare BLOCK ;type CELL ;type LINK is access CELL;type CELL is recordVALUE:INTEGER;NEXT: LINK;end record;type VECTOR is array (

11、INTEGER range< >) of FLOAT;LA:LINK ; V: VECTOR ;VB:VECTOR(1.5)beginLA:=new CELLLA.all:=(3120聲明訪問類型變量 聲明數(shù)組類型變量 聲明數(shù)組類型變量LA，但未分配V 未分配VB,運行前已分配但未定義,n ull)動態(tài)分配無名CELL對象由LA代名 定義LA所訪問對象V:=(1=>5.04=>2.0，2=>4.0 ；3=>3.0，5=>1.0 ， 6=>0.0)-分配V為六元素數(shù)組，且得到定義，動態(tài)完成 只有VB(3)得到定義，VB的其余元素未定義VB(3) e

12、nd BLOCK L : = LA ；:=V(1)；-LA-V-Ada值已失去定義，出錯,VB(3)的值均失去定義有無用單元收集，此處可將失去定義的變量存儲回收end MAIN;4.1.4可存儲值就變量訪問和更新而言，我們把可以直接訪問和更新的存儲對象的值稱為可存儲值 (storable)。它們是可訪問的最小存儲單元。因此，復(fù)合值如果它們的成分不能選擇更新， 該復(fù)合值即為可存儲值。例如，Pascal的集合值，不能單獨更新其中某個元素，它是可存儲值。反之，數(shù)組元素是可以選擇更新的。整個的記錄、文件也都不是可存儲值。所以， Pascal中可存儲值是：基本類型值C+語言設(shè)置了引用集合值 指針值 變量

13、引用、函數(shù)過程抽象也不是可存儲值，它們本身不是可存儲的。 類型變量，變量引用有了名字，它是可存儲的。ML的可存儲值有：基本類型值 記錄、構(gòu)造、表 函數(shù)抽象 變量引用ML的記錄、構(gòu)造、表是可存儲值，因為它們不能選擇更新，更新其中一個元素存儲要重整一遍。由于函數(shù)抽象和變量引用全部采用類似C+引用類型的辦法，借助于引用可以有選擇地更新復(fù)合值。事實上除數(shù)組而外，ML所有的值均為可存儲值。例4-4 ML的函數(shù)抽象是可存儲值函數(shù)名即函數(shù)抽象，在 Pascal中，f(x)的f是不能單獨存取和更新的，ML中卻可寫為：(if exp the n sin else cos) (x)這個條件表達式的返回值(sin或

14、cos)是函數(shù)抽象，sin(x)是函數(shù)定義，也叫型構(gòu) (signature), sin(a)是函數(shù)引用。后二者都不是可存儲值。4.2組織存儲對象的存儲模型存儲管理模型是翻譯器必須選定的關(guān)鍵部分，各語言不盡相同，但從總體說有三種存儲 模型，靜態(tài)存儲，堆存儲，棧存儲。后二者也稱動態(tài)存儲模型。421存儲對象的生命期每個存儲對象都有其創(chuàng)建 （生）、可用（活著）、撤消（死）的生命期。每當(dāng)分配存儲即創(chuàng)建 存儲對象。當(dāng)所在程序塊或整個程序執(zhí)行結(jié)束，程序?qū)ο笏劳?，存儲對象也?yīng)自動撤銷。但多 數(shù)對象生命期不會像程序執(zhí)行期一樣長，也有少量對象的生命期比程序還要長。我們把壽命和 程序一樣長的變量稱為全局變量；壽命和

15、程序中一個或幾個模塊一樣長的變量稱局部變量;壽命大于程序執(zhí)行期的變量稱持久變量。文件變量即持久變量。與此對應(yīng)，程序中變量都叫臨時變量（包括全局、局部、靜態(tài)、堆變量活著的對象必須在內(nèi)存中才可用。然而，由于有虛擬存儲技術(shù)。外存上虛存中的對象也是 活對象，除非所占存儲被撤銷并分配給其它程序?qū)ο?。在程序?zhí)行期間，一個存儲單元可多次分配給局部變量，甚至同一存儲對象可由多個程序 對象共享，如C的聯(lián)合，Pascal、Ada的變體記錄。FORTRAN價語句指明的各變量。反過來，一個程序?qū)ο罂捎啥鄠€存儲對象實現(xiàn)。如前述的引用、指針。程序?qū)ο笏懒?，對?yīng)的存儲對象沒撤銷，此時引用該對象就會引起難以預(yù)計的錯誤。分 配

16、了沒有賦（初）值就引用也會引起錯誤。這兩種錯誤在程序調(diào)試中屢見不鮮。422靜態(tài)存儲對象在程序運行之前分配的程序?qū)ο蠖冀徐o態(tài)存儲對象。編譯時分配自不用說。近代語言有 在裝入內(nèi)存后，運行前分配，Ada稱之為確立（elaboration）期間（確立除分配某些對象外還計算初值表達式定義初值）。之所以稱靜態(tài)，因它們在分配之后整個程序執(zhí)行期間不再改動。靜 態(tài)分配常伴之以初始化。所有語言的全局變量都是靜態(tài)對象。某些語言（COBOL）只有靜態(tài)對象；某些語言（P ascal）除全局變量而外沒有靜態(tài)對象；而C和Algol允許程序員把局部變量聲明為靜態(tài)的，即該局部塊執(zhí)行結(jié)束靜態(tài)變量并不失去定義，該塊下次還可用，但同

17、一程序其它局部塊卻不能用。所以 Algol把它叫做OWN自己的），聲明中顯式指明。C則用Static ，C的extern變量全局于所在文件也是靜態(tài)的。靜態(tài)存儲對象直觀易于查錯，但它不能支持遞歸，因為多次遞歸調(diào)用相關(guān)的動態(tài)參數(shù)無 法分配（不知道遞歸幾次）。靜態(tài)存儲對象僅限于全局變量的第二個缺點是被迫使用易引起副作用的全局量。對于某 些問題（如求隨機數(shù)，輸入/出程序指示當(dāng)前輸入/出位置的指針）需要在程序多次執(zhí)行時值有 連續(xù)性，因而沒有執(zhí)行后仍保持值的變量（若完全是局部變量執(zhí)行后自動銷毀）無法模型客觀世界。然而，采用全局變量其它無關(guān)模塊也可使用就會引起副作用，C的靜態(tài)變量即為局限于一個文件（模塊）的

18、局部變量，即保持值的連續(xù)性又有保護作用。靜態(tài)存儲對象，無論是全局量還是局部量的第三個缺點（也是它的優(yōu)點）是占據(jù)的存儲不FORTRA的等價語句（新一代語言的聯(lián)合、變體記錄 ）C語言叫自動變量）是靜態(tài)程序中的局部變量（到程序執(zhí)行完不釋放。對于大程序且有眾多只需短壽命變量的應(yīng)用就浪費了大量存儲。即使有 無用單元回收機制不到執(zhí)行完也收不到它， 就為（起到）緩解作用而設(shè)。請注意，靜態(tài)分配的不一定是靜態(tài)變量， （編譯時）分配的，運行時存貯的地址可變。423 動態(tài)存儲對象動態(tài)存儲對象在程序執(zhí)行期間誕生（分配和定義），故名動態(tài)。多數(shù)動態(tài)對象它們的大小和結(jié)構(gòu)形態(tài)往往依賴輸入，編譯時無法確定。例如，遞歸定義的二叉

19、樹，其結(jié)點、葉子、層數(shù) 完全由輸入值定。因此，動態(tài)存儲對象生命期長短不同，大小不同，類型各異，如何使存儲管 理高效是一個中心問題。管理不好對程序執(zhí)行的時、空效率影響極大。在某種意義上說，它是 發(fā)展先進語言或軟件技術(shù)的關(guān)鍵。例如，Prolog、Smalltalk出現(xiàn)初期都是執(zhí)行效率難以和傳統(tǒng)語言匹敵的，慢 5-30倍。不斷改進才能進入實用。影響最大的因素是動態(tài)存儲對象的生命 期，而不同生命期存儲對象搭配使用，恰巧是增加表達能力，減少程序錯誤的進步。所以一般 語言提供管理不同的生命期對象的模型。最簡單的模型是在內(nèi)存中開辟一個堆（heaP）空間，放入其中的動態(tài)對象的壽命完全由程序員控制，語言系統(tǒng)全然

20、不知。每當(dāng)創(chuàng)建一新存儲對象，存儲管理則找出一個足以放下該對象的堆空間。每當(dāng)存儲管理得知（出了所在程序塊）它已死亡，它就記下該對象不再使用。隨來隨堆，誰死誰釋放，新來的沒地方就等到老的死了再存入，故名堆。一般的指針動態(tài)生成的對象即按此型式，故指針變量也叫堆變量。管理堆型式最大的問題是多次存儲后留下存儲碎片，因為新對象的大小往往不能填足老 對象的空間，時間長了形成星星點點的許多“小洞”，管理很麻煩。拿出記錄該碎片信息所費 存儲比這些“小洞”本身小不了多少，而且運行時一個到一個鏈接十分低效。再者還沒有能找 出合適的識別算法將“小洞”合并。這些問題各語言系統(tǒng)都采取了各自的做法。本節(jié)將介紹主 要做法。由

21、于堆型式管理存在著麻煩，人們尋求并得到第二種管理型式：嵌套生命期型式，按照 這種型式任何兩同時出現(xiàn)的對象其生命期長短可以不同，但必須完全嵌套，即不能交錯。也就 是在時間上一個包容一個，我們就可以把相近壽命變量歸成一組，最長壽命組放在堆棧的底部最短的在頂部，逐級釋放和重新占據(jù)存儲，可以得到成片干凈的存儲。如圖4-2所示。塊11 塊2 塊3塊4 I 塊51塊6 IJ4r6-r-l' :XXI,14J亠丄"Lbbbxbbbbxi圖4-2嵌套生命期存儲原理圖6組不同壽命的存儲塊。由于塊6中對象壽命最短，全部重新分配3次本例依次分配了塊4,塊5可重新分配兩次而塊 1的一次生命期還沒完。

22、如同倒下來的堆棧，棧頂?shù)膶ο笊?快死得也快，死了清除再分配第二批。而棧底的對象一直活著。事實上，動態(tài)對象壽命長短本 來就和所在嵌套模塊相關(guān)，只要把壽命特長的（如文件，全局量）排出來歸到棧底的某一組,把壽命特短的（如循環(huán)控制變量）另立嵌套組，這個分組的問題也就解決了。424動態(tài)堆棧存儲按照嵌套生命期存貯原理，對于嵌套塊結(jié)構(gòu)的程序設(shè)計語言如（Pascal，Ada, C）動態(tài)堆棧型管理特別有效，因為多數(shù)變量和所在塊壽命一樣長。變量生死隨所在塊的激活和消亡高效 自動實現(xiàn)。所以C語言把局部于塊結(jié)構(gòu)的變量叫做auto（自動）變量。但多數(shù)語言（包括C）堆、堆棧管理同時并用（原因見后文）。4.2.4.1動態(tài)

23、堆棧式管理機制為了說明堆棧式管理，我們再參照圖 如圖4-3所示。4-2運行時堆棧，結(jié)合執(zhí)行過程，介紹其實現(xiàn)機制,f參數(shù) XkLBBJXLB-S-h返回地址 =動態(tài)鏈 靜態(tài)鏈“返回值"”“局部變量程序代碼,全局靜態(tài)存儲 首先調(diào)用塊:堆棧幀最新調(diào)用塊堆棧幀棧頂:第二調(diào)用塊 堆棧幀臨時變量空間運行時堆棧堆棧幀組織圖4-3 運行時堆棧和堆?？蚣軐崿F(xiàn)運行時堆棧（Run-time stack）是在內(nèi)存開辟一個空間，如同堆。首先將程序代碼和全局、靜態(tài)變量裝入，示意為圖4-3的右圖最上一塊。這一塊的詞法上輩（Lexical Parent） 是操作系統(tǒng)。當(dāng)執(zhí)行控制開始時，首先執(zhí)行這一塊，當(dāng)執(zhí)行到調(diào)用時

24、，按編譯時生成的嵌套關(guān)系， 找出被調(diào)用的塊，將該塊的數(shù)據(jù)（包括實參和局部量）作為新的一幀，記下靜態(tài)鏈（連接詞法祖先（Lexical ancestor），壓入運行時堆棧后記下動態(tài)鏈（連接執(zhí)行順序）。由于編譯時詞法祖先塊的地址無法確定，靜態(tài)鏈要根據(jù)祖先塊分配存儲對象去找，有時要用到局部變量和參 數(shù)。動態(tài)鏈指出當(dāng)前塊的動態(tài)執(zhí)行的上輩，以便在塊出口時彈出棧內(nèi)的執(zhí)行指令。動態(tài)和靜態(tài) 鏈在壓入棧時利用局部分配指針從棧中第一個自由位置逐個向上（下）分配，記下該指針的值，以便以后彈棧。每個堆棧幀（stack frame） 的組織如圖4-3的左圖，它按以下事件序列壓棧：1 入，234 的。調(diào)用程序?qū)崊⒅抵糜谛?/p>

25、塊底部，用局部分配的指針，一般說，最后一個實參先放倒數(shù)第二個第二第一個放在最上面。接著放入新塊的返回地址。把當(dāng)前棧頂指針值拷貝到棧內(nèi)，這是新塊動態(tài)鏈的一個域（存放當(dāng)前棧頂?shù)刂罚Ｌ顚戩o態(tài)鏈，將編譯時生成的標記碼拷貝進來，對于調(diào)用塊靜、動態(tài)鏈標記是一樣再留足夠的位置以放下局部變量的返回值，如已有初始化則拿來就可以了。控制轉(zhuǎn)回父塊代碼執(zhí)行，直至到生成另一個內(nèi)嵌塊的堆棧幀，如此，運行堆棧又生成一層如果某塊對應(yīng)的程序代碼出口則根據(jù)動態(tài)鏈返回父塊，再生成復(fù)蓋的新的一層堆棧幀 老塊被復(fù)蓋也就是除分配了。此處為了簡化，返回值假定在塊內(nèi)，實際上常用寄存器。4.2.4.2用堆棧式存儲實現(xiàn)遞歸顯然，遞歸調(diào)用是堆棧

26、存儲管理最簡單的形式。因為它的運行棧每次壓入的是同一模塊 新的數(shù)據(jù)對象版本，靜態(tài)鏈自然按逐層遞歸調(diào)用展開直至到達邊界，現(xiàn)舉例說明。例4-4 P ascal的遞歸函數(shù)In teger): In teger ;求整數(shù)之連乘積function P roduct (jj:var kk : In teger;beginif jj <= 0 the n p roduct:=1else begi nreadl n (kk)；p roduct:=kk * p roduct(jj-l)讀二次 kk=25 , 7 。endend ;其執(zhí)行圖示于圖4-4.為簡化令jj=2 ,動態(tài)鏈靜態(tài)鏈最初調(diào)用時堆棧幀第一次

27、調(diào)用時堆棧幀第一次調(diào)用時堆棧幀棧頂圖4-4遞歸函數(shù)的堆棧幀4.2.5 動態(tài)堆存儲動態(tài)堆棧存儲雖然解決了碎片問題，但是存儲對象壽命只能和堆棧幀同時生死，限制太 嚴。而且在每一個塊的進口處并不知道存儲對象的大小和個數(shù)，以及要求存儲對象比創(chuàng)建它的塊的壽命長。所以堆存儲有時是必不可少的。我們再詳細討論堆存儲。4.2.5.1 堆分配許多語言允許程序員顯式分配動態(tài)存儲，分配語句可以出現(xiàn)在程序中的任何地方，辦法 是調(diào)用操作系統(tǒng)ALLOC函數(shù)。ALLO(將存儲對象分配在堆中并返回對該對象的引用。如前所述堆 分配有時在連接的較小的空間上，算法比較復(fù)雜。所以要建立一處自由表登錄已死存儲對象的 空間，并查清相鄰的碎

28、片予以合并。這些算法還必須高效，否則影響性能。故往往是折衷，求快速犧牲一些過小碎片(這又是潛在危險，當(dāng)指針錯誤地指向這些無用小碎片時，后果極難預(yù)料)。各個語言組織動態(tài)堆及分配后的返回值也不完全一樣。現(xiàn)例舉說明：(1) FORTH的堆分配/除配 分配：HERE <表達式>ALLOT程序員通過 HEREN, ALLOT各N個字FORTH在存放符號表和全局對象的字典中作動態(tài)分配。HER是系統(tǒng)變量，另設(shè)一小棧記下新增區(qū)域存入，用戶只存入指針變量。 無無用單元回收。重新分配由用戶自己寫例程。 的分配/除配(cons<表達式1><表達式2>)訪問字典頂端指針。先把 HE

29、RE勺當(dāng)前值放入堆，然后對表達式求值得一整數(shù) 節(jié)加到字典指針。除配1的值填入,2式是N個字節(jié)；第3(2) LIS P 分配：見到這個表達式就分配一新表，并返回對新表的引用。新表左域由表達式 右域用表達式2的值填入。除配：由無用單元收集機制自動完成。(3) C的動態(tài)分配/除配分配：malloc (sizeof(T) malloc(N) calloc(N, sizeof(baset yp e)式中T、basetype是類型名，N是整數(shù)。第1式是分配T類型的一個對象；第 式是分配一個數(shù)組，類型為 basetype，元素是N個，并初始化為0。malloc和calloc均返回對 新對象的引用。程序員必須

30、將返回值賦給某個指針類型或強行轉(zhuǎn)成所希望的指針類型。(再分配)。除配：free (ptr)ptr必須指向已分配過的堆對象。該對象經(jīng)此函數(shù)即可重用(4) Pascal動態(tài)分配/除配分配：new (<指針名>)< 指針名 >必須是聲明為指向某類型的指針。該指針存放引用返回值。除配：Dis pose (< 指針名>)< 指針名 >所指對象置入自由表。(5) Ada動態(tài)分配/除配分配：new <TYPE>'(< 表達式 >)分配一 TYPE類型的對象，如果提供了可選表達式，對它求值并用以初始化該新對象， new是函數(shù)返回對

31、新對象的引用。該返回值程序員應(yīng)賦給ACCES類型變量(即指針)。除配：有無用單元回收，顯式除配一般不用，而是所在塊執(zhí)行完自動完成。 425.2死堆對象處理死堆對象叫無用單元或垃圾(garbage)。堆對象死亡是當(dāng)它引用的對象已失去定義(即出了創(chuàng)建該對象的塊)，我們稱這種死亡是自然死亡。強行用 (或類似)操作系統(tǒng)KILL命令也能顯 式使之死亡。自然死亡一般程序員和運算支持系統(tǒng)都是察覺不到的，不知不覺在一個未知的(地址)置入自由表。在語言中實現(xiàn)KILL并拿出大量地方留下垃圾。死堆對象往往不在堆的末端而在中間，簡單地KILL 命令在除配之后將該對象的引用 存儲以便追蹤，一直存在著很大的爭議。回收死堆

32、對象的存儲比堆存儲復(fù)雜得多。減少堆高指針是不行的。要把它們做成登錄可重分配存儲對象的自由表。效率高低全看自由表 的設(shè)計，曾經(jīng)有過以下三種辦法：忽略死對象，這種表當(dāng)然最容易實現(xiàn)。這看上去近乎胡來的策略還真有實現(xiàn)的，如 AOD-V礫作系統(tǒng)上（數(shù)據(jù)通用公司的MV800（機的P ascal，在其參考手冊中明文寫出 Dis pose命令 無其它操作。該操作系統(tǒng)是有虛存、頁式管理和分時的）。編譯實現(xiàn)者的哲學(xué)是：頁式管理若有浪費充其量不到一頁。如果一頁上的對象全都死了 操作系統(tǒng)就不會把這頁裝入內(nèi)存。事實上，當(dāng)存儲對象的創(chuàng)建時間、壽命大致相差不多時， 這種策略能工作得很好。否則浪費巨大。保持一個自由表它將所有

33、自由空間連接在一起。這樣，每個自由空間都要有幾個字節(jié) 記錄它的大小并指示鏈接（多數(shù)硬件是8個字節(jié)），小于此數(shù)的空間也只能放棄了。多數(shù)C,Pascal編譯版本采用這個方案。8字節(jié)的頭部說明是需要的：兩個指針以構(gòu)成雙向循環(huán)鏈表，一個字節(jié)指示該小塊是自由還是工作的。各小塊編排次序和內(nèi)存地址一致，這樣相鄰的小塊合 并就很方便了。死對象除配也很方便：只要把指示位設(shè)成“自由”。相鄰小塊都自由則合并。掃描到第一個自由區(qū)并接著找到足夠大的空間是很費事的，因為多數(shù)區(qū)域都在工作。故 掃描從正在工作的頂部開始，倒著來，如果額外增加一些記錄信息空間，掃描效率會高些。這 里有時、空互易問題。保持多個表按類型的長度，每種

34、長度一個表，表的元素可以交換，次序就不重要了。 這樣就不需要標識區(qū)域的開銷。歸并、重分配實現(xiàn)起來就容易得多。Ada即采用這種辦法。堆式管理除產(chǎn)生碎片之外仍有懸掛指針問題，其原因是當(dāng)有多個指針指向同一存儲對象 時，除配該存儲對象及其一個指針而忘掉消除所有指針，其它指針就是懸空（其實是指向無定義存儲）了。兩對象共享一數(shù)據(jù)結(jié)構(gòu)時更容易出現(xiàn)。因為一個死了一個活著，既要除配又不應(yīng) 除配，一除配就產(chǎn)生懸掛指針。而識別這種情況比較困難。因此，有人主張不要顯式的除配 （KILL）操作。P ascal的Dis pose備受攻擊，許多版本取消，并有返復(fù)。LIS P 語言就是自動處理重用死堆對象。沒有顯式KILL命

35、令，堆對象依然要死的，但存儲管理不知道什么時候死。它采用無用單元回收機制，每當(dāng)堆接近滿的時候，從頭檢查起，如果 是靜態(tài)的、堆棧分配的它就認為是活的，凡有一活對象指向的存儲也是活的。一律作上標記。 最后將無標記的存儲重新分配。盡管如此，程序員依然有義務(wù)刪除對不再需要的對象的引用（無用單元收集只解決最后全無用單元收集似乎是存儲管理部不用了的對象除配）。此外，無用單元收集費時低效。隨著存儲廉價可配備大內(nèi)存，就不致 于在一個程序運行期間多次運行它。隨著機器速度進一步提高， 有希望的出路。（Da ngli ng Referen ces），或懸掛指（KILL）時最容易產(chǎn)生。對于堆棧式管4.3懸掛引用指針指

36、向一個已死或無定義的對象，就稱為懸掛引用 針。程序設(shè)計語言采用堆式管理，同時提供顯式除配命令 理，如果外塊的指針指向內(nèi)塊的存儲對象時也會產(chǎn)生懸掛指針，因為當(dāng)內(nèi)塊執(zhí)行完除配，外塊 指針依然活著可用，它就指向無意義的單元的。懸掛指針是極為有害的。它甚至可以無緣無故地修改另一個程序。這對另一個程序是無 論如何也查不出的錯。-地址操作快速索引。&”運算符隨處使用。當(dāng)然也可以用到已除配的正因為如此，指向堆棧內(nèi) （即內(nèi)塊）的指針Pascal是不允許的。Pascal只限指針為堆對 象，構(gòu)造鏈表和樹數(shù)據(jù)結(jié)構(gòu)的指針都在堆中分配。簡單變量和數(shù)組在堆棧中分配，不提供地址 運算。因此，只能用下標處理數(shù)組，不能

37、用指針C 對指針的使用完全沒有限制。取地址“堆棧對象上。即使 C不許函數(shù)嵌套，主函數(shù)對函數(shù)的一層調(diào)用用堆棧實現(xiàn)時也會產(chǎn)生懸掛引 用，試看以下例題：例4-4懸掛引用(C)int * dan gle (int * ppp) int p=5;int m=21;*ppp=&p；return & mma in( ) int k =17int * pmpm = dan gle (&pk) /參數(shù)是指針的指針傳回的指向P的指針 返回m的地址,*pk=&k ；指向k/pk返回時pm pk均指向已失去定義的指針函數(shù) 局部量，即P和mmain()調(diào)用dangle后，堆棧中dangl

38、e所據(jù)空間可重新分配，而pm, pk指向其中的m,p就成了懸掛引用。當(dāng)然讀者會問，既然對指針如此自由使用，為什么不全由堆式管理實現(xiàn)呢？原因是堆?？蓪崿F(xiàn)高效的遞歸。C語言追求高效也支持遞歸，所以采用棧-堆結(jié)合的管理方式。只好把懸掛引用的問題留給程序員解決。C設(shè)計是為系統(tǒng)程序員用的，它的哲學(xué)是程序員不需要更多的限制。C本來就簡單，提供特征不多，限制多了會成為無用的小語言。函數(shù)抽象作為第一類值是另一個誘發(fā)懸掛引用的原因，請看以下示例：例4-5 假定Pascal將函數(shù)擴充成第一類對象var fv : Integer 宀 Boolean ；Real;:Integer) : Boolean ;p roce

39、dure P;var V1, V2 :fun ctio n f (mbegin V1 V2 end:=f第一類對象/begin fvend ;beginP ；Writel n(fv(0)endP 把局部函數(shù)抽象f賦給全局函數(shù)變量fv。執(zhí)行P后引用fv(O)時等于間接引用f(0)。然而，此時V1，V2均已失去定義，fv(0)的返回值成了懸掛引用。把局部函數(shù)值作為返回值產(chǎn)生的這類引用，在函數(shù)式語言把函數(shù)作為第一類值時懸掛引用尤其嚴重。所以 ML Miranda采用的方法是把所有變量作為堆變量處理，且不提供強行KILL指令。所以在程序塊啟動結(jié)束時，只要(直接或間接的)引用變量還存在，那么每個變量就繼

40、續(xù)有效。但存儲空間利用率就沒有堆棧式分配有效了。Algol68部分解決了懸掛引用問題：對引用賦值作些限制，弓I用局部變量不賦給比它生命長的變量。在對抽象的賦值方面也作了相應(yīng)限制。但實施這些限制是增加運行時的檢查。增加 了開銷。4.4變量更新有了變量的存儲我們接著討論這些存儲里的值如何更新。變量更新實則是把存儲看作一 自動機其中狀態(tài)（以共值表征）有了改變。存儲對象更新只有兩個途徑：賦值和初始化。也可以 用程序運行作界線劃分為靜態(tài)賦值（初始化）和動態(tài)賦值。4.4.1變量初始化變量分配了沒有定義就使用，是程序錯誤主要來源之一。為此早期曾有自動賦初值的做法，即分配了一律賦初值 0，或某個可區(qū)分的位模式

41、。事實證明，它不是個好辦法，不顯式賦 初值帶來查錯困難，再者除數(shù)值變量而外，其它類型初值約定也易產(chǎn)生誤解。變量顯式初始化由程序員在變量聲明中給出。許多語言都有初始化子句。以下舉出FORTRA和C兩個例子：1=1，8）/8.2 ，2.6，3.1，17.0，4* 0.0/'/'區(qū)分，先寫變量再寫初值，交替表示按位甚至可以寫出更復(fù)雜的嵌套循環(huán)。后面的值 n*表示。句中例4-6 FORTRAN初始化聲明 CHARACTER * 3 EOFLAG DIMENSION A（8） DATA EOFLAG ， ISUM/'NO '， 0/（A（I），ISUM偽隱含聲明的整變量。

42、FORTRAN賦初值在DATA語句中完成，用一對 置對應(yīng)，（A（I） ，I=1.8）是循環(huán)表達的數(shù)組元素， 是與元素出現(xiàn)次序一一對應(yīng)的，多個相同連續(xù)值用no例4-7 C的初始化聲明static char en d_of_file_flag =int isum=0；（第一行）的長度可由初始化值0。C稱后者為初始化符static float a8 = 8.2， 2.6， 3.1 ， 17.0；這是和上一個FORTRA例子一樣的初始化。C語言字符數(shù)組 表達式長度定。第三行只賦了半數(shù)初值，也按位對應(yīng)，其余自動為 （ini tializer），由字面量、常量、常量表達式構(gòu)成。表達式在編譯時求值。只要復(fù)合

43、變量中一個域（元素）初始化，所有域都要初始化。唯一的偷巧是自動為零。C 語言設(shè)計者認為FORTRA初始化，有不必要的靈活性。它們比FORTRA簡單直接。FORTRA有復(fù)雜的嵌套循環(huán)只能在裝載后運行前完成。另一個現(xiàn)代風(fēng)格初始化例子見前述例3-4?，F(xiàn)代語言支持堆棧式嵌套結(jié)構(gòu)的初始化（ANSI C，C+，Ada），即給自動變量初始化,在編譯和初裝時是無法完成的。因為這個堆棧框架還沒生成。于是由編譯算出表達式存在某個地方，并生成幾個裝載指令，待幀生成后裝入。老C版本是不支持這種自動數(shù)組初始化的。概念上還屬于靜態(tài)初始化。4.4.2動態(tài)更新賦值是以表達式的值強行置換存儲對象中的內(nèi)容。正因為如此，才有一個存

44、儲對象在不 同的時間代表不同的程序?qū)ο?，這是命令式語言造成語義復(fù)雜和混亂的根源。我們稱強行賦值 為破壞性賦值(Destructive Assignment) 。(1)簡單賦值與聚集賦值單個變量、數(shù)組元素、記錄成分值的改變即通過簡單賦值。它不涉及新值。只涉及兩個 對象：一個引用(在賦值號左邊),一個值或有值對象。多數(shù)語言只允許簡單賦值，初始化中靜 態(tài)聚集賦值我們已介紹過了。 之間。例如，ANSI C中有：typ edef struct int age person a , b = 10 a = b ;近代語言幾乎都擴充了動態(tài)聚集賦值。但僅限于同類型復(fù)合變量，70，/，weight ；'M

45、'；char sex ； person ;/b有初值，a沒有。動態(tài)聚集賦值，a也有了。READS程把待賦值變量作為返回參數(shù)也能實現(xiàn)賦值。此時REA實現(xiàn)一系列動作完成賦值，沒有返回值。在這個意義LIS P及所有函(2)通過函數(shù)賦值除了強行賦值之外，如果通過 引用作為參數(shù)，值由輸入介質(zhì)提供。 上，REA僅僅是過程，不是求值的函數(shù)。然而，真有一些語言賦值按函數(shù)實現(xiàn)。 數(shù)式語言，APL, C就采用函數(shù)賦值。例4-8 C語言賦值的函數(shù)實現(xiàn)#define MAXLENGTH 100float arMAXLENGTH ;int high_sub , num_elements ; high_sub=(

46、 nu m_eleme nts=MAXLENGTH)-1 ;最后一行'='號如同一般運算符是中綴函數(shù)名，前后兩個操作數(shù)是參數(shù)，它返回一個值(就是num_elements的值)。正因為如此，它可以出現(xiàn)在表達式之中。LISP的'賦值'函數(shù)是replaca , replacd，返回值是對參數(shù)的引用。以下將常見語言賦值實現(xiàn)列表如下：語言賦值號聚集賦值多重賦值實現(xiàn)機制COBOLADDDIVII FORTRAN ALGOL:P L/1=FORTH Pascal := Ada:=MOVE(在COMPUTE句中)SUBTRACT,MULT IPLY )E可 否 否否 否 可 否

47、 可 可可 可 可否 否 可 否 否 否語 句LIS PrepAPL C(1973)=)lace ,rep laced某些版本可 可 否返回結(jié)果 引用 值 值函 數(shù)ANSI C表4-1常見語言賦值的實現(xiàn)機制其中多重賦值指形如a=b=c=3.0的連接賦值。C語言是允許的。既然函數(shù)可以動態(tài)地改變值，則函數(shù)式語言每當(dāng)有破壞性賦值時就用參數(shù)束定的函數(shù)調(diào) 用替代。每當(dāng)要把一個計算值存入變量時，函數(shù)式語言則把該值作為參數(shù)傳遞給函數(shù)。賦值例 程(或函數(shù))體內(nèi)的動作繼續(xù)以嵌套函數(shù)實現(xiàn)，這樣就避免了變量。參數(shù)束定在一個例程入口和 出口的語義是不變的。因而是可以得到語義清晰的語言。4.5有副作用的表達式我們把賦值

48、V: =E稱之為賦值命令(也就是語句)，它對表達式E求值，并以該值強行更 新V中的原有值。一般表達式在求值過程中是不會更新其中操作數(shù)的值的，它只引用各操作數(shù) 的值。它更新的是賦值號左邊的值。如果E是一個復(fù)合的表達式會怎樣呢？例如，其中一個子表達式是函數(shù)引用，在對E求值時必然要將此函數(shù)執(zhí)行一遍。函數(shù)體中顯然又有許多聲明和賦值語句，因此，除了求出函數(shù)返回值之外，其中的賦值語句更新了函數(shù)體中的變量。也就是除 了求函數(shù)值的主要作用而外，也起了更新變量的副作用(side effect)。如果只更新了函數(shù)局部變量，下次求該函數(shù)值時并沒有影響，如果更新了全局變量，就會影響到其它表達式求值， 這就難于控制了。

49、4.5.1塊表達式塊(Block)是嵌套在程序中的局部程序，由封閉的聲明和語句集組成。如果表達式包含的 子表達式是一個聲明或定義，該表達式即為塊表達式。前述函數(shù)引用是隱式的塊表達式，函數(shù) 體中既有聲明又有語句。如果該函數(shù)沒有副作用則與變量引用無異，如果有則以塊表達式看 待。有些語言具有顯式塊表達式，如ML例4-9 已知三角形三邊a，b，c的長度求三角形的面積：let val s = (a+b+c)*0.5in sqrt(s*(s-a)*(s-b)*(s-c)end抽象形式是let D in E end ，其中D是說明E的表達式，一起叫塊表達式。D的作用僅限于說明E。，C語言有顯式的命令4.5.

50、2命令表達式如果沒有聲明，塊中只有命令，嵌入到表達式中則為命令表達式 表達式：例4-10 C語言讀字符常見的表達式(c=getchar( )!=EOF該表達式求真值，若 C中讀入是EOF本表達式求值為0(假)。其它字符時值為1(真)。子表達式 c=getchar() 是賦值命令。故本表達式是 (嵌入了)命令(的)表達式。這個getchar() 肯定是有副作用的。因為兩次同樣無參調(diào)用可得出不同的字符。從當(dāng)前讀的位置移到下一個字符位置就是副作用，但這個副作用正是C程序員希望的。塊表達式和命令表達式都是具有副作用的表達式，我們擴充它們無非是希望它的副作用 能增強表達能力，事實上有了它們程序清晰可讀，

51、如上面的例子。ML沒有全局量不會有什么壞的副作用。C語言就靠程序員保證了。4.6小結(jié)程序變量具有時、空特性，故引入存儲對象概念。它既是程序?qū)ο蟮膶崿F(xiàn)又是獨立的 存儲體。變量名字編譯后成為地址碼，將此碼存放在存儲對象中，該存儲對象對應(yīng)的程序?qū)ο?叫引用(C+)，引用變量是該變量的別名。指針可以存放任何程序?qū)ο蟮牡刂罚沙绦騿T操 縱。通過指針變量引用程序?qū)ο蟮闹到羞f引用。變量有分配、未分配、除分配，定義、未定義、失去定義的因時而變的狀態(tài)。存儲模型有兩大類：靜態(tài)存儲和動態(tài)存儲。靜態(tài)存儲在運行前分配變量的存儲，動態(tài) 存儲在運行中分配和除配。動態(tài)存儲模型又分兩類：堆存儲和堆棧存儲。堆棧存貯，堆存貯模型是

52、單今多數(shù)模塊語言模型。存儲對象是有其生命周期的。一般局限于生成該存儲對象所在模塊的生命期。程序員 可顯式控制存儲對象的生命期，在一模塊內(nèi)使用多生命期對象，以程序運行周期為準，大于此 周期為持久變量，等于為全局，小于為局部，局部尚可內(nèi)嵌局部。除持久對象外其余隨程序運 行終止而銷毀，均為臨時的。靜態(tài)存儲對象一般由編譯分配后在整個程序執(zhí)行期間不會改變。全局的、外部的變量 均靜態(tài)對象。也有語言將局部變量定為靜態(tài)的。動態(tài)存儲對象往往取決于輸入值和程序執(zhí)行情況無法在編譯時確定所需存儲，只能動 態(tài)分配/除配。堆棧式管理和程序模塊執(zhí)行自然相適應(yīng)，且天然支持遞歸，高效。堆式管理自由方便，存儲利用相對耗費大。多數(shù)

53、語言是兩者相結(jié)合。指針對象一般是堆對象。顯式除配操作易引起懸掛指針，外塊指針指向內(nèi)塊對象也易引起懸掛。懸掛指針是程 序出錯根源之一。一般認為命令式語言有三大害：任意的goto語句、懸掛指針、函數(shù)副作用，本章涉及一個半。函數(shù)副作用第 6章還要講。程序中變量更新只有兩個途徑 ：賦值和初始化。賦值通過賦值命令或調(diào)用讀例程。調(diào)用 例程或函數(shù)是避免破壞性賦值重要途徑。是函數(shù)式語言得以發(fā)展的原因。當(dāng)今語言賦值有按賦值命令模型有按函數(shù)調(diào)用模型。C語言按函數(shù)模型故有賦值命令出現(xiàn)在表達式中的命令表達式。如果一個程序塊(分程序)嵌入在表達式中則稱塊表達式。函數(shù)體是塊表達式，嵌有函 數(shù)引用的表達式是隱式塊表達式，M

54、L有顯式塊表達式。如果塊中只有命令沒有聲明即為命令表達式。擴充它們是為了擴大表達能力，但也會 帶來副作用，故稱有副作用的表達式。好的函數(shù)副作用使程序簡單清晰，一旦放開了函數(shù)副作用又易產(chǎn)生難調(diào)易出錯問題。 這取決于語言設(shè)計的宗旨。但目前所有命令式語言都有一定程度的的函數(shù)副作用。習(xí)題4.1 一般變量和指針變量有何不同？引用類型變量與它們又有何不同？答：在尋址對照表中，一般變量對應(yīng)的地址碼即為該變量值的存儲單元，而指針變量 對應(yīng)的地址碼則為該指針所指向的存儲單元的地址。引用型變量與指針變量的區(qū)別在于它是常指針，一旦對照表建立，也就創(chuàng)建了引用， 不可改變。引用是變量的別名，但它必須賦初值。4.2 C語

55、言中數(shù)組名的含義是什么，當(dāng)把數(shù)組的地址賦給某指針時是否要用算符，為什么答：C語言中的數(shù)組名可以看作是一個指針變量名，它代表數(shù)組元素的首地址。但其值 不可改變，這一點與引用型變量有些類似。當(dāng)把數(shù)組的地址賦給某指針時不用運算符，因為數(shù) 組名本身就是指向數(shù)組首地址的指針。?哪些動態(tài)實現(xiàn)？4.3 現(xiàn)今語言有靜態(tài)數(shù)組、動態(tài)定義數(shù)組、可變長靈活數(shù)組，試說出它們的定義，并舉 出哪種語言采用它的例子 （一個語言也行）。4.4 找一個你所熟悉的語言所寫的程序，指出哪些變量應(yīng)用靜態(tài)實現(xiàn) 該語言真是這樣的嗎？4.5 試總結(jié)存儲對象生命期有哪幾種，C語言與此對應(yīng)各叫什么變量4.6 何謂運行時堆棧？堆棧幀？堆？答：運行時堆棧是在內(nèi)存開辟一個空間，如同堆棧。首先將程序代碼和全局靜態(tài)變量裝 入。在執(zhí)行控制開始時首先