[Types-sig] parameterized typing (was: New syntax?)

[Greg Stein]

Hrm. Looks like I deleted Paul's original note. I've got some ideas now on
how to do parameterized types, so I'll just piggyback on Martijn's :-)

On Fri, 17 Dec 1999, Martijn Faassen wrote:
> Paul Prescod wrote:
> > Martijn Faassen wrote:
> > > ...
> > > Didn't you think parameterized types looked fairly straightforward in my
> > > syntax proposal?
> > 
> > I must have missed something. Could you show me how to do Btree of X and
> > then make concrete types Btree of Int and Btree of Functions From String
> > to Int?

The first issue to handle with parameterized classes is how to specify the
parameter(s) to be used in your class definition. Tim's "decl" keyword
comes into play here. So lets jump in with definition-by-example:

class Btree:
  decl param _T: any    # the parameter can have any type

  def insert(self, value: _T) -> None:
    ...

  def asList(self) -> [_T]:
    ...


Now that we have defined and declared our Btree class, we can parameterize
it in later declarations:

decl tree1: Btree(Int)               # Paul's first request
decl tree2: Btree(def(String)->Int)  # Paul's second request

tree1.insert("foo")   # causes type-check error; we're passing wrong type
l = tree1.asList()    # we know that <l> is [Int]

Other examples of param declarations might be:

decl param _T: Int or String or Tuple
decl param _S: [Int] or [Float]

It is interesting to note that the above lines are almost exactly the same
as doing:

_T = typedef Int or String or Tuple
_S = typedef [Int] or [Float]

The only difference is that (in the decl case) Python understands that _T
and _S are type-substitution parameters. If a true typedef was used in the
Btree class definition, then we would simply end up with a
non-parameterizable class that had "any" in some of its declarations.
Note that the compiler *does* treat the declarations using the typedef
notion: it can perform optimizations, type checks, and other stuff as if
"any" was used. To be clear:

class Foo:
  decl param _T: Int or Float

  def bar(self, value: _T) -> _T:
    return 2 * value

In the above code, the compiler uses _T as a typedef and optimizes the
"2 * value" line, knowing that "value" is either an Int or a Float.
Runtime checks are present, as usual. The "decl param" is only important
to *users* of class Foo -- the _T becomes part of Foo's interface and
type substitutions can be made.

---- Point (1)   (this will be important later)

One issue is that Btree has no (runtime) argument checks in the above
example. "any" is allowed for the insert() parameter, which effectively
means "no type check." In other words, Btree is still an abstract
implementation; the concreteness is only present in compile-time type
checks.

Recall my previous note regarding type declarators. Note that a type
declarator object can be a type, a class, an interface, or a composite.
For example:

t1 = typedef Int         # typedecl of a type
t2 = typedef Btree       # typedecl of a class
t3 = typedef Sequence    # typedecl of an interface
t4 = typedef Btree(Int)  # typedecl of a composite

I might suggest that, in the same way instances are created, we can create
concrete classes through the use of type declarators:

BtreeInt = typedef Btree(Int)
tree = BtreeInt()

In other words, typedecl objects are callable. A typedecl that is a class
or a parameterized class will instantiate an object.

So what does "concrete class" actually give you? (note that I mean
something other than the type checks mentioned above)  I think a concrete
class would be an on-the-fly constructed subclass of the abstract class.
Each method would be overridden: a method arg runtime check is done, then
a call to the abstract method if performed. For example:

class __compiler_built_Btree_Int(Btree):
  def insert(self, value: Int)->None:
    return Btree.insert(self, value)
  def asList(self)->[Int]:
    return Btree.asList(self)

The notion of "concrete class" (to me) simply means the addition of
runtime checks to enforce the type constraint.

Theoretically, the system could recompile the Btree class and perform
various optimizations. But: I don't think that is really possible, given
Python's model (the source may not be readily available, and there isn't a
way for the compiler to reach into the middle of a source file to grab the
Btree class source and rebuild a concrete version).

Given that we have compile-time checks with the simplest notion of
parameterized types, I don't see the runtime checks offering a whole lot
more. Especially for the complexity involved.

I think I'll take Tim's tack here: the notion of on-the-fly building
concrete classes won't work; the example above is a before-somebody-
suggests-it counterproof.

So, I would say everything above Point (1) is valid. Everything below
should not be dealt with.

Paul: does this sufficiently address your desire for parameterized types?
Others: how does this look? It seems quite Pythonic to me, and is a basic
extension of previous discussions (and to my thoughts of the design).

Cheers,
-g

-- 
Greg Stein, http://www.lyra.org/