Lassie: HOL4 tactics by example

Heiko Becker, Nathaniel Bos, Ivan Gavran, Eva Darulova, Rupak Majumdar

Lassie: HOL4 Tactics by Example

Abstract

Interactive Theorem Provers (ITPs) like HOL4 are powerful tools for formal verification but suffer from a steep learning curve due to complex, low-level tactic languages. This paper introduces Lassie, a framework that allows users to define custom proof tactics using natural language examples. By integrating an extensible semantic parser (SEMPRE) into HOL4, Lassie generalizes user-provided examples into reusable, parametric commands. This approach lowers the barrier to entry for domain experts and improves proof readability without compromising logical rigor.

Introduction

Interactive Theorem Provers (ITPs) such as HOL4, Coq, and Isabelle represent the gold standard for software and mathematical verification. However, their adoption is hindered by the difficulty of providing a sequence of tactics—low-level commands required to manipulate the proof state. Users face a significant "vocabulary overload," needing to memorize hundreds of cryptically named tactics like rpt strip_tac or qpat_x_assum. Furthermore, creating custom, higher-level tactics typically requires deep expertise in the prover’s implementation language (e.g., Standard ML for HOL4).

A typical HOL4 proof state showing the theorem REAL_INV_LE_AMONO and the use of the 'rpt strip_tac' tactic.

Lassie addresses these challenges by enabling users to "naturalize" the proof process. It allows for the creation of a personalized language that aligns with the user's mental model of the proof, effectively bridging the gap between high-level reasoning and low-level implementation.

Methods

The core of Lassie is the integration of the SEMPRE extensible semantic parser into the HOL4 environment. The framework operates through several key mechanisms:

  • Definition by Example: Users define new tactics by providing a natural language "utterance" and its corresponding HOL4 tactic. For instance, def 'simplify with [L]' 'fs [L]'.
  • Definitional Generalization: The semantic parser identifies parameters within these examples. In the previous case, it recognizes [L] as a list of theorems, creating a grammar rule that allows simplify with to work with any theorem list.
  • Ambiguity Resolution via ITP: Lassie leverages the ITP's strict logical kernel to resolve natural language ambiguities. It uses HOL4’s type information and the current proof state to filter out invalid parses, ensuring only mathematically sound tactics are executed.
  • Pedagogical Support: The nlexplain mode "decorates" the proof state, showing users the underlying HOL4 tactics generated by their Lassie commands. This serves as a learning bridge, helping users transition to native system commands over time.

Evaluation and Results

Lassie was evaluated through various case studies, including a re-implementation of Euclid’s "infinite primes" proof, algebraic identities for real and natural numbers, and integration with the large-scale FloVer library (~10,000 lines of code).

Key findings include:

  • Enhanced Readability: In the Euclid’s Theorem study, 22 custom Lassie tactics replaced cryptic HOL4 code, resulting in a script that closely resembles a textbook proof.
  • High Reusability: Tactics were frequently reused across different subgoals; for example, a generic "solve" tactic was used 16 times in the Euclid proof.
  • Seamless Integration: The FloVer study demonstrated that Lassie can be applied to existing, complex libraries without modifying their underlying code.
  • Zero-Cost Abstraction: Lassie tactics map directly to standard, kernel-checked HOL4 tactics. Proofs can be exported as standard HOL4 scripts, maintaining full rigor and independence from the Lassie framework.

Discussion and Future Work

While Lassie significantly improves the user experience, some limitations remain. Debugging failed tactics can still be difficult for novices, as it currently requires inspecting the generated HOL4 code. Additionally, the SEMPRE parser's performance can degrade with very large text strings, though the authors have implemented chunking strategies to mitigate this. Future work will focus on expanding the core grammar to support more complex structures like nested sub-proofs and improving the discovery of user-defined tactics to manage cognitive load as the custom language grows.

Summary updated

BibTeX
@inproceedings{becker2021lassie,
  author = {Heiko Becker and Nathaniel Bos and Ivan Gavran and Eva Darulova and Rupak Majumdar},
  title = {{Lassie: HOL4 tactics by example}},
  booktitle = {CPP},
  year = {2021},
  doi = {10.1145/3437992.3439925},
}
Figure