Deforestation optimises a functional program by transforming it into another one htat does not create certain intermediate data structures.Short cut deforestation is a deforestation mehtod which is based on a single,local transformation rule.In return,short cut deforestation expects both producer and ocnsumer of the intermediate structure in a certain form.Warm fusin was propsoed to automatic ally transform functins into this form.unfortunately,it is costly and hard to implement.Stating from the fact that short cut defroestation is based on a parametricity theorem of the second-order typed #lambda#-calculus,we show how the requried form of a list producer cna be derived by the use of type inferene.Typability for the second-orde tyepd #lambda#-calculus is undecidable.However,we presetn a linear-time algorithm that solves a partial type inferene prolem and that ,together with controlled inlining and polymorphic type instantiation,suffices for deforestation.The resulting new short cut deforestation algorithm is efficient and removes more intermediate lists than the original.
展开▼
