[plt-scheme] typed scheme vs. PLAI types

People in untyped languages often -- but not always -- work with  
unions where the pieces do not overlap. Because of the exception, TS  
must be prepared to accommodate both kinds. After all TS exists so  
that you can port untyped PLT programs into the typed world.


On Feb 9, 2010, at 4:20 PM, keydana at gmx.de wrote:

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