File size: 1,979 Bytes
6d5264f a891214 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | -- SPDX-License-Identifier: LicenseRef-Sovereign-Leviathan-SL-AGPL3-001
-- Licensing: see LICENSE in the repository root.
/- LatticeKernel.lean β Lean 4 specification of the relational kernel.
Theorems are the contracts; execution stays in miniKanren/Prolog/Formulog.
lake / lean LatticeKernel.lean (mathlib not required)
-/
namespace LatticeKernel
inductive Peano where
| z
| s : Peano β Peano
deriving Repr, DecidableEq
def add : Peano β Peano β Peano
| .z, y => y
| .s x, y => .s (add x y)
def mul : Peano β Peano β Peano
| .z, _ => .z
| .s x, y => add y (mul x y)
theorem add_z (y : Peano) : add .z y = y := rfl
theorem add_s (x y : Peano) : add (.s x) y = .s (add x y) := rfl
inductive Bit where
| b0 | b1
deriving Repr, DecidableEq
def bitXor : Bit β Bit β Bit
| .b0, .b0 => .b0
| .b0, .b1 => .b1
| .b1, .b0 => .b1
| .b1, .b1 => .b0
def bitAnd : Bit β Bit β Bit
| .b1, .b1 => .b1
| _, _ => .b0
def fullAdd (cin x y : Bit) : Bit Γ Bit :=
let w := bitXor x y
let c1 := bitAnd x y
let r := bitXor w cin
let c2 := bitAnd w cin
(r, bitXor c1 c2)
inductive Smt where
| atom : String β Smt
| not : Smt β Smt
| and : Smt β Smt β Smt
deriving Repr
partial def atoms : Smt β List Smt
| .and a b => atoms a ++ atoms b
| p => [p]
def satStub (Ο : Smt) : Bool :=
let as := atoms Ο
Β¬ as.any (fun p =>
match p with
| .not q => as.contains q
| q => as.contains (.not q))
inductive FsmState where
| s0 | s1
deriving Repr, DecidableEq
def fsm (st : FsmState) (inp : Bit) : FsmState Γ Bit :=
match st, inp with
| .s0, .b0 => (.s0, .b0)
| .s0, .b1 => (.s1, .b0)
| .s1, .b0 => (.s0, .b1)
| .s1, .b1 => (.s1, .b1)
inductive Abs where
| conc : Nat β Abs
| top
| interval : Nat β Nat β Abs
deriving Repr
def refines : Abs β Nat β Prop
| .conc c, n => c = n
| .top, _ => True
| .interval lo hi, n => lo β€ n β§ n β€ hi
end LatticeKernel
|