Is it usual for interaction nets to leave piles of redundant fans?

Question

I'm compiling lambda calculus terms to interaction nets in order to evaluate them using Lamping's abstract algorithm. In order to test my implementation, I used this church-number division function:

div = (λ a b c d . (b (λ e . (e d)) (a (b (λ e f g . (e (λ h . (f h g)))) (λ e . e) (λ e f . (f (c e)))) (b (λ e f . e) (λ e . e) (λ e . e)))))

Dividing 4 by 4 (that is, (λ k . (div k k)) (λ f x . (f (f (f (f x)))))), I get this net:

(Sorry for the awful rendering. λ is a lambda, R is root, D is a fan, e is eraser.)

Reading this term back, I get the church number 1, as expected. But this net is very inflated: it has a lot of fans and erasers that serve no obvious purpose. Dividing bigger numbers is even worse. Here is div 32 32:

This again reads back as one, but here we can see an even longer tail of redundant fan nodes. My question is: is this an expected behavior of interaction needs when reducing that particular term or is this a possible bug on my implementation? If this isn't a bug, is there any way around that?

Answer 1

Yes, it is usual (but there are techniques to lessen its presence)

Abstracting from some details of your implementation with Interaction Nets, and also from your hypothesis of soundness of the abstract algorithm for your div, everything seems just fine to me.

• No further interaction can be applied to the output you show, in spite of chi's claim, because none of the pairs D-e can interact through their principal port.

• This latter kind of reduction rule (that is not allowed by IN framework) may improve efficiency and it is also sound in some particular cases. Basically, the involved fan must not have any "twin", i.e. there must exists no D' in the net such that eventually the annihilation D-D' can happen. For more details, look at The optimal implementation of functional programming language, chapter Safe nodes (which is available online!), or at the original paper from which that came:

  Asperti, Andrea, and Juliusz Chroboczek. "Safe Operators: Brackets Closed Forever Optimizing Optimal λ-Calculus Implementations." Applicable Algebra in Engineering, Communication and Computing 8.6 (1997): 437-468.

• Finally, the read-back procedure must be intended not as some sort of external cost for your reduction precedure, but rather as a deferred cost of computing duplication and erasure. As you notice, such a cost is rarely negligible, so if you want to test efficiency in a real-world scenario, always sum up both sharing reduction and read-back reduction.