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

Question

我正在尝试模拟 Parsing a simple imperative language 的第 3 节( haskell )。特别是，我正在考虑使用基于堆栈的语言而不是命令式语言，并且我正在尝试使用正确的惯用 Rust 代码来表示数据。

假设您想制作一个小的(非常小)stack based language它有一些基本的算术运算，没有用户定义的函数，并且适用于十进制数和整数。例如:

   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是整数或 float 。

但是，这会导致:

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描述了一个 trait 对象，它是实现此 trait 的任何类型的占位符。由于特征可以通过普通函数或捕获额外变量的闭包来实现，编译器无法知道为这样的对象分配多少空间。特征对象是“动态调整大小”的，因此不能存在于堆栈中。

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

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

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

另一种方法是使用普通函数指针而不是特征对象:

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

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

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

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

自定义特征会给你更多的灵 active 来附加元数据和额外的方法到特征对象，例如一种检索函数将消耗的输入数量的方法。