[plt-scheme] typed scheme vs. PLAI types

Hi Matthias,

thanks, that sounds good! (And thanks for the explanation of what a tagged vs. set-theoretic unions imply!). Just one question, I wonder why I would want to define overlapping variants?

Ciao,
Sigrid



Am 08.02.2010 um 21:43 schrieb Matthias Felleisen:

> 
> TS will soon come with a facility for defining a type that looks like an algebraic union. Of course, since the purpose of TS is to provide a target for enriching untyped code with type specifications, this type is a true union (as in set theory) not a tagged union (as in ML or Haskell). Practical meaning: If your variants overlap, you won't be able to distinguish how the values made it into the type.
> 
> Watch for announcements on this list -- Matthias
> 
> 
> 
> 
> 
> 
> On Feb 8, 2010, at 3:03 PM, keydana at gmx.de wrote:
> 
>> Hi all,
>> 
>> I have a (naive and hopefully not too stupid :-;) question about defining algebraic data types in typed scheme.
>> 
>> I would like to define type aliases and algebraic data types for a  relational algebra. I don't know too much of Haskell, but I find algebraic data types helpful to think about data representation, so in order to find an "example" I could then follow in typed scheme,
>> I started out with the following (just as a first approximation):
>> 
>> type Relation = (Attlist, [Tuple])
>> 
>> type Attlist = [Attribute]
>> type Attribute = (String, String)
>> 
>> type Tuple = [String]
>> 
>> data Expr = Prop | RelExpr
>> 
>> data RelExpr = Project Relation Attlist
>>            | Restrict Relation Prop
>>            | Join [Relation]
>> 
>> data Prop = Const Bool
>>         | Is Expr Expr
>>         | And Prop Prop
>>         | Or Prop Prop
>> 
>> 
>> 
>> When I try to do a similar thing in typed scheme, it looks fine for the type aliases, but regarding the algebraic types, it seems to me I have to define structures and then a type alias which defines a union of them:
>> 
>> 
>> 
>> (define-type-alias Relation (Pair Attlist (Listof Tuple)))
>> 
>> (define-type-alias Attlist (Listof Attribute))
>> (define-type-alias Attribute (Pair String String))
>> 
>> (define-type-alias Tuple (Listof String))
>> 
>> (define-struct: Project ((rel : Relation) (attl : Attlist)))
>> (define-struct: Restrict ((rel : Relation) (prop : Prop)))
>> (define-struct: Join ((rels : (Listof Relation))))
>> 
>> (define-type-alias RelExpr (U Project Restrict Join))
>> 
>> (define-type-alias Expr (U Prop RelExpr))
>> 
>> (define-struct: Is ((expr1 : Expr) (expr2 : Expr)))
>> (define-struct: And ((expr1 : Expr) (expr2 : Expr)))
>> (define-struct: Or ((expr1 : Expr) (expr2 : Expr)))
>> 
>> (define-type-alias Prop (U Boolean Is And Or))
>> 
>> 
>> 
>> This looks rather ugly, especially having structs for the Is, And and Or expressions... I guess this should  be done completely differently, but I don't see how. (So my first question would be, how can I do this better in typed scheme?)
>> 
>> What I would in fact like is a define-type like in PLAI, where it would look like this ( I'm leaving out the aliases, as I don't know how to define them in PLAI):
>> 
>> (define-type Prop
>> (CONST (b boolean?))
>> (IS (e1 Expr?) (e2 Expr?))
>> (AND (p1 Prop?) (p2 Prop?))
>> (OR (p1 Prop?) (p2 Prop?)))
>> 
>> (define-type RelExpr
>> (Project (r Relation?) (a Attlist?))
>> (Restrict (r Relation?) (p Prop?))
>> (Join (r1 Relation?) (r2 Relation?)))
>> 
>> 
>> My second question is, why does typed scheme not have such a define-type? (I find it very appealing because it makes the algebraic type definition very concise.)
>> 
>> 
>> Many thanks in advance,
>> Sigrid
>> 
>> 
>> 
>> 
>> 
>> _________________________________________________
>> For list-related administrative tasks:
>> http://list.cs.brown.edu/mailman/listinfo/plt-scheme