On Thursday 2015-09-24, at 10:30, in room Byron Blanc,
Speaker: Claudio Sacerdoti Coen
Title: On the Relative Usefulness of Fireballs
Publication: Beniamino Accattoli, Claudio Sacerdoti Coen, LICS 2015.
Abstract:
In CSL-LICS 2014, Accattoli and Dal Lago showed that there is an implementation of the ordinary (i.e. strong, pure, call-by-name) lambda-calculus into models like RAM machines which is polynomial in the number of beta-steps, answering a long-standing question. The key ingredient was the use of a calculus with useful sharing, a new notion whose complexity was shown to be polynomial, but whose implementation was not explored. We study useful sharing in a call-by-value scenario, introducing a new reduction machine to reduce open terms according to call-by-value and that has only a _LINEAR_ overhead with respect to the number of beta-steps.
