/**
 * A collection of strategies that keeps traversing a term until
 * no more applications of some strategy to the nodes can be
 * found.
 */
module strategy/traversal/fixpoint
imports 
  strategy/iteration 
  strategy/traversal/simple
  strategy/general/memo
strategies

  // reduce(s) = repeat(rec x(s + one(x)))

  reduce(s) = 
    repeat(rec x(some(x) + s))

  outermost(s) = 
    repeat(oncetd(s))

  innermost'(s) = 
    repeat(oncebu(s))

  innermost(s)  = 
    bottomup(try(s; innermost(s)))

  innermost-old(s) =
    rec x(all(x); (s; x <+ id))

  pseudo-innermost3(s) =
    rec x(all(x); rec y(try(s; all(all(all(y); y); y); y)))

  innermost-memo(s) =
    rec x(memo(all(x); (s; x <+ id)))

 /**
  * innermost-tagged(s) reduces the subject term by applying s to
  * innermost redices first. Terms in normal form are tagged (using
  * attributes) to prevent renormalization.
  */
  innermost-tagged(s : a -> a) = // : a -> a
    where(new => tag);
    rec x(?_{tag} <+ (all(x); (s; x <+ !<id>{tag})));
    bottomup(?<id>{tag})