User loginNavigation 
archivesThe complexity of abstract machinesI previously wrote about a brand of research by Guy Blelloch on the Cost semantics for functional languages, which let us make precise claim about the complexity of functional programs without leaving their usual and comfortable programming models (betareduction). While the complexity behavior of weak reduction strategies, such as callbyvalue and callbyname, is by now relatively wellunderstood, the lambdacalculus has a much richer range of reduction strategies, in particular those that can reduce under lambdaabstractions, whose complexity behavior is sensibly more subtle and was, until recently, not very well understood. (This has become a practical concern since the rise in usage of proof assistants that must implement reduction under binders and are very concerned about the complexity of their reduction strategy, which consumes a lot of time during type/proofchecking.) Beniamino Accatoli, who has been coauthoring a lot of work in that area, recently published on arXiv a new paper that has survey quality, and is a good introduction to this area of work and other pointers from the literature.
By gasche at 20170112 01:09  Lambda Calculus  login or register to post comments  other blogs  50306 reads

Browse archivesActive forum topics
New forum topics

Recent comments
2 days 1 hour ago
3 days 19 hours ago
2 weeks 20 hours ago
3 weeks 1 hour ago
3 weeks 6 days ago
5 weeks 5 days ago
6 weeks 1 day ago
7 weeks 1 day ago
7 weeks 5 days ago
7 weeks 5 days ago