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
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.
m: [T <: AnyRef{def name: String}](x: T)String
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
--
Miles Sabin
tel: +44 7813 944 528
gtalk: mi...@milessabin.com
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin
They are inherited from the AnyRef (Object) anyway, aren't they? Or am I missing something?
I need the structural type as a lower bound, not the upper.
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.
No, no, please do not interpret me too litarally :)
I meant und implied, of course, that all and any types extend AnyRef (Object) anyway.
Structurally equal, i.e. can have another class name or be created as a structural type as well.
Sorry, in this (my former) case type of T can only be inferred as AnyRef. Not a bug.
or
class AnyName {def name: String}
> If so, what's the point of the parametrization, if only one type is valid, and is already known?
The goal is to implement a (statically) type checked relational algebra library.
E.g. if assigning a tuple value, the new value must not have additional attributes, compared to the
type of the variable (i.e. no polymorphism allowed in assignment).
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
*/
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?
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.
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)
> <console>: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.
Yes, it is!
Dave, thank you very much!
Wow, the second type param really does the magic.
I'm simply happy :)
--
Eugen
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?
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.
...
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)
It seems to be the right direction. Thank you, Paul!
PS: I'm not leaving Scala. Scala remains my preffered language :)
I'm curious. Why is it so important that a tuple don't have extra attributes?
I'm thinking that maybe you can approach this using typeclasses instead. I.e. (implicit iso: Isomorphic[T1,T2]) or such.
BR
John
Sent from my phone
Hi John, sorry for the delay.
A good question. You brought me to search for the source of that assumtion.
And here it is [1, #22] (** markup by me) :
"Let T and T' be both tuple types or both relation types. Then type T' shall be a subtype of type T,
and type T shall be a supertype of type T', if and only if (a) T and T' have *the same attribute
names* A1, A2, ..., An and (b) for all j (j = 1, 2, ..., n), the type of attribute Aj of T' is a
subtype of the type of attribute Aj of T. Tuple t shall be of some subtype of tuple type T if and
only if the heading of t is that of some subtype of T. Relation r shall be of some subtype of
relation type T if and only if the heading of r is that of some subtype of T (in which case every
tuple in the body of r shall necessarily also have a heading that is that of some subtype of T)."
I understand that this cite is not necessarily to be the final truth, especially in a practical
implementation. And I don't know an argument (besides that bare statement in the cite above), why
the assignement of a value with extended attribute set should be prohibited generally in a
relational algebra system. I'm also very interested in such arguments (pro or contra).
I should also state that my initial assumtion (no subtyping polymorphism in assignment is allowed)
isn't correct. At least according to C.J. Date [1, #9 #11], polymorphic assignments are allowed. I.e.
if (1) T' is a subtype of T, and
(2) variable V has declared type T, and
(3) type of expression X is T'
then assignment V := X is allowed.
As you see, my fundamental assumtions should be rethinked. May be it turns out that the real
problems arises elsewhere...
I would like also to thank you, John, for your question on Stackoverflow [2] and C�dric Lavanchy for
the report [3] that were the most useful readings for me in the area of implementing type safe
relational algebra.
[1] C. J. Date, Hugh Darwen.
Database Explorations: Essays on the Third Manifesto and Related Topics
Trafford Publishing, 2010
Chapter 19. "The Inheritance Model" is available online:
http://www.dcs.warwick.ac.uk/~hugh/TTM/DBE-Chapter19.pdf
[2] Language features to implement relational algebra
http://stackoverflow.com/questions/170500/language-features-to-implement-relational-algebra
[3] C�dric Lavanchy.
Static type safety guarantees for the operators of a relational database querying system
http://lamp.epfl.ch/teaching/projects/archive/lavanchy_report.pdf
--
Eugen
Regarding your concrete proposition:
What do you mean with "Isomorphic[T1,T2]"? Is it something similar to the =:= class from Predef [1]?
How can it be used?
(I also created a separate topic regarding the meaning of <:<, =:=, <%< on scala-user
http://groups.google.com/group/scala-user/browse_thread/thread/2088da6e35fa4456#)
--
Eugen
[1] https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_0_1/src//library/scala/Predef.scala#L353
I understand that this cite is not necessarily to be the final truth, especially in a practical
implementation. And I don't know an argument (besides that bare statement in the cite above), why
the assignement of a value with extended attribute set should be prohibited generally in a
relational algebra system. I'm also very interested in such arguments (pro or contra).
I would like also to thank you, John, for your question on Stackoverflow
On 2011-08-09 20:36, John Nilsson wrote:
> I'm curious. Why is it so important that a tuple don't have extra attributes?Regarding your concrete proposition:
>
> I'm thinking that maybe you can approach this using typeclasses instead. I.e. (implicit iso:
> Isomorphic[T1,T2]) or such.
What do you mean with "Isomorphic[T1,T2]"? Is it something similar to the =:= class from Predef [1]?
How can it be used?
I [...] started thinking of how to rethink the primitives of the relational model in terms of functions to synthesise a kind of functional-relational language.
Unsubscribe
-Shaun
Sent from my cell phone. Brevity & typos expected.
Heading in a lens direction there. There exists a compiler plugin for the conclusion of this direction.