Vrednosti in tipi podatkov

Vrednosti in tipi

• Vrednost je vse, kar se da izračunati, ovrednotiti ali shraniti v podatkovno strukturo
• Vrednost je definirana kot pojem oziroma entiteta med računanjem
• Mnoge vrednosti so neprimerljive
• Tipi združujejo vrednosti za lažjo obravnavo in preprečevanje napak
• Tip je množica vrednosti in operacij, definiranih nad temi vrednostmi
• Tip ne predpisuje samo množice vrednosti, ampak tudi operacije nad njimi

Osnovni tipi

• Vsak programski jezik vsebuje osnovne in sestavljene tipe, nekateri pa tudi rekurzivne
• Osnovni tip (primitive type) je elementaren ali atomaren in ga ni mogoče razstaviti na preprostejše vrednosti
• Programski jeziki imajo vgrajene osnovne tipe
• Najobičajnejši osnovni tipi so Truth-Value, Integer, Real in Character
• Truth-Value = {true, false}
• Integer = {..., -2, -1, 0, 1, 2, ...}
• Real = {..., -1.0, ..., 0.0, ..., +1.0, ...}
• Character = {..., 'A', 'B', ..., 'Z', ..., 'a', 'b', ..., 'z', ...}
• Različni programski jeziki imajo različna imena za osnovne tipe (npr. C++, Java, Kotlin)
• Dejanska implementacija osnovnih tipov se razlikuje od jezika do jezika, kar poslabša prenosljivost programov

Nov osnovni tip

• Uporabniki lahko definirajo povsem nov osnovni tip z naštevanjem vrednosti, imenovan naštevni tip (enumeration type)
• Posamezna vrednost naštevnega tipa se imenuje enumerand
• V C++ in Adi se naštevni tip definira z naštevanjem identifikatorjev, ki predstavljajo vrednosti

Podintervalni tip

• V Pascalu se lahko definira podintervalni tip (subrange type) kot podmnožica obstoječega tipa
• Podintervalni tip 28..31 ima množico vrednosti {28, 29, 30, 31}, ki je podmnožica množice Integer
• Kotlin ima obseg (range), ki ni nov tip, ampak uporaba obstoječih tipov
• Kardinalnost množice (#) pove moč množice, torej število elementov v množici

Sestavljeni tipi

• Sestavljeni tip (composite type) ali strukturirani podatkovni tip (structured data type) je tip, katerega vrednosti so sestavljene iz preprostejših komponent
• Primeri sestavljenih tipov: n-terice, zapisi, razredi, inačice, unije, polja, množice, nizi, seznami, drevesa idr.
• Podatkovne strukture lahko opišemo z matematičnimi pojmi: kartezični produkt, disjunktna unija, preslikava, potenčna množica in rekurzivni tipi

Kartezični produkt

• Kartezični produkt je sestavljanje vrednosti dveh tipov (elementov množic) v množico urejenih parov
• Kartezični produkt n tipov S1, S2,..., Sn se piše S1 × S2 ×... × Sn
• Elementi so urejene n-terice, kjer je prva vrednost iz S1, druga iz S2 itd.
• Zapis v Pascalu, struktura v C++, razred v Javi in n-terice v Kotlinu so primeri kartezičnih produktov
• Strukture v jeziku C++ imajo množico vrednosti, ki predstavljajo pare vrednosti
• Glavna operacija nad kartezičnim produktom je izbira koordinate oziroma komponente
• Posamezne komponente zapisa tipa se izberejo z operatorjem (.) in identifikatorji, oziroma s selektorjem komponente
• Pri kazalcih na strukturo v C++ se uporablja operator puščice (->)

Izbira v n-terici

• V ML se n-terice zapisujejo podobno kot v matematiki: type oseba = string * string * int * real
• Vrednost se lahko razčleni: val (priimek, ime, starost, visina) = nekdo
• Do komponent n-terice se dostopa z identifikatorji
• V Pythonu se za dostop do komponent uporabljajo identifikatorji
• Kardinalnost kartezičnega produkta: #(S × T) = #S × #T
• Homogene n-terice so primeri kartezičnega produkta z elementi iz iste množice
• Kardinalnost homogene n-terice: #(Sn) = (#S)n
• 0-terica nima komponent, ima natanko eno vrednost: Unit = {()}
• Unit ni prazna množica, ampak predstavlja n-terico brez komponent, ter ustreza void v C++ in Javi

Disjunktna unija

• Je združitev vrednosti, kjer se izbere vrednost iz dveh tipov
• Vrednost iz množice S se označi z značko prvi, iz T pa z drugi
• Značka (angl. tag) pove, iz katere množice smo izbrali vrednost
• Splošna oblika disjunktne unije je S1 + S2 + ... + Sn
• Osnovni operaciji nad disjunktno unijo sta testiranje značke in projekcija
• Primeri disjunktne unije: zapisi z inačico v Adi, unije v C++, konstruktorji v ML
• Unije v C++ ne uporabljajo značk za ločevanje vrednosti, ampak programer shrani tip komponente v spremenljivko
• Unije v C++ so lahko tudi anonimne

Preslikava

• Funkcija m : S → T preslika vsako vrednost x iz množice S v vrednost m(x) iz množice T
• Vrednost m(x) se imenuje slika od x
• Zapis S → T pomeni družino vseh preslikav iz S v T
• Polja lahko obravnavamo kot preslikave iz množice indeksov v množico komponent polja
• Dostop do komponente je preslikava indeksa v pozicijo komponente
• V C++ je množica indeksov lahko le celoštevilčnega tipa
• V Pascalu in Adi je množica indeksov lahko katerikoli diskretni osnovni tip
• Goin Pythonu omogoča rezanje polja z operatorjem

Dvodimenzionalna polja

• Večina jezikov pozna večdimenzionalna polja, do komponent dostopamo preko n indeksov
• Dvodimenzionalna polja so preslikava urejenih n-teric v množico komponent polja

Funkcije

• Funkcije so preslikave, kjer funkcijska abstrakcija izvede preslikavo iz S → T z algoritmom
• Funkcijska abstrakcija ni enaka matematični funkciji in ima lahko n parametrov
• Funkcija f(double a, int b) {...} opravi preslikavo Real × Integer → Real

Potenčna množica

• Potenčna množica od S (℘S ) je množica vseh podmnožic množice S: ℘S = {s | s ⊆ S}
• Kardinalnost potenčne množice: #(℘S) = 2#S
• Osnovne operacije nad množicami: testiranje pripadnosti, vsebovanosti, unija, presek, razlika
• Pascal neposredno podpira potenčne množice (set of)

Kazalci in reference

• So abstrakcija pomnilniških naslovov, to je pomnilniška lokacija, v kateri je zapisan naslov pomnilniške lokacije, kjer je shranjena vrednost
• Zaloga vrednosti kazalčnega tipa je množica celoštevilčnih vrednosti, ki označujejo pomnilniške naslove
• Na naslovu, kamor kaže kazalec, je lahko vrednost poljubnega tipa
• Obstajajo kazalci na polja, strukture, objekte, funkcije in kazalci na kazalce
• NULL, null, nil je posebna vrednost, ki ne predstavlja pomnilniškega naslova in pove, da kazalec ne kaže na nobeno vrednost
• Najpomembnejša operacija nad kazalci je dereferenciranje
• S kazalci upravljamo s pomnilniškimi lokacijami, zato moramo biti pazljivi pri delu z njimi
• Kazalčna aritmetika, ki jo lahko izvajamo nad kazalcem , ni dovojena za reference
• Nad referenco se dereferenciranje izvedeImplicitno
• Reference so "varni kazalci", saj ne omogočajo kazalčne aritmetike
• Java pozna reference, kazalcev pa ne
• Referenca je konstanten kazalec, kjer se derefenciranje izvedeImplicitno
• V C++ reference niso vrednosti prvega razreda in ne moremo ustvariti polja referenc
• Polje je shranjen naslov prvega elementa, naslednji izrazi so ekvivalentni: polje, &polje[0], polje[i], *(polje+i)

Rekurzivni tipi

• Rekurzivni tip (T) je definiran sam s seboj, definiran je kot T = ... T ...
• Primeri: datatype seznam = nil | cons of int * seznam
• Kardinalnost rekurzivnega tipa je neskončna
• Znan predstavnik sta seznam (List) in drevo
• Rekurzivne tipe v C++ in Adi se definira s kazalci, v novejših jezikih pa neposredno

Nizi

• Zaporedje znakov
• Implementiran v programskih jezikih
• Nejasnosti glede ali je niz osnovni ali sestavljeni tip
• Različni jeziki jih obravnavajo: osnovni tip, polje znakov ali seznam znakov
• Operacije nad tipi: stikanje dveh nizov (konkatenacija), izbira znaka ali podzina in leksikografska ureditev

Sistemi tipov

• Združevanje vrednosti v tipe omogoča boljšo organizacijo podatkov in zagotavlja zaščito pred nesmiselnimi operacijami
• Jezikovni tipi se razlikujejo od nizkonivojskih - kjer je enoten tip byte ali beseda
• Preverjanje se izvede pred samo operacijo

Statično in dinamično tipizirani jeziki

• Ločijo se glede na čas preverjanja tipov
• statično tipizirani jeziki (preverjanje že o času prevajanja)
• dinamično tipizirani jeziki (imajo le vrednosti določen tip, spremenljivka privzame tip od različnih vrednosti v različnih časih (polimorfne)

Močno in šibsko tipizirani jeziki

• Po preverjanju tipov ločimo
• Močno tipizirane jezike (popolno preverjanje tipov -> ne moremo prirediti spremenljivki, ki je drugačnega tipa)
• Šibko tipizirane jezike (nepopolno preverjanje tipov -> pri privede do nepravilnega obnašanja)
• Pre-ANSI C pri klicu *funkcije (procedure) ne preverja

Ekvivalenca tipov

• Nekatere operacije zahtevajo ekvialentne tipe ("=", ne prireditveni operator)
• Kaj to pomeni je odvisno od programskega jezika:
  • strukturno ekvivalenca: imata T in isto množico vrednosti
  • ekvivalenco po imenu: sta T in definirana na istem mestu
• Strukturno ekvivalenco tipov najdemo v jeziku ML, ekvivalenco po imenu pa v jezikih C, C++ in ada.
• Procedura p(f1) je pravilna, ker sta tipa spremenljivk in imensko ekvivalentna
• Napak klic p(f2), ker niso enaka imena tip v header file-u

Vrednosti prvega in drugega razreda

• Proceduralne in funkcijske abstrakcije so vrednosti
• Ne moremo jih ovrednotiti, prirejati ali uporabljati kot komponente sestavljenih tipov (vrednosti drugega razreda) -Logični vrednosti, cela števila, zapise, polja imenujemo vrednosti prvega razreda
• Programski jeziki delijo implementacije
• Je zaželeni, da programski jeziki zadostujejo principu polnosti tipa (type completeness principle). - Operacije naj ne bodo omejene glede na vrsto tipa.

Izrazi

• Je programska fraza, ki jo izračunamo za določen namen
• Močni imeti različen način postavitve / sintakse
• Osnovne so:
  • literali (število, char)
  • agregati (string)
  • funkcijski klici
  • pogojni izrazi
  • bločni izrazi
  • dostopi do konstant in spremenljivk.

Literali in agregati

• Literal: najpreprostejša vrsta izraza - "symbol"
• Agregat: zgradi sestavljeno vrednost iz njenih posameznih komponent
  • ML omogoča agregate za n-terice, zapise in sezname, programski jezikada in C++ za zapise in polja, j e- zik java za polja in - programski jezik pascal za množice.

Agregati

• tipa Real Real v jeziku ML:(a*2.0, b/2.0)
• Agregat za seznam v jeziku ML: [31, if prestopno (leto) then 29 else 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
• Agregat za polje v jeziku Java: int[] dolzinaMesec = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

Klic funkcije

• Izračuna rezultat z uporabo funkcijske abstrakcije nad parametri
• Oblika: F(AP)
• Splosna oblika z n parametri: F(AP1, AP2,..., APn)
• Funkcijsko abstrakcijo je lahko kakrsen koli izraz
• Je mozno da izpise na podlagi bool vrednosti
• Je mozno imeti operatorje

Operatorji

• Lahko ga obravnavamo podobno kot funkcijo
• S tem se izognmo pravilom in omogocimo programerju deklariranje novih operatorjev.
• Binarne operatorje pisemo med operandoma (infix), v Lisp pred svojimi operandi (prefix)(E1 (E1, E2))
• Pri postfixnotaciji je pa je operator za svojimi operandi
• Prioriteta pove kdaj se operacija izvede
• Razen leve in desne asociativnosti poznamo se neasociative operatorje (ne moremo uporabiti večkrat v istem izrazu)
• Nekateri programski jeziki omogočajo tudi ”short circuit ovrednotenje” (ada and then, or else) (c++ && ||) (izvajanje konjunktivnega logičnega izraza prekine ob prvem podizrazu, ki vrača logično vrednost false)
• V večini programskih jezikov sta prioriteta in asociativnost operatorjev predpisani
• Novi operatorji morajo imeti omagoceno prioriteto in asociativnost
• Redefiniramo lahko samo obstoječe operatorje (C++)

Pogojin izraz

• ima različne podizraze in ima praviloma pogol, da se pogoj izbere v vredenotijo natančno enkrat

Konstante in spremebljivke

• Double, Float: Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY,
• Double.NaN, Float.POSITIVE_INFINITY, Float.NEGATIVE_INFINITY, in Float.NaN.
• Int and Long: Int.MIN_VALUE, Int.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE.
• Char: Char.MIN_VALUE, Char.MAX_VALUE.
• String: String.Companion.EMPTY. Unit