Language virtualizing for pattern matching with the virtualized pattern matcher?

[Paolo G. Giarrusso]

Hi all,

it seems that the virtualized pattern matcher in 2.10.0-M{5,6} does not support virtualization so well, given the compile errors which I show in https://gist.github.com/3299381 (with associated source code) and explain below.

Warning: the rest of the mail assumes extreme familiarity with Scala-virtualized and Lightweight Modular Staging (LMS).

Given such definitions:

type Rep[+T]

object __match ...

and all the associated code needed for LMS, I'd like to virtualize code like this:

def test3(i: Rep[Int]): Rep[String] = i match { case j => "foo3: " + j }

I've seen the testcases in the compiler distribution, with code like

def test3(i: Int): Rep[String] = i match { case j => "foo3: " + j }

(altered from test/files/run/virtpatmat_staging.scala), but the type difference is crucial (I can't use the latter test3 inside a virtualized expression).

I think my goal is reasonable because of this example from virtualization-lms-core:

        println("NOTE: doesn't work yet :-(")

        def test = repInt(7) match { case 5 => "foo" case _ => "bar" }

given: 

implicit def repInt(t: Int): Rep[Int] = ...

(https://github.com/TiarkRompf/virtualization-lms-core/blob/delite-develop/test-src/epfl/test4-functions/TestPatMat.scala#L72)

My first question is whether this code is indeed supposed to work. If yes, my second question is when people plan to get it fixed, since this code currently does not typecheck. My last question is whether macro expansion runs before or after 

However, with -M5 or -M6, this code does not even typecheck. The error message below comes from the first example - the second one fails similarly. Notice how the compiler mentions Rep[Rep[Int]] instead of Rep[Int].

virtpatmat_staging-altered.scala:34: error: type mismatch;

 found   : Intf.this.Rep[Intf.this.Rep[Int]] => Intf.this.M[String]

 required: Intf.this.Rep[Int] => Intf.this.M[?]

 def test3(i: Rep[Int]) = i match { case j => "foo3: " + j } //type error!

                          ^

one error found

An additional note. I wonder if, within such code:

def test3(i: Int): Rep[String] = i match { case j => "foo3: " + j }

the reference to i was supposed or not to be implicitly converted to repInt(i), that is, if the above line was supposed or not to expand into:

def test3(i: Int): Rep[String] = repInt(i) match { case j => "foo3: " + j }

Best regards,
Paolo

[Adriaan Moors]

sorry, I'm swamped right now and can't go into details,

but here's a staging example from the test suite: https://github.com/scala/scala/blob/master/test/files/run/virtpatmat_staging.scala

[Paolo Giarrusso]

On Thu, Aug 9, 2012 at 9:36 AM, Adriaan Moors <adriaa...@epfl.ch> wrote:
> sorry, I'm swamped right now and can't go into details,
> but here's a staging example from the test suite:
> https://github.com/scala/scala/blob/master/test/files/run/virtpatmat_staging.scala

I understand, and thanks for the answer, but I already looked into it
(it's the first example I mention below), and it does not do what I
need.
Best,
Paolo

--
Paolo Giarrusso - Ph.D. Student
http://www.informatik.uni-marburg.de/~pgiarrusso/

[Adriaan Moors]

i tried to understand your goal but am afraid it's not immediately clear to me

something that I expect might foil/complicate attempts like this is that type checking for matches flows differently from what one might expect

for example, the selector is typed without an expected type (see typedMatch in typers.scala or work your way through the -Ytyper-debug jungle)

that type is then used as the expected type for the top-level pattern of each case

cheers

adriaan

[Dave]

But didn't you forget to make repInt in trait Impl implicit?

 

implicit def repInt(x: Int): Rep[Int] = x.toString

 

.

Op donderdag 9 augustus 2012 00:50:11 UTC+2 schreef Paolo G. Giarrusso het volgende:

[Paolo Giarrusso]

On Thu, Aug 9, 2012 at 12:57 PM, Adriaan Moors <adriaa...@epfl.ch> wrote:
> i tried to understand your goal but am afraid it's not immediately clear to
> me

I didn't make it immediately apparent, but my goal is no different
than yours: having support for
pattern matching with Scala-virtualized, lightweight modular staging (LMS)
&C. The program in the testsuite shows that you can reify a
simple pattern match, like this:

def test = 7 match { case 5 => "foo" case _ => "bar" }

but of course one needs to support also more complex examples - and
that currently fails. Say, calling
staged functions and pattern matching on the their result:

def power(b: Rep[Int], x: Int): Rep[Int] = if (x == 0) 1 else b *
power(b, x - 1)
def test2 = power(3, 2) match { case 9 => "Bingo!" case _ => "What???" }

As you see, in that code I'm pattern-matching over a value of type
Rep[Int], instead of just Int. But whenever I try this, the virtualized pattern
matcher currently gives a type error. In other words, it is not
possible to virtualize pattern matches where the scrutinee is an
already staged representation - that is, most interesting examples;
see for instance figure 17 in the LMS paper from Tiark Rompf&Martin
Odersky, GPCE '10.

Tiark's testcase in virtualized-lms-core shows that instead Scala
2.10.0-M1-virtualized did not give a type error, but failed to
virtualize the code.

Thanks for your time on this.
Paolo

[Dave]

It looks like implicit conversions (e.g. from a pattern Int(5) to a pattern Rep[Int](5) don't work within pattern matching and Int doesn't have an extractor to get a Rep[Int] because it is not a constituent and there is nothing to extract.

 

a (cheezy) workaround could be

 

val five = repInt(5)
val nine = repInt(9)

 

def test2 = repInt(7) match { case five => "foo" }

def test4 = power(3, 2) match { case nine => "Bingo!" }

 

the case _ may be removed because of unreachable code warning

 

Don't know if implicit conversions of patterns is on the roadmap.

Hopefully reified patterns first.

Op donderdag 9 augustus 2012 15:03:16 UTC+2 schreef Paolo G. Giarrusso het volgende:

[Paolo G. Giarrusso]

Il giorno giovedì 9 agosto 2012 14:39:36 UTC+2, Dave ha scritto:

But didn't you forget to make repInt in trait Impl implicit?

 

implicit def repInt(x: Int): Rep[Int] = x.toString

I didn't write that part myself, but it seems that 'implicit' is inherited. Otherwise, new Prog with Impl could not compile.

[Dave]

If I remove implicit from Intf and Impl the new Prog with Impl still compiles

 

The funny thing is that the new Prog with Impl  also doesn't need the workaround for the pattern val five = repInt(5)

It looks like there is a difference between static inheritance and dynamic mixin.

Op vrijdag 10 augustus 2012 00:03:36 UTC+2 schreef Paolo G. Giarrusso het volgende:

[Paolo G. Giarrusso]

Il giorno venerdì 10 agosto 2012 00:18:47 UTC+2, Dave ha scritto:

If I remove implicit from Intf and Impl the new Prog with Impl still compiles

I meant that the definition in Impl must override the one in Intf, otherwise new Prog with Impl would be incomplete (have abstract methods) and 'new Prog with Impl' would be rejected. And the overriding definition cannot be "less implicit" - it must be implicit as well.

I did not expect that the code would still compile - I would investigate whether any virtualization happened (I guess not).

The funny thing is that the new Prog with Impl  also doesn't need the workaround for the pattern val five = repInt(5)

I'm not sure what you mean, but if you progressed beyond what I achieved, I would love an example.

It looks like there is a difference between static inheritance and dynamic mixin.

Not in the things we're discussing about - especially, I don't see in which way inheritance is more static than mixins. At compile-time, classes are constructed and both their parent class and their parent traits are checked, and for each concrete class and for each constructor call "new A with B with ...", the compiler checks that all methods are defined in the type given. Overrides are then resolved at runtime.

[Paolo G. Giarrusso]

Il giorno giovedì 9 agosto 2012 19:16:24 UTC+2, Dave ha scritto:

It looks like implicit conversions (e.g. from a pattern Int(5) to a pattern Rep[Int](5) don't work within pattern matching and Int doesn't have an extractor to get a Rep[Int] because it is not a constituent and there is nothing to extract.

 

Indeed you can't extract an Int from a Rep[Int], because of the reason you give (you could evaluate Rep[Int], but that's of course not what you want to reify pattern matching).

a (cheezy) workaround could be

 

val five = repInt(5)
val nine = repInt(9)

 

def test2 = repInt(7) match { case five => "foo" }

def test4 = power(3, 2) match { case nine => "Bingo!" }

 

the case _ may be removed because of unreachable code warning

That would work in only a few cases—when you don't need to bind a variable. (Plus you forgot backticks or capitals). But this code still gives the same error:

 def test5(i: Rep[Int]) = {

   val J = repInt(5)

   i match { case J => "foo3: " + J } //type error!

 }

virtpatmat_staging-altered.scala:39: error: type mismatch;

 found   : Intf.this.Rep[Intf.this.Rep[Int]] => Intf.this.M[String]

 required: Intf.this.Rep[Int] => Intf.this.M[?]

   i match { case J => "foo3: " + J } //type error!

   ^

one error found

Don't know if implicit conversions of patterns is on the roadmap.

Hopefully reified patterns first.

Not sure what "implicit conversion of patterns" should be - this example from Tiark Rompf are the whole explicit roadmap I can think of:

        println("NOTE: doesn't work yet :-(")

        def test = repInt(7) match { case 5 => "foo" case _ => "bar" } 

But in fact, I think this code after translation will require implicit conversions - the translated code compares 

All descriptions I've studied up to now (and the mechanisms of staging) imply that to use an extractor A => B you'd need an extractor with a type like Rep[A] => Rep[Option[B]], where Option can be replaced by some other type supporting methods flatMap and orElse with the right signatures (see class Matcher in my gist). More precisely, that's the type for an extractor which makes the current translation typecheck. One could "automate" the construction of this extractor in various ways (say macros, but not as 2.10 knows them, the ones of the future which will generate classes - type macros?), but I've not seen this described.

Best regards

[Paul Phillips]

On Wed, Aug 8, 2012 at 3:50 PM, Paolo G. Giarrusso <p.gia...@gmail.com> wrote:

Notice how the compiler mentions Rep[Rep[Int]] instead of Rep[Int].

Neato, I made your power example with the mixed Int and Rep[Int] work by not lifting Rep[T] to Rep[Rep[T]] during match translation.

Will send code later, have to run.

[Paolo Giarrusso]

That's extremely cool! I guess I don't owe anymore _just_ a soft drink.
--
Paolo Giarrusso - Ph.D. Student, Philipps-University Marburg
http://www.informatik.uni-marburg.de/~pgiarrusso/

[Paul Phillips]

On Thu, Aug 9, 2012 at 6:20 PM, Paolo Giarrusso <pgiar...@mathematik.uni-marburg.de> wrote:

That's extremely cool! I guess I don't owe anymore _just_ a soft drink.

Well don't upgrade me too much just yet.  I can't look at this any more now, but here's my tiny patch which you can try out and see what sort of bedlam it creates for you.

  https://github.com/paulp/scala/tree/topic/virtualized-pmat

[Dave]

Looks like Google didn't mail my last response.

 

Op vrijdag 10 augustus 2012 00:37:11 UTC+2 schreef Paolo G. Giarrusso het volgende:

Il giorno giovedì 9 agosto 2012 19:16:24 UTC+2, Dave ha scritto:

It looks like implicit conversions (e.g. from a pattern Int(5) to a pattern Rep[Int](5) don't work within pattern matching and Int doesn't have an extractor to get a Rep[Int] because it is not a constituent and there is nothing to extract.

 

Indeed you can't extract an Int from a Rep[Int], because of the reason you give (you could evaluate Rep[Int], but that's of course not what you want to reify pattern matching).

a (cheezy) workaround could be

 

val five = repInt(5)
val nine = repInt(9)

 

def test2 = repInt(7) match { case five => "foo" }

def test4 = power(3, 2) match { case nine => "Bingo!" }

 

the case _ may be removed because of unreachable code warning

That would work in only a few cases—when you don't need to bind a variable. (Plus you forgot backticks or capitals).

 

 

Yes, I forgot. with the capitals indeed it wants the case _ even if there is an applicable case

 

 

 

 

 

But this code still gives the same error:

 def test5(i: Rep[Int]) = {

   val J = repInt(5)

   i match { case J => "foo3: " + J } //type error!

 }

 

Yes, however I get runtime match error, but maybe that is because I have more implicit conversions

 

virtpatmat_staging-altered.scala:39: error: type mismatch;

 found   : Intf.this.Rep[Intf.this.Rep[Int]] => Intf.this.M[String]

 required: Intf.this.Rep[Int] => Intf.this.M[?]

   i match { case J => "foo3: " + J } //type error!

   ^

one error found

Don't know if implicit conversions of patterns is on the roadmap.

Hopefully reified patterns first.

Not sure what "implicit conversion of patterns" should be - this example from Tiark Rompf are the whole explicit roadmap I can think of:

        println("NOTE: doesn't work yet :-(")

        def test = repInt(7) match { case 5 => "foo" case _ => "bar" } 

But in fact, I think this code after translation will require implicit conversions - the translated code compares 

It prints "bar" but is also prints bar if case 7. It always compiles with me.

 

 

Note that instead of type Rep[+T] = String, I have type Rep[+T] = RichString (with implicit conversions) which support multiplication since String doesn't support it and is final.

 

[Dave]

Also funny is that with your source code and milestone 6 I cannot reproduce the exact error message.

 

Op vrijdag 10 augustus 2012 09:32:49 UTC+2 schreef Dave het volgende: