[Haskell] SPJ book - big idea behind supercombinator reduction
paul_bostonjp at hotmail.co.uk
Sat Oct 8 13:36:49 EDT 2005
Simon Peyton Jones's book "The Implementation of Functional Programming
Languages", chapter 13 (Supercombinators and Lamba-lifting), page 222,
describes a "multi-argument" beta-reduction strategy whereby several free
variables of a multi-argument abstraction may be instantiated
Then, on page 225 the following sentence appears:
"A crucial point in the definition of a supercombinator given above is that
a supercombinator reduction only takes place when all the arguments are
I feel that there's some big idea in the pages between these two references,
but I can't quite grasp it.
I can appreciate that there are good reasons (e.g. efficiency) to
instantiate several variables at once, but I don't quite understand why this
restriction is "crucial".
Is it crucial just for reasons of efficiency - and in actual fact it's
entirely possible, albeit inefficient, to instantiate one variable at a
time? Or is it, given that the whole point of supercombinators is to allow
compilation to fixed code sequences for the G-machine, that there is a good
reason to avoid having these fixed code sequences deal with instantiating
one free variable at a time (simplicity of design, or some kind of
restriction on the way that G-machine operations work)? Or is there a deeper
theoretical reason related to the combinators themselves that has nothing to
do with the downstream compilation process?
Be the first to hear what's new at MSN - sign up to our free newsletters!
More information about the Haskell