4 ms·
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 math
by scott_s 17y ago
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.h 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.
- jrockway 17y ago"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 r
- scott_s 17y agoI actually realized that relationship about a month ago, but not too many people read the related article: http://news.ycombinator.com/item?id=779689 http://news.ycombinator.com/item?id=779689
- jrockway 17y agoIt is easy to see the relationship if you have used CLOS. Consider: (defgeneric evaluate (op)) (defmethod evaluate ((op add-op)) ...) (defmethod evaluate ((op mult-op)) ...) (defmethod evaluate ((op const-op)) ...) This is the same as class AddOp { method evaluate { ... }} ... and so on. In either case, it eventually compiles down to something like: (defun evaluate (op) (typecase op (add-op <add>) (mult-op <mult>) (const-op <const>)) which is just an if statement with some sugar on top. 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.)
- beza1e1 17y agoDynamic 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.
- jrockway 17y agoIt 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.
- beza1e1 17y agoI 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 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.
- cema 17y ago"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 17y ago[deleted]
- beza1e1 17y agoI 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.
- scott_s 17y agoThere'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.
- loup-vaillant 17y agoBetter 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) I don't even need eval: Haskell is non strict!
- silentbicycle 17y agoType 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.
- jrockway 17y agoYou 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".)
- silentbicycle 17y agoRight. If you're going to push that sort of checking on to the type system, then at least have a smart one.