4 ms·

But, a series of pattern matching expressions can compile down to a bunch of sealed/final classes that descend from a common base class. In that case, it would

But, a series of pattern matching expressions can compile down to a bunch of sealed/final classes that descend from a common base class. In that case, it would still end up using a vtable[1]. I think this is how it works in F# and Scala. [1] I think that the JITs for the CLR and JVM can do better than vtables in the cases of sealed/final classes.

seanmcdirmid 12y ago
I am sure it doesn't work with way in either scala or F#. You can use classes to represent structure, but the matching is still extrinsic and can't use a table given the flexibility of both languages (you don't just match on class).
- noblethrasher 12y ago
  Just curious… why not? Isn't a class definition just a type constructor? For instance, if I have a class, Foo, with three types of fields: int, bool, and string, isn't that the same as: Foo of int * bool * string I don't have a full PC handy, but, while learning F# a few years ago, I remember using Reflector to analyze an assembly generated by FSC.exe and the pattern match turned into a class hierarchy. It may not work for all kinds of pattern matching, but that seems like the most straightforward way of handling sum types. What am I missing?
  - seanmcdirmid 12y ago
    I doubt that was what was going on, but I can't find any documentation right now on how F# optimizes case matches. If it was doing that, it would have to apply those classes to all instances of the patterns, which seems unlikely in the face of separate compilation as "Foo of int * bool * string" could be constructed in a far away place. Well, if Foo was a local type that wouldn't escape, perhaps they could optimize it in the module, but it still seems unlikely. OO languages have trouble optimizing constructs such as interfaces (and other forms of multiple inheritance) because the v-table is no longer very linear. Now throw in arbitrary predicates and you are pretty much back to linear search. Probably the state of the art can be found in GHC, but even they probably fall back to linear in a lot of cases.
    - noblethrasher 12y ago
      Looks like you're correct; I just examined some F# code in LINQPad 4, and the IL has a bunch of `isinst` instructions to check the type at runtime, and no `callvirts` to the one pattern matching expression that I created. https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd

seanmcdirmid 12y ago

I am sure it doesn't work with way in either scala or F#. You can use classes to represent structure, but the matching is still extrinsic and can't use a table given the flexibility of both languages (you don't just match on class).

noblethrasher 12y ago
Just curious… why not? Isn't a class definition just a type constructor? For instance, if I have a class, Foo, with three types of fields: int, bool, and string, isn't that the same as: Foo of int * bool * string I don't have a full PC handy, but, while learning F# a few years ago, I remember using Reflector to analyze an assembly generated by FSC.exe and the pattern match turned into a class hierarchy. It may not work for all kinds of pattern matching, but that seems like the most straightforward way of handling sum types. What am I missing?
- seanmcdirmid 12y ago
  I doubt that was what was going on, but I can't find any documentation right now on how F# optimizes case matches. If it was doing that, it would have to apply those classes to all instances of the patterns, which seems unlikely in the face of separate compilation as "Foo of int * bool * string" could be constructed in a far away place. Well, if Foo was a local type that wouldn't escape, perhaps they could optimize it in the module, but it still seems unlikely. OO languages have trouble optimizing constructs such as interfaces (and other forms of multiple inheritance) because the v-table is no longer very linear. Now throw in arbitrary predicates and you are pretty much back to linear search. Probably the state of the art can be found in GHC, but even they probably fall back to linear in a lot of cases.
  - noblethrasher 12y ago
    Looks like you're correct; I just examined some F# code in LINQPad 4, and the IL has a bunch of `isinst` instructions to check the type at runtime, and no `callvirts` to the one pattern matching expression that I created. https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd