"Any sufficiently advanced technology is indistinguishable from magic."
- Arthur C. Clarke
"We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a ___program___. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells."
- Abelson and Sussman, Structure and Interpretation of Computer Programs aka The Wizard Book
"Computer program, detailed plan or procedure for solving a problem with a computer; more specifically, an unambiguous, ordered sequence of computational instructions necessary to achieve such a solution. "
Vad menas med en serie instruktioner?¶
In [2]:
from IPython import display
display.YouTubeVideo(id="cDA3_5982h8", width=400, height=300, start=37)
Out[2]:
Svårt när man inte kan reglerna¶
Vi behöver ett tydligare sätt att skriva instruktioner¶
Olika sätt att uttrycka instruktioner¶
Notation för matematik och logik¶
$$ A = \{1, 2, 3\}\\ B = \{3, 4, 5\}\\ A \cup B = \{x| x \in A \lor x \in B \} \\ A \cup B = C \\ $$
$$
C = \{1, 2, 3, 4, 5\}
$$
Mer datornära kanske?¶
Programmeringsspråk som Python¶
In [3]:
sul = "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ"
slv = "aeiouyåäö"
slc = ""
for i, l in enumerate("ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ"):
if l not in slv.upper():
slc = slc + l.lower()
print(slc)
bcdfghjklmnpqrstvwxz
- Verkligen jättedumma variabelnamn, gör inte så här.
Hur fattar datorn det?¶
Historia och abstraktion¶
Tidigt 1940-tal: ENIAC — Kod är kablar, data är hålkort¶
1945: John von Neumann och den fundamentala datorarkitekturen¶
von Neumann-arkitekturen
Om både kod och data är hålkort kan de hanteras på samma sätt
- Processorenhet med aritmetisk-logisk enhet och in/ut-register för denna
- Kontrollenhet med aktuellt instruktionsregister och en programräknare som håller koll på nästa instruktion
- Externminne för långtidslagring av data och program (hålkorten)
- Internminne som efter inläsning lagrar både data och instruktioner som används i den aktuella processen
- In- och Utenheter
Binär maskinkod, vår första abstraktion i kod
- Består av långa sekvenser av
1:or och0:or som representerar instruktioner och den data som instruktionerna opererar på, motsvarar hål och inte hål på ett hålkort. - Exempelvis
10111000,00000000,10111000,10001110,11011000,11000110,00000110,10011110,00001111,00100100,11001101,00100000- Med "vanliga" heltal med talbas 10 motsvarar detta
184,0,184,142,216,198,6,158,15,36,205,32
- Med "vanliga" heltal med talbas 10 motsvarar detta
- Ofta uttrycker vi 8-bitars sekvenser av binära tal (1 byte) som hexadecimala tal (med talbas 16).
- Vi använder
aför att representera vanliga heltalet10,bför11, osv. upp tillfför15 - Exemplet ovan blir då
b8,00,b8,8e,d8,c6,06,9e,0f,24,cd,20
- Vi använder
Maskinkod för Intel 8085 (1976), några exempel
| Binary | Opcode (hex) | Description |
|---|---|---|
10000111 |
87 |
Add the contents of register A to that of the accumulator |
00111010 |
3a |
Load data stored in the given memory address |
01111001 |
79 |
Move data from register A to C |
11000011 |
c3 |
Jump to instruction in specified memory address |
11000001 |
c1 |
Pop from stack and copy to memory registers B + C |
Assemblykod assembleras till maskinkod
MOV AX, 47104
MOV DS, AX
MOV [3998], 36
INT 32
- En assemblator (eng. assembler), skriven i maskinkod, kan använda ovanstående text och assemblera ett program i maskinkod.
- (Exempel från http://www.swansontec.com/sprogram.html)
- Olika assemblers kan generera maskinkod för olika besläktade hårdvaror utifrån samma kod.
C kompileras till assembly- och maskinkod
#include <stdio.h>
int main() {
printf("Hello, World!\n");
return 0;
}
- En kompilator, som någon ursprungligen skapat med hjälp av assemblykod, översätter ett program från kod som alla programmerare, med lite övning, kan läsa och förstå, till maskinkod.
- Källkoden är samma (eller nästan samma) för alla datorer, men kompileras till maskinkod för olika datorer.
Högnivåkod som kan köras direkt av ett annat program
(hate 'I
(and 'programming-jokes
(and 'lisp 'irony)))
- En interpretator eller programtolk (eng. interpreter), kompilerad till maskinkod, kan köra program direkt, utan att översätta dem till maskinkod.
- Källkoden är samma för alla datorer, men kräver att en interpretator är installerad på datorn (eller att källkoden och interpretatorn för att köra dem distribueras gemensamt).
Abstraktionshierarki
Vilket programmeringsspråk är bäst?¶
Bättre fråga: Vilket programmeringsspråk är bäst för vårt syfte?¶
Kort om Python
- Födelsedatum: sent 80-tal men officiellt 20e februari 1991
- Skapare: Guido van Rossum (före detta "Benevolent Dictator For Life", eller BDFL, över Python)
- Fyllde 2.0 i oktober 2000
- Fyllde 3.0 i december 2008
- Idag: 3.13 (3.14 den 1 oktober)
- I kursen använder vi 3.10 (från 2021)
- Top 5 i de flesta rankningar av popularitet, nr 1 i flera av dem.
- Interpreterat, objektbaserat och dynamiskt typat programmeringsspråk.
Kommandot python3 i LiUs Linux-miljö¶
- Interaktiv användning:
$ python3
- Kör ett skript:
$ python3 filnamn
Interaktiv användning¶
- Starta en pythontolk genom att skriva
python3i terminalen. - Python ersätter skalprogrammet i terminalen.
- Bra för att experimentera, testa och felsöka.
- Avsluta genom att trycka Ctrl-D eller genom att köra python-kommandot
exit().- Tekniskt sett så anropar vi funktionen
exitutan några argument
- Tekniskt sett så anropar vi funktionen
Skriv och kör ett skript¶
- Starta en text-editor (t.ex. VSCode)
- Skriv kod och spara i en fil med exempelvis namnet
hello.py. - Från terminalen, kör programtolken och skicka med sökvägen till textfilen med pythonkoden som argument genom att skriva
python3 hello.py
- Bra för kod som man vill spara eller sätta i produktion.
Några termer¶
- Källkod: Kod skriven i ett programmeringsspråk som kompileras till maskinkod. I överförd betydelse, kod som tolkas av en interpretator och utförs, även om en kompilering inte sker.
- Alltid singular, dvs "källkod" eller "kod", aldrig
"koder". Jämför med t.ex. "vatten". (Vi kan säga flera glas vatten, eller flera kodfiler, men aldrig flera vatten eller flera koder, när vi pratar om källkod dvs.)
- Alltid singular, dvs "källkod" eller "kod", aldrig
Hur lär man sig programmera?¶
- Inte genom att lyssna på föreläsningar och läsa kodexempel.
- Rättelse: Inte genom att bara lyssna på föreläsningar och läsa kodexempel.
Ett vanligt missförstånd¶
- Kritik från tidigare studenter:
- "Det är orimligt att vi ska kunna lösa uppgifter vi inte sett förut."
- "Jag känner igen duggauppgifterna, men de har alltid en twist jämfört med vad vi sett förut."
Förenklad jämförelse¶
- Hur många här inne har sett följande mattetal förut?
- Hur många kan räkna ut det?
- Vilka två tal som adderas gör det inte konceptuellt svårare att räkna ut resultatet.
- Det kan vara svårare rent praktiskt om talen är stora, men...
- Vi vet hur addition fungerar oavsett vilka tal som adderas.
Relevans?¶
Programmering fungerar på samma sätt¶
- Vi lär oss
- Hur språkliga konstruktioner (som t.ex. operatorn $+$) fungerar (semantik).
- Hur sådana konstruktioner kan kombineras för att lösa olika problem (syntax och mer semantik).
- Hur större problem kan brytas ned i hanterbara delar med hjälp av konstruktionerna (dekomposition).
- Hur lösningar på delproblem kan namnges och återanvändas utan att behöva tänka på detaljerna (abstraktion).
- Att känna igen återkommande mönster i problem (mönsterigenkänning).
- Vilka mönster av konstruktioner som löser sådana återkommande problemmönster (algoritmer).
- Vi lär oss inte
Lösningar på 1500 specifika uppgifter utantill.