面向堆栈编程
![本页使用了标题或全文手工转换](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).
|
|