Logica Hoare — Demonstrarea matematică a corectitudinii programelor

Ce este logica Hoare?

Logica Hoare este un sistem formal pentru raționament despre corectitudinea programelor imperativ. A fost propusă de C. A. R. Hoare în 1969 și rămâne fundația teoretică a verificării formale a software-ului.

Ideea centrală: Orice program poate fi caracterizat printr-un triplet logic:

$${P}\ C\ {Q}$$

• $P$ = precondiția — ce trebuie să fie adevărat înainte de execuție
• $C$ = comanda (programul)
• $Q$ = postcondiția — ce e garantat adevărat după execuție

"Testele pot demonstra prezența bug-urilor, dar nu și absența lor. O demonstrație formală poate." — Edsger Dijkstra

1. Tripletul Hoare în profunzime

1.1 Semantica

Tripletul ${P}\ C\ {Q}$ e adevărat dacă și numai dacă:

Pentru orice stare care satisface $P$, după execuția comenzii $C$, starea rezultată satisface $Q$.

Cu alte cuvinte: dacă $P$ e adevărat înainte și $C$ se execută, atunci $Q$ e adevărat după.

1.2 Exemple intuitive

1.3 Precondiția cea mai slabă (Weakest Precondition)

Dijkstra a introdus conceptul de weakest precondition $wp(C, Q)$ — cea mai slabă precondiție care garantează $Q$ după $C$.

Exemplu:

$$wp(y \leftarrow x + 2, y > 10) = x + 2 > 10 = x > 8$$

Orice $x > 8$ garantează $y > 10$ după asignare. $x > 8$ e cea mai slabă precondiție — nu putem cere mai puțin.

2. Regulile de inferență

2.1 Regula de asignare

Cea mai fundamentală regulă:

$$\overline{{Q[x \leftarrow e]}\ x \leftarrow e\ {Q}}$$

Se citește: dacă înlocuim pe $x$ cu $e$ în $Q$ și obținem o afirmație adevărată înainte, atunci după asignare $Q$ e adevărat.

Exemplu:

$$\overline{{x + 2 > 10}\ y \leftarrow x + 2\ {y > 10}}$$

Simplificând: ${x > 8}\ y \leftarrow x + 2\ {y > 10}$.

2.2 Regula de secvență

Dacă avem două comenzi în secvență:

$$\frac{{P}\ C_1\ {R},\ {R}\ C_2\ {Q}}{{P}\ C_1; C_2\ {Q}}$$

Exemplu: $$\frac{{x = 5}\ y \leftarrow x + 2\ {y = 7},\ {y = 7}\ z \leftarrow y * 2\ {z = 14}}{{x = 5}\ y \leftarrow x + 2;\ z \leftarrow y * 2\ {z = 14}}$$

2.3 Regula condițională

if (B) { C1 } else { C2 }

$$\frac{{P \land B}\ C_1\ {Q},\ {P \land \lnot B}\ C_2\ {Q}}{{P}\ \textbf{if}\ B\ \textbf{then}\ C_1\ \textbf{else}\ C_2\ {Q}}$$

Exemplu: Vrem să demonstrăm că programul calculează corect valoarea absolută:

// { x este un întreg oarecare }
if (x >= 0) {
    abs = x;
} else {
    abs = -x;
}
// { abs == |x| }

Demonstrație:

• Cazul 1 ($x \ge 0$): ${x \ge 0}\ abs \leftarrow x\ {abs = |x|}$ — corect, $|x| = x$ când $x \ge 0$
• Cazul 2 ($x < 0$): ${x < 0}\ abs \leftarrow -x\ {abs = |x|}$ — corect, $|x| = -x$ când $x < 0$

2.4 Regula buclei (while)

Cea mai importantă și dificilă regulă:

while (B) { C }

$$\frac{{I \land B}\ C\ {I}}{{I}\ \textbf{while}\ B\ \textbf{do}\ C\ {I \land \lnot B}}$$

$I$ = invariantul buclei — o proprietate care:

1. E adevărată înainte de buclă
2. Rămâne adevărată după fiecare iterație
3. E adevărată (împreună cu $\lnot B$) după buclă

3. Invarianți de buclă — arta verificării

3.1 Ce face un invariant bun?

Un invariant trebuie să fie:

• Adevărat inițial — înainte de prima iterație
• Preservat de corpul buclei — dacă e adevărat înainte de o iterație, rămâne adevărat după
• Util — împreună cu condiția de ieșire, implică postcondiția

3.2 Exemplu clasic: suma primelor n numere

// { n >= 0 }
int i = 0;
int sum = 0;
// { invariant: sum == i*(i+1)/2 && i <= n }
while (i < n) {
    i = i + 1;
    sum = sum + i;
}
// { sum == n*(n+1)/2 }

Verificare pas cu pas:

3.3 Găsirea invariantului — nu e trivial

Pentru căutare binară:

// { arr e sortat && 0 <= low <= high+1 && high < len(arr) }
int binary_search(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    // invariant: target e în arr[low..high] DACĂ există
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
// { rezultat == indexul lui target SAU -1 dacă nu există }

Invariant: target poate exista doar în arr[low..high]. La început, acoperă tot array-ul. La final, dacă low > high, intervalul e gol ⇒ target nu există.

3.4 Tehnici practice pentru invarianți

1. Taie problema — lasă deoparte ce s-a rezolvat deja (ex: primele $i$ elemente sunt sortate)
2. Măsoară progresul — o cantitate care scade (variantul buclei)
3. Copiază postcondiția — înlocuiește constanta cu variabila buclei

4. Corectitudine parțială vs. totală

Corectitudine parțială

$${P}\ C\ {Q}$$

Dacă $P$ e adevărat și $C$ se termină, atunci $Q$ e adevărat.

Nu spune nimic despre terminare. E suficientă pentru programe care oricum se termină (ex: bucle cu număr fix de iterații).

Corectitudine totală

$$[P]\ C\ [Q]$$

Dacă $P$ e adevărat, atunci $C$ se termină și $Q$ e adevărat.

Pentru a demonstra corectitudinea totală, la fiecare buclă trebuie un variant — o expresie cu valori naturale strict descrescătoare la fiecare iterație.

Variant pentru bucla while:

$$\frac{{I \land B}\ C\ {I},\ {I \land B}\ variant\downarrow}{{I}\ \textbf{while}\ B\ \textbf{do}\ C\ {I \land \lnot B}}$$

Exemplu de variant:

// variant: n - i (strict descrescător, delimitat inferior de 0)
while (i < n) {
    i = i + 1;  // n - i scade
}

5. Separation Logic — extensia pentru pointeri

Logica Hoare clasică nu poate trata corect pointerii și heap-ul. Problemă: aliasing-ul.

*x = 5;  // Ce s-a întâmplat cu *y dacă x == y?

Separation Logic (Reynolds, 2002) introduce un nou operator:

Regula de asignare în Separation Logic:

$${x \mapsto -}\ *x = 5\ {x \mapsto 5}$$

Regula de frame:

$$\frac{{P}\ C\ {Q}}{{P * R}\ C\ {Q * R}}$$

$R$ (frame-ul) nu e modificat de $C$ — esențială pentru modularitate.

6. Instrumente practice bazate pe logica Hoare

6.1 Dafny

Dafny (Microsoft Research) înglobează logica Hoare direct în limbaj:

method Sum(n: nat) returns (s: nat)
    ensures s == n * (n + 1) / 2
{
    s := 0;
    var i := 0;
    while i < n
        invariant s == i * (i + 1) / 2
        invariant i <= n
    {
        i := i + 1;
        s := s + i;
    }
}

Dafny verifică automat:

• Invariantul e corect?
• Postcondiția e satisfăcută?
• Bucla se termină? (variant implicit: $n - i$)

6.2 Frama-C

Frama-C (CEA, Franța) verifică cod C cu adnotări ACSL (ANSI/ISO C Specification Language):

/*@ requires n >= 0;
    ensures \result == n*(n+1)/2;
*/
int sum(int n) {
    int s = 0;
    /*@ loop invariant s == i*(i+1)/2;
        loop invariant i <= n;
        loop variant n - i;
    */
    for (int i = 0; i < n; i++) {
        i++;
        s += i;
    }
    return s;
}

6.3 Comparație

7. Exemple complete

7.1 Factorial

// { n >= 0 }
int i = 1;
int fact = 1;
// { invariant: fact == i! && i <= n }
while (i < n) {
    i = i + 1;
    fact = fact * i;
}
// { fact == n! }

Demonstrație:

• Inițial: $1! = 1$, $1 \le n$ ✅
• Preservare: $fact' = fact \cdot (i+1) = i! \cdot (i+1) = (i+1)!$ ✅
• Final: $\lnot(i < n) \Rightarrow i = n \Rightarrow fact = n!$ ✅

7.2 Algoritmul lui Euclid (CMMDC)

// { a > 0, b > 0 }
int x = a, y = b;
// { invariant: cmmdc(x, y) == cmmdc(a, b) }
while (x != y) {
    if (x > y) {
        x = x - y;
    } else {
        y = y - x;
    }
}
// { x == cmmdc(a, b) }

**R:

Răspuns final:

Gândire: Am scris articolul, dar s-a tăiat la final. Treasure Completez ultima parte.

<｜｜DSML｜｜tool_calls> <｜｜DSML｜｜invoke name="replace_string_in_file"> <｜｜DSML｜｜parameter name="filePath" string="true">/home/iuri/Desktop/2/myapp/articles/logica-hoare.md