Currently, type tasks are collected using an alltd traversal. However, alltd does not execute the strategy on subterms if the strategy succeeds for the superterm. This causes some terms to not be annotated with their type.
For example, the type task collection for Call:

type-of-task(|partition): 
  Call(_, x, _) -> <resolve-type(|partition)> x

prevents the type task for the expression of the call to be executed.

There are two ways to fix this:

• Explicitly execute type task collection for subterms. For example, the type task collection for Call would also collect and annotate the expression.
• Use a bottomup traversal so that the leaves of the tree are annotated first.

Submitted by Gabriël Konat on 3 May 2013 at 15:50

Fixed using bottomup.

IMO, the task rule for the call is the issue. Only well-typed expressions should have types, thus this needs to be checked in the type rule. This check would get the types of the children, and by this trigger their annotation.

Alltd gives us a complexity of O(n), since every subterm is visited once, either by alltd or by the manual traversal in the type-task rules. Bottomup makes this O(n^2), since all subtasks are re-generated at each upper level, since the manual traversal goes down again.

If this is for any reason not wanted, the types are needed for resolution and we could call type-task on any term that needs a type for name resolution.

The tasks are not re-generated, they are retrieved from the annotations of subterms. They only look one level deep.