Etikettarkiv: Datavetenskap

Parentesfrågan

Läsaren har högst antagligen en uppfattning om vad parenteser är och vad deras roll är i en mening. Parenteser (trots namnet) är alltså inte teser, utan de ”… förtydligar, kommenterar, förklarar eller innebär ett sidospår från den övriga texten” (copy paste från Wikipedia). Med ”parenteser” menar jag förstås rundparenteser och inte hak-, klammer-, vinkel- eller piggparenteser, fastän samma grundprincip gäller också för dem.

Inom matematikens teoretiska drömvärld, till skillnad från naturliga språk, används parenteser för att ”ange grupper av termer […] för ordningen av räkneoperationer” (Wikipedia). Vi kan därmed säga att i matematiken har parenteserna olik semantik, vilket leder oss till en fråga: Vilken roll borde parenteser ha inom programmering?

Programmering är till stor del matematik. De första programmeringsstrukturerna härstammade från rena matematiska modeller som förverkligades med hjälp av elektronrör och senare mikroelektronik. Vi tar två konkreta exempel för att illustrera hur parenteser vanligtvis används inom programmering.

(defn kvadrat-summa [n]; summerar n första kvadraterna
(loop [i 0 resultat 0]; sätter variablerna 'i' och 'resultat' som 0
(if (<= i n)
(recur (inc i) (+ resultat (* i i)))
resultat
)))

(print (kvadrat-summa 5))

Ovan är Clojure kod som spottar ut summan på de fem första kvadrattalen. Clojure tillhör LISP familjen av programmeringsspråk där parenteser strukturerar programmet. Notera att all kod är omringad av parenteser som skapar en hierarki av funktioner och värden. Förklarningar och kommentarer placeras inte inom parenteser, utan inleds med semikolon. Koden kan köras här för de intresserade.

!gfortran, gcc version 5.4.0 20160609
!Summerar n första kvadraterna
integer function kvadrat_summa(n) result(summa)
real :: lista(n)

lista = (/(i, i=1,n, 1)/)
lista = lista*lista
summa = sum(lista)
end function kvadrat_summa

program P
print *, kvadrat_summa(5)
end program P

Som ett mindre extremt exempel på parenteser inom programmering kan vi betrakta ett bekant språk för fysiker, Fortran! Du kan köra koden här. Se hur parenteser används för att:

  • generera listor,
  • definiera funktionens resultat samt listans storlek, och
  • för att gruppera parametrar givna till funktioner.

Vi ser att parenteser behandlas liknande som inom matematiken, men varför så? Borde inte kod sträva efter att vara så naturligt läsbart som möjligt?

Svaret på första frågan är simpel; programmeringsspråk skapas av datanördar och inte lingvister. Men för att exemplifiera att naturliga parenteser är möjliga (och kanske även vettiga) inom programmering skrev jag nedan ett exempel på ett påhittat Python-liknande språk. Parenteserna fungerar som kommentarer eller tillägger extra detaljer.

(heltals) funktion kvadrat_summan på n (ett heltal):
(summerar n första kvadraterna)
i = 0
resultat = 0
medan i <= n:
resultat += i * i
i += 1
resultat

visa kvadrat_summan på 5

Mycket snyggare och klarare kod, inte sant? Bara om nån skulle hitta på ett liknande språk som också är körbart…

Fortsättning följer!

PyClojuR: En kod ouroboros

Betrakta Python-koden nedan.

s = 's = %r\nprint(s%%s) #Hello'
print(s%s) #Hello

Du kan prova köra den härifrån. Vad händer?

Ett program som skriver ut sin egen källkod utan att fuska kallas för en ’quine’. (Som ’fusk’ räknas direkt uppläsning av programfilen och annat liknande.) Exemplet ovan består av tre delar:

  1. Kod som data. Strängen ’s = %r\nprint(s%%s) #Hello’ innehåller kopian av programmet i text form.
  2. Kod som processerar datan. Notera att all processerande kod befinner sig i någon form i den användbara datan.
  3. Övrig data. Kommentarerna #Hello samt mellanslagen är fullständigt övriga och kan tas bort utan större problem.

Du kanske tänker att quiner är unika för Python-språket, men i själva verket kan man bevisa följande sats:

För alla vettiga programmeringsspråk L existerar det åtminstone ett program P∈ L som skriver ut innehållet av P.

Beviset kan läsas här för dem som är intresserade. I ett nötskal listas alla giltiga program Pi upp, vartefter det bevisas att för varje beräkningsbar funktion h kan man hitta en fixpunkt k så att Pk och Ph(k) är identiska. Genom att välja funktionen h så att Ph(t) skriver ut innehållet av Pt kan man hitta k så att programmet Pk skriver ut innehållet av sig själv.

Utifrån detta presenterar jag Waffes ouroborosprogram teorem (WOooP teoremet):

Givet vettiga programmeringsspråk L1, L2, … Ln  existerar det ett en serie av program P1∈ L1, P2 ∈ L2, … Pn∈ Ln där Pn skriver ut P1, och Pi skriver ut Pi+1.

Programmen P1, P2, … Pn kallas då för ouroborosprogram, namngett efter den mytologiska ormen som äter sin egen svans. Börjandes från Pi får man efter minst n körningar tillbaka det ursprungliga programmet Pi. En quine kan då tänkas vara ett ouroborosprogram på bara ett språk.

För att bevisa WOooP räcker det med att definiera LC som språkens L1, L2, … Ln sammansättning. Man kan sedan använda första satsen för att bevisa att det måste finnas en quine för LC, vilket är ouroborosprogrammet vi söker efter.

Som ett test på mitt teorem skrev jag ett hackigt ouroborosprogram från Python till Clojure till R. Ta gärna och testa för er själva! Koden finns i min git här: code.py.

Alla tre språken har online terminaler, så inget behöver installeras för att testa koden.

P.S. Här är ett lite längre ouroborosprogram på 128 språk.

Språk och tolkning

Eftersom jag har kodat på ett skolprojekt under hela veckoslutet tänkte jag  skriva en artikel om det. Uppgiften var att skriva en programtolk för det simpla MiniPL programmeringsspråket (tekniska specifikationen finns här för de nyfikna).

En vad?

En programtolk/interpretator (eng. interpreter) är ett program som tar in kod av ett specifikt språk och gör/kör det som koden begär. Detta är skillnad till en kompilator, som helt enkelt översätter kod från ett språk till ett annat. Programtolken är ofta uppdelad i 4  huvudsakliga delar: lexikal-, syntax- och semantisk analys, som tillsammans skapar en mängd programinstruktioner, och till sist själva körningen av instruktionerna.

Tolkningen börjar med lexikalanalys där karaktärer grupperas till ”symboler” eller ord (eng. tokens). Vi tar som exempel meningen ”Datorer har en von Neumann-arkitektur.” Karaktärerna kan grupperas till följande symboler: ”Datorer”, ”har”, ”en”, ”von Neumann”, ”-”, ”arkitektur” och till sist ”.”-tecknet. Till symbolerna tillsätts tilläggsdata, som att symbolen ”Datorer” är ett substantiv i plural, symbolen ”har” är ett verb osv.

Syntaxanalysen tar in dessa symboler, och försöker bygga upp satser och meningar av dessa, enligt specifierade grammatikregler. Satserna och meningarna sparas i ett så kallat (abstrakt) syntaxträd. Av exempelmeningen kan man bygga upp följande träd:

I programmeringsspråk är det ytterst viktigt att man kan tolka de givna symbolerna bara på ett visst sätt, dvs. språket får inte vara tvetydigt. Olikt en människa vet inte datorn vad den skall göra då en kod kan betyda två olika saker. Tvetydighet uppkommer oftast i syntaxanalysen, då man inte kan utgöra hurdant syntaxträd som ska byggas upp med hjälp av grammatikreglerna. Grammatiken måste omformas för att fixa problemet.

Efter att syntaxet är granskat så söker den semantiska analysen efter ”meningen” bakom meningarna — vad den givna koden eller texten betyder. En syntaktiskt korrekt mening behöver inte vara semantiskt korrekt. Ett typexempel är ”Färglösa gröna idéer sover häftigt.” Meningen är inte alls vettig (så länge man inte är alltför poetisk av sig), men följer ändå de svenska grammatikreglerna.

Vi tittar igen på exemplet ”Datorer har en von Neumann-arkitektur.” Den semantiska analysen för detta påstående kan bland annat bestå av att svara dessa frågor: Är datorer saker med en ”arkitektur”? Är ”von Neumann-arkitektur” en egenskap som en dator kan ha? Syntaxträdet omvandlas eller påfylls sedan med den information som man har samlat och rent syntaktiska element skärs bort, som punkter och bindestreck.

I semantisk analys av programmeringsspråk granskas det att variabel-/funktiontyperna är överensstämmande och att de variabler/funktioner som används är definierade. Syntaxträdet omvandlas samtidigt till en mängd programinstruktioner (oftast ändå i formen av ett träd) samt en ”symboltabell”, där definitionerna av variabler och funktioner sparas.

Efter allt detta kan instruktionerna köras. Under körningen sparas variabelvärden i symboltabellen, varifrån de kan återhämtas senare. Programtolken borde innehålla en liten mängd basfunktioner (som aritmetik och loopar) som sedan kan användas av programmerare för att bygga upp mer komplexa funktioner. Eller varför inte en ny programtolk?