堆疊導向編程
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
堆疊導向編程,或基於堆疊編程,是依賴於堆疊機器模型來傳遞參數的程式設計範式。一些程式語言適合這種描述,著名的有Forth、RPL、 PostScript、BibTeX風格設計語言[1]和很多組合語言。
概述
堆疊導向語言運算於一個或多個堆疊之上,每個都充任不同用途。因此,用其他程式語言構造的程式,在堆疊導向系統中使用可能需要修改[2]。進一步的說,一些堆疊導向語言運算,採用字尾表示法也稱為逆波蘭表示法,就是說,命令的任何實際參數(argument)或形式參數(parameter),都在這個命令之前陳述。例如,字尾表示法寫為3 4 +
,而非+ 3 4
,這是字首表示法也稱為波蘭表示法,或者3 + 4
,這是中綴表示法。
基於堆疊演算法
PostScript是字尾式基於堆疊語言的例子。在這種語言中表達式的一個例子是2 3 mul
。計算這個表達式,涉及到理解堆疊導向是如何工作的。
堆疊導向可以用如下傳送帶類比來體現。在傳送帶(輸入)末端,按順序擺放了標記著2
、3
和mul
的盤子。在傳送帶末端的盤子(2
)可以拾取,但其他盤子不能被訪問,直到在末端的盤子被移除。這些盤子只能儲存在一個堆疊中,並且只能在這個堆疊頂上被增加或移除,而不能在中間或底部。可以提供空白盤子(和一個標記者)並且盤子可以永久丟棄。
拾取盤子2
並把它放置在堆疊上,接著拾取盤子3
並把它放置在堆疊上,然後拾取mul
盤子。這是一個要進行的指令。接著從堆疊取走頂部的兩個盤子,將其標籤(2
和3
)相乘,並在一個新盤子上寫下結果(6
)。丟棄兩個舊盤子(2
和3
)和盤子mul
,並將新盤子放置在堆疊上。當傳送帶上不再具有更多的盤子,計算的結果(6
)就展示在這個堆疊頂上。
這是一個非常簡單的計算。如果是更複雜的計算比如(2 + 3) × 11 + 1
,那麼需要些什麼?如果它最初寫為字尾形式,就是說2 3 add 11 mul 1 add
,計算可以按完全形同的方式進行,並完成出正確結果。計算步驟展示在下面的表格中。每列展示一個輸入元素(在傳送帶末端的盤子),和處理這個輸入之後堆疊的內容:
輸入 | 2 | 3 | add | 11 | mul | 1 | add |
---|---|---|---|---|---|---|---|
堆疊 | 2 | 3 2 |
5 | 11 5 |
55 | 1 55 |
56 |
在處理完所有輸入之後,這個堆疊包含56
,它是答案。
從而可以得出如下結論:基於堆疊的程式語言只有一種處理資料方式,即通過從堆疊頂部選取一塊資料,術語叫做「彈出」,和將資料放回堆疊,術語叫「壓入」。可以按常規或用其他種類程式語言書寫的任何表達式,可以寫成字尾(或字首)形式,從而服從堆疊導向語言去做出解釋。
堆疊操縱
因為堆疊是在堆疊導向語言中操縱資料的關鍵方式,這種語言通常提供某種堆疊操縱算子。經常提供的有:dup
,重複堆疊頂部元素;exch
(或swap
),交換堆疊頂部元素(第一個成為第二個而第二個成為第一個);roll
,迴圈的置換在堆疊中或堆疊一部份上的元素;pop
(或drop
)丟棄棧頂元素,還有隱含的push
等等。這些是在研習過程中的關鍵。
堆疊作用的示意
為了輔助理解語句的作用,使用簡短注釋來展示在這個語句前後的堆疊頂部。如果有多個專案,堆疊的頂部在最右端。這個表示法常用於Forth語言,在它那裡的注釋包圍在圓括號內。
( 之前 -- 之后 )
例如,描述如下基本Forth堆疊算子:
dup ( a -- a a )
drop ( a -- )
swap ( a b -- b a )
over ( a b -- a b a )
rot ( a b c -- b c a )
還有如下這樣描述fib
函式:
fib ( n -- n' )
它等價於霍爾邏輯的先決條件和後置條件。二者注釋也可以稱為斷言,儘管在基於堆疊語言中無此必要。
PostScript堆疊
PostScript和其他一些堆疊語言有用於其他用途的其他獨立堆疊。
變數和字典
已經分析了不同表達式的求值。變數的實現對於任何程式語言都是重要的,但是對於堆疊導向語言,它有著特殊關切,因為這是與資料互動的唯一方式。
在堆疊導向語言比如PostScript中實現變數的方式,通常涉及到一個獨立的特殊化了堆疊,它持有鍵-值對的「字典」。要建立一個變數,首先必須建立一個鍵(變數名字),具有與之關聯的一個值。在PostScript中,一個名字資料對象字首著一個/
,所以/x
是名字資料對象,可以被關聯上舉例的數42
。define
(定義)命令是def
,代碼如下:
/x 42 def
在堆疊頂部的字典中,將名字x
關聯於數42
。在/x
和x
之間存在不同,前者是表示一個名字的資料對象,而x
表示/x
所定義的東西。
過程
在基於堆疊語言中,過程自身被當作資料對象。在PostScript中,過程被指示在{
和}
之間。例如,在PostScript語法中有:
{ dup mul }
表示一個匿名過程,它重複在堆疊頂部的東西並接著相乘二者得出結果,這是個求平方的過程。
因為過程被當作一個簡單的資料對象,可以定義過程的名字。在檢索到它們的時候,直接執行它們。字典在儲存各種定義的同時,提供了控制作用域的一種方式。
因為資料對象被儲存在最頂部字典,自然出現了一種未預料的能力:在從一個字典尋找一個定義的時候,檢查最頂部字典,接下一直往下。如果在一個不同的字典中已經定義了同名的一個過程,呼叫局部的那個過程。
典型過程的剖析
過程經常接受實際參數。它們被過程以非常特殊的方式處理,不同於其他程式語言。下面檢視PostScript下的一個斐波那契數列程式:
/fib
{
dup dup 1 eq exch 0 eq or not
{
dup 1 sub fib
exch 2 sub fib
add
} if
} def
在堆疊上使用了遞迴定義。斐波那契數函式接受一個實際參數。首先,它被測試是否為1
或0
。
假定計算fib(4)
,下面分解這個程式的每個關鍵步驟和反映堆疊:
stack: 4 dup stack: 4 4 dup stack: 4 4 4 1 eq stack: 4 4 false exch stack: 4 false 4 0 eq stack: 4 false false or stack: 4 false not stack: 4 true
因為這個表達式求值為真,求值最內層過程:
stack: 4 dup stack: 4 4 1 sub stack: 4 3 fib
- (這裡是遞迴呼叫)
stack: 4 F(3) exch stack: F(3) 4 2 sub stack: F(3) 2 fib
- (這裡是遞迴呼叫)
stack: F(3) F(2) add stack: F(3)+F(2)
這是預期的結果。
這個過程不使用命名變數,單純使用堆疊。命名變數可以使用/a exch def
構造來建立。例如{/n exch def n n mul}
,是有命名變數n
的一個求平方的過程。假定/sq {/n exch def n n mul} def
,並呼叫3 sq
,以如下方式分析過程sq
:
stack: 3 /n exch stack: /n 3 def stack: 空(它已经被定义) n stack: 3 n stack: 3 3 mul stack: 9
這是預期結果。
控制和流程
因為存在匿名過程,流程控制可以自然出現。if…then…else語句需要三段資料:條件,如果條件為真要做的過程,和如果條件為假要做的過程。例如在PostScript中:
2 3 gt { (2 is greater than three) = } { (2 is not greater than three) = } ifelse
所進行的幾乎等價於C代碼:
if (2 > 3) { printf("2 is greater than three\n"); } else { printf("2 is not greater than three\n"); }
迴圈和其他構造也是類似的。
基於堆疊程式語言
參見
參照
- ^ Oren Patashnik, Designing BibTeX styles (PDF), [2022-06-04], (原始內容 (PDF)存檔於2022-03-07)
- ^ Luerweg, T. (2015). Stack based programming paradigms. Concepts of Programming Languages–CoPL』15, 33.
- ^ Canonware Onyx. Canonware.com. [July 7, 2018]. (原始內容存檔於March 13, 2017).
|
|