www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Is there an easy way to mimic generics with an accept method of a

reply Mina <minallkamel gmail.com> writes:
I'm following along with the crafting interpreters book 
(https://craftinginterpreters.com) and it goes into implementing 
a visitor pattern that returns generic types, so implementing it 
in D came down to the accept method causing undefined symbol 
error that goes away when changing it to returning a concrete 
type, so here's what I've got working 
(https://github.com/MKamelll/dlox/blob/main/source/loxast.d) and 
here's the book's implementation 
(https://github.com/munificent/craftinginterpreters/blob/master/java/com/craftinginterpreters/lox/Expr.java).


Thanks.
Feb 18 2021
parent reply Paul Backus <snarwin gmail.com> writes:
On Thursday, 18 February 2021 at 11:14:05 UTC, Mina wrote:

 I'm following along with the crafting interpreters book 
 (https://craftinginterpreters.com) and it goes into 
 implementing a visitor pattern that returns generic types, so 
 implementing it in D came down to the accept method causing 
 undefined symbol error that goes away when changing it to 
 returning a concrete type, so here's what I've got working 
 (https://github.com/MKamelll/dlox/blob/main/source/loxast.d) 
 and here's the book's implementation 
 (https://github.com/munificent/craftinginterpreters/blob/master/java/com/craftinginterpreters/lox/Expr.java).


 Thanks.


In D, because generics are implemented using templates 
("monomorphization"), generic methods can't be virtual and can't 
be overridden in child classes. As you've discovered, that means 
`accept` has to work entirely with concrete types rather than 
generic ones.

One way to solve this (which is used in the D compiler's source 
code) is to have both `accept` and `visit` return `void` and put 
the result inside the visitor object as a member variable. For 
example:

interface Visitor
{
     void visit(Expr.Literal expr);
     // etc.
}

class AstPrinter : Visitor
{
     string result;

     override void visit(Expr.Literal expr)
     {
         if (!expr.literal.hasValue) result =  "nil";
         else result = lexLiteralStr(expr.literal);
     }

     // etc.

     string print(Expr expr)
     {
         expr.accept(this);
         return result;
     }
}

Another possibility is to use discriminated unions and tag-based 
dispatch (i.e., switch statements) instead of classes and virtual 
method dispatch. This would make it a bit harder to follow the 
book, but might be a better learning experience if you're up for 
a challenge.
Feb 18 2021
next sibling parent reply vitamin <vit vit.vit> writes:
On Thursday, 18 February 2021 at 13:53:19 UTC, Paul Backus wrote:

 On Thursday, 18 February 2021 at 11:14:05 UTC, Mina wrote:

 I'm following along with the crafting interpreters book 
 (https://craftinginterpreters.com) and it goes into 
 implementing a visitor pattern that returns generic types, so 
 implementing it in D came down to the accept method causing 
 undefined symbol error that goes away when changing it to 
 returning a concrete type, so here's what I've got working 
 (https://github.com/MKamelll/dlox/blob/main/source/loxast.d) 
 and here's the book's implementation 
 (https://github.com/munificent/craftinginterpreters/blob/master/java/com/craftinginterpreters/lox/Expr.java).


 Thanks.


 In D, because generics are implemented using templates 
 ("monomorphization"), generic methods can't be virtual and 
 can't be overridden in child classes. As you've discovered, 
 that means `accept` has to work entirely with concrete types 
 rather than generic ones.

 One way to solve this (which is used in the D compiler's source 
 code) is to have both `accept` and `visit` return `void` and 
 put the result inside the visitor object as a member variable. 
 For example:

 interface Visitor
 {
     void visit(Expr.Literal expr);
     // etc.
 }

 class AstPrinter : Visitor
 {
     string result;

     override void visit(Expr.Literal expr)
     {
         if (!expr.literal.hasValue) result =  "nil";
         else result = lexLiteralStr(expr.literal);
     }

     // etc.

     string print(Expr expr)
     {
         expr.accept(this);
         return result;
     }
 }

 Another possibility is to use discriminated unions and 
 tag-based dispatch (i.e., switch statements) instead of classes 
 and virtual method dispatch. This would make it a bit harder to 
 follow the book, but might be a better learning experience if 
 you're up for a challenge.


Or combination of discriminate uninons and classes:

/+dub.sdl:
dependency "sumtype" version="~>0.10.0"
+/
import std.stdio;

import sumtype;

alias Expression = SumType!(
     ExprValue,
     ExprBinary,
     ExprUnary
);

class Expr{
     abstract Expression expression()pure nothrow  safe  nogc;

}

class ExprValue : Expr{
	string val;

     override Expression expression()pure nothrow  safe  nogc{
     	return Expression(this);
     }

     this(string val)pure{
     	this.val = val;
     }

}

class ExprBinary : Expr{
     string op;
     Expr left;
     Expr right;

     override Expression expression()pure nothrow  safe  nogc{
     	return Expression(this);
     }

     this(string op, Expr left, Expr right)pure{
     	this.op = op;
     	this.left = left;
     	this.right = right;
     }

}

class ExprUnary : Expr{
     string op;
     Expr expr;

     override Expression expression()pure nothrow  safe  nogc{
     	return Expression(this);
     }

     this(string op, Expr expr)pure{
     	this.op = op;
     	this.expr = expr;
     }
}

string printExpr(Expr expr){
     assert(expr !is null);

     static auto impl(E)(E e){
         static if(is(E == ExprValue)){
         	return e.val;
         }
         else static if(is(E == ExprUnary)){
         	return e.op ~ printExpr(e.expr);
         }
         else static if(is(E == ExprBinary)){
         	return printExpr(e.left) ~ e.op ~ printExpr(e.right);
         }
         else static assert(0, "no impl");

     }

     return expr.expression.match!impl;
}
void main(){
     // (1 + (- 2 ))
     Expr expr = new ExprBinary(
         "+",
         new ExprValue("1"),
         new ExprUnary(
             "-",
             new ExprValue("2")
         )
     );

     writeln(expr.printExpr());


}
Feb 18 2021
parent reply Paul Backus <snarwin gmail.com> writes:
On Thursday, 18 February 2021 at 14:26:37 UTC, vitamin wrote:

 Or combination of discriminate uninons and classes:

 /+dub.sdl:
 dependency "sumtype" version="~>0.10.0"
 +/
 import std.stdio;

 import sumtype;

 alias Expression = SumType!(
     ExprValue,
     ExprBinary,
     ExprUnary
 );

 class Expr{
     abstract Expression expression()pure nothrow  safe  nogc;

 }


I don't see what this buys you compared to sticking with one or 
the other, but you are correct that it is technically possible.
Feb 18 2021
parent reply vitamin <vit vit.vit> writes:
On Thursday, 18 February 2021 at 14:43:43 UTC, Paul Backus wrote:

 On Thursday, 18 February 2021 at 14:26:37 UTC, vitamin wrote:

 Or combination of discriminate uninons and classes:

 /+dub.sdl:
 dependency "sumtype" version="~>0.10.0"
 +/
 import std.stdio;

 import sumtype;

 alias Expression = SumType!(
     ExprValue,
     ExprBinary,
     ExprUnary
 );

 class Expr{
     abstract Expression expression()pure nothrow  safe  nogc;

 }


 I don't see what this buys you compared to sticking with one or 
 the other, but you are correct that it is technically possible.


It infer function atributes (pure, nothrow  nogc  safe) for 
"visitor" and let you use classes and inheritence.
With standard visitor pattern you need PureVisitor. 
NothrowVisitor, PureNothrowVisitor...
Feb 18 2021
parent reply Paul Backus <snarwin gmail.com> writes:
On Thursday, 18 February 2021 at 14:51:09 UTC, vitamin wrote:

 On Thursday, 18 February 2021 at 14:43:43 UTC, Paul Backus 
 wrote:

 I don't see what this buys you compared to sticking with one 
 or the other, but you are correct that it is technically 
 possible.


 It infer function atributes (pure, nothrow  nogc  safe) for 
 "visitor" and let you use classes and inheritence.
 With standard visitor pattern you need PureVisitor. 
 NothrowVisitor, PureNothrowVisitor...


It seems to me like you would also get those benefits by just 
using a discriminated union, without the classes.
Feb 18 2021
parent vitamin <vit vit.vit> writes:
On Thursday, 18 February 2021 at 15:11:44 UTC, Paul Backus wrote:

 On Thursday, 18 February 2021 at 14:51:09 UTC, vitamin wrote:

 On Thursday, 18 February 2021 at 14:43:43 UTC, Paul Backus 
 wrote:

 I don't see what this buys you compared to sticking with one 
 or the other, but you are correct that it is technically 
 possible.


 It infer function atributes (pure, nothrow  nogc  safe) for 
 "visitor" and let you use classes and inheritence.
 With standard visitor pattern you need PureVisitor. 
 NothrowVisitor, PureNothrowVisitor...


 It seems to me like you would also get those benefits by just 
 using a discriminated union, without the classes.


Yes, but classes has nice things like abstract/override/final 
methods and covariant return types and almost everybody known how 
they works. Maybe this things can be simulated with templates.
Feb 18 2021
prev sibling parent Mina <minallkamel gmail.com> writes:
On Thursday, 18 February 2021 at 13:53:19 UTC, Paul Backus wrote:

 Another possibility is to use discriminated unions and 
 tag-based dispatch (i.e., switch statements) instead of classes 
 and virtual method dispatch. This would make it a bit harder to 
 follow the book, but might be a better learning experience if 
 you're up for a challenge.


Thanks for the reply.
Feb 18 2021