3 files changed, 135 insertions, 0 deletions
diff --git a/rabbit-prover/ord.scm b/rabbit-prover/ord.scm
new file mode 100644
index 0000000..c752d36
--- /dev/null
+++ b/rabbit-prover/ord.scm
@@ -0,0 +1,79 @@
+;;; Rabbit Prover --- Prove S-expression
+;;; Copyright © 2020 Masaya Tojo <masaya@tojo.tokyo>
+;;;
+;;; This file is part of Rabbit Prover.
+;;;
+;;; Rabbit Prover is free software; you can redistribute it and/or modify it
+;;; under the terms of the GNU General Public License as published by
+;;; the Free Software Foundation; either version 3 of the License, or
+;;; (at your option) any later version.
+;;;
+;;; Rabbit Prover is distributed in the hope that it will be useful, but
+;;; WITHOUT ANY WARRANTY; without even the implied warranty of
+;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+;;; General Public License for more details.
+;;;
+;;; You should have received a copy of the GNU General Public License
+;;; along with Rabbit Prover.  If not, see <http://www.gnu.org/licenses/>.
+
+(define-module (rabbit-prover ord)
+  #:export (ord?
+            ord-fin?
+            ord-inf?
+            ord-first-expt
+            ord-first-coeff
+            ord-rest
+            ord<)
+  #:use-module (rabbit-prover syntax)
+  #:use-module (rabbit-prover primitive))
+
+;;; ACL2's O-p
+;; https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.php/ACL2____O-P?path=3574/6842/3819/225/243
+(define (ord? x)
+  (if (ord-fin? x)
+      (natural? x)
+      (and (pair? (car x))
+           (ord? (ord-first-expt x))
+           (not (eqv? 0 (ord-first-expt x)))
+           (positive? (ord-first-coeff x))
+           (ord< (ord-first-expt (ord-rest x))
+                 (ord-first-expt x)))))
+
+(define/guard (ord (first-expt ord?) (first-coeff positive?) (rest ord?))
+  (cons (cons first-expt first-coeff) rest))
+
+(define (ord-fin? x)
+  (not (pair? x)))
+
+(define (ord-inf? x)
+  (pair? x))
+
+(define (ord-first-expt x)
+  (if (ord-fin? x)
+      0
+      (caar x)))
+
+(define (ord-first-coeff x)
+  (if (ord-fin? x)
+      x
+      (cdar x)))
+
+(define (ord-rest x)
+  (cdr x))
+
+(define (ord< x y)
+  (cond ((ord-fin? x)
+         (or (ord-inf? y)
+             (< x y)))
+        ((ord-fin? y) #f)
+        ((not (equal? (ord-first-expt x)
+                      (ord-first-expt y)))
+         (ord< (ord-first-expt x)
+               (ord-first-expt y)))
+        ((not (= (ord-first-coeff x)
+                 (ord-first-coeff y)))
+         (< (ord-first-coeff x)
+            (ord-first-coeff y)))
+        (else
+         (ord< (ord-rest x)
+               (ord-rest y)))))
diff --git a/rabbit-prover/primitive.scm b/rabbit-prover/primitive.scm
new file mode 100644
index 0000000..e20406e
--- /dev/null
+++ b/rabbit-prover/primitive.scm
@@ -0,0 +1,25 @@
+;;; Rabbit Prover --- Prove S-expression
+;;; Copyright © 2020 Masaya Tojo <masaya@tojo.tokyo>
+;;;
+;;; This file is part of Rabbit Prover.
+;;;
+;;; Rabbit Prover is free software; you can redistribute it and/or modify it
+;;; under the terms of the GNU General Public License as published by
+;;; the Free Software Foundation; either version 3 of the License, or
+;;; (at your option) any later version.
+;;;
+;;; Rabbit Prover is distributed in the hope that it will be useful, but
+;;; WITHOUT ANY WARRANTY; without even the implied warranty of
+;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+;;; General Public License for more details.
+;;;
+;;; You should have received a copy of the GNU General Public License
+;;; along with Rabbit Prover.  If not, see <http://www.gnu.org/licenses/>.
+
+(define-module (rabbit-prover primitive)
+  #:export (natural?))
+
+;; (natural? x) -> boolean?
+(define (natural? x)
+  (and (integer? x)
+       (not (negative? x))))
diff --git a/rabbit-prover/syntax.scm b/rabbit-prover/syntax.scm
new file mode 100644
index 0000000..5087ea2
--- /dev/null
+++ b/rabbit-prover/syntax.scm
@@ -0,0 +1,31 @@
+;;; Rabbit Prover --- Prove S-expression
+;;; Copyright © 2020 Masaya Tojo <masaya@tojo.tokyo>
+;;;
+;;; This file is part of Rabbit Prover.
+;;;
+;;; Rabbit Prover is free software; you can redistribute it and/or modify it
+;;; under the terms of the GNU General Public License as published by
+;;; the Free Software Foundation; either version 3 of the License, or
+;;; (at your option) any later version.
+;;;
+;;; Rabbit Prover is distributed in the hope that it will be useful, but
+;;; WITHOUT ANY WARRANTY; without even the implied warranty of
+;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+;;; General Public License for more details.
+;;;
+;;; You should have received a copy of the GNU General Public License
+;;; along with Rabbit Prover.  If not, see <http://www.gnu.org/licenses/>.
+
+(define-module (rabbit-prover syntax)
+  #:export (define/guard))
+
+(define-syntax-rule (define/guard (name (var pred?) ...) b b* ...)
+  (define (name var ...)
+    (unless (pred? var)
+      (error (format #f
+                     "~a:~%  expected:  ~a~%  given: "
+                     'name
+                     'pred?)
+             var))
+    ...
+    b b* ...))