Files
skills/public/program-verification.html
zeekay 747dafba10 Register WebMCP tools on every page, and name each page's twin from site.py
Every page now loads /webmcp.js, scripts/webmcp.ts with its types
stripped (npm run webmcp). Where the browser has document.modelContext
it registers two read-only tools: search_skills over the published
skills index, and get_skill, which returns a skill's markdown checked
against the index digest. The markdown alternate link moves from
build.py to site.py, so CI holds every page to it.

The API catalog gains the site itself (llms.txt and the skills index)
and hanzo.ai/agents; the live discovery check now fetches every
catalog link. tests/site.mjs drives the tools through a recording
modelContext, and checks a browser without one loads clean.
2026-10-26 20:57:05 -07:00

596 lines
26 KiB
HTML

<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>program-verification</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/program-verification">
<link rel="alternate" type="text/markdown" href="/program-verification.md">
<script type="module" src="/webmcp.js"></script>
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/program-verification.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>program-verification</h1><p class="lede">Program verification including Hoare logic, SMT-based verification, refinement types, and proof-carrying code</p><h1>Program Verification</h1>
<p><strong>Scope</strong>: Hoare logic, weakest preconditions, SMT-based verification, refinement types, separation logic, proof automation <strong>Lines</strong>: ~400 <strong>Last Updated</strong>: 2025-10-25</p>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Proving program correctness formally</li><li>Implementing verified compilers or kernels</li><li>Using tools like Dafny, Frama-C, or Why3</li><li>Designing proof-carrying code systems</li><li>Verifying safety and security properties</li><li>Working with separation logic for memory safety</li></ul>
<h2>Core Concepts</h2>
<h3>Hoare Logic</h3>
<p><strong>Hoare triple</strong>: {P} C {Q}</p>
<ul><li>P: precondition (assertion before C)</li><li>C: command/program</li><li>Q: postcondition (assertion after C)</li></ul>
<p><strong>Partial correctness</strong>: If P holds before C and C terminates, then Q holds after <strong>Total correctness</strong>: P holds before C, C terminates, and Q holds after</p>
<pre><code class="lang-python">from dataclasses import dataclass
from typing import Union, Callable
# Assertions (predicates on program state)
Assertion = Callable[[dict], bool]
# Commands
@dataclass
class Skip:
&quot;&quot;&quot;skip - do nothing&quot;&quot;&quot;
pass
@dataclass
class Assign:
&quot;&quot;&quot;x := e&quot;&quot;&quot;
var: str
expr: &#x27;Expr&#x27;
@dataclass
class Seq:
&quot;&quot;&quot;C₁; C₂ - sequential composition&quot;&quot;&quot;
first: &#x27;Command&#x27;
second: &#x27;Command&#x27;
@dataclass
class If:
&quot;&quot;&quot;if B then C₁ else C₂&quot;&quot;&quot;
cond: &#x27;Expr&#x27;
then_branch: &#x27;Command&#x27;
else_branch: &#x27;Command&#x27;
@dataclass
class While:
&quot;&quot;&quot;while B do C&quot;&quot;&quot;
cond: &#x27;Expr&#x27;
body: &#x27;Command&#x27;
Command = Union[Skip, Assign, Seq, If, While]
# Hoare logic rules
def hoare_skip(P: Assertion) -&gt; bool:
&quot;&quot;&quot;
{P} skip {P}
Skip preserves any assertion
&quot;&quot;&quot;
return True # Always valid
def hoare_assign(P: Assertion, var: str, expr) -&gt; Assertion:
&quot;&quot;&quot;
{P[x := e]} x := e {P}
Weakest precondition: substitute e for x in P
&quot;&quot;&quot;
def precondition(state: dict) -&gt; bool:
# Evaluate expression in current state
new_state = state | {var: eval_expr(expr, state)}
return P(new_state)
return precondition
def hoare_seq(P: Assertion, C1: Command, C2: Command, Q: Assertion) -&gt; tuple[bool, Assertion]:
&quot;&quot;&quot;
{P} C₁ {R} {R} C₂ {Q}
─────────────────────────
{P} C₁; C₂ {Q}
Need to find intermediate assertion R
&quot;&quot;&quot;
# R is the weakest precondition of C₂ with respect to Q
R = weakest_precondition(C2, Q)
return True, R
def hoare_if(P: Assertion, B, C1: Command, C2: Command, Q: Assertion) -&gt; bool:
&quot;&quot;&quot;
{P ∧ B} C₁ {Q} {P ∧ ¬B} C₂ {Q}
───────────────────────────────────
{P} if B then C₁ else C₂ {Q}
&quot;&quot;&quot;
# Verify both branches
def P_and_B(state): return P(state) and eval_expr(B, state)
def P_and_not_B(state): return P(state) and not eval_expr(B, state)
# Would need to verify {P ∧ B} C₁ {Q} and {P ∧ ¬B} C₂ {Q}
return True # Simplified
def hoare_while(I: Assertion, B, C: Command) -&gt; bool:
&quot;&quot;&quot;
{I ∧ B} C {I}
────────────────────────
{I} while B do C {I ∧ ¬B}
I: loop invariant
Must prove:
1. I preserved by loop body when B true
2. After loop, I ∧ ¬B holds
&quot;&quot;&quot;
# Verify loop invariant preservation
def I_and_B(state): return I(state) and eval_expr(B, state)
# Would verify {I ∧ B} C {I}
return True # Simplified
def eval_expr(expr, state: dict):
&quot;&quot;&quot;Evaluate expression in state&quot;&quot;&quot;
# Simplified evaluation
return expr
# Example: Prove {x = 5} x := x + 1 {x = 6}
def example_assign():
# Postcondition: x = 6
Q = lambda state: state[&#x27;x&#x27;] == 6
# Precondition: Q[x := x+1] = (x+1 = 6) = (x = 5)
P = lambda state: state[&#x27;x&#x27;] + 1 == 6
# Verify
initial_state = {&#x27;x&#x27;: 5}
assert P(initial_state)
# Execute x := x + 1
final_state = {&#x27;x&#x27;: initial_state[&#x27;x&#x27;] + 1}
assert Q(final_state)
print(&quot;Verified: {x = 5} x := x + 1 {x = 6}&quot;)
example_assign()</code></pre>
<h3>Weakest Precondition</h3>
<p><strong>wp(C, Q)</strong>: Weakest precondition - most general P such that {P} C {Q}</p>
<pre><code class="lang-python">def weakest_precondition(cmd: Command, Q: Assertion) -&gt; Assertion:
&quot;&quot;&quot;
Compute wp(C, Q) - weakest precondition
&quot;&quot;&quot;
match cmd:
case Skip():
# wp(skip, Q) = Q
return Q
case Assign(var, expr):
# wp(x := e, Q) = Q[x := e]
return lambda state: Q(state | {var: eval_expr(expr, state)})
case Seq(C1, C2):
# wp(C₁; C₂, Q) = wp(C₁, wp(C₂, Q))
wp_C2 = weakest_precondition(C2, Q)
return weakest_precondition(C1, wp_C2)
case If(B, C1, C2):
# wp(if B then C₁ else C₂, Q) = (B ⟹ wp(C₁, Q)) ∧ (¬B ⟹ wp(C₂, Q))
wp_C1 = weakest_precondition(C1, Q)
wp_C2 = weakest_precondition(C2, Q)
return lambda state: (
(eval_expr(B, state) and wp_C1(state)) or
(not eval_expr(B, state) and wp_C2(state))
)
case While(B, body):
# wp(while B do C, Q) requires loop invariant
# For now, return Q (simplified)
return Q
# Example: wp(x := x + 1; y := x * 2, y = 12)
C1 = Assign(&#x27;x&#x27;, lambda s: s[&#x27;x&#x27;] + 1)
C2 = Assign(&#x27;y&#x27;, lambda s: s[&#x27;x&#x27;] * 2)
program = Seq(C1, C2)
postcondition = lambda s: s[&#x27;y&#x27;] == 12
wp = weakest_precondition(program, postcondition)
# wp should be: x + 1 * 2 = 12, i.e., x = 5
state = {&#x27;x&#x27;: 5, &#x27;y&#x27;: 0}
print(f&quot;wp holds for x=5: {wp(state)}&quot;)</code></pre>
<h3>Refinement Types</h3>
<p><strong>Refinement type</strong>: {x:τ | P(x)} - type τ refined by predicate P</p>
<pre><code class="lang-python">@dataclass
class RefinementType:
&quot;&quot;&quot;Refinement type: {x:τ | P(x)}&quot;&quot;&quot;
base_type: type
predicate: Callable[[any], bool]
def check(self, value):
&quot;&quot;&quot;Check if value satisfies refinement&quot;&quot;&quot;
if not isinstance(value, self.base_type):
return False
return self.predicate(value)
# Examples
Pos = RefinementType(int, lambda x: x &gt; 0)
Nat = RefinementType(int, lambda x: x &gt;= 0)
NonZero = RefinementType(int, lambda x: x != 0)
def safe_div(a: int, b: int) -&gt; int:
&quot;&quot;&quot;
Type: (a:int) → (b:int) → {b ≠ 0} → int
Requires proof that b ≠ 0
&quot;&quot;&quot;
assert NonZero.check(b), &quot;Division by zero&quot;
return a // b
# Usage
result = safe_div(10, 2) # OK
print(f&quot;10 / 2 = {result}&quot;)
try:
result = safe_div(10, 0) # Error: assertion fails
except AssertionError as e:
print(f&quot;Error: {e}&quot;)
# In Liquid Haskell:
&quot;&quot;&quot;
{-@ type Pos = {v:Int | v &gt; 0} @-}
{-@ type NonZero = {v:Int | v /= 0} @-}
{-@ div :: Int -&gt; NonZero -&gt; Int @-}
div :: Int -&gt; Int -&gt; Int
div x y = x `div` y
-- Type checker ensures y ≠ 0 at call sites
&quot;&quot;&quot;</code></pre>
<h3>SMT-Based Verification</h3>
<p><strong>Using Z3 for verification</strong>:</p>
<pre><code class="lang-python">try:
from z3 import Int, Solver, sat, And, Or, Not
def verify_program_z3():
&quot;&quot;&quot;
Verify: {x ≥ 0} if x &lt; 10 then y := x else y := 10 {y &lt; 11}
Using Z3 SMT solver
&quot;&quot;&quot;
x, y, y_out = Int(&#x27;x&#x27;), Int(&#x27;y&#x27;), Int(&#x27;y_out&#x27;)
# Precondition: x ≥ 0
P = x &gt;= 0
# Program semantics
branch1 = And(x &lt; 10, y_out == x) # Then: y := x
branch2 = And(x &gt;= 10, y_out == 10) # Else: y := 10
program = Or(branch1, branch2)
# Postcondition: y &lt; 11
Q = y_out &lt; 11
# Verify: ¬(P ∧ program ⟹ Q)
# If unsatisfiable, then {P} program {Q} is valid
solver = Solver()
solver.add(P)
solver.add(program)
solver.add(Not(Q))
if solver.check() == sat:
print(f&quot;Counterexample: {solver.model()}&quot;)
return False
else:
print(&quot;Verified: {x ≥ 0} program {y &lt; 11}&quot;)
return True
verify_program_z3()
except ImportError:
print(&quot;Z3 not available, skipping SMT verification example&quot;)</code></pre>
<h3>Separation Logic</h3>
<p><strong>Heap assertions</strong>: P * Q (P and Q hold on disjoint heap parts)</p>
<pre><code class="lang-python">@dataclass
class PointsTo:
&quot;&quot;&quot;x ↦ v - heap location x contains value v&quot;&quot;&quot;
location: str
value: any
@dataclass
class SeparatingConjunction:
&quot;&quot;&quot;P * Q - P and Q hold on disjoint heaps&quot;&quot;&quot;
left: &#x27;HeapAssertion&#x27;
right: &#x27;HeapAssertion&#x27;
@dataclass
class Emp:
&quot;&quot;&quot;emp - empty heap&quot;&quot;&quot;
pass
HeapAssertion = Union[PointsTo, SeparatingConjunction, Emp]
# Frame rule (key rule in separation logic):
&quot;&quot;&quot;
{P} C {Q}
─────────────────── (Frame)
{P * R} C {Q * R}
If R describes heap C doesn&#x27;t touch, it&#x27;s preserved
&quot;&quot;&quot;
def frame_rule_example():
&quot;&quot;&quot;
Example: {x ↦ 5} *p := 10 {x ↦ 5}
where p and x are different locations
Frame rule:
{emp} *p := 10 {p ↦ 10}
─────────────────────────────── (Frame)
{emp * x ↦ 5} *p := 10 {p ↦ 10 * x ↦ 5}
&quot;&quot;&quot;
print(&quot;Frame rule: Unmodified heap portions preserved&quot;)
frame_rule_example()</code></pre>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: Loop Invariants</h3>
<pre><code class="lang-python">def verify_loop_invariant():
&quot;&quot;&quot;
Verify: {n ≥ 0} i := 0; s := 0; while i &lt; n do (s := s + i; i := i + 1) {s = n*(n-1)/2}
Loop invariant: s = i*(i-1)/2 ∧ i ≤ n
&quot;&quot;&quot;
# Precondition: n ≥ 0
# After i := 0; s := 0: s = 0 ∧ i = 0 (implies invariant)
# Invariant: s = i*(i-1)/2 ∧ i ≤ n
# Body preserves invariant when i &lt; n
# After loop: i = n ∧ s = i*(i-1)/2 = n*(n-1)/2
print(&quot;Loop invariant: s = i*(i-1)/2 ∧ i ≤ n&quot;)
verify_loop_invariant()</code></pre>
<h3>Pattern 2: Verification Conditions</h3>
<pre><code class="lang-python">def generate_verification_conditions(cmd: Command, Q: Assertion) -&gt; list:
&quot;&quot;&quot;
Generate verification conditions (VCs) for program
VCs are formulas to prove for correctness
&quot;&quot;&quot;
vcs = []
# Example: for loop, generate:
# 1. Invariant initially true
# 2. Invariant preserved by body
# 3. Invariant + ¬condition implies postcondition
match cmd:
case While(cond, body):
# Would generate 3 VCs above
pass
return vcs</code></pre>
<hr>
<h2>Quick Reference</h2>
<h3>Hoare Logic Rules</h3>
<pre><code>{P} skip {P} (Skip)
{P[x := e]} x := e {P} (Assign)
{P} C₁ {R} {R} C₂ {Q}
──────────────────────── (Seq)
{P} C₁; C₂ {Q}
{P ∧ B} C₁ {Q} {P ∧ ¬B} C₂ {Q}
────────────────────────────────── (If)
{P} if B then C₁ else C₂ {Q}
{I ∧ B} C {I}
──────────────────────── (While)
{I} while B do C {I ∧ ¬B}</code></pre>
<h3>Weakest Precondition</h3>
<pre><code>wp(skip, Q) = Q
wp(x := e, Q) = Q[x := e]
wp(C₁; C₂, Q) = wp(C₁, wp(C₂, Q))
wp(if B then C₁ else C₂, Q) = (B ⟹ wp(C₁, Q)) ∧ (¬B ⟹ wp(C₂, Q))</code></pre>
<hr>
<h2>Anti-Patterns</h2>
<p>❌ <strong>Forgetting loop invariants</strong>: Can&#x27;t verify loops without them ✅ Find invariant that: (1) holds initially, (2) preserved by body, (3) + ¬condition implies post</p>
<p>❌ <strong>Over-specifying preconditions</strong>: Weakest precondition is most general ✅ Use wp() to find most permissive precondition</p>
<p>❌ <strong>Ignoring frame</strong>: Assuming entire heap in Hoare triple ✅ Use separation logic to reason about heap portions</p>
<hr>
<h2>Related Skills</h2>
<ul><li><code>lambda-calculus.md</code> - Formal semantics foundation</li><li><code>type-systems.md</code> - Type soundness proofs</li><li><code>curry-howard.md</code> - Proofs as programs</li><li><code>operational-semantics.md</code> - Program execution model</li><li><code>formal/z3-solver-basics.md</code> - SMT solving for verification</li><li><code>formal/lean-proof-basics.md</code> - Interactive theorem proving</li></ul>
<hr>
<p><strong>Last Updated</strong>: 2025-10-25 <strong>Format Version</strong>: 1.0 (Atomic)</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/program-verification.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>