Interaction net optimization strategies

[cwgoes]

How best to optimize (~ reduce normalization time & space cost) interaction nets?

Note that the following properties have to be preserved:

• Locality on active pairs
• Strong confluence
• Linearity (can be relaxed given optimal reduction)

Possible strategies:

• Directly compile core-language functions to new primitive node types and rewrite rules Definitely necessary for e.g. integer operations, should generalize. Possibly choose this automatically for short functions based on cost analysis.
• Speculative execution (branched rewrite) on finite types, e.g. booleans or integers. Optimal reduction may (should?) render this unnecessary.
• Optimize memory layout for spacial contiguity Nodes next to each other in the graph should be contiguous in memory addresses. Whether this matters depends on memory access costs and cache behaviour.
• Trade time for space in optimal reduction. Discard & later recalculate (if necessary) subgraphs according to some LRU-ish algorithm.
• Target parallelism in translation from lambda calculus (see this paper perhaps)

[cwgoes]

Directly compile core-language functions to new primitive node types and rewrite rules Definitely necessary for e.g. integer operations, should generalize. Possibly choose this automatically for short functions based on cost analysis.

This is likely a necessary approach. What cost metric should be used for choice - platform-dependent?

It's not necessary decidable; may be input-dependent (e.g. with recursion based on argument value).

A few options:

• Directly compile functions of small size with no shared evaluations (easy).
• Allow the programmer to denote "inet-inlined" or "non-inlined" functions (easy, can be combined).
• Estimate cost based on trying a few thousand random inputs, choose cheapest (med).
• Runtime JIT according to actual use patterns (bookkeeping costs? - in any case hard).

[cwgoes]

I suspect we will end up bespoke encoding most unbounded recursive functions and thus avoid that space concern (e.g. fib being unrolled into a case-switch for the first n integers whenever called).