Transformation of Prolog Programs to Perform Update in Place: A Prototype Code SynthesizerTransformation of Prolog Programs to Perform Update in Place: A Prototype Code SynthesizerThis paper was my undergraduate honors thesis at Penn State.
Single assignment languages, such as Prolog or Standard ML, endure considerable inefficiency to support their declarative semantics. Lacking destructive assignment, programs written in these languages must frequently duplicate large portions of structures that conventional programs would simply modify in place. This paper presents techniques for automatically transforming Prolog programs to perform in-place updates using destructive assignment, and reports and evaluates experience prototyping the code synthesis portion of the transformation. Where applicable, such a transformation produces code that updates structures two to more than three times faster than naïve implementations and uses vastly less memory.
The full paper is available as a single PDF document or as a single PostScript document. A suggested BibTeX citation record is also available.