Code generator and visitor pattern
Karsten Wutzke
this is obviously a Python OO question:
Since Python isn't stringly typed, single-dispatch isn't available per
se. So is the "double-dispatch" Visitor pattern, which is usually used
in OO systems to implement code generators. So, what is the de facto
method in Python to handle source code generation?
Karsten
Thomas Jollans
> Hello,
>
> this is obviously a Python OO question:
>
> Since Python isn't stringly typed,
I expect this is an innocent typo, and you mean strictly.
> single-dispatch isn't available per se. So is the "double-dispatch" Visitor pattern,
Wait, what?
First of all, python is strictly typed in that every object has exactly
one type, which is different from other types. So you can't do "1"+2, as
you can in some other languages.
Anyway, this is interesting: Tell me more about how Python's dynamic
nature makes it impossible to do whatever you're trying to do. I'm
baffled. What are you trying to do, anyway?
> which is usually used
> in OO systems to implement code generators. So, what is the de facto
> method in Python to handle source code generation?
WHOA! Now if that isn't a Gedankensprung. Also, I'm still very far from
your train of thought, apparently: Now, the thing that code generators
probably share is that they write code to files. It depends on what I'm
trying to do of course, but I expect there's a good chance that if I
wrote a code generator in Python, it wouldn't be particularly
object-oriented at all.
Karsten Wutzke
> On 07/15/2010 07:58 PM, Karsten Wutzke wrote:
>
> > Hello,
>
> > this is obviously a Python OO question:
>
> > Since Python isn't stringly typed,
>
> I expect this is an innocent typo, and you mean strictly.
>
> > single-dispatch isn't available per se. So is the "double-dispatch" Visitor pattern,
>
Yes, typo, I meant strictly.
> Wait, what?
> First of all, python is strictly typed in that every object has exactly
> one type, which is different from other types. So you can't do "1"+2, as
> you can in some other languages.
>
> Anyway, this is interesting: Tell me more about how Python's dynamic
> nature makes it impossible to do whatever you're trying to do. I'm
> baffled. What are you trying to do, anyway?
>
> > which is usually used
> > in OO systems to implement code generators. So, what is the de facto
> > method in Python to handle source code generation?
>
> WHOA! Now if that isn't a Gedankensprung. Also, I'm still very far from
> your train of thought, apparently: Now, the thing that code generators
> probably share is that they write code to files. It depends on what I'm
> trying to do of course, but I expect there's a good chance that if I
> wrote a code generator in Python, it wouldn't be particularly
> object-oriented at all.
Well, I'm most experienced in OO, so writing OO in Python seems like
the way to start with Python. The visitor pattern uses single-
dispatch, that is, it determines which method to call be the type of
object passed in. I did some reading and it turned out that Python
can't do it without some tricks (function decorators and 3rd party
code). For what I'm doing, I can't, or rather don't want to rely on
3rd party code (that has reasons). Thus, the visitor OO pattern must
be replaced by some other way.
As I expected, you already hinted a non-OO solution. Which is now that
*I* am wondering what that would look like...
Note, that I have an hierarchical object structure which I want to
iterate over, so using OO looked natural to me. If there's a better
approach, I'm all ears.
Karsten
Christian Heimes
> se. So is the "double-dispatch" Visitor pattern, which is usually used
> in OO systems to implement code generators. So, what is the de facto
> method in Python to handle source code generation?
Do you mean strongly typed langauge?
You are wrong, Python is a strongly typed language. Perhaps you are
confusing strong/weak with dynamic/static? These attributes are
orthogonal to each other. Python is a strongly and dynamicly typed language.
The visitor pattern is required for double dispatching in *some* OO
language like C++, to work around issues with inheritance and function
overloading. Python's OO works differently.
Christian
Karsten Wutzke
> Yes, typo, I meant strictly.
>
Damn, I mean strongly. At least not for identifying which methods to
call depending on the type/s.
Karsten
Thomas Jollans
Well, yes: the name of a function or method refers to a single callable
object and piece of code. if you care about the type of the argument,
you must say so explicitly:
class A:
def dothing(self, obj):
if isinstance(obj, str):
self.dostringthing(obj)
elif isinstance(obj, (int,float)):
self.donumberthing(obj)
else:
self.dogenericthing(obj)
# ...
while python doesn't have C++-style function overloading, its
alternative also doesn't have the limitations that come with it.
Stefan Behnel
> Well, I'm most experienced in OO, so writing OO in Python seems like
> the way to start with Python. The visitor pattern uses single-
> dispatch, that is, it determines which method to call be the type of
> object passed in.
Well, then do that. Put the types into a dict and map them to the functions
to call, then call the function through the dict. That's a pretty common
way to do dispatching.
> Note, that I have an hierarchical object structure which I want to
> iterate over, so using OO looked natural to me. If there's a better
> approach, I'm all ears.
You speak in riddles, but my guess is that your problem is that you don't
want to dispatch mechanism to match only exact types but also subtypes. No
problem, just build your dict incrementally and add new types as they come
in. See this file for an example:
http://hg.cython.org/cython-devel/file/tip/Cython/Compiler/Visitor.py
Stefan
Stefan Behnel
>> Yes, typo, I meant strictly.
>
> Damn, I mean strongly. At least not for identifying which methods to
> call depending on the type/s.
I think you meant "statically typed".
http://c2.com/cgi-bin/wiki?StronglyTyped
http://www.c2.com/cgi/wiki?StaticTyping
Stefan
MRAB
> Karsten Wutzke, 15.07.2010 20:45:
>> the way to start with Python. The visitor pattern uses single-
>> dispatch, that is, it determines which method to call be the type of
>> object passed in.
>
> functions to call, then call the function through the dict. That's a
> pretty common way to do dispatching.
>
>
>> iterate over, so using OO looked natural to me. If there's a better
>> approach, I'm all ears.
>
> don't want to dispatch mechanism to match only exact types but also
> subtypes. No problem, just build your dict incrementally and add new
> types as they come in. See this file for an example:
>
> http://hg.cython.org/cython-devel/file/tip/Cython/Compiler/Visitor.py
>
types then it adds subtypes on demand:
def visit(self, obj):
try:
handler = self.dispatch_table[type(obj)]
except KeyError:
for disp_type, disp_func in self.dispatch_table.items():
if isinstance(obj, disp_type):
self.dispatch_table[type(obj)] = disp_func
handler = disp_func
else:
raise RuntimeError("Visitor does not accept object: %s"
% obj)
return handler(obj)
Matt McCredie
> So, what is the de facto method in Python to handle source code generation?
Take a look at the NodeVisitor class in the ast module in python 2.6+.
The visitor pattern is implemented in the python standard library.
Matt
Stefan Behnel
> Stefan Behnel wrote:
>> Karsten Wutzke, 15.07.2010 20:45:
>>> the way to start with Python. The visitor pattern uses single-
>>> dispatch, that is, it determines which method to call be the type of
>>> object passed in.
>>
>> functions to call, then call the function through the dict. That's a
>> pretty common way to do dispatching.
>>
>>
>>> iterate over, so using OO looked natural to me. If there's a better
>>> approach, I'm all ears.
>>
>> don't want to dispatch mechanism to match only exact types but also
>> subtypes. No problem, just build your dict incrementally and add new
>> types as they come in. See this file for an example:
>>
>> http://hg.cython.org/cython-devel/file/tip/Cython/Compiler/Visitor.py
>>
> Another variation: the dispatch table starts with entries for certain
> types then it adds subtypes on demand:
>
> def visit(self, obj):
> try:
> handler = self.dispatch_table[type(obj)]
> except KeyError:
> for disp_type, disp_func in self.dispatch_table.items():
> if isinstance(obj, disp_type):
> self.dispatch_table[type(obj)] = disp_func
> handler = disp_func
> else:
> raise RuntimeError("Visitor does not accept object: %s" % obj)
> return handler(obj)
Well, yes, that's basically what the code behind the above link does,
except that it follows the type hierarchy correctly to find the closest match.
Stefan
Ian Hobson
What feature of Python stops you writing the three parts of the visitor
pattern:
IIRC you need:
A tree walker that creates the visitor and walks the tree calling
node.visitFrom(visitor)
on each one in the required order.
The visitfrom(aVisitor) routines in each node type that calls
aVisitor.visitedMyNodeType(self)
where MyNodeType is, naturally different for each node type!
All the
def visitedNodeType(aNode): routines in visitor to generate the code.
Simples! No? :)
Ian
Ian Hobson
Ian Hobson
Carl Banks
Oh brother.
Around these parts, we consider the main use of most Design Patterns
to be to work around limitations of other languages. Visitor Pattern
is probably the worst example of it.
In Python it's completely unnecessary (at least in its boilerplate-
heavy incarnation as used in C++), and the fact that Python isn't
strongly typed, as you put it, is exactly the reason why.
Say you have a bunch of unrelated types that define a calculate
method, you have a variable x that could be any of these types.
Here's how you would do that in Python:
x.calculate()
Bam, that's it. Visitor Pattern in Python. You don't have to create
a bunch of homemade dispatching boilerplate like you do in C++.
Carl Banks
Stefan Behnel
> Around these parts, we consider the main use of most Design Patterns
> to be to work around limitations of other languages. Visitor Pattern
> is probably the worst example of it.
>
> In Python it's completely unnecessary (at least in its boilerplate-
> heavy incarnation as used in C++), and the fact that Python isn't
> strongly typed, as you put it, is exactly the reason why.
>
> Say you have a bunch of unrelated types that define a calculate
> method, you have a variable x that could be any of these types.
> Here's how you would do that in Python:
>
> x.calculate()
>
> Bam, that's it. Visitor Pattern in Python. You don't have to create
> a bunch of homemade dispatching boilerplate like you do in C++.
Well, you can do that in every OO language. It's not what the visitor
pattern is there for, though.
The code I referenced is from the Cython compiler, and we use it to "do
stuff" with the AST. The visitor pattern is actually a pretty common way to
bind code in a single place that does a certain thing to different parts of
a data structure. Without it, if you kept that code *inside* of the data
structure, you'd have to spill the type specific parts all over your code.
Stefan
Paul Rubin
> Since Python isn't stringly typed, single-dispatch isn't available per
> se. So is the "double-dispatch" Visitor pattern, which is usually used
> in OO systems to implement code generators. So, what is the de facto
> method in Python to handle source code generation?
A minute of web surfing found this:
http://chris-lamb.co.uk/2006/12/08/visitor-pattern-in-python/
Carl Banks
Ahh, so this aspect oriented programming is it.
I see your point, Visitor Pattern isn't necessary to work around the
"can't easily polymorph unrelated types" limitation, but could still
be necessary to work around "can't easily dispatch on methods not part
of the class" limitation. So, ok, Visitor Pattern maybe isn't the
worst one. My bad
Carl Banks
Michele Simionato
You ask about code generation and you already had answers in that
area, but let me talk a bit about a simpler topic, traversing a
hierarchical file system. I think this is relevant (even if not
answering your question) if you want to get familiar with the Python
way. In the old days, the way to traverse a file system was through
the os.path.walk function. Here is what the docs say (from
http://docs.python.org/library/os.path.html):
"""
os.path.walk(path, visit, arg)
Calls the function visit with arguments (arg, dirname, names) for each
directory in the directory tree rooted at path (including path itself,
if it is a directory). The argument dirname specifies the visited
directory, the argument names lists the files in the directory (gotten
from os.listdir(dirname)). The visit function may modify names to
influence the set of directories visited below dirname, e.g. to avoid
visiting certain parts of the tree. (The object referred to by names
must be modified in place, using del or slice assignment.)
"""
As you see the documentation make explicit reference to the visitor
pattern.
However a note below says:
"""
This function is deprecated and has been removed in 3.0 in favor of
os.walk().
"""
In other word, the visitor pattern is *not* the Pythonic way to solve
this
problem. The Pythonic way is to use os.walk, which converts the nested
structure in a flat structure. From the docs
(http://docs.python.org/library/os.html):
"""
This example displays the number of bytes taken by non-directory files
in each directory under the starting directory, except that it doesn’t
look under any CVS subdirectory:
import os
from os.path import join, getsize
for root, dirs, files in os.walk('python/Lib/email'):
print root, "consumes",
print sum(getsize(join(root, name)) for name in files),
print "bytes in", len(files), "non-directory files"
if 'CVS' in dirs:
dirs.remove('CVS') # don't visit CVS directories
"""
There is a big conceptual difference between os.path.walk and os.walk.
The first works like a framework: you pass a function to it and
os.path.walk
is in charging of calling it when needed. The second works like a
library:
os.walk flattens the hierarchical structure and then you are in charge
of
doing everything you wish with it.
os.walk is the Pythonic way, and you suggested to follow that
approach;
for instance elementTree and lxml (libraries for parsing XML data)
work
exactly that way. Actually one of the motivating examples for the
introduction of generators in Python was their use in flattening
data structure, i.e. exactly the pattern used by os.walk.
The message is stop thinking like in Java and start using idiomatic
Python. We are here to help.
Michele Simionato
Stefan Behnel
> On Jul 15, 8:33 pm, Stefan Behnel wrote:
>> The code I referenced is from the Cython compiler, and we use it to "do
>> stuff" with the AST. The visitor pattern is actually a pretty common way to
>> bind code in a single place that does a certain thing to different parts of
>> a data structure. Without it, if you kept that code *inside* of the data
>> structure, you'd have to spill the type specific parts all over your code.
>
> Ahh, so this aspect oriented programming is it.
Never thought about it that way, but you have a point there. It's pretty
much the same idea as AOP, but without any of those huge and feature
drooling code injection frameworks.
Stefan
Jean-Michel Pichavant
JM
Thomas Jollans
stringly typed sounds like "everything is a string" - doesn't Tcl do
that ? ^^
Mick Krippendorf
> The visitor pattern uses single-dispatch, that is, it determines
Say, in Python, I have an object o and want to call one of it's methods,
say m. Then which of possibly many methods m to call is determined by
the type of o, and nothing else (at least without further magic) -
hence, it is single dispatch. The VP uses two single dispatch calls (one
being a callback) to accomplish double dispatching.
Java has a form of multiple dispatch through function overloading. In
fact, it's still single dispatch, because which of the targets
overloaded methods gets called is determined at compile time by the
staticly known types of the methods parameters, AKA the formal parameter
types.
Anyway. Although VP *uses* double dispatch, it does not necessarily rely
on function overloading. In Java the VP is most often implemented like this:
<java>
interface IASTNode {
void accept(IASTVisitor);
}
class IfNode implements IASTNode {
void accept(IASTVisitor visitor) {
visitor.visit(this);
}
}
class ElseNode implements IASTNode {
void accept(IASTVisitor visitor) {
visitor.visit(this);
}
}
interface IASTVisitor {
void visit(IfNode node);
void visit(ElseNode node);
...
}
class PrettyPrinter implements IASTVisitor {
public void visit(IfNode n) {
...
}
public void visit(ElseNode n) {
...
}
}
</java>
but it could as well be implemented like this:
<java>
interface IASTNode {
void accept(IASTVisitor);
}
class IfNode implements IASTNode {
void accept(IASTVisitor visitor) {
visitor.visitIfNode(this);
}
}
class ElseNode implements IASTNode {
void accept(IASTVisitor visitor) {
visitor.visitElseNode(this);
}
}
interface IASTVisitor {
void visitIfNode(IfNode node);
void visitElseNode(ElseNode node);
...
}
class PrettyPrinter implements IASTVisitor {
public void visitIfNode(IfNode n) {
...
}
public void visitElseNode(ElseNode n) {
...
}
}
</java>
If Java were *really* a multiple dispatch language, it wouldn't be
necessary to repeat the accept-code for every subclass. Instead a single
accept method in the base class would suffice. In fact, with true
multiple dispatch VP wouldn't even be needed.
Regards,
Mick.
Mick Krippendorf
Am 16.07.2010 09:52, Michele Simionato wrote:
> [os.path.walk vs os.walk]
> There is a big conceptual difference between os.path.walk and os.walk.
> The first works like a framework: you pass a function to it and
> os.path.walk is in charging of calling it when needed. The second works
> like a library: os.walk flattens the hierarchical structure and then
> you are in charge of doing everything you wish with it.
>
> os.walk is the Pythonic way, and you suggested to follow that
> approach; for instance elementTree and lxml (libraries for parsing XML
> data) work exactly that way. Actually one of the motivating examples for
> the introduction of generators in Python was their use in flattening
> data structure, i.e. exactly the pattern used by os.walk.
The Visitor Pattern isn't about traversing, so they could as well have
had an os.walk() that took a visitor object. Instead, it's about the
untangling of unrelated stuff. Not the traversing vs. everything else -
that's what iterators are for, like you said. But if you want to be able
to add new types of operations without ever touching the code of the
objects on which to apply those operations, then the VP is an easy way
to accomplish things:
<python>
class IfNode:
def apply(self, operation):
operation.handleIfNode(self)
...
class ElseNode:
def apply(self, operation):
operation.handleElseNode(self)
...
class PrettyPrinter:
def handleIfNode(self, if_node):
# print if_node pretty
def handleElseNode(self, else_node):
# print else_node pretty
...
class Interpreter:
def handleIfNode(self, if_node):
# interpret if_node
def handleElseNode(self, else_node):
# interpret else_node
...
class AST:
def apply(self, operation):
# apply operation to all nodes
...
some_ast = ...
some_ast.apply(PrettyPrinter())
some_ast.apply(Interpreter())
</python>
The traversing in AST.apply() is not really part of the pattern, it
could also be done in the client code. The VP lives in the relation
between the ...Node and the operation classes. It Encapsulates What
Varies and helps to uphold the Open/Closed Principle, because to add new
operations one does not need to touch the ...Node classes. It implements
double dispatching in a single dispatch language.
Regards,
Mick.
Mark Lawrence
Boilerplate, boilerplate everywhere, but not a beer to drink.
Hope everyone at EuroPython is having a good time.
Kindest regards.
Mark Lawrence.
Mick Krippendorf
That's Java for ya.
<python>
class ASTNode:
def accept(self, visitor):
getattr(visitor, self.__class__.__name__)(self)
class IfNode(ASTNode):
... # inherits generic accept method
class ElseNode(ASTNode):
... # inherits generic accept method
class PrettyPrinter:
def IfNode(self, node):
...
def ElseNode(self, node):
...
</python>
Regards,
Mick.