Re: Equality of structural types

On 2011-08-08 16:56, Paul Phillips wrote:
> On 8/8/11 7:52 AM, 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?
>>
>
> scala> def m[T <: {def name: String}](x: T) = x.name
> m: [T <: AnyRef{def name: String}](x: T)String
>
>
>

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

On 2011-08-08 16:56, Paul Phillips wrote:
> On 8/8/11 7:52 AM, 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?
>>
>
> scala> def m[T <: {def name: String}](x: T) = x.name
> m: [T <: AnyRef{def name: String}](x: T)String
>
>
>

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

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

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

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

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

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?

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

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

Den 8 aug 2011 17:23 skrev "Eugen Labun" <labun@gmx.net>:
>> 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).

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

[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

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/2088da6e3...)

--
Eugen

[1] https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_0_1/src//lib...

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.

[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

On Thu, Aug 11, 2011 at 11:24 AM, Eugen Labun <labun@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

On Thu, Aug 11, 2011 at 11:40 AM, Eugen Labun <labun@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

On Fri, Aug 19, 2011 at 4:53 PM, John Nilsson <john@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
1: http://web.mac.com/ben_moseley/frp/paper-v1_01.pdf

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" <john@milsson.nu> wrote:

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

On Sat, Aug 20, 2011 at 2:32 AM, Tony Morris <tmorris@tmorris.net> wrote:

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" <john@milsson.nu> wrote: