Title: The Complexity of Abstract Machines,
Abstract: The lambda-calculus is a peculiar computational model whose definition does
not come with a notion of machine. Unsurprisingly, implementations of the
lambda-calculus have been studied for decades. Abstract machines are
implementations schema for fixed evaluation strategies that are a compromise
between theory and practice: they are concrete enough to provide a notion of
machine and abstract enough to avoid the many intricacies of actual
implementations. There is an extensive literature about abstract machines for
the lambda-calculus, and yet-quite mysteriously-the efficiency of these
machines with respect to the strategy that they implement has almost never been
studied.
This paper provides an unusual introduction to abstract machines, based on
the complexity of their overhead with respect to the length of the implemented
strategies. It is conceived to be a tutorial, focusing on the case study of
implementing the weak head (call-by-name) strategy, and yet it is an original
re-elaboration of known results. Moreover, some of the observation contained
here never appeared in print before.