Advertisement
Published in:
2015 | OriginalPaper | Chapter
Synthesizing Heap Manipulations via Integer Linear Programming
Authors : Anshul Garg, Subhajit Roy
Published in: Static Analysis
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Writing heap manipulating programs is hard. Even though the high-level algorithms may be simple, it is often tedious to express them using low-level operations. We present a new tool — Synlip — that uses expression of intent in the form of concrete examples drawn using box-and-arrow diagrams to synthesize heap-manipulations automatically. Instead of modeling the concrete examples in a monolithic manner, Synlip attempts to extract a set of patterns of manipulation that can be applied repeatedly to construct such programs. It, then, attempts to infer these patterns as linear transformations, leveraging the power of ILP solvers for program synthesis.
In contrast to many current tools, Synlip does not need a bound on the number of statements and the number of temporaries to be used in the desired program. Also, it is almost insensitive to the size of the concrete examples and, thus, tends to be scalable. Synlip was found to be quite fast; it takes less than 10 seconds for most of our benchmark tasks spanning data-structures like singly and doubly linked-lists, AVL trees and binary search trees.