5 ms·

I consider expression problem pretty much solved. There are two composable solutions: (1) multi-methods (described in this article), suitable mainly for dynamic

• eliben 11y ago
  I looked into type classes in Haskell, but my understanding was they they provide static, not dynamic dispatch. Is that wrong? FWIW I've also been wondering about Go. On one hand in Go you don't have to pre-declare which interfaces your type is implementing. OTOH you can't just extend an existing type from a different package with new methods, AFAIU
  • tomp 11y ago
    Depends what you mean by "static/dynamic dispatch". Strictly speaking, the only example of static dispatch is when the called function is known at compile time. Dynamic dispatch allows selection of the function being called at runtime; either via inheritance (the called method depends on the exact subclass of the object), or via typeclasses (the called method depends on the typeclass passed along with the values - e.g. the addition typeclass will be different for a list of ints and a list of matrices).
  • akavi 11y ago
    Nope, type classes use dynamic dispatch (I might be wrong, but I think higher kinded types are impossible with pure static dispatch.).
    • Chattered 11y ago
      They can be implemented via method dictionaries but, sans type system extensions, polymorphic recursion and separate compilation, all uses of a type variable constrained by a type class could, in principle, be monomorphised and the dictionaries eliminated. This is not true of dynamic dispatch.
      • naasking 11y ago
        That's true, but I believe less relevant than most would think. Most of the "dynamic dispatching" people talk about could be similarly monomoprhized. The only real dynamic dispatch occurring in most programs is due to dynamic code loading (separate compilation from your post).
        • Chattered 11y ago
          I disagree, and since we are talking about the expression problem, we should not be conflating dynamic dispatching code which could be statically resolved from dynamic dispatching code which is necessarily dynamic. A standard use-case of dynamic dispatch is for representing different types of term in a parse tree, where we want to dispatch on nodes according to type. This sort of dispatch cannot be monomorphised, since the the exact callee depends on the shape of the trees being traversed and this almost certainly cannot be figured out statically. In Haskell, you do not do this sort of dispatch with typeclasses, but instead use ADTs. When it comes to the expression problem, the tradeoff is that ADTs allow you to easily write new sorts of traversal but do not allow you to extend the tree type in a modular way. By contrast, single dispatch OO allows you to easily extend the tree type by providing new classes to implement the traversal methods, at the cost that you cannot easily define new traversals.
          • naasking 11y ago
            > we should not be conflating dynamic dispatching code which could be statically resolved from dynamic dispatching code which is necessarily dynamic. This is exactly what I said: most of what people call "dynamic dispatching" is not truly dynamic, and the use of dispatching code is merely an implementation detail. > In Haskell, you do not do this sort of dispatch with typeclasses, but instead use ADTs. Except you can, and this is one way to solve the expression problem in Haskell, ie. by lifting constructors to their own types with pattern matching functions lifted to type classes. At which point we come full circle: most uses of ADTs can also be monomorphized and so are not dynamically dispatched either. Dynamic dispatches then occur only on input at runtime to select the type being instantiated (and so the type class being dispatched into).
  • deleted 11y ago
    [deleted]
• kibwen 11y ago
  Rust's implementation of "type classes" (bounded generics) guarantees monomorphization and therefore static dispatch, so there's zero time overhead to using them. But they're also less expressive than type classes in other languages.
  • pron 11y ago
    If you guarantee static dispatch, then you haven't solved the expression problem, which requires some sort of dynamic dispatch (even a switch/pattern match). The only way to address the expression problem and provide zero time overhead in practice (though it can't be guaranteed) is with a JIT/profile-guided optimization. This, BTW, is why I find Rust's use of the term "zero-cost abstractions" confusing. Where Rust guarantees zero-cost it does so for weak abstractions only, and where it provides stronger abstractions, their cost may be higher than in other languages (because Rust's compiler is still behind on optimizations). It's a little like a restaurant advertising "free food", when they're really only offering free popcorn at the bar, while their steaks are rather pricey. It may be a great offering, but the copy is a little confusing.
    • kibwen 11y ago
      Hey, I'm not the one claiming that Rust solves the expression problem. :) > where it provides stronger abstractions, their cost may > be higher than in other languages What is this referring to? I can't think of anything in Rust that matches this description, unless you're referring to something like e.g. devirtualization via JIT compilation. Rust's abstractions are actually supremely impressive IMO; just yesterday I was marvelling at how `(0..x).fold(0, |sum, i| sum + i)` (which involves an external iterator, a generic function, and a closure) gets compiled down to the closed-form `((x - 1) * (x - 2) / 2) + x - 1` (which admittedly slightly misses Gauss' famous `(x * (x + 1)) / 2`, but that might just be nitpicking :P ).
      • pron 11y ago
        > unless you're referring to something like e.g. devirtualization via JIT compilation. Yep. > I was marvelling at how `(0..x).fold(0, |sum, i| sum + i)` (which involves an external iterator, a generic function, and a closure) gets compiled down to the closed-form `((x - 1) * (x - 2) / 2) + x - 1` That is very cool, but once iterators are turned into loops (perhaps they're even treated specially) and the closure inlined (I would expect both from a decent compiler), it is a rather straightforward optimization (a loop with a constant step). OTOH, a JIT can do this: https://twitter.com/ChrisGSeaton/status/619885182104043520 https://twitter.com/ChrisGSeaton/status/619885182104043520