Record number :
16842
Title of article :
The Under-Appreciated Unfold
Author/Authors :
Gibbons، Jeremy نويسنده , , Jones، Geraint نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1999
Pages :
-272
From page :
273
To page :
0
Abstract :
Arity raising, also known as variable splitting or flattening, is the program optimization which transforms a function of one argument into a function of several arguments by decomposing the structure of the original one argument into individual components in that structure. This optimization eliminates the need for the structuring of the components and also allows more arguments to be passed in registers during a function call. We present a formal specification of arity raising for a higher-order functional language. This specification supports the general arity raising of functions, even for functions which are passed as arguments or returned as values. We define a practical algorithm, based on algorithm W, which implements arity raising, and we prove this algorithm sound with respect to the deductive system. These results provide a declarative framework for reasoning about arity raising and support a richer form of the transformation than is currently found in compilers for functional languages.
Keywords :
Program calculation , functional programming , unfold , anamorphism , traversal , breadth-first , fold , level-order , co-induction
Journal title :
A C M Sigplan (Programming Languages) Sigplan Notices
Link To Document :