Programmeringsfilosofin

Logiskt tänkande === bra programvara

Programmering är den nya läskunnigheten. Men hur skriver vi bra program? Här är de återkommande frågorna vi behöver lösa:

• Hur kommer vi fram till algoritmiska lösningar på ett problem?
• Hur vet vi då att lösningen faktiskt fungerar?
• Även om vi är säkra på att det fungerar, hur säger vi att datorn ska köra den?

Roligt faktum - om du har svårt att slipa någon av dessa frågor gör du faktiskt filosofi.

För att se varför, låt oss undersöka några intressanta likheter mellan programmering och filosofiskt resonemang.

Den första principen: du måste tänka hårt.

Datorer gör inget smartare än vi kan - skillnaden är att de gör det med snabbare hastighet.

Men de kan inte lösa ett verkligt problem som "hur kommer jag till mitt kontor hemifrån?"

En effektiv metod kan (i princip) utföras av en människa utan hjälp av någon maskin förutom papper och penna. - The Church-Turing Thesis

Fördelarna med programmering ligger fortfarande i resonemanget. Det vill säga att översätta ett verkligt världsproblem till enkla instruktioner som en dator kan utföra.

Naturligtvis har olika programmeringsspråk olika nivåer av semantiska abstraktioner. Ett Python-program kan vara kortare än dess motsvarighet. Men det ändrar bara mängden översättningar. Vi kan inte bli av med översättningsarbetet. Men vi lämnar denna diskussion för senare.

En programmerares resonemangsflöde

Nu stirrar vi på någon problembeskrivning. Vi kan först leta efter småskaliga exempel på input-output för att förstå problemet:

Induktion. Vi behöver en algoritm som kan hantera sådana exempel. Nu gör du induktion: generaliserar principer från erfarenhet.

Avdrag. Hur vet vi om det fungerar för andra okända ingångar? Vi gör avdrag för att bevisa riktigheten i vår algoritm.

Ontologi . Vi måste behålla data i datorminnet. Målet är att göra dem effektiva för datorerna att bearbeta. I ord ord, vilken datastruktur kan bäst fånga det dynamiska flödet av min information?

Induktion igen . Sedan kommer det allra sista steget: felsökning. Vi framkallar den buggiga delen av programmet från att analysera de oväntade resultaten.

Ett exempel

Låt oss nu undersöka ovanstående process genom att följa detta verkliga exempel: hitta den kortaste vägen från topp A till topp E.

För småskaliga problem kan vi lösa dem med instinkter. Liksom, det är väldigt enkelt för oss att känna igen lösningen ACE bara genom att titta.

Men hur är det med mer komplexa topologier? Vad sägs om olika kantvikter?

Vi behöver hjälp från datorer. Ändå är det inte rakt fram att berätta för en dator vad man ska göra. Det finns ett gap mellan hur människor tänker och hur en dator fungerar.

Processen

1. Allmänna principer från erfarenhet: algoritmer

För att berätta för en dator vad man ska göra måste vi först komma med en algoritmisk procedur.

Giriga strategier är ett naturligt sätt att gå vidare. Det vill säga att börja från källpunkten A och gå hela vägen längs den kända kortaste vägen. Fortsätt utforska nya hörnpunkter tills vi når destination E. Och den här metoden uppfyller verkligen vårt exempel.

Intuitionen är att längs den kortaste vägen till en destination besöks varje mellanliggande nod också på den kortaste vägen. (Naturligtvis antar denna intuition att alla kanter har positiva vikter. Detta kanske inte stämmer, beroende på applikationer. Vi kommer att diskutera detta i detalj senare).

Så här är det algoritmiska förfarandet:

1. Någon inställning: (1) bokför de hörn vi har besökt: en uppsättning ( visited), (2) kom ihåg de kända kortaste avstånden till varje toppunkt som endast använder upptäckta hörn : en annan uppsättning distance(u). Varje vertex avstånd är initialt oändligt, förutom att källpunkten är 0.
2. Nu börjar vi utforska: först besöker vi toppunktet som har den kända kortaste vägen hittills, säg att den är u. (Ursprungligen skulle det vara källpunkten).
3. När uvi står vid vertex tittar vi runt de utgående kanterna. Varje kant, säg (u,v), ger oss en väg till vertex vsom använder vertex usom det sista men bara ett steg. Om någon av dem verkligen är en kortare väg till v, eller den första vägen vi hittade v, hurra kan vi uppdatera vår uppsättning kortaste vägar nu. I annat fall ignorera och fortsätt.
4. Vi är färdiga med vertex u, så vi lägger till det i vår visiteduppsättning.
5. Gå tillbaka till steg 2, fortsätt utforska tills vi har besökt alla hörnpunkter.

distancekan nu berätta de kortaste avstånden globalt, eftersom den används för att hålla de kortaste avstånden med endast besökta noder. Och alla hörn besöks när algoritmen är klar.

Vi har just uppfunnit Dijkstras algoritm. Naturligtvis finns det många andra algoritmer för att hitta den kortaste vägen. Men poängen är att vi behöver en algoritmisk procedur för att lösa problemet.

2. Validera allmänna principer genom avdrag

Hur ser vi till att algoritmens principer är korrekta? Vi kan antingen öka vårt förtroende genom att testa principen mot fler ingångsexempel, eller mer effektivt kan vi hitta ett strikt matematiskt bevis.

Liksom ett a priori-förslag i filosofin är korrektheten hos en algoritm oberoende av dess exekvering. Med andra ord kan testning inte garantera att algoritmer är korrekta. Vi måste bevisa det.

Här är det grundläggande flödet av beviset:

1. För alla besökta hörn hittar vi de kortaste vägarna.

2. Målet besöks.

3. Därför hittar vi den kortaste vägen till destinationen.

Verkar de inte något bekanta? Så här:

1. Alla män är dödliga.

2. Socrate är en man.

3. Därför är Socrate dödlig.

I själva verket är detta Syllogism, en klassisk form av deduktivt resonemang. Det här är ganska mycket vad logiker gör.

Ett annat intressant historiskt faktum: det formella konceptet för beräkning kom först upp av logiker på 1930-talet. De behövde veta om vissa logiska problem egentligen är lösbara alls (så att de kunde undvika att slösa bort sin tid på att lösa något olösligt). För att svara på det kommer de med tanken på beräkningsbarhet.

Senare 1936 utvecklade Alonzo Church och Alan Turing den formella definitionen av Computability, oberoende, samtidigt. Denna uppsats ger en historisk genomgång av beräkningen.

Slutsatsens riktighet beror på de två första förutsättningarna. I vårt bevis är den andra förutsättningen trivial, eftersom vår algoritm bokstavligen besöker alla noder. Ändå bevisar den första förutsättningen, att vi hittar den kortaste vägen när vi besöker en nod, lite arbete.

Matematisk induktion kan hjälpa. Det är faktiskt en av de mest användbara teknikerna för att bevisa riktigheten hos många andra algoritmer.

Det allmänna flödet går enligt följande. För det första, om en algoritm fungerar på input 0, och för det andra, om det faktum att den fungerar på input ninnebär att den fungerar på input n+1 också, så fungerar den för alla input större eller lika med 0. Vid denna tidpunkt kan du garantera korrektheten i din algoritm.

För enkelhetens skull hänvisar du till denna föreläsningsanteckning för fullständig bevis på denna sökvägalgoritm.

Observera att vi inte ska förväxla matematisk induktion och filosofisk induktion. Enligt den filosofiska definitionen är matematisk induktion en deduktiv resonemangsprocess, eftersom dess korrekthet finns i sig själv utan några yttre observationer.

Lektionen är: när vi kommer med en algoritm ska den kunna hantera alla möjliga exekveringsfall.

I praktiken är det kanske inte den mest effektiva strategin att gå igenom det stränga matematiska beviset. Men åtminstone vill vi överväga så många exekveringsärenden som möjligt, särskilt de kontroversiella. Denna övning skulle förbättra robustheten i vår kod.

Du kanske har lagt märke till att det i vårt exempel på sökvägsalgoritm inte fungerar om kantvikten är negativ. Du hittar orsaken i denna föreläsningsanteckning. För att hantera ett diagram med negativ vikt kan du använda Bellman-Ford-algoritmen.

3. Ontologiproblemet: datastruktur

Hittills övertygade vi oss själva om att vi har en korrekt algoritm. Men det här är bara halva striden.

Nästa fråga är, hur matar vi informationen till datorer? Människor gillar visualiserad information, som grafer eller histogram. Men dagens datorer hanterar bara binära bitar.

Vi måste komma med en datastruktur som innehåller viktig information. Och det borde vara effektivt för ett program att bearbeta samtidigt.

Låt oss fortsätta på vår väg att hitta exempel. En sökväg är en ordnad lista. Men det är irriterande att hantera, jämfört med ett heltal. Observera att vi i vår algoritm måste hitta den kortaste vägen från vår uppsättning upptäckta vägar. Och sedan iterera hela vägen till slutet. Det verkar som att vi måste ägna en matris eller ett minne för att lagra varje sökväg.

Kan vi göra bättre? Observera att i en giltig sökväg måste på varandra följande utseenden av element motsvara en kant i diagrammet. Men vi har redan kantinformation och de är desamma för alla vägar. Varför kan vi inte bli av med denna överflödiga information?

Vi kan bli av med listan. Det visar sig att för att samla den kortaste vägen är det mellanliggande steget att bestämma vad som är nästa hopp du behöver gå. Allt vi behöver för att hämta den kortaste vägen från källa A till vilken målnod som helst är bara själva diagrammet och det kortaste avståndet från A till varje nod.

En visuell representation finns i bilden ovan. Denna representation är minneseffektiv. Det är också mer effektivt för programmet att bearbeta.

Så här konstruerar den den kortaste vägen med endast avståndsvektorn. Börja från destinationspunkten och en tom sökväg. Slå upp mellanhörn genom inkommande kanter. Välj den med det lägsta värdet i distance. Lägg till den i sökvägens huvud. Upprepa tills vi når källan. Detta trick har faktiskt en formell notation, kallad back-tracking.

Filosofer söker den eviga sanningen. Och programmerare vill ta reda på den exakta datastrukturen som bäst fångar informationens dynamik. Som du ser i sökvägsexemplet är allt som behövs för att ge en kortaste väg bara en vektor som berättar för dig de kortaste avstånden till varje toppunkt. Detta gäller för alla diagram, oavsett antal hörn eller kanter.

4. Ett efterföljande förslag: felsökning

De flesta programmerare har gått igenom detta resonemang många gånger. Jag slår vad om att detta är en av de svåraste och mest tidskrävande delarna av någon programmeringsuppgift.

Till exempel orsakas segmenteringsfel i C-program ofta av nullpekarehänvisningar. Jag lärde mig detta efter att hantera massor av C / C ++ segmenteringsfel. Naturligtvis finns det mer subtila fall som rör personliga programmeringsvanor.

Följande exempel är ett syntaxfel som görs av en programmerare. Om-villkoret borde ha varit is_float==1, men programmeraren misstog den logiska lika operatören ==som en utvärderingsoperator =. Detta kommer fortfarande att passera kompilatorns kontroll, eftersom antingen är korrekt syntax.

if (is_float = 1) { // do something}

Detta är en induktiv resonemangsprocess. Din felsökningsdiagnos är endast vettig om du har observerat tillräckligt många programkörningar.

Här kommer värdet av övning in. Oavsett vilken typ av tekniker du lär dig, måste du samla in tillräckligt med praktiska data. Annars skulle du inte ha tillräckligt med erfarenhet för att genomföra induktion.

Du bör hålla ett öga på de återkommande mönstren i dina buggykoder. När du hittar ett fel räcker det inte med att åtgärda det. Du behöver lite extra orsak-effekt-analys på din egen programmeringsmetod. Fråga dig själv: är den här delen av mina programmeringsvanor särskilt sårbar för den här typen av fel?

Så varför spelar det någon roll?

Programmering handlar inte bara om att skriva kod, det är ett systematiskt sätt att resonera. Eftersom kod eller instruktioner är bara ett sätt att nå ett mål. Med utvecklingen av programmets syntesteknik kanske du inte ens bry dig om att skriva kod och felsöka dig själv. Allt som är viktigt är om du kan berätta för datorn vad du ska göra.

Som det första steget mot att förbättra dina programmeringsfärdigheter avslöjar den här artikeln det underliggande resonemangsmönstret som vi kanske inte ens känner igen när vi programmerade. De flesta av oss litar på undermedvetna, automatisk reflektion för att slutföra de flesta av våra dagliga uppgifter. Men var kommer förbättringar ifrån? Det kommer först från att märka några felaktigheter eller misstag vi gjorde i vårt resonemang.

För praktiska råd rekommenderar jag den här artikeln om hur man tänker som en programmerare, och den här boken om samma ämne men med mer detaljer.

Referenser

• Beräkning, filosofiska frågor om. Matthias Scheutz.
• The Church-Turing-avhandlingen.
• Tänk som en programmerare: En introduktion till kreativ problemlösning. V. Anton Spraul.