Compiling higher-order specifications to SMT solvers : how to deal with rejection constructively

Daggitt, Matthew L. and Atkey, Robert and Kokke, Wen and Komendantskaya, Ekaterina and Arnaboldi, Luca; Krebbers, Robbert and Traytel, Dmitriy and Pientka, Brigitte and Zdancewic, Steve, eds. (2023) Compiling higher-order specifications to SMT solvers : how to deal with rejection constructively. In: CPP 2023 : Proceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs. ACM, New York, NY., pp. 102-120. ISBN 9798400700262 (https://doi.org/10.1145/3573105.3575674)

[thumbnail of Daggit-etal-SIGPLAN-2023-Compiling-higher-order-specifications-to-SMT-solvers]
Preview
 Text. Filename: Daggit_etal_SIGPLAN_2023_Compiling_higher_order_specifications_to_SMT_solvers.pdf
Accepted Author Manuscript
License: Creative Commons Attribution 4.0 logo
Download (344kB)| Preview

Abstract

Modern verification tools frequently rely on compiling high-level specifications to SMT queries. However, the high-level specification language is usually more expressive than the available solvers and therefore some syntactically valid specifications must be rejected by the tool. In such cases, the challenge is to provide a comprehensible error message to the user that relates the original syntactic form of the specification to the semantic reason it has been rejected. In this paper we demonstrate how this analysis may be performed by combining a standard unification-based type-checker with type classes and automatic generalisation. Concretely, type-checking is used as a constructive procedure for under-approximating whether a given specification lies in the subset of problems supported by the solver. Any resulting proof of rejection can be transformed into a detailed explanation to the user. The approach is compositional and does not require the user to add extra typing annotations to their program. We subsequently describe how the type system may be leveraged to provide a sound and complete compilation procedure from suitably typed expressions to SMT queries, which we have verified in Agda.

ORCID iDs

Daggitt, Matthew L., Atkey, Robert ORCID logoORCID: https://orcid.org/0000-0002-4414-5047, Kokke, Wen, Komendantskaya, Ekaterina and Arnaboldi, Luca; Krebbers, Robbert, Traytel, Dmitriy, Pientka, Brigitte and Zdancewic, Steve
CORE (COnnecting REpositories)