typechecker wish

Subject: typechecker wish
From: Craig Chambers (chambers@cs.washington.edu)
Date: Mon Jan 15 2001 - 17:10:54 PST

I'm trying to put in accurate types for the Whirlwind dataflow analysis engine,
and I'm trying to get the type parameterization to work right.

One of my interfaces is AnalysisGraph, the dependence graph over which analysis
is done:

abstract object AnalysisGraph[`E <= IREdge, `P <= AnalysisPriority[P]];

The graph is parameterized by the kinds of edges in the graph, and the way in
which nodes of the graph are ordered (e.g. topological order). No problem so
far.

Now I want to define the abstract interface for the information that a client
analysis stores on each edge, AnalysisInfo:

abstract object AnalysisInfo[I <= AnalysisInfo[I]]
                                        isa comparable[AnalysisInfo[I]];

The AnalysisInfo is parameterized by the particular kind of analysis info being
represented, in the standard idiomatic way to define the abstract interface to
comparable types (it effectively simulates a more flexible form of MyType using
F-bounded polymorphism). Still, no problem.

Now I want do define the abstract interface for a client dataflow analysis,
Analysis. Analysis should be parameterized by the particular analysis info and
the particular analysis graph. I'd like to write the following:

abstract object Analysis[`I <= AnalysisInfo[I],
                         `G <= AnalysisGraph[`E, `P]]

However, the current Cecil typechecker doesn't let me. It doesn't allow
implicit binding of the `E and `P arguments of the AnalysisGraph upper bound.
It instead forces me to write the following:

abstract object Analysis[`I <= AnalysisInfo[I], `G <= AnalysisGraph[E, P],
                         `E <= IREdge, `P <= AnalysisPriority[P]];

Here, the E and P parameters are made explicit. (I have gotten all my code to
successfully typecheck using this declaration.)

This is less desirable, because all clients have to specify the additional two
type parameters, E and P, even though they're redundant with the specification
of the particular AnalysisGraph type.

Also, it's inconsistent with how we allow formal argument types to contain
implicit parameter bindings, e.g.

method analyze(analysis:Analysis[`AnalysisInfo, `AnalysisGraph,
                                 `IREdge, `AnalysisPriority],
               graph:AnalysisGraph,
               incoming_infos:indexed[AnalysisInfo]
               ):pair[indexed[AnalysisInfo],
                      indexed[TransformAnalysisAction[AnalysisInfo,
                                                      AnalysisGraph,
                                                      IREdge,
                                                      AnalysisPriority]]]
{ ... }

Here, the analysis argument contains the backquoted argument types, which binds
those type names in the rest of the method declaration, and furthermore
implicitly constrains those types to be known to satisfy whatever constraints
are required of the parameters of the Analysis type (defined in the declaration
of Analysis). I didn't have to write:

method analyze[`I <= AnalysisInfo[I], `G <= AnalysisGraph[E, P],
               `E <= IREdge, `P <= AnalysisPriority[P]](
               analysis:Analysis[I, G, E, P],
               graph:G,
               incoming_infos:indexed[I]
               ):pair[indexed[I],
                      indexed[TransformAnalysisAction[I, G, E, P]]]
{ ... }

nor did callers of analyze have to specify a bunch of extra type parameters.

I propose that we make upper bounds of type parameters similarly be able to
include backquoted type parameters, along with inference of the appropriate
constraints on such type parameters. I don't think this should be too
difficult, since we already support all the functionality for method formal
parameters. The analyze method itself would simplify, because Analysis and
TransformAnalysisAction would lose two uninteresting type parameters:

method analyze(analysis:Analysis[`AnalysisInfo, `AnalysisGraph],
               graph:AnalysisGraph,
               incoming_infos:indexed[AnalysisInfo]
               ):pair[indexed[AnalysisInfo],
                      indexed[TransformAnalysisAction[AnalysisInfo,
                                                      AnalysisGraph]]]
{ ... }

The only thing we still wouldn't get with this change is a way to talk about the
arguments of the AnalysisGraph type, i.e., the particular bindings of IREdge and
AnalysisPriority used by the type that was bound to the AnalysisGraph type
variable. I'd like to be able to say something like `AnalysisGraph[`IREdge,
`AnalysisPriority] in place of just `AnalysisGraph above, to bind the extra type
parameter names in case I need to refer to them in the type of analyze or in its
body, e.g.:

method analyze(analysis:Analysis[`AnalysisInfo,
                                 `AnalysisGraph[`IREdge, `AnalysisPriority]],
               graph:AnalysisGraph,
               incoming_infos:indexed[AnalysisInfo]
               ):pair[indexed[AnalysisInfo],
                      indexed[TransformAnalysisAction[AnalysisInfo,
                                                      AnalysisGraph]]]
{ ... edges:indexed[IREdge] := graph.incoming_edges; ... }

This may be more difficult to implement, however.

What do you all think?

Vass, how hard would it be to implement at least the first of what I propose?

-- Craig

This archive was generated by hypermail 2b25 : Mon Jan 15 2001 - 17:11:01 PST