Implement `Copy` for a recursive enum

help
#1

I'm an absolute beginner in rust and am trying to implement a while interpreter. The problem is that I want to have a recursive enum having the Copy implemented for it, but I can't. It might be worth mentioning that I'm a Haskell programmer and look at it with my Haskell mind set.
I get the following error when I'm trying to run the code:
value used here after move
Below you can find my code. Any sort of opinion or help would be appreciated. Thanks.

use std::collections::HashMap;

#[derive(Debug)]
enum Com {
    Skip,
    Assign(Loc, ArithE),
    Seq(Box<Com>, Box<Com>),
    If(BoolE, Box<Com>, Box<Com>),
    While(BoolE, Box<Com>),
}

#[derive(Debug)]
enum ArithE {
    Num(i32),
    VarA(Loc),
    Aexp(Aop, Box<ArithE>, Box<ArithE>),
}

#[derive(Debug)]
enum BoolE {
    Truth(bool),
    VarB(Loc),
    Bexp(Bop, Box<BoolE>, Box<BoolE>),
    BexpA(BopA, ArithE, ArithE),
    BexpN(BopN, Box<BoolE>),
}

#[derive(Debug, Hash, Clone, Copy, PartialEq)]
enum Loc {
    L(i32),
}
impl Eq for Loc {}

#[derive(Debug)]
enum Aop {
    Plus,
    Minus,
    Mul,
}

#[derive(Debug)]
enum Bop {
    And,
    Or,
}

#[derive(Debug)]
enum BopA {
    Equ,
    LOE,
}

#[derive(Debug)]
enum BopN {
    Neg,
}

type Mem = HashMap<Loc, i32>;

fn eval_a(a: ArithE, m: &mut Mem) -> Option<ArithE> {
    return match a {
        ArithE::Num(n) => Some(ArithE::Num(n)),
        ArithE::VarA(loc) => Some(ArithE::Num(*m.get(&loc).unwrap())),
        ArithE::Aexp(op, a0, a1) => match *a0 {
            ArithE::Num(n0) => match *a1 {
                ArithE::Num(n1) => match op {
                    Aop::Plus => Some(ArithE::Num(n0 + n1)),
                    Aop::Minus => Some(ArithE::Num(n0 - n1)),
                    Aop::Mul => Some(ArithE::Num(n0 * n1)),
                },
                _ => eval_a(ArithE::Aexp(op, a0, Box::new(eval_a(*a1, m).unwrap())), m),
            },
            _ => eval_a(ArithE::Aexp(op, Box::new(eval_a(*a0, m).unwrap()), a1), m),
        },
    };
}

fn eval_b(b: BoolE, m: &mut Mem) -> Option<BoolE> {
    return match b {
        BoolE::Truth(t) => Some(BoolE::Truth(t)),
        BoolE::VarB(loc) => Some(BoolE::Truth(*m.get(&loc).unwrap() != 0)),
        BoolE::Bexp(op, b0, b1) => match *b0 {
            BoolE::Truth(t0) => match *b1 {
                BoolE::Truth(t1) => match op {
                    Bop::And => Some(BoolE::Truth(t0 && t1)),
                    Bop::Or => Some(BoolE::Truth(t0 || t1)),
                },
                _ => eval_b(BoolE::Bexp(op, b0, Box::new(eval_b(*b1, m).unwrap())), m),
            },
            _ => eval_b(BoolE::Bexp(op, Box::new(eval_b(*b0, m).unwrap()), b1), m),
        },
        BoolE::BexpA(op, a0, a1) => match a0 {
            ArithE::Num(n0) => match a1 {
                ArithE::Num(n1) => match op {
                    BopA::Equ => Some(BoolE::Truth(n0 == n1)),
                    BopA::LOE => Some(BoolE::Truth(n0 <= n1)),
                },
                _ => eval_b(BoolE::BexpA(op, a0, eval_a(a1, m).unwrap()), m),
            },
            _ => eval_b(BoolE::BexpA(op, eval_a(a0, m).unwrap(), a1), m),
        },
        BoolE::BexpN(op, b) => match *b {
            BoolE::Truth(t) => match op {
                BopN::Neg => Some(BoolE::Truth(!t)),
            },
            _ => eval_b(BoolE::BexpN(op, Box::new(eval_b(*b, m).unwrap())), m),
        },
    };
}

fn eval_c(c: Com, m: &mut Mem) -> Option<&mut Mem> {
    return match c {
        Com::Skip => Some(m),
        Com::Assign(loc, a) => Some(add_to_map(m, loc, a)),
        Com::Seq(c0, c1) => eval_c(*c1, eval_c(*c0, m).unwrap()),
        Com::If(b, c0, c1) => match eval_b(b, m).unwrap() {
            BoolE::Truth(true) => eval_c(*c0, m),
            _ => eval_c(*c1, m),
        },
        Com::While (b, c) => eval_c(Com::If(b, Box::new(Com::Seq(c, Box::new(Com::While (b, c)))), Box::new(Com::Skip)), m),
    };
}

fn add_to_map(m: &mut Mem, loc: Loc, a: ArithE) -> &mut Mem {
    let ua = unwrap_arith(eval_a(a, m).unwrap());
    m.insert(loc, ua);
    m
}

fn unwrap_arith(a: ArithE) -> i32 {
    return match a {
        ArithE::Num(n) => n,
        _ => -1,
    };
}
#2

These types cannot be Copy because they can't be copied just by a simple memcpy. (The copy operation needs to run code to perform allocations and follow pointers and so on.) In general, Copy is only possible for a very restricted set of types, which do not include any smart pointers or heap allocations.

But you can derive the Clone trait and then use the .clone() method to duplicate values of these types. (Playground)

If you replace the Box pointers with Rc pointers, then instead of a ”deep” clone, you'll produce a new value with a pointer to the same shared structures. (This would be more similar to how Haskell works, but with reference counting instead of a tracing garbage collector.)

4 Likes
#3

That makes perfect sense now. Awesome, thanks Matt.

#4

As a Haskell programmer, you might be delighted to learn that

fn foobar(x: SomeType) { return some_expression(x); }

can be rewritten

fn foobar(x: SomeType) { some_expression(x) }

without the return (and the ;). In general, blocks and function bodies in Rust look like

{
    STATEMENT;
    STATEMENT;
    ...
    STATEMENT;
    RETURNED_EXPRESSION
}

(statements end in ;, the final expression does not)

Without a final expression like RETURNED_EXPRESSION above, implicitly either unit, i.e. “()” is returned,
or any type is allowed if there’s (something like) a return statement on any code path leading to the end of the block.

And by the way, a statement is always either a let statement of just an expression whose value is ignored that is only evaluated for the side-effects. In particular, all control flow primitives such as match, if, loop, for, etc. are expressions.

On the other hand, to note an important difference to Haskell, you don’t have tail-call-optimization in Rust, so recursive functions such as your while interpreter will probably quickly lead to stack overflows.

2 Likes