compiler weirdness with crazy types

[Matt Hellige]

Sorry for the vague subject, I'm not sure how else to describe this.

This is based on some thinking about the following blog post:
  http://michid.wordpress.com/2008/07/30/meta-programming-with-scala-part-ii-multiplication/#comment-69

Consider:
  object Church {
    abstract class Zero
    abstract class Succ[T]

    type _0[s[_], z] = z
    type _1[s[_], z] = s[z]
    type _2[s[_], z] = s[s[z]]
    type _3[s[_], z] = s[s[s[z]]]
    type _4[s[_], z] = s[s[s[s[z]]]]

    trait apply1[t[_[_],_],u[_]] {
      type It[a] = t[u,a]
    }

    type mul[m[s[_], z], n[s[_], z], s[_], z] = m[apply1[n,s]#It, z]
    type x[m[s[_], z], n[s[_], z]] = mul[m, n, Succ, Zero]

    type three = _3 x _1
    //type four = _2 x _2
    type six = _2 x _3
    type eight = _4 x _2
  }

This code compiles fine. We can even use the defined types! But if we
uncomment the definition of "four":
  type four = _2 x _2
then we get the following:
  church2.scala:19: error: illegal cyclic reference involving type _2
    type four = _2 x _2
         ^
  church2.scala:20: error: illegal cyclic reference involving type x
    type six = _2 x _3
                  ^
  church2.scala:21: error: illegal cyclic reference involving type x
    type eight = _4 x _2
                    ^
  three errors found

Notice that even the previously working definitions are now broken?
Why? What gives??

(This is with the current nightly build.)

Thanks...
Matt

--
Matt Hellige / matt@...
http://matt.immute.net

[Matt Hellige]

On Fri, Aug 1, 2008 at 2:40 PM, Matt Hellige <matt@...> wrote:
> This code compiles fine. We can even use the defined types! But if we
> uncomment the definition of "four":
>  type four = _2 x _2
> then we get the following:

More generally, it doesn't work for squares:
 type one = _1 x _1
 type nine = _3 x _3
These have the same problem. Does anyone see why?

Matt

--
Matt Hellige / matt@...
http://matt.immute.net

[Matt Hellige]

On Fri, Aug 1, 2008 at 2:55 PM, Matt Hellige <matt@...> wrote:

> On Fri, Aug 1, 2008 at 2:40 PM, Matt Hellige <matt@...> wrote:
>> This code compiles fine. We can even use the defined types! But if we
>> uncomment the definition of "four":
>>  type four = _2 x _2
>> then we get the following:
>
> More generally, it doesn't work for squares:
>  type one = _1 x _1
>  type nine = _3 x _3
> These have the same problem. Does anyone see why?
>

Ok. Sorry to keep emailing myself, but I think I see what's happening.
The expansion of a type like _1 x _1 goes as follows:
  _1 x _1
    -> mul[_1, _1, Succ, Zero]
    -> _1[apply1[_1,Succ]#It, Zero]
    -> apply1[_1,Succ]#It[Zero]
    -> _1[Succ,Zero]
    -> Succ[Zero]

The third line seems to be the problem, as we can see by writing
  type test = _1[apply1[_1,Succ]#It, Zero]
which produces the same error.

This would lead us to think maybe we can avoid the problem just by
making more aliases. Indeed we can. The following works fine:
  type _1x[s[_], z] = s[z]
  type _2x[s[_], z] = s[s[z]]
  type _3x[s[_], z] = s[s[s[z]]]
  type one = _1 x _1x
  type four = _2 x _2x
  type nine = _3 x _3x

But this is really ugly. So there are three questions.

1. Is this right? Can it be fixed? Can we relax the rules on illegal
cycles somehow? I have really wished for this in other cases as
well...

2. Why does this error break compilation of the other definitions in
the file? Not a big deal, maybe, but it makes it extra confusing.

3. Should I open a bug?

Thanks, and sorry for all the messages about this...
Matt

--
Matt Hellige / matt@...
http://matt.immute.net

Matt,

Thanks for providing this cool code! I tried it out and it works perfectly. With
the new Eclipse plugin (nightly from August 2.) the problem with the squares
does only appear partially. Though at some point I get an error message from the
plugin about the cyclic reference, the code seems to compile fine:

println((nullval[_1 x _1]).eval)
println((nullval[_1 x _2]).eval)
println((nullval[_2 x _3]).eval)
println((nullval[_2 x _2]).eval)

correctly prints
1
2
6
4

Michael