How moratori/clover works
Main Components
• Core Proof Engine: Representing the heart of the system that performs logical proofs, including implementation of the Knuth-Bendix completion algorithm and resolution-based inference. This includes modules such as:
– The resolution module (e.g., src/resolution.lisp)
– Completion/rewrite module (e.g., src/rewrite.lisp & src/simplify.lisp)
– Unification and term manipulation (e.g., src/unify.lisp, src/substitute.lisp, src/termorder.lisp)
• Parsing & Conversion: Modules that take input expressions and convert them into internal representations (e.g., src/parser.lisp, src/converter.lisp)
• Search Algorithms: Components for exploring derivations and proofs using algorithms like A*, DFS, IDDFS (e.g., src/search/astar.lisp, src/search/dfs.lisp, src/search/iddfs.lisp, src/search/extractor.lisp, src/search/common.lisp)
• User Interface & REPL: Components managing command-line interaction, batch execution, and user inputs (e.g., src/ui/main.lisp, src/ui/repl.lisp, src/ui/batch.lisp, src/ui/util.lisp)
• Utility & Support Modules: Including logging, error management, and additional utility functions (e.g., src/util.lisp, src/conditions.lisp, src/property.lisp, src/multicompletion.lisp, src/multiprocess.lisp)
Relationships and Interactions
• Input Handling: The user enters expressions via either the REPL or by passing a file in batch mode. The UI module (CLI front-end) then sends this data to the Parser.
• Transformation Pipeline: The Parser interprets the input into internal data structures, then passes these to the Converter for any required normalization.
• Proof Engine Interaction: Once parsed, the internal representations are sent to the proof engine, which branches out to the different strategies:
– Resolution algorithm for logical expressions.
– Term rewriting and completion algorithms for equality proofs.
The Search modules support these by handling the search space (via DFS, A*, etc.) during the proof process.
• Result Reporting: After processing, the engine returns a result (proof found, non-provable, irreducible form, etc.) that is handled by the UI and either displayed on the command line or saved if Graphviz code for a proof tree is generated.
• Testing & CI: A test suite (located in the tests directory) interacts with the modules through similar interfaces to ensure correctness. Continuous integration files (like .travis.yml and .github workflows) imply automated testing and release management flows.
Architectural Patterns & Design Principles
• Modular Decomposition: The system is organized into logically separated modules (parsing, conversion, search, rewriting, and UI), each encapsulated in its own file or directory.
• Pipeline Design: There is a linear flow from input -> parsing -> proof engine -> UI, with branching for different proof techniques.
• Functional Decomposition: Each component (for example, each search algorithm like A*, DFS, IDDFS) has a clear single responsibility.
• Extensibility: The design allows for potential extensions. For example, adding new search strategies or interactive commands in the REPL is straightforward given the modular design.
Relevant Technologies & Libraries
• Common Lisp: The primary language used across the system.
• Quicklisp/ASDF: Build and dependency management is likely handled through ASDF systems, as seen with files like clover.asd.
• Roswell: Build scripts related to Roswell (a Lisp installer/launcher) indicate the environment required to run the project.
• CI/CD & Testing Tools: GitHub workflows, Travis CI configurations, and shell scripts (like run-all-tests.sh) sustain quality and releases.
• Graphviz: There is an option to output the proof tree in Graphviz format, indicating integration with external visualization tools.