www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.patterns: it was about time

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
In wake of the increasing power of templates in D2, I am starting the 
std.patterns module, which is to contain boilerplate for a number of 
common design patterns (as in the GoF book). For now I'm adding a 
Visitor implementation, which was lying in my codebase for a while.

http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.html
http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.d

Comments and suggestions are as always welcome.


Andrei
Jan 31 2009
next sibling parent reply BLS <windevguy hotmail.de> writes:
Hi Andrei,
that's now something I appreciate ... Thanks!

I general patterns are not reusable as code, as developers must 
implement them new, over and over again.
I also thought that Mixins should be the key to implement a pattern 
library.
Let me name a library implemented pattern : Component.
The question is now which GoF pattern could be implemented as Component, 
or in other words are some are too much context-dependent ? ( Strategy, 
Provider /non GoF/)

I found a very interesting PhD thesis regarding this topic.
1- componentizable patterns
Flyweight
Observer
Mediator
Abstract Factory
Factory Method
Visitor
Command
Composite
Chain of Responsibility

I think we could add Singleton

2- Componentizable but not comprehensive
Builder
Proxy
State

Regarding Observer.
I think let's wait until Katrina (from the Qt binding project) explains 
what is needed to implement Qt Signal Slot in D2, so that hopefully the 
underlaying observer component fits.

Bjoern
PS. Source link don't work


Andrei Alexandrescu wrote:

 In wake of the increasing power of templates in D2, I am starting the 
 std.patterns module, which is to contain boilerplate for a number of 
 common design patterns (as in the GoF book). For now I'm adding a 
 Visitor implementation, which was lying in my codebase for a while.
 
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.d
 
 Comments and suggestions are as always welcome.
 
 
 Andrei
Feb 01 2009
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
BLS wrote:

 Hi Andrei,
 that's now something I appreciate ... Thanks!


[snip]

 PS. Source link don't work


Sorry, that must be:

http://ssli.ee.washington.edu/~aalexand/d/web/phobos/patterns.d


Andrei
Feb 01 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
BLS wrote:

 Hi Andrei,
 that's now something I appreciate ... Thanks!
 
 I general patterns are not reusable as code, as developers must 
 implement them new, over and over again.
 I also thought that Mixins should be the key to implement a pattern 
 library.
 Let me name a library implemented pattern : Component.
 The question is now which GoF pattern could be implemented as Component, 
 or in other words are some are too much context-dependent ? ( Strategy, 
 Provider /non GoF/)
 
 I found a very interesting PhD thesis regarding this topic.


Link?

Andrei
Feb 01 2009
parent BLS <windevguy hotmail.de> writes:
Andrei Alexandrescu wrote:


 Link?


Sorry,
http://se.inf.ethz.ch/people/arnout/patterns/

Implementation is in Eiffel...
Bjoern
PS:
The Pattern Wizard, shown on this page, is definitely something I would 
like to see as IDE Wizard... Can you here me Arie ?
Feb 01 2009
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2009-01-31 22:52:09 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:


 In wake of the increasing power of templates in D2, I am starting the 
 std.patterns module, which is to contain boilerplate for a number of 
 common design patterns (as in the GoF book). For now I'm adding a 
 Visitor implementation, which was lying in my codebase for a while.
 
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.d
 
 Comments and suggestions are as always welcome.


Using mixins to implements common patterns and place them in the 
standard library is a great idea. By the way, the correct URL for the 
code seems to be: 
<http://ssli.ee.washington.edu/~aalexand/d/patterns.d>.

A general comment about the visitor pattern: if we had class extensions 
where you could add new methods to Object, then the ability to add 
overrides of those methods by extending various derived classes, you 
wouldn't even need the visitor pattern. When you're used to that in 
Objective-C, the visitor pattern feels like a clever but cumbersome 
workaround for the lack of class extensibility.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Feb 01 2009
parent "Nick Sabalausky" <a a.a> writes:
"Michel Fortin" <michel.fortin michelf.com> wrote in message 
news:gm45h5$6p1$1 digitalmars.com...

 A general comment about the visitor pattern: if we had class extensions 
 where you could add new methods to Object, then the ability to add 
 overrides of those methods by extending various derived classes, you 
 wouldn't even need the visitor pattern. When you're used to that in 
 Objective-C, the visitor pattern feels like a clever but cumbersome 
 workaround for the lack of class extensibility.



extension methods) before I really looked into the visitor pattern, and that 
was pretty much my thought on the visitor pattern as well (ie, a cumbersome 
workaround). Although, there's two things about the visitor patten that I'm 
not certain would be taken care of by extension methods:

Multiple Dispatch: Although that could be overcome manually with RTTI.

Compositional Hierarchy (such as the car example): But I would think this 
could be handled by exposing an opApply or something like that.

Although, extension methods are really just syntactical sugar for a 
non-member (or static member) function call with a class as the first 
argument, so I'm not sure that even extension methods are strictly necessary 
to render the visitor pattern unneeded (But maybe there's something about 
the visitor pattern I'm not understanding.)
Feb 01 2009
prev sibling next sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
Andrei Alexandrescu escribió:

 In wake of the increasing power of templates in D2, I am starting the 
 std.patterns module, which is to contain boilerplate for a number of 
 common design patterns (as in the GoF book). For now I'm adding a 
 Visitor implementation, which was lying in my codebase for a while.
 
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.d
 
 Comments and suggestions are as always welcome.


It's nice to implement patterns with mixins, like Singleton in my video.

But that way of the visitor pattern seems pretty useless. I used that 
pattern a lot in Descent for the AST of the D language (and also in 
other projects). Each node of the AST has children, so for example:

---
class BinaryExp {

   Exp leftOperand;
   Exp rightOperand;
   Op operator;

   void accept(ASTVisitor visitor) {
     boolean visitChildren = visitor.visit(this);
     if (visitChildren) {
       if (leftOperand != null) leftOperand.accept(visitor);
       if (rightOperand != null) rightOperand.accept(visitor);
     }
     visitor.endVisit(this);
   }

}
---

Major differces with what you have are:
  1. Two methods: visit and endVisit. This allows you to know when the 
visitor enters a node and exits it. This is useful for algorithms with 
stacks: Say you want to print the AST back to a string with nice 
formatting. Whenever you enter a WhileStatement you increment the 
indentation, and when you exit it, you decrease it.
  2. visit returns true if the visitor wants to visit the node's 
children, false otherwise. This allows you to skip entire nodes upon a 
condition or depending on the visitor logic.
  3. The children of a node are visited automatically by that node (if 
desired by the visitor).

When it says "Essentially the Visitor pattern offers a means to add new 
methods to a class hierarchy without touching the hierarchy", I think it 
doesn't means a hierarchy of classes, but a conceptual hierarchy, like 
an AST or a Car with it's parts, where there are some things that 
contain other things.

Here's the ASTVisitor in JDT: 
http://help.eclipse.org/help32/index.jsp?topic=/org.eclipse.jdt.doc.isv/reference/api/org/eclipse/jdt/core/dom/ASTVisitor.html

So maybe the visitor pattern should be implemented like this:

---
class BinaryExp {

   Exp leftOperand;
   Exp rightOperand;

   mixin MakeVisitable!(leftOperand, rightOperand);

}
---

Also, since you normally write visitors for the same conceptual 
hierarchy, you'd like to do something like this:

---
auto expHierarchy = VisitorHierarchy!(BinaryExp, PrefixExp, Number, 
Parenthesis);

class Calculator : Visitor!(expHierarchy) {

   // ...

}
---

And the Visitor should be an abstract class where every visit method 
returns true by default. In that way you can extend it and overrite just 
the methods you need in your visitor.

Well... just thoughts. There are a lots of ways to implement this 
pattern, but I find this one the most useful.
Feb 01 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Ary Borenszweig wrote:

 Andrei Alexandrescu escribió:

 In wake of the increasing power of templates in D2, I am starting the 
 std.patterns module, which is to contain boilerplate for a number of 
 common design patterns (as in the GoF book). For now I'm adding a 
 Visitor implementation, which was lying in my codebase for a while.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.d

 Comments and suggestions are as always welcome.


 
 It's nice to implement patterns with mixins, like Singleton in my video.


[...]

Thanks for sharing your insights. So far Visitor is concerned with I 
disagree with the "automatically" here. Visitor has one purpose in life: 
you call accept() with the appropriate visitor, it calls visit() back 
with the appropriate type. That's a lot of saved boilerplate already. 
However, the notion of visitable children is not captured yet, and 
probably it should.


 So maybe the visitor pattern should be implemented like this:
 
 ---
 class BinaryExp {
 
   Exp leftOperand;
   Exp rightOperand;
 
   mixin MakeVisitable!(leftOperand, rightOperand);
 
 }
 ---


Not bad.


 Also, since you normally write visitors for the same conceptual 
 hierarchy, you'd like to do something like this:
 
 ---
 auto expHierarchy = VisitorHierarchy!(BinaryExp, PrefixExp, Number, 
 Parenthesis);
 
 class Calculator : Visitor!(expHierarchy) {
 
   // ...
 
 }
 ---


That's already in:

alias TypeTuple!(BinaryExp, PrefixExp, Number, Parenthesis
     ExpHierarchy;
class Calculator : Visitor!(ExpHierarchy)
{
     ...
}


 And the Visitor should be an abstract class where every visit method 
 returns true by default. In that way you can extend it and overrite just 
 the methods you need in your visitor.


Sometimes you need strict visitation, some other times you need 
non-strict visitation. We should capture both.


 Well... just thoughts. There are a lots of ways to implement this 
 pattern, but I find this one the most useful.


A good generic implementation would save the repetitive part without 
disallowing you from being creative.


Andrei
Feb 01 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Andrei Alexandrescu wrote:

 Ary Borenszweig wrote:

 Andrei Alexandrescu escribió:

 In wake of the increasing power of templates in D2, I am starting the 
 std.patterns module, which is to contain boilerplate for a number of 
 common design patterns (as in the GoF book). For now I'm adding a 
 Visitor implementation, which was lying in my codebase for a while.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.d

 Comments and suggestions are as always welcome.


 It's nice to implement patterns with mixins, like Singleton in my video.


 [...]
 
 Thanks for sharing your insights. So far Visitor is concerned with I 
 disagree with the "automatically" here. Visitor has one purpose in life: 
 you call accept() with the appropriate visitor, it calls visit() back 
 with the appropriate type.


Heh, I've mixed up copy and paste across a draft response. You may want 
to ignore the ``I disagree with the "automatically" here.'' part. I meant:

Thanks for sharing your insights. So far Visitor has one purpose in 
life: you call accept() with the appropriate visitor, it calls visit() 
back with the appropriate type.


Andrei
Feb 01 2009
prev sibling parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Andrei Alexandrescu wrote:

 In wake of the increasing power of templates in D2, I am starting the 
 std.patterns module, which is to contain boilerplate for a number of 
 common design patterns (as in the GoF book). For now I'm adding a 
 Visitor implementation, which was lying in my codebase for a while.
 
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_patterns.d
 
 Comments and suggestions are as always welcome.
 
 
 Andrei


It was, indeed, about time.

Simple as it is, you might as well toss a Singleton mixin in there.  Its 
so common and so insanely simple that there may as well be an "official" 
one.

Observer should be an interesting one to try implementing.  It could 
make use of signals/slots to good effect.  The question there is in 
whether one is to observe a Foo or a particular property of a Foo.  Both 
should probably be available.

-- Chris Nicholson-Sauls
Feb 11 2009