Equality of structural types

On Mon, Aug 8, 2011 at 4:44 PM, Eugen Labun <labun@gmx.net> wrote:

Hi all,

I'm trying to achieve a compiler enforced checking of equality of structural types.

E.g. a method is allowed to accept only instances of classes that have a "def name: String" method,
not more (i.e. that class is not allowed to have other methods) and not less.

Why would that matter? Do you want all your structural types have to declare toString, equals, hashCode, wait, notify etc?

 

My attempts so far:


This simple definition does not help (object 'a' is accepted).
"x: {def name: String}" works, of course, as "x is a ...", not as "x equal to ...".
(I recall the earlier term was "structural SUBtyping", now used without the "sub", but the meaning
remains the same):

 scala> val a = new {def name = "A"; def age = 20}
 a: java.lang.Object{def name: String; def age: Int} = $anon$1@d60225

 scala> def m(x: {def name: String}) = x.name
 m: (x: AnyRef{def name: String})String

 scala> m(a)
 res0: String = A


This does not compile:

 scala> def m[T: {def name: String}](x: T) = x.name
 <console>:7: error: AnyRef{def name: <?>} does not take type parameters
        def m[T: {def name: String}](x: T) = x.name
               ^
 <console>:7: error: value name is not a member of type parameter T
        def m[T: {def name: String}](x: T) = x.name
                                               ^

Does not compile either:

 scala> def m[T >: {def name: String}](x: T) = x.name
 <console>:7: error: value name is not a member of type parameter T
        def m[T >: {def name: String}](x: T) = x.name
                                                 ^


A structural type + upper and lower bounds does not work (theoretically, "T1 is a T2" AND "T2 is a
T1" must mean "T1 equals T2", isn't it?):

 scala> def m[T >: {def name: String} <: {def name: String}](x: T) = x.name
 m: [T >: AnyRef{def name: String} <: AnyRef{def name: String}](x: T)String


 scala> m(a)
 res1: String = A




Is the compile time check of equality of structural types somehow possible?

Compiler plugin only? In this case please some hints: Which syntax from above should be used? What
compiler phase? An example of something similar via compiler plugin?

How about the future "intersection types"? Are they intended to work with structural types? Would
they perhaps help?


--
Best regards
Eugen Labun

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

On 2011-08-08 16:44, Eugen Labun wrote:
> scala> def m[T >: {def name: String}](x: T) = x.name
> :7: error: value name is not a member of type parameter T
> def m[T >: {def name: String}](x: T) = x.name
> ^

Should it be considered as a bug?

On 2011-08-08 16:46, √iktor Ҡlang wrote:
> Why would that matter? Do you want all your structural types have to declare toString, equals,
> hashCode, wait, notify etc?

They are inherited from the AnyRef (Object) anyway, aren't they? Or am I missing something?

On Mon, Aug 8, 2011 at 4:58 PM, Eugen Labun <labun@gmx.net> wrote:

On 2011-08-08 16:46, √iktor Ҡlang wrote:
> Why would that matter? Do you want all your structural types have to declare toString, equals,
> hashCode, wait, notify etc?

They are inherited from the AnyRef (Object) anyway, aren't they? Or am I missing something?

You stated: "E.g. a method is allowed to accept only instances of classes that have a "def name: String" method,
not more (i.e. that class is not allowed to have other methods) and not less."

That means, since we're on the JVM all classes implicitly or explicitly extends java.lang.Object, which has quite a few methods. If I interpret what you said above correctly, and quite literary, any structural type declared would _always_ need to declare all public methods of java.lang.Object, which I see 0 awesomeness in.


--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

On Mon, Aug 8, 2011 at 3:52 PM, Eugen Labun wrote:
> On 2011-08-08 16:44, Eugen Labun wrote:
>>   scala> def m[T >: {def name: String}](x: T) = x.name
>>   :7: error: value name is not a member of type parameter T
>>          def m[T >: {def name: String}](x: T) = x.name
>>                                                   ^
>
> Should it be considered as a bug?

No, you're asking for a type T which is a supertype of your structural
type. Type Any satisfies that constraint, so clearly x (which could be
of type Any) can't be required to have a name member.

You probably meant,

scala> def m[T <: {def name: String}](x: T) = x.name
m: [T <: AnyRef{def name: String}](x: T)String

"<:" means subtype.

Cheers,

Miles

On 2011-08-08 16:57, Miles Sabin wrote:
> On Mon, Aug 8, 2011 at 3:52 PM, Eugen Labun wrote:
>> On 2011-08-08 16:44, Eugen Labun wrote:
>>> scala> def m[T >: {def name: String}](x: T) = x.name
>>> :7: error: value name is not a member of type parameter T
>>> def m[T >: {def name: String}](x: T) = x.name
>>> ^
>>
>> Should it be considered as a bug?
>
> No, you're asking for a type T which is a supertype of your structural
> type. Type Any satisfies that constraint, so clearly x (which could be
> of type Any) can't be required to have a name member.

Oh, yes, in this case you and Paul are right. Type of 'x' should be restricted to Any. Not a bug. Sorry.

My original goal remains: m must accept only types that a structurally equal to the specified type.

On 2011-08-08 17:00, √iktor Ҡlang wrote:
> You stated: "E.g. a method is allowed to accept only instances of classes that have a "def name:
> String" method,
> not more (i.e. that class is not allowed to have other methods) and not less."
>
> That means, since we're on the JVM all classes implicitly or explicitly extends java.lang.Object,
> which has quite a few methods. If I interpret what you said above correctly, and quite literary, any
> structural type declared would _always_ need to declare all public methods of java.lang.Object,
> which I see 0 awesomeness in.

No, no, please do not interpret me too litarally :)
I meant und implied, of course, that all and any types extend AnyRef (Object) anyway.

On Mon, Aug 8, 2011 at 5:04 PM, Eugen Labun <labun@gmx.net> wrote:

On 2011-08-08 16:57, Miles Sabin wrote:
> On Mon, Aug 8, 2011 at 3:52 PM, Eugen Labun <labun@gmx.net> wrote:
>> On 2011-08-08 16:44, Eugen Labun wrote:
>>>   scala> def m[T >: {def name: String}](x: T) = x.name
>>>   <console>:7: error: value name is not a member of type parameter T
>>>          def m[T >: {def name: String}](x: T) = x.name
>>>                                                   ^
>>
>> Should it be considered as a bug?
>
> No, you're asking for a type T which is a supertype of your structural
> type. Type Any satisfies that constraint, so clearly x (which could be
> of type Any) can't be required to have a name member.

Oh, yes, in this case you and Paul are right. Type of 'x' should be restricted to Any. Not a bug. Sorry.

My original goal remains: m must accept only types that a structurally equal to the specified type.

If it has to be the exact type, why even bother parameterizing it?

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

On 8/8/11 7:44 AM, Eugen Labun wrote:
> E.g. a method is allowed to accept only instances of classes that have
> a "def name: String" method, not more (i.e. that class is not allowed
> to have other methods) and not less.

You can't do this in the type system because the type system is built on
the concept of subtyping, and by definition any class which has a "def
name: String" method is a subtype of a type which is defined around the
presence of that method.

> Compiler plugin only? In this case please some hints: Which syntax
> from above should be used? What compiler phase? An example of
> something similar via compiler plugin?

Since this is an unusually tractable compiler question, I implemented
it for you, in broad strokes anyway. I leave a more rigorous argument
to corresponds and all the scaffolding as an exercise.

// compile this part
package foo {
class OK { def name = "abc" }
class TooBusy { def name = "def" ; def bippy = "so many methods" }
}

package object foo {
type Bippy = { def name: String }
}

/*
Then run this part. Requires using a recent trunk build.

% scala -Dscala.repl.power

scala> def getDecls(name: String) = intp(name).tpe.decls.toList.filterNot(_.isConstructor).sortBy("" + _)
getDecls: (name: String)List[$r.intp.global.Symbol]

scala> getDecls("foo.Bippy").corresponds(getDecls("foo.OK"))(_.name == _.name)
res0: Boolean = true

scala> getDecls("foo.Bippy").corresponds(getDecls("foo.TooBusy"))(_.name == _.name)
res1: Boolean = false

*/

On 2011-08-08 17:26, Paul Phillips wrote:
> On 8/8/11 7:44 AM, Eugen Labun wrote:
>> E.g. a method is allowed to accept only instances of classes that have
>> a "def name: String" method, not more (i.e. that class is not allowed
>> to have other methods) and not less.
>
> You can't do this in the type system because the type system is built on
> the concept of subtyping, and by definition any class which has a "def
> name: String" method is a subtype of a type which is defined around the
> presence of that method.

OK, but we have also lower bounds.
Why the conjunction of upper and lower bounds does not work with structural types?
(the last example in my orig. post)

>> Compiler plugin only? In this case please some hints: Which syntax
>> from above should be used? What compiler phase? An example of
>> something similar via compiler plugin?
>
> Since this is an unusually tractable compiler question, I implemented
> it for you, in broad strokes anyway. I leave a more rigorous argument
> to corresponds and all the scaffolding as an exercise.

Sorry if cannot explain my needs in a more correct way. If I could formulate the question quite
correctly, I would have been able to find the answer :)

> // compile this part
> package foo {
> class OK { def name = "abc" }
> class TooBusy { def name = "def" ; def bippy = "so many methods" }
> }
>
> package object foo {
> type Bippy = { def name: String }
> }
>
> /*
> Then run this part. Requires using a recent trunk build.
>
> % scala -Dscala.repl.power
>
> scala> def getDecls(name: String) = intp(name).tpe.decls.toList.filterNot(_.isConstructor).sortBy("" + _)
> getDecls: (name: String)List[$r.intp.global.Symbol]
>
> scala> getDecls("foo.Bippy").corresponds(getDecls("foo.OK"))(_.name == _.name)
> res0: Boolean = true
>
> scala> getDecls("foo.Bippy").corresponds(getDecls("foo.TooBusy"))(_.name == _.name)
> res1: Boolean = false
>
> */

OK, I can do something similar at runtime, too. How to do that at compile time?

Or I misunderstood your code? Then I must to think about a little more...
Paul, thank you anyway for taking time to answer!

On 8/8/11 8:55 AM, Eugen Labun wrote:
> OK, but we have also lower bounds.
> Why the conjunction of upper and lower bounds does not work with structural types?
> (the last example in my orig. post)

It does work, it just doesn't mean what you think.

scala> def m[T >: {def name: String} <: {def name: String}](x: T) = x.name
m: [T >: AnyRef{def name: String} <: AnyRef{def name: String}](x: T)String

That definition is equivalent to this one:

scala> def m(x: {def name: String}) = x.name

Let's try it with AnyRef:

def m[T >: AnyRef <: AnyRef](x: T) = ()

Are you surprised to be able to call that with a String?

// equivalently
def m(x: AnyRef) = ()

Are you surprised to be able to call that?

The lower bound is AnyRef, but that does not create some kind of fence which keeps out String, because a String *is* an AnyRef. Your situation is identical. The lower+upper bound on m can prevent you from parameterizing the method call differently, but it can't prohibit values which are subtypes of the type which is allowed. That's pretty much what subtyping is.

On 2011-08-08 18:14, Paul Phillips wrote:
> On 8/8/11 8:55 AM, Eugen Labun wrote:
>> OK, but we have also lower bounds.
>> Why the conjunction of upper and lower bounds does not work with structural types?
>> (the last example in my orig. post)
>
> It does work, it just doesn't mean what you think.
>
> scala> def m[T >: {def name: String} <: {def name: String}](x: T) = x.name
> m: [T >: AnyRef{def name: String} <: AnyRef{def name: String}](x: T)String
>
> That definition is equivalent to this one:
>
> scala> def m(x: {def name: String}) = x.name
>
> Let's try it with AnyRef:
>
> def m[T >: AnyRef <: AnyRef](x: T) = ()
>
> Are you surprised to be able to call that with a String?
>
> // equivalently
> def m(x: AnyRef) = ()
>
> Are you surprised to be able to call that?
>
> The lower bound is AnyRef, but that does not create some kind of fence which keeps out String, because a String *is* an AnyRef. Your situation is identical. The lower+upper bound on m can prevent you from parameterizing the method call differently, but it can't prohibit values which are subtypes of the type which is allowed. That's pretty much what subtyping is.
>

I really misunderstood the meaning of bounds. *After* your explanation the things are simple und
understandable. But, strange, *before* they weren't! Thank you again, Paul!

My conclusion so far:
To have the native structural equality, and therefore to implement relational algebra, the language
must not support the subtyping polymorphism (plus, probably, further conditions). And that is not
the case for all mainstream languages.

Try this, I think you need just an extra type parameter relation:
Is this the behaviour you are looking for?

REPL
====

scala> val a = new {def name = "A"; def age = 20}
a: java.lang.Object{def name: java.lang.String; def age: Int} = $anon
$1@135265e

scala> val b = new {def name = "B"}
b: java.lang.Object{def name: java.lang.String} = $anon$1@c32102

scala> val c = new {def age = 20}
c: java.lang.Object{def age: Int} = $anon$1@13437f0

scala> def m[T >: {def name: String} <: {def name: String},T2 >:T <:T]
(x: T2) =
x.name
m: [T >: AnyRef{def name: String} <: AnyRef{def name: String}, T2 >: T
<: T](x:
T2)String

scala> m(a)
:10: error: inferred type arguments [AnyRef{def name:
String},java.lang
.Object{def name: java.lang.String; def age: Int}] do not conform to
method m's
type parameter bounds [T >: AnyRef{def name: String} <: AnyRef{def
name: String}
,T2 >: T <: T]
m(a)
^

scala> m(b)
res3: String = B

scala> m(c)
:10: error: inferred type arguments
[java.lang.Object,java.lang.Object{
def age: Int}] do not conform to method m's type parameter bounds [T
>: AnyRef{d
ef name: String} <: AnyRef{def name: String},T2 >: T <: T]
m(c)
^

Compiler
========

struct.scala
============
package struct
object Main extends App {
val a = new {def name = "A"; def age = 20}
val b = new {def name = "B"}
val c = new {def age = 20}
def m[T >: {def name: String} <: {def name: String},T2 >:T <:T](x:
T2) = println(x.name)
m(a)
m(b)
m(c)
}

C:\scala-2.9.1.RC1\examples>scalac struct.scala
struct.scala:7: error: inferred type arguments [AnyRef{def name:
String},java.la
ng.Object{def name: java.lang.String; def age: Int}] do not conform to
method m'
s type parameter bounds [T >: AnyRef{def name: String} <: AnyRef{def
name: Strin
g},T2 >: T <: T]
m(a)
^
struct.scala:9: error: inferred type arguments
[java.lang.Object,java.lang.Objec
t{def age: Int}] do not conform to method m's type parameter bounds [T
>: AnyRef
{def name: String} <: AnyRef{def name: String},T2 >: T <: T]
m(c)
^
two errors found

After outcommenting //m(a) and //m(c):

C:\scala-2.9.1.RC1\examples>scalac struct.scala

C:\scala-2.9.1.RC1\examples>scala struct.Main
B

On 8/9/11 5:58 AM, Dave wrote:
> Try this, I think you need just an extra type parameter relation:
> Is this the behaviour you are looking for?

This is clever, but be aware that you are not enforcing any different
behavior. What you're doing is utilizing your knowledge of the type
inferencer to pull the wool over its eyes.

For instance:

> scala> m(a)
> :10: error: inferred type arguments [AnyRef{def name:
> String},java.lang
> .Object{def name: java.lang.String; def age: Int}] do not conform to
> method m's
> type parameter bounds [T>: AnyRef{def name: String}<: AnyRef{def
> name: String}
> ,T2>: T<: T]
> m(a)
> ^

The inferencer fails trying to pick a T2 which conforms to T. But that
is only an (unnecessary) quirk of the implementation. You can still
call the method by giving it the types it should have inferrred.

scala> m[{ def name: String }, { def name: String }](a)
res5: String = A

There is no scenario where you will be able to exclude this method call.
You don't want to depend on the vagaries of the inferencer in matters
of correctness.

On 2011-08-09 14:58, Dave wrote:
> Try this, I think you need just an extra type parameter relation:
> Is this the behaviour you are looking for?
> ...
> scala> def m[T >: {def name: String} <: {def name: String},T2 >:T <:T]

Yes, it is!
Dave, thank you very much!

Wow, the second type param really does the magic.
I'm simply happy :)

--
Eugen

On 2011-08-09 15:52, Paul Phillips wrote:
> ...
> The inferencer fails trying to pick a T2 which conforms to T. But that is only an (unnecessary)
> quirk of the implementation. You can still call the method by giving it the types it should have
> inferrred.
>
> scala> m[{ def name: String }, { def name: String }](a)
> res5: String = A
>
> There is no scenario where you will be able to exclude this method call. You don't want to depend
> on the vagaries of the inferencer in matters of correctness.

Therefore for a robust implementation I would need a language with
1) structural types
and
2) no subtyping.
Probably, the higher kinded types are needed, too. If it's at all possible with (1) and (2) ...

Are you agree?

Interesting, are there such languages?

On 8/9/11 7:32 AM, Eugen Labun wrote:
> Interesting, are there such languages?

I'm no expert, but maybe ocaml can be bent to your will. It has subtyping, but according to the following excerpt, subtyping coercions don't happen automatically. It sounds like it's in the right ballpark anyway.

http://skydeck.com/blog/programming/ocaml-for-the-recovering-java-progra...

...

One difference between Java and OCaml is nominal vs. structural subtyping. In Java, one class is a subclass of another only if you declare it to be so (e.g. Cat extends Pet); what matters is the names of the classes involved (hence “nominal”). In OCaml what matters is the methods that the class supports (its structure, hence “structural”); if you declare classes pet with a legs:int method and cat with legs:int and snooty:bool methods, then cat is a subclass of pet even though you have declared no relationship between them (as with “duck typing”, but statically checked.)

A second difference is that in Java subtyping coercions happen automatically, while in OCaml you must request them explicitly with the :> operator. In Java you can write

Pet p = new Cat();

while in OCaml you must write

let (p : pet) = (new cat : cat :> pet)

On 2011-08-09 16:58, Paul Phillips wrote:
> On 8/9/11 7:32 AM, Eugen Labun wrote:
>> Interesting, are there such languages?
>
> I'm no expert, but maybe ocaml can be bent to your will. It has subtyping, but according to the following excerpt, subtyping coercions don't happen automatically> let (p : pet) = (new cat : cat :> pet)
> ...

It seems to be the right direction. Thank you, Paul!

PS: I'm not leaving Scala. Scala remains my preffered language :)

Unsubscribe

-Shaun 

Sent from my cell phone. Brevity & typos expected.

On Aug 8, 2011 10:44 AM, "Eugen Labun" <labun@gmx.net> wrote:
> Hi all,
>
> I'm trying to achieve a compiler enforced checking of equality of structural types.
>
> E.g. a method is allowed to accept only instances of classes that have a "def name: String" method,
> not more (i.e. that class is not allowed to have other methods) and not less.
>
>
> My attempts so far:
>
>
> This simple definition does not help (object 'a' is accepted).
> "x: {def name: String}" works, of course, as "x is a ...", not as "x equal to ...".
> (I recall the earlier term was "structural SUBtyping", now used without the "sub", but the meaning
> remains the same):
>
> scala> val a = new {def name = "A"; def age = 20}
> a: java.lang.Object{def name: String; def age: Int} = $anon$1@d60225
>
> scala> def m(x: {def name: String}) = x.name
> m: (x: AnyRef{def name: String})String
>
> scala> m(a)
> res0: String = A
>
>
> This does not compile:
>
> scala> def m[T: {def name: String}](x: T) = x.name
> <console>:7: error: AnyRef{def name: <?>} does not take type parameters
> def m[T: {def name: String}](x: T) = x.name
> ^
> <console>:7: error: value name is not a member of type parameter T
> def m[T: {def name: String}](x: T) = x.name
> ^
>
> Does not compile either:
>
> scala> def m[T >: {def name: String}](x: T) = x.name
> <console>:7: error: value name is not a member of type parameter T
> def m[T >: {def name: String}](x: T) = x.name
> ^
>
>
> A structural type + upper and lower bounds does not work (theoretically, "T1 is a T2" AND "T2 is a
> T1" must mean "T1 equals T2", isn't it?):
>
> scala> def m[T >: {def name: String} <: {def name: String}](x: T) = x.name
> m: [T >: AnyRef{def name: String} <: AnyRef{def name: String}](x: T)String
>
>
> scala> m(a)
> res1: String = A
>
>
>
>
> Is the compile time check of equality of structural types somehow possible?
>
> Compiler plugin only? In this case please some hints: Which syntax from above should be used? What
> compiler phase? An example of something similar via compiler plugin?
>
> How about the future "intersection types"? Are they intended to work with structural types? Would
> they perhaps help?
>
>
> --
> Best regards
> Eugen Labun