## User login## Navigation |
## How efficient is partial sharing?Partial sharing graphs offer a reduction model for the lambda calculus that is optimal in a sense put forward by Jean Jacques Levy. This model has seen interest wax and wane: initially it was thought to offer the most efficient possible technology for implementing the lambda calculus, but then an important result showed that bookkeeping overheads of any such model could be very high (Asperti & Mairson 1998). This result had a chilling effect on the initial wave of excitement over the technology. Now Stefano Guerrini, one of the early investigators of partial sharing graphs, has an article with Marco Solieri (Guerrini & Solieri 2017) arguing that the gains from optimality can be very high and that partial sharing graphs can be relatively close to the best possible efficiency, within a quadratic factor on a conservative analysis (this is relatively close in terms of elementary recursion). Will the argument and result lead to renewed interest in partial sharing graphs from implementors of functional programming? We'll see... (Asperti & Mairson 1998) Parallel beta reduction is not elementary recursive. (Guerrini & Solieri 2017) Is the Optimal Implementation inefficient? Elementarily not. |
## Browse archives## Active forum topics |

## Recent comments

1 hour 41 min ago

3 hours 5 min ago

4 hours 32 min ago

5 hours 42 min ago

6 hours 23 min ago

9 hours 11 min ago

10 hours 15 min ago

12 hours 35 min ago

18 hours 7 min ago

19 hours 20 min ago