#programmeringsteori

[kqrx]

[Java] is C with range checking and garbage collection

John Carmack, (Twitter, 2012-04-30)

[kqrx]

Gratislunchen är över; parallellismen gör entré (del 3)

Så två processer kan inte försöka använda samma variabel samtidigt. Det ger problem. En naiv lösning är ju att bara förhindra dem från att använda samma variabel samtidigt. Det brukar kallas lås eller mutexes (mutex står för mutual exclusion och betyder att flera saker inte får komma åt en variabel samtidigt.)

Process 1 sätter ett lås på variabeln den använder, gör sitt med den, och låser sen upp låset. Process 2 får då sätta sitt lås på den. Det är faktiskt så här man oftast gör i dag när man gör något parallellt. Man låser variabler eller delar av minnet. Tyvärr är det inte utan problem.

Tänk dig att Erika och Jonas går på dagis båda två. Det finns två lådor med lego som man behöver för att bygga en tuff borg. Både Erika och Jonas vill bygga den där borgen, men de pratar inte med varandra så de vet inte om att den andra vill det.

Erika går fram till en av lådorna och sätter sitt lås på den för att han kommer att använda den. Erika går vidare till den andra lådan och upptäcker att Jonas har satt sitt lås på den. Erika ställer dig där och väntar på att Jonas ska bli klar med lådan och låsa upp sitt lås, men det händer aldrig. Erika står där natt efter natt och dag efter dag men aldrig låser Jonas upp sin låda.

Har du listat ut vad som har hänt? Jonas ville också bygga den tuffa borgen, så han låste lådan som var närmast honom och gick till lådan som Erika just hade låst. Där väntar Jonas på att Erika ska låsa upp sin låda, men det händer aldrig. Båda väntar på varandras lås och det här kallas för en deadlock.

Det finns naturligtvis strategier för att undvika deadlocks, som till exempel att alla måste låsa lådorna i samma ordning, men i någorlunda komplicerade system så kommer deadlocks uppstå ändå.

Deadlocks är inte heller det enda problemet med lås. Lås kan vara ineffektiva också. Tänk dig om en process behöver 57 variabler för någon lång uträkning, medan en annan process bara behöver en av de där variablerna för att skriva ut något. Om den långa processen hinner låsa variablerna först måste den lilla, snabba vänta länge på att få göra den där viktiga utskriften som den skulle kunna göra bara den fick.

Då kan man börja prata om lås som hindrar andra från att skriva, men de fortfarande får läsa. I vissa fall fungerar det, i andra är det väldigt dumt; tänk dig ett kärnkraftverk eller sjukhus där programmet inte får läsa en variabel som är halvskriven.

Lås är långt ifrån perfekta. Faktum är att de som arbetar med dem brukar avsky dem, för de är svåra att debugga, de är instabila, de ger jätteful kod och så vidare. De är visserligen lite bättre än att inte ha något skydd alls, men de är väldigt omständliga.

[kqrx]

Gratislunchen är över; parallellismen gör entré (del 2)

Så nu när gratislunchen är över måste vi göra program snabbare på något annat sätt. Parallellism betyder att göra flera saker samtidigt. Med flera kärnor kan man göra flera saker samtidigt. Ändå verkar det som att de allra flesta program som skrivs i dag bara kör på en kärna. De är skrivna för att bara göra en sak i taget.

Trots allt är det så vi är vana vid att programmera saker. Vi är vana att skriva kod på formen

gör det här

sen gör det här

sen gör det här

om det här är på något visst sätt

gör det här

annars

gör det här

och det här

och det här istället

när du är klar med det, gör det här

och gör sen det här

och så vidare. Det här är en lista på instruktioner som måste göras uppifrån och ned, annars blir det problem. Det går inte att köra något samtidigt där inte.

Den största boven här är variabler. Tänk dig följande kodsnutt i assembler.

li $t0, 0x03fb6c78 # stoppa in adressen 0x03fb6c78 till t0 lw $t1, 0($t0) # ladda in innehållet i adressen till t1 addi $t1, $t1, 1 # lägg till 1 på värdet i t1 sw $t1 0($t0) # stoppa tillbaks nya t1 till gamla adressen

Först hämtar man innehållet någonstans i minnet, sen ökar man på det med ett, och sen stoppar man tillbaks det. Det där är vad som i C skrivs

variabel++;

Ser du hur det är komponerat av fyra olika instruktioner egentligen? Där kommer problemet in. Tänk om det är två processer som körs på olika kärnor som ska göra det där. Om variabeln börjar med värdet fyra kan man vänta sig att efter att två processer har ökat den så blir värdet sex. Inte om de försöker öka samtidigt.

Process 1 hämtar variabel som har värde fyra

Process 1 lägger till 1 till variabel, som får värde fem lokalt i process 1

Process 2 hämtar variabel som har värde fyra i minnet fortfarande

Process 1 skriver tillbaks sin lokala variabel med värde fem till minnet

Process 2 lägger till 1 till sin variabel, som får värde fem lokalt i process 2

Process 2 skriver tillbaks sin lokala variabel med värde fem till minnet.

I slutändan har variabeln värdet fem i minnet, trots att vi väntade oss sex. Kaos! Det här är problemet med flera processer som kör samtidigt. De kan förstöra för varandra när de delar på minne och sånt.

Du kan säkert redan tänka dig en lösning, eller hur? Du kan säkert föreställa dig att "Men om process 2 inte får röra minnet medan process 1 använder det?" Du har helt rätt! Det kommer i nästa del.

[kqrx]

Gratislunchen är över; parallellismen gör entré (del 1)

Ända sen datorer började bli användbara på 50- och 60-talet har de alltid blivit snabbare, snabbare och åter snabbare. En dator i början av 80-talet var lite grovt 50 gånger snabbare än en i början av sjuttitalet. På ett år hann datorerna bli lite grovt 1.6 gånger snabbare.

Det här är vad som kallas för en gratis lunch. När man på 90-talet programmerade något, så kunde man medvetet göra programmet lite långsamt på dagens datorer, för när programmet släpps ett år senare, kommer det gå ungefär 1.6 gånger snabbare. Utan att programmeraren behöver göra någonting. Det sparar massa utvecklingstid. Programmeraren behöver inte bry sig om ifall programmet är lite långsamt, för hårdvaran kommer att komma ikapp.

Men något har hänt. Vi nådde området omkring 4 GHz vid 2005 eller 2006. Vi borde ju nu i 2012 ha allra minst 50 GHz. Varför har vi inte det? Det har hänt något. Det har hänt något stort.

När vi slog i 4 GHz-gränsen så blev värmen för mycket. Vi kan inte längre ha snabbare processorer, för de blir alldeles för varma. De som överklockar en bra bit över 4 GHz skaffar vattenkylning. Det räcker inte med luft då längre. Industrin tänker inte tvinga alla att vattenkyla sina datorer. Industrin har gett upp jakten på fler GHz.

Så vad kan man göra om man inte har snabbare processorer? Var tar utvecklingen vägen? Vi får fler kärnor istället. Nu har antalet kärnor börjat växa lika snabbt som processorhastigheten gjorde förut.

Nu, år 2012, tillverkas det väldigt få datorer eller datorliknande enheter med bara en kärna. Samtliga nya, häftiga mobiltelefoner har flera kärnor (oftast fyra.) Så vitt jag vet har alla spelkonsoler flera kärnor. Laptops och stationära datorer är flerkärniga. Surfplattor är flerkärniga.

Man kan inte längre utveckla långsamma program och vänta på att hårdvaran ska komma ikapp.

Gratislunchen är över. Vad kan vi utvecklare göra?

[kqrx]

Ibland stöter jag på blogginlägg som jag egentligen inte är intresserad av, men jag läser ändå för att författaren skriver så bra. Det här är ett av dem.

Och det är ju bra, för nu vet jag hur man kan dela upp load mellan cache-servrar på ett skalbart och relativt tryggt sätt.

[kqrx]

Re: Är något tal summan av de övriga talen?

Men... säger du, Jag gillade ju den första funktionen, som tog tre argument. Det blir ju jättekrångligt om man ska göra en lista varje gång.

Överlagring, säger jag, Överlagring, min vän.

Förutsatt att du har den funktionen vi kom fram till i ursprungliga inlägget så kan du ju lätt skapa en funktion som tar tre argument istället, like so:

def isSum(a: Int, b: Int, c: Int): Boolean = isSum(Vector(a, b, c))

Det där är Scala för att säga det som på svenska heter, "Att kolla om tre heltal är en summering är samma sak som att kolla om en lista av samma tre heltal är en summering."

Och allt var gott igen. Och det blev natt och morgon igen. Det var den andra dagen.

[kqrx]

Tidskomplexitet förklarad (lite)

Tänk dig att du ska leta upp ett speciellt namn i en telefonkatalog. Det finns två självklara sätt att göra det på.

Du kan börja på Aab-Ericsson Sara, konstatera att "det var inte det här namnet jag ville ha," gå vidare till nästa namn, som kanske råkar vara Aalto Catharina och konstantera "inte det här heller." Så fortsätter du till nästa, nästa och nästa namn tills du hittar det du vill ha.

Att söka igenom en telefonkatalog på det sättet tar tid. Väldigt lång tid. Om namnet man letar efter är det sista namnet i katalogen måste man söka igenom lika många namn som det finns namn i katalogen. Man brukar kalla det för att sökningsmetoden man använder har en tidskomplexitet på $$\\mbox{O}(n)$$, eller att metoden är linjär i sin tidskomplexitet.

$$\\mbox{O}(n)$$ betyder att "Om telefonkatalogen har $$n$$ namn, så måste man i värsta fall söka igenom $$n$$ namn för att hitta det man vill."

Som du säkert känner till finns det andra metoder för att hitta namn i telefonkatalogen. Om du är smart kan du slå upp telefonkatalogen på precis mitten, titta på namnet som är på mitten av sidan, och fråga dig själv, "Namnet jag söker, ligger det före eller efter det namnet jag tittar på nu?"

På det sättet kan du fortsätta dela in telefonkatalogen i hälfter, och till slut har du bara ett eller inget namn kvar, beroende på om det du söker finns eller inte finns i katalogen. Då har du utnyttjat att telefonkatalogen faktiskt är sorterad.

Det häftiga med den metoden är att den kräver inte alls att man kollar igenom lika många namn som den förra. Om telefonkatalogen skulle ha 3 000 namn så skulle du med förra metoden behöva läsa 3 000 namn. Det är sjukt mycket. Med den här nya metoden behöver du bara läsa 12 namn. Bara tolv namn.

Den andra metoden kallas för en binär sökning och har en tidskomplexitet på $$\mbox{O}(\\log{n})$$. Om telefonkatalogen innehåller $$n$$ namn, så behöver man i värsta fall bara söka igenom $$\\log_2{n}$$ namn innan man hittar det man letar efter. (Bry dig inte om vad det här $$\\log$$ betyder, det enda du behöver veta är att $$\\log{n}$$ är mycket mindre än $$n$$.)

Tillåt mig illustrera hur stor skillnaden är mellan $$\mbox{O}(\\log{n})$$ och $$\\mbox{O}(n)$$. Tänk dig att det flyttar in massa människor i området, så telefonkatalogens storlek dubbleras. Telefonkatalogen blir dubbelt så tjock. Telefonkatalogen går från att vara kanske fyra centimeter tjock till att bli åtta centimeter. Det är många, många fler namn.

Med den linjära sökningen behöver du nu söka igenom dubbelt så många namn. Om det tog en halvtimme från början, så kommer det ta en timme nu att leta igenom alla namn.

Med den binära sökningen behöver du bara leta igenom ett namn till. När telefonkatalogens tjocklek dubbleras behöver du bara leta igenom ett enda ynka litet namn till.

Det är därför man, när man programmerar, hellre använder metoder som går i $$\mbox{O}(\\log{n})$$ än $$\\mbox{O}(n)$$.

[kqrx]

Grundläggande lambdakalkyl

Lambdakalkyl låter fånigt (jag tänker på professor Kalkyl i Tintin) men är i själva verket riktigt läckert. Lambdakalkyl formar grunden för all funktionell programmering, och det är så simpelt.

Du känner förmodligen till funktioner från matematiken eller programmeringen. Så här kan till exempel en funktione inom matematiken se ut.

$$$f(x) = 2x$$$

Funktionen $$f$$ tar ett $$x$$ som argument, och returnerar det dubbla värdet (två gånger $$x$$.) Låt mig visa precis samma sak i lambdakalkylen.

$$$\\lambda x \\rightarrow 2x$$$

Detta är en funktion som dubblerar invärdet. Först skriver man $$\\lambda$$ för att ange att det är en lambdafunktion, sen skriver man parameterns namn (bara en parameter!) som funktionen ska ta emot som argument, sen har jag valt att använda en pil (även om det inte är helt korrekt) och sen funktionskroppen. Du kan se följande omvandling:

$$$\\mbox{funktionsnamn}(\\mbox{parameter}) = \\mbox{funktionskropp}$$$

är samma sak som

$$$\\lambda \\mbox{parameter} \\rightarrow \\mbox{funktionskropp}$$$

Att ha en pil där är mitt påfund. Egentligen ska det vara en punkt, men punkt är så sjukt otydligt så jag låter gärna bli det. Lambdafunktioner har inget namn, är en första iakttagelse. Man kan identifiera dem med deras parameternamn istället. (Det innebär att parameternamnet måste vara unikt! Jag återkommer till det.)

Så. Right. En lambdafunktion är liksom en helt insluten enhet. Du kan plocka ut en lambdafunktion från var som helst och den betyder fortfarande samma sak, oavsett var den sitter. Så här applicerar man lambdafunktioner till något argument:

$$$(\\lambda x \\rightarrow 2x)\\ 5$$$

Vi innesluter lambdafunktionen i parenteser för att visa att det är en enhet, och sen sätter vi något argument till höger om den. Det som är direkt till höger om funktionen kommer att stoppas in istället för $$x$$ i funktionen. I det här fallet får vi $$$2 \\times 5$$$ som i sin tur blir 10, det vet vi alla. Men grejen är att när man stoppar in ett argument i en lambdafunktion, så tar man bort allt fancy $$\\lambda x \\rightarrow$$, om det inte behövs längre. Kvar är bara funktionskroppen, med alla $$x$$ ersatta med argumentet.

Här får du några till lambdafunktioner att träna på.

$$$(\\lambda y \\rightarrow 5y)\\ 7$$$ $$$(\\lambda z \\rightarrow z^2)\\ 8$$$ $$$(\\lambda k \\rightarrow 3k + 9)\\ 3$$$

Så, jag tror du fattar. Dags att gå vidare till Häftigt #1. Man kan använda vilka värden som helst som argument, inklusive andra lambdafunktioner! Här är en funktion som tar en funktion som argument.

$$$\\lambda f \\rightarrow f\\ 4$$$

Den här kan ta emot en funktion i $$f$$, och sen stoppar den in den funktionen i 4. Så den här funktionen gör något med fyra. Vad något är beror på vilken funktion man stoppar in. Till exempel kan man göra så här:

$$$(\\lambda f \\rightarrow f\\ 4)\\ (\\lambda x \\rightarrow 2x)$$$

För att ta reda på vad det här blir får vi börja med att stoppa in $$\\lambda x$$ i $$\\lambda f$$, och då får vi $$$(\\lambda x \\rightarrow 2x)\\ 4$$$

Vi har bara gjort vår vanliga ersättning och vi bytte ut alla $$f$$ i funktionskroppen mot argumentet. Den här resulterande funktionen vet vi ju hur man räknar ut. Så, det där är ju flexibelt. Nu kommer Häftigt #2.

Lambdafunktioner kan returnera vilka värden som helst, även andra lambdafunktioner. Nyss använde vi lambdafunktioner som argument, nu kan vi också returnera dem.

Detta är en lambdafunktion som returnerar en annan lambdafunktion.

$$$\\lambda b \\rightarrow (\\lambda a \\rightarrow a + b)\\ 3$$$

För att veta vad funktionen $$\\lambda b$$ returnerar, måste vi först veta vad dess kropp blir. Men vi vet ju redan att $$(\\lambda a \\rightarrow a + b) 3$$ kommer att ge resultatet av att ersätta alla $$a$$ med 3. Så, om vi gör det får vi $$$\\lambda b \\rightarrow 3 + b$$$

Och wham! En lambdafunktion returnerade en annan lambdafunktion! Den här funktionen kan vi nu ge ett argument för att plussa något med tre.

$$$(\\lambda b \\rightarrow 3 + b)\\ 4$$$

Och vi får $$3 + 4$$. Nu kommer the interesting part. Vi skulle kunna skrivit allt på en rad istället, like so:

$$$(\\lambda b \\rightarrow (\\lambda a \\rightarrow a + b)\\ 3)\\ 4$$$

Det här betyder "Jag vill ha $$a+b$$ där $$a = 3$$ och $$b = 4$$." Ser du hur det kan tolkas som en funktion med två argument, fast det egentligen är två funktioner med ett argument var? Så här skulle man kunna skriva:

$$$(\\lambda b \\rightarrow (\\lambda a \\rightarrow a + b)\\ b)\\ 3\\ 4$$$

Ser du!! Det är en funktion i en funktion, så det är visserligen två funktioner, men till det yttre tar den två argument. Om du skulle kunna stoppa in lambdorna i en låda, så här,

$$$\\mbox{sum} = \\lambda b \\rightarrow (\\lambda a \\rightarrow a + b)\\ b$$$

så skulle du också kunna anropa den så här:

$$$\mbox{sum}\\ 3\\ 4$$$

En funktion som tar emot två argument! Trots att den är uppbyggd av lambdor som bara kan ta ett argument. Vänta nu, hur gick det där till? Vi återgår till den ursprungliga lambdan som vi döpte om till $$\\mbox{sum}$$.

$$$(\\lambda b \\rightarrow (\\lambda a \\rightarrow a + b)\\ b)\\ 3\\ 4$$$

Vi börjar med att göra vad vi kan. Trean är ett argument till $$\\lambda b$$, så vi kan börja med att stoppa in den:

$$$(\\lambda b \\rightarrow (\\lambda a \\rightarrow a + b)\\ 3)\\ 4$$$

Notera två saker här.

Vi kan inte stoppa in trean istället för $$b$$ inuti $$\\lambda a$$, för vi kan inte se in i andra lambdafunktioner. Det hade varit smidigt om vi kunde, men vi kan inte. Det är bra med strikta regler för vad man får och inte får göra.

Vi har inte tagit bort $$\\lambda b \\rightarrow$$. Eftersom det finns en lambdafunktion kvar inuti $$\\lambda b$$:s funktionskropp kan vi inte säkert veta att $$\\lambda b$$ osv inte längre behövs. (Vi kan inte se in i andra lambdafunktioner, som sagt.) Vi behåller det tills vi vet säkert att det inte behövs längre.

Så, nu har vi ett nytt uttryck, och det vet vi vad vi kan göra med det. Stoppa in trean som argument till $$\\lambda a$$.

$$$(\\lambda b \\rightarrow 3 + b)\\ 4$$$

Där fick vi ta bort $$\\lambda a \\rightarrow$$, för vi vet säkert att det inte behövs mer. Nu har vi ett nytt uttryck, som vi också vet vad man gör med. Stoppa in fyran som argument till $$\lambda b$$.

$$$3 + 4$$$

Och så har vi lyckats följa hur en funktion som tar emot två argument fungerar, när den faktiskt är uppbyggd av flera funktioner som tar ett argument var. Att bygga upp en funktion som tar flera argument utav flera funktioner som bara tar ett argument kallas förresten för currying.

Nu ringer mitt sällskap på dörren, men lite senare kanske jag kan visa hur man faktiskt kan programmera i lambdakalkyl.