research icon indicating copy to clipboard operation
research copied to clipboard

Interaction net garbage collection strategies

Open cwgoes opened this issue 5 years ago • 0 comments

If we only reduce primary pairs, we will end up performing unnecessary evaluation on garbage.

See e.g. BOHM p.26 if M is connected to an if-then-else subgraph which is disconnected.

We may be able to give up strong confluence (diamond property) but retain reduction equivalence after at least n steps (which is fine in practice), adding reduction rules which operate on primary ports of erasers and auxiliary ports of other node types, which could be more efficient. The worst-case n will be high but maybe we can almost always reduce in fewer steps by picking an intelligent strategy.

Not immediately high-priority.

cc @mariari

cwgoes avatar Jul 04 '19 14:07 cwgoes