<p>I am looking for implementation of optimal reduction for λ-calculus based on interaction nets (<a href="http://www.sciencedirect.com/science/article/pii/S1571066105803639" rel="nofollow">McCarthy's amb</a> allowed) in the spirit of <a href="http://www.sciencedirect.com/science/article/pii/S1571066106000934" rel="nofollow">"Token-Passing Nets: Call-by-Need for Free" by François-Régis Sinot</a>. 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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-09-22T14:59:42.063Z
Eventually, I would like to replace the current evaluation strategy in my Web-based implementation https://codedot.github.io/lambda/ of the solution by François-Régis Sinot with optimal reduction. However, I could not find a suitable version of Lamping's algorithm yet.
Anton Salikhmetov
CC BY-SA 3.0
2015-10-20T09:33:19.913Z
I managed to derive a token-passing net implementation of optimal reduction http://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.
Anton Salikhmetov
<lambda-calculus><interaction-nets>
Optimal reduction using token-passing nets
Anton Salikhmetov
# Optimal reduction using token-passing nets

(Asked by: username_0 on 2015-09-22)

I am looking for implementation of optimal reduction for λ-calculus based on interaction nets ([McCarthy's amb](http://www.sciencedirect.com/science/article/pii/S1571066105803639) allowed) in the spirit of ["Token-Passing Nets: Call-by-Need for Free" by François-Régis Sinot](http://www.sciencedirect.com/science/article/pii/S1571066106000934). 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.

**Tags:** lambda-calculus, interaction-nets

> **Comments:**
> **username_0**: Eventually, I would like to replace the current evaluation strategy in my Web-based implementation https://codedot.github.io/lambda/ of the solution by François-Régis Sinot with optimal reduction. However, I could not find a suitable version of Lamping's algorithm yet.  
> **username_0**: I managed to derive a token-passing net implementation of optimal reduction http://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.  

---

## 0 answers

