How to correctly represent a stack based language in Rust?

Question

I am trying to emulate section 3 of Parsing a simple imperative language (Haskell). In particular, I am considering a stack based language instead of an imperative language, and I am trying to right idiomatic Rust code to represent the data.

Suppose you want to make a small (really small) stack based language that has some basic arithmetic operations, no user defined functions, and works on decimal numbers and integers. So for example:

   1 2 +
-> Stack contains: 3

What's going on? Read from left to right, push 1 and 2 on the stack, and the + would push off the 1 and 2 and then push 3 (= 1 + 2) onto the stack.

My idea is there to consider 3 types of "primitives" that need parsing. You have integers, decimal numbers, and functions. Furthermore, decimal and integers numbers are both "nouns", and functions are "verbs". So when executing a program my idea was you could represent these ideas in Rust by extending the idea of the Result<T, E> enum. I came up with the following scheme:

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!");
}

In other words, a primitive is either a Noun or a Verb, and Noun is either an integer or a float.

However, this results in:

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)

What would be the standard way of doing this in Rust?

Sven Marnach Sven Marnach · Accepted Answer · 2018-10-18T19:59:14

The type Fn(Vec<Noun>) -> Noun describes a trait object, a place holder for any type implemting this trait. Since the trait could be implemented by plain functions or closures that capture additional variables, the compiler can't know how much space to allocate for such an object. A trait object is "dynamically sized" and as such can't live on the stack.

One option to resolve the error message is to store in on the heap instead:

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

The dyn keyword makes explicit that we are dealing with a trait object, and that method calls on this object are dynamically dispatched. It's optional in current Rust, but recommended in new code to make trait objects more obvious.

An alternative is to use a plain function pointer instead of a trait object:

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

A function pointer can only point to an ordinary function or a closure that does not capture any variables, and as such is statically sized, so it can be stored on the stack.

Personally, I would probably implement a custom trait called Function or similar, and use

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

The custom trait will give you a lot more flexibility to attach metadata and additional methods to the trait object, e.g. a method to retrieve the number of inputs the function will consume.

How to correctly represent a stack based language in Rust?

1 Answers