Executable specifications for Java programs

In this thesis, we present a unified environment for running declarative specifications in the context of an imperative object-oriented programming language. Specifications are Alloy-like, written in first-order relational logic with transitive closure, and the imperative language for this purpose is Java. By being able to mix imperative code with executable declarative specifications, the user can easily express constraint problems in-place, i.e. in terms of the existing data structures and objects on the heap. After a solution is found, our framework will automatically update the heap to reflect the solution, so the user can continue to manipulate the program heap in the usual imperative way, without ever having to manually translate the problem back and forth between the host programming environment and the solver language. We show that this approach is not only convenient, but, for certain problems, like puzzles or NP-complete graph algorithms, it can also outperform the manual implementation. We also present an optimization technique that allowed us to run our tool on heaps with almost 2000 objects.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2010

Author dc:creator

• Milicevic, Aleksandar, Ph. D. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Daniel N. Jackson.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/62442

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/62442