Transition to AML: sorts

[h0nzZik]

When we remove the information about sorts from variables and symbols, we need a way to recover it for the strategies that need it. This is a proposal how to do it.

Which strategies use sorts?

Sorts, in the form of the function getReturnSort, are currently used by the following tactics:

1. purify
2. match (and match-pto)
3. instantiate-universals-with-ground-terms
4. smt

General idea

The idea is that getReturnSort will examine the context searching for typing information, using a simple heuristic. (The heuristic may also be exported as a separate strategy for proving typing-related claims.) The prelude will provide a notation

notation \typeof(X, S) = /* implementation defined */  [builtin(typeof)]

and the prover will understand axioms of the shape

axiom \typeof(Term, Sort)

and axioms for (not necessarily function) symbols

axiom \forall x1. \typeof(x1, Sort1) -> ... -> \typeof(xn, Sortn) -> \typeof(f(x1,...,xn), Sort)

and equality axioms

axiom \equals(Term1, Term2)

and the function getSorts() will search for such axioms and generate a list of sorts for given term. (Note that if two terms are equal, then they also share their sorts).

Looking at the strategies, it seems to me that they need the information that a term can be assigned some sort, but they do not need to know a term can not be assigned a given sort.

Modifying strategies

1. The strategy purify (transforms assumptions S(T, Vs) to S(V, Vs) /\ V = T could work without sorts, but it is important that after applying this strategy, getSorts(S(V,Vs)) returns the same list of sorts as did previously S(T, Vs). Currently, the strategy works on the LHS of the goal that is an implication and generates conjunction; it would need to be changed so that it worked on the local axiom set instead. Instead of generating conjunction, it would turn one axiom into two axioms, one of which would be V=T. The function getSorts would then be able to use the generated equality. Btw: moving the assumptions to the local context means that the variable V would no longer be a variable, but a constant symbol. Another note: when the context is no longer on LHS, the smt strategies need to be able to work with the local context.

2. The matching strategies need to match variables against other terms. Removing sorts here would mean that variables can match more things. However, they work on the goal (whose RHS is) of the shape \exists { Vs } Rest, where variables in Vs are currently typed. The typing information from Vs is then propagated to the #match function. After the transition, the strategies would work on goals of the shape \exists { Vs } \typeof(x1, S1) /\ \typeof(xn, Sn) /\ Rest, so we can extract the typing information from the \typeofs. Btw, a strategy that splits a conjunction in the proof context might be useful.

3. The strategy instantiate-universals-with-ground-terms would need to operate on the local context and understand assumptions of the shape \forall x. \typeof(x, S) -> Phi, so that it does not plug typed terms to non-matching assumptions. However, when searching for ground terms, we will lose free variables, because they will not have associated a type. To recover this, we need the goal to not contain free variables - they need to be universally quantified and the formula guarded by typeof. Also, the strategy might want to plug even terms without a type to assumptions that work with untyped foralls.

4. Smt. The problem is that smtlib does not support subsorting, and imho assumes that terms of different sorts cannot be equal. One idea is that we would have two strategies for SMT - one that would work with builtin sorts (like Int), and other that would work just with one universal sort. The consequence is that we would not be able to let SMT reason much about goals with mixed builtin and user-defined sorts, e.g. about arithmetic and other stuff at once.

Variants

Another variant of the same idea is having two symbols

symbol \inh         [builtin(inhabitant)]
symbol \member [multin(member)]

Maybe we need the prover to understand also subseq of inhabitant sets.

[xc93]

getSorts(S(V,Vs)) returns the same list of sorts as did previously S(T, Vs).

I don't think it is right, if V here denotes an unsorted free variable. There is no way to decide the sort of V, if we don't have the equation V = T.

[xc93]

Currently, the strategy works on the LHS of the goal that is an implication and generates conjunction; it would need to be changed so that it worked on the local axiom set instead.

Have we reached an agreement on the names local axiom set, or local proof context? I would like to clarify the terminologies to prevent possible confusion. Personally, I prefer theory, because, by definition, a theory defines a signature that contains the declarations of all symbols, and a set of axioms. I'm also OK with declaration, which is common in programming languages.

[xc93]

the prover will understand axioms of the shape
axiom \typeof(Term, Sort)

Just to clarify, the Term here is (most likely) a ground term, right? If Term has variables X1,...,Xn then the axiom should look like

axiom \forall X1 . \typeof(X1,S1) -> ... -> \forall Xn . \typeof(Xn,Sn) -> \typeof(Term,Sort)```

[xc93]

The function getSorts would then be able to use the generated equality.

Suppose there are two sorts Int and Bool. Consider the ground pattern add(2,3), which has sort Int. Can we claim that add(x,3) /\ x=2 also has sort Int? I don't think so, because it depends on the sort of x. If x has sort Bool, then x=2 is not possible and thus it equals \bot, and the entire pattern is \bot.

Since in AML, sorts are something that are defined, not built-in, we need to formalize what do we mean by saying a pattern P has a sort S. I think it means this:

Global_Theory U Local_Theory |- \subset(P, \domain(S))

Does this make sense? In other words, we define

notation \typeof(P, S) = \subseteq(P, \domain(S))  [builtin(typeof)]

[xc93]

moving the assumptions to the local context means that the variable V would no longer be a variable, but a constant symbol.

I would separate this step into two, namely first replace V with a fresh constant cV, by adding it to the local theory. Then, we use the deduction theorem to move cV from the premise of the implication to an axiom in the local theory.

[nishantjr]

I'm going to use the word local declarations to talk about the goal-level declarations,
global declarations for the top-level declarations, and theory to talk about their union.

Purify... Instead of generating conjunction, it would turn one axiom into two axioms, one of which would be V=T.

I don't see why the behaviour of purify needs to change. Why can't it keep generating conjunctions?

One idea is that we would have two strategies for SMT - one that would work with builtin sorts (like Int), and other that would work just with one universal sort

I think in the long run what we need is a nelson-oppen + DPLL equivalent for AML to separate the reasoning about sort/set membership and specific theories.

[h0nzZik]

getSorts(S(V,Vs)) returns the same list of sorts as did previously S(T, Vs).

I don't think it is right, if V here denotes an unsorted free variable. There is no way to decide the sort of V, if we don't have the equation V = T.

This is probably a misunderstanding. I wanted to say that we want it to return the same list, and that it is important. The rest of the paragraph is about how to do that (basically, we need to use the equation V = T).

the prover will understand axioms of the shape
axiom \typeof(Term, Sort)

Just to clarify, the Term here is (most likely) a ground term, right? If Term has variables X1,...,Xn then the axiom should look like

axiom \forall X1 . \typeof(X1,S1) -> ... -> \forall Xn . \typeof(Xn,Sn) -> \typeof(Term,Sort)```

Yes, a ground term.

The function getSorts would then be able to use the generated equality.

Suppose there are two sorts Int and Bool. Consider the ground pattern add(2,3), which has sort Int. Can we claim that add(x,3) /\ x=2 also has sort Int? I don't think so, because it depends on the sort of x. If x has sort Bool, then x=2 is not possible and thus it equals \bot, and the entire pattern is \bot.

The sort inference routine needs to be able to work with equalities. From x=2 it follows that x can be assigned any sort S such that S is a sort of 2 - so "x is a sort of Int" is a valid typing judgment.
Also, I would like if x=2 becomes an axiom in the theory, so that the sort inference routine easily finds it. But then we need to make x a symbol instead of a variable.

Since in AML, sorts are something that are defined, not built-in, we need to formalize what do we mean by saying a pattern P has a sort S. I think it means this:

Global_Theory U Local_Theory |- \subset(P, \domain(S))

Does this make sense?

Yes, that makes sense. If we do it this way, then the prover needs to understand both \subsetand\domain` (or \inh as in the AppKore proposal). My idea was that we would formalize it as

Global_Theory U Local_Theory |- \typeof(P, S)

where typeof is just an alias with an attribute builtin(typeof). This way, the prover would need to understand just one thing. But if we wanted the prover to understand subsorting, it would still need to understand \subset and \domain, so maybe your idea is superior. In that case, we would use builtin(subset) and builtin(domain) (or rather hook(subset) and hook(domain)?)

In other words, we define

notation \typeof(P, S) = \subseteq(P, \domain(S))  [builtin(typeof)]

[h0nzZik]

Purify... Instead of generating conjunction, it would turn one axiom into two axioms, one of which would be V=T.

I don't see why the behaviour of purify needs to change. Why can't it keep generating conjunctions?

We need the generated equalities to be easily accessible for the sort inference routine, and in the left-hand side of the goal that is an implication they are not easily accessible. Morever, the equalities would be usable only when reasoning about the RHS of an implication, so we would need two versions of the sort inference routine, or a parameter whether to use the LHS, which is weird. It would be much cleaner if strategies work with the local context and a goal of a non-implication shape.

[h0nzZik]

moving the assumptions to the local context means that the variable V would no longer be a variable, but a constant symbol.

I would separate this step into two, namely first replace V with a fresh constant cV, by adding it to the local theory. Then, we use the deduction theorem to move cV from the premise of the implication to an axiom in the local theory.

Yes. Both replace-evar-with-func-constant and intros are already merged.

[xc93]

I didn't know that you were thinking of sort inference. I was thinking about sort checking. Sort inference is definitely something good to have, but we need to be more careful here, as it infers new information.

Let's come back to my previous example (with some modification). Consider x + 2, where x is a free (unsorted) variable. What is the sort of this pattern? Is it Int, or Nat (suppose we have both Nat and Int), or is it not-determined because we don't know the sort of x?

For sort inference, maybe one of Nat or Int is the right answer, and it is debatable whether we want the most specific or general sort. For sort checking, the answer is not-determined, because x is not sorted, so we cannot sort-check x + 2. I would like to throw a warning at this stage.

[h0nzZik]

I think that the strategy purify requires sort inference. I would like to have a function getSorts() that would return a list/set of all sorts for given term. So getSorts(2)={int, nat}. We would have an axiom for plus, saying that it returns Int if the argumets are Ints. In this case, getSorts(x+2)=\emptyset, because for free variable x we do not have any sort, so that the typing axiom for + does not apply. We could throw a warning, if we would need the sort to be something - but maybe it is not necessary in all cases.

However, if the goal is of the shape \typeof(x, Int) ->Phi(x+2), we can do replace-evar-with-func-constant x . intros x_is_Int and we end with a goal the shape Phi(x() + 2) and axiom \typeof(x(), Int), and then getSorts(x() + 2) = {Int}.

[xc93]

if the goal is of the shape \typeof(x, Int) ->Phi(x+2)

Currently, we have sorted variables. Maybe what we need to do here is to keep them, so instead of the above we write \typeof(x, Int) -> Phi(x:Int, 2). This way, there is no need for inference, but just checking. This is also more efficient because we have the sorting information by hand.

[h0nzZik]

Do you mean that we could specify a type of a variable, or that we would have to do that? On the latter case, how could we specify the membership axioms, where we need to quantify over all elements?

[h0nzZik]

When thinking about the four uses from the initial comment, we probably do not need inference (represented by function getSorts), but checking would be enough (isSortOf). Purify does not need any sort information at all, we just need to make sure sorts are propagated through equalitis. Match needs to know whether a term can be bound to a variable whos sort is known. Similarly for instantiate-universals-with-ground-terms. Smt just check for the Heap sort.

[h0nzZik]

A few remarks

1. instantiate-universals-with-ground-terms and kt-solve-implications are not used in proving SL properties. However, I have heard that the former is often used in combination with the latter. Then maybe the former may not need to understand sorts - it would just instantiate every variable with every term, and the latter strategy could be used in a combination with a specialized strategy for solving sorts, like this: kt-solve-implication(solve-sorts | smt).

2. The strategy match currently work with the goal of shape
   _ -> \exists { (V1{T1}, ..., V2{T2}) #as Vs } sep(RSPATIAL) /\ RHS
   . where Vs with the information about sorts is propagated to #match. One solution is that could work with the goal of the shape

_ -> \exists { V1, ..., Vn } typeof(V1, T1) /\ ... /\ typeof(Vn, Tn) /\ sep(RSPATIAL) /\ RHS

and again, propagate the information about sorts to #match. But there is another solution: it would work with the goal of the shape

_ -> \exists { V1, ..., Vn } sep(RSPATIAL) /\ RHS

where Vi are unsorted; it would generate more matched then it does now, and we could use together with a strategy that extracts from RHS typing constraints (typeof(Vi, Ti)) and attempts to solve them (or fails) - e.g., solve-sorts from the previous point.

3. Having a separate strategy for proving sorts has at least two advantages: (1) other strategies could be simpler because now they do not need to care about sorts, and (2) if we need, we could write more advanced strategies for proving sorts, or we could use helper lemmas. Both instantiate-universals-with-ground-terms and match are still correct if the strategy for proving sorts fails.

4. @nishantjr In contrary to what I said, now I believe that not only purify does not need to be changed to work on the local context, but it cannot be changed that way - because the term it operates on may not be a predicate. Also, the generated equality cannot be added to the context, because it contains a free variable. Instead, I would just change it so that the fresh variable it generates is unsorted, and make sure that the sorting strategy (solve-sorts) can use sort information and equalities from the LHS.

5. drivers/smt-driver.md also works with sorts, but it calls getReturnSort only on symbols.

6. The SMT strategy works with sorts when it translates quantification to smtlib. I am not sure what to do here; maybe we can look to the rest of the formula to find the sort of the variable. But we may still need two SMT modes, one that works with builtin sorts and one that treats everything as unsorted. I am not sure yet. Also, the SMT strategy looks for sorted symbol declarations, so we need it to understand function sorting axioms.

7. The function filterVariablesBySort is never used; however, there is also filterBySort that is used.

8. Other places that use getReturnSort: makeFreshVariables, isPredicatePattern, isSpatialPattern. Not sure yet what to do with those.

[h0nzZik]

makeFreshVariables is used only in substMap, and the variables it creates are later overridden by other terms, so it can work without sorts and nothing should break.

isPredicatePattern, isSpatialPattern - this is used at many places; that is a reason why we can't defer sort reasoning only to a standalone strategy, but we need it available as a function.

Purify - afaik it is not used for SL properties, which means we do not have to worry about propagating sorts through equations.

[h0nzZik]

Suppose we have a function plus_1, together with the followign axiom:

\forall n. n \in [[Nat]] -> plus_1(n) \in [[Nat]].

or:

\forall n. typeof(n, Nat) -> typeof(plus_1(n), Nat).

Lets say we have a pattern P=plus_1(2 or 3). We can not easily use those axioms to prove that P has sort Nat, because in general we can substitute for n only a functional pattern. The sorting routine would need to somehow understand that the obligation typeof(2 or 3, Nat) is sufficient. Instead, I propose we use axiom with set variables:

typeof(#X, Nat) -> typeof(plus_1(#X)), Nat)

This is easier for the sorting routine to understand. Eventually, we can turn this axiom into a claim and prove it from the original axiom. This way, the advanced reasoning might be deferred to a specialized strategy.

[h0nzZik]

A few other observations. Assume the Function axiom:

A1: \forall x. typeof(x, Nat) -> exists y. typeof(y, Nat) /\ f(x)=y

This axiom combines pattern functionality with sorting information. If we wanted to prove that the pattern f(f(3)) is functional and has sort Nat, i.e. that \exists z. typeof(z, Nat) /\ f(f(3)) = z, we might use that axiom to proceed simultaneously on the functional and sorting component of our goal: the goal is an instance of A1's conclusion; therefore, using A1 we get two new obligations: from the LHS of A1 we need typeof(f(3), Nat) and from the functionality requirement we get exists t. f(3) = t. Now, these two obligations do not match A1's conclusion, so we cannot easily proceed further.

But if we used slightly more modular form of the axiom:

A2: \forall x. typeof(x, Nat) -> typeof(f(x), Nat) /\ exists y. f(x)=y

and a more modular version of the goal: typeof(f(f(3)), Nat) /\ exists z. f(f(3)) = z
then applying axiom A2 yields obligations: typeof(f(3), Nat) and exists t. f(3) = t. If we combined these two obligations into one using conjunction: typeof(f(3), Nat) /\ exists t. f(3) = t, then we could continue using axiom A2. This is quite nice, but has a few drawbacks: first, combining the two obligations into one seems too arbitrary inside the backwards-reasoning routine, and works only if the axiom has only one assumption - otherwise we the combination would have three or more components, which does not match against the conclusion of A2. Second, if we wanted to prove just sorting, or just functionality, we would need to generalize our goal, and we would still need an aditional strategy/routine to handle sorting of non-functional patterns.

We may try being more modular and split A2 into A3 and A4 as follows:

A3: \forall x. typeof(x, Nat) -> typeof(f(x), Nat)
A4: \forall x. typeof(x, Nat) -> exists y. f(x)=y

The drawback here is that attempting to prove typeof(f(f(f(3))), Nat) using A3 requires proving functionality of f(f(3)), so we still need f to be functional even if we care only about sorting. An alternative is using A5 instead of A3:

A4: \forall x. typeof(x, Nat) -> exists y. f(x)=y
A5: typeof(#X, Nat) -> typeof(f(#X), Nat)

If we care only about functionality, we still need to check sorts of subterms. We cannot completely get rid of that issue, but there is also a performance aspect: to prove exists z. f(f(f(3))) = z, we need to prove typeof(t(3), Nat) twice - this is exponential in the size of the term (minus 1 or 2 or so). We might eliminate this blowup if we considered a set of all formulas to prove, but then, what about backtracking?