Using regular approximations for generalisation during partial evalution
John P. Gallagher, Julio C. Peralta · 1999
On-line partial evaluation algorithms include a generalisation step, which is needed to ensure termination. In partial evaluation of logic and functional programs, the usual generalisation operation applied to computation states is the most specific generalisation (msg) of expressions. This can cause loss of information, which is especially serious in programs whose computations first build some internal data structure, which is then used to control a subsequent phase of execution - a common pattern of computation. If the size of the intermediate data is unbounded at partial evaluation time then the msg will lose almost all information about its structure. Hence the second phase of computation cannot be effectively specialised.