Type Unfolding

[Fergus Henderson]

Peter David ROSS, you wrote:
> 
> Here is a brief outline of my thoughts on type unfolding.
> 
> Could you comment on it.
> 
> Also I really am not sure where it type unfolding should occur.  I was
> thinking after type checking, but I don't know.

Yes, I think just after type checking is the right time.

> TYPE UNFOLDING
> ==============
> 
> DESCRIPTION
> -----------
> 
> Type unfolding is the following process.
> 
> If we have the following:
> 
> :- type t1 ---> top(t2, t3).
> :- type t2 ---> f(int, int).
> :- type t3 ---> g(float, float).
> 
> We really could have the following type
> 
> :- type T1 ---> top(int, int, float, float).

Uh, that's an example, not a specification.
I'd like to see a specification.

> This would mean that in the compiler there would be less chains of
> pointers to follow as one deconstructs the types.

That's one advantage.  Another is that there are fewer memory allocations
needed to construct a value of such a type.

There are some disadvantages, though.
e.g. consider

	:- 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 must become

	foo(X, C, Y) :-
		X = top(A1, A2, _, _),
		C = g(C1, C2),
		Y = top(A1, A2, C1, C2).

This will be less efficient: it allocates and initializes
four words of memory, instead of two.

> ISSUES
> ------
> 
> * Recursive types.
> 
> Types which are recursive such as trees cannot be unfolded.
> 
> * Polymorphism.
> 
> No idea.
> 
> * Types which are exported.
> 
> If the type is exported there can be problems.  How do things in the
> other modules know if the type has been unfolded.
>
> * Sub-types
> 
> If the type has been flattened and the predicate makes a call to another
> predicate which requires the sub-type then we need to handle it.
> 
> Also what happens if the sub-types have alternatives, think about how to
> handle tags.
> 
> 
> PLANS
> -----
> 
> Assume that the optimisation is done on the HLDS level, where should it
> be done?
> 
> Phase 1 would be to do type unfolding for types which are local to the
> module.  (except for the builtin types)
> 
> Phase 2 would be to do it over the whole system.
> 
> 
> LOCAL MODULE
> 
> 1.  Construct a list of the types which are local to the module or
>     builtin.
> 
> 2.  Put these types into a relation and use that to work out which types
>     are recursive and which types can be unfolded.
> 
> 3.  Unfold the types by modifing the specification for each predicate
>     that uses the type.

The above plan looks OK.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.