Connect++ 0.3.0
A fast, readable connection prover for first-order logic.
Loading...
Searching...
No Matches
StackProver.hpp
1/*
2
3Copyright © 2023-24 Sean Holden. All rights reserved.
4
5*/
6/*
7
8This file is part of Connect++.
9
10Connect++ is free software: you can redistribute it and/or modify it
11under the terms of the GNU General Public License as published by the
12Free Software Foundation, either version 3 of the License, or (at your
13option) any later version.
14
15Connect++ is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
18more details.
19
20You should have received a copy of the GNU General Public License along
21with Connect++. If not, see <https://www.gnu.org/licenses/>.
22
23*/
24
25#ifndef STACKPROVER_HPP
26#define STACKPROVER_HPP
27
28#include<iostream>
29#include<string>
30#include<filesystem>
31#include <chrono>
32
33#include "FunctionIndex.hpp"
34#include "PredicateIndex.hpp"
35#include "StackItem.hpp"
36#include "Matrix.hpp"
37#include "TPTPParser.hpp"
38#include "ProverOutcome.hpp"
39#include "SubstitutionStack.hpp"
40#include "ProofPrinter.hpp"
41#include "Interval.hpp"
42#include "cursor.hpp"
43#include "PathUtilities.hpp"
44#include "vic_strings.hpp"
45
46using std::string;
47using std::get;
48
49namespace fs = std::filesystem;
50namespace chrono = std::chrono;
51
52using namespace tptp_parser;
53
75private:
80 size_t num_preds;
116 vector<StartClauseStatus> results;
172 string status;
177 vector<StackItem> stack;
183 vector<StackItem> right_branch_stack;
196 fs::path problem_path;
228 uint32_t proof_count;
236 chrono::steady_clock::time_point end_time;
241 //----------------------------------------------------------------------
242 //----------------------------------------------------------------------
243 //----------------------------------------------------------------------
244 // Here is where the heavy lifting happens.
245 //----------------------------------------------------------------------
246 //----------------------------------------------------------------------
247 //----------------------------------------------------------------------
251 ProverResult go();
256 void populate_stack_item();
261 void extend_with_action();
265 bool depth_limited();
269 bool axiom() const;
283 void backtrack_once();
287 void reduction_backtrack();
291 void lemmata_backtrack();
310 depth_limit_reached = false;
311 si = nullptr;
312 backtrack = false;
313 path.clear();
314 stack.clear();
315 lemmata.clear();
316 right_branch_stack.clear();
318 }
350public:
354 StackProver();
358 StackProver(const StackProver&) = delete;
359 StackProver(const StackProver&&) = delete;
360 StackProver& operator=(const StackProver&) = delete;
361 StackProver& operator=(const StackProver&&) = delete;
365 std::tuple<VariableIndex*, FunctionIndex*, PredicateIndex*, TermIndex*> get_indexes() {
366 auto result = std::make_tuple(&var_index, &fun_index, &pred_index, &term_index);
367 return result;
368 }
372 string get_status() const { return status; }
384 void set_timeout(chrono::steady_clock::time_point time) {
385 use_timeout = true;
386 end_time = time;
387 }
393 void set_problem_path(fs::path& p) { problem_path = p; }
399 void set_num_preds(size_t);
410 void read_from_tptp_file(const string&, bool&, size_t&);
426 void deterministic_reorder(uint32_t n) {
428 }
434 }
438 void show_matrix() {
439 cout << "Matrix:" << endl;
440 cout << matrix.to_string() << endl;
441 }
446 return matrix;
447 };
452 bool problem_is_cnf_only() const {
453 return cnf_only;
454 }
460 return conjecture_true;
461 }
467 return conjecture_false;
468 }
475 return conjecture_missing;
476 }
483 }
489 return fof_has_axioms;
490 }
497 }
502 cout << endl << "% Problem matrix:" << endl;
504 cout << endl << "% Proof stack:" << endl;
506 }
513 ProverOutcome prove();
518 vector<pair<string, vector<size_t>>> get_internal_proof() const;
519 /*
520 * The remaining material is really just for debugging.
521 */
522 void show_matrix() const { cout << matrix << endl; }
523 void show_path() const { cout << path << endl; }
524 void show_stack();
525 void show_right_stack();
526 void show_term_index() { cout << term_index << endl; }
527 void show_statistics() const;
528 friend ostream& operator<<(ostream&, const StackProver&);
529};
530
531#endif
Representation of clauses.
Definition Clause.hpp:52
Mechanism for looking after functions.
Simple class to help you count intervals.
Definition Interval.hpp:35
Representation of the lemma list.
Definition Lemmata.hpp:49
void clear()
Self-explanatory.
Definition Lemmata.hpp:70
Representation of the Matrix within a proof.
Definition Matrix.hpp:72
string to_string() const
Make a string representation.
Definition Matrix.cpp:234
void deterministic_reorder(size_t)
Deterministic reorder of the clauses.
Definition Matrix.cpp:105
void show_tptp() const
Output in TPTP compatible format.
Definition Matrix.cpp:287
void random_reorder()
Randomly reorder the matrix.
Definition Matrix.cpp:136
Basic representation of predicates: here just names, ids and arities.
Definition Predicate.hpp:51
Management of Predicate objects.
Class for rendering a proof in various formats.
void show_tptp()
Show the proof in a TPTP-friendly format.
Simple representation of the path within a proof tree.
void clear()
evert to the empty state without changing num_preds.
Prover using a pair of stacks to conduct the proof search.
void set_num_preds(size_t)
Set the number of predicates.
bool depth_limit_reached
Self-explanatary.
void process_axiom_forward()
Start a right branch to continue from an axiom.
string status
Problem status, if found in input file.
void read_from_tptp_file(const string &, bool &, size_t &)
Obviously, reads a problem from a TPTP file.
vector< StartClauseStatus > results
This is populated by the StackProver::set_up_start_clauses method.
bool negated_conjecture_removed
Keep track of whether the parser simplified the conjecture away.
uint32_t lemmata_tried
We'll be keeping some simple statistics about the search process.
void lemmata_backtrack()
One of several different kinds of backtracking.
bool problem_has_true_conjecture() const
Find out whether the problem's conjecture is $true.
void reset_for_start()
Reset everything so that you can start from a specified start clause.
void random_reorder()
Randomly reorder the matrix.
uint32_t current_depth_limit
Self-explanatary.
void show_tptp_proof()
Show a Prolog-formatted proof.
bool problem_is_cnf_only() const
Find out whether the problem is CNF only.
InferenceItem action
Stores the next action from the current StackItem.
void set_up_start_clauses()
The start clauses to use depend on the settings, and the settings can change.
size_t num_preds
How many prdicates does the problem of interest have?
bool fof_has_axioms
Keep track of whether the parser found that it's an FOF problem with axioms before simplification.
StackProver(const StackProver &)=delete
Don't try to copy this.
void set_problem_path(fs::path &p)
Set the path for the problem being solved. U.
vector< StackItem > stack
Main stack: this is constructed by the search process and, if completed, represents a proof.
ProverResult go()
This runs the proof search from a given Start Move.
Matrix matrix
A copy of the matrix you're working with.
void deterministic_reorder(uint32_t n)
Deterministically reorder the matrix n times.
PredicateIndex pred_index
This class needs one of each kind of index to keep track of Variables, Terms etc.
vector< StackItem > right_branch_stack
We build the proof by trying the left branches of extensions first: this stack keeps track of the rig...
ProofPrinter proof_printer
You need one of these to print LaTeX output or any kind of proof certificate.
void extend_with_action()
Take a single inference (action) and update the stacks accordingly.
bool cnf_only
Keep track of whether there were any FOF formulas in the problem file.
SimplePath path
At any point in the search process this is a copy of the path for the current node in the proof being...
FunctionIndex fun_index
This class needs one of each kind of index to keep track of Variables, Terms etc.
void populate_stack_item()
Fill the vector of possible actions with everything available.
Lemmata lemmata
At any point in the search process this is a copy of the list of lemmata for the current node in the ...
void show_matrix()
Show a nicely formatted matrix.
bool problem_has_missing_conjecture() const
Find out whether the problem's conjecture is missing, in the sense that it didn't appear in the inp...
uint32_t extensions_tried
We'll be keeping some simple statistics about the search process.
uint32_t current_depth
Self-explanatary.
bool problem_has_negated_conjecture_removed() const
Find out whether the problem's negated conjecture was simplified out.
void add_equality_axioms(Predicate *)
After reading a problem in which = and/or != appears, add the axioms for equality.
void set_timeout(chrono::steady_clock::time_point time)
Set a timeout.
bool simplified_fof_has_axioms
Keep track of whether the parser found that it's an FOF problem with axioms after simplification.
bool conjecture_missing
Keep track of whether the parser found a conjecture in the problem file.
TermIndex term_index
This class needs one of each kind of index to keep track of Variables, Terms etc.
uint32_t proof_count
If we're searching for multiple proofs, keep count of which one this is.
bool conjecture_false
Keep track of whether the parser found the conjecture to be false.
VariableIndex var_index
This class needs one of each kind of index to keep track of Variables, Terms etc.
bool simplified_problem_has_fof_axioms() const
Find out from the parser whether the problem had axioms after simplification.
string get_status() const
Straightforward get method.
bool problem_has_fof_axioms() const
Find out from the parser whether the problem had axioms before simplification.
void backtrack_once()
Basic, single step backtrack on the stack.
bool depth_limited()
Test for the depth limit.
bool conjecture_true
Keep track of whether the parser found the conjecture to be true.
std::tuple< VariableIndex *, FunctionIndex *, PredicateIndex *, TermIndex * > get_indexes()
Straightforward get method.
void left_extension_backtrack()
One of several different kinds of backtracking.
uint32_t right_branches_started
We'll be keeping some simple statistics about the search process.
bool backtrack
Are we moving up or down the stack?
chrono::steady_clock::time_point end_time
When do we stop because of a timeout?
vector< pair< string, vector< size_t > > > get_internal_proof() const
Get an internal representation of the proof stack.
StackItem * si
Pointer to the current StackItem.
Clause new_C
At any point in the search process this is a copy of the clause for the current node in the proof bei...
void right_extension_backtrack()
One of several different kinds of backtracking.
fs::path problem_path
Path for the problem of interest.
StackProver()
You only need a basic constructor.
bool use_timeout
Are we using a timeout?
void reduction_backtrack()
One of several different kinds of backtracking.
Matrix & get_matrix()
Get a reference to the matrix.
uint32_t reductions_tried
We'll be keeping some simple statistics about the search process.
SubstitutionStack sub_stack
There is a separate stack to make application and removal of substitutions straightforward.
verbose_print::VPrint show
Set up printing according to verbosity.
bool problem_has_false_conjecture() const
Find out whether the problem's conjecture is $false.
Unifier u
We need a single Unifier to use throught the process.
bool axiom() const
Test to see if you're at an axiom.
ProverOutcome prove()
Here is where the magic happens.
Interval output_interval
How often do you output updates about progress?
As you build a proof you make substitutions that apply to the entire proof: if you backtrack during t...
void clear()
Reset everything.
Look after terms, (ideally) using hash consing to avoid storing copies of terms.
Definition TermIndex.hpp:75
Wrap up various applications of unificiation into a single class: all the unification you need to do ...
Definition Unifier.hpp:83
Storage of named variables, and management of new, anonymous variables.
The tptp_parser namespace contains a lot of stuff that's essentially just global.
Full representation of inferences, beyond just the name.
Stack items: each contains its own stack of possible next inferences.
Definition StackItem.hpp:51