面向堆棧編程

面向堆棧（stack-oriented）編程，或基於堆棧編程，是依賴於堆棧機器模型來操縱數據和傳遞參數的編程范型。一些程式語言適合這種描述，著名的有Forth、RPL (程式語言)、 PostScript、BibTeX樣式設計語言和很多彙編語言。

## 概述

面向堆棧語言運算於一個或多個堆棧之上，每個都充任不同用途。因此，用其他程式語言構造的程序，在面向堆棧系統中使用可能需要修改。進一步的說，一些面向堆棧語言運算，採用後綴表示法也稱為逆波蘭表示法，就是說，命令的任何實際參數（argument）或形式參數（parameter），都在這個命令之前陳述。例如，後綴表示法寫為`3 4 +`，而非`+ 3 4`，這是前綴表示法也稱為波蘭表示法，或者`3 + 4`，這是中綴表示法。

## 基於堆棧演算法

PostScript是後綴式基於堆棧語言的例子。在這種語言中表達式的一個例子是`2 3 mul`。計算這個表達式，涉及到理解堆棧導向是如何工作的。

堆棧導向可以用如下傳送帶類比來體現。在傳送帶（輸入）末端，按順序擺放了標記著`2`、`3`和`mul`的盤子。在傳送帶末端的盤子（`2`）可以拾取，但其他盤子不能被訪問，直到在末端的盤子被移除。這些盤子只能存儲在一個堆棧中，並且只能在這個堆棧頂上被增加或移除，而不能在中間或底部。可以提供空白盤子（和一個標記者）並且盤子可以永久丟棄。

<image>

拾取盤子`2`並把它放置在堆棧上，接著拾取盤子`3`並把它放置在堆棧上，然後拾取`mul`盤子。這是一個要進行的指令。接著從堆棧取走頂部的兩個盤子，將其標籤（`2`和`3`）相乘，並在一個新盤子上寫下結果（`6`）。丟棄兩個舊盤子（`2`和`3`）和盤子`mul`，並將新盤子放置在堆棧上。當傳送帶上不再具有更多的盤子，計算的結果（`6`）就展示在這個堆棧頂上。

這是一個非常簡單的計算。如果是更複雜的計算比如`(2 + 3) &times; 11 + 1`，那麼需要些什麼？如果它最初寫為後綴形式，就是說`2 3 add 11 mul 1 add`，計算可以按完全形同的方式進行，並完成出正確結果。計算步驟展示在下面的表格中。每列展示一個輸入元素（在傳送帶末端的盤子），和處理這個輸入之後堆棧的內容：

輸入｜2｜3｜11｜1

堆棧｜2｜32｜5｜115｜55｜155｜56

在處理完所有輸入之後，這個堆棧包含`56`，它是答案。

從而可以得出如下結論：基於堆棧的程式語言只有一種處理數據方式，即通過從堆棧頂部選取一塊數據，術語叫做「彈出」，和將數據放回堆棧，術語叫「壓入」。可以按常規或用其他種類程式語言書寫的任何表達式，可以寫成後綴（或前綴）形式，從而服從面向堆棧語言去做出解釋。

## 堆棧操縱

因為堆棧是在面向堆棧語言中操縱數據的關鍵方式，這種語言通常提供某種堆棧操縱算子。經常提供的有：`dup`，重複堆棧頂部元素；`exch`（或`swap`），交換堆棧頂部元素（第一個成為第二個而第二個成為第一個）；`roll`，循環的置換在堆棧中或堆棧一部份上的元素；`pop`（或`drop`）丟棄棧頂元素，還有隱含的`push`等等。這些是在研習過程中的關鍵。

## 堆棧作用的示意

為了輔助理解語句的作用，使用簡短注釋來展示在這個語句前後的堆棧頂部。如果有多個項目，堆棧的頂部在最右端。這個表示法常用於Forth語言，在它那裡的注釋包圍在圓括號內。

```forth
( 之前 -- 之后 )
```

例如，描述如下基本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`函數：

```forth
fib  ( n -- n' )
```

它等價於霍爾邏輯的先決條件和後置條件。二者注釋也可以稱為斷言，儘管在基於堆棧語言中無此必要。

## PostScript堆棧

PostScript和其他一些堆棧語言有用於其他用途的其他獨立堆棧。

### 變量和字典

已經分析了不同表達式的求值。變量的實現對於任何程式語言都是重要的，但是對於面向堆棧語言，它有著特殊關切，因為這是與數據交互的唯一方式。

在面向堆棧語言比如PostScript中實現變量的方式，通常涉及到一個獨立的特殊化了堆棧，它持有鍵-值對的「字典」。要建立一個變量，首先必須建立一個鍵（變量名字），具有與之關聯的一個值。在PostScript中，一個名字數據對象前綴著一個`/`，所以`/x`是名字數據對象，可以被關聯上舉例的數`42`。`define`（定義）命令是`def`，代碼如下：

```postscript
/x 42 def
```

在堆棧頂部的字典中，將名字`x`關聯於數`42`。在`/x`和`x`之間存在不同，前者是表示一個名字的數據對象，而`x`表示`/x`所定義的東西。

### 過程

在基於堆棧語言中，過程自身被當作數據對象。在PostScript中，過程被指示在`{`和`}`之間。例如，在PostScript語法中有：

```postscript
{ dup mul }
```

表示一個匿名過程，它重複在堆棧頂部的東西並接著相乘二者得出結果，這是個求平方的過程。

因為過程被當作一個簡單的數據對象，可以定義過程的名字。在檢索到它們的時候，直接執行它們。字典在存儲各種定義的同時，提供了控制作用域的一種方式。

因為數據對象被存儲在最頂部字典，自然出現了一種未預料的能力：在從一個字典查找一個定義的時候，檢查最頂部字典，接下一直往下。如果在一個不同的字典中已經定義了同名的一個過程，調用局部的那個過程。

### 典型過程的剖析

過程經常接受實際參數。它們被過程以非常特殊的方式處理，不同於其他程式語言。下面查看PostScript下的一個斐波那契數列程序：

```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)`，下面分解這個程序的每個關鍵步驟和反映堆棧：

```
                堆栈：4
   dup 
                堆栈：4 4
   dup 
                堆栈：4 4 4
   1 eq 
                堆栈：4 4 false
   exch 
                堆栈：4 false 4
   0 eq
                堆栈：4 false false
   or
                堆栈：4 false
   not
                堆栈：4 true
```

因為這個表達式求值為真，求值最內層過程：

```
                堆栈：4
   dup 
                堆栈：4 4
   1 sub
                堆栈：4 3
   fib

  （这里省略了递归调用的计算步骤）

                堆栈：4 F(3)
   exch 
                堆栈：F(3) 4
   2 sub 
                堆栈：F(3) 2
   fib

  （这里省略了递归调用的计算步骤）

                堆栈：F(3) F(2)
   add
                堆栈：F(3)+F(2)
```

這是預期的結果。

這個過程不使用命名變量，單純使用堆棧。命名變量可以使用/a exch def構造來建立。例如，是有命名變量`n`的一個求平方的過程。假定，並調用`3 sq`，以如下方式分析過程`sq`：

```
                堆栈：3 /n 
   exch 
                堆栈：/n 3
   def 
                堆栈：空（原内容已被用于定义）
   n 
                堆栈：3
   n 
                堆栈：3 3 
   mul
                堆栈：9
```

這是預期結果。

### 控制和流程

因為存在匿名過程，流程控制可以自然出現。if…then…else語句需要三段數據：條件，如果條件為真要做的過程，和如果條件為假要做的過程。例如在PostScript中：

```postscript
 2 3 gt { (2 is greater than three) = } { (2 is not greater than three) = } ifelse
```

所進行的幾乎等價於C代碼：

```c
 if (2 > 3) { printf("2 is greater than three\n"); } else { printf("2 is not greater than three\n"); }
```

循環和其他構造也是類似的。

## 基於堆棧程式語言

- dc
- Canonware Onyx
- Factor
- Forth
- Joy
- Poplog
- PostScript
- RPL語言
- S-Lang