PL真有意思（三）：名字、作用域和約束
前言
這兩篇寫了詞法分析和語法分析，比較偏向實踐。這一篇來看一下語言設計里一個比較重要的部分：名字。在大部分語言里，名字就是標識符，如果從抽象層面來看名字就是對更低一級的內存之類的概念的一層抽象。但是名字還有其它相關的比如它的約束時間和生存周期等等
約束時間
約束就是兩個東西之間的一種關聯，例如一個名字和它所命名的事物，約束時間就是指創建約束的時間。有關的約束可以在許多不同的時間作出
- 語言設計時
- 語言實現時
- 編寫程序時
- 編譯時
- 鏈接時
- 裝入時
- 運行時
這就是為什麼基於編譯的語言實現通常會比基於解釋器的語言的實現更高效的原因，因為基於編譯的語言在更早的時候就做了約束，比如對於全局變量在編譯時就已經確定了它在內存中的布局了
對象生存期和存儲管理
在名字和它們所引用的對象的約束之間有幾個關鍵事件：
- 對象的創建
- 約束的創建
- 對變量、子程序、類型等的引用，所有這些都使用了約束
- 對可能暫時無法使用的約束進行失活或者重新約束
- 約束的撤銷
- 對象的撤銷
對象的生存期和存儲分配機制有關
- 靜態對象被賦予一個絕對地址，這個地址在程序的整個執行過程中都保持不變
- 棧對象按照後進先出的方式分配和釋放，通常與子程序的調用和退出同時進行
- 堆對象可以在任意時刻分配或者釋放，它們要求更通用的存儲管理算法
靜態分配
全局變量是靜態對象最顯而易見的例子，還有構成程序的機器語言翻譯結果的那些指令，也可以看作是靜態分配對象。
還有像每次調用函數都會保持相同的值的局部變量也是靜態分配的。對於數值和字符串這些常量也是靜態分配。
還有用來支持運行時的各種程序，比如廢料收集和異常處理等等也可以看作是靜態分配
基於棧的分配
如果一種語言允許遞歸，那麼局部變量就不能使用靜態分配的方式了，因為在同一時刻，一個局部變量存在的實例個數是不確定的
所以一般對於子程序，都用棧來保存它相關的變量信息。在運行時，一個子程序的每個實例都在棧中有一個相應的棧幀，保存着它的參數、返回值、局部變量和一些簿記信息
基於堆的分配
堆是一塊存儲區域，其中的子存儲塊可以在任意時間分配與釋放。因為堆具有它的動態性，所以就需要對堆空間進行嚴格的管理。許多存儲管理算法都維護着堆中當前尚未使用的存儲塊的一個鏈接表，稱為自由表。
初始時這個表只有一個塊，就是整個堆，每當遇到分配請求時，算法就在表中查找一個大小適當的塊。所以當請求次數增多，就會出現碎片問題，也需要相應的解決
所以有廢料收集的語言其實就是對堆的管理
作用域作用
一個約束起作用的那一段程序正文區域，稱為這個約束的作用域。
現在大多數語言使用的都是靜態作用域，也就是在編譯時就確定了。也有少數語言使用動態作用域，它們的約束需要等到運行時的執行流才能確定
靜態作用域
在使用靜態作用域的語言，也叫作詞法作用域。一般當前的約束就是程序中包圍着一個給定點的最近的，其中有與該名字匹配的聲明的那個快中建立的那個約束。比如C語言在進入子程序時，如果局部變量和全局變量，那麼當前的約束就是與局部變量關聯，直到退齣子程序才撤銷這個約束
但是有的語言提供了一種可以提供約束的生存期的機制，比如Fortran的save和C的static
嵌套子程序
有許多語言允許一個子程序嵌套在另一個子程序的。這樣有關約束的定義通常來說都是首先用這個名字在當前、最內層的作用域中查找相應的聲明，如果找不到就直接到更外圍的作用域查找當前的約束，直到到達全局作用域，否則就發生一個錯誤
訪問非局部變量
上面提到的訪問外圍作用域的變量，但是當前子程序只能訪問到當前的棧幀，所以就需要一個調用幀鏈來讓當前的作用域訪問到外圍作用，通過調用順序形成一個靜態鏈
聲明的順序
關於約束還有一個問題，就是在同一作用域里，先聲明的名字是否能使用在此之後的聲明
在Pascal里有這樣兩條規則：
- 修改變量要求名字在使用之前就進行聲明
- 但是當前聲明的作用域是整個程序塊
所以在這兩個的相互作用下，會造成一個讓人吃驚的問題
const N = 10;
procedure foo;
const
M = N; (*靜態語義錯誤*)
N = 20;但是在C、C++和Java等語言就不會出現這個問題，它們都規定標識符的作用域不是整個塊，而是從其聲明到塊結束的那一部分
並且C++和Java還進一步放寬了規則，免除了使用之前必須聲明的要求
模塊
恰當模塊化的代碼可以減少程序員的思維負擔，因為它最大限度的減少了理解系統的任意給定部分時所需的信息量。在設計良好的程序中，模塊之間的接口應盡可能的小，所有可能改變的設計決策都隱藏在某個模塊里。
模塊作為抽象
模塊可以將一組對象（如子程序、變量、類型）封裝起來。使得：
- 這些內部的對象相互可見
- 但是外部對象和內部對象，除非显示的導入，否則都是不可見的
模塊作為管理器
模塊使我們很容易的創建各種抽象，但是如果需要多個棧的實例，那麼就需要一個讓模塊成為一個類型的管理器。這種管理器組織方式一般都是要求在模塊中增加創建/初始化函數，並給每一個函數增加一個用於描述被操作的實例
模塊類型
對於像這種多實例的問題，除了管理器，在許多語言里的解決方法都是可以將模塊看作是類型。當模塊是類型的時候，就可以將當前的方法認為是屬於這個類型的，簡單來說就是調用方法變化了
push(A, x) -> A.push(x)
本質上的實現區別不大
面向對象
在更面向對象里的方法里，可以把類看作是一種擴充了一種繼承機制的模塊類型。繼承機制鼓勵其中所有操作都被看作是從屬於對象的，並且新的對象可以從現有對象繼承大部分的操作，而不需要為這些操作重寫代碼。
類的概念最早應該是起源於Simula-67，像後來的C++，Java和C#中的類的思想也都起源於它。類也是像Python和Ruby這些腳本語言的核心概念
從模塊到模塊類型再到類都是有其思想基礎，但是最初都是為了更好的數據抽象。但是即使有了類也不能完全取代模塊，所以許多語言都提供了面向對象和模塊的機制
動態作用域
在使用動態作用域的語言中，名字與對象間的約束依賴於運行時的控制流，特別是依賴子程序的調用順序
n : integer
procedure first
n := 1
procedure second
n : integer
first()
n := 2
if read_integer() > 0
second()
else
first()
write_integer()這裏最後的輸出結果完全取決於read_integer讀入的数字的正負，如果為正，輸出就為2，否則就打印一個1
作用域的實現
為了跟蹤靜態作用域程序中的哥哥名字，編譯器需要依靠一個叫做符號表的數據結構。從本質上看，符號表就是一個記錄名字和它已知信息的映射關係的字典，但是由於作用域規則，所以還需要更強大的數據結構。像之前那個寫編譯器系列的符號表就是使用哈希表加上同一層作用域鏈表來實現的
而對於動態作用域來說就需要在運行時執行一些操作
作用域中名字的含義
別名
在基於指針的數據結構使用別名是很自然的情況，但是使用別名可能會導致編譯器難以優化或者造成像懸空引用的問題，所以需要謹慎使用
重載
在大多數語言中都或多或少的提供了重載機制，比如C語言中（+）可以被用在整數類型也可以用在浮點數類型，還有Java中的String類型也支持(+)運算髮
要在編譯器的符號表中處理重載問題，就需要安排查找程序根據當前的上下文環境返回一個有意義的符號
比如C++、Java和C#中的類方法重載都可以根據當前的參數類型和數量來判斷使用哪個符號
內部運算符的重載
C++、C#和Haskell都支持用戶定義的類型重載內部的算術運算符，在C++和C#的內部實現中通常是將A+B看作是operator+(A, B)的語法糖
多態性
對於名字，除了重載還有兩個重要的概念：強制和多態。這三個概念都用於在某些環境中將不同類型的參數傳給一個特定名字的子程序
強制是編譯器為了滿足外圍環境要求，自動將某類型轉換為另一類型的值的操作
所以在C中，定義一個計算整數或者浮點數兩個值中的最小值的函數
double min(double x, double y);只要浮點數至少有整數那麼多有效二進制位，那麼結果就一定會是正確的。因為編譯器會對int類型強制轉換為double類型
這是強制提供的方法，但是多態性提供的是，它使同一個子程序可以不加轉換的接受多種類型的參數。要使這個概念有意義，那麼這多種類型肯定要具有共同的特性
顯式的參數多態性就叫做泛型，像Ada、C++、Clu、Java和C#都支持泛型機制，像剛才的例子就可以在Ada中用泛型來實現
generic
type T is private;
with function "<" (x, y : T) return Boolean;
function min(x, y : T) return T;
function min(x, y : T) return T is
begin
if x < y then return x;
else return y;
end if;
end min
function string_min is new min(string, "<")
function date_min is new min(date, date_precedes);像List和ML中就可以直接寫
(define min (lambda (a b) (if (< a b) a b)))其中有關類型的任何細節都由解釋器處理
引用環境的約束
提到引用環境的約束就有兩種方式：淺約束和深約束
推遲到調用時建立約束的方式淺約束。一般動態作用域的語言默認是淺約束，當然動態作用域和深約束也是可以組合到一起的。
執行時依然使用傳遞時的引用環境，而非執行時的引用環境。那麼這種規則稱為深約束，一般靜態作用域的語言默認是深約束
閉包
為了實現神約束，需要創建引用環境的一種顯示錶示形式，並將它與對有關子程序的引用捆綁在一起，這樣的捆綁叫做閉包
總而言之，如果子程序可以被當作參數傳遞，那麼它的引用環境一樣也會被傳遞過去
一級值和非受限生存期
一般而言，在語言中，如果一個值可以賦值給變量、可以當作參數傳遞、可以從子程序返回，那麼它被稱為具有一級狀態（和我們在js中說函數是一等公民一個含義）。大多數的語言中數據對象都是一級狀態。二級狀態是只能當作參數傳遞；三級值則是連參數也不能做，比如C#中一些+-*/等符號。
在一級子程序會出現一個複雜性，就是它的生存期可能持續到這個子程序的作用域的執行期外。為了避免這一問題，大部分函數式語言都表示局部變量具有非受限的生命周期，它們的生命周期無限延長，直到GC能證明這些對象再也不使用了才會撤銷。那麼不撤銷帶來的問題就是這些子程序的存儲分配基於棧幀是不行了，只能是基於堆來分配管理。為了維持能基於棧的分配，有些語言會限制一級子程序的能力，比如C++，C#，都是不允許子程序嵌套，也就從根本上不會存在閉包帶來的懸空引用問題。
小結
這一篇從名字入手，介紹了名字與其背後的對象的約束關係、以及約束時間的概念；然後介紹了對象的分配策咯（靜態、棧、堆）；緊接着討論了名字與對象之間建立的約束的生命周期，並由此引出了作用域的概念；進一步延伸出多個約束組成的引用環境的相關概念以及問題。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享
※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選
