Introduktion till
Utformad för dem som vet och skall veta allra mest om datorer och programmering
Hur hittar man den: från svårast till lättast
0. Navigera i Chalmers studieportal
http://www.student.chalmers.se/
1. Anteckna URL (Uniform Resource Locator)
http://www.cs.chalmers.se/~aarne/datorintro/
2. Googla med
datorintroduktion D-linjen Chalmers
3. Googla med läraren
Aarne Ranta
tryck på "Datorintroduktion"
Vi går snabbt genom kurswebbsidan, för att förklara
Datavetenskap (Computer Science) har sina rötter på två håll:
Datavetenskap kan därför se rätt så olika ut beroende på datavetare.
hårdvara = maskinvara, mjukvara = programvara
mjukvara användarprogram -- Firefox, emacs, GHC operativsystemet -- Windows, Unix, Symbian ------------------------------------------------------------- hårdvara datorn -- PC, Mac, iPhone, PSP
Första versionen i 1970
Känns numera under namnen Linux, Mac OS X, SunOS, BSD...
Fungerar på alla sorters maskiner
Populärt bland professionella programmerare och datavetare
Kärnan (Eng. kernel): närmast hårdvaran
Filsystemet: kataloger och filer
Kommandotolken (Eng. shell): närmast användaren
Därtill:
När man matat in användar-ID och lösenord, kommer man oftast in i ett fönstersystem.
Man kan då öppna ett "shell", som kan heta "terminal", "konsole", "xterm", "cygwin", etc.
I shellen kör vi följande kommandon (vart och ett efter prompten $
):
$ whoami -- visa mitt användarnamn $ pwd -- print working directory $ ls -- lista innehållet i biblioteket $ mkdir datorintro -- skapa bibliotek för kursen $ cd datorintro -- gå till det nya biblioteket
För mera information: see Unix-kompendiet (kommer snart)
En texteditor som är många programmerares favorit.
Speciellt lämpligt för att skriva programkod i.
Kan öppnas från shellet med kommandot emacs
, eller eventuellt från
en meny i "applications" eller motsvarande.
Från shellet:
$ emacs MyProgram.hs -- öppna filen MyProgram.hs i emacs-editorn
Vi lär ut Haskell först
Senare lär vi Java, C, assembler
Och ännu lägre: datorarkitektur, kretselektronik...
Och ännu högre: matematiska modeller av beräkning
Och bryggan mellan nivåer: kompilatorer
Kompilatorn är ett program som automatiskt översätter högnivåspråk till maskinspråk.
Det är därför programmerarna (oftast) kan hålla sig till högnivåspråk.
Det är därför samma program kan köras på olika sorters datorer.
GHC = Glasgow Haskell Compiler
GHCi = GHC Interactive
Vi kommer att
GHC(i) finns för Linux, Mac, Windows... gratis från
Starta ett GHCi-shell i Unix-shellet och skriva program till prompten
$ ghci Prelude> 2+2 4 Prelude> sum [1 .. 100] 5050
Snabbt och effektivt för mycket korta program.
Även för att testa längre program.
Skriv program i en fil, t.ex. MyProgram.hs
, läs in i GHCi, och kör i GHCi
Prelude> :l MyProgram.hs MyProgram> factorial 12 479001600
Snabbt för program stora som små, men inte effektivast.
Det vi mest använder resten av kursen. Filen MyProgram.hs
kan se ut så här:
factorial n = product [1 .. n]
Haskell är ett funktionellt programspråk
Köra ett program = beräkna värdet av en funktion med givna argument
Exempel från matematik:
f : R -> R
f(x) = (x + 1)(x - 1)
f(3.1) = 8.61
(Ungefär) samma exempel i Haskell:
f :: Float -> Float f x = (x + 1) * (x - 1) MyProgram> f 3.1 8.61
Heltal, flyttal: Int
, Float
De fyra räknesätten: + - * /
Potensupphöjning: 2.7 ^ 6
Dessa kan kombineras i uttryck, där parenteser kan behövas:
Prelude> 2 + 3 * 4 14 Prelude> (2 + 3) * 4 20
Nu ska vi sitta ner och göra några beräkningar.
GHCi-prompten visar den modul vars funktioner är tillgängliga.
En modul, som heter Prelude
är alltid tillgänglig.
Även om man har laddat in ett annat program, är Prelude
tillgänglig.
Prelude
innehåller de flesta funktioner vi behöver på denna kurs, t.ex.
de viktigaste matematiska funktionerna.
Hur definierar vi medelvärdet av en lista av tal?
Just det: vi behöver en lista av tal.
Listor kan skrivas på olika sätt:
[] [1,2,3} [1 .. 100] [2,4 .. 100]
Preludfunktionen sum
tar en lista av tal och returnerar
deras summa. Nu:
Prelude> sum [1,2,3] / 3 2.0 Prelude> sum [1 .. 100] / 100 50.5
En lista kan vara oändlig.
Prelude> [1 ..] [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41, 42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57Interrupted.
Tryck Control-C för att avbryta beräkningen!
Kan vi beräkna summan av en oändlig lista?
Prelude> sum [1 ..] Prelude> sum [0,0 ..]
Dags att sitta ner och experimentera igen.
Hur skriver vi listan av jämna tal mellan 1 och 100?
Antingen med med stegning:
[2,4 .. 100]
eller också med en listkomprehension:
[x | x <- [1 .. 100], even x]
Delarna i listkomprehensionen:
x
x <- [1 .. 100]
even x
Obs. even
är en funktion som avgör om ett tal är jämnt. Den returnerar
True
eller False
.
Vi ska sitta ner och prova exempel:
odd
)
<
) 50
==
) sig själva
Villkor kan kombineras med &&
("och") och ||
("eller").
Listan av tal som är mindre än 10 eller större är 90:
[x | x <- [1 .. 100], x < 10 || x > 90]
Funktionen length
anger en listas längd som heltal.
Prelude> length [] 0 Prelude> length [2,4 .. 100] 50 Prelude> length [1,1,1] 3
Observera att length
räknar varje etta separat i det tredje exemplet.
Hur många tal uder 100 har kvadrat mindre än 500?
length [x | x <- [1 .. 100], x * x < 500]
Ta en lista av tal och addera 1 till varje tal;
[x + 1 | x <- [1 .. 100]]
Ta en lista av tal returnera talens kvadrater:
[x * x | x <- [1 .. 100]]
Ta en lista av tal och returnera talens fakulteter:
[product [1 .. x] | x <- [1 .. 20]]
Ta en lista av tal returnera kvadraterna av dem som är udda:
[x * x | x <- [1 .. 100], odd x]
Nu ska vi verkligen sitta ner och experimentera!
Man kan "klippa av" början av en lista, även oändlig, med take
:
take 5 [1 ..] == [1,2,3,4,5] take 5 [1,2,3] == [1,2,3]
Med detta kan man skapa approximeringar av en oändlig lista:
Prelude> take 10 [1/n | n <- [1 ..]] [1.0,0.5,0.3333333333333333,0.25,0.2,0.16666666666666666, 0.14285714285714285,0.125,0.1111111111111111,0.1]
Listor är en datastruktur: en komplex form av data (jämfört med tal, som är enkla).
En annan datastruktur är par
(1,2)
En tabell är en lista av par. Här är en tabell av kvadrater:
[(x, x * x) | x <- [1 .. 100]]
Och, lite mer intressant: av kvadratrötter:
[(x, sqrt x) | x <- [1 .. 100]]
Låt oss köra några till exempel igen.
När ett heltal delas med ett heltal, kan man få kvoten med funktionen
div
och resten med mod
:
Prelude> div 13 5 2 Prelude> mod 13 5 3
Att ett tal m är delbart med n betyder att
mod m n == 0
Ett tals faktorer är alla de tal som det är delbart med:
[n | n <- [1 .. m], mod m n == 0] Prelude> [n | n <- [1 .. 123], mod 123 n == 0] [1,3,41,123]
Ett primtal har inga andra faktorer än 1 och sig självt. Hur ska vi uttrycka detta i Haskell? Låt oss prova!
Beräkna alla primfaktorer av talet 45678.
Det här blir risigt, även med listkomprehensioner.
Nu är det dags att skriva ett litet bibliotek, en fil med användbara funktioner som har att göra med delbarhet:
module Prime where divisible m n = mod m n == 0 factors m = [n | n <- [1 .. m], divisible m n] prime m = m > 1 && factors m == [1,m] primeFactors m = [n | n <- factors m, prime n]
Vi laddar vårt bibliotek i GHCi:
Prelude> :l Prime.hs Prime> primeFactors 45678 [2,3,23,331]
Ny uppgift: skriv ut tabellen av alla tal från 1 till 1000 och deras primfaktorer.
Prime> [(x,primeFactors x) | x <- [1 .. 1000]] [(1,[]),(2,[2]),(3,[3]),(4,[2]),(5,[5]),(6,[2,3]),(7,[7]), (8,[2]),(9,[3]),(10,[2,5]),(11,[11]),(12,[2,3]),(13,[13]), (14,[2,7]),(15,[3,5]),(16,[2]) ...
Obs: vår algoritm för att räkna primfaktorer är långsam: senare kurser ska lära ut bättre algoritmer!
För att dokumentera vad funktionerna gör anger man med fördel typsignaturer till varje funktion:
module Prime where divisible :: Int -> Int -> Bool divisible m n = mod m n == 0 factors :: Int -> [Int] factors m = [n | n <- [1 .. m], divisible m n] prime :: Int -> Bool prime m = m > 1 && factors m == [1,m] primeFactors :: Int -> [Int] primeFactors m = [n | n <- factors m, prime n]
Konjektur: Det finns oändligt många p sådana att både p och p+2 är primtal. T.ex. 3,5 ; 5,7 ; 11,13 ; 17,19 ; ...
Detta har varken bevisats eller motbevisats.
Uppgift: Skriv ett Haskell-program som genererar (den oändliga?) listan av alla tvillingprimtal.
Uppgifterna ska redovisas i en fil Ex1.hs
, som ser ut så här:
module Main where import Prime main = do print ex2 print ex3 print ex4 print ex5 -- definitionerna av ex2, ex3, 3x4, ex5, samt eventuella hjälpfunktioner
När man kör kommandot
runghc Ex1
skrivs lösningarna på skärmen, rad för rad.
Hur print
och do
exakt fungerar kommer att förklaras
i Föreläsning 3.
1. Skriv och beräkna ett Haskell-uttryck som anger antalet dagar sedan du föddes.
2. Definiera ett Haskell-uttryck ex2
, som genererar tabellen av
konverteringar från Fahrenheit till Celsius för Fahrenheit-värdena
0,20,40,...,300 (20 graders stegning). Konversionsformeln är:
C = 5(F-32)/9. T.ex. om F=86 är C=30.
3. Hur många primtal finns mellan 0 och 1000 respektive 7000 och 8000?
Definiera ett uttryck ex3
, som returnerar dessa som ett par.
Du får använda filen Prime.hs
som hjälp.
4. Definiera ett Haskell-uttryck twins
, som genererar
(den oändliga?) tabellen av
alla tvillingprimtal. Du får använda filen Prime.hs
som hjälp. Definiera sedan ett uttryck ex4
, som ger de tio första
paren.
5. Skriv en funktion geom
, som approximerar den geometriska serien
1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^n) + ...
med ett heltal n
som argument. Skriv sedan ett uttryck ex5
, som ger
listan av approksimationerna med n = 1,...,10
.
Starta GHCi med kommandot ghci
Beräkna värdet av ett uttryck: skriv uttrycket i prompten
Ladda en fil: :l FILE
Help: :?
Avbryta beräkning: Control-C
Föregående kommando: pil-upp
Module-header följd av eventuella modulimportdirektiv följda av funktionsdefinitioner med eller utan typsignaturer:
module Prime where import List divisible :: Int -> Int -> Bool divisible m n = mod m n == 0 -- ingen typsignatur (detta är en kommentar) factors m = [n | n <- [1 .. m], divisible m n]
Modulen Prime
ska finnas i filen Prime.hs
.
Undantag: om modulen heter Main
kan filen heta vad som helst.
Varje definition ska börja från början av en rad. Inget annat får placeras i början av en rad (förutom kommentarer).
Det finns måga sätt att skapa och modifiera en fil under Unix och
andra operativsystem. De flesta dataloger använder Emacs.
Den kan startas från Unix-shellen med kommandot emacs
.
Då öppnas ett fönster med menyer för att skapa, öppna och spara filer, osv.
Numeriska typer:
Int
, med positiva och negativa heltal
Float
Sanningsvärden: Bool
, med objekten True
och False
Datastrukturer:
[a]
där a
är en typ
(a,b)
, där a
och b
är typer
Funktioner: a -> b
där a
och b
är typer
a -> b -> c
Infixoperatorer, med parenteser vid behov: (2 + 3) * 4 > 15
Funktionsapplikationer: divisible 12 4
Listor:
[1,2,3]
[1 .. 100]
, [1 ..]
, [1,3 .. 100]
[x * x | x <- [1 .. 100], even x]
-- defined for Numeric types (+) :: (Num a) => a -> a -> a (-) :: (Num a) => a -> a -> a (*) :: (Num a) => a -> a -> a (/) :: (Num a) => a -> a -> a (^) :: (Num a) => a -> Int -> a -- a^n är a upphöjt till potens n div :: Int -> Int -> Int mod :: Int -> Int -> Int sqrt :: Float -> Float -- defined for types with Equality (==) :: (Eq a) => a -> a -> Bool (/=) :: (Eq a) => a -> a -> Bool (<) :: (Eq a) => a -> a -> Bool (>) :: (Eq a) => a -> a -> Bool (&&) :: Bool -> Bool -> Bool (||) :: Bool -> Bool -> Bool even :: Int -> Bool odd :: Int -> Bool sum :: (Num a) => [a] -> a product :: (Num a) => [a] -> a length :: [a] -> Int take :: Int -> [a] -> [a]