[an error occurred while processing this directive] TDDC66 > Prova på-laboration i Haskell
Göm menyn

Prova på-laboration i Haskell

1. Introduktion till Haskell

Haskell är ett exempel på ett strikt funktionellt språk. Språk uppstår och dör, och Haskell är ett av de relativt unga språk som har överlevt ett tag, med stöd inom forskarvärlden och från exempelvis Microsoft Research. Det (och liknande språk) används inom exempelvis inom finansvärlden (databehandling), och koncept därifrån har fått efterföljare i andra språk.

Jämför man med Python, står Haskell för ett rätt annorlunda tankesätt. I Python och andra mer eller mindre imperativa språk fokuserar man ofta på hur beräkningar sker, vilka steg man ska ta (be användaren om indata, sätt res = 0, loopa n varv...). Inom funktionell programmering spelar det såklart roll hur man formulerar problemet, men fokus ligger mer på data och funktionsanvändning. Det ger programmeraren god koll på vad som gäller i programmet (vi har exempelvis aldrig variabler som vi måste hålla reda på om vi har ändrat eller inte), och ger det direkt mer av en matematisk grund. Det kan också kännas väldigt ovant.

Ett återkommande fenomen här är byggandet av generaliserbara strukturer. Du kommer nedan att se ett exempel på ett enkelt miniräknarspråk (och få bygga färdigt det). Ett typexempel i större kurser i Haskell är att bygga en generell struktur för en språkparser, där man bara behöver mata in de olika delarna av språket och vad de enskilt gör, och få ut en tolk.

Vad vi ska pröva på

Efter denna labb ska du ha fått pröva på åtminstone

  • Lösning av småproblem på funktionellt vis, i ett annat språk.
  • Haskells kodstil, med mönstermatchning
  • Ett språk som inte har ducktyping (mer om det nedan).
  • Testat ett språk med lat evaluering. (se nedan)
  • Partialevaluering.
  • Sett hur man kan hantera ett litet egendefinierat datorspråk.

Redovisning

Varje avsnitt har tillhörande övningsuppgifter. De som det står Att redovisa på skall redovisas. Gör dem först.

Det finns också valfria uppgifter. De kan du göra och visa upp för labbassistent om du vill, men det är inget krav. Gör dem först efter att du är klar med de som ska redovisas.

Den som hinner klart, har hunnit läsa alla utblickarna, kan dessutom ta en titt på det lätt utökade miniräknarspråket.

OBS! Räkna med att denna laboration kan komma att ta längre tid än prova-på-laborationen i SQL.

Att läsa labben

Denna labb kommer att introducera koncept från språket steg för steg. Den innehåller också en del exempel för den som vill läsa vidare, eller göra jämförelser med andra språk. Dessa små överkursavsnitt/utblickar har blålila bakgrund, och man behöver inte läsa dem för att klara labben.

Överkurs/utblick (när du är klar med labben, inte innan)
Den som funderar på funktionellt tänkande och dess användbarhet när man ska göra stora beräkningar/storskalig databehandling (modell dataindexering hos Google) kan ta en titt på sammanfattningen av Google Research-artikeln MapReduce: Simplified Data Processing on Large Clusters. Mer information finns på Wikipedias MapReduce-artikel eller vid Googles officiella Python-API-sida.

2. Att testa ghci

Haskell finns i både kompilerad och interpreterad version. Här väljer vi att skriva kod, och köra den direkt. Detta liknar sättet vi använt Python.

Starta emacs genom emacs &. Glasgow Haskell Compiler (som inkluderar en interpretator) finns tillgängligt i systemet.

Skriv in detta enkla program i emacs:

factorial :: Integer -> Integer factorial 0 = 1 factorial n = n * factorial (n - 1)

Spara det i din hemkatalog som my_fac.hs, och kör ghci.

andma54@parlomba1:tddc66$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude>

Du bör få upp en loop modell Pythons REPL (Read-Eval-Print-Loop), där du kan ladda in filen. Detta kan du göra med hjälp av ":l FILNAMN" (l som i load).

Tips
I GHCi kan du nästan alltid tab-komplettera dig fram, både till filer och funktioner. Så det räcker med att skriva ":l my<TAB>".

Prelude> :l my_fac.hs [1 of 1] Compiling Main ( my_fac.hs, interpreted ) Ok, modules loaded: Main. *Main> factorial 5 120

Vad vi har gjort är att skapa en funktion (inte så optimerad, men helt ok). Vad vi kan se här har vi

  1. Mönstermatchning. Precis som i språk som PROLOG skriver vi ett antal mönster som kan passa, och tolken använder det första som fungerar. Skriver vi "factorial 0" matchar vi det översta mönstret, och ger tillbaka ett returvärde. Skriver vi "factorial 72", matchar vi mönstret "factorial n", där vi nu har att variabeln "n" har värdet 72.
  2. In- och utdata. En mer subtil detalj är att vi direkt skriver "funktionsanrop indata = utdata". Vi tänker i termer av värden (nästan) hela tiden, och funktioner som gör annat (till exempel skriver ut till skärmen) är lite speciella.
  3. En typsignatur. Funktionen heter factorial, den tar in ett argument (ett heltal), och ger tillbaka ett heltal. Mer om det nedan.

En följd av att vi skrivit factorial :: Integer -> Integer är att vi inte kan skriva något i stil med factorial 5.0. Haskell är statiskt och starkt typat, så är factorial skriven så att den ska ta in ett heltal, måste den få ett heltal (och den kommer inte att försöka göra om 5.0 till 5 utan att tala om det). Till skillnad från i Python sätter Haskell (och många andra språk du kommer att stöta på) stopp för att man skickar runt fel slags data, redan på kodstadiet.

Ett mer praktiskt sätt att skriva mönstermatchningen ovan är

factorial :: Integer -> Integer factorial n | n == 0 = 1 | otherwise = n * factorial (n - 1)

Tips
När du sedan skriver egen kod, tänk på att Haskell (precis som Python) är indenteringskänsligt. Pipe-tecknen ska stå lika långt in på raden.

Ett mer "Haskellskt" sätt att skriva rekursiva funktioner är att försöka få dem att ge tillbaka svaret på slutet (snarare än bygga upp det på vägen tillbaka, modell 5 * factorial 4 = 5 * 4 * factorial 3...). Så här kan man skriva en sådan funktion:

factorial n = fact_iter n 1 where fact_iter n res | n == 0 = res | otherwise = fact_iter (n - 1) (n * res)

Notera likheten med hur man gör i en for-loop i Python. I Python börjar vi med resultat = 1, kör n varv och uppdaterar resultat varje varv. I Haskell passar vi med en nyuppdaterad resultat i varje anrop istället, och returnerar resultatvärdet på slutet (detta värde vandra oförändrat åter genom anropskedjan). Detta kallas svansrekursion, och Haskell kommer att göra optimeringar så att detta blir effektivt.

Överkurs/utblick (när du är klar med labben, inte innan)
Om du vill lära dig mer om detta (och jämförelser med andra språk), finns en kort genomgång i början av Real World Haskell, kapitel 2, Types and functions.

3. Koncept och övningar

Listor och listbyggare

Listor i Haskell och Python liknar varandra ytligt, i synnerhet vad gäller listbyggare (där Python kopierat konceptet rakt av). Vi kan bygga en lista av alla tal 1..20 genom att skriva [1,2..20] eller [1..20], och på matematiskt vis skriva

Prelude> let squares = [x*x | x <- [1..10]] Prelude> squares [1,4,9,16,25,36,49,64,81,100] Prelude> squares !! 0 -- Ta ut element nummer 0 1 Prelude> :t squares squares :: [Integer] Prelude> head squares 1 Prelude> tail squares [4,9,16,25,36,49,64,81,100] Prelude> take 5 squares [1,4,9,16,25]

När vi befinner oss i loopen - till skillnad från när vi definierade funktionen i en separat fil - måste vi skriva let innan våra definitioner.

Observera typen för listan. När vi vill bygga ihop listor, kan vi använda (++) eller (:). Kolon kan man tänka på som att man lägger till ett element först.

Prelude> [1000,1000,1000] ++ take 5 squares [1000,1000,1000,1,4,9,16,25] Prelude> 999999:(take 5 squares) [999999,1,4,9,16,25] Prelude> 1:2:3:[] [1,2,3]

Observera att de flesta typer du stöter på inte kan ändras (precis som strängar i Python). Detta inkluderar listor. Listor är alltså inte är muterbara. Vill du ersätta ett element i en lista, bygg upp en ny istället.

Strängar är listor med bokstäver (typ: [Char]), och fungerar precis som andra listor. Att blanda olika slags listor går inte:

Prelude> "Hej" ++ " hopp" "Hej hopp" Prelude> ["Hej", "Tesco"] ++ take 5 squares <interactive>:22:28: Couldn't match expected type `[Char]' with actual type `Integer' Expected type: [[Char]] Actual type: [Integer] In the second argument of `take', namely `squares' In the second argument of `(++)', namely `take 5 squares'

Tips
Det är ofta värt att läsa felmeddelanden noga. Det gäller många av de språk du kommer att stöta på.

Tolkning: Vi får in en lista med strängar (typ [Char]). Det till höger om ++ är en lista med Integer. Haskell försöker matcha dessa, och misslyckas. Den väntade sig [[Char]] (expected type), och fick [Integer] (actual type). I det här fallet är felmeddelandet rätt informativt, om man väl tar sig tid att avkoda det.

Tips
Om du behöver fler exempel, eller lite mer matig förklaring, är avsnittet An intro to lists i gratisboken Learn you a Haskell for great good bra. Där finns också diskussion om list comprehensions. Om man inte har tid att läsa all text, kan det vara värt att titta på exempelkoden.

Mönstermatchning med listor

Ett väldigt praktiskt sätt att skriva funktioner som använder listor, ser ut som detta:

lastElement [e] = e lastElement (x:xs) = lastElement xs

Om vi skickar in en lista "[1,2,3]" så kommer den inte att matcha det första alternativet (den passar inte mönster "lista med ett element"). Däremot matchar den det andra. Vi kommer att ha x=1 och xs = [2,3] (precis motsvarande head och tail). Vad vi säger sedan är att sista elementet i listan [1,2,3] är samma som sista elementet i listan [2,3]. Och så vidare. xs kan matchas mot valfri lista. Den tomma listan skriver, man precis som i Python, [].

Tips
Mönstret "_" matchar vad som helst. Vi kan till exempel definiera tail som "tail (_:xs) = xs". Första elementet spelar ingen roll, men vi bryr oss om resten. Detta fungerar utanför list-parenteser också: "andraArgumentet _ y = y".

Att redovisa Skriv en funktion listLength som tar en lista och ger tillbaka antalet element i en lista. Skriv till att börja med ingen typsignatur.

Att redovisa Skriv en funktion addLists som tar två listor (x:xs) och (y:ys), och ger en lista där vi adderat de båda första-elementen, de båda andra-elementen, och så vidare, elementvis. Skriv till att börja med inte någon typsignatur. Du kan inte anta att listorna har lika många element. Se på följande körexempel:

*Main> addLists [1,2,3] [500, 600, 700] [501,602,703] *Main> addLists [1,2] [500,600,700,800] [501,602] *Main> addLists [1,2,3] [500] [501]

Tips
Det finns ett par bra exempel i Learn you a Haskell-avsnittet Pattern matching. Listexemplen börjar strax innan den första gula tipsrutan.

Lathet

En skillnad mellan Python och Haskell är att Haskell använder lat evaluering, och bara beräknar argument om de verkligen behövs. Detta ger ibland en mer naturlig struktur, och behandling av stora, potentiellt sett oändliga, dataströmmar. Det kräver samtidigt att man är van vid det, framförallt om man vill skriva minneseffektiv kod.

För att ta ett konkret exempel, skapar detta alltså inga problem:

Prelude> let allSquares = [x*x | x <- [1,2..]] Prelude> :sprint allSquares -- skriver ut allSquares värde utan att tvinga fram beräkning allSquares = _

Vad vi ser här är att allSquares är något okänt som inte beräknats än. Vi fortsätter.

Prelude> take 2 allSquares [1,4] Prelude> :sprint allSquares allSquares = 1 : 4 : _

Det vi beräknat hittills är första två elementen. Vi har något som ser list-aktigt ut, och börjar med 1, 2.

Prelude> head allSquares 1 Prelude> let allButFirstSquare = tail allSquares Prelude> allButFirstSquare !! 123 15625 Prelude> :sprint allSquares -- OBS! allSquares, inte allButFirstSquare allSquares = 1 : 4 : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : 15625 : _

Kopplingen mellan allButFirstSquare och allSquares gör att när vi beräknar element 123 i allButFirstSquare, får vi reda på något om ett element i allSquares.

OBS! Att "behövs" i "behöver beräknas" kan inkludera "användaren försöker visa dem på skärmen". Så skriver man allSquares i loopen efter att ha skrivit det ovan, kommer man att få ut en följd av kvadrater som fortsätter tills minnet tar slut, eller man trycker Ctrl-C. Ta för vana att bara testa med ett begränsat antal värden (take ...).

Att redovisa Skriv let x = [0] ++ addLists x [1,1..] i loopen. Vad är X (med medvetet dåligt namn) för lista? Förklara varför den ser ut som den gör, och hur den beräknas.

Typ, liksom

För att förstå lite mer vad man sysslar med i Haskell, är det värt att ta en väg förbi dess typsystem.

Om vi matematiskt ser på funktionen f(x,y) = 2x + y + 1, ser vi att den - lite slarvigt - tar in två tal, och ger tillbaka ett tal. Om vi inte vet mer, kan vi skriva

f : Tal x Tal -> Tal

Än så länge inte sagt om dessa tal måste vara heltal, positiva, komplexa... Om vi med "1" menar siffran 1, vet vi åtminstone att det är ett tal som kommer ut ur beräkningen (och inte något annat matematiskt objekt som kan adderas, som en vektor.

I Haskell ser det lite liknande ut. Starta ghci och skriv följande:

Prelude> let f x y = 2*x + y + 1 Prelude> :t f

Vad som händer är att Haskell listar ut att vi (på ett ungefär - se nedan!) har en funktion som har tar två parametrar av en viss typ a, och ger tillbaka ett svar som är av samma typ. Vi säger inte om parametern a ska vara ett heltal, decimaltal, komplext tal eller annat. Men vi vet svaret kommer att vara begränsat till något slags tal (så a kan inte vara en sträng...). Därför står det "Num a => " innan.

Num är ett exempel på en typklass. Ett par andra praktiska exempel är Eq (saker där man kan testa likhet), Ord (där det finnns ordning; vi kan säga att 2 > 1, och "b" > "a"), och Show. Det här sättet att arbeta gör att man kan bygga funktioner som är väldigt generella, men där man ändå har koll på vilken sorts data som skickas runt.

Överkurs (om du är klar med labben)
Detta kallas parametrisk polymorfism (och har influerat hur C# och Java utvecklats). En kort förklaring finns i Real World Haskell, kapitel 2, Polymorphism in Haskell.

Currying och partialevaluering

Om man jämför med den matematiska versionen av funktionen f, ser man en viss skillnad. Matematiskt tänker man sig det som

f : Tal x Tal -> Tal
men Haskell-funktionen ser ut som
f :: Num a => a -> a -> a.

Detta har att göra med att Haskell kommer att göra en kedja av funktioner med en parameter. Istället för att anropa funktionen med f(21, 1), som man gjort i Python, betar man av argumenten ett i taget. Först körs f 21, vilket blir en funktion. Vi går från Num a => a -> a -> a till något där vi fixerat vad första argumentet är. Sedan kör vi denna nya funktion med indata 1, och får ut vårt svar.

Det finns inget som hindrar att vi sparar undan funktionen. Vill vi skapa plusFyrtioTre, och har definierat f som i stycket ovan, kan vi skriva

Prelude> let plusFyrtioTre = f 21 Prelude> plusFyrtioTre 100 143

Detta kallas partialevaluering, där vi inte evaluerar hela uttrycket, utan bara gör en del av bindningarna (bara första parametern sätts till 42, andra lämnas kvar).

Att omvandla en funktion från f : A x B -> C till f : A -> B -> C kallas Currying (efter logikern Haskell Curry, som också gett namn åt språket).

Övning Pröva att kommentera bort typsignaturen (lägg till -- innan factorial :: ...-raden) i my_fac.hs. Det kommenterar bort raden. Undersök sedan vilken typ factorial har (:t factorial). Borde factorial 5.0 fungera, nu när din första typsignatur kommenterats bort? (Tänk först, pröva sedan)

Att redovisa I övning ovan skrev du en funktion listLength, utan att skriva vad den hade för typsignatur (vad för in- och utdata den klarar). Fundera på vad för slags listor den bör klara. Skriv sedan :t listLength. Förklara resultatet. Skriv till motsvarande typsignatur i din kod.

Att redovisa Tidigare skrev du en addLists. Vad för typsignatur bör den ha? Låt Haskell räkna ut detta åt dig, skriv till det i din kod (det är god stil), och förklara resultatet när du redovisar.

Valfri Vi har en funktion map som tar en funktion och en lista, och ger tillbaka resultatet av att applicera funktionen på alla element i listan. Vad har map för typ? Tänk först, använd sedan :t map. Förklara resultatet (vad är det för slags parametrar, hur passar de olika typvariablerna ihop? Varför står det inte bara en mängd a?)

Valfri addLists är en specialiserad version av mönstret "ta två listor, och sätt ihop elementen på något sätt" (i detta fall "lägg ihop elementen var och ett för sig"). Detta är bekant från föreläsningarna (eller kunskap om hur blixtlås ser ut) som något slags zip. Ta reda på en användbar funktion för detta ändamål. Ett första steg är att börja att skriva zip och tryck TAB ett par gånger för att få (flera) förslag. Undersök typerna för de olika funktionerna, och hitta en som ser bra ut. Använd sedan denna för att definiera addLists'.

Tips
Du kan läsa mer om detta i början av kapitlet Higher order functions i Learn you a Haskell.

Att bygga med funktioner

Precis som i Python (och i ännu högre utsträckning) kan vi bygga med funktioner. Om vi (i en fil) har definierat

f x = 100*x g y = y * y

kan vi skriva funktionssammansättningen som h = f . g. När vi anropar h 7 får detta alltså samma resultat som f (g 7), det vill säga f 49, och därmed 4900.

Ett bekant exempel från Python är map, som tar en funktion och en lista, och applicerar den på varje element i listan (utdata är en ny lista som innehåller alla resultat).

lambdan, anonyma funktioner, skrivs i Haskell med backslash och pilar. En anonym funktion som lägger ihop två argument skrivs \x y -> x + y (så (\x y -> x + y) 1 2 ger heltalet 3 som svar).

foldl, foldr, där det första även är känt som combine är praktiska:

Prelude> foldl (\acc elem-> 2*acc + elem) 1000 [7,8,9] 8053 Prelude> foldl (\acc elem-> 2*acc + elem) 0 [7,8,9] 53 Prelude> foldl (+) 0 [100,62, 9] 171

Eftersom ( ( ( 2*1000 + 7 )* 2 + 8)*2 + 9) = (((2007*2)+8)*2 + 9) = 4022*2 + 9 = 8053.

Att redovisa Använd map och en anonym funktion (ett lambda) för att skriva en funktion squareAll som tar en lista med tal av något slag, och kvadrerar varje element.

Att redovisa Använd foldl och listbyggare för att skriva en enkel fakultetsfunktion. Funktionen ska bli en enradare (så det blir två rader inklusive typsignatur).

4. Ett litet språk

Vi kan såklart även definiera egna datatyper. Eftersom Haskell typiskt sett passar väl för att hantera små egendefinierade språk, väljer vi att definiera följande enkla exempel:

data Uttryck a = Siffra a | Plus (Uttryck a) (Uttryck a) deriving (Show, Eq) berakna :: (Num a) => Uttryck a -> a berakna (Plus u1 u2) = (berakna u1) + (berakna u2) ...

Skelettet, och ett par testfall finns i minisprak.hs. Ladda ned den och modifiera. Notera att skelettet ännu inte är färdigskrivet, så det kommer inte att gå att ladda riktigt än.

Notera likheten mellan hur vi definierar språket, och logikuttrycken i laboration 3. Detta är ett mer generellt mönster. Skillnaden här är att vi bara behöver skriva själva beteendet - ett plusuttryck ska beräkna vänster uttrycksträd, höger uttrycksträd och returnera summan av värdena. Inget mer.

Mönstermatchning fungerar precis som i fallet med listan:

Övning Att fundera på: låt säga att vi har testuttrycket let elva = Plus (Siffra 5) (Plus (Siffra 6) (Siffra 0)). Om vi försöker köra berakna här ovan, vad kommer u1 att matchas mot? u2?

Att redovisa Utöka berakna så att den klarar siffror också (på formen ovan). När du är klara med detta, ska du kunna köra följande:

*Main> let elva = Plus (Siffra 5) (Siffra 6) *Main> let sjua = Siffra 7 *Main> berakna sjua 7 *Main> berakna elva 11

Det enda som behöver läggas till rör Siffra. Plus-raden kan vara orörd.

Att redovisa Ett par operationer som vi vill ha med saknas. Utöka språket så att det klarar Minus och Ggr (på samma sätt som för Plus).

När du har utökat språket, kan du lägga in koden från prettyprint.hs. Det gör att du kan skriva

*Main> printAnswer test2 (5 + 5) + 12.52 = 22.52

5. Om du har tid

Det finns ett antal saker som inte hunnits med under denna labb. Börja med att se på valfria uppgifter ovan, och utblickarna.

En lite större uppgift därefter är att lägga till variabeluppslagning i beräkningsspråket ovan. Räkna till att börja med att du vet att variabeln finns med i variabeltabellen.

Du behöver inte fundera särskilt på effektiv uppslagning i detta skede, utan gör en funktion som tar in ett variabelnamn (till exempel av typ [Char]), och en variabeltabell (till exempel av typ [ ([Char], a) ], där a är ett tal). Definiera en typ type Tabell a = ([Char], a). Se till att denna fungerar först. Inför sedan "Variabel [Char]" i grammatiken, en berakna-rad, och utöka alla tidigare funktioner så att de får med tabellen också..

Ett tips om du vill ha en något mer effektiv uppslagning, är att använda Data.Map. Det bör inte vara svårt att modifiera din variabeluppslagning (och type Tabell=...-rad) när du lärt dig hur Map fungerar.

Fundering: om det går fel?

I Python, och många andra språk där man har visst fokus på själva instruktionerna som ska utföras, kan man säga att man prövar att göra en beräkning. Om den genererar fel, fångar man det felet, och gör något särskilt. I Haskell förväntar vi oss hela tiden att det ska komma tillbaka värden. Detta gör det ytligt sett svårt att hantera uppslagning av variabler som inte finns. Ett sätt att hantera detta är Maybe-monaden. Du kan läsa mer på denna wikibook-sida, i Real World Haskell eller Learn you a Haskell.

6. Om du vill läsa vidare

Den som vill pröva språket ytterligare kan ladda ned Haskell Platform (GHC med mera).

Ett par bra ställen att börja om man vill lära sig mer, är

Ett par kul exempel är

Kurser

Det finns inga LiTH-kurser i Haskell, eller (strikt) funktionell programmering. Om man är intresserad av programmeringsspråk och språkkoncept mer generellt, kan det vara värt att titta på (senareårskurserna) TDDA69 Data- och programstrukturer och TDDB44 Kompilatorkonstruktion.

Bland svenska universitet kan Chalmers vara värt att notera här. De har en forskargrupp inom funktionell programmering, och ger i dagsläget ett par fristående kurser i Haskellprogrammering (både introduktionskurs och rätt avancerade, samtliga på plats i Göteborg).

Överkursartiklar och utblickar

En filosofiskt intressant artikel (med exempel i Haskell) är Hughes - Why Functional Programming Matters. Det är kanske inte det man läser i första taget, men den är intressant likafullt.

En illustration av hur generella strukturer kan byggas och användas, ges i Monadic parsing in Haskell. Vad som görs där är att man på ett matematiskt sätt definierar hur språkparsers kan se ut, och sedan visar hur det kan fungera. Räkna inte med att du förstår allt (förkunskapskrav: student som läst ett par år, inklusive ett par Haskell-kurser), men ta en titt på hur man går från "något som kan skapa en parser som tar kod till en körbar struktur som den ovan" till en faktisk tolk för ett kalkylspråk som liknar det i övningen. Det konkreta exemplet har vi på näst sista sidan i PDF-filen.

Om laborationen

Denna laboration togs fram 2013 av Anders Märak Leffler. Tack till Peter Larsson-Green för kommentarer. Modifikationer har gjorts 2015 för att underlätta, och med anledning av uppdaterade datorsystem.


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2015-10-13