Optimizing pattern matching for non-case class extractors?

[Shelby Moore]

I read[1]:

"The current Scala implementation also compiles pattern matching over case
classes into more efficient code than pattern matching using extractors.
One reason for this is that different case classes are known not to
overlap, i.e. given two patterns C(...) and D(...) where C and D are
different case classes, we know that at most one of the patterns can
match. The same cannot be assured for different extractors."

I understand it is impossible to do `C with D` for any class because in
Scala's multiple inheritance linearization, only one may be a (concrete or
abstract) class and the rest on the inheritance tree must be traits.

So it seems the above optimization could be done for extractors that input
a class (not just a case class) and return an Option of the same class,
and where it is known for example that C and D don't extend one or the
other? Correct? Does the pattern matcher do this now?

Additionally traits can be joined into a conjunction employing `with`, but
what if there was some keyword that could be prefixed to a base
(supertype) trait (e.g. supertype of C and D when C and D are traits) to
indicate that subtypes can never be joined into the same conjunction, then
the above said optimization of pattern matching could also apply?

Additionally, thus it seems not only do we need a first-class disjunction
for the significant use-case I noted today:

https://groups.google.com/d/msg/scala-debate/LWBz3-Q0pNI/MzuU-5HgFyQJ

Then we also need to be able to declare a disjunction that can only
reference instances that are not conjunctions of the types of the
disjunction (so we can most efficiently downcast them with match-case
pattern matching).

P.S. I am at the forehead on the keyboard, drooping eyelids held open with
toothpicks, so if the above doesn't make sense, please tell me.

[1] Case Classes and Extractors, pg 15. of Matching Objects With Patterns,
Emir, Odersky, Williams

[Shelby]

On Sunday, September 15, 2013 10:37:08 PM UTC+8, Shelby wrote:

I read[1]:

"The current Scala implementation also compiles pattern matching over case
classes into more efficient code than pattern matching using extractors.
One reason for this is that different case classes are known not to
overlap, i.e. given two patterns C(...) and D(...) where C and D are
different case classes, we know that at most one of the patterns can
match. The same cannot be assured for different extractors."

I understand it is impossible to do `C with D` for any class because in
Scala's multiple inheritance linearization, only one may be a (concrete or
abstract) class and the rest on the inheritance tree must be traits.

So it seems the above optimization could be done for extractors that input
a class (not just a case class) and return an Option of the same class,
and where it is known for example that C and D don't extend one or the
other? Correct? Does the pattern matcher do this now?

Ugh, I was obviously too sleepy when I wrote that.

I meant to write where the extractor's Option returns a tuple of the same types as the class's constructor parameters. Actually it doesn't matter to my point what is returned by the extractor.

 

Additionally traits can be joined into a conjunction employing `with`, but
what if there was some keyword that could be prefixed to a base
(supertype) trait (e.g. supertype of C and D when C and D are traits) to
indicate that subtypes can never be joined into the same conjunction, then
the above said optimization of pattern matching could also apply?

I meant to equate with the above, so the returned Option for a trait's extractor is a tuple of the return types of the methods (in top-bottom = left-right order) of the trait which don't have input parameters, i.e. function type () => Any. Noting that such methods of a trait can be implemented with a class's constructor parameters if the class extends the trait. Nevertheless as I state above, I don't think the extractor's returned type is relevant to my suggestion for further optimization.

[Shelby]

On Sunday, September 15, 2013 10:37:08 PM UTC+8, Shelby wrote:

I read[1]:

"The current Scala implementation also compiles pattern matching over case
classes into more efficient code than pattern matching using extractors.
One reason for this is that different case classes are known not to
overlap, i.e. given two patterns C(...) and D(...) where C and D are
different case classes, we know that at most one of the patterns can
match. The same cannot be assured for different extractors."

I understand it is impossible to do `C with D` for any class because in
Scala's multiple inheritance linearization, only one may be a (concrete or
abstract) class and the rest on the inheritance tree must be traits.

So it seems the above optimization could be done for extractors that input

a class (not just a case class) ...,

and where it is known for example that C and D don't extend one or the
other? Correct? Does the pattern matcher do this now?

Seems this optimization could also be done for extractors that input an Option of a class:

https://groups.google.com/d/msg/scala-language/TJVDYGNalAM/mcEPRsiuzIoJ

Because we know Option is sealed. 

[Jason Zaugg]

You might be interested in what we're baking for Scala 2.11:

https://github.com/scala/scala/pull/2848

-jason

[Shelby]

I am doing a dancing baby ;) 

[Jason Zaugg]

On Wed, Sep 18, 2013 at 10:01 AM, Shelby <she...@coolpage.com> wrote:

You might be interested in what we're baking for Scala 2.11:

https://github.com/scala/scala/pull/2848

-jason

I am doing a dancing baby ;) 

Off topic for this thread (I can't locate the right one), you might also like to take a look at a few other projects aiming for a neater syntax for applicative functors via Scala macros:

https://github.com/scala/async

https://github.com/pelotom/effectful

https://github.com/aztek/scala-workflow

Note that the last one depends on a now-abandoned experimental flavour of macros (untyped macros).

-jason