  A key challenge facing natural language interfaces is enabling users to
understand the capabilities of the underlying system. We propose a novel
approach for generating explanations of a natural language interface based on
semantic parsing. We focus on counterfactual explanations, which are post-hoc
explanations that describe to the user how they could have minimally modified
their utterance to achieve their desired goal. In particular, the user provides
an utterance along with a demonstration of their desired goal; then, our
algorithm synthesizes a paraphrase of their utterance that is guaranteed to
achieve their goal. In two user studies, we demonstrate that our approach
substantially improves user performance, and that it generates explanations
that more closely match the user's intent compared to two ablations.
