TDDE44 Programmering, grundkurs

Föreläsning 2.1-2.2

Johan Falkenjack, johan.falkenjack@liu.se

• Ofiltrerad.

Föreläsningsöversikt FÖ 2.1-2.2

• ~Programflöde - Anropsstacken och scope~
• Upprepning
  • ~Rekursion~
  • Iteration
    • Fördefinierat antal upprepningar - for
    • Generell iteration - while
• Om vi hinner, lite om:
  • Felsökning
  • Parprogrammering
  • Programmeringsparadigm
  • Läsa/skriva textfiler i Python

Kort repetition: Anropsstacken

• En stack, datastruktur där vi bara kan ta bort eller lägga till element "på toppen", eller mer generellt, i ena änden.
  • Följer principen: First in, last out eller FILO.
  • (Vi kommer senare att stöta på datastrukturen kö, eller queue som följer FIFO eller First in, first out.)
• Anropsstacken, en stack med omgivningar, eller frames, som håller koll på:
  1. Var olika namn och bindningar mellan namn och värden existerar, dvs. variablers scope.
  2. Var i programflödet exekveringen av koden just nu befinner sig och
  3. vart exekveringen skall fortsätta när den aktuella funktionen returnerar.

Kort repetition: Rekursion

• Upprepning med hjälp av funktionsanrop och anropsstacken.
• En funktion anropar sig själv med enklare och enklare delproblem tills vi når ett trivialt basfall där svaret är givet utan ytterligare anrop.
• För varje anrop läggs en ny frame på stacken som håller reda på hur resultaten på de lösta delproblemen skall returneras tillbaka genom alla anropen.

Rekursiv kontra iterativ processlösning

• Rekursiv process: Kombinationen av lösningarna till alla delproblem utförs först när vi nått basfallet. Det rekursiva anropet måste ske innan dess returvärde kan kombineras med lösningen på det aktuella delproblemet.
• Iterativ process: Lösningarna på delproblemen kombineras i en ackumulator allt eftersom de beräknas. Det rekursiva anropet är alltid det sista som utförs i funktionen.
• Olika problem kan lämpa sig bättre för ena eller andra approachen, i många fall går båda lika bra och i vissa komplexa fall blandar vi båda teknikerna.
• Ofta är returvärdet i basfallet i den rekursiva processlösningen samma värde som startvärdet på ackumulatorn i den motsvarande iterativa processlösningen.

def tallest(heights):
    if heights == []:
        return 0
    tallest_in_rest = tallest(heights[1:])
    if heights[0] > tallest_in_rest:
        return heights[0]
    else:
        return tallest_in_rest
print("tallest([10, 79, 41])", "->", tallest([10, 79, 41]))

• Rekursiv processlösning.
• Det rekursiva anropet sker innan returvärdet "kombineras" (här är det inte så mycket en kombination som en antingen-eller, men principiellt är det samma sak).
• Resultatet byggs upp först när de rekursiva anropen returnerar, "på vägen upp" eller "på vägen tillbaka", och alla de rekursiva anropen kommer alltså inte nödvändigtvis att returnera samma värde.

def tallest_iter(heights, tallest_found):
    if heights == []:
        return tallest_found
    if heights[0] > tallest_found:
        return tallest_iter(heights[1:], heights[0])
    else:
        return tallest_iter(heights[1:], tallest_found)
print("tallest_iter([10, 79, 41])", "->", tallest_iter([10, 79, 41]))

• Iterativ processlösning.
• Resultatet byggs upp i en ackumulator, tallest_found, "på vägen ner".
• Det rekursiva anropet är det sista som sker i funktionen och alla anrop kommer alltså alltid att returnera värdet av nästa anrop, dvs. alltid det slutgiltiga värdet på tallest_found.

Prova att köra både tallest och tallest_iter i Python Tutor.

Iteration - Upprepning utan nya anrop

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 den nuddar en vägg

Rekursion kan lösa alla problem - i teorin

• Alan Turing (känd från filmer som the Imitation Game etc.) beskrev en universell maskin som kunde beräkna "det mesta", inklusive beskriva och implementera sin egen funktion, sendermera kallad den Universella Turingmaskinen.
• Alonzo Church (mindre känd men sedermera Turings handledare när Turing doktorerade) hade beskrivit $\lambda$-kalkylen, en matematisk formalism som också kunde beräkna "det mesta".
• Church-Turing-satsen säger att $\lambda$-kalkylen och den Universella Turing-maskinen är ekvivalenta.
• En följd av detta är att rekursion är Turingkomplett, dvs. alla problem som kan lösas av en dator kan, i teorin, lösas med rekursion.
• Beviset lämnas som övning (efter att ha läst t.ex. TDDD85 Formella språk och automatateori och ytterligare några kurser i beräkningsteori).

Två iterationssatser i Python

• for-satsen
  • Utför ett stycke kod för varje element i en sekvens.
• while-satsen
  • Som en if-sats, men blocket upprepas så länge som villkoret är uppfyllt.

for-loopen

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

• Vi säger att for-loopen loopar över en sekvens.
• I varje upprepning, varje iteration, innehåller loopvariabeln element det aktuella värdet i sekvensen.
  • OBS! Namnet element är helt godtyckligt och kan sättas till vad som helst. Lämpligen väljer vi oftast ett mindre abstrakt namn som tydligt beskriver vad de enskilda elementen faktiskt representerar.
• Ingen manuell kontrollvariabel.

• 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

• Notera att loopvariabeln här heter name, som vi har valt eftersom vi loopar över en lista med namn.

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

Längsta längden med for

lengths = [120, 100, 160, 124, 112, 150, 188, 134]
tallest_found = 0

for length in lengths:
    print("Längsta hittills:", tallest_found)
    if length > tallest_found:
        tallest_found = length
 
print("Längsta i hela listan:", tallest_found)

Längsta hittills: 0
Längsta hittills: 120
Längsta hittills: 120
Längsta hittills: 160
Längsta hittills: 160
Längsta hittills: 160
Längsta hittills: 160
Längsta hittills: 188
Längsta i hela listan: 188

for length in lengths:
    if length > max_length:
        max_length = length

• Notera att vi inte behövde varken funktion eller funktionsanrop

Gå igenom en sträng med for

• Här har vi valt namnet char för loopvariabeln eftersom vi loopar över delsträngar bestående av enskilda tecken, characters, i strängen.

word = "fantastic"

for char in word:
    print(char)

f
a
n
t
a
s
t
i
c

# För bara halva word
for char in word[len(word)//2:]:
    print(char)

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

• Variabeln new_string är vår ackumulatorvariabel, dvs. en variabel vars värde stegvis byggs upp under iterationen.
  • På samma sätt som vi använde en ackumulatorvariabel i en iterativ processlösning när vi använde rekursion för upprepningen.
• Kan vara nästan vilken klass som helst, sträng, lista, tal, osv.
• I det här fallet vill vi ta bort alla svenska tecken ur en sträng.

swe_string = "Sträng med svenska tecken som å, ä och ö."
new_string = ""

for char in swe_string:
    if char == "å":
        new_string = new_string + "a"
    elif char == "ä":
        new_string = new_string + "a"
    elif char == "ö":
        new_string = new_string + "o"
    else:
        new_string = new_string + char
            
print(new_string)

Strang med svenska tecken som a, a och o.

if char == "å":
        new_string = new_string + "a"
    elif char == "ä":
        new_string = new_string + "a"
    elif char == "ö":
        new_string = new_string + "o"
    else:
        new_string = new_string + char

Byt ut bokstäver, något kortare

• Vi kan använda operatorn in, inte att förväxla med nyckelordet in i en for-sats, för att kontrollera för både å och ä samtidigt, eftersom vi ska göra samma sak i båda de fallen, lägga till ett a:

swe_string = "Sträng med svenska tecken som å, ä och ö."
new_string = ""

for char in swe_string:
    if char in "åä":
        new_string = new_string + "a"
    elif char == "ö":
        new_string = new_string + "o"
    else:
        new_string = new_string + char
            
print(new_string)

Strang med svenska tecken som a, a och o.

Påminnelse om strängar och deras element

• Varje element i en sträng är i sig en sträng, Python har ingen separat datatyp för enskilda tecken.
• Alla element i en sträng är alltså en sträng med längden 1.
• Litteralerna för tecken kan dock ibland röra till det för oss.
  • Kom ihåg att en litteral bara är en textuell representation av det underliggande värdet.
  • En litteral för vad som i Python räknas som ett enskilt tecken kan ibland behöva skrivas med mer än ett tecken på skärmen. T.ex. för specialtecken som "\n", en radbrytning:

print("Längden av en radbrytning:", len("\n"))
print("Längden av tre radbrytningar:", len("\n\n\n"))

Längden av en radbrytning: 1
Längden av tre radbrytningar: 3

chars_in_string = []
for char in "\n\n\n":
    chars_in_string = chars_in_string + [char]
print('Tecken i strängen "\\n\\n\\n":', chars_in_string)

Tecken i strängen "\n\n\n": ['\n', '\n', '\n']

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))

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, -2))

[10, 8, 6, 4, 2]

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

[10, 8, 6, 4]

Reglerna för range motsvarar reglerna för slice

• sequence[start:stop:step]
• range(start, stop, step)
• step kan vara positiv eller negativ men är 1 om inget annat anges.
• Om start > stop så måste step vara negativ annars är resultatet tomt.
• Både range(start, stop) och sequence[start:stop] indikerar halvöppna intervall $[start, stop)$.
  • Med andra ord, alla index $i$ sådana att $start \leq i \lt stop$.

# För att illustrera använder vi följande sekvens:
sequence = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(list(range(10)), "==", sequence[:10])
print(list(range(4, 8)), "==", sequence[4:8])
print(list(range(6, 2, -2)), "==", sequence[6:2:-2])
# Men range behöver ingen fördefinierad sekvens att utgå ifrån utan genererar de värden som efterfrågas:
print(list(range(8, 15)), "!=", sequence[8:15])

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[4, 5, 6, 7] == [4, 5, 6, 7]
[6, 4] == [6, 4]
[8, 9, 10, 11, 12, 13, 14] != [8, 9]

for med range

# Skriv ut siffrorna 0 till 9 (10 siffror)

for i in range(0, 10, 1):
    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

• Här hade det varit lämpligare 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 eller ännu hellre zip.)

while-loopen

• Som en if-sats, men upprepad så länge villkoret är sant.
• Satserna i blocket som tillhör while-loopen upprepas tills while-satsens villkor blir falskt.
• Först kontrolleras om villkoret är sant.
  • Om villkoret är sant utförs koden i blocket en gång, sedan kontrolleras villkoret igen, osv.
  • Om villkoret inte är sant "hoppar" exekveringen av koden till efter while-satsens kodblock precis som för en if-sats.
• Varje upprepning eller "varv" loopen gör kallas för en iteration precis som för for.

while boolean:
    # Code to repeat

Exempel

• Räkna upp till 10.
• Vi använder variabeln count som kontrollvariabel (eng. loop control variable), eller loopvariabel.
  • Till skillnad från i for-loopen behöver vi initiera och räkna upp loopvariabeln manuellt.

count = 0
while count < 10:
    print(count)
    count += 1
    

0
1
2
3
4
5
6
7
8
9

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

Exempel

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

Längsta längden med while

lengths = [120, 100, 160, 124, 112, 150, 188, 134]
tallest_found = 0

index = 0
while index < len(lengths):
    if lengths[index] > tallest_found:
        tallest_found = lengths[index]
    index = index + 1

print(tallest_found)

188

index = 0
while index < len(lengths):
    if lengths[index] > max_length:
        max_length = lengths[index]
    index = index + 1

Varför while när for finns?

• För att kunna använda for krävs att vi har eller kan fördefiniera en sekvens.
• Exempel: Vi vill slå en 6-sidig tärning tills summan är minst 20.
  • Vi använder modulen random för att slumpa ett tal mellan 1 och 6 som representerar ett tärningsslag.
  • Variabeln total utgör både kontrollvariabel/loopvariabel och ackumulatorvariabel.

import random
total = 0
rolls = []

while total < 20:
    roll = random.randint(1, 6)
    rolls = rolls + [roll]
    total = total + roll
 
print(total, rolls)

22 [1, 1, 6, 6, 5, 3]

while total < 20: roll = random.randint(1, 6) total += roll print("Roll is:", roll, "( total is:", total, ")\n")

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

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

• Nyckelordet break används 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 (nästa iteration)

for count in range(10):
    if count == 3 or count == 5:
        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) + ")")    

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

När ska man välja for resp. while?

• for
  • När vi har en fördefinierad sekvens (t.ex. en lista eller en sträng), eller
  • När vi kan generera sekvensen (t.ex. med range eller enumerate).
• while
  • När vi inte i förväg kan definiera en sekvens att loopa över.
  • 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 😱
• Heurestik att använda tills ni börjar få en intuition:
  1. Använd for om det går.
  2. Annars, fundera på om for + range fungerar.
  3. I sista hand, använd while.

Varför introducerade vi enkelrekursion när for och while finns?

• Krävde ingen ny syntax, bara funktionsanrop och villkorssatser som vi redan avhandlat.
• Inte alla programmeringsspråk har loopar, men nästan alla tillåter rekursion.
• Rekursion är mest generellt och kan hantera situationer där bara en loop inte räcker, men är slött och begränsas i praktiken av anropsstackens maximala storlek.
  • Dubbelrekursion, som bygger på enkelrekursion, är det mest naturliga sättet att bearbeta godtyckligt nästlade data och trädstrukturer, som vi kommer till längre fram i kursen.

Finns det fler sätt att åstadkomma upprepning?

• Mest Pythonic: Generatoruttryck och listbyggare (list comprehensions).
  • Överkurs och skall förklaras om ni väljer att använda det i en labb.
• Mer generellt: Funktionerna map, filter, reduce
  • Mer om dessa längre fram i kursen.

Felsökning

Olika typer av fel

• Syntaxfel:
  • Koden bryter mot programspråkets grammatiska regler.
• Runtime-fel:
  • Fel som uppstår vid körning och resulterar i en "krasch".
• Logiska fel:
  • Programmet kan köra utan att "krascha" men gör inte det man hade tänkt sig.
• Det är inte alltid tydligt var gränsen mellan de sistnämnda går, då många logiska fel kan leda till runtime-fel i vissa men inte alla fall.

Syntaxfel

• Koden bryter mot programspråkets grammatiska regler. Exempelvis:

2+ # Oavslutat uttryck

  Cell In[63], line 1
    2+
      ^
SyntaxError: invalid syntax

for i of range(3): # Använt `of` istället för `in`
    print(i)

  Cell In[65], line 1
    for i of range(3):
          ^
SyntaxError: invalid syntax

def fun(args) # Saknas kolon
    do_something()

  Cell In[64], line 1
    def fun(args)
                 ^
SyntaxError: expected ':'

return = 4 # Försöker tilldela ett värde till ett nyckelord

  Cell In[66], line 1
    return = 4
           ^
SyntaxError: invalid syntax

def if(cond, expr, alt): # Försöker skapa en funktion med samma namn som ett nyckelord
    return expr if cond else alt # Denna rad är dock giltig python, men får betraktas som överkurs

  Cell In[70], line 1
    def if(cond, expr, alt): # Försöker skapa en funktion med samma namn som ett nyckelord
        ^
SyntaxError: invalid syntax

• Exempel:
  • 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:

1+'1'

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[37], line 1
----> 1 1+'1'

TypeError: unsupported operand type(s) for +: 'int' and 'str'

1/0

---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
Cell In[71], line 1
----> 1 1/0

ZeroDivisionError: division by zero

"abcd"[4]

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[72], line 1
----> 1 "abcd"[4]

IndexError: string index out of range

len(4)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[73], line 1
----> 1 len(4)

TypeError: object of type 'int' has no len()

• Exempel:
  • Division med 0. a = 2

b = 1 a/b - Kombinera en sträng och ett heltal med +-operatorn.a = '2' b = 1 a + b

Logiska fel

• Programmet kan köra utan att "krascha" men gör inte det man hade tänkt sig. Exempelvis:

2+3 * 5 # Vi förväntade oss resultatet 25, men operatorn * har högre prioritet än + oavsett var man placerar mellanslag, vi får använda parenteser precis som inom matematiken.

17

'abcd'[1] # Vi ville ha första elementet men glömde att första elementet ligger på index 0, inte index 1.

'b'

• Exempel:
  • Felaktig operatorprioritet, t.ex. råka skriva 3 + 2 * 5 när man menade (3 + 2) * 5.
  • Off-by-one-fel, t.ex. glömma bort att indexering börjar på 0, inte 1.
    • a = ['1', '2', '3']
    • a[1]
    • Eller överkompensera och anta att något ska vara 0 när det borde vara 1.
    • Eller använda strikt olikhet där det borde vara <= eller vice versa.

Spårutskrifter

• Utskrift av variabelvärden vid olika tillfällen i koden
  • T.ex. print(my_var) före och efter ett anrop till en funktion för att kontrollera ifall värdet förändrats pga anropet.
• Utskrift av text för att visa var i koden pythontolken befinner sig
  • T.ex. print("Entering my_fun") på första raden i funktionen my_fun.

Felsökning av olika typer av fel

• Syntaxfel: kontrollera syntax, antal blanksteg, parenteser, kolon, etc.
  • Felmeddelande: Oftast väldigt tydligt exakt var felet är och vad som var fel (dock inte självklart för nybörjaren vad som är rätt).
  • Spårutskrifter är inte till någon hjälp.
• Runtime-fel: tolka felmeddelandet, lägg till spårutskrifter
  • Felmeddelande: Oftast tydligt vad felet är och var det orsakar problem, dock inte alltid vad som orsakar felet eller var det inträffar.
  • Spårutskrifter är ibland nödvändiga för att hitta felet.
• Logiska fel: 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.
  • Felmeddelande: Osäkert om man ens får något.
  • Spårutskrifter är nästan alltid nödvändiga om man inte direkt inser var man tänkt fel.

• När det är svårt att hitta felet: Det är alltid bättre att vara noggrann och dubbelkolla med spårutskrifter än att göra antaganden om att man gjort rätt, om alla våra antaganden alltid vore korrekta hade det ju inte blivit fel från första början.

Sidospår: Begreppet "krasch"

• Vi säger ofta lite slarvigt att "Python kraschade" när vår kod inte fungerar och vi får ett felmeddelande.
• Tekniskt sett är detta inte korrekt. Själva Python, dvs. Pythontolken, har inte kraschat utan har upptäckt ett fel och stoppat exekveringen under kontrollerade former.
  • Eventuellt kan vi säga att "vårt skript kraschade", men inte att "Python kraschade".
• En verklig "krasch" är okontrollerad från programmets (i det här fallet Pythontolkens) sida.
  • Antingen kliver operativsystemet in och stoppar Pythontolken utan vidare konsekvenser för datorn, eller så är felet så allvarligt att hela operativsystemet utför ett kontrollerat nödstopp (t.ex. klassiska "Bluescreen of Death" i Windows). I värsta fall är problemet så allvarligt att även operativsystemet avslutas okontrollerat, om själva datorn har upptäckt ett så allvarligt fel att den omgående stoppar allt för att undvika att maskinvaran tar skada.
  • Typiskt för att Python kraschar är att vi inte får något felmeddelande från Python, i bästa fall får vi ett felmeddelande av operativsystemet.
• Det är väldigt svårt att få själva Python att krascha.
  • (Jag kan räkna på ena handens fingrar antalet gånger jag sett operativsystemet behöva nödstoppa Python, jag har aldrig sett hela systemet påverkas av ett trasigt Pythonskript. //Johan)

Tips för parprogrammering

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

Förare och observatör

Växla ofta (minst var 15e minut)

• 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örrän på tentan.
  • Är ni ett ojämnt par där den ena har mer erfarenhet så bör den med minst erfarenhet spendera mest tid vid tangentbordet.
• 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 löpande, och be föraren förklara om du tror att något är fel eller är osäker på varför föraren skrev en specifik sak.
  • 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

Program- och dataabstraktion

• Programabstraktion
  • Uppdelning av större program i flera moduler, funktioner och processer som ansvarar för olika saker.
  • Döljer onödig komplexitet bakom anrop till funktioner med beskrivande namn.
  • Vi abstraherar bort detaljerna för hur något skall utföras så att vi inte behöver hålla det i huvudet hela tiden.
• Dataabstraktion
  • Döljer detaljer kring hur data faktiskt lagras bakom ett gränssnitt, en uppsättning funktioner som används för att arbeta med datan utan att behöva veta detaljerna.

Programmeringsparadigm

(https://en.wikipedia.org/wiki/Programming_paradigm)

(Lästips för den nyfikne: Sebesta, Robert W. Concepts of programming languages (11th Edition). Pearson Education, Inc, 2016 .)

Programmeringsstilar

• Olika sätt att strukturera ett program, dvs. olika sätt att skapa abstraktioner och principer att följa kring var abstraktioner skapas och hur de interagerar med varandra.
• Olika programmeringsspråk har olika språkliga konstruktioner med olika semantik (hur konstruktionerna faktiskt fungerar) som gör olika stilar lättare eller svårare att applicera.
• Stilarna är ofta mer av tendenser än strikta definitioner, och vissa stilar råder det debatt om hur de faktiskt ska definieras.
• Många stilar är ortogonala och kan användas samtidigt.
• När en viss stil efterföljs utan undantag, eller med så få undantag som möjligt, kallar vi det för ett programmeringsparadigm.
• Historiskt sett var programmeringsspråk mer paradigmatiska, dvs. mer begränsade till en viss programmeringsstil. De flesta populära och mer moderna språk, som Python, är multiparadigmatiska.

Strukturerad programmering, ett paraplyparadigm

• All programmering i den här kursen och nästan all annan modern programmering går under paraplyet strukturerad programmering.
• Det kan vara enklare att förklara vad som INTE är strukturerad programmering.

Ostrukturerad programmering (eller go to-programmering)

• Program körs rad för rad, uppifrån och ned, och programmets flöde styrs genom go to-operationer som hoppar till en viss rad eller, senare, en viss label, och fortsätter därifrån.
• Många moderna språk som Python har ingen go to-operation (annat än som ett aprilskämt 2004).
• Assembly-programmering och maskinkod är fortfarande oftast "ostrukturerad".
  • Y:arna får lära sig mer om detta i TSEA28 Datorteknik Y. (En av få kurskoder som finns kvar ända sedan min tid. //Johan)

Ostrukturerad programmering i Python (enligt april-skämt 2004)

• Edsger W. Dijkstra. 1968. Letters to the editor: Go To Statement Considered Harmful. Commun. ACM 11, 3 (March 1968), 147–148. https://doi.org/10.1145/362929.362947
  • En lite mer sentida analys av Dijkstras resonemang, med moderniserat (nåja) språkbruk, av David Tribble finns här.
• Värt att påpeka är att Dijkstra inte hävdade att en enskild go to-operation i sig alltid var problematisk (den starka titeln var det tidskriftens redaktör som hittade på) utan att överanvändning av go to-konstruktionen ofta ledde till extremt svårtolkad kod. Vad som senare kom att kallas "Spaghettikod".
  • Omöjligt att följa programflödet eftersom det bara är en röra mellan olika rader/labels och goto-operationer, som att försöka följa en enskild spaghetti i en skål full med spaghetti.
• Istället skulle man använda konstruktioner som funktionsanrop, if, while, osv. för att strukturera koden.
• Vi har alltså hela tiden arbetat inom ramarna för strukturerad programmering.

goto .start;
label .fun;
print("Fun output 1")
print("Fun output 2")
goto .continue;
label .start;
print("Output 1")
print("Output 2")
goto .fun;
label .continue;
print("Output 3")
print("The End")
label .end;

Exemplet är inte körbart, eftersom riktig Python inte har goto eller label i verkligheten.

• Inte körbart eftersom Python tack-och-lov inte har goto i verkligheten

Strukturerad programmering i riktig Python

def fun():
    print("Fun output 1")
    print("Fun output 2")
print("Output 1")
print("Output 2")
fun()
print("Output 3")
print("The End")

Ytterligare två dimensioner

• Imperativ programmering
  • Beskriver hur datorn skall utföra något.
  • Beskriv steg för steg de operationer som tillsammans löser ett problem.
  • Ostrukturerad på låg nivå och historiskt sett, idag finns strukturerade paradigm som också är imperativa.
• Deklarativ programmering
  • Beskriver vad datorn skall göra.
  • Beskriv en uppsättning regler och relationer som programmet ska följa.
  • I princip alltid strukturerad per definition.

Tre mer praktiskt tillämpbara kategorier

• Procedurell programmering (imperativ)
  • Procedurer (i Python, funktioner) och moduler. Enkla och föränderliga data. Programmets tillstånd, dvs. vad som just nu är lagrat i minnet, är centralt. Satser som ändrar programmets tillstånd.
  • (Används ibland synonymt med imperativ programmering men lämpligare är kanske att säga att procedurell programmering är en strukturerad form av imperativ programmering.)
• Funktionell programmering (deklarativ)
  • Rena funktioner, dvs. funktioner utan sidoeffekter eller beroende av delat tillstånd. Oföränderliga data. Eventuellt nödvändigt tillstånd isoleras och hanteras separat. Uttryck som beskriver värden och relationer.
• Objektorienterad programmering (imperativ, oftast)
  • Objekt och, oftast, klasser. Programmets tillstånd distribuerat mellan objekt som kapslar in sina egna tillstånd. Meddelanden skickas mellan objekt för att indirekt manipulera objektens tillstånd.

Programmeringsparadigm som stöds i Python

Objektorienterad, Procedurell och Funktionell programmering (nåja)

Python är multiparadigmatiskt

• Den programmeringsstil som kallas Pythonic är influerad av flera stilar.
  • Allting är objekt som i OOP, men vi måste inte programmera objektorienterat.
  • Pythons subrutiner kallas "funktioner" men kan vara
    • Rena procedurer, utan returvärde, som i procedurell programmering.
    • Rena funktioner, utan sidoeffekter, som i funktionell programmering.
    • Något mittemellan.
  • Plockar russinen ur många kakor.
• Vi kan dock skriva kod som är mer typisk för ett visst paradigm, vi kan använda Python paradigmatiskt.

Bygga upp ett program med hjälp av funktioner

• Istället för att ha en monsterfunktion som gör allt
  • identifiera mönster
  • deluppgifter som förekommer på flera olika ställen i ett program
• Skriv en funktion för varje deluppgift
• Uppdelningen kan vara hierarkisk:
  • Problem $A$ består av delproblemen $B$ och $C$
  • Problem $B$ består av delproblemen $E$, $F$ och $G$
  • Problem $C$ består av delproblemen $H$, $E$ och $I$

Välj beskrivande variabelnamn...

i = ""
while i != 'q':
    i = input("Skriv något: ")
    p = None
    h = False
    for c in i:
        if p and p == c:
            h = True
        p = c
    if h:
        print("Det du skrev har upprepade bokstäver i sig!")
    else:
        print("Det finns inga upprepade bokstäver där.")
print("Hej då.")

Välj beskrivande variabelnamn...

user_input = ""
while user_input != 'q':
    user_input = input("Skriv något: ")
    prev_char = None
    has_repeated = False
    for curr_char in user_input:
        if prev_char and prev_char == curr_char:
            has_repeated = True
        prev_char = curr_char
    if has_repeated:
        print("Det du skrev har upprepade bokstäver i sig!")
    else:
        print("Det finns inga upprepade bokstäver där.")
print("Hej då.")

Vi kan skapa egna abstraktioner med t.ex. funktioner

def has_repeated_char(s):
    prev_char = None
    for curr_char in s:
        if prev_char and prev_char == curr_char:
            return True
        prev_char = curr_char
    return False

user_input = ""
while user_input != 'q':
    user_input = input("Skriv något: ")
    if has_repeated_char(user_input):
        print("Det du skrev har upprepade bokstäver i sig!")
    else:
        print("Det finns inga upprepade bokstäver där.")
print("Hej då.")

Kommentarer kan göra det lättare att förstå koden, men bara om de stämmer!

def has_repeated_char(s):
    """Returnera True om upprepade tecken finns i s, annars False."""
    prev_char = None
    for curr_char in s:
        # Check whether previous charcter is the same as the current character.
        if prev_char and prev_char == curr_char:
            return True
        prev_char = curr_char
    return False

# Ask user for a word and answer whether it contains repeated characters or not.
user_input = ""
while user_input != 'q':
    user_input = input("Skriv något: ")
    if has_repeated_char(user_input):
        print("Det du skrev har upprepade bokstäver i sig!")
    else:
        print("Det finns inga upprepade bokstäver där.")
print("Hej då.")

Skiss för interaktivt program

def ta_emot_kommando():
    satser
    return kommando

def kommando1():
    satser

def kommando2():
    satser

def utför_kommando(kommando):
    satser

def main():
    while True:
        kommando = ta_emot_kommando()
        utför_kommando(kommando)

Skiss för autocomplete-uppgift

def ladda_ordlistor():
    satser
def ladda_ordlista(ordlista):
    satser
def autocomplete_strategi1():
    satser
def autocomplete_strategi2():
    satser
def autocomplete(strategi, ord, ordlistor)
    satser
def välj_strategi():
    satser
def main():
    ordlistor = ladda_ordlistor()
    strategi = välj_strategi()
    while True:
        ord = input("Skriv ett ord: ")
        if ord != "q":
            kompletterat_ord = autocomplete(strategi, ord, ordlistor)
            print(kompletterat_ord)

Läsa från textfil

Läsa data från textfil

• Läsning sker sekventiellt
• Olika strategier
  • hela filen som en textsträng
  • en rad i taget, en rad → en sträng
  • hela filen som en lista, varje rad blir ett element i en lista

Förberedelser innan läsning

• Filen måste öppnas för läsning
• Liknelse: undersöka innehåll i en låda från en lagerlokal
  • ange vilken låda - ange sökväg till filen
  • öppna låda för att plocka ut saker - öppna filen i "läsläge"
  • plocka fram innehåll - läs från fil

Läsa in information från en fil

• Funktionen open tar in en sträng (namn på fil), och öppnar filen och returnerar den öppna filen (speciell datatyp)

file = open(filnamn)
file = open(filnamn, 'r') # read - endast läsning
file = open(filnamn, 'w') # write - skriva över
file = open(filnamn, 'a') # append - lägga till

Läsa in information från en fil

• Metoden .readlines läser innehållet i filen och returnerar det som en lista av strängar.
  • (metod: funktion som sitter ihop med ett värde)

file = open("hemligt.txt")
contents = file.readlines()

Stänga fil

• Vi stänger en fil när vi är klara med den (praxis, för att undvika diverse problem)

file = open("data.csv")
contents = file.readlines()
file.close()

Funktionen repr

• repr returnerar sträng inklusive citattecken för att indikera att det är en sträng

print(True)
print("True")
print(repr(True))
print(repr("True"))