23 sep. 2025·8 min
Tony Hoares idéer om korrekthet: Från logik till säker kod
Lär dig hur Tony Hoares arbete med Hoare-logik, Quicksort och säkerhetstänk formade praktiska tekniker för att skriva och granska korrekt programvara.
Lär dig hur Tony Hoares arbete med Hoare-logik, Quicksort och säkerhetstänk formade praktiska tekniker för att skriva och granska korrekt programvara.
När folk säger att ett program är “korrekt” menar de ofta: “Jag körde det några gånger och resultatet såg rätt ut.” Det är en användbar signal—men det är inte korrekthet. Enkelt sagt betyder korrekthet att programmet uppfyller sin specifikation: för varje tillåten indata producerar det det kravställda resultatet och respekterar eventuella regler om tillståndsändringar, tid och felhantering.
Problemet är att “uppfyller sin spec” är svårare än det låter.
För det första är specifikationer ofta oklara. Ett produktkrav kan säga “sortera listan”, men betyder det stabil sortering? Vad händer med dubbletter, tomma listor eller icke-numeriska element? Om specen inte säger, kommer olika personer anta olika saker.
För det andra är kantfall inte sällsynta—de testas bara mer sällan. Null-värden, overflow, off-by-one-gränser, ovanliga användarsekvenser och oväntade externa fel kan förvandla “det verkar fungera” till “det gick sönder i produktion.”
För det tredje ändras krav. Ett program kan vara korrekt i förhållande till gårdagens spec och felaktigt i förhållande till dagens.
Tony Hoares stora bidrag var inte påståendet att vi alltid ska bevisa allt. Det var idén att vi kan vara mer precisa om vad koden ska göra—och resonera om det på ett disciplinerad sätt.
I det här inlägget följer vi tre sammankopplade trådar:
De flesta team skriver inte fullständiga formella bevis. Men även partiellt, "bevisliknande" tänkande kan göra buggar lättare att upptäcka, förbättra granskningar och göra beteendet tydligare innan koden skickas.
Tony Hoare är en av de där sällsynta datavetarna vars arbete inte stannade i artiklar eller klassrum. Han rörde sig mellan akademi och industri, och brydde sig om en praktisk fråga som varje team fortfarande möter: hur vet vi att ett program gör vad vi tror att det gör—särskilt när insatserna är höga?
Denna artikel fokuserar på några Hoare-idéer som dyker upp i riktiga kodbaser:
{P} C {Q}.Du kommer inte hitta djup matematisk formalism här, och vi försöker inte med ett komplett maskinkontrollerat bevis av Quicksort. Målet är att hålla koncepten tillgängliga: tillräckligt med struktur för att göra ditt resonemang tydligare utan att förvandla kodgranskningen till ett doktorsseminarium.
Hoares idéer översätts till vanliga beslut: vilka antaganden en funktion förlitar sig på, vad den garanterar till anroparen, vad som måste vara sant mitt i en loop och hur man ser “nästan korrekt” ändringar i granskningar. Även när du aldrig skriver {P} C {Q} uttryckt, förbättrar tänkandet i den formen API:er, tester och diskussionernas kvalitet kring knepig kod.
Hoares syn är striktare än “det klarade några exempel”: korrekthet handlar om att uppfylla ett överenskommet löfte, inte att se rätt ut i ett litet urval.
Buggar uppstår ofta när team hoppar över mittensteget: de går direkt från krav till kod och lämnar löftet otydligt.
Två olika påståenden blandas ofta ihop:
För verkliga system kan “aldrig bli klar” vara lika skadligt som “blir klar med fel svar”.
Korrekthetspåståenden är aldrig universella; de förlitar sig på antaganden om:
Att vara explicit om antaganden förvandlar “fungerar på min maskin” till något andra kan resonera om.
Tänk på en funktion sortedCopy(xs).
En användbar spec kan vara: “Returnerar en ny lista ys sådan att (1) ys är sorterad stigande, och (2) ys innehåller exakt samma element som xs (samma förekomster), och (3) xs är oförändrad.”
Nu betyder “korrekt” att koden uppfyller dessa tre punkter under angivna antaganden—inte bara att output såg sorterad ut i ett snabbt test.
Hoare-logik är ett sätt att prata om kod med samma tydlighet som ett kontrakt: om du börjar i ett tillstånd som uppfyller vissa antaganden, och du kör detta kodstycke, kommer du att hamna i ett tillstånd som uppfyller vissa garantier.
Kärnnotationen är Hoare-trippeln:
{precondition} program {postcondition}
En precondition anger vad som måste vara sant innan programfragmentet körs. Det handlar inte om vad du hoppas är sant; det är vad koden behöver vara sant.
Exempel: anta en funktion som beräknar medelvärdet av två tal utan overflow-kontroller.
a + b ryms i heltalstypenavg = (a + b) / 2avg är det matematiska medelvärdet av a och bOm precondition inte håller (overflow är möjlig) gäller inte längre postcondition- löftet. Trippeln tvingar dig att säga det högt.
En postcondition anger vad som kommer att vara sant efter att koden körs—förutsatt att precondition var uppfylld. Bra postconditions är konkreta och kontrollerbara. Istället för “resultatet är giltigt”, säg vad “giltigt” betyder: sorterat, icke-negativt, inom gränser, oförändrat utom för specifika fält, osv.
Hoare-logik skalar från små satser till flerstegs kod:
x = x + 1, vilka fakta om x är nu sanna?Poängen är inte att strö krullparenteser överallt. Det är att göra avsikten läsbar: tydliga antaganden, tydliga utfall och färre “det verkar fungera”-samtal i granskningar.
En loopinvariant är ett påstående som är sant innan loopen startar, förblir sant efter varje iteration och fortfarande är sant när loopen avslutas. Det är en enkel idé med stor utdelning: den ersätter “det verkar fungera” med ett påstående du faktiskt kan kontrollera i varje steg.
Utan en invariant låter en granskning ofta: “Vi itererar över listan och fixar gradvis saker.” En invariant tvingar precision: vad är redan korrekt just nu, även om loopen inte är klar? När du kan säga det klart blir off-by-one-fel och saknade fall lättare att upptäcka, eftersom de visar sig som tillfällen där invariant skulle brytas.
Det mesta vardagskod kan använda några pålitliga mallar.
1) Gränser / index-säkerhet
Håll index i ett säkert intervall.
0 \u003c= i \u003c= nlow \u003c= left \u003c= right \u003c= highDenna typ av invariant är bra för att förebygga utanför-gräns-åtkomst och göra arrayresonemang konkreta.
2) Bearbetade vs obearbetade element
Dela upp dina data i ett "klart" område och ett "inte ännu" område.
a[0..i) har granskats.”result uppfyller filterpredikatet.”Detta förvandlar vag framdrift till ett klart kontrakt om vad “bearbetat” betyder.
3) Sorterat prefix (eller partitionerat prefix)
Vanligt i sortering, sammanslagning och partitionering.
a[0..i) är sorterat.”a[0..i) är \u003c= pivot, och alla element i a[j..n) är \u003e= pivot.”Även om hela arrayen inte är sorterad än, har du spikat fast vad som är.
Korrekthet handlar inte bara om att vara rätt; loopen måste också avslutas. Ett enkelt sätt att argumentera för det är att namnge ett mått (ofta kallat variant) som minskar varje iteration och inte kan minska för evigt.
Exempel:
n - i krymper med 1 varje gång.”Om du inte kan hitta ett krympande mått kan du ha upptäckt en verklig risk: en oändlig loop för vissa indata.
Quicksort har ett enkelt löfte: givet ett segment av en array, ordna elementen så att de hamnar i icke-avtagande ordning, utan att tappa eller hitta på värden. Algoritmens högnivåform är enkel att sammanfatta:
Det är ett utmärkt undervisningsexempel för korrekthet eftersom det är tillräckligt litet för att hålla i huvudet men rikt nog att visa var informellt tänkande fallerar. En Quicksort som “verkar fungera” på några slumpmässiga tester kan ändå vara felaktig på sätt som bara syns för vissa indata eller kantvillkor.
Få problem orsakar majoriteten av felen:
För att argumentera för korrekthet i Hoare-stil delar man ofta upp beviset i två delar:
Denna separation håller resonemanget hanterbart: få partition rätt, bygg sedan sorteringskorekthet ovanpå det.
Quicksorts hastighet beror på en förrädiskt liten rutin: partition. Om partition är ens lite fel kan Quicksort fel-sorta, loopa för evigt eller krascha på kantfall.
Vi använder den klassiska Hoare-partitionschemat (två pekare som rör sig inåt).
Input: en arraydel A[lo..hi] och ett valt pivot-värde (ofta A[lo]).
Output: ett index p sådant att:
A[lo..p] är \u003c= pivotA[p+1..hi] är \u003e= pivotNotera vad som inte lovas: pivoten behöver inte hamna i position p, och element lika med pivot kan förekomma på båda sidor. Det är okej—Quicksort behöver bara en korrekt uppdelning.
När algoritmen avancerar två index—i från vänster, j från höger—fokuserar gott resonemang på vad som redan är “låst”. En praktisk mängd invariants är:
A[lo..i-1] är \u003c= pivot (vänstersidan är ren)A[j+1..hi] är \u003e= pivot (högersidan är ren)A[i..j] är oklassificerat (återstår att kontrolleras)När vi hittar A[i] \u003e= pivot och A[j] \u003c= pivot, bevarar en swap dessa invariants och krymper det oklassificerade mittpartiet.
i rör sig hela vägen åt höger; partition måste ändå terminera och returnera ett meningsfullt p.j rör sig åt vänster; samma terminationsbekymmer.\u003c vs \u003c=) kan pekare stanna. Hoares schema förlitar sig på en konsekvent regel så att framsteg sker.Olika partitionscheman finns (Lomuto, Hoare, trevägs). Nyckeln är att välja ett, ange dess kontrakt och granska koden konsekvent mot just det kontraktet.
Rekursion blir lättast att lita på när du tydligt kan svara på två frågor: när slutar det? och varför är varje steg giltigt? Hoare-stil tänkande hjälper eftersom det tvingar dig att ange vad som måste vara sant före ett anrop och vad som kommer att vara sant efter att det returnerar.
En rekursiv funktion behöver minst ett basfall där den inte gör fler rekursiva anrop och ändå uppfyller lovat resultat.
För sortering är ett typiskt basfall “arrayer av längd 0 eller 1 är redan sorterade.” Här bör “sorterad” vara explicit: för en ordningsrelation ≤ är utdata sorterad om för varje index i \u003c j gäller a[i] ≤ a[j]. (Huruvida lika element behåller sin ursprungliga ordning kallas stabilitet; Quicksort är normalt inte stabil om du inte designar för det.)
Varje rekursivt steg ska anropa sig själv på en strikt mindre indata. Denna “krympning” är ditt termineringsargument: om storleken minskar och inte kan bli mindre än 0 kan du inte recursa för evigt.
Krympning spelar också roll för stack-säkerhet. Även korrekt kod kan krascha om rekursionsdjupet blir för stort. I Quicksort kan obalanserade partitioner ge djupt rekursionsdjup. Det är både ett bevis-på-terminering och en praktisk påminnelse att överväga värsta-fallets djup.
Quicksorts värsta fall kan degraderas till O(n²) när partitionerna är mycket obalanserade, men det är en prestandafråga—inte en korrekthetsbrist. Målet här är: under antagandet att partitionsteg bevarar element och delar dem enligt pivot, innebär rekursiv sortering av mindre delar att hela intervallet blir sorterat enligt definitionen av sorteradhet.
Testning och bevislikt resonerande siktar på samma mål—förtroende—men når dit på olika sätt.
Tester är utmärkta för att fånga konkreta misstag: ett off-by-one, ett saknat kantfall, en regression. Men en testsvit kan bara sampla indatarummet. Även “100% täckning” betyder inte “alla beteenden kontrollerade”; det betyder mest “alla rader exekverades.”
Bevislikt tänkande (särskilt Hoare-stil) utgår från en specifikation och frågar: om dessa preconditions håller, etablerar koden alltid postconditions? När du gör det väl hittar du inte bara en bugg—du kan ofta utesluta en hel kategori av buggar (som “arrayåtkomst håller sig inom gränser” eller “loopen bryter aldrig partitionsegenskapen”).
En tydlig spec är en testgenerator.
Om din postcondition säger “utdata är sorterad och är en permutation av indata” får du automatiskt testidéer:
Specen berättar vad “korrekt” betyder, och testerna kontrollerar att verkligheten matchar.
Property-baserad testning ligger mellan bevis och exempel. Istället för att handplocka några fall anger du egenskaper och låter ett verktyg generera många indata.
För sortering räcker två enkla egenskaper långt:
Dessa egenskaper är i huvudsak postconditions skrivna som exekverbara kontroller.
En lättviktig rutin som skalar:
Om du vill institutionaliserar detta, lägg "spec + resonemangsanteckningar + tester" i din PR-mall eller kodgransknings-checklista (se även /blog/code-review-checklist).
Om du använder ett vibe-coding-arbetsflöde (genererar kod från en chattbaserad gränssnitt) gäller samma disciplin—kanske ännu mer. I Koder.ai, till exempel, kan du börja i Planning Mode för att spika preconditions/postconditions innan någon kod genereras, och sedan iterera med snapshots och rollback medan du lägger till property-baserade tester. Verktyget snabbar upp implementationen, men specen är fortfarande det som hindrar att “snabbt” blir “skört.”
Korrekthet handlar inte bara om “programmet returnerar rätt värde.” Säkerhetstänk ställer en annan fråga: vilka utfall är oacceptabla, och hur förhindrar vi dem—även när koden är stressad, missbrukad eller delvis felande? I praktiken är säkerhet korrekthet med ett prioritetsystem: vissa fel är bara jobbiga, andra kan orsaka ekonomisk skada, intrång i integritet eller fysisk skada.
En bugg är ett fel i kod eller design. En risk (hazard) är en situation som kan leda till ett oacceptabelt utfall. En bug kan vara harmlös i ett sammanhang och farlig i ett annat.
Exempel: ett off-by-one-fel i ett bildgalleri kan felmärka en bild; samma fel i en doseringskalkylator kan skada en patient. Säkerhetstänk tvingar dig att koppla kodbeteende till konsekvenser, inte bara till “spec-uppfyllelse.”
Du behöver inte tunga formella metoder för att få omedelbar säkerhetsnytta. Team kan införa små, upprepbara principer:
Dessa tekniker passar naturligt ihop med Hoare-stil resonemang: gör preconditions explicita (vilka indatan är acceptabla) och säkerställ att postconditions inkluderar säkerhetsegenskaper (vad som aldrig får hända).
Säkerhetsorienterade kontroller kostar något—CPU-tid, komplexitet eller ibland falska avslag.
Säkerhetstänk handlar mindre om att bevisa elegans och mer om att förhindra de felmoder du inte har råd med.
Kodgranskningar är där korrekthetstänk ger snabbast utdelning, eftersom du kan upptäcka saknade antaganden långt innan buggar når produktion. Hoares kärnidé—att ange vad som måste vara sant före och vad som kommer att vara sant efter—översätts lätt till granskningsfrågor.
När du läser en ändring, försök formulera varje nyckelfunktion som ett litet löfte:
En enkel granskarvana: om du inte kan säga pre/post-conditions i en mening är koden troligen i behov av tydligare struktur.
För riskfyllda eller centrala funktioner, lägg till en liten kontraktskommentar ovanför signaturen. Håll den konkret: indatan, utdata, sidoeffekter och fel.
def withdraw(account, amount):
"""Contract:
Pre: amount is an integer \u003e 0; account is active.
Post (success): returns new_balance; account.balance decreased by amount.
Post (failure): raises InsufficientFunds; account.balance unchanged.
"""
...
Dessa kommentarer är inga formella bevis, men de ger granskare något precist att kontrollera mot.
Var extra tydlig när du granskar kod som hanterar:
Om ändringen rör något av detta, fråga: “Vilka är preconditions och var upprätthålls de?” och “Vilka garantier ger vi även vid fel?”
Formellt resonemang behöver inte innebära att hela kodbasen blir en matematisk uppsats. Målet är att lägga extra säkerhet där det lönar sig: platser där “ser bra ut i tester” inte räcker.
De passar bra när du har en liten, kritisk modul som allt annat beror på (auth, betalningsregler, behörigheter, säkerhetslås), eller en knepig algoritm där off-by-one-fel gömmer sig länge (parsning, schemaläggare, caching/eviction, partition-typ kod, gränstunga datatransformationer).
En användbar regel: om en bugg kan orsaka verklig skada, stora ekonomiska förluster, eller tyst datakorruption, vill du ha mer än vanlig granskning + tester.
Du kan välja från “lättviktigt” till “tungt”, och ofta ger kombinationer bäst resultat:
Avgör graden av formalitet genom att väga:
I praktiken kan du betrakta “formalitet” som något du lägger till stegvis: börja med explicita kontrakt och invariants, och låt automation hålla dig uppriktig. För team som bygger snabbt på Koder.ai—där du kan generera en React-front, en Go-backend och Postgres-schema i en tajt loop—gör snapshots/rollback och källkodsexport det lättare att iterera snabbt samtidigt som kontrakt upprätthålls via tester och statisk analys i CI.
Använd detta som en snabb "bör vi formalisera mer?"-grind i planering eller kodgranskning:
Ytterligare läsning: design-by-contract, property-baserad testning, model checking för tillståndsmaskiner, statiska analyser för ditt språk, och introduktionsmaterial om bevisassistenter och formell specifikation.
Korrekthet betyder att programmet uppfyller en överenskommen specifikation: för varje tillåten indata och relevant systemtillstånd ger det de förväntade utsignalerna och sidoeffekterna (och hanterar fel som utlovat). "Det verkar fungera" betyder oftast att du bara testade ett fåtal exempel, inte hela indatautrymmet eller de knepiga gränsfallen.
Krav är affärsbehovet på vanlig engelska (vad intressenter vill ha). En specifikation är det precisa, kontrollerbara löftet (vad funktionen måste göra). Implementation är koden (hur det görs). Buggar uppstår ofta när team hoppar direkt från krav till kod utan att skriva ner det kontrollerbara löftet.
Partial korrekthet: om koden returnerar så är resultatet korrekt. Total korrekthet: koden returnerar och resultatet är korrekt—så terminering ingår i påståendet.
I praktiken är total korrekthet viktig när "hänga sig" är ett synligt fel, ett resursläckage eller en säkerhetsrisk.
En Hoare-trippel {P} C {Q} kan läsas som ett kontrakt:
P (precondition): vad som måste vara sant innan C körsPreconditions är vad koden behöver (t.ex. "index är i spannet", "element är jämförbara", "lås hålls"). Om en precondition kan brytas av anroparen bör du antingen:
Annars blir dina postconditions önsketänkande.
En loopinvariant är ett påstående som är sant innan loopen startar, förblir sant efter varje iteration och fortfarande är sant när loopen slutar. Användbara mallar inkluderar:
0 \u003c= i \u003c= n)Om du inte kan formulera en invariant är det ett tecken på att loopen gör för mycket eller att gränserna är oklara.
Du namnger vanligtvis ett mått (variant) som minskar varje iteration och inte kan minska för evigt, till exempel:
n - i minskar med 1Om du inte hittar ett avtagande mått kan det finnas en verklig risk för icke-terminering (särskilt med dubbletter eller stillastående pekare).
I Quicksort beror allt på partitionrutinen. Om partition är lite fel kan du få:
Därför hjälper det att tydligt ange partitionskontraktet: vad som ska gälla till vänster, till höger, och att elementen bara omarrangeras (permutation).
Dubbletter och hur man hanterar "lika pivot" är vanliga felpunkter. Praktiska regler:
i/j)Om dubbletter är vanliga kan trevägspartitionering minska både buggar och rekursionsdjup.
Tester hittar konkreta misstag; resonemang kan utesluta hela kategorier av fel (gränssäkerhet, bevarande av invariants, terminering). Ett praktiskt hybridflöde är:
För sortering är två högvärda egenskaper:
C: kodstycketQ (postcondition): vad som kommer att vara sant efter att C avslutats, under antagandet att P höllDu behöver inte skriva notationen i koden—att använda strukturen i recensioner ("antaganden in, garantier ut") är den praktiska vinsten.