nqthm

h A and B are identical. This creates a problem. An array can be represented as a list of (index, value), but for EQUAL to work, the list has to be ordered by subscript and each subscript unique. So storing into an array is represented as insertion into an ordered list. That generates a lot of special cases. Accessing an array is a linear list search by recursion: (DEFN selecta (A I) (IF (EQUAL (array-elt-subscript A) I) (array-elt-value A) (IF (EQUAL (array-prev A) (empty-array)) (UNDEFINED) (selecta (array-prev A) I)))) That's around line 3276 in [2]. The other definitions of array operations are similarly simple. Then we get to proving the classic four axioms of arrays. Around 3000 lines later, the classic four "axioms" of arrays have been proved. Much grinding through special cases. It's a neat result, but bulky. So I submitted a paper to JACM. Reviewer comments included "I hate to see something this complicated at the foundations of computer science", and just "This is unnecessary." People were really upset by all that case analysis. The theoretical problem was that I didn't have set theory. I could have built up set theory first, before array theory, then used set theory to prove array theory. That probably would have made mathematicians happier. Or not. Set theory is traditionally axiomatic, but it can be built up from constructive Boyer-Moore tuple theory if desired. I didn't argue with the reviewers. I probably could have found a more elegant path to this result, by creating intermediate lemmas, rather than letting the prover grind through the cases on automatic. But I wasn't going for a PhD. I had real work to do at an aerospace company. So, I've been beaten on by the academic community for a bulky machine proof. Today, nobody would be bothered by this approach. It's only a few thousand lines, and a human can follow it. You can be too early. (You can still run this prover today. I converted it to GNU Common LISP a decade ago. It takes about one second on a modern machine to go from the Peano-like axioms to array theory. It took 45 minutes on the VAX 11/780 I was using back in the early 1980s.) [1] https://github.com/John-Nagle/nqthm [2] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

first SAT solver, for the easy stuff. We had the Boyer-Moore prover for the hard stuff. It's Good Old Fashioned AI, and very good for the late 1970s. The SAT solver knocks off over 90% of the verification conditions. Then you want verification notation that creates hard but abstract problems for the AI solver. Like writing two asserts in a row, with the hard problem being to prove the second one from the first. We didn't have enough compute back then. It took about 45 minutes on a VAX 11/780 for the Boyer-Moore prover to build up number theory from something similar to the Peano axioms. Now it takes about a second. I ported the Boyer-Moore prover to GNU Common LISP a few years ago, just to see it live again.[3] With LLMs to do the grunt work, this is a lot less labor-intensive. And it's really needed to keep LLM garbage under control. Given a concrete goal against which to optimize, LLM coding is much more effective. Formal specifications are still hard to write, but there are many important areas of software for which the specification is simple but an efficient implementation is hard. File systems. Databases. Networking. Some kinds of control systems. Stuff that really needs to work right. [1] https://en.wikipedia.org/wiki/Mutation_testing [2] https://www.animats.com/papers/verifier/verifiermanual.pdf [3] https://github.com/John-Nagle/nqthm

e permutations of one another”)." - Boyer and Moore [1] https://www.cs.utexas.edu/~boyer/acl.pdf [2] https://github.com/John-Nagle/nqthm/tree/master

F (NUMBERP Y) (ADD1 (PLUS X Y)) (ADD1 X)))) ADD1 is a primitive of Boyer-Moore theory. ADD is actually recursive ADD1. The user just lists the proof goals. Here's the input file.[3] The proofs are all automatic. This is more automation than many modern provers seem to have. Toward the end, it proves McCarthy's theory of arrays, something I wrote. McCarthy stated those as axioms, but they are in fact provable. The proofs are clunky because there's no set theory yet. I should have built up constructive set theory first, but I didn't realize that back then. [1] https://github.com/John-Nagle/nqthm [2] https://github.com/John-Nagle/pasv/blob/master/src/work/temp... [3] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

vented, that mostly became unnecessary. Languages can be too dynamic. You pay a price for that. Python suffers from the design feature that anything can store into anything at any time. This blocks most compile-time optimizations. * Lists as a primitive are OK, but modifying lists all the time isn't what you really want. Most languages have settled on a useful set of collections today, and their implementations, especially hashes, are highly optimized. Python pretty much got this right, and other languages now use roughly Python's various collection types. * Saving the entire state of the system, instead of having source files, was a really bad idea for anything that had more than one person working on it. * The overly clever macro system makes code hard to maintain. (I tried to port [2] to Common LISP. Got about half way. It has the original Oppen-Nelson simplifier inside, the first of what's now called a SAT solver. Originally written in MACLISP (MIT's Project MAC, not Apple Macintosh), and ported to Franz LISP by Oppen and Nelson, it has too many clever macros that I wasn't able to completely figure out a decade ago.) This is a generic problem with macro systems, of course, which is why C deliberately had a weak macro system. LISP is a blast from the path. It's fun for retro reasons, but things have moved on. [1] https://github.com/John-Nagle/nqthm [2] https://github.com/John-Nagle/pasv/tree/master/src/CPC4

eory first. Arrays had a concrete representation as an ordered sequence of (index, value) tuples. The sequence has to be ordered so that array equality works. So all the functions for operating on arrays are rather clunky. Here's the sequence of machine proofs for that.[3] Back then, mathematicians hated such approaches. Infinity is a useful trick for handling the edge cases within the main case. Formulas become simpler. You can do things on blackboards with chalk more easily. Constructive math is boring and kind of ugly, because there's a lot of case analysis. But it's sound. You can avoid undecidability and Russel's class of all classes paradox. You don't actually need infinities for much of mathematics. Today there's more acceptance of machine proofs and case analysis. Everybody has computers, after all. I'm not a mathematician; I just used formal math as a tool to improve programs. This is a problem for the theorists. (A few years ago, I converted the original Boyer-Moore code to run under Gnu Common LISP, so it can be run today.[2] Proving the basics of number theory now takes under a second. It took about 45 minutes in 1981.) [1] https://sites.math.rutgers.edu/~zeilberg/Opinion160.html [2] https://github.com/John-Nagle/nqthm [3] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

ted order, and was able to prove the usual "axioms" for arrays as theorems. The machine proofs were long and involved much case analysis.[2] I submitted a paper to JACM in the early 1980s and got back reviews saying that it was just too long and inelegant to be at the fundamentals of computer science. That might not be the case today. A few years back, I put the Boyer-Moore prover on Github, after getting it to work with Gnu Common LISP. So you can still run all this 1980s stuff. It's much faster today. It took about 45 minutes to grind through these proofs on a VAX 11/780 in the early 1980s. Now it takes about a second. The proof log [2] is amusing. It's building up number theory from a very low level, starting by proving that X + 0 = X. Each theorem proved can be used as a lemma by later theorems, so you guide the process by giving it problems to solve in the right order. By line 1900, it's proving that multiplication distributes over addition. Array theory, the new stuff, starts around line 2994. The reason this is so complicated and ugly is that there's no use of axiomatic set theory. Arrays are easy if you have sets. But there are no sets here. Sets don't fit well into this strict constructive theory, because EQUAL means identical. You can't create weaker definitions of equality which say that two sets are equal if they contain the same elements regardless of order, because that introduces a risk of unsoundness. Effort must be put into keeping the tuples of the array representation in ascending order by subscript, which implies much case analysis. Mathematicians hate case analysis. Computers are good at it. [1] https://github.com/John-Nagle/nqthm [2] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

matter". At startup, there's no notion of a "set". But you can build one up via definitions and theorems. So I started by defining an array as an list of (subscript, value) tuples, ordered by subscript. Two arrays are equal if they are both valid and identical. So, given that definition, we can write the classic "axioms" for arrays as statements to be proven. First, we define "storea(A,I,V)" as the function that stores into an array in a functional sense - it creates a new array where element I has been replaced with V. And we define the predicate "arrayp", which tests whether an array is properly constructed. The key "axiom" for arrays, in Boyer-Moore notation, reads: (PROVE-LEMMA SELECT-OF-STORE (REWRITE) (IMPLIES (AND (arrayp A) (NUMBERP I) (NUMBERP J)) (EQUAL (selecta (storea A I V) J) (IF (EQUAL I J) V (selecta A J))))) That means, if A is an array, and I and J are integers, then, for all A, I, and J: storea(A,I,V)[J] = (if i=j then V else A[J]) So that's McCarthy's key axiom for arrays. It's not an axiom here. It's a lemma to be proven. It turns out that with the right sequence of lemmas, that statement can be proved as a theorem. Here's that sequence.[3] I wrote that around 1981, and it went through the Boyer-Moore theorem prover. So we could then load those statements into the Oppen-Nelson simplifier (what today is called a SAT solver) as safely proven rewrite rules. This established that the array theory was both sound and consistent between the two provers. A few years back, I revived the original Boyer-Moore theorem prover, converted it to GNU Common LISP, and put it on Github.[4] You can download it, run it, and run the set of rules in [3] through it to get the proofs. (That took about 45 minutes of VAX time in 1981. Now it takes about a second.) The proofs are long, because there's a lot of case analysis. Arrays are ordered lists of tuples in this theory, and there's a lot of detail about maintaining that order. We had to prove (PROVE-LEMMA STORE-IS-PROPER (REWRITE) (EQUAL (arrayp (storea A I V)) T)) which proves that the storing operation always produces a validly ordered array. That's essentially a code proof of correctness for a recursive function The Boyer-Moore prover was able to grind out a proof of that without help. That was a long proof, too. I submitted this to JACM. It was rejected, mostly for uglyness. The concept that you needed all this heavy machine-driven case analysis to prove a nice simple "axiom" upset mathematicians. Today it would be less of an issue. People are now more used to proofs that take a lot of grinding through cases. You could build up set theory this way, via ordered lists, if you wanted. So that's a classic of what happens if you take "equal" seriously. [1] http://www-formal.stanford.edu/jmc/towards.pdf [2] https://theory.stanford.edu/~arbrad/papers/arrays.pdf [3] https://github.com/John-Nagle/pasv/blob/master/src/work/temp... [4] https://github.com/John-Nagle/nqthm

the number representation in their prover, after which it could prove useful theorems about bounded arithmetic. (I still keep a copy of their prover around. It's on Github, at [1]. It's several thousand times faster on current hardware than it was on the DECSYSTEM 2060.) [1] https://github.com/John-Nagle/nqthm

in the pre-computer era. Simple theorems were essential in the paper and pencil era. In the 1970s and 1980s, Boyer and Moore took on much the same problem as Principia Mathematica. They published "A Computational Logic"[1], and built the first good inductive theorem prover for constructive mathematics. (I used it back then, and a few years ago I got it running again on Common LISP and put it on Github, so you can still run it.[2]) Proofs that come out of that thing have lots of case analysis. Mathematicians used to hate proofs like that. Many still do. At one point Boyer and Moore formalized what a floating point unit does, and this was used to verify an AMD floating point unit. This followed an embarrassing recall of Intel CPUs that were slightly off on division, and was paid for by AMD. It's a huge, ugly problem to formalize, compared to the ordinary rules for real arithmetic. It is, however, a system in which every true statement you care about can be proved. The proof of the four-color theorem shook up the field. Thousands of cases. A simple problem with a huge proof that required machine assistance was a new thing back then. Now it's more common. Still makes many mathematicians unhappy. [1] https://www.cs.utexas.edu/users/boyer/acl.pdf [2] https://github.com/John-Nagle/nqthm

e theorems could be transferred to the SMT solver and used there. One of the things we set out to prove were the "axioms" for arrays. There are four, credited to McCarthy in his classic 1962 paper. But we wanted to prove them from a theory of constructive arrays. In Boyer-Moore theory, we defined arrays as sorted lists of (subscript, value) tuples. And then we set out to prove the classic four axioms for arrays with machine proofs. Which we did.[3], starting at line 3372. That file is the Boyer-Moore theorem prover grinding its way up from a very low base of number theory to the theorems we needed for our program proving system. (On a modern computer, in seconds. Took 3 hours on a VAX in 1980. We just didn't have enough engine for this stuff back then.) In that notation, "(selecta A I)" means A[I], and "(storea A I V)" is array A with A[I] replaced with V. After some struggles, we got the the prover to find a way to prove that. But it's ugly. There's lots of case analysis, which mathematicians hate. We didn't get to redefine "equal", so we couldn't have abstract sets. We had to have ordered lists of tuples, which meant all the fussyness of updating an ordered list representation and proving that was sound. But it all worked. So I submitted this to JACM, back when that mattered. It was rejected. The comments were along the lines of "I don't like having something that ugly at the foundations of computer science". The reviewers all agreed it was valid, but they just didn't like doing it that way, in an automatic but inelegant way. Looks like the author of the original article here is still having that problem. Good times back then. But we were way ahead of our time. [1] https://github.com/John-Nagle/pasv [2] https://github.com/John-Nagle/nqthm [3] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

s a complete decision procedure for formulas which contain only addition, subtraction, multiplication by constants, Boolean operators, structures, and arrays. This covers most data access operations. It's fully automatic and complete - the algorithm always succeeds within its problem space. You need one of those for the easy parts. For the hard parts, we used the Boyer-Moore prover. (Sources are available and I brought it back to life on Github.[3] It runs 3000x faster than it did in 1982.) The interface with the language is crucial to usability. Most efforts get this wrong. They put the verification stuff in separate files, or in comments. It should be part of the normal code. We built the verification language into the compiler, so you used the same source and the same syntax for compiling and verification. There were additional statements - ASSERT, ENTER, EXIT, etc. The same compiler front end was used for both compiling and verification. The verifier itself ran off the byte code from the compiler front end. All type and size issues had been decided at that point, so the verifier was looking at unambiguous operations such as "pop two operands from stack, add in 16-bit twos complement arithmetic, push on stack". This captured the semantics of the program the same way the compiler did. The user never sees the easy stuff. Every subscript use generates a bounds check assertion which has to be proved. If the prover is able to prove the assertion true, the user doesn't see it. Only the errors are visible. Another trick is that you don't write "assert(a and b and and d)", you write "assert(a); assert(b);". Those generate separate proof goals, and if only one fails,the user gets error messages about only that one. Also, when you write "assert(a); assert(b);", the second one is proved under the assumption the first one is true. This prevents cascading errors. A key point here is that verification is meaningless unless you prove all the theorems. If you write "assert(false)" other errors go away, and you're left with one simple error, which you cannot eliminate. You don't get to dismiss it. It's possible to write an assertion that's equivalent to "assert(false);", such as "assert(0 > 1)"; This is why I'm so negative on the arguments from some of the Rust crowd that a little undefined behavior is OK. It can blow at any seam. When you needed to prove something hard, you wrote assert(a); assert(b); where a could be proved by the Nelson-Oppen prover from the code before it. B was chosen such that if you assumed b, the Nelson-Oppen prover could prove anything required past that point. Now you had one error message, that the system couldn't prove "a implies b". So then someone had to try to prove that with the Boyer-Moore prover. The Boyer-Moore prover is mostly automatic, but often someone had to provide intermediate theorems to get to a hard one. Those were all machine-checked. If this succeeded, the Boyer-Moore prover generated a theorem that a implies b for use by the verifier. Rerunning the program verifier would then succeed. Such theorems could be reused with different variable bindings, so if the same problem came up again, it didn't require more work with the Boyer-Moore system. If you're generating vast amounts of user-visible proof work, something is wrong. The whole system I'm describing is now on Github.[4] It's decades-old code, but I've ported about 80% of it to modern compilers. The Franz LISP to Common LISP port of the prover isn't working well, and the author of that code died years ago. If anyone wants to work on that, go ahead. [1] http://www.animats.com/papers/verifier/verifiermanual.pdf [2] https://docs.microsoft.com/en-us/windows-hardware/drivers/de... [3] https://github.com/John-Nagle/nqthm [4] https://github.com/John-Nagle/pasv

ea A I V) I) V))) (PROVE-LEMMA SELECT-OF-STORE-2 (REWRITE) (IMPLIES (AND (arrayp A) (NUMBERP I) (NUMBERP J) (NOT (EQUAL I J))) (EQUAL (selecta (storea A I V) J) (selecta A J)))) But Boyer-Moore theory is constructive; everything must have a definition that can be evaluated as a function. So I had to define arrays and the "selecta" and "storea" functions so that this would work. I could do this by defining an array as a list of (subscript, value) tuples. (ADD-SHELL UNDEFINED-OBJECT UNDEFINED UNDEFINEDP ()) (ADD-SHELL array-shell empty-array array-recognizer ((array-elt-value (NONE-OF) UNDEFINED) (array-elt-subscript (ONE-OF NUMBERP) ZERO) (array-prev (ONE-OF array-recognizer) empty-array))) This is simply a structure definition for a list. An array-shell has an array-elt-value, an array-elt-subscript, and array-prev, which is the rest of the elements. "array-shell" is the constructor, "empty-array" is essentially "nil" for this type, and "array-recognizer" is a predicate which is true for objects of type array-shell. For array equality to work, the list of tuples had to be ordered by subscript, so that two arrays with the same values would always have the same representation. So selecta and storea are complicated. selecta is a recursive lookup in a list: (DEFN selecta (A I) (IF (EQUAL (array-elt-subscript A) I) (array-elt-value A) (IF (EQUAL (array-prev A) (empty-array)) (UNDEFINED) (selecta (array-prev A) I)))) Store into array is ugly, because it's an update of an ordered list. (DEFN storea (A I V) (IF (NOT (arrayp A)) (empty-array) (IF (NOT (NUMBERP I)) A (IF (EQUAL A (empty-array)) (IF (EQUAL V (UNDEFINED)) (empty-array) (array-shell V I (empty-array))) (IF (EQUAL (array-elt-subscript A) I) (IF (EQUAL V (UNDEFINED)) (array-prev A) (array-shell V I (array-prev A))) (IF (LESSP (array-elt-subscript A) I) (IF (EQUAL V (UNDEFINED)) A (array-shell V I A)) (array-shell (array-elt-value A) (array-elt-subscript A) (storea (array-prev A) I V)))))))) This recursive function is complicated enough that it needs a lemma to help with proof of termination. (PROVE-LEMMA storea-is-sound (REWRITE) (implies (and (arrayp a) (not (equal a (empty-array)))) (lessp (count (array-prev a)) (count a)))) This says that the array-prev list component of a is always shorter than a. The Boyer-Moore prover must prove termination for all defined functions, which it does by examining any recursive call and proving that there is a measure defined on the arguments which is a smaller nonnegative integer. For the easy cases, the prover can do this automatically, but sometimes you have to define a lemma to help it. The lemma, of course, also has to be proved. So, given all that, the Boyer-Moore theorem prover could be turned loose to grind out proofs of the rules for arrays. It took about 45 minutes of grinding in 1982 on a 1 MIPS VAX 11/780. You can rerun it now. Here's the prover, which requires clisp.[1]. Here's the entire set of definitions and theorems we used for program verification.[2]. Read the instructions at [1], and get the system up to where it's done "boot-strap". Then load the file at [2]. Long, detailed, human-readable explanations of the proof steps are displayed. The entire proof run for all those basic theorems takes about a second, and that's probably mostly scrolling. So, having rigorously proved the "axioms" for arrays from first principles, I submitted a paper to JACM. The reviewer comments I got back were mainly about the uglyness of the approach. All that case analysis! One comment was that the reviewer was upset about having a proof that ugly at the foundations of computer science. The paper was rejected. The reason it's ugly is that it doesn't get to use set theory. Informally, a set is a collection whose order does not matter. "Order does not matter" is not a meaningful concept in strict Boyer-Moore theory. If order matters, there are many cases to prove, stemming from all those IF statements in the definitions. A generation later, fewer mathematicians would be bothered by this form of "uglyness". But back then, machine proofs were so rare that this was considered awful. Also, now that computers can do this in a second, complaining that it's too complicated seems whiny. [1] https://github.com/John-Nagle/nqthm [2] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

L is not a list, it is considered to be ordered. This makes it a total function, runnable on any input, even though the result for the "wrong" type is not useful. This provides the benefits of types without requiring a theory of types. It's a very clean way to look at the foundations of mathematics. It's simpler than Russell and Whitehead. When you prove things using definitions like this, there's a lot of case analysis. This gets worse combinatorially; a theorem with four variables with type constraints will generate at least 2⁴ cases, only one of which is interesting. Most of the cases, such as when L is not a list, are trivial, but have to be analyzed. Computers are great at this, and the Boyer-Moore prover deals with those cases without any trouble. But it went against a long tradition in mathematics of avoiding case analysis. That made this approach unpopular with the generation of pre-computer mathematicians. Today, it would be more acceptable. (It's fun to run the Boyer-Moore prover today. In the 1980s, it took 45 minutes to grind through the basic theory of numbers. Now it takes a few seconds.) [1] https://www.amazon.com/Computational-Logic-Robert-S-Boyer/dp... [2] https://github.com/John-Nagle/nqthm