跳至內容

面向堆棧編程

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

面向堆棧編程,或基於堆棧編程,是依賴於堆棧機器模型來傳遞參數編程范型。一些編程語言適合這種描述,著名的有ForthRPL英語RPL (programming language)PostScriptBibTeX風格設計語言[1]和很多匯編語言

概述

[編輯]

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

基於堆棧算法

[編輯]

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

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

拾取盤子2並把它放置在堆棧上,接着拾取盤子3並把它放置在堆棧上,然後拾取mul盤子。這是一個要進行的指令。接着從堆棧取走頂部的兩個盤子,將其標籤(23)相乘,並在一個新盤子上寫下結果(6)。丟棄兩個舊盤子(23)和盤子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是名字數據對象,可以被關聯上舉例的數42define(定義)命令是def,代碼如下:

/x 42 def

在堆棧頂部的字典中,將名字x關聯於數42。在/xx之間存在不同,前者是表示一個名字的數據對象,而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

在堆棧上使用了遞歸定義。斐波那契數函數接受一個實際參數。首先,它被測試是否為10

假定計算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"); }

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

基於堆棧編程語言

[編輯]

參見

[編輯]

引用

[編輯]
  1. ^ Oren Patashnik, Designing BibTeX styles (PDF), [2022-06-04], (原始內容 (PDF)存檔於2022-03-07) 
  2. ^ Luerweg, T. (2015). Stack based programming paradigms. Concepts of Programming Languages–CoPL』15, 33.
  3. ^ Canonware Onyx. Canonware.com. [July 7, 2018]. (原始內容存檔於March 13, 2017).