8. Abstraktion

Uppdateringar

Denna labb är färdig för 2023.

Om du ska komplettera en labb från 2019 eller tidigare finns också gamla instruktioner kvar. Dessa använder ett annat sätt att programmera och är inte aktuella för senare studenter.

Studiematerial

Innan denna labb påbörjas ska följande studiematerial ha lästs:

• Dataabstraktion

Det är också till hjälp att ha gått på seminarium 10.

Använd kursmodulen!

Använd kursmodulen (module add courses/TDDE24) för att få rätt version av Python samt tillgång till moduler som används under labben!

8.1. Inledning

Denna laboration handlar om att lära sig tänka i lager av abstraktioner och funktionalitet, och att hantera detta på ett klokt vis. Mer specifikt kommer vi att arbeta med dataabstraktion och med de lager av funktionalitet som behövs för att stödja abstraktionen.

Detta görs i 4 steg, labb 8A till 8D. När ni implementerar dessa steg kommer ni att lägga all er egen kod i separata filer vars namn börjar med lab8 -- dessa filer finns redan med i labbskelettet som ni laddar ner. Ni kommer också att kunna ändra i settings.py (mer om det senare). Övriga filer ska ni inte ändra.

Ni demonstrerar resultatet en gång efter labb 8C och därefter en gång när hela labben är klar.

Checka in och pusha kod ofta, gärna flera gånger om dagen, även om ni inte är klara med labben. Dels är versionshantering bra för att få "kontrollpunkter" som man kan backa till vid behov, dels ger regelbundna incheckningar en tydlig logg över hur arbetet har gått till. Den loggen är inte minst bra för att demonstrera att ni har skrivit programkoden själva!

Som exempel för dataabstraktion kommer vi att använda ett system för att hantera en personlig almanacka. Någon har redan börjat utveckla detta system, och har både skapat en design och till stora delar implementerat designen i Python. Tyvärr följs inte riktigt de riktlinjer som vi har diskuterat i studiematerialet! Du ska därför ta över arbetet:

• Det finns funktioner som bryter mot abstraktionen och som måste skrivas om. För att hjälpa er har vi redan lagt in de filerna i lab8a.py.

• Det finns också funktioner som inte ens är implementerade, och som måste skrivas från början. Dessa kommer att läggas i lab8b.py, lab8c.py, och lab8d.py.

Men först ska du få experimentera lite med den existerande implementationen så att du får en bättre uppfattning om hur den är tänkt att fungera.

8.1.1. Hitta labbfilerna

Alla filer som används för labb 8 -- inklusive de som du själv ska fylla i -- ska redan finnas i ditt Git-arkiv. (Dessutom finns de tillgängliga på webben, i alma-katalogen, men titta i din lab8-katalog först.)

Den ursprungliga implementationen finns i följande filer:

• cal_abstraction.py -- ett abstraktionslager som definierar hur information faktiskt lagras i en almanacka. Eftersom du har läst studiematerialet vet du redan vad detta betyder! Här finns både de primitiva funktioner som behövs i abstraktionslagret för de egna datatyperna och 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. Filen får inte modifieras.

• cal_booking.py -- bokningsfunktioner som använder funktionerna i cal_abstraction.py för att manipulera almanackor utan att behöva veta exakt hur den interna representationen ser ut. Här finns funktioner för att till exempel boka möten. Filen får inte modifieras.

• cal_output.py -- utmatningsfunktioner som använder funktionerna i cal_abstraction.py för att hämta ut och skriva ut information från en almanacka på ett läsbart sätt. Filen får inte modifieras.

• cal_ui.py -- användargränssnittet, funktioner som användaren kan anropa från Python-prompten för att hantera bokningar i olika almanackor, och som använder funktionalitet från övriga filer. Filen får inte modifieras.

• settings.py -- inställningar som ska användas i labbarna (förklaras senare). Filen får modifieras för att ändra inställningarna -- när vi säger till!

Du ska själv implementera eller ändra kod i lab8a.py, lab8b.py, lab8c.py, lab8d.py, och lab8d_tests.py.

8.1.2. Testa den ursprungliga implementationen

För att testa läser du in filen cal_ui.py på följande sätt:

>>> from cal_ui import *

Efter det kan du skapa nya almanackor med hjälp av funktionen create, och visa vilka almanackor som finns med funktionen show_calendars.

>>> create("Mal")
A new calendar by the name Mal has been created.
>>> create("River")
A new calendar by the name River has been created.
>>> show_calendars()
The following calendars exist:
River
Mal

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

>>> create("Jayne")
A new calendar by the name Jayne has been created.
>>> book("Jayne", 20, "sep", "12:00", "14:00", "Rob train")
The appointment has been booked.
>>> book("Jayne", 20, "sep", "13:00", "15:00", "Rob train")
The proposed time is already taken.
>>> book("Jayne", 20, "sep", "15:00", "16:00", "Escape with loot")
The appointment has been booked.
>>> show("Jayne", 20, "sep")
20 september
===========
12:00-14:00 Rob train
15:00-16:00 Escape with loot

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

Övning 801 Ladda in almanackan och testa de användarfunktioner som finns beskrivna i listan nedan. Prova att skapa ett par almanackor, boka möten i dem och visa vilka möten som finns bokade en viss dag. Spara gärna undan koden som skapar kalendern i en Pythonfil och kör den därifrån, istället för att köra direkt från terminalen. Då kan du använda detta till framtida tester när du börjar ändra i almanackans kod! (Om du bara sparar resultatet, med save(), kan detta inte användas till att testa funktionerna för att skapa almanackan... så spara kod med själva anropen till create, book med mera.)

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

calhelp()

Ger en påminnelse om vilka kommandon (funktioner) som finns.

show_calendars()

Visar vilka almanackor som finns.

create(cal_name)

Skapar en ny almanacka med det angivna namnet.
Exempel: create("Kaylee")

show(cal_name, d, m)

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

book(cal_name, d, m, t1, t2, subject_text)

Bokar ett nytt möte i den angivna almanackan.
Exempel: book("Kaylee", 12, "nov", "19:00", "21:00", "Repair engine")

remove(cal_name, d, m, start)

Avbokar ett möte med given starttid i almanackan. Denna implementerar du i 8C.
Exempel: remove("Kaylee", 12, "nov", "19:00")

save(filename)

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

load(filename)

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

8.2. Almanackans nuvarande design och implementation

Nu ska vi titta närmare på almanackans design och implementation. Vi går därför tillbaka till början av designprocessen och börjar se på hur man har tänkt när man har strukturerat almanackan. När vi går vidare genom olika aspekter av designen kommer vi även att se på vad som blev bra, var det finns brister, och varför vi ser detta som brister.

8.2.1. Specifikation av datatyper för almanackan

Den ursprungliga utvecklaren började med att tänka genom vilka datatyper som behövs och hur dessa ska hänga ihop (se slutet av studiematerialet för dataabstraktion för mer detaljer om syntaxen för dessa beskrivningar).

  Hour: integer                      # timme -- ett heltal
  Minute: integer                    # minut -- ett heltal
  Time: <Hour, Minute>               # klockslag (absolut tid på dagen)
  TimeSpan: <Time, Time>             # tidsrymd med start och slut
  Duration: <Hour, Minute>           # varaktighet (hur länge ett TimeSpan varar)
                                     # (det är skillnad på "2 timmar" och "klockan 02"!)

  Day: integer                       # dag
  Month: string                      # månad
  Date: <Day, Month>                 # datum med dag och månad

  Subject: string                    # ärende för ett möte
  Appointment: <TimeSpan, Subject>   # möte

  CalendarDay: <Day, {{Appointment}}*>      # kalenderdag som sekvens av möten med dagsangivelse
  CalendarMonth: <Month, {{CalendarDay}}*>  # kalendermånad med månadsangivelse
  CalendarYear: {{CalendarMonth}}*          # kalenderår

Detta fungerar bra för den funktionalitet vi vill ha och vi har just nu ingen anledning att ändra på det. Men tänk på att detta i princip bara är en designspecifikation på hög nivå: Vi vill att dessa datatyper ska existera och att de ska vara implementerade på ett lämpligt sätt i det programspråk som väljs (vilket för vår del råkar vara Python). Vi har ännu inte talat om vilken övrig funktionalitet datatyperna ska ha.

8.2.2. Att konkretisera specifikationen i Python

Datatyperna som vi angav nyss har alltså ingenting med ett specifikt programmeringsspråk att göra. Vi har helt enkelt talat om vilken sorts information som behöver finnas, utan att säga något om hur den ska lagras.

Den okända författaren till den existerande programkoden funderade på att implementera specifikationen på enklaste möjliga sätt genom att timmar blev till Pythons heltal, tupler (<Hour,Minute>) helt enkelt blev till Pythons tupler (timme,minut), och sekvenser blev till Pythons listor. Då skulle en TimeSpan som beskriver tiden mellan 15:15 och 17:00 kunna se ut så här:

span = ((15, 15), (17, 0))

Ett möte (av typ Appointment) under denna tidsperiod kan se ut så här:

prep = (((15, 15), (17, 0)), 'Lab prep in Java')

Men vänta nu. Hur ska vi då kunna testa om rätt typ skickas in till olika funktioner? Författaren funderade på att göra detta genom att lägga på en etikett på varje värde. Då blir alla värden istället till tupler som börjar med en etikett:

prep = ('Appointment', (('TimeSpan', (('Time', (('hour', 15), ('Minute', 15))), ('Time', (('hour', 17),
    ('Minute', 0))))), ('Subject', 'Lab prep in Java')))

Rent tekniskt skulle det här så klart fungera – det innehåller all den information vi behöver. Men Python ger oss också möjlighet att skapa egna datatyper, inte bara återanvända tupler till allt. Då får vi också fördelen att vi t.ex. kan testa typer med isinstance istället för att uppfinna egna sätt att känna igen typer.

Därför gick författaren vidare från de "vanliga" tuplerna och övergick till NamedTuple, som i labbskelettet (i cal_abstraction.py) har använts på följande sätt:

Hour     = NamedTuple("Hour",     [("number", int)]
Time     = NamedTuple("Time",     [("hour", Hour), ("minute", Minute)])
TimeSpan = NamedTuple("TimeSpan", [("start", Time), ("end", Time)])

Här definieras alltså en typ som heter Hour (vilket man måste ange två gånger, som en identifierare och som en sträng som talar om för den nya typen vad den heter). Den innehåller ett enda namngivet värde, number som är av typen int, men är ändå en tupel i och med att författaren genomgående använder NamedTuple för att skapa sina egna nya namngivna typer.

Sedan definieras Time, som innehåller två namngivna värden: hour som är av typen Hour, och minute av typen Minute. Därefter definieras den nya typen TimeSpan.

hour = ...
minute = ...
my_time_span = TimeSpan(hour, minute)
print(my_time_span.hour.number, ":", my_time_span.minute.number)

Här skapas ett nytt TimeSpan-värde, my_time_span, och sedan skriver man ut dess timme och minut genom att titta direkt på de namngivna värdena (vilket vi senare kommer att ändra på). Mer exempel på hur det fungerar kan man se i cal_abstraction.py.

Har du redan arbetat med objektorientering? Undrar du varför vi inte använder "vanliga" klasser och objekt i Python? Dels vill vi inte införa alla de extra begreppen nu (de kommer i TDDD78/TDDE30) utan håller oss till en sorts tupler, dels vill vi visa att dataabstraktion inte är specifikt för objektorientering utan är precis lika viktigt och precis lika möjligt att genomföra i icke objektorienterade språk!

Det här fungerar faktiskt utmärkt som vår representation av möten, i alla fall för tillfället. Men hur ska vi arbeta med de här nya datatyperna?

8.2.3. Att gå direkt på den konkreta representationen

Det är så klart alltid möjligt att låta all kod i hela almanackan gå direkt på den konkreta representationen som nästlade värden av de nya tupelbaserade typerna:

• För att skapa ett möte skapar man en Appointment med den önskade strukturen.

• Sedan skulle man kunna ta fram själva ärendedelen – informationsmässigt det som innehåller rubriken för mötet – genom att skriva app.subject.

• För själva rubriken "Lab prep in Java" får man gräva i app.subject.text.

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, och på ytan ser det inte så underligt ut, men det finns vissa problem:

• Om vem som helst kan skapa en Time finns det inget sätt att garantera att man alltid kontrollerar att värdena är rimliga. Vi kan skapa Time(Hour(42), Minute(-3)), men vad betyder det? Måste alla funktioner som arbetar med Time klara av negativa minuter?

• Om de som använder Time-typen titar direkt på my_time.hour och my_time.minute är vi fast i att lagra fält med timmar och minuter. Vad gör vi om vi istället vill ändra till att lagra tiden som sekunder sedan midnatt? Det finns ju redan annan kod som förväntar sig att komma åt data som värdefält. En del av den koden kanske andra personer har skrivit, så vi inte ens kan ändra den även om vi vill spendera all den tiden.

  Eller om just det exemplet verkar osannolikt: Vad händer om vi vill ändra vår Calendar-typ så att den lagrar data direkt i en databas och direkt sparar varje ändring i den databasen, för att garantera att informationen inte försvinner om systemet kraschar?

8.2.4. Att införa dataabstraktion

Det finns alltså goda anledningar till att undvika att använda datatypernas konkreta egenskaper direkt ifrån koden, och att separera "kontraktet" (vad en typ lovar att klara av) från implementationen (hur det faktiskt genomförs). För att undvika de problemen skapar vi ett lager av funktioner som hanterar just datalagringen.

• För att skapa ett möte använder man inte Appointment() direkt, utan anropar istället app = new_appointment(TimeSpan, Subject).

• För att ta fram själva ärendedelen anropar man app_subject(app).

• För själva rubriken "Lab prep in Java" får man anropa subject_text(app_subject(app)).

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 låta app_subject() slå upp information i en SQL-databas), behöver vi bara ändra i just funktionen app_subject(). Alla de andra potentiella funktionerna – från bokning i almanackan via filtrering/sökning till eventuella mobilinterface – fortsätter fungera som de gjort tidigare.

Vi har nu börjat definiera ett abstraktionslager. Målet med detta är bland annat att almanackans gränssnitt mot terminalfönstret (create, show_calendars, ...) inte ska behöva skrivas i ren Pythonkod som bara manipulerar tupler (med eller utan namn) och listor på låg nivå. Istället arbetar vi med ett mellanlager som ger oss tillgång till data utan att vi behöver veta hur dessa data egentligen var lagrade:

Vi behöver dock lite mer funktionalitet än bara de tre funktioner som vi gav exempel på ovan. Det ska vi titta på snart.

Vi ska strax diskutera vilka funktioner (operationer) som behövs för att slutföra vårt lager av dataabstraktion i almanackan. När detta blir klart kommer vi också ett steg närmare mot att ha definierat en abstrakt datatyp, även om vi inte går så långt att vi inför matematiska specifikationer av vad varje operation gör. Men innan detta måste vi se hur vi åtminstone kan beskriva den förväntade datatypen för funktionernas parametrar och returvärden.

Här arbetar vi återigen på en abstrakt specifikationsnivå. Vi bryr oss inte om vilket språk vi använder -- Python, Java, C++, assemblerkod, eller vad det nu kan vara. Vi måste ändå hålla koll på vad vi tänker oss att den konkreta implementationen ska göra, och därför skriver vi själva 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 str, int, med flera). Om vi ser på trädet från laboration 4 kan vi se att några typsignaturer är:

Vad det betyder är: "new_tree" 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 Tree och mängden Tree (därav krysset - kartetisk produkt) till mängden av Tree. 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 traverse.

8.2.6 Specifikation av funktionerna i dataabstraktionslagret

Den ursprungliga utvecklaren av almanackan har faktiskt också definierat typsignaturer för ett antal funktioner som hör hemma i dataabstraktionslagret. Här finns till exempel konstruktorer, igenkännare och selektorer (se studiematerialet). Här finns också annan funktionalitet som inte har att göra med just datalagringen, men som ändå kan sägas höra till datatypen – till exempel en funktion som testar om två TimeSpan överlappar varandra.

Här visar vi de viktigaste av de funktioner som utvecklaren hade specificerat. De här funktionerna ingår i den nedersta delen av abstraktionslagret, vars implementation oftast är beroende på exakt hur datatypen är implementerad i ett visst språk, men vars specifikation (som ni ser här) är oberoende av språk.

Den konkreta implementationen i just Python kan ni också hitta i cal_abstraction.py. Där kan ni också hitta ett antal andra funktioner ger mer funktionalitet till de olika datatyperna genom att anropa abstraktionslagret, och som därför inte är direkt beroende av den exakta representationen.

Hour – timme

Minute – minut

Time – klockslag (till exempel 15:45)

TimeSpan – tidsperiod (börjar ett klockslag, slutar ett klockslag)

Duration – tidsrymd (ej klockslag, utan en utsträckning, t.ex. 48h 15 minuter)

Day – dag

Month – månad

Date – datum

Subject – ärende (för ett möte)

Appointment – möte (har ett ärende, och en tidsperiod då det infaller)

CalendarDay – dagalmanacka

CalendarMonth – månadsalmanacka

CalendarYear – årsalmanacka

8.2.7. Att konkretisera typspecifikationer i Python -- type hinting

När vi hade diskuterat vilka abstrakta datatyper som behövdes (8.2.1) gick vi direkt vidare till att se hur dessa typer kunde konkretiseras i Python (8.2.2). Nu är frågan hur vi också ska konkretisera specifikationen av argumenttyper och returtyper i Python. Kan vi ens göra det?

Till skillnad från språk som Java, Haskell och Ada är inte Python statiskt typat. Det innebär att språket inte gör någon kontroll av att data av rätt typer kommer in i funktionerna innan 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 programmet körs och försöker göra något som man inte kan göra med textsträngar).

Men sedan Python 3.5 kan vi ändå arbeta med så kallad type hinting för att ge både läsaren och utvecklingsmiljöer en "vink" om vilka typer som förväntas. Det ser ut så här.

# new_appointment: TimeSpan × Subject -> Appointment
def new_appointment(span: TimeSpan, subject: Subject) -> Appointment:
    """
    Create and return a new Appointment with the given
    time span and subject.
    """
    ...

# app_span: Appointment -> TimeSpan
def app_span(app: Appointment) -> TimeSpan:
    """Return the TimeSpan of the given Appointment"""
    ...

# Funktion utan returvärde
def show_hour(h: Hour) -> None:
    """Print the parameter in an appropriate way, with no line break."""
    print(h, end="")

Detta har många fördelar.

• Den som vill anropa koden ser direkt vilka datatyper som förväntas skickas in och vad man ska få tillbaka.

• Den som vill vidareutveckla själva funktionen ser direkt vilka antaganden man kan göra om parametertyperna och vad man måste se till att uppfylla när man skickar tillbaka ett returvärde.

• Utvecklingsmiljöer som PyCharm kan ofta (men inte alltid) se om detta stämmer, så att de kan varna direkt om någon skickar in data av en typ som en funktion inte förväntar sig.

• Utvecklingsmiljöer kan också ta hänsyn till typinformationen när man vill komplettera/expandera kod -- om man till exempel skriver subject. och vill se vad man kan fortsätta med efter punkten.

Man måste vara medveten om att typerna inte automatiskt testas vid själva programkörningen. Det handlar just om hinting och inte om att Python har fått statisk typning som måste följas. Anropar vi new_appointment(10,[1,2,3]) kommer Python inte att klaga för att detta inte följer de förväntade typerna! Istället får vi troligen ett följdfel senare, när vi försöker göra något som ett värde inte stödjer -- som att hämta ut subject.text när subject==[1,2,3].

Därför kan vi vilja kontrollera typerna på egen hand, så att vi hittar eventuella buggar så snabbt som möjligt. I abstraktionslagret finns därför några funktioner som används för att explicit testa typer, till exempel:

def ensure_type(val, some_type: Type) -> None:
    """Assert that the given value is of the given type."""
    ...
    ...

Detta används i de flesta existerande funktioner i den ursprungliga utvecklarens implementation:

def new_appointment(span: TimeSpan, subject: Subject) -> Appointment:
    """Create and return a new Appointment with the given time span and subject."""
    ensure_type(span, TimeSpan)
    ensure_type(subject, Subject)
    return Appointment(span, subject)

8.2.8. Implementationens kodstruktur på högre nivå

Vi såg redan tidigare en illustration av den konkreta implementationens struktur med ett abstraktionslager i mitten. Beroende på hur man ser det kan man faktiskt identifiera ett lager till:

• Längst ner finns Python och dess kodbibliotek.

• För att hantera de olika delarna i almanackan har vi infört ett abstraktionslager. Vi kan se det som att vi har utökat språket Python med nya typer och nya funktioner som opererar på dessa.

• 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.

Varje del i detta finns alltså i en separat kodfil:

8.2.9. Inte modifiera indata!

Listan på funktioner i dataabstraktionslagret innehåller bland annat funktionen cd_plus_appointment: Appointment × CalendarDay -> CalendarDay. Som namnet och specifikationen antyder tar den här funktionen in en kalenderdag och returnerar en ny kalenderdag där ett möte har lagts till. Detta förtydligas i dokumentationen för den konkreta implementationen:

Returns a copy of the given CalendarDay, where the given Appointment
has been added in its proper position.

Funktionen ändrar alltså inte på sina indata, och den modifierar överhuvudtaget inget yttre / externt tillstånd. Detta gäller för alla funktioner i abstraktionslagret, och även alla andra funktioner utom de användargränssnittsfunktioner (i cal_ui.py) som lagrar själva kalendrarna i en global variabel – de funktionerna måste ju trots allt få ändra den globala variabeln.

Dina egna funktioner får inte heller ändra på indata!

Däremot går vi inte hela vägen till strikt funktionell programmering: En funktion får ändra på sina interna data medan den håller på att konstruera dem. Det går alltså bra att internt bygga upp en nylista och lägga till nya element i den medan funktionen körs, eller att loopa över alla element i en lista.

8.3. Arbeta med almanackans abstraktionslager

Nu är det dags att börja skriva om de problematiska delarna av almanackan. Det första steget är att lära sig arbeta med almanackans abstraktionslager.

För att kunna skilja våra olika datatyper åt har vi infört en uppsättning datatyper som hjälper oss att paketera information. Precis som vi har sett tidigare talar datatyperna om vilken typ av objekt det rör sig om, och som vanligt kan detta testas med isinstance(). Våra konstruktorer, som t.ex. new_time(), ä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. Både av den anledningen och för att underlätta framtida ändringar är det viktigt att alltid gå genom konstruktorerna när vi ska skapa nya värden av en given typ.

I och med att vi använder NamedTuple lagras information rent konkret som namngivna fält i en sorts tupler. Det gör också att vi tekniskt sett kan komma åt dessa data genom t.ex. my_time.hour. Det ska vi inte göra, utom just i dataabstraktionslagret! Där vi kan, ska vi använda selektorerna istället, t.ex. time_hour(my_time).

Det är alltså enbart de primitiva funktionerna i filerna cal_abstraction.py och lab8.py som ska känna 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.

>>> month_of_january = new_month("jan")
>>> month_of_january
Month(name='january')
>>> month_name(month_of_january)
january
>>> isinstance(month_of_january, Month)
True
>>> isinstance("january", Month)
False

I exemplet ovan ser vi hur funktionen new_month returnerar ett värde av typen Month. Den interna representationen har en egen utskriftsfunktion som representerar månaden som Month(name='january'), men det är inget som vi ska fästa något avseende vid utom att det kan vara praktiskt vid debugging. 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 802 Testa de olika primitiva funktionerna och se att du kan skapa olika slags objekt. Pröva till exempel att skapa följande objekt med hjälp av lämpliga konstruktorer:

• Skapa klockslaget (Time) 13:15 och lagra värdet i den globala variablen t1315.
• Skapa tidsperioden (TimeSpan) 13:15-15:00 och lagra värdet i den globala variabeln ts1315.
• Skapa en tom CalendarDay och lägg sedan till två möten: ett kl 8:15-9:30 för "Redovisning av uppgift", samt ett 13:15-15:00 med "Seminarium i Python". Lagra värdet i den globala variabeln cd15.

>>> create("Jayne")
A new calendar by the name Jayne has been created.
>>> book("Jayne", 20, "sep", "12:00", "14:00", "Rob train")
The appointment has been booked.
>>> book("Jayne", 20, "sep", "15:00", "16:00", "Escape with loot")
The appointment has been booked.
>>> show("Jayne", 20, "sep")
20 september
===========
12:00-14:00 Rob train
15:00-16:00 Escape with loot
>>> remove("Jayne", 20, "sep", "15:00")
Appointment removed.
>>> book("Jayne", 20, "sep", "15:00", "16:00", "Return loot")
The appointment has been booked.
>>> show("Jayne", 20, "sep")
20 september
===========
12:00-14:00 Rob train
15:00-16:00 Return loot

8.4. Algoritmer och testning

De primitiva funktionerna och "bra att ha"-funktionerna i cal_abstraction.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 CalendarDay? Vi vet att en CalendarDay 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 (de bokade och de där man vill hitta lediga tider) kan starta, sluta och överlappa varandra på olika sätt. Därför ska ni i nästa uppgift systematisera testningen genom att konstruera egna testfall.

OBS! 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.

>>> create("Jayne")
A new calendar by the name Peter has been created.
>>> book("Jayne", 20, "sep", "12:00", "14:00", "Rob train")
The appointment has been booked.
>>> book("Jayne", 20, "sep", "15:00", "16:00", "Escape with loot")
The appointment has been booked.
>>>> show_free("Jayne", 20, "sep", "08:00", "19:00")
08:00-12:00
14:00-15:00
16:00-19:00

Överkurs: Traverse (för intresserade)

OBS! Detta avsnitt behövs inte för att klara kursen.

Vad för typ har den högre ordningens funktion traverse? Vi kan påminna om att man anropar funktionen i stil med traverse( Tree, inner_node_fn, leaf_fn, empty_tree_fn), så den kommer att vara av typ Tree × 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

traverse: Tree × (?? -> ??) × (?? -> ??) × (?? -> ??) -> ngt.

Vad är dessa typer? För att se det måste vi räkna ut typerna för inner_node_fn, leaf_fn och empty_tree_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 empty_tree_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:

Och därmed får vi:
traverse: Tree × (Integer × a × a -> a) × (Integer -> a) × (-> a) -> a

Hoppa tillbaka.

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2023-11-13