Pages

sâmbătă, 21 noiembrie 2026

Lean 4 : Testing simple FASM assembly with Lean 4.

This Lean 4 program parses, simulates, and formally verifies a simple x86-64 FASM assembly routine. First, it reads the raw assembly text, strips out comments and headers, and extracts 5 executable instructions: loading 10 into rax, adding 25 to rax, moving the result into rdi, setting rax to 60 (the Linux sys_exit syscall number), and triggering syscall. Next, it executes those 5 instructions on a virtual machine model and proves mathematically that adding any two numbers leaves their exact sum in rax. The output confirms the execution succeeded. Parsed ops count: 5 means all 5 instructions were recognized cleanly. The final machine state shows rax holds 60 (the exit syscall code), rdi holds 35 (the result of 10 + 25), and exited is true. Finally, exit code (rdi): 35 confirms the assembly routine computed the right answer and terminated cleanly. Note that the "No connection to Lean" line in your editor simply means the web server briefly timed out after printing the result—your code compiled and evaluated properly.
-- Testing simple program FASM with Lean 4

inductive Reg where
  | RAX
  | RDI
deriving Repr, DecidableEq

inductive FasmOp where
  | movImm (dst : Reg) (val : Int)
  | addImm (dst : Reg) (val : Int)
  | movReg (dst src : Reg)
  | syscallExit
deriving Repr

structure Machine where
  rax    : Int := 0
  rdi    : Int := 0
  exited : Bool := false
deriving Repr

def getReg (m : Machine) : Reg → Int
  | .RAX => m.rax
  | .RDI => m.rdi

def setReg (m : Machine) (r : Reg) (v : Int) : Machine :=
  match r with
  | .RAX => { m with rax := v }
  | .RDI => { m with rdi := v }

def step (m : Machine) : FasmOp → Machine
  | .movImm dst val => setReg m dst val
  | .addImm dst val => setReg m dst (getReg m dst + val)
  | .movReg dst src => setReg m dst (getReg m src)
  | .syscallExit    =>
    if m.rax == 60 then
      { m with exited := true }
    else
      m

def exec (ops : List FasmOp) (init : Machine := {}) : Machine :=
  ops.foldl step init

def trimWs (s : String) : String :=
  let cs := s.toList
  let leftTrimmed := cs.dropWhile Char.isWhitespace
  let rightTrimmed := leftTrimmed.reverse.dropWhile Char.isWhitespace
  String.ofList rightTrimmed.reverse

def normalizeWs (s : String) : String :=
  let cleaned := trimWs s
  let noTabs := cleaned.replace "\t" " "
  let tokens := noTabs.splitOn " " |>.filter (fun p => !p.isEmpty)
  String.intercalate " " tokens

def parseReg? (s : String) : Option Reg :=
  match normalizeWs s |>.toLower with
  | "rax" => some .RAX
  | "rdi" => some .RDI
  | _     => none

def parseLine? (line : String) : Option FasmOp :=
  let rawBeforeComment := (line.splitOn ";").head!
  let codePart := normalizeWs rawBeforeComment
  if codePart.isEmpty || codePart.endsWith ":" || codePart.startsWith "format " ||
     codePart.startsWith "entry " || codePart.startsWith "segment " then
    none
  else if codePart == "syscall" then
    some .syscallExit
  else if codePart.startsWith "mov " then
    let rest := normalizeWs (codePart.drop 4).toString
    let args := rest.splitOn "," |>.map normalizeWs
    match args with
    | [d, s] =>
      match parseReg? d, s.toInt? with
      | some reg, some imm => some (.movImm reg imm)
      | _, _ =>
        match parseReg? d, parseReg? s with
        | some r1, some r2 => some (.movReg r1 r2)
        | _, _             => none
    | _ => none
  else if codePart.startsWith "add " then
    let rest := normalizeWs (codePart.drop 4).toString
    let args := rest.splitOn "," |>.map normalizeWs
    match args with
    | [d, s] =>
      match parseReg? d, s.toInt? with
      | some reg, some imm => some (.addImm reg imm)
      | _, _               => none
    | _ => none
  else
    none

def parseFasm (src : String) : List FasmOp :=
  (src.splitOn "\n").filterMap parseLine?

theorem fasm_add_general (a b : Int) :
    (exec [.movImm .RAX a, .addImm .RAX b]).rax = a + b := by
  simp [exec, step, setReg, getReg]

theorem fasm_add_correct :
    (exec [.movImm .RAX 10, .addImm .RAX 25]).rax = 35 := by
  simpa using fasm_add_general 10 25

def sampleFasm : String :=
  "format ELF64 executable 3\n" ++
  "entry _start\n" ++
  "segment readable executable\n" ++
  "_start:\n" ++
  "\tmov rax, 10\n" ++
  "    add  rax,  25\n" ++
  "    mov rdi, rax\n" ++
  "    mov rax, 60\n" ++
  "    syscall\n"

def testFasmInLean : IO Unit := do
  let ops := parseFasm sampleFasm
  let finalState := exec ops {}
  IO.println s!"Parsed ops count: {ops.length}"
  IO.println s!"Final machine state: {repr finalState}"
  IO.println s!"Exit code (rdi): {finalState.rdi}, Exited: {finalState.exited}"

#eval testFasmInLean