Gå till innehållet

DD1366 Programmeringsparadigm 6,0 hp

Tillfälleskod Termin(er) Period(er) Föreläsare
52149 VT2025 3 Marcus Dicander

Föreläsningsanteckningar.

Inledning/föreläsning 0

Programmeringsparadigm: Handlar om att lyfta fram bakomliggande modeller och idéer bakom program och programmeringsspråk och jämför dessa sida vid sida. För att göra detta kommer vi att titta på språk som skiljer sig mcket åt, t.ex. PHP och Haskell.

Interpretering: översättning mellan programmeringsspråk, on the fly.
Kontrollflöde: if/while

Föreläsning 1: Funktionell programmering, del 1

Funktionell programmering: En programmeringsstil vars grundläggand operation är funktionsanrop. En vidareutveckling av lambdakalkylen (konstanter, variabler, funktioner och funktionsanrop/tillämpningar - även uttryck, vilket följer av de 4 nämnda "axiomen").

I Haskell är allt immutable (oföräderligt). Underläggar parallellisering.

Kodexempel:

main::IO()
main = -- Observera att main är en oren funktion (modifierar I/O)
    putStrLn "Hello world!" -- funktion med bieffekt

I vanliga Haskell-funktioner finns inget returvärde, utan värdet representerar funktionen.

Rekursion

Svansrekursion: Det rekursiva anropet returnerar direkt utan några kvarhängande operationer. Svansrekursiva anrop kan optimeras bättre av GHC, men se upp med '++'!

Ett exempel:

collatzList::Integer -> [Integer]
collatzList 1 = [1] -- Basfall
collatzList n = n : collatzList (collatzStep n) -- Effektivt att lägga till n i början av listan (++ långsammare)
    where collatzStep n
        | odd n     = 3 * n + 1 -- if odd(n) ...
        | otherwise = n `div` 2 -- else ...

collatzList är inte svansrekursiv, eftersom : blir en kvarhängande operator.

Lat evaluering

Haskell har lat evaluering - väntar med att beräkna saker tills de verkligen behövs. Stora beräkningsträd kan byggas upp av funktionsanrop som beror på varandra. När sedan värdet behövs, kan Haskell tillämpa sina optimeringar och köra alltsammans.

T.ex. orsakar let infinite = [1..] inga problem, och vi kan t.o.m. köra take 42 infinity. Att försöka printa ut hela listan leder dock till oändlig rekursion.

Kör vi take 10 (collatzList 27) kommer Haskell enbart att räkna ut de första 10 talen med collatzList-funktionen, eftersom det är de enda talen som behövs. Detta är väldigt användbart ur prestandasynpunkt!

Listomfattningar

I matematiken kan vi skriva \([x|x\in\{1,2,3,4\},\text{odd}\ x]\), vilket i Haskell kan skrivas som [x | x<-[1..4], odd(x)].

Exempel: [mod 73 d | d<-[2..72]] innehåller alla rester vid division av 73 med 2..72. Vi kan kolla om elem 0 <...>, vilket ger False (73 ej jämnt delbart med något sådant tal, dvs. 73 är ett primtal).

Definitionen av primtal 2-1000: [x | x<-[2..1000], notElem 0 [mod x y | y<-[2..(x-1)]]]

Föreläsning 2: Funktionell programmering, del 2 (22/1-2025)

Flyttal

Det finns 252 tal i varje fönster.

Stark och svag typning

Java, Haskell, Python är starkt typade.

  • Statisk typning: Sker vid kompilering. T.ex. Java, Haskell. "Nästan alla typfel upptäcks".
  • Dynamisk typning: T.ex. Python ("duck typing")

Typsäkerhet

Ett typsystem är säkert om det garanterar att inga uttryck kan anta värden som inte är definierade av typen.

Implicita & explicita typkonverteringar

T.ex. Haskell: 

i = 1::Int
t1 = (fromIntegral i)::Double
:t fromIntegral -- fromIntegral :: (Integral a, Num b) => a -> b
i2 = fromIntegral t1::Int -- error

(length lista) / 10 -- error
(fromIntegral (length lista)) / 10 -- explicit typkonvertering med fromIntegral

-- Typsignatur: fromIntegral :: (Integral a, Num b) => a -> b

Egna typnamn

T.ex. type Coord = (Float, Float) definierar Coord som en tupel av två stycken Float.

Fungerar även med polymorfa typer: type AssocList a b = [(a, b)] (a och b är typvariabler).

Typsignaturer (Haskell)

Skrivs ovanför (funktioner) eller efter (anonyma funktioner).

Exempel: isEven :: Int -> Bool

Typinferens

Haskell har lat typinferens - om ingen typ avges kommer typen att bestämma senare, av kontext.

Exempel: 

t1 = (3, "små", "grisar")
:t t1 // t1 :: Num => (a, String, String)
head "Maskens huvud" // 'M'
tail "Maskens huvud" // "askens huvud"

Typklasser

Förekommer ofta i typsignaturer och ställer krav på deras typvariabler. T.ex. Num (numeriska), Ord (ordnade), Eq (jämförbara m. likhetsoperatorn ==), Show...

sum :: Num a => [a] -> a -- syntax: ("typklass-krav") => typ x -> typ y
Arv hos typklasser
class Eq a => Ord a where
    (<), (<=) :: a -> a -> Bool
    (>=), (>) :: a -> a -> Bool

"Varje Ord-typ måste också vara Eq."

Exempel:

import Data.Char
import Numeric

-- Typklassen Incrementable
class Incrementable a where
    inc :: a -> a -- för att kalla dig för "Incrementable" måste typen implementera "inc"
    inc2 :: a -> a
    inc2 x = inc (inc x) -- default-implementation av inc2

instance Incrementable Integer where
    inc x = x + 1
instance Incrementable Int where
    inc x = x + 1
instance Incrementable Char where
    inc c = chr ((ord c) + 1)
    inc2 c = chr ((ord c) - 32) -- ersätter default-implementationen för "inc2"

Algebraiska datatyper (ADT)

data Color = RGB Double Double Double -- "kombinerad konstruktor/typsignatur"
    deriving (Show, Eq) -- "Show" (stringify-bar), och "Eq" (jämförelse av likhet)
-- Getters/accessors
red (RGB r g b) = r
green (RGB r g b) = g
blue (RGB r g b) = b
brightness :: Color -> Double -- typsignatur
brightness (RGB r g b) = sqrt((r^2+g^2+b^2) / 3)
black = RGB 0 0 0
white = RGB 1.0 1.0 1.0

makeColorRGB r g b = RGB r g b -- funktion som skapar en RGB

En algebraisk datatyp är statisk (inga setters), och allt är publikt.

Record syntax

Record syntax -- en alternativ syntax för att skapa en ADT. "Getters" skapas automatiskt.

Nackdel: "Äter upp" namnen -- går ej att återanvända fältnamn (inom samma modul).

Exempel:

data Record = Record { name :: String, achievement :: String, measurement :: Double } deriving(Show, Eq)

Polymorfism

  • Ad hoc-polymorfism: T.ex. operator-/funktionsöverlagring. Sker i compile time.
  • Parametrisk polymorfism: T.ex. templates i C++ och generics i Java.
    • Samma kod kan köras på många olika typer, eftersom typen har abstrakteras bort.
    • T.ex. typsignaturen length :: [a] -> Int där a är en typvariabel.
  • Subtyping polymorfism (dynamisk bindning): T.ex. arvshierarkier för klasser i C++/Java. Sker i runtime.
    • En ny form av polymorfism (1980-tal).

Obs! För ALLA labbar i kursen räcker det att använda immutable (dessutom REKOMMENDERAT att göra så). Förändringsbarhet behövs inte för någon labb, inte ens de betygshöjande.

Föreläsning 3: Funktionell programmering, del 3 (24/1-2025)

Högre ordningens funktioner...

Föreläsning 3: Funktionell programmering, del 4 (30/1-2025)

Monader...