如何在 Rust 中正确表示基于堆栈的语言?

Question

我正在尝试模拟解析简单命令式语言(Haskell(的第3节。特别是，我正在考虑一种基于堆栈的语言而不是命令式语言，并且我正在尝试纠正惯用的 Rust 代码来表示数据。

假设你想创建一个基于堆栈的小(非常小(的语言，它有一些基本的算术运算，没有用户定义的函数，并且处理十进制数和整数。所以例如：

1 2 +
-> Stack contains: 3

这是怎么回事？从左到右读取，按堆栈上的 1 和 2，+将推开1并2，然后将3(= 1 + 2(推到堆栈上。

我的想法是考虑3需要解析的"原语"类型。您有整数、十进制数和函数。此外，十进制和整数都是"名词"，函数是"动词"。因此，在执行程序时，我的想法是，您可以通过扩展Result<T, E>枚举的想法在 Rust 中表示这些想法。我想出了以下方案：

enum Noun {
Integer(i64),
Decimal(f64)
}
enum Primitive<T> {
Noun(T),
Verb(Fn(Vec<Noun>) -> Noun),
}
// Not really important, just giving a main so it can be ran
fn main() {
println!("Hello, world!");
}

换句话说，基元要么是Noun，要么是Verb，Noun要么是整数，要么是浮点数。

但是，这会导致：

error[E0277]: the trait bound `std::ops::Fn(std::vec::Vec<Noun>) -> Noun + 'static: std::marker::Sized` is not satisfied
--> main.rs:8:10
|
8 |     Verb(Fn(Vec<Noun>) -> Noun),
|          ^^^^^^^^^^^^^^^^^^^^^^ `std::ops::Fn(std::vec::Vec<Noun>) -> Noun + 'static` does not have a constant size known at compile-time
|
= help: the trait `std::marker::Sized` is not implemented for `std::ops::Fn(std::vec::Vec<Noun>) -> Noun + 'static`
= note: only the last field of a struct may have a dynamically sized type
error: aborting due to previous error(s)

在 Rust 中执行此操作的标准方法是什么？

Answer 1

类型Fn(Vec<Noun>) -> Noun描述一个特征对象，一个包含此特征的任何类型的占位符。 由于该特征可以通过捕获其他变量的普通函数或闭包来实现，因此编译器无法知道为此类对象分配多少空间。 特征对象是"动态调整大小"的，因此不能存在于堆栈上。

解决错误消息的一个选项是改为存储在堆上：

enum Primitive<T> {
Noun(T),
Verb(Box<dyn Fn(Vec<Noun>) -> Noun>),
}

dyn关键字明确表示我们正在处理一个 trait 对象，并且对该对象的方法调用是动态调度的。 它在当前的 Rust 中是可选的，但在新代码中推荐，以使 trait 对象更加明显。

另一种方法是使用纯函数指针而不是 trait 对象：

enum Primitive<T> {
Noun(T),
Verb(fn(Vec<Noun>) -> Noun),
}

函数指针只能指向不捕获任何变量的普通函数或闭包，因此是静态大小的，因此可以存储在堆栈上。

就个人而言，我可能会实现一个名为Function或类似的自定义特征，并使用

enum Primitive<T> {
Noun(T),
Verb(Box<dyn Function>),
}

自定义特征将为您提供更大的灵活性，可以将元数据和其他方法附加到特征对象，例如检索函数将消耗的输入数的方法。