Using Polymorphism instead of conditionals when programming(theshyam.com)
theshyam.com
Using Polymorphism instead of conditionals when programming
http://theshyam.com/2009/09/using-polymorphism-instead-of-conditionals/
8 comments
Replace all conditionals with polymorphism:
The way Smalltalk does things, IIRC.
Syntactically yes. To make it fast the compiler recognizes it as a special case. I think that there is no special case for this in Self: the self compiler can optimize this away (even if you write your own True and False). But maybe I didn't remember that correctly.
Here let me add some syntax sugar:
if(condition) { print "true" } else { print "false" }
if(condition) { print "true" } else { print "false" }
If the call-able values are looked up dynamically, both branches will always run up to call().
I don't understand what you mean. Can you elaborate?
Well, I'm guessing that in your Python-ish pseudocode any code wrapped in curly braces is a lambda. I missed that when I commented.
What I meant was that if you had code that ran to look up / generate those blocks, rather than just a literal block, it would always process both (even though only one is needed).
What I meant was that if you had code that ran to look up / generate those blocks, rather than just a literal block, it would always process both (even though only one is needed).
This is pretty good actually, because one thing that always bothered me about previous articles that said the same thing, was that those articles didn't have any concrete examples of how you might implement a class hierarchy instead of a conditional. This one has exactly that, good work.
This article makes me nervous. I think that the example given is somewhat overengineered for the task of representing a tree with values and operations, and I don't think that it's good to jump immediately to "let's design an object model with abstract operations and operands using polymorphism to sort out the different behavior" for this problem and other small problems like this. It's a fun exercise in modeling, but produces code that is often just more than you need or want.
There's a time and place for good OO, but knowing when not to apply it seems like an equally useful skill as knowing when to apply it.
There's a time and place for good OO, but knowing when not to apply it seems like an equally useful skill as knowing when to apply it.
Agreed. You still need a nest of conditionals when you populate the tree, and you need a separate class for each operations - so what's the advantage of using polymorphism here?
The disadvantage of poly here is more code and more classes. Yes, you can add a new operator without modifying the node class - but now you must modify the tree-populating code instead.
The disadvantage of poly here is more code and more classes. Yes, you can add a new operator without modifying the node class - but now you must modify the tree-populating code instead.
Consider a few of the benefits not mentioned in the article:
- You have reduced the cyclomatic complexity of each class, which makes the code less fragile and easier to unit test.
- When adding a new operator, you are now forced to implement everything it needs to work. If you don't define a method, it won't compile. This is not the case with a long list of if/else statements.
- "You still need a nest of conditionals when you populate the tree..." This is true, but now all the conditionals are in one place, rather than two (in their example, toString and evaluate). Again, this will make testing easier.
- You have reduced the cyclomatic complexity of each class, which makes the code less fragile and easier to unit test.
- When adding a new operator, you are now forced to implement everything it needs to work. If you don't define a method, it won't compile. This is not the case with a long list of if/else statements.
- "You still need a nest of conditionals when you populate the tree..." This is true, but now all the conditionals are in one place, rather than two (in their example, toString and evaluate). Again, this will make testing easier.
Your second point is actually a feature, and is equivalent to structural pattern matching in languages with algebraic types not allowing you to have unspecified cases.
I think he was advertising this as a feature. Failing to compile is much better than hitting your "this can't happen" conditional at runtime.
Absolutely. One of the advantages of static typing (NOT starting a type war here, oh gods) is that you can transform error conditions from the run-time to the compile-time world. Earlier failure = cheaper failure, so this is great.
I try to take this as far as I can. For instance, when writing Servlet code in Java, I define all my request parameter names in an enum, so that I can never misspell any lest the compiler tell me.
I try to take this as far as I can. For instance, when writing Servlet code in Java, I define all my request parameter names in an enum, so that I can never misspell any lest the compiler tell me.
You're right, I didn't understand his intentions.
you can use factories for creation, which abstracts the conditionals into nice bundles. you can in a sense do factories regardless of having classes, in that you can always factor code into happy utility methods. the insight is thinking about how much code has to change per update. there are numerous possible situations and conclusions.
I do not represent 2 + 3 * 5 as a binary tree internally. Of course, I encounter it in a parse tree when parsing, but as soon as I do I transform it into a mathematical expression object.
I don't actually use inheritance, but composition. Who contains who depends on the grammar. The expression 2 + 3 * 5 becomes (using a pseudo-object shorthand) Add(2, Mult(3, 5)).
It looks something like this: http://github.com/scotts/cellgen/blob/master/src/math_exprs.... There is an interface that all of the classes share, I just haven't bothered to abstract it out. (Partially because it often changes, and I've never need to refer to that interface explicitly.)
I get his point, of course, it's just that the solution he's looking for isn't the most natural way for me to solve the general problem.
I don't actually use inheritance, but composition. Who contains who depends on the grammar. The expression 2 + 3 * 5 becomes (using a pseudo-object shorthand) Add(2, Mult(3, 5)).
It looks something like this: http://github.com/scotts/cellgen/blob/master/src/math_exprs.... There is an interface that all of the classes share, I just haven't bothered to abstract it out. (Partially because it often changes, and I've never need to refer to that interface explicitly.)
I get his point, of course, it's just that the solution he's looking for isn't the most natural way for me to solve the general problem.
"Polymorhism" in the article is just a workaround for Java's lack of a real type system. An alternate representation:
data Op a = Constant a | Add (Op a) (Op a) | Multiply (Op a) (Op a)
deriving (Show)
evaluate :: Num a => Op a -> a
evaluate (Constant x) = x
evaluate (Add l r) = evaluate l + evaluate r
evaluate (Multiply l r) = evaluate l * evaluate rI actually realized that relationship about a month ago, but not too many people read the related article: http://news.ycombinator.com/item?id=779689
It is easy to see the relationship if you have used CLOS. Consider:
In either case, it eventually compiles down to something like:
In the end, pattern matching and polymorhism are just syntax sugar on top of "if". But it's syntax sugar that makes the code very easy to read and write correctly. (The advantage is that you write a method for each type, which means one lexical block only knows about the specifics of the operation is is performing; no need for Add to know about Mulitply, for example.)
(defgeneric evaluate (op))
(defmethod evaluate ((op add-op)) ...)
(defmethod evaluate ((op mult-op)) ...)
(defmethod evaluate ((op const-op)) ...)
class AddOp { method evaluate { ... }}
...
In either case, it eventually compiles down to something like:
(defun evaluate (op)
(typecase op (add-op <add>)
(mult-op <mult>)
(const-op <const>))
In the end, pattern matching and polymorhism are just syntax sugar on top of "if". But it's syntax sugar that makes the code very easy to read and write correctly. (The advantage is that you write a method for each type, which means one lexical block only knows about the specifics of the operation is is performing; no need for Add to know about Mulitply, for example.)
Dynamic dispatch is not syntactic sugar for a if-cascade. It is normaly implemented via vtables. If you try to do this in a language without polymorphism (e.g. C) you have to do this by hand and keep track of your vtable layout (third function pointer is 'evaluate' ...). Your example is nice to describe the effect of dynamic dispatch, but misleading about the mechanism.
Polymorphism is the core of OOP, which consequently means that Haskell is OO.
Polymorphism is the core of OOP, which consequently means that Haskell is OO.
It is normally implemented via vtables.
OK, irrelevant. We are not discussing runtime implementation, we are discussing language semantics. A table lookup and a cascade of if statements are semantically the same. Value in, result out.
Polymorphism is the core of OOP, which consequently means that Haskell is OO.
You're going to have to explain this with more than one statement. "OOP" is a meaningless expression. "Haskell is OO" is similarly meaningless.
My Haskell example shows that functions can be polymorphic over values. OOP is polymorphic over types. Haskell typeclasses provide polymorphism over classes of types.
Not the same. But similar expressive power is possible either way.
OK, irrelevant. We are not discussing runtime implementation, we are discussing language semantics. A table lookup and a cascade of if statements are semantically the same. Value in, result out.
Polymorphism is the core of OOP, which consequently means that Haskell is OO.
You're going to have to explain this with more than one statement. "OOP" is a meaningless expression. "Haskell is OO" is similarly meaningless.
My Haskell example shows that functions can be polymorphic over values. OOP is polymorphic over types. Haskell typeclasses provide polymorphism over classes of types.
Not the same. But similar expressive power is possible either way.
I don't think OOP is meaningless. It's just diffused by too much talking. For me OOP essentially means polymorphism and here is an article i wrote about that: http://beza1e1.tuxen.de/articles/oop.html
My Haskell knowledge is superficial so i'll keep my mouth shut about the various kinds of polymorphism you describe.
My Haskell knowledge is superficial so i'll keep my mouth shut about the various kinds of polymorphism you describe.
"For me OOP essentially means" etc: that's the key. OOP means different things to different people. So the term is confusing and people who seek clarity want to avoid it.
[deleted]
I can't see a relationship between polymorphism and structural pattern matching. Both could be label "dynamic dispatch", but the mechanism is very different. While polymorphism can be implemented efficiently via vtables, i don't know of a method to this with general pattern matching.
Vtables means just one indirection thus no more than one more memory access. Pattern matching is like parsing.
Vtables means just one indirection thus no more than one more memory access. Pattern matching is like parsing.
There's a relationship in the sense that they can both be used to solve the same problem, and it's possible to write a function that generates one from the other.
Better yet:
newtype Node a = (a, string)
op :: (a -> b -> c) -> string -> node a -> Node b -> Node c
op (<>) str left right = (fst left <> fst right,
"(" ++ snd left ++ " " ++ str ++ " " ++ snd right ++ ")")
plus = op (+) "+"
mult = op (*) "*"
minus = op (-) "-"
constant x = (x, show x)
Type systems have their uses, but just pattern matching is sufficient here. In Prolog:
eval(const(X), X).
eval(add(L, R), S) :- eval(L, LV), eval(R, RV), S is LV + RV.
eval(mul(L, R), P) :- eval(L, LV), eval(R, RV), P is LV * RV.
?- eval(const(6), Z).
Z = 6.
?- eval(mul(const(3), add(const(71), const(9))), Z).
Z = 240.You are right. This really has nothing to do with types.
Java uses types for pattern matching since that's all the language allows pattern matching on. (Common Lisp is similar, but also has eql qualifiers.)
The type system can be useful for more complex cases. Eventually you might have a good reason to represent each operation with its own type. In this case, typeclasses can remove redundant code. (For example, if you write a lazy evaluator for each type of operation, you can get the eager evaluator "for free", implemented in terms of the lazy evaluation in the typeclass definition. etc., etc. I am too tired to decide how this would happen in Java, but my gut instinct is "not cleanly".)
Java uses types for pattern matching since that's all the language allows pattern matching on. (Common Lisp is similar, but also has eql qualifiers.)
The type system can be useful for more complex cases. Eventually you might have a good reason to represent each operation with its own type. In this case, typeclasses can remove redundant code. (For example, if you write a lazy evaluator for each type of operation, you can get the eager evaluator "for free", implemented in terms of the lazy evaluation in the typeclass definition. etc., etc. I am too tired to decide how this would happen in Java, but my gut instinct is "not cleanly".)
Right. If you're going to push that sort of checking on to the type system, then at least have a smart one.
I would answer the question in my best alan partridge voice and say "but I'm using smalltalk you bastards!"
Google posted a tech talk about this a while ago: http://www.youtube.com/watch?v=4F72VULWFvc
which is more comprehensive than the posted article.