Equality of structural types

84 views
Skip to first unread message

Eugen Labun

unread,
Aug 8, 2011, 10:44:23 AM8/8/11
to scala-l...@googlegroups.com
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

√iktor Ҡlang

unread,
Aug 8, 2011, 10:46:01 AM8/8/11
to scala-l...@googlegroups.com
On Mon, Aug 8, 2011 at 4:44 PM, Eugen Labun <la...@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?

 



--
Viktor Klang

Akka Tech Lead
Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

Eugen Labun

unread,
Aug 8, 2011, 10:52:30 AM8/8/11
to scala-l...@googlegroups.com
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?

Paul Phillips

unread,
Aug 8, 2011, 10:56:28 AM8/8/11
to scala-l...@googlegroups.com, Eugen Labun

m: [T <: AnyRef{def name: String}](x: T)String


Miles Sabin

unread,
Aug 8, 2011, 10:57:39 AM8/8/11
to scala-l...@googlegroups.com

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

Eugen Labun

unread,
Aug 8, 2011, 10:58:10 AM8/8/11
to scala-l...@googlegroups.com
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?

Eugen Labun

unread,
Aug 8, 2011, 11:00:22 AM8/8/11
to Paul Phillips, scala-l...@googlegroups.com

I need the structural type as a lower bound, not the upper.

√iktor Ҡlang

unread,
Aug 8, 2011, 11:00:38 AM8/8/11
to scala-l...@googlegroups.com
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.

Eugen Labun

unread,
Aug 8, 2011, 11:04:25 AM8/8/11
to scala-l...@googlegroups.com
On 2011-08-08 16:57, Miles Sabin wrote:
> On Mon, Aug 8, 2011 at 3:52 PM, Eugen Labun <la...@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.

√iktor Ҡlang

unread,
Aug 8, 2011, 11:07:53 AM8/8/11
to scala-l...@googlegroups.com
If it has to be the exact type, why even bother parameterizing it?

Eugen Labun

unread,
Aug 8, 2011, 11:09:33 AM8/8/11
to scala-l...@googlegroups.com
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.

Eugen Labun

unread,
Aug 8, 2011, 11:12:57 AM8/8/11
to scala-l...@googlegroups.com
> 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?

Structurally equal, i.e. can have another class name or be created as a structural type as well.

Eugen Labun

unread,
Aug 8, 2011, 11:16:21 AM8/8/11
to scala-l...@googlegroups.com
On 2011-08-08 16:56, Paul Phillips wrote:

Sorry, in this (my former) case type of T can only be inferred as AnyRef. Not a bug.

√iktor Ҡlang

unread,
Aug 8, 2011, 11:17:44 AM8/8/11
to scala-l...@googlegroups.com

What type T could statisfy your bound: T >: {def name: String} <: {def name: String}

If I interpreted you correctly, only: {def name: String}
If so, what's the point of the parametrization, if only one type is valid, and is already known?

Eugen Labun

unread,
Aug 8, 2011, 11:23:22 AM8/8/11
to scala-l...@googlegroups.com
> What type T could statisfy your bound: T >: {def name: String} <: {def name: String}
>
> If I interpreted you correctly, only: {def name: String}

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).

Paul Phillips

unread,
Aug 8, 2011, 11:26:35 AM8/8/11
to scala-l...@googlegroups.com, Eugen Labun
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

*/

Eugen Labun

unread,
Aug 8, 2011, 11:55:27 AM8/8/11
to scala-l...@googlegroups.com, Paul Phillips
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?

Eugen Labun

unread,
Aug 8, 2011, 12:07:35 PM8/8/11
to scala-l...@googlegroups.com, Paul Phillips
Or I misunderstood your code? Then I must to think about a little more...
Paul, thank you anyway for taking time to answer!

Paul Phillips

unread,
Aug 8, 2011, 12:14:14 PM8/8/11
to Eugen Labun, scala-l...@googlegroups.com
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.

Eugen Labun

unread,
Aug 8, 2011, 12:35:41 PM8/8/11
to Paul Phillips, scala-l...@googlegroups.com

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.

Dave

unread,
Aug 9, 2011, 8:58:11 AM8/9/11
to scala-language
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)
<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)
^

scala> m(b)
res3: String = B

scala> m(c)
<console>: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








Paul Phillips

unread,
Aug 9, 2011, 9:52:14 AM8/9/11
to scala-l...@googlegroups.com, Dave
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)
> <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.

Eugen Labun

unread,
Aug 9, 2011, 9:53:57 AM8/9/11
to scala-l...@googlegroups.com, Dave
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

Eugen Labun

unread,
Aug 9, 2011, 10:32:19 AM8/9/11
to scala-l...@googlegroups.com, Paul Phillips, Dave
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?

Paul Phillips

unread,
Aug 9, 2011, 10:58:54 AM8/9/11
to Eugen Labun, scala-l...@googlegroups.com, Dave
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-programmer-part-1-objects-and-subtyping

...

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)

Eugen Labun

unread,
Aug 9, 2011, 12:05:17 PM8/9/11
to Paul Phillips, scala-l...@googlegroups.com, Dave
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 :)

John Nilsson

unread,
Aug 9, 2011, 2:36:15 PM8/9/11
to scala-l...@googlegroups.com

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

Eugen Labun

unread,
Aug 11, 2011, 5:24:19 AM8/11/11
to scala-l...@googlegroups.com, John Nilsson
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?
>
> I'm thinking that maybe you can approach this using typeclasses instead. I.e. (implicit iso:
> Isomorphic[T1,T2]) or such.

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

Eugen Labun

unread,
Aug 11, 2011, 5:40:46 AM8/11/11
to scala-l...@googlegroups.com, John Nilsson
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?
>
> I'm thinking that maybe you can approach this using typeclasses instead. I.e. (implicit iso:
> Isomorphic[T1,T2]) or such.

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

Eugen Labun

unread,
Aug 11, 2011, 11:30:30 AM8/11/11
to scala-l...@googlegroups.com, John Nilsson
Yet another remark: Date and Darwen presume that types are "named" [1 #1].
But I can also imagine that structural types (as opposed to nominal types) were unintentionally not
taken into account.

John Nilsson

unread,
Aug 19, 2011, 7:53:18 PM8/19/11
to Eugen Labun, scala-l...@googlegroups.com
On Thu, Aug 11, 2011 at 11:24 AM, Eugen Labun <la...@gmx.net> wrote:
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 ran into one issue that might be hint towards an argument. While trying to implement  join[T1,T2](t1:T1,t2:T2):T1 with T2   using a dynamic proxy it was an interesting challenge to determine which members to consider for a join key. Only members of the T1 and T2 types? Only members of the concrete classes implementing T1 and T2? All inherited methods all the way up to Any?

At the time I hadn't considered using type classes though. Maybe join[T1:Tuple,T2:Tuple] ?
 

I would like also to thank you, John, for your question on Stackoverflow

Yeah, your questions here did trigger a eerie sense of déjà vu. ;-) I should tell you that after experimenting for a while using dynamic proxies I dropped the project deciding that I didn't want to tackle Scala with reflection.

Armed with some loose inspiration from stuff like Kava[1], and XST[2] I instead started thinking of how to rethink the primitives of the relational model in terms of functions to synthesise a kind of functional-relational language. This mostly ended up as a braindump
in a github wiki[3] though.

I think the most interesting outcome was the idea to separate the notion of iterating a data set from the querying for set membership. Date and Darwen seems very focused on the relational model as a kind of logic programming system for deciding the truth of things, I guess in the style of Prolog. My practical experience with SQL systems, though, are that they tend to be far more interesting as aggregating and presenting lots of "truths".

My thinking was then that instead of a relation being defined from tuples, and then adding constraints to those to model functional dependencies. You start with the functional dependencies as functions and then define how to generate input to those function to derive the tuples.
So given a function T->A,B,C and some means of producing Ts, for example a function Nat->T you have a way to iterate over a data set.

Further thinking of SQL vs Relational:
Date and Darwen is hell bent on the big problem being that SQL is defined on tables and not sets. In my experience it's very seldom that I reach for the DISTICT keyword in SQL. In fact most of the time I go out of my way to _not_ lose rows. Using joins instead of exists, union all instead of just plain union and so on.

So I don't agree with them that this is an issue to focus on. Instead I find that the major pain point of SQL is that it's just not composable. Reusing query snippets for various similar queries is very hard. While it's possible to define views fore some reuse they have two major flaws.
  1. To allow adding specific filtering to the reused view you need to expose the attributes to filter on in the view. This tends to produce bloated SQL, confusing and unrelated relations with unclear keys, extra joins and references not needed by all users of the view with potential performance problems as a result.
  2. The view cannot be parameterised in any other way than selecting from it with a filter. This leaves you at the mercy of the RDBMS ability to perform predicate pushing and other optimising strategies for performance. Which might be fine in theory but in practice, at least with Oracle 10g, gives entirely unsatisfying results.

Bringing this slightly on topic I might here mention Squeryl. [4] I haven't had an opportunity to play with it yet, but from a distance it looks like it makes an honest effort in addressing these issues.

And on that note I'll stop my ramblings, I fear I'm way off topic now. I wish good luck with your efforts, and should you end up with anything interesting, please do tell. :-P

[1] http://www.research.ibm.com/people/d/dfb/papers/Bacon02Kava.pdf
[2] http://c2.com/cgi/wiki?ExtendedSetTheoryStorageModel
[3] https://github.com/JohnNilsson/Dung-Beetle/wiki/Language
[4] http://squeryl.org/

BR,
John

John Nilsson

unread,
Aug 19, 2011, 7:57:16 PM8/19/11
to Eugen Labun, scala-l...@googlegroups.com
On Thu, Aug 11, 2011 at 11:40 AM, Eugen Labun <la...@gmx.net> wrote:
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?
>
> I'm thinking that maybe you can approach this using typeclasses instead. I.e. (implicit iso:
> Isomorphic[T1,T2]) or such.

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?

Ah, didn't mean to imply that it actually exists. But yes, similar to =:= I was just thinking that you could define a type class to act as evidence that the properties you are interested in holds for the two types.  I just picked Isomorphic as a name because it seemed suitable to what you were asking for before.

BR,
John

Alex Cruise

unread,
Aug 19, 2011, 8:21:09 PM8/19/11
to jo...@milsson.nu, Eugen Labun, scala-l...@googlegroups.com
On Fri, Aug 19, 2011 at 4:53 PM, John Nilsson <jo...@milsson.nu> wrote:
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.

Have you read Out of the Tar Pit[1], Ben Moseley's paper espousing functional relational programming? :)  I can see you're not really aiming in the same direction as he was, but it would probably provide some useful colour.

-0xe1a

Shaun Sorrells

unread,
Aug 19, 2011, 8:22:44 PM8/19/11
to scala-l...@googlegroups.com

Unsubscribe

-Shaun 

Sent from my cell phone. Brevity & typos expected.

On Aug 8, 2011 10:44 AM, "Eugen Labun" <la...@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

Tony Morris

unread,
Aug 19, 2011, 8:32:02 PM8/19/11
to scala-l...@googlegroups.com

Heading in a lens direction there. There exists a compiler plugin for the conclusion of this direction.

On 10/08/2011 4:36 AM, "John Nilsson" <jo...@milsson.nu> wrote:

John Nilsson

unread,
Aug 19, 2011, 10:08:21 PM8/19/11
to scala-l...@googlegroups.com
I'm assuming you ScalaQL, which is a very interesting project indeed. It seems kind of dead atm though.

I'm not entierly sure that it is a suitable match for the analysis and reporting kind of SQL I'm thinking of. I have a feeling it would be better for light ORM style querying like what you do with HQL. OTOH I'm rather convinced that the sort of things you do with ORM-tools is probably better solved not involving anything relational at all.

BR,
John
Reply all
Reply to author
Forward
0 new messages