View mode: basic / threaded / horizontal-split · Log in · Help
August 10, 2012
An example of Rust code
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
August 10, 2012
Re: An example of Rust code
Sorry, my mistake again, this was meant for the main D newsgroup.

Bye,
bearophile
August 10, 2012
Re: An example of Rust code
On 10-08-2012 03:44, bearophile wrote:
> Sorry, my mistake again, this was meant for the main D newsgroup.
>
> Bye,
> bearophile

Please repost on the main newsgroup so it gets attention. :)

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org
August 10, 2012
Re: An example of Rust code
Alex Rønne Petersen:

> Please repost on the main newsgroup so it gets attention. :)

OK. But I don't know much much interested they will be :-)

Bye,
bearophile
Top | Discussion index | About this forum | D home