跳转到内容

面向堆栈编程

本页使用了标题或全文手工转换
维基百科,自由的百科全书

面向堆栈编程,或基于堆栈编程,是依赖于堆栈机器模型来传递参数编程范型。一些编程语言适合这种描述,著名的有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).