Today I was looking into the MRR 3 node issue, and it looks like, at least from all the examples I have, that the first two references are actually the same line, and the third is different. So I'm currently ensuring that this is the case, and then performing resolution on the first and third (the second and third work just as well); this completes the proof. Is it necessary to consider the second? If not, is there a reason SPASS uses three references?
I also cleaned up a bit of the code; for example the parser no longer parses "eq", "ge", etc. functions explicitly; it just parses a function with an arbitrary name and number of arguments.
Also, when Skeptik is done the proof is often shorter than the given proof, at least in terms of lines: for FSTP2.spass for example, it has 18 lines in the file (each one is a Res, MRR or Inp, and thus useful?), but Skeptik only has 12:
1: { ⊢ (eq (f U) 0), (eq (f U) 1)} : Axiom()[]
2: {(eq (f X) 0) ⊢ (eq (f (s X)) 1)} : Axiom()[]
3: {(eq (f W) 0) ⊢ (eq (f (max NEW1 (s W))) 1)} : Axiom()[]
4: { ⊢ (le W (max W X))} : Axiom()[]
5: {(eq (f V) 1), (eq (f U) 1), (le (s U) V) ⊢ } : Axiom()[]
6: {(eq (f (max (s U) X)) 1), (eq (f U) 1) ⊢ } : UnifyingResolution(4, 5)[]
7: {(eq (f W) 0), (eq (f U) 1) ⊢ } : UnifyingResolution(3, 6)[]
8: {(eq (f X) 0) ⊢ } : UnifyingResolutionMRR(2, 7)[]
9: { ⊢ (eq (f X) 1)} : UnifyingResolutionMRR(1, 8)[]
10: { ⊢ (le W W)} : Axiom()[]
11: {(eq (f (s U)) 1), (eq (f U) 1) ⊢ } : UnifyingResolution(10, 5)[]
12: { ⊢ } : UnifyingResolutionMRR(9, 11)[]
Do you know if Skeptik is already compressing/reducing the proof? If so, is there a way to disable this (just so that I can see that everything is working properly?
Saturday, 31 May 2014
Friday, 30 May 2014
Parser - Final Edits?
I was working investigating the MRR inference rule, and fixing bugs that resulted from it. It does look like MRR is the same as resolution in the general case, but my code kept outputting some extra formulas compared to what was expected. I created a new (temporary) class (just so I don't break 'regular' resolution) to change this for the MRR-specific resolution calls, but I fear this means there's a bug in the resolution -- though everything matches the expected output. This method works for now though.
There's one last problem beyond this: the last MRR reference in the proof has three references -- the code only support resolution on two nodes. I'm not entirely sure how to resolve the three nodes at once, and I'll think about this next.
There's one last problem beyond this: the last MRR reference in the proof has three references -- the code only support resolution on two nodes. I'm not entirely sure how to resolve the three nodes at once, and I'll think about this next.
Location:
Victoria, BC, Canada
Thursday, 29 May 2014
Unifying Resolutions - Final Part
Today, I think I've finally fixed the UnifyingResolutions class. It looks like the bug that was mentioned in the last post was a result of my re-naming of shared variables in premises being applied in the wrong place. It turns out that I was 'waiting too long' to clear up the difference, and once I put it in the right spot, it's looks to be working fine.
By that, I mean that for every line of my example SPASS proof, the line representing the Resolvent computed by Skeptik matches the line provided by SPASS (except for some difference in variable names -- but this is fine, and some ordering of formulas). So the parsing is done, except for one thing.
The proof, when finally displayed, is not much more than a single line:
1: { ⊢ } : Axiom()[]
I think this is because the last line of the example proof is generated by an MRR inference rule, which the parser treats as an axiom. And when printing the proof, Skeptik reduces the output to show only what is necessary. But in this case what we want to show is an axiom (and the last one we've seen), so it prints that and stops. The rest of the proof using UnifyingResolutions is working well -- you can print out the proof for an intermediate result (generated by resolution, and thus not treated as an axiom) and it looks good.
So I think the next step is to stop treating other inference rules as Axioms, and code at least a quick class for at least MRR, to see the entire proof. (Even if this class does treat the input as an axiom, but something that references the premises used by MRR, so that the proof is at least displayed properly).
By that, I mean that for every line of my example SPASS proof, the line representing the Resolvent computed by Skeptik matches the line provided by SPASS (except for some difference in variable names -- but this is fine, and some ordering of formulas). So the parsing is done, except for one thing.
The proof, when finally displayed, is not much more than a single line:
1: { ⊢ } : Axiom()[]
I think this is because the last line of the example proof is generated by an MRR inference rule, which the parser treats as an axiom. And when printing the proof, Skeptik reduces the output to show only what is necessary. But in this case what we want to show is an axiom (and the last one we've seen), so it prints that and stops. The rest of the proof using UnifyingResolutions is working well -- you can print out the proof for an intermediate result (generated by resolution, and thus not treated as an axiom) and it looks good.
So I think the next step is to stop treating other inference rules as Axioms, and code at least a quick class for at least MRR, to see the entire proof. (Even if this class does treat the input as an axiom, but something that references the premises used by MRR, so that the proof is at least displayed properly).
Location:
Victoria, BC, Canada
Unifying Resolutions - Continued
(This post was supposed to go up yesterday, but it did not -- though it was posted on the Google group)
Today, I've been debugging a different problem: the resolvents we get are very close to those output by SPASS, but appear to be off in terms of where variables appear, e.g.:
Parsed: 10: ⊢ (le U (max V U))
First premise: ⊢ (le U U)
First formula: (le U U)
Second premise: (le (max U V) W) ⊢ (le V W)
Second formula: (le (max U V) W)
Computed: 10: ⊢ (le V (max U V))
but unfortunately, not always, e.g.:
First premise: ⊢ (le U U)
First formula: (le U U)
Second premise: (le (max U V) W) ⊢ (le U W)
Second formula: (le (max U V) W)
Parsed: 13: ⊢ (le U (max U V))
Computed: 13: ⊢ (le U (max U V))
But should this even be a concern, considering all the variables are universally quantified, and we can just rename them when doing resolution? And in some cases, this does not seem to be an issue: sometimes, UnifyingResolution can deal with the different names, e.g.
Attempting to parse line 18
First premise: ⊢ (le U (max NEW1 (max U V)))
First formula: (le U (max V (max U W)))
Second premise: (le (max U V) W) ⊢ (le U W)
Second formula: (le (max U V) W)
Parsed: 18: ⊢ (le U (max V (max (max U W) X)))
Computed: 18: ⊢ (le U (max NEW1 (max (max U V) NEW0)))
but of course we get new variables in the end result.
And in other cases it does not work:
Attempting to parse line 44
First premise: ⊢ (le V (max U V))
First formula: (le U (max V U))
Second premise: (eq (f V) 3), (eq (f U) 3), (le (s U) V) ⊢
Second formula: (le (s U) V)
Exception in thread "main" java.lang.Exception: Resolution: the conclusions of the given premises are not resolvable.
So if the variable names are not an issue, there might be an issue in finding unifying pairs (so the Martelli Montanari algorithm again?). I'm looking into this now.
And I should note that the filtering issue has been fixed.
Location:
Victoria, BC, Canada
Tuesday, 27 May 2014
Unifying Resolutions - Continued
Today I spent a great deal of time debugging a few things in UnifyingResolutions. For one, often, when resolvents are computed by Skeptik, I have an extra formula in my antecedent, and of course this should not be happening. Furthermore, I am concerned about the symmetry of UnifyingResolutions, as when I make unit tests with the same proof nodes, say A,B passed as (A,B), it works fine, but (B,A) does not ("Resolution: the conclusions of the given premises are not resolvable."). This is apparently fine in practice though, so I'm dropping this concern for now.
The concern I was having was regarding extra antecedents in my code (and possibly extra succedents--though I haven't yet observed this, likely by luck/not looking past extra antecdents). Bruno has identified this as an error in filtering some formulas in the resolvent, and so there's hope for a (relatively) quick fix.
The concern I was having was regarding extra antecedents in my code (and possibly extra succedents--though I haven't yet observed this, likely by luck/not looking past extra antecdents). Bruno has identified this as an error in filtering some formulas in the resolvent, and so there's hope for a (relatively) quick fix.
Location:
Victoria, BC, Canada
Saturday, 24 May 2014
Unifying Resolutions
Today, I was mainly engaged in programming the changes outlined by Bruno for the fix to the UnifyingResolutions class. I coded a first draft, but it's still incomplete, and so it's certainly not yet tested. Should finish it (with some unit tests too) tomorrow.
Location:
Victoria, BC, Canada
Friday, 23 May 2014
Pasers, Day IV
Today was spent by continued debugging of the parser. Yesterday, I ended on the UnifyingResolutions class throwing an exception informing me that I couldn't resolve those nodes; today, that was corrected, but only to introduce new errors; in this case an infinite loop that occurs in the Martelli-Montanari algorithm for computing unifiers. So far, I can't quite find the fix, and so while I spent a lot of time on it, I also spent some time reading relevant literature as well. In particular, I found the original Martelli-Montanari paper [1] and read some of that (which was not helpful so far), a document on how LowerUnits might be generalized, and re-read background literature like [2,3].
[1] Martelli, Alberto, and Ugo Montanari. "An efficient unification algorithm." ACM Transactions on Programming Languages and Systems (TOPLAS) 4.2 (1982): 258-282.
[2] Fontaine, Pascal, Stephan Merz, and Bruno Woltzenlogel Paleo. "Compression of propositional resolution proofs via partial regularization." Automated Deduction–CADE-23. Springer Berlin Heidelberg, 2011. 237-251.
[3] Leitsch, Alexander. "Resolution theorem proving: A logical point of view." Logic Colloquium. Vol. 1. 2001.
[1] Martelli, Alberto, and Ugo Montanari. "An efficient unification algorithm." ACM Transactions on Programming Languages and Systems (TOPLAS) 4.2 (1982): 258-282.
[2] Fontaine, Pascal, Stephan Merz, and Bruno Woltzenlogel Paleo. "Compression of propositional resolution proofs via partial regularization." Automated Deduction–CADE-23. Springer Berlin Heidelberg, 2011. 237-251.
[3] Leitsch, Alexander. "Resolution theorem proving: A logical point of view." Logic Colloquium. Vol. 1. 2001.
Labels:
gsoc2014,
lit-reference,
parser,
Skeptik,
SPASS
Location:
Victoria, BC, Canada
Thursday, 22 May 2014
Day 2: Parsers, Part III
Today was continued development of the SPASS parser that I've been working on for the last two days. Progress is being made: the issues I had yesterday for example, (with respect to n-ary functions and their representation) have been resolved through AppRec which uses currying to deal with such functions. As a result, I think I was able to correctly store such expressions in memory, and this allowed me to deal with working with those expressions in memory. In particular lines of the proofs that use inference rules can, for example, be parsed, or computed from the axioms already parsed into Skeptik (or both, to say, check for errors). So today was refactoring the code so that it does the latter and uses UnifyingResolutions to compute the resolution based on the referenced lines in the proof.
This took admittedly longer than I had expected, and it's still not quite working. It compiles, but outputs an exception "Resolution: the conclusions of the given premises are not resolvable.", which is obviously not good. I've been toying around and investigating, and now I'm pretty sure it's my code (not the UnifyingResolutions class, which has not been tested). The function calls for a Set[Var] of unifying variables, and right now I think I'm just passing in an empty place holder (but that variable is also implicitly defined, so I'm not sure if I need to be passing in anything at all--though that results in the compiler errors). Will replace the placeholder with something useful tomorrow, and see if that works.
This took admittedly longer than I had expected, and it's still not quite working. It compiles, but outputs an exception "Resolution: the conclusions of the given premises are not resolvable.", which is obviously not good. I've been toying around and investigating, and now I'm pretty sure it's my code (not the UnifyingResolutions class, which has not been tested). The function calls for a Set[Var] of unifying variables, and right now I think I'm just passing in an empty place holder (but that variable is also implicitly defined, so I'm not sure if I need to be passing in anything at all--though that results in the compiler errors). Will replace the placeholder with something useful tomorrow, and see if that works.
Location:
Victoria, BC, Canada
Wednesday, 21 May 2014
Day 1: Parsers, Part II
Today was adding the important code to the SPASS parser that was built yesterday: the parser no longer discards input, but rather stores it and attempts to build a proof from it. That's not done yet--resolutions are not operational as I think I don't have the handling of functions down quite right yet. In order to explain, perhaps an example is in order. An example input line starts with following:
1[0:Inp] || eq(f(U),0) ...
For now, the stuff to the left of || can be ignored: it's a description of what the line is doing, and in this case it's saying we've received this formulas input (as an axiom, say), and the first predicate of the formula is that f(U) = 0, where U is an implicitly universally quantified variable. Okay; that's straightforward, but Skeptik did not have a (direct) way to deal with either of the f(U), or the eq() expressions, or at least not from my previous experience with the E (expression) class.
For the function f, I think this was already something that could be dealt with: using an App expression (which maybe stands for function application?), I think I've defined a suitable expression by first creating an Arrow object, which, to be perfectly honest, I only did because the App class requires one (though the names do seem to match what I'm looking to do). But then I also created new versions App (App2, App3 respectively--I'm still coming up with a better name) to take two or three arguments, as opposed to one, and did the same for Arrow (ArrowPair, ArrowTriple) to describe functions that take as input multiple expressions.
Now the question that really matters is was this the right choice? I know that I need to keep the functions or predicates as instances of expression, so that I can eventually pass them off to one of the resolution classes (which will likely need to be modified to handle whatever new form), but beyond the similar names (and I think code functionality?), I'm not sure if this made sense. Or did I just miss something, and is there already support for these types of expressions somewhere in the code?
1[0:Inp] || eq(f(U),0) ...
For now, the stuff to the left of || can be ignored: it's a description of what the line is doing, and in this case it's saying we've received this formulas input (as an axiom, say), and the first predicate of the formula is that f(U) = 0, where U is an implicitly universally quantified variable. Okay; that's straightforward, but Skeptik did not have a (direct) way to deal with either of the f(U), or the eq() expressions, or at least not from my previous experience with the E (expression) class.
For the function f, I think this was already something that could be dealt with: using an App expression (which maybe stands for function application?), I think I've defined a suitable expression by first creating an Arrow object, which, to be perfectly honest, I only did because the App class requires one (though the names do seem to match what I'm looking to do). But then I also created new versions App (App2, App3 respectively--I'm still coming up with a better name) to take two or three arguments, as opposed to one, and did the same for Arrow (ArrowPair, ArrowTriple) to describe functions that take as input multiple expressions.
Now the question that really matters is was this the right choice? I know that I need to keep the functions or predicates as instances of expression, so that I can eventually pass them off to one of the resolution classes (which will likely need to be modified to handle whatever new form), but beyond the similar names (and I think code functionality?), I'm not sure if this made sense. Or did I just miss something, and is there already support for these types of expressions somewhere in the code?
Location:
Victoria, BC, Canada
Tuesday, 20 May 2014
Day 0: Parsers
For the first official day of coding, I coded the first two versions of two parsers. The first was for the TPTP format, and the second, which relies (partially) on the TPTP format, is one for the actual proof output for the SPASS theorem prover. The parsers currently only read input and then discard it, because I haven't yet decided how to modify the proof classes of Skeptik to handle FOL proofs--that's the goal for tomorrow, and after that, completing the parsers should be easy.
A note on the TPTP parser: there are several existing parsers written in Scala for it, e.g. one in the MELIA repository, and it seems like it would parse a greater set of text then the one I wrote today, but it's so deeply tied into the MELIA code that it's useless until I modify the Skeptik proof classes in order to possibly replace the MELIA classes with Skeptik ones. So for now, I'm going to use my small one, which doesn't require me to possibly break some one else's code, and allows me greater control. If all goes well, I'll swap mine out later in the week.
A note on the TPTP parser: there are several existing parsers written in Scala for it, e.g. one in the MELIA repository, and it seems like it would parse a greater set of text then the one I wrote today, but it's so deeply tied into the MELIA code that it's useless until I modify the Skeptik proof classes in order to possibly replace the MELIA classes with Skeptik ones. So for now, I'm going to use my small one, which doesn't require me to possibly break some one else's code, and allows me greater control. If all goes well, I'll swap mine out later in the week.
Location:
Victoria, BC, Canada
Subscribe to:
Posts (Atom)