Example of Rust code

[bearophile]

(Repost from D.learn.)

Through Reddit I've found a page that shows a small example of 
Rust code:

http://www.reddit.com/r/programming/comments/xyfqg/playing_with_rust/
https://gist.github.com/3299083

The code:
https://gist.github.com/3307450

-----------------------------

So I've tried to translate this first part of the Rust code to D 
(I have not run it, but it looks correct):


enum expr {
     val(int),
     plus(&expr, &expr),
     minus(&expr, &expr)
}

fn eval(e: &expr) -> int {
     alt *e {
       val(i) => i,
       plus(a, b) => eval(a) + eval(b),
       minus(a, b) => eval(a) - eval(b)
     }
}

fn main() {
     let x = eval(
         &minus(&val(5),
                &plus(&val(3), &val(1))));

     io::println(#fmt("val: %i", x));
}


A comment from the little article:

>putting a & in front of a expression allocates it on the stack 
>and gives you a reference to it. so the lifetime of this tree is 
>to the end of the run [main] function.<

-----------------------------

The first D version is easy enough to write, but:
- It uses classes, I think each class instance uses more memory 
than what's used in the original Rust code.
- All the class instances here are allocated on the Heap. This is 
less efficient than the Rust code, where all the data is 
stack-allocated.
- This code contains boilerplate, it's long.
- Writing eval() is easy, but in the first version of eval() 
there were two bugs.
- The assert(0) in eval() is not nice. There is no compile-time 
safety.
- The several dynamic casts in eval() are slow.


interface Expr {}

class Val : Expr {
     const int v;
     this(in int v_) pure nothrow {
         this.v = v_;
     }
}

class Plus : Expr {
     const Expr x, y;
     this(in Expr x_, in Expr y_) pure nothrow {
         this.x = x_;
         this.y = y_;
     }
}

class Minus : Expr {
     const Expr x, y;
     this(in Expr x_, in Expr y_) pure nothrow {
         this.x = x_;
         this.y = y_;
     }
}

int eval(in Expr e) pure nothrow {
     if (Val ve = cast(Val)e)
         return ve.v;
     else if (Plus pe = cast(Plus)e)
         return eval(pe.x) + eval(pe.y);
     else if (Minus me = cast(Minus)e)
         return eval(me.x) - eval(me.y);
     else
         assert(0);
}

void main() {
     auto ex = new Minus(new Val(5),
                         new Plus(new Val(3),
                                  new Val(1)));

     import std.stdio;
     writeln("Val: ", eval(ex));
}

-----------------------------

This second D version uses the same class definitions, but 
allocates the class instances on the stack. The code is bug prone 
and ugly. The other disadvantages are unchanged:


void main() {
     import std.stdio;
     import std.conv: emplace;
     import core.stdc.stdlib: alloca;

     enum size_t size_Val = __traits(classInstanceSize, Val);
     enum size_t size_Plus = __traits(classInstanceSize, Plus);
     enum size_t size_Minus = __traits(classInstanceSize, Minus);

     Val e1 = emplace!Val(alloca(size_Val)[0 .. size_Val], 5);
     Val e2 = emplace!Val(alloca(size_Val)[0 .. size_Val], 3);
     Val e3 = emplace!Val(alloca(size_Val)[0 .. size_Val], 1);
     Plus e4 = emplace!Plus(alloca(size_Plus)[0 .. size_Plus], e2, 
e3);
     Minus ex2 = emplace!Minus(alloca(size_Minus)[0 .. 
size_Minus], e1, e4);

     writeln("Val: ", eval(ex2));
}

-----------------------------

A third D version, using tagged structs:
- It doesn't look nice, and it's long.
- Class references can be null, so I have added tests at runtime 
in the pre-conditions. In the Rust code the "references" can't be 
null.
- The structs are stack-allocated but the main() code is not nice.
- The tags can't const or immutable, otherwise the compiler 
doesn't read the actual value of the various tags, assuming it's 
always Tag.none.
- Too many casts make this code bug-prone.


import std.stdio;

enum Tag { none, val, plus, minus }

struct Expr {
     Tag tag = Tag.none;
}

struct Val {
     Tag tag = Tag.val;
     immutable int v;

     this(int v_) pure nothrow {
         this.v = v_;
     }
}

struct Plus {
     Tag tag = Tag.plus;
     const Expr* x, y;

     this(in Expr* x_, in Expr* y_) pure nothrow
     in {
         assert(x_ != null);
         assert(y_ != null);
     } body {
         this.x = x_;
         this.y = y_;
     }
}

struct Minus {
     Tag tag = Tag.minus;
     const Expr* x, y;

     this(in Expr* x_, in Expr* y_) pure nothrow
     in {
         assert(x_ != null);
         assert(y_ != null);
     } body {
         this.x = x_;
         this.y = y_;
     }
}

int eval(in Expr* e) pure nothrow
in {
     assert(e);
} body {
     final switch (e.tag) {
         case Tag.none:
             assert(0);
         case Tag.val:
             return (cast(Val*)e).v;
         case Tag.plus:
             auto pe = cast(Plus*)e;
             return eval(pe.x) + eval(pe.y);
         case Tag.minus:
             auto me = cast(Minus*)e;
             return eval(me.x) - eval(me.y);
     }
}

void main() {
     const e1 = Val(5);
     const e2 = Val(3);
     const e3 = Val(1);
     const e4 = Plus(cast(Expr*)&e2, cast(Expr*)&e3);
     const ex = Minus(cast(Expr*)&e1, cast(Expr*)&e4);

     writeln("Val: ", eval(cast(Expr*)&ex));
}


Probably there are ways to improve my D versions, or to write 
better versions.

Bye,
bearophile