6. Abstraktion

6.1. Inledning

I denna laboration kommer du att få tillgång till ett system för att hantera en personlig almanacka. Systemet är byggt i Python, och innehåller ett antal fördefinierade funktioner som kommunicerar med varandra på bestämda sätt. Du ska i denna labb reparera ett par funktioner och bygga ut systemet med ny funktionalitet. Huvudpoängen är att du ska få arbeta med- och skapa abstrakta datatyper.

Föreläsning 12 och lektion 5 förbereder för denna laboration.

6.1.1 Datalagret, ett exempel

Vi kan illustrera hur detta fungerar genom ett exempel. I almanackan som den ser ut just nu ser en mötestid mellan 15.15 och 17:00 ut så här:

mötet = ('mötestid', (('tidsperiod', (('klockslag', (('timme', 15), ('minut', 15))), ('klockslag', (('timme', 17), ('minut', 0))))), ('möte', 'Skriva labb')))

Vi skulle kunna ta fram själva mötesdelen - informationsmässigt det som innehåller rubriken för mötet - genom att skriva mötet[1][1]. För själva textsträngen "Skriva labb" får vi gräva i mötet[1][1][1]. På liknande sätt skulle vi kunna hantera de andra delarna. I varje funktion som behöver använda denna information skulle vi sedan kunna infoga kodstycket med alla index här ovan. Det är möjligt, men har flera problem:

• koden blir oläslig
• det blir osmidigt att ändra representation
• det blir svårt för utomstående att bygga vidare på din kod

Istället skapar vi ett lager av funktioner som hanterar just denna funktionalitet. Varje funktion som behöver ha reda på vad för möte ett visst mötestidsobjekt är knutet till skriver sedan bara mötesdel(<mötestiden>). Om vi sedan bestämmer oss för att det är bättre att lagra mötestid på något annat vis (kapsla i egna objekt, göra ett dictionary eller bara ha pekare till något som gör slagningar i en SQL-databas), behöver vi bara ändra i just funktionen "mötesdel". Alla de andra potentiella funktionerna - från bokning i almanackan via filtrering/sökning till eventuella mobilinterface - fortsätter fungera som de gjort tidigare.

Denna laboration handlar om att lära sig tänka i lager, och hantera detta på klokt vis.

Till skillnad från språk som Java, Haskell och Ada är inte Python starkt typat. Det innebär att språket inte gör någon kontroll av att data av rätt typer kommer in i funktionerna förrän de körs. Vi kan exempelvis skriva kod där en funktion "väntar sig" att få in en lista, och sedan i själva anropet skicka in en textsträng. Python kommer inte stoppa det (förrän det kraschar när vi kör programmet).

I denna labb kommer vi att skicka runt data av egendefinierade slag. För att hålla koll på vad funktioner gör, och inte få oväntade effekter, skriver vi upp vad för slags indata funktionen väntar sig, och vad den ska ge åter (en typsignaturer). Detta är ett matematiskt sätt att beskriva funktioner i allmänhet, och är inte begränsat till de datatyper som Python har inbyggt (som String, Integer, m.fl.). Om vi ser på trädet från laboration 3 kan vi se att några typsignaturer är

Vad det betyder är det naturliga: "skapa_träd" tar två argument. Både första och andra argumentet väntas vara träd, och det funktionen ger tillbaka är isåfall ett träd. Notationen är precis samma som i den diskreta matematiken. Formellt beskriver man en funktion från den kartesiska produkten mellan mängden Träd och mängden Träd (därav krysset - kartetisk produkt) till mängden av Träd. Rent praktiskt: har man en funktion som tar in argument av olika typer, skriver man mängderna i samma ordning som argumenten och sätter kryss mellan.

Överkurs (inte nödvändig): För den som har specialintresse, finns en motsvarande analys av traversera här.

6.2. Filerna

Almanacksystemet består av följande filer:

• almanacka.py
• bokningar.py
• datatyper.py
• timeedit_import.py
• utskrifter.py

För att så enkelt som möjligt använda almanacksystemet bör du ladda ner alla filerna och spara dem i en och samma mapp. Om du sitter på IDA kan du komma åt filerna i katalogen ~TDDC66/src/alma/.

För att förstå hur funktionerna hänger ihop finns det en lista på typsignaturer för alla funktioner i almanackan (funktioner hittills, det vill säga). Använd den för att få överblick.

6.3. Att använda almanackan

Koden är uppdelad i flera olika filer, men en del filer är tyvärr inte färdigskrivna än. I en fil finns det funktioner som bryter mot abstraktionen (läs mer om detta längre fram) och som måste skrivas om, i andra filer finns det funktioner som inte ens är implmenterade, och som måste skrivas från början. Laborationsuppgifterna går i princip ut på att lösa detta, så att almanackan kan användas som väntat.

För att du ska få en liten uppfattning om hur almanackan fungerar bör du testa den. Det gör du genom att läsa in filen almanacka.py på följande sätt:

OBS! Denna prompt får du upp genom att köra den vanliga interpretatorloopen i python3. Detta är alltså inte inbyggt i utvecklingsmiljön Eclipse.

Efter det kan du skapa nya almanackor med hjälp av funktionen skapa samt visa vilka almanackor som finns med funktionen visa_almanackor.

När man har skapat en almanacka för en person kan man även boka möten för den personen med funktionen boka samt visa alla bokningar för den personen en viss dag med funktionen visa.

För att göra almanackan användbar finns en möjlighet att importera schema från timeedit med funktionerna importera_kurs och importera_grupp. Observera att man först måste ha skapat en almanacka för att det ska fungera.

Med funktionen spara kan man även spara alla almanackor i en fil och sedan ladda in dem igen med funktionen ladda (se hur man anropar dessa funktioner under rubriken Användargränssnittsfunktioner nedan).

Övning 601 Ladda in almanackan och testa de användarfunktioner som finns beskrivna i listan nedan. Pröva att skapa ett par almanackor, boka möten i dem och visa vilka möten som finns bokade en viss dag. Pröva också att importera ditt eget schema och se hur det ser ut.

Användargränssnittsfunktioner

Nedan följer en sammanfattad förklaring på de användargränssnittsfunktioner som finns.

visa_almanackor()

Visar vilka almanackor som finns.

skapa(namn)

Skapar en ny almanacka med det angivna namnet.
Exempel: skapa("Kalle")

boka(namn, dag, månad, start, slut, text)

Bokar ett nytt möte i den angivna almanackan.
Exempel: boka("Kalle", 12, "nov", "19:00", "21:00", "Födelsedagskalas")

visa(namn, dag, månad)

Visar alla bokningar för den angivna dagen.
Exempel: visa("Lisa", 1, "jul")

importera_kurs(namn, kurskod)

Importerar aktuellt kursschema från timeedit.
Exempel: importera_kurs("Stina", "TDDC67")

importera_grupp(namn, gruppnamn)

Importerar aktuellt gruppschema från timeedit.
Exempel: importera_grupp("Olle", "C1")

spara(filnamn)

Sparar samtliga existerande almanackor i en extern fil.
Exempel: spara("testdata")

ladda(filnamn)

Laddar in almanackor från en extern fil. Detta ersätter alla nuvarande almanackor.
Exempel: ladda("testdata")

6.3. Almanackans struktur

I det förra avsnittet tittade vi på almanackan från ett användarperspektiv. Nu ska vi lyfta på locket och se hur den fungerar inuti. Almanackan består av fem källkodsfiler och du kommer att behöva utöka definitionerna i senare uppgifter.

För att hantera de olika delarna i almanackan har vi infört abstrakta datatyper. Vi kan se det som att vi har utökat språket Python med nya typer och nya funktioner som opererar på dessa. Vi kan också se det som att vi har infört flera abstraktionslager. Det understa lagret är originalspråket, i det här fallet Python. Ovanpå det har vi skapat en samling primitiva funktioner för att hantera våra abstrakta datatyper. I nästa lager har vi byggt en rad hjälpfunktioner, dvs funktioner för att boka möten eller visa bokade möten en viss dag. De använder sig av de primitiva funktionerna i lagret under. Det översta lagret består av funktioner som användaren av almanackan ska använda. De brukar också kallas för gränssnittsfunktioner, eftersom de utgör gränssnittet mellan användaren och programmet, eller högnivåfunktioner eftersom de utgör den högsta abstraktionsnivån.

Innehållet i de olika filerna är följande:

• datatyper.py innehåller de primitiva funktioner som behövs för att kontrollera de abstrakta datatyperna samt en rad "bra att ha"-funktioner som används för att utföra generella mindre uppgifter som t.ex. att räkna ut längden av en tidsperiod eller jämföra två klockslag.
• bokningar.py innehåller funktioner som tar hand om större uppgifter som att till exempel boka möten.
• utskrifter.py innehåller funktioner för att skriva ut almanacksdata på ett läsbart sätt.
• timeedit_import.py innehåller funktioner för att importera schema från timeedit.
• almanacka.py innehåller funktioner för att hantera bokningar i olika almanackor och de gränssnittsfunktioner som användaren kommer åt.

6.4. Almanackans representation

För att kunna skilja våra olika abstrakta datatyper åt har vi infört en uppsättning grundläggande funktioner som hjälper oss att paketera information. Vi kan se det som att vi sätter en etikett på varje dataobjekt i almanackan. Etiketten talar om vilken typ av objekt det rör sig om och är samtidigt en kvalitetsstämpel som garanterar att innehållet har rätt struktur. Till exempel får inga klockslag 27:15 finnas, inte heller datumet 37 april.

Vårt typmaskineri består av två viktiga funktioner som paketerar respektive packar upp dataobjekt. Dessa funktioner heter packa_ihop och packa_upp. I praktiken så skapar packa_ihop en tupel där första värdet är en typetikett (en sträng) och andra värdet är det dataobjekt som ska märkas (t.ex. ett tal eller en lista). Funktionen packa_upp plockar ut dataobjektet, dvs första värdet av tupeln. Utöver dessa finns funktionen typ som returnerar etiketten och typkontroll som används för att kontrollera parametrarnas typer och vid behov skriva ut felmeddelanden.

Med detta typmärkningssystem kan vi lättare skapa abstrakta datatyper. Vi använder oss av våra packa-funktioner för att bygga igenkänningsfunktioner, skapa-funktioner och selektor-funktioner. Det är enbart de primitiva funktionerna i filen datatyper.py som känner till den exakta representationen, dvs hur strukturen av den högra delen av dataobjektet ser ut. Övriga funktioner manipulerar almanacksobjekten via de primitiva funktionerna, aldrig direkt.

I exemplet ovan ser vi hur funktionen skapa_månad returnerar ett almanacksobjekt av typen månad. Den interna representationen är ('månad', 'januari'), men det är inget som vi ska fästa något avseende vid. När vi bygger mer abstrakta funktioner kan vi inte utgå från att månader alltid representeras på det här sättet, utan vi använder de primitiva funktionerna för att skapa objekt, känna igen dem samt plocka ut deras delar.

Övning 602 Testa de olika primitiva funktionerna och se att du kan skapa olika slags objekt. Pröva till exempel att skapa följande objekt:

• Skapa klockslaget 13:15 och lagra värdet i den globala variablen kl1315.
• Skapa tidsperioden 13:15-15:00 och lagra värdet i den globala variabeln tp1315.
• Skapa en dagalmanacka som innehåller två möten: ett kl 8:15-9:30 för "Redovisning av uppgift", samt ett 13:15-15:00 med "Föreläsning i Python". Lagra värdet i den globala variabeln dag15.

6.5. Algoritmer och testning

De primitiva och "bra att ha"-funktionerna i datatyper.py fungerar som en verktygslåda med vars hjälp vi kan bygga mer avancerade funktioner. Bokning och avbokning av möten har vi redan sett exempel på. För att kunna lösa lite större problem, till exempel hitta lediga tider i en almanacka, behöver vi dock tänka efter lite extra och konstruera algoritmer som kan använda sig av våra primitiva funktioner.

Som exempel kan vi ta en situation där två personer ska försöka bestämma ett möte någon gång under en specifik dag. För att göra detta behöver båda två ha reda på vilka tider som finns lediga så att de kan jämföra dessa med varandra. Hur hittar man de lediga tiderna i en dagalmanacka? Vi vet att en dagalmanacka består av en sekvens av mötestider ordnade i kronologisk ordning. På något sätt måste vi gå igenom dessa i tur och ordning och identifiera mellanrummen mellan mötena. Hur kan man göra det?

Samtidigt som ni tar fram en algoritm för att lösa problemet ska ni också bestämma hur algoritmen ska testas. Detta är första gången som ni har en mer komplicerad funktion att testa, där många olika fall kan uppstå. Tidsperioder kan starta, sluta och överlappa varandra på olika sätt. Därför ska ni i nästa uppgift systematisera testningen genom att studera och anppassa en så kallad test driver samt konstruera egna testfall.

Börja med att på papper beskriva de olika testfall som kan uppstå och skriv ner vad du förväntar dig att funktionen ska göra. Du får skapa ditt eget sätt att formalisera detta, till exempel genom att rita tidsperioder som intervall. När du kommit en bit med att formulera eventuella hjälpfunktioner, fundera på vad för in- och utdata de behöver, och formulera deras typsignaturer. Detta kan vara till hjälp när du sedan konstruerar funktionerna.

6.6. Typsignaturer för primitiva funktioner

Här kan du hitta de primitiva funktioner som finns tillgängliga i almanackssystemet, grupperade efter vilken datatyp de opererar på. För förklaring av typsignaturer, se ovan.

timme

minut

dag

månad

möte

tidsrymd

klockslag

tidsperiod

datum

mötestid

dagalmanacka

månadsalmanacka

årsalmanacka

Överkurs. OBS! Detta avsnitt behövs inte för att klara kursen. Vad för typ har den högre ordningens funktion traversera? Vi kan påminna om att man anropar funktionen i stil med traversera( Träd, inre_nod_fn, löv_fn, tomt_träd_fn), så den kommer att vara av typ Träd × ngt × ngt × ngt -> ngt. Vi vet också att dessa andra typer "ngt" (som inte nödvändigtvis är samma) kommer att vara funktioner. Dessa har definitions- och värdemängd, och vi skriver deras typer som Df -> Vf. Om vi inte vet något om Df och Vf kan vi alltså skriva signaturen i stil med

traversera: Träd × (?? -> ??) × (?? -> ??) × (?? -> ??) -> ngt.

Vad är dessa typer? För att se det måste vi räkna ut typerna för inre-nod-fn, löv-fn och tomt-träd-fn. Det är inte helt uppenbart. Vi kan skicka med funktioner som ger heltal (räkna djupet på ett träd till exempel), eller funktioner som ger sanningsvärden (finns ett element i trädet?). Vi kan alltså inte ha en enda fix Python-typ som utdatatyp för alla funktionerna vi skickar med. Låt oss istället kalla utdatatypen för tomt_löv_fn för a (och på så sätt få något sätt att beskriva sambandet mellan in- och utdatatyperna, även om vi inte fixerat ett a). Det är potentiellt en typ som kan innehålla många saker - till exempel "en sträng eller en lista" (en unionstyp). Då kan vi räkna oss fram till att beteendet vi vill ha är

Utifrån det ser vi att en inre-nod-funktion som indata kommer att ta ett heltal (nyckeln) och något av denna typ a (tänk dig att vi befinner oss näst längst ned i trädet och får tillbaka värden från antingen ett tomt träd eller ett löv vi behandlat). Nästa steg är att konstatera att vi borde få samma utdatatyp från alla träd, alternativt att tänka oss ett träd där vänster gren är inre nod och höger gren är ett löv. Både inre-nod och löv-funktionerna borde alltså ha samma utdatatyp, d v s a. Därmed

Och därmed får vi
traversera: Träd × (Heltal × a × a -> a) × (Träd -> a) × (-> a) -> a

Hoppa tillbaka.

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2012-11-11