(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

On Friday, 10 August 2012 at 12:32:28 UTC, bearophile wrote:
>
> 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));
> }
>
> Probably there are ways to improve my D versions, or to write better versions.
>
> Bye,
> bearophile

I think version 2 would be the easiest one to improve, by including a combined emplace/alloca convenience function in Phobos for this common use-case.

See the technique used in:
http://www.digitalmars.com/d/archives/digitalmars/D/run-time_stack-based_allocation_166305.html

"auto Create(void* buf=alloca(frame_size))"

One simple possibility is

import std.stdio;
struct Expr{
    enum Tag { val, plus, minus }
    union{int i;struct{Expr* a, b;}}
    Tag tag;
}
Expr val(int i){ Expr e;e.tag=Expr.Tag.val;e.i=i;return e;}
Expr plus(Expr* a, Expr* b){Expr e;e.tag=Expr.Tag.plus; e.a=a; e.b=b;return e;}
Expr minus(Expr* a, Expr* b){Expr e;e.tag=Expr.Tag.minus; e.a=a; e.b=b;return e;}

int eval(scope Expr* e){
    final switch(e.tag) with(Expr.Tag){
        case val:   return e.i;
        case plus:  return eval(e.a) + eval(e.b);
        case minus: return eval(e.a) - eval(e.b);
    }
}
void main(){
    auto five = val(5), three = val(3), one = val(1);
    auto add  = plus(&three, &one);
    auto sub  = minus(&five, &add);
    auto x    = eval(&sub);
    writeln("val: ",x);
}

It would of course be better if D supported ADTs.

On 8/10/2012 5:32 AM, bearophile wrote:
> Through Reddit I've found a page that shows a small example of Rust code:

Here's the D version:
-----------------------------------------
import std.stdio;

struct expr {
    int val;
    int eval() { return val; }
}

expr plus (expr a, expr b) { return expr(a.val + b.val); }
expr minus(expr a, expr b) { return expr(a.val - b.val); }

void main() {
    auto x = minus(expr(5), plus(expr(3), expr(1))).eval();
    writeln("val: ", x);
}
------------------------------------------

And the generated code:

------------------------------------------
__Dmain comdat
        assume  CS:__Dmain
L0:             push    EAX
                mov     EAX,offset FLAT:_D3std5stdio6stdoutS3std5stdio4File
                push    dword ptr FLAT:_DATA[0Ch]
                push    dword ptr FLAT:_DATA[08h]
                push    1
                push    0Ah
                call    near ptr _D3std5stdio4File18__T5writeTAyaTiTaZ5writeMFAyaiaZv
                xor     EAX,EAX
                pop     ECX
                ret
----------------------------------------

I'd say we're doing all right.

Walter Bright:

> I'd say we're doing all right.

Are you serious?

Bye,
bearophile

Tove:

> I think version 2 would be the easiest one to improve, by including a combined emplace/alloca convenience function in Phobos for this common use-case.
>
> See the technique used in:
> http://www.digitalmars.com/d/archives/digitalmars/D/run-time_stack-based_allocation_166305.html
>
> "auto Create(void* buf=alloca(frame_size))"

I see, thank you for the suggestion, seems interesting.
And thank you to Timon Gehr for his compacted code.

Walter's code seems to miss the point, but maybe he's trying to tell me something about very small demo programs.

Bye,
bearophile

On 8/10/2012 3:42 PM, bearophile wrote:
> Walter Bright:
>
>> I'd say we're doing all right.
>
> Are you serious?

Yes. What's wrong with my D version? It's short and to the point, works, and produces optimal code.

On 8/10/2012 3:46 PM, bearophile wrote:
> Walter's code seems to miss the point, but maybe he's trying to tell me
> something about very small demo programs.

If you want something allocated on the stack, us a struct, not a class.
It's what structs are for.

You can also use templates with overloading to get stack allocated parametric polymorphism and zero runtime overhead.

What I mean is:

1. If you write FORTRAN code in D, it will not work as well as writing FORTRAN in FORTRAN.

2. If you write C code in D, it will not work as well as writing C in C.

3. If you write Rust code in D, it will not work as well as writing Rust in Rust.

If you want D code to perform, you gotta write it in D. Not in Rust, C, or Java.

On 8/10/2012 4:19 PM, Walter Bright wrote:
> You can also use templates with overloading to get stack allocated parametric
> polymorphism and zero runtime overhead.

It appears that Rust does not have function overloading. Is this correct?

On Fri, Aug 10, 2012 at 4:35 PM, Walter Bright <newshound2@digitalmars.com> wrote:
> On 8/10/2012 4:19 PM, Walter Bright wrote:
>>
>> You can also use templates with overloading to get stack allocated
>> parametric
>> polymorphism and zero runtime overhead.
>
>
> It appears that Rust does not have function overloading. Is this correct?

That is correct.