Automating the Design of Specification Interpreters

Abstract

In this paper, we demonstrate the use of model checking in an automated technique to verify the operationalization of a declarative specification language. We refer to an interpreter synthesizer as a software tool that transforms a declarative specification into an executable interpreter. Iterative approaches to synthesizer generation refine initial synthesizer designs by validating them over a test suite of specifications. Carefully chosen test suites and structural constraints enable inductive reasoning with support from a model checker to assert the correctness of generated interpreters. This iterative approach to synthesizer generation occurred naturally in our work on developing interpreters for declarative human-computer dialogue languages as part of the DARPA MASTERMIND project. We will discuss the issues underlying the translation, operationalization and verification of the hierarchical task language for MASTERMIND. We will also discuss the importance of this semi-automated, iterative approach for assessing non-functional design tradeoffs.