folding
folding
1. An important method in program transformation, introduced by Burstall and Darlington. Many simple mathematical techniques for processing the equations and formulas of algebra and logic have important consequences when applied to programs. Folding is an example. It concerns programs that are expressed as collections of equations forming recursive function definitions (programs written in a functional language are often essentially in that form). The idea is to derive new equations, and in doing so one of the characteristic steps is to replace an instance of a right-hand side of an existing equation by the corresponding instance of the left-hand side (folding) or vice versa (unfolding). The resulting new equations form a new program equivalent to the original one. Programs derived in this way can often display significantly different efficiency conditions from the original programs.
2. A simple method of hashing a key, in which the key is subdivided into several parts that are added together to give an address. The folding ratio is the ratio of the sizes of the domain of this hashing function to the size of its range.
1. An important method in program transformation, introduced by Burstall and Darlington. Many simple mathematical techniques for processing the equations and formulas of algebra and logic have important consequences when applied to programs. Folding is an example. It concerns programs that are expressed as collections of equations forming recursive function definitions (programs written in a functional language are often essentially in that form). The idea is to derive new equations, and in doing so one of the characteristic steps is to replace an instance of a right-hand side of an existing equation by the corresponding instance of the left-hand side (folding) or vice versa (unfolding). The resulting new equations form a new program equivalent to the original one. Programs derived in this way can often display significantly different efficiency conditions from the original programs.
2. A simple method of hashing a key, in which the key is subdivided into several parts that are added together to give an address. The folding ratio is the ratio of the sizes of the domain of this hashing function to the size of its range.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
folding