Top Up Prev Next Bottom Contents Index Search

6.10 The PortHole type resolution algorithm

The type resolution algorithm is concerned with assigning concrete types to ANYTYPE portholes and resolving conflicts between the types of connected portholes. The algorithm is somewhat complex since it tries to produce convenient results in an area where the "right" behavior is not always easy to define. Ptolemy 0.7 introduces a new resolution algorithm that is hoped to produce more convenient and less surprising results than the method previously used.

The problem of connecting ports of different types is simple to resolve: we say that the input porthole determines what particle type to use, and that any necessary type conversion takes place when the output porthole puts data into a particle (or buffer variable, in the case of codegen domains). The opposite convention would be about equally defensible, but this is the one that has historically been used in Ptolemy. It has the advantage that star writers can presume that the declared type of an input porthole is the data type that will actually be received, whenever the declared type is not ANYTYPE.

Resolving ANYTYPE portholes is much more difficult. We need to handle several fundamental cases:

1. Printer and similar polymorphic stars, which accept any input type. They simply declare their inputs to be ANYTYPE, and we need to resolve them to the type of the connected output. (Introducing any forced particle type conversion would be very undesirable.)

2. Fork and similar stars, which want to bind multiple outputs to the type of a given input. Here the input porthole and output portholes are ANYTYPE, and are bound into a type equivalence set by inheritTypeFrom(). If possible we want to resolve all these portholes to the type of the output porthole connected to the input.

3. Merge and similar stars, which have a single output type-equivalenced to multiple inputs. If the inputs all receive the same type of data, we should resolve the output to that type. If there is no common input type, but the input connected to the single output has determinable type, we can resolve the output porthole to that type (since the data would ultimately get converted to that type, anyway). If the connected input is ANYTYPE, we must declare error, because we have no good way to choose a type for the Merge's output.

We have to recursively propagate type information in order to deal with chains of ANYTYPE stars, such as one Fork following another. In some cases the type is really undefined. Consider this universe (using ptcl syntax):

star f Fork; star p Printer
connect f output f input
connect f output p input
There are no types anywhere in the system. We have little choice but to declare an error. Thus, the fact that we will sometimes fail to assign a type is not an implementation shortcoming but an unavoidable property of the problem.

These considerations lead to the following algorithm. We first perform a recursive scan to resolve ANYTYPE portholes, the results of which are represented by a "preferred" type assigned to each porthole. (A porthole of non-ANYTYPE declared type always has that type as its preferred type; so preferred type assignment is only interesting for ANYTYPE portholes.) Then, the "resolved" type of each connected pair of input and output portholes is the preferred type of the input porthole. This is the type that will be used for actual data transported between those portholes. It is useful to explicitly store the preferred type, so that codegen domains can detect type mismatches just by looking at individual output portholes. A type conversion star can be spliced in wherever an output is found that has preferredType != resolvedType. Assignment of preferred types proceeds in two passes. Pass 1 is "feed forward" from outputs to inputs. Pass 2 is "feed back" from inputs to outputs; it is the dual of Pass 1. Pass 2 is invoked only if Pass 1 is unable to choose a type for a porthole. The details are:

Pass 1:

Non-ANYTYPE portholes are simply assigned their declared type as preferred type. If an ANYTYPE porthole is not a member of an equivalence group, but is an input porthole and is connected to a porthole of pass-1-assignable type, that porthole's type becomes its preferred type. When an ANYTYPE porthole is a member of an equivalence group, the group is scanned to see if it includes any non-ANYTYPE portholes; if so, they must all agree in type, and that type becomes the preferred type of all members of the group. But usually, all the members of an equivalence set will be ANYTYPE. Then, pass 1 scans all the input portholes of the group to see whether their connected portholes have pass-1-assignable type. If at least one does, and all of the assignable ones have the same preferred type, then that common type becomes the preferred type of all the members of the equivalence group.

Pass 2:

If an unassigned ANYTYPE porthole is not a member of an equivalence group, but is connected to a porthole of type assignable by either pass 1 or pass 2, that porthole's type becomes its preferred type. When an ANYTYPE porthole is a member of an equivalence group, all the output portholes of the group are scanned to see whether their connected portholes have type assignable by either pass 1 or pass 2. If at least one does, and all of the assignable ones have the same preferred type, then that common type becomes the preferred type of all the members of the equivalence group.

Pass 1 handles Fork-like stars as well as Merge stars whose inputs all have the same type. Pass 2 does something reasonable with Merge stars that have inputs of different types: if the merge output is going to a port of knowable type, we may as well just output particles of that type. An error is declared if a porthole's type remains unassigned after both passes. This occurs if a Merge-like star has inputs of nonidentical types and an output connected to an (unresolvable) ANYTYPE input. The user must insert type conversion stars to coerce the Merge inputs to a common type, so that the system can figure out what type to use for the Merge output.

Notice that each pass will resolve an equivalence set if all the assignable connected portholes agree on a type; it is not required that all the connected portholes be assignable. This rule is needed to allow resolution of schematics that contain type-free loops. Here is an example:

domain DE
star imp Impulse; star m Merge; star f Fork
star d Delay; star p Printer
numports m input 2
connect imp output m input#1
connect m output f input
connect f output d input
connect d output m input#2
connect f output p input
This schematic will work if we resolve all the ports to FLOAT (the output type of Impulse). But if we insist on both Merge inputs being resolved before we assign a type to the Merge output, we will be unable to resolve the schematic. So, once Pass 1 has recursively traversed the schematic and concluded that it can't yet assign a type to Merge's input#2, it uses the FLOAT type found at input#1 to resolve the type of the Merge portholes. Further recursion then propagates this result around the schematic.

This rather baroque-looking algorithm does have some simple properties. In particular, all members of an equivalence set are guaranteed to be assigned the same preferred type; an error will be reported if this is not possible. In some domains it is important that members of an equivalence set have the same resolved type, not just the same preferred type. (For example, the CGC Fork star fails if this is not so, because its various portholes are all just aliases for a single variable.) The domain can check this by seeing whether preferred type equals resolved type for all portholes. If the types are not the same, it can either report an error or splice in a type-conversion star to make them the same.

Note:

It might be better to cause this to happen on a per-star-type basis, not a per-domain basis, since one can imagine that some CG blocks would need strict type equality of portholes while others would not. This improvement is not currently implemented; the CG domains just enforce it for all stars.
The porthole type resolution algorithm is dependent on the notion that every porthole is connected to just one other porthole. If class Geodesic is ever redesigned to support multiple connections directly, some work would be needed. A likely tactic is to move some or all of the resolution work into Geodesic. A one-to-one Geodesic could enforce the same behavior described above, but one-to-many or many-to-many Geodesics would need different, possibly domain-dependent behavior.



Top Up Prev Next Bottom Contents Index Search

Copyright © 1990-1997, University of California. All rights reserved.