;;; Vikalpa --- Proof Assistant
;;; Copyright © 2020 Masaya Tojo <masaya@tojo.tokyo>
;;;
;;; This file is part of Vikalpa.
;;;
;;; Vikalpa 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.
;;;
;;; Vikalpa 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 Vikalpa.  If not, see <http://www.gnu.org/licenses/>.

(define-module (vikalpa the-little-prover)
  #:export (atom? nat? the-little-prover)
  #:use-module (vikalpa))

(define (atom? x)
  (not (pair? x)))

(define (nat? x)
  (and (integer? x)
       (<= 0 x)))

(define-system the-little-prover ()
  (define-core-function atom? (x) atom?)
  (define-core-function nat? (x) nat?)
  (define-core-function < (x y)
    (lambda (x y)
      (if (number? x)
          (if (number? y)
              (< x y)
              (< x 0))
          (if (number? y)
              (< 0 y)
              #f))))
  (set-measure-predicate nat?)
  (set-measure-less-than <)
  (define-core-function + (x y)
    (lambda (x y)
      (if (number? x)
          (if (number? y)
              (+ x y)
              x)
          (if (number? y)
              y
              0))))
  (define-core-function cons (x y) cons)
  (define-core-function car (x)
    (lambda (x)
      (if (atom? x) '() (car x))))
  (define-core-function cdr (x)
    (lambda (x)
      (if (atom? x) '() (cdr x))))
  (define-trivial-total-function size (x)
    (if (atom? x)
        0
        (+ 1
           (+ (size (car x))
              (size (cdr x))))))

  ;; Axioms of Equal
  (define-axiom equal-same (x)
    (equal? (equal? x x) #t))
  (define-axiom equal-swap (x y)
    (equal? (equal? x y) (equal? y x)))
  (define-axiom equal-if (x y)
    (if (equal? x y) (equal? x y) #t))

  ;; Axioms of Cons
  (define-axiom atom/cons (x y)
    (equal? (atom? (cons x y)) #f))
  (define-axiom car/cons (x y)
    (equal? (car (cons x y)) x))
  (define-axiom cdr/cons (x y)
    (equal? (cdr (cons x y)) y))
  (define-axiom cons/car+cdr (x)
    (if (atom? x)
        #t
        (equal? (cons (car x) (cdr x)) x)))

  ;; Axioms of If
  (define-axiom if-true (x y)
    (equal? (if #t x y) x))
  (define-axiom if-false (x y)
    (equal? (if #f x y) y))
  (define-axiom if-same (x y)
    (equal? (if x y y) y))
  (define-axiom if-nest-A (x y z)
    (if x (equal? (if x y z) y) #t))
  (define-axiom if-nest-E (x y z)
    (if x #t (equal? (if x y z) z)))

  ;; Axioms of Size
  (define-axiom nat/size (x)
    (equal? (nat? (size x)) #t))
  (define-axiom size/car (x)
    (if (atom? x)
        #t
        (equal? (< (size (car x)) (size x)) #t)))
  (define-axiom size/cdr (x)
    (if (atom? x)
        #t
        (equal? (< (size (cdr x)) (size x)) #t)))

  ;; Axioms of `+` and `<`
  (define-axiom identity-+ (x)
    (if (nat? x)
        (equal? (+ 0 x) x)
        #t))
  (define-axiom commute-+ (x y)
    (equal? (+ x y) (+ y x)))
  (define-axiom associate-+ (x y z)
    (equal? (+ (+ x y) z) (+ x (+ y z))))
  (define-axiom positive-+ (x y)
    (if (< '0 x)
        (if (< '0 y)
            (equal? (< '0 (+ x y)) #t)
            #t)
        #t))
  (define-axiom nat/+ (x y)
    (if (nat? x)
        (if (nat? y)
            (equal? (nat? (+ x y)) #t)
            #t)
        #t))
  (define-axiom common-addends-< (x y z)
    (equal? (< (+ x z) (+ y z))
            (< x y)))
  
  ;; Prelude
  (define-function list-induction (x)
    (if (atom? x)
        x
        (cons (car x)
              (list-induction (cdr x)))))

  (define-function star-induction (x)
    (if (atom? x)
        x
        (cons (star-induction (car x))
              (star-induction (cdr x)))))

  (define-proof list-induction
    (size x)
    (((2 3) size/cdr)
     ((2) if-same)
     ((1) nat/size)
     (() if-true)))

  (define-proof star-induction
    (size x)
    (((2 3 1) size/car)
     ((2 3 2) size/cdr)
     ((2 3) if-true)
     ((2) if-same)
     ((1) nat/size)
     (() if-true))))