729G46 Informationsteknologi och programmering

Föreläsning Tema 2

Johan Falkenjack, johan.falkenjack@liu.se

Föreläsningsöversikt, FÖ 2

• Recap Tema 1
• Programflöde
  • Översikt
  • Funktioner och scope
  • Rekursion och iteration
• Övrigt smått och gott i mån av tid
  • Parprogrammering

Reflektioner efter Tema 1

• Vad var svårt?
• Vad var lätt?
• Lade jag tid på rätt saker och i rätt ordning?

Jag fattar inte ett dugg efter Tema 1, hur körd är jag?

Tema 1

• Datorn, operativsystemet och filsystemet

• Beståndsdelar i ett program:

  • värden, datatyper: int, float, str, list, tuple
  • variabler, operatorer, uttryck
  • satser, nyckelord
  • funktioner, argument, returvärden
  • block

Tema 2: Programflöde

Tema 2

• Styra flöde i program
  • Funktioner och scope
  • Repetition i program
  • Bearbetning av värden i sekvens

• Diskret matematik
  • Mängdlära i Python

Funktioner och scope

Tips: http://pythontutor.com

Anatomilektion

Vårt exempel

• Förklara vad funktionen gör
• Nämn syntax highlight

Funktionsdefinition

• Sammansatt sats (compound statement)
• En klausul

Funktionsdefinition - header

• Börjar med nyckelordet def följt av funktionens namn och en parameterlista inom parentes
  • Inte samma sak som datatypen list

Funktionskropp

• Formellt: sammansatta satsens svit
• Körs ej vid definition
  • Eventuella fel upptäcks inte än

Funktionsanrop

• Ett uttryck, till skillnad från definitionen som bara är en sats.

Retursats

• När vi betraktar ett funktionsanrop som ett uttryck:
  • Returvärdet är det värde som uttrycket får när det evalueras.

Argument och parametrar

• Notera att argument refererar till faktiska värden. De kan finnas i variabler, beräknas via uttryck, eller skickas med som literaler som i det här fallet.
• Parametrar är de variabler inne i funktionen som kommer innehålla argumentvärdena.

def triangle_area(height, width):
    area = (height*width)/2
    return area

triangle_area(7, 9)

31.5

Anropsstacken (eng. call stack)

Datastrukturen stack

• En stapel av objekt:
  • Lägg till objekt på toppen (eng: push)
  • Ta bort översta objektet (eng: pop)
  • Alla andra objekt i stacken är otillgängliga
• Liknelse: Lista där nya element bara kan läggas till i slutet (append), och bara det sista elementet kan tas bort (pop).

Källa: Wikipedia

• Inte något vi behöver hantera manuellt, men vi måste vara medvetna om den och vad den innebär.
• Mycket snack för något som verkar ganska irrelevant.
• Intressant först när funktion anropas

Programflöde - funktionsanrop

• Ett pythonprogram tolkas sekventiellt av pythontolken.
• Vi tänker oss att vi har en körmarkör som pekar på vad det som ska utföras näst
• När pythontolken ser ett funktionanrop görs följande
  1. eventuella argument i funktionsanropet beräknas
  2. eventuella argument skickas till den anropade funktionen och en frame för anropet skapas på toppen av stacken
  3. den anropade funktionens funktionskropp utförs sekventiellt - körmarkören flyttas till funktionskroppen
  4. när funktionen är klar tas dess frame bort och
  5. körmarkören flyttas tillbaka dit anropet påträffades och funktionens returvärde "ersätter" funktionsanropet

Exempel

print("Första raden")

def calc_double(value):
    new_value = value * 2
    print("värdet på value:", value)
    print("värdet på new_value:", new_value)
    return new_value

def main():
    print("Nu körs main()")
    value = 5
    double = calc_double(value)
    print("Dubbla värdet är", double)
 
main()
print("Nu är programmet slut!")

Första raden
Nu körs main()
värdet på value: 5
värdet på new_value: 10
Dubbla värdet är 10
Nu är programmet slut!

(http://pythontutor.com)

• Beroende på tid, kör exemplet i Pythontutor eller lämna det som övning.

Scope

• Den kontext där en variabel är giltig.
• En variabel som skapats inne i en funktion kallar vi för lokal variabel
• Scopet för en lokal variabel är den frame som skapades vid funktionsanropet.
  • Dvs den lokala variabeln är endast giltig och tillgänglig i funktionsanopets frame.
• Variabler med samma namn kan existera i olika scopes med olika värden.

• Håll tungan rätt i mun.

Lokala variabler

• Funktionens parametrar blir lokala variabler i funktionen, med argumenten som initialt värde.

def calc_double(value):
    new_value = value * 2
    print("värdet på value inne i calc_double:", value)
    print("värdet på new_value:", new_value)
    return value

value = 10
print("värdet på value utanför:", value)
calc_double(value)

värdet på value utanför: 10
värdet på value inne i calc_double: 10
värdet på new_value: 20

10

print("värdet på value utanför:", value)

värdet på value utanför: 10

print("värdet på new_value:", new_value)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[7], line 1
----> 1 print("värdet på new_value:", new_value)

NameError: name 'new_value' is not defined

Sekvenser av värden

När behövs en sekvens av värden?

Vad kan representeras som en sekvens av värden?

Sekventiell information och datorn

• Minnesplatser i RAM.
• Tecken, ord, meningar, stycken, kapitel och dokument lagrade i filer.
• Värden från olika sensorer över tid.
• Inlägg i ett flöde i sociala medier.

• Vi har redan bearbetat tupler, listor och strängar i Python

Programmatisk bearbetning av sekvenser

De flesta beräkningarna och processer i datorer är sekventiella

• Information läses sekventiellt från start till slut.
• Vad får detta för konsekvenser?

Vem är längst?

Vem är längst?

A = ("A", 120)
B = ("B", 100)
C = ("C", 160)

if A[1] > B[1]:
    tallest = A
else:
    tallest = B
if C[1] > tallest[1]:
    tallest = C
    
print("The tallest person is " + tallest[0])

The tallest person is C

Vem är längst?

Vem är längst?

Från datorns perspektiv

• Har datorn en översiktsbild? Kan datorn titta på en hel sekvens på en gång?
  

• Datorn kan "titta" på ett element i taget, möjligtvis två precis vid en jämförelse
• Vi måste tillhandahålla arbetsminne
• Datorn kommer inte ihåg något "automatiskt"

Rekursion

Upprepning utan ny syntax.

• Vilka har hört talas om rekursion förut?
• I vilket sammanhang?

Droste-effekten, rekursion i bild och form

Rekursiva flaggor

Det finns flera!

Konceptet rekursion

• Självlikhet eller självreferens.
• Fenomen som i sin struktur innehåller en mindre variant av sig själva.
  • Träd, med grenar, som har grenar, som har grenar...
  • Världskarta, som består av kartor över länder, som innehåller kartor över städer, som innehåller kartor över kvarter...
  • En mening i naturligt språk kan innehålla en bisats, som kan innehålla en bisats, som kan innehålla en bisats...
• Processer som innehåller sig själva som ett delsteg.
  • Surdeg, där den viktigaste ingrediensen är?
  • Att gå upp för en trappa med $n$ steg, som består av att först gå upp för en trappa med $1$ trappsteg...

Vad har detta med programmering att göra?

• Redan tidigare: Kodblock som innehåller kodblock.

• Nu: Rekursiva processer.
  • Funktioner som direkt anropar sig själva.

• Sen: Rekursiva datastrukturer.
  • T.ex. listor som kan innehålla listor, som kan innehålla listor, som kan...
  • Grafer, där varje möjlig delgraf i sig är en graf.
    • T.ex. använder vi ofta grafer för att representera kartor.

• I framtida kurser:
  • Funktioner som i en ändlig kedja av funktionsanrop anropar sig själva, t.ex. funktion $A$ anropar funktion $B$ och funktion $B$ i sin tur anropar $A$.
  • Behandling av naturliga språk, som (om Chomsky har rätt) alltid är rekursiva eller (om Chomsky har fel) i alla dokumenterade fall utom 1 är rekursiva.

Komponenter i en enkelrekursiv funktion

def rec_fun(input):
    if *stoppvillkor*:
        return *trivialt basfall*
    else:
        return do_something(input) *kombinerat med* rec_fun(*ett värde härlett från input*)

• Inte en speciell syntax, bara ett generellt mönster.
• Vad gör denna enkel? Vi gör som mest ett rekursivt anrop varje gång funktionen exekveras.

Summera en lista av heltal med rekursion

• Vi vill summera listan [1, 2, 75, 6, 7]

def sum_list_rec(values):
    if values == []:
        return 0
    else:
        return values[0] + sum_list_rec(values[1:])

print(sum_list_rec([1, 2, 75, 6, 7]))

print(sum_list_rec([1, 2, 75, 6, 7, 75, 6, 7]))

91
179

if values == []:
    return 0
else:
    return values[0] + sum_list_rec(values[1:])

• Stoppvillkor och trivialt basfall.
• Var är do_something?
• Kombinationsoperation.
• Rekursionssteg.

Jaha, men hur kom vi på det då?

Rekursiv problemlösning

• För att lösa ett problem rekursivt, behöver vi formulera eller dela upp det på ett sådant sätt så att delarna är enklare varianter av det större problemet.

• Om vi har problemet summera talen 1, 2, 75, 6 och 7. Att uttrycka det som 1 + 2 + 75 + 6 + 7 är att försöka lösa allt på en gång.
• Ett alternativt sätt är uttrycka det som 1 + summan av de resterande talen; 2, 75, 6, 7
• Summan av de resterande talen i sin tur kan vi uttrycka på samma sätt, 2 + summan av de resterande talen; 75, 6, 7
• Vi har hittat ett sätt att formulera problemet så att vi kan tillämpa samma lösning på mindre och mindre varianter av samma problem.

Iteration - Ny syntax för upprepning

I folkmun ofta kallat att loopa

• Används för att köra samma kod flera gånger
• Exempel
  • skriva ut varje element i en lista
  • addera ett tal till en variabel tills det överstiger ett visst värde
  • flytta fram figuren tills det nuddar en vägg

Två iterationssatser i Python

• for-satsen
  • Utför ett stycke kod för varje element i en sekvens.
  • Förutsätter att vi kan specificera en sekvens att loopa eller iterera över.
• while-satsen
  • Som en if-sats, men blocket upprepas så länge som villkoret är uppfyllt.
  • Mer generell än for.

for-loopen

for element in a_sequence:
    # Code to run for every element in a_sequence

• Varje exekvering av kodblocket kallas för en iteration.
• I varje iteration kommer element innehålla det aktuella värdet i sekvensen.

• Loopen slutar när vi gått igenom hela a_sequence
• OBS! variablerna behöver inte heta element och a_sequence

Gå igenom en lista med for

names = ["Ada", "Beata", "Cecilia", "Diana"]


for name in names:
    print(name)

Ada
Beata
Cecilia
Diana

• Gå igenom alla element i names.
• Det aktuella elementet refereras till via variabeln name i loopen.
• Notera hur mycket enklare än motsvarande while-loop.

Gå igenom en sträng med for

word = "fantastic"

for vadsomhelst in word:
    print(vadsomhelst)

f
a
n
t
a
s
t
i
c

• Gå igenom alla tecken i word.
• Det aktuella tecknet refereras till via variabeln char i loopen.

Byt ut bokstäver

word = "fantastic"
new_word = ""

for char in word:
     if char == "a":
         new_word += "å"
     elif char == "s":
         new_word += "l"
     else:
         new_word += char
print(new_word)

fåntåltic

• Variabeln new_word är en så kallad ackumulatorvariabel, dvs en variabel vars värde stegvis byggs upp under iterationen.
• Kan vara nästan vilken klass som helst, sträng, lista, tal, osv.

Funktionen range

• Skapar en "virtuell lista med heltal" (tekniskt sett en sk generator *) som man kan använda som en vanlig lista med heltal.
• range(stop): Börja från 0, öka med 1 och fortsätt generera heltal så länge som heltalet är mindre än stop
• range(start, stop): Börja från start, öka med 1 och fortsätt generera heltal så länge som heltalet är mindre än stop
• range(start, stop, step): Börja från start, öka med step och fortsätt att generera heltal så länge som heltalet är mindre än stop
• För att få en riktig lista kan vi skicka returvärdet från range till funktionen list, t.ex. list(range(10))

• Jämför med slice: seq[start:stop:step]

* En generator håller bara ett värde i taget i minnet, och genererar nästa värde vid behov, istället för att lagra hela sekvensen. Praktiskt för väldigt långa sekvenser.

Funktionen range

list(range(10))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

list(range(4,6))

[4, 5]

list(range(10, 101, 10))

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

list(range(10, 110, 10))

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

list(range(10, 0, -1))

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

list(range(10, 3, -2))

[10, 8, 6, 4]

for med range

# Skriv ut siffrorna 0 till 9 (10 siffror)
for i in range(10):
    print(i)

0
1
2
3
4
5
6
7
8
9

for med range över längden på en sekvens

Ofta överflödigt:

names = ["Adam", "Bethany", "Chris"]
# Skriv ut elementen i listan names
for i in range(len(names)):
    print(names[i])

Adam
Bethany
Chris

• Lämpligare och enklare att loopa direkt över namnen.

for med range över längden på en sekvens

men ibland praktiskt:

names = ["Adam", "Bethany", "Chris"]
# Skriv ut elementen i listan names
for i in range(len(names)):
    print(names[i] + " likes " + names[(i+1) % len(names)])

Adam likes Bethany
Bethany likes Chris
Chris likes Adam

(För den som vill se en mer "pythonic" approach, kolla upp funktionen enumerate.)

while-loopen

• Satserna i blocket som tillhör while-loopen upprepas tills while-satsens villkor blir falskt.
• Efter sista satsen i blocket börjar loopen om från blockets första sats.
• Varje upprepning loopen gör kallas för en iteration.

while boolean:
    # Code to repeat

Exempel

• Räkna upp till 10.

count = 0
while count <= 10:
    print(count)
    count = count + 1
print("Efter loopen är count: " + str(count))

0
1
2
3
4
5
6
7
8
9
10
Efter loopen är count: 11

• Notera att vi använder <= för att få med talet 10.
• Vilket värde har count efter att loopen är klar?

Exempel

# evig loop
x = 0
while x <= 10:
    print("En dator blir aldrig uttråkad.")
    print(x)

Avbryta en loop, eller gå till nästa iteration i en loop

• Nyckelordet break användas för att avbryta en loop (hela loopen).
• Nyckelordet continue används för att hoppa över resten av loop-blocket och börja om igen från början (av nästa iteration)

count = 0
while count < 10:
    if count == 3 or count == 5:
        count += 1
        continue

    if count > 7:
        print("Nu orkar jag inte mer." + "(count: " + str(count) + ")")
        break
    elif count > 3:
        print("Är vi framme snart?" + "(count: " + str(count) + ")")
    elif count > 4:
        print("Har vi kört vilse?" + "(count: " + str(count) + ")")
    else:
        print("Det här är roligt!" + "(count: " + str(count) + ")")
    count += 1

Det här är roligt!(count: 0)
Det här är roligt!(count: 1)
Det här är roligt!(count: 2)
Är vi framme snart?(count: 4)
Är vi framme snart?(count: 6)
Är vi framme snart?(count: 7)
Nu orkar jag inte mer.(count: 8)

• Variabeln count kallas kontrollvariabel eller loop control variable på eng.
• Notera att vi inte kan skriva if count == 3 or 5

Ska man använda for, while eller rekursion?

• Beror på situationen.
• Rekursion är mest generellt och kan (i tema 3) hantera situationer där bara en loop inte räcker, men är slött och begränsas av anropsstackens maximala storlek.
• Kan vi definiera en sekvens att loopa över så bör vi använda for, det är mer lättläst och det är mindre risk att göra fel.
• Vi använder while när vi inte kan definiera en sekvens i förväg, t.ex. för att antalet iterationer beror på någon form av slumpning, en mer komplicerad beräkning eller, värst av allt, input från en mänsklig användare 😱

Tips för parprogrammering

(https://www.wikihow.com/Pair-Program)

Förare och observatör

Växla ofta

• Byt person som sitter vid tangentbordet med jämna mellanrum
  • Men INTE för att ni kört fast. "Nä, men asså såhär! ___KNYCK___"
  • Viktigt att skriva själv, inte bara sitta bredvid. Risken är att ni inte märker fundamentala kunskapshål förrens på tentan
• Båda äger koden.

Hur är man en bra förare?

• Tänk högt medan du skriver och förklara varför du skriver som du gör.
• Lyssna på observatören.

Hur är man en bra observatör?

• Var aktiv
  • se till att ni jobbar med det ni ska
  • granska koden
  • fundera på större designfrågor än raden som skrivs just nu (mer aktuellt ju längre fram i kursen vi kommer)
• Var öppna för input från varandra, och kommunicera produktivt
• Misstag/problem i koden är egenskaper hos koden, inte personliga egenskaper hos den som skrivit koden

Fira när ni har löst ett problem

Felsökning

Olika typer av fel

• Syntaxfel: Koden bryter mot programspråkets grammatiska regler, exempelvis
  • använda reserverade ord på fel sätt, t.ex. att döpa en variabel till return eller en funktion till if
  • saknat kolon i slutet av if-sats
• Runtime-fel: Fel som uppstår vid körning och resulterar i en krasch, exempelvis
  • Division med 0
  • Försöka läsa en fil som inte existerar
• Logiska fel: Fel som uppstår när programmet fungerar men inte gör vad som var tänkt.
  • Felaktig operatorprioritet, t.ex. råka skriva x + y * 5 när man menade (x + y) * 5
  • Off-by-one-fel, t.ex. glömma bort att indexering börjar på 0, inte 1

Spårutskrifter

• Utskrift av variabelvärden
• Utskrift av text för att visa var i koden pythontolken befinner sig

• Hur vi skrev ut variabeln value på olika ställen för att se vilket värde den hade i en viss kontext

Felsökning av olika typer av fel

• Syntaxfel: kontrollera syntax, antal blanksteg, parenteser, kolon, etc.
• Runtime-fel: tolka felmeddelandet, lägg till spårutskrifter
• Logiska fel i programmet: försök att isolera felet, på vilka ställen i koden används variabeln/funktionen som har med felet att göra? Lägg till spårutskrifter.

• När det är svårt att hitta felet: det är bättre att vara noggrann och dubbelkolla med spårutskrifter än att göra antaganden om att man gjort rätt.