[plt-scheme] Typed Scheme polymorphic variadic functions
On Mar 17, 2009, at 11:34 AM, Anthony Cowley wrote:
> Is there somewhere else I can find more explanation of this syntax?
I'll add something similar to the following to the documentation as
well, so that it's in the obvious place.
The types for non-uniform variadic functions are meant to abstract
over a family of related types. For example, take the types:
(All (R) (-> R))
(All (R A) (A -> R))
(All (R A B) (A B -> R))
(All (R A B C) (A B C -> R))
...
Then how can we abstract over this family of types? We want to take
in some number of type variables, and then use those as the domain to
our function type. So we write:
(All (R A ...) (A ... -> R))
Here the A ... is instantiated with a sequence of types, where that
sequence may be empty.
However, we may have multiple dotted type variables (like "A ..."
above) in scope at a given time,
e.g., (All (A ...) (All (B ...) ((A ... -> B) ... -> Number)))
so how do we know when a given ellipsis should be expanded? We mark
the ellipsis with the appropriate dotted type variable, so we get
(All (A ...) (All (B ...) ((A ... A -> B) ... B -> Number)))
So now it's clear that when the dotted type variable A is
instantiated, that we expand the innermost ellipsis, and then when B
is instantiated, we expand the outermost ellipsis. We call the
combination of the base (the template you noted), ellipsis, and bound
(the occurrence of a dotted type variable) a dotted pre-type.
Initially, dotted pre-types could only appear as the last part of the
domain of a function (since they often describe rest arguments).
However, they are now allowed to appear in some other useful type
constructors such as Values. Unfortunately, we have not yet handled
List, and so there's no way for you to write an appropriately generic
type for the listf function you provided. This work is something we
hope to do in the future.
Another source of information is a recently-published paper:
http://www.ccs.neu.edu/scheme/pubs/#esop09-sthf
Please let me know if this is unclear in any way, or if you have any
further questions.
HTH,
Stevie