[plt-scheme] typed scheme vs. PLAI types

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