PL真有意思（四）：控制流

Posted on 2020-01-102020-01-10 by admin

前言

對大多數計算模型而言，順序都是基本的東西，它確定了為完成所期望的某種工作，什麼事情應該最先做，什麼事應該隨後做，我們可以將語言規定順序的機制分為幾個類別：

順序執行
選擇
迭代
過程抽象
遞歸
併發
異常處理和推斷
非確定性

對於不同類別的語言對不同類別的控制流的重要性也不盡相同，比如順序執行相比於函數式對於命令式則更加重要。而命令式中更傾向用迭代，函數則更強調遞歸

表達式求值

在討論控制流之前先討論下錶達式的問題，先明確兩個概念：運算符通常是指那些採用特殊語法形式的內部函數（比如+-*/等），運算對象指的是運算符的參數（如2+3，2和3就是運算對象），那麼運算符和運算對象的組合就是表達式。一般根據運算符出現的位置（相對於運算對象而言），可以分為3類表示形式：前綴、中綴和後綴。比如Lisp就運用前綴語法：

(+ 1 3 4 6)      
(* (+ 1 7) 8)

大多數命令式語言對二元運算符都使用中綴記法，而對一元運算符和其它函數使用前綴激發。但是像Lisp就全部統一使用中綴記法

優先級和結合性

大多數程序設計語言都提供豐富的內部算術。在用中綴方式（沒有括號）寫出就可能出現歧義。所以就需要優先級和結合性來解決歧義性，但是我覺得

媽的你寫括號就完事兒了

而且不同語言的優先級和結合性也不盡相同

賦值

在純函數式語言中，程序的基本組成部分是表達式，計算也僅是對表達式求值。任何一個表達式對於整個計算的影響也僅限於這個表達式所處的上下文環境。

而命令式語言的情況與此截然不同，計算通常是通過對內存中變量值的一系列修改操作來完成，賦值就是這種修改的最基本手段。每一次賦值都表示一個值被放入一個對應的變量中。

一般來說，如果語言中的一個結構除了返回一個值供其外圍環境所使用，還能以其他方式影響後續計算(並最終影響程序輸出)，那麼我們就說這種結構有副作用。而副作用也是命令式語言里最核心的部分

而在純函數語言中沒有任何的副作用，表達式的值只依賴於輸入

但是現在許多語言都是混合的，像Python和Ruby主要是命令式的，但是也提供了很多的函數式的特徵，現在連Java都提供了對函數式的支持

引用和值

考慮一下下面的C語言的賦值：

d = a;
a = b + c;

第一個語句中，賦值語句右部引用了a的值，並希望把這個值放入d。第二個語句左部引用了a的位置，希望把b+c的結果放進去。這兩種解釋(值和位置)都是可行的，因為c語言中變量就是能保存值的命名容器，所以我們會說類似的語言的變量是值模型。由於指示位置的表達式被放在賦值語句的左部，所以這種指示位置的表達式成為左值表達式。表示一個值的表達式稱為右值。在變量的值模型下，同一表達式也可能是左值或者右值，比如(a=a+1)，左部的a是左值，用於表示存放結果的位置；右部的a是右值，用於代表a具體所指的值。

在採用了變量的引用模型的語言中，這種左值和右值的差異就更加明顯了。

b = 2;
c = b;
a = b + c;

在值模型語言中程序員會說：“把2放入b，然後複製到c，然後用它們兩個的值相加，把結果4放入a。”。;

在引用模型語言中的程序員會說：“讓b引用2，讓c也引用2，然後把這兩個引用送給+運算，並讓a引用算出的結果，也是4“。

而在Java中，對於內部類型使用值模型，而類使用引用模型

裝箱

對於內部類型使用值模型，就無法以統一的方式將它們傳給要求類類型的參數的方法，所以這裏就需要一個裝箱過程

比如Java提供的Integer類

Integer i = new Integer(12);

多路賦值

我們知道賦值操作有右結合性，這使得我們可以寫出a=b=c的簡練代碼，在一些語言中(Ruby，Go，Python)我們可以進一步這樣寫：

a, b = 1, 2;
//上面的語句結果就是a等於1，b等於2。

a, b = b, a;
//交換兩個值，如果沒有這種語言特性，那麼就需要引入臨時變量了。

a, b , c = funx(d, e, f);

這種記法也消除了大多數程序設計語言中函數的非對稱性，這些語言可以允許任意多個參數，但只能返回一個返回值。但是其實在Python中的返回多個值，就是將多個值封裝為元組，在賦值的時候又拆箱而已

初始化

並不是所有語言都提供聲明變量時指定初始值的方式，但是至少有這幾點可以證明提供初始值的機制是有益的

局部靜態變量需要一個初始值才能使用
使用靜態分配的變量，可以由編譯器放入全局內存，避免了在運行時賦予吃數值所造成的開銷
可以避免意外的使用未初始的變量

如果聲明時沒有明確的給定變量的初始值，語言也可以給定一個默認值。像C、Java和C#也都提供了類似的機制

動態檢查

除了可以指定默認值之外，還可以採用另外一種方式，將對為初始化的變量的使用作為動態語義錯誤，在運行時捕獲這種錯誤。但是在運行時捕獲所有使用到未初始化的情況的代價非常高

定義性賦值

在Java和C#中提供了一種定義性賦值的表示形式，意思就是由編譯器來檢查在達到一個表達式的所有可能控制路徑上，都必須為這個表達式中的每個變量賦過值

構造函數

許多面向對象語言都提供了為用戶定義的類型的自動初始化方法，也就是構造函數

在C++中，還區分了初始化和賦值，它將初始化賦值解釋為調用變量所屬類型的構造函數，以初始值作為調用參數。在沒有強制的情況下，賦值被解釋為調用相關類型的賦值運算符，如果沒有定義賦值運算符，就默認將賦值右部的值簡單的按位複製過來

區分初始化和賦值的好處是，可以區分在賦值前是不是需要先釋放空間

表達式的順序問題

雖然優先級和結合性規則定義了表達式里二元中綴運算符的應用順序，但卻沒有明確說明特定運算符的各運算對象的求值順序。舉例來說，如下錶達式：

 a - f(b) - c * d

根據結合性可知a-f(b)將在第二個減法前執行，根據優先級可知第二個減法的右運算對象是cd這個整體而不是c。但是如果沒有進一步的規則描述，我們無法得知a-f(b)是否在cd之前運行。諸如此類：對於f(a,g(b),c)這個子程序調用，我們也不知這三個參數的求值順序。

求值順序之所以重要：

副作用：如果f(b)這個子程序可能會修改c的值，那麼a-f(b)-cd的求值結果將依賴f(b)和cd哪一個先執行；類似的，如果g(b)修改了a或者c的值，那麼f(a,g(b),c)的結果也是依賴於參數的求值順序。
代碼改進：子表達式的求值順序對於寄存器分配和指令調度都有重要的影響。比如（ab+f(c)），我們可能會希望在執行ab之前調用f(c)。因為如果先計算乘法，則在調用f(c)之前就要先保存起來乘積，因為f(c)可能會用光所有的寄存器。

短路求值

對於布爾表達式，如果編譯器可以對其執行短路求值，那麼它生成的代碼可以在表達式前一半的結果可以確定整個表達式的值的情況下跳過後一半的計算。

比如(a<b) and(b<c)，如果a>b，那麼完全沒必要去檢查b是否小於c就可以確定這個表達式一定為假。在一些特殊情況下，短路求值可節省大量時間，比如if(func&&func())。實際上這種情況下短路求值已經改變了布爾表達式的語義，如果非短路求值，那麼在func不存在的情況下去執行func()，程序是會拋出錯誤的。

我們常見的語法表現形式是&&和||這種布爾運算符身兼多職，既是布爾運算符又會觸發短路求值，但是有一些語言針對短路求值是有單獨的語法形式的，比如Clu語言中布爾運算符是and和or,短路運算符是cand和cor。這是為何呢，因為有些代碼邏輯是不需要這種短路求值的優化的。

結構化和非結構化的流程

彙編語言中的控制流通過有條件的或無條件的跳轉（分支）指令來完成，早期的高級語言模仿這種方式（如Fortran），主要依賴goto來描述大部分非過程化控制流，比如下面代碼：

if A < B goto label1;

label1;

但是如今goto像在Java、Clu和Eiffel里已經完全被禁止了，在其它語言也是受限了或者只是為了向前兼容而已

goto的結構化替代品

對於goto被廢棄，各種使用goto的地方也被結構的方案給代替了

循環中的退出和繼續

break和contiune這兩個關鍵字大家應該很熟悉了

從子程序提前返回

return

多層返回

上面的兩個問題都可以有很好的替代品，但是對於多層返回就會比較麻煩一點。return或”局部的goto“只能在子程序中返回,如果遇到多層嵌套的子程序，想從內層的子程序返回來結束外圍子程序的執行，那return和局部的goto就無能為力了。這種情況下，語言實現要保證能恰當的恢復棧上的子程序調用信息，這種修復工作稱為”回卷”，為完成此事，不僅必須釋放需要跳出的所有子程序的棧幀，還要執行一些信息管理工作，比如恢復寄存器內容。

Common Lisp提供了return-from語句來明確指定需要退出的詞法外圍函數或嵌套塊，還可以提供一個返回值：

Common Lisp和另外一個語言Ruby中還內置一個throw/catch語法來支持這種多層返回，注意這種結構並不是所謂的異常處理，而是一種多層返回的語法結構，直白點說是一種功能強大的變相”goto“，看下面代碼：

//定義一個方法
def search_file(filename,pattern)
   file=File.Open(filename)
   //遍歷文件每一行
   file.each{|line|
        //根據parrern匹配模式查找，如果匹配就返回到定義found標籤的位置
        throw :found,line if line=~/#{pattern}/
   }
end

//用catch定義一個found標籤
math=catch:found do
   serach_file("f1",key) 
   serach_file("f2",key)    //如果f2文件找到了則就會返回line至math
   serach_file("f3",key)
   ”not fount“              //找不到就執行到此處了
end

print match

錯誤和異常

多層返回的概念假定了被調用方知道調用方期的是什麼，並且能返回一個適當的值。還存在一種情況，其中深層嵌套的子程序中發生了一些情況，導致無法繼續執行下去，而且因為沒有足夠的環境信息，甚至無法合適的結束自己的工作，這種情況下，唯一能做的就是”退回去“，一直回退到能夠恢復執行的地方，這種要求程序退回去的條件通常稱為叫做”異常“。常見的結構化的異常處理和多層返回有很大的相似性，兩者都需要從某一個內層上下文回退到外層的上下文。具體的差異則是多層返回是內層的上下文正常的完成計算然後根據需要返回正確的值，然後轉移到外層上下文，並不需要後續處理。而異常中的內層上下文已經是無法進行正常的計算，必須以一種非正常的退出一直回卷，然後觸發某個特殊的處理流程直到catch到它。

繼續

如果進一步推廣上一小節中造成棧回卷的非局部goto概念，則可以定義一種稱為繼續（Continuations）的概念。從底層來看，一個繼續是由一個代碼地址與其關聯的一個引用環境組成的，如果跳轉到這個地址，就該恢復這個引用環境。從抽象層面看，它描述一個可能由此繼續下去的執行上下文。在Scheme和Ruby中，繼續是基本的一等公民，我們可以利用這種機制有效的擴充流程控制結構集合。

Scheme中支持繼續由一個通常稱為call-with-current-continuation的函數實現，有時簡稱”call/cc”。該函數有一個參數f,f也是一個函數；”call/cc”調用函數f,把一個記錄著當前程序計數器和引用環境的“繼續（暫時稱為是c）c”傳遞給f，這種”繼續c”由一個閉包來表示（通過參數傳遞的子程序的表示的閉包並無不同）。在將來任何時候，f都可以調用c,然後可以用c來重新建立其保存的上下文。一般的應用情況是我們把這個c賦值給一個變量，則可重複的調用它，甚至我們可以在f中返回它，即使f已經執行完畢，仍然可以調用c。

順序執行

選擇

現在大部分命令式語言中採用的選擇語句，都是從Algol 60引進過的 if…then…else 的某種演進變形：

if condition then statement
else if condition then statement
else if condition then statement
...
else statement

短路條件

雖然 if…then…else 語句的條件是一個布爾表達式，但是通常沒有必要求出這個表達式的值放入寄存器。大部分機器都提供了條件分支指令（如上面提到的IL指令brtrue.s），因為這個表達式求值的目的並不是為了值，而是為了跳轉到合適的位置。這種看法使得可以對短路求值的表達式生成高效的代碼（稱為跳轉碼）。跳轉碼不但可以用於選擇語句，也可用在“邏輯控制的循環”中。如下面代碼：

if((A>B)&&(C<D)||(E!=F)){
    then_clause
}
else{
    else_clause
}

在不使用短路求值的Pascal中，生成的代碼大致如下(它會計算每個表達式的結果並放入寄存器r1…，然後再決定跳轉)：

     r1=A
     r2=B
     r1=r1>r2
     r2=C
     r3=D
     r2=r2>r3
     r1=r1&r2
     r2=E
     r3=F
     r2=r2!=r3
     r1=r1|r2
     if r1=0 goto L2
L1: then_clause
    goto L3
L2: else_clause
L3:

跳轉碼的情況於此不同，它不會把表達式的值存入寄存器，而是直接跳轉(只用到了r1和r2兩個寄存器，明顯也不會針對整個表達式進行求值，比上面的要高效一些)：

     r1=A
     r2=B
     if r1<=r2 goto L4
     r1=C
     r2=D
     if r1>r2 goto L1
L4: r1=E
     r2=F
     if r1=r2 goto L2
L1: then_clause
    goto L3
L2: else_clause
L3:

case/switch語句

對於if else結構來說，如果嵌套的層數過多、或者是用於判斷的條件表達式是基於一些有限的簡單值（或編譯時常量），那麼出現了一種更為優雅的語法結構“case語句”，有很多ifelse都可以很輕鬆的改寫成case/switch語句

對於case/switch的優勢還不只是語法上的優雅，有時還可以生成更高效的代碼

T: &L1
   &L2
   &L3
   &L4
   &L5
   &L6
L1: clause_A
    goto L7
L2: clause_B
    goto L7
L3: clause_C
    goto L7
L4: clause_D
    goto L7
L5: clause_E
    goto L7
L6: clause_F
    goto L7
L7:

這樣其實T就是一個地址跳轉表

迭代

迭代和遞歸是計算機能夠重複執行一些操作的兩種機制；命令式語言傾向於使用迭代、函數式語言則更看重遞歸。大多數語言中的迭代都是以循環的形式出現的，和複合語句中的語句一樣，迭代的執行通常也是為了副作用，也就是修改一些變量的值。根據用何種方式控制迭代的次數來看，循環有兩個主要變種”枚舉控制的循環”和“邏輯控制的循環”。前者是在給定的某個有限的集合中執行，後者則是不確定要執行多少次（直到它所依賴的表達式結果被改變）。對於這兩種結構，大多數的語言都提供了不同的語法結構來表示。

枚舉控制的循環

枚舉控制的循環最初來自Fortran的do循環，

do i = 1, 10, 2
  ...
enddo

等號後面的表達式分別是i的初始值，邊界值和步長

像這種枚舉循環可以說的不多，但是如果前幾次迭代的執行會導致迭代的次數或下標值的發生變化，那麼我們就需要一個更通用的實現

思考幾個問題：

控制是否可以通過枚舉之外的任何方式進入和離開循環呢？
如果循環體修改了用於計算循環結束邊界的變量，會發生什麼？
如果循環體修改了下標變量，會發生？
程序是否可以在循環結束後讀取下標變量，如果可以，它的值將是什麼？

現在的大多數語言都提供了，break類似的機制來離開循環。Fortran IV允許通過goto跳入到一個循環中，但是這個通常被認為是一個語言缺陷
同樣的，在大多數語言中，邊界值只在第一次計算，並且保存在一個臨時寄存器中，所以對於之後的修改並不會起作用
早期的大部分語言都禁止在枚舉控制的循環中修改下邊變量。但是剛剛試驗了一下，許多的語言好像都放開了這個禁止，也就是按照修改后的正常邏輯繼續執行
首先這是一個語言實現的問題，現在的大多數語言應該都是將循環下標的作用域限定在循環體內了，所以出了循環體是訪問不到的

當然在之後出現了C的for循環

for (int i = first; i < last; i += step) {
  ...
}

這樣有關結束條件、溢出和循環方向的問題全都交由程序員來掌控

迭代器

上面描述的循環都是在算術值的序列上迭代。不過一般而言，我們還希望可以在任何定義的良好的集合的元素上迭代。在C++和Java里叫做迭代器

真迭代器

Clu，Ruby等語言允許任何容器對象提供一個枚舉自己元素的迭代器，這種迭代器就像是允許包含yield語句的子程序，每次yield生成一個循環下標

在Python里就可以這樣寫

for i in range(first, last, step):
    ...

在被調用時，這個迭代器算出循環的第一個下標值，然後通過yield語句返回給調用者，yield語句很像return，但是不同的是再每次循環結束后控制權會再次的交給迭代器，重新開始下一次yield，直到迭代器沒有元素可yield為止才結束for循環。從效果上看迭代器就像是另外一個控制線程，有它自己的程序計數器，它的執行與為它提供下標值的for循環交替執行，這一類通常稱為真迭代器。

迭代器

在許多面向對象語言里，用了更加面向對象的方法來實現迭代器。它們的迭代器就是一個常規對象，它提供了一套方法，用來初始化、生成下一個下標值和檢測結束條件

BinTree<Integer> myTree;

for (Integer i : myTreee) {

}

上面的這段代碼其實是下面這段的一個語法糖

for(Iterator<Integer> it = myTree.iterator();it.hasNext();) {

}

用一級函數來實現迭代器

實現是將循環的體寫成一個函數，用循環的下標作為函數的參數，然後將這函數作為參數傳遞給一個迭代器

(define uptoby
    (lambda (low high step f)
        (if (<= low higt)
            (begin
                (f low)
                (uptoby (+ low step) high step f))
            '())))

不用迭代器的迭代

在那些沒有真迭代器或者迭代器對象的語言中，還是可以通過編程方式實現集合枚舉和使用元素之間的解耦的，用C語言做例子：

tree_node *my_tree;    
tree_iter ti:                 
...
for(ti_create(my_tree,&ti);
              !ti_done(ti);
              ti_next(&ti)){
     tree_node *n=ti_val(ti);
     ...
}
ti_delete(&ti);

邏輯控制的循環

和枚舉循環相比，邏輯控制的循環關注點只在結束條件上

前置檢測

由Algol W引進，後來被Pascal保留

while cond do stat

後置檢測

這種的循環體不管是否滿足循環條件，都至少會執行一次循環體。如C語言的do while語句

do{
   line=read_line();
   //...代碼
} while line[0]!='$';

中置檢測

中置檢測一般依賴if

for(;;){
   line=read_line();
   if line[0]!='$' break;
}

遞歸

遞歸和上述討論的其他控制流都不同，它不依賴特殊的語法形式，只要語言允許函數直接或間接的調用自身，那麼就是支持遞歸的。大部分情況下遞歸和迭代都可以互相用對方重寫的。

迭代和遞歸

早期的一些語言不支持遞歸（比如Fortan77以前的版本），也有一些函數式語言不允許迭代，然而大部分現代語言都是同時支持兩者的。在命令式語言中，迭代在某種意義上顯得更自然一些，因為它們的核心就是反覆修改一些變量；對於函數式語言，遞歸更自然一些，因為它們並不修改變量。如果是要計算gcd（更相減損法），遞歸更自然一些：

int gcd(int a,int b){
  if(a==b) return a;
  else if (a>b) return gcd(a-b,b);
  else return gcd(a,b-a);
}

用迭代則是這樣：

int gcd(int a,int b){
   while(a!=b){
      if(a>b) a=a-b;
      else  b=b-a;
   }
   return a;
}

尾遞歸

經常有人說迭代比遞歸效率更高，其實更準確的說法應該是，迭代的樸素實現的（無優化）效率通常比遞歸的樸素實現的效率要高。如上面gcd的例子，如果遞歸的實現確實是實實在在的子程序調用，那麼這種子程序調用所帶來的棧的分配等的開銷確實要比迭代要大。然而一個“優化”的編譯器（通常是專門為函數式語言設計的編譯器），常常能對遞歸函數生成優異的代碼，如上面的gcd尾遞歸（尾遞歸函數是指在遞歸調用之後再無其他計算的函數，其返回值就是遞歸調用的返回值）。對這種函數完全不必要進行動態的棧分配，編譯器在做遞歸調用時可以重複使用當前的棧空間，從效果上看，好的編譯器可以把上面遞歸的gcd函數改造為：

int gcd(int a,int b){
start:
   if (a==b) return a;
   else if (a>b){
     a=a-b;
     goto start;  
   }
   else{
     b=b-a;
     goto start;
  }
}

即使是那些非尾遞歸函數，通過簡單的轉換也可能產生出尾遞歸代碼。

應用序和正則序求值

在上述的討論中，我們都假定所有參數在傳入子程序之前已經完成了求值，但是實際中這並不是必須的。完全可以採用另外一種方式，把為求值的之際參數傳遞給子程序，僅在需要某個值得時候再去求它。前一種在調用前求值的方案稱為應用序求值；后一種到用時方求值的方式稱為正則序求值。正則序求值在宏這個概念中是自然而然的方式，前面討論的短路求值、以及後面要討論的按名調用參數也是應用的正則序求值，一些函數式語言中偶爾也會出現這種方式。

但是我們來看一個例子：

#define MAX(a,b) ((a)>(b)?(a):(b))

如果我這麼調用MAX（i++，j++），導致i和j都執行兩次++，產生了兩次副作用，這是我們不願意看到的結果。總結來說，只有在表達式求值不會產生副作用的情況下正則序才是安全的。

惰性求值

從清晰性和高效的角度看，應用序求值通常會比正則序合適一些，一次大部分語言都採用如此的方式。然而也確實有一些特殊情況下正則序更高效一些，而應用序會造成一些錯誤出現，這種情況的出現時因為一些參數的值實際上並不會被需要，但是還是被求值了，應用序求值有時也成為非惰性求值，比如下面的JavaScript代碼就會是一個死循環：

function while1() {
    while (true) { console.log('死循環')}
}
function NullFunction() { }
console.log(NullFunction(1,2,3,while1()));

Scheme通過內部函數delay和force提供可選的正則序求值功能，這兩個函數提供的實際上是惰性求值的一種實現

惰性求值最常見的一種用途就是用來創建無窮數據結構

(define naturals
    (letrec ((next (lambda (n) (cons n (delay (next (+ n 1)))))))
    (next 1)))

這樣就可以用Scheme表述所有的自然數

小結

本篇首先從表達式開始，介紹了表達式（語句）中的一些基本概念；然後從討論了從彙編時代到結構化程序設計時代語言中的控制流程的演進以及發展；有了前面兩個基礎，後面就詳細的介紹了程序中的三大基本流程控制結構順序、選擇、循環（遞歸和迭代）。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※收購3c,收購IPHONE,收購蘋果電腦-詳細收購流程一覽表

※網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司，幫您輕鬆架站!

※想要讓你的商品成為最夯、最多人討論的話題?網頁設計公司讓你強力曝光

※高價收購3C產品,價格不怕你比較

※想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師”嚨底家”!!

前言