Type Unfolding Mark II

Peter David ROSS petdr at students.cs.mu.oz.au
Thu Mar 13 15:00:25 AEDT 1997


Specification for type unfolding

Any type which consists of one constructor can be flattened into its
component types.  If any component of the flattened type is also a type
with one constructor, then it can also be flattend.

i.e.
:- type t1 ---> top(t2, t3).
:- type t2 ---> f(int, int).
:- type t3 ---> g(float, float).

If we then had the following predicate

        :- pred foo(t1, t3, t1).
        :- mode foo(in, in, out) is det.
        foo(X, C, Y) :-
                X = top(A, _),
                Y = top(A, C).

After type unfolding, this should become

        foo(X_A1, X_A2, X_C1, X_C2, C_1, C_2, Y_A1, Y_A2, Y_C1, Y_C2) :-
                Y_A1 = X_A1,
                Y_A2 = X_A2,
                Y_C1 = C_1,
                Y_C2 = C_2.

We would then need to run the unused arguments predicate on the above
example to remove X_C1 and X_C2.

I am not sure if there is any disadvantage in completely flattening the
type above in terms of the implementation, so I would appreciate any
comments.

The above scheme course falls down if we change the predicate to be the
following, because we cannot must stop unfolding at the top level
functor for the type in order to store them in the list (as in my
first post).

        :- pred foo(list(t1), list(t3), list(t1)).
        :- mode foo(in, in, out) is det.
        foo([], [], []).
        foo([X | Xs], [C | Cs], [Y | Ys]) :-
                X = top(A, _),
                Y = top(A, C).

This is of course where it gets complicated, because we have to start
being careful in each predicate of exactly how far the type has been
unfolded and that may cause a lot of overhead as one converts between
the two representations of the unfolded type.  Hopefully this will be
recognised and we will not unfold the type.

Any comments appreciated.

Pete.
-- 
 +-----------------------------------------------------------------+
 | Peter Ross    Sci/Eng Melbourne Uni                             |
 | email: petdr at cs.mu.oz.au  WWW: http://www.cs.mu.oz.au/~petdr    |
 +-----------------------------------------------------------------+



More information about the developers mailing list