Spines

The result of null?, pair?, or atom? may be S or even metastatic even if its argument is partially dynamic. cogen handles them specially to avoid lifting to D.

Consider the length procedure applied to a typical partially static alist (as in section Environments). Somewhere it makes this test:

(code length
      (l n k)
      ((prim t atom? l)
       (if t ((return ...)))
       (loop ...)))

L is partially static, so if $\\widetilde{atom?}$ = $\\widetilde{prim}$ then l would be lifted to D, so t would be D, and we lose. Instead, the generated compiler can test the static value. This requires no modification to the binding time lattice, only implementation of $\\widetilde{atom?}$ .

Whereas a human programmer would be unlikely to write code having a test with a metastatic result, such code could easily be automatically generated by a higher layer or the lift compiler (see lifting). Extending $\\widetilde{atom?}$ to have metastatic results requires adding another bit to the binding times for conses:

bt ::= S | D | (cons bt bt cp is-clo is-sure) | (const v)
cp ::= instruction
is-clo ::= boolean
is-sure ::= boolean
v ::= any-value

If a cons has never been joined with S, then it is guaranteed to be a cons, and no longer approximates a static atom:

(cons a d cp ic #t)  S --> (cons a d cp ic #f)

This is a big change to the lattice, but I think it's still safe. A formal definition of the ordering of the lattice and a soundness proof remain. Its full ramifications for cogen are not completely understood.

You could also just not reduce such things, and leave them as lub (or) nodes in the binding times. I did this originally, and this is basically what [Mogenson89] does: represent binding times with grammars instead of with graphs (only real difference is garbage collection and normal form properties). Simlix and Schism don't have this bit.