1
$\begingroup$

I am looking for implementation of optimal reduction for λ-calculus based on interaction nets (McCarthy's amb allowed) in the spirit of "Token-Passing Nets: Call-by-Need for Free" by François-Régis Sinot. Implementations of optimal reduction that I am aware of either assume a specific strategy for the interaction net reduction, or involve non-pure graph reductions rather than just interaction rules.

The reason why I am interested in such implementation is that I already have a compiler for interaction nets which is based on interaction calculus, but is agnostic to any notion of interface, thus unable to follow any strategy while reducing a configuration simply represented as a queue of active pairs.

Improve this question
$\endgroup$
3
  • $\begingroup$ Might this be more appropriate at cs.stackexchange.com? $\endgroup$
    – Noah Schweber
    Commented Sep 22, 2015 at 16:08
  • $\begingroup$ It might, indeed. I just asked this question there as well cstheory.stackexchange.com/questions/32602/… $\endgroup$
    – Anton Salikhmetov
    Commented Sep 22, 2015 at 16:19
  • $\begingroup$ I managed to derive a token-passing net implementation of optimal reduction codedot.dreamwidth.org/174955.html by introducing a waiting construct. However it results in too much overhead and significantly worse overall performance than call-by-need implementation by Sinot. $\endgroup$
    – Anton Salikhmetov
    Commented Oct 20, 2015 at 9:34

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .