Vrednosti in tipi podatkov

Vrednosti in tipi

• Vrednost je vse, kar se lahko izračuna, ovrednoti, shrani ali se pridruži podatkovni strukturi.
• Vrednost je lahko rezultat funkcije ali argument procedure.
• Vrednost se definira kot pojem ali entiteta, ki obstaja med računanjem.
• Mnoge vrednosti so med seboj neprimerljive (npr. true in 'a').
• Vrednosti se združujejo v tipe za lažjo obravnavo in preprečevanje napak.
• Tip je množica vrednosti definirana z operacijami, ki delujejo nad njimi.
• Tip ne definira samo množice vrednosti, ampak tudi operacije nad temi vrednostmi.

Tipi

• Vsak programski jezik vsebuje osnovne in sestavljene tipe.
• Osnovni ("primitive") ali atomarni tip so elementarni tipi, katerih vrednosti se ne morejo razstaviti na preprostejše vrednosti.
• Programski jeziki imajo že vgrajene osnovne tipe.
• Najpogostejši osnovni tipi so Truth-Value (Bool), Integer (int), Real (float) in Character (char).
• Različni programski jeziki uporabljajo različne imena za osnovne tipe (npr. C++, Java, Kotlin).
• Dejanska implementacija osnovnih tipov se razlikuje med jeziki, kar zmanjšuje prenosljivost programov.
• Nekateri jeziki omogočajo uporabnikom definirati nove osnovne tipe z naštevanjem vrednosti, kar se imenuje naštevni tip ("enumeration type"), kjer je posamezna vrednost enumerand ("enumerand").
• V C++ in Ada se naštevni tip definira z naštevanjem identifikatorjev, ki predstavljajo njihove vrednosti.

Podintervalni tip

• V Pascalu se lahko definira podintervalni tip ("subrange type"), ki je podmnožica obstoječega tipa (npr. 28..31 je podmnožica Integer).
• Kotlin ima obseg (range), ki ni nov tip, ampak uporaba obstoječih tipov: IntRange, LongRange, CharRange.
• Kardinalnost ("cardinality") množice označuje moč množice in se zapiše z #.
• Kardinalnost je število elementov v množici.
  • #Truth-Value = 2
  • #BarvaKarte = 4

Sestavljeni tipi

• Sestavljeni tip ("composite type") ali strukturirani podatkovni tip je tip, katerega vrednosti so sestavljene ali zgrajene iz preprostejših vrednosti ali komponent.
• Primeri sestavljenih tipov: n-terice, zapisi, razredi, inačice, unije, polja, množice, nize, sezname, drevesa, sekvenčne datoteke, datoteke z naključnim dostopom in relacije.
• Vse podatkovne strukture se lahko razume in opiše z matematičnimi pojmi, kot so kartezični produkt, disjunktna unija, preslikava, potenčna množica in rekurzivni tipi.

Kartezični produkt

• Kartezični produkt ("cartesian product") je preprosta oblika sestavljanja vrednosti, kjer se vrednosti dveh tipov (elemente dveh množic) združi v množico urejenih parov.
• S × T = {(x, y) | x ∈ S ∧ y ∈ T}
• Kartezični produkt n tipov S₁, S₂, ..., Sₙ se piše kot S₁ × S₂ × ... × Sₙ.
• Elementi so urejene n-terice, kjer je prva vrednost iz S₁, druga iz S₂ itd.
• Primeri: zapisi v jeziku Pascal, strukture v jeziku C++, razredi v jezikih Java in n-terice v jeziku Kotlin.
• Strukture v C++ se lahko predstavijo kot kartezični produkt (primer: struct Karta {BarvaKarte barva; StevEnum stev;}).
• Glavna operacija nad kartezičnim produktom je izbira koordinate ali komponente.
• Komponente zapisa tipa se izberejo z operatorjem . in pripadajočima identifikatorjema.
• Pri kazalcih na strukture v C++ se za izbiro selektor komponente uporablja operator ->.

Izbira v n-terici

• V jeziku ML se n-terice zapišejo podobno kot v matematiki, npr. type oseba = string * string * int * real.
• Za dostop do komponent n-terice se uporabljajo identifikatorji.
• Python omogoča razpakiranje n-teric znotraj kode.
• Kardinalnost kartezičnega produkta je #(S × T) = #S × #T.
• Homogene n-terice so poseben primer kartezičnega produkta z elementi iz iste množice (Sn = S × ... × S).
• Kardinalnost homogene n-terice je #(Sn) = (#S)n.
• 0-terica nima komponent; množica S⁰ ima natanko eno vrednost: Unit = {()}.
• Unit ni prazna množica, temveč n-terica brez komponent; ustreza tipu Unit v Kotlin in void v C++ ter Java.

Disjunktna unija

• Disjunktna unija ("disjoint union") združuje vrednosti iz dveh (različnih) tipov: S + T = {prvi x | x ∈ S } ∪ { drugi y | y ∈ T}.
• Vrednost iz množice S se označi z značko prvi, iz T pa z drugi, kar pove, iz katere množice je vrednost izbrana.
• Splošna oblika disjunktne unije je S₁ + S₂ + ... + Sₙ.
• Osnovni operaciji nad disjunktno unijo sta testiranje značke in projekcija.
• Kardinalnost disjunktne unije je #(S + T) = #S + #T.
• Posplošitev: #(S₁+S₂+...+Sₙ) = #S₁ + #S₂ + ... + #Sₙ
• Primeri: zapis z inačico v jeziku Ada, unije v jeziku C++, konstruktorji v jeziku ML ter unije v jeziku PHP in TypeScript.
• Unije v C++ ne uporabljajo značk za ločevanje vrednosti, programer pa tip komponente shrani v posebni spremenljivki.
• Unije se uporabljajo za shranjevanje izključujočih se vrednosti ali pretvorbo med vrednostmi; lahko so tudi anonimne.

Preslikava

• Preslikava (mapping) ali funkcija je pomemben pojem v programskih jezikih.
• 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: S → T = {m | x ∈ S ⇒ m(x) ∈ T}.
• Polja se lahko obravnavajo kot preslikave in so običajno shranjena kot zaporedje komponent.
• Dostop do komponente je tako preslikava indeksa v pozicijo komponente.
• Indeks se zapiše med oglate oklepaje [ ]. Zapis polja je array [S] of T.
• V C++ so indeksi lahko le celoštevilčni, v Pascalu in Adi pa je lahko množica indeksov poljubni diskretni osnovni tip.
• V Python-u in Go omogočajo rezanje polja z operatorjem :.
• Pri večdimenzionalnih poljih se dostopa do komponent z n indeksi in se lahko gleda kot na preslikavo urejenih n-teric v množico komponent.
• Funkcijska abstrakcija opravi preslikavo iz S v T z algoritmom, ki vzame vrednost iz S in izračuna sliko v T.
• Funkcijska abstrakcija implementira funkcijo z algoritmom.
• V večini programskih jezikov ima lahko funkcijska abstrakcija n parametrov, ki se lahko obravnavajo kot funkcija, ki sprejme en parameter v obliki n-terice.

Potenčna množica

• Množica vseh podmnožic množice S se imenuje potenčna množica ("power set") od S: 𝒫S = {s | s ⊆ S}.
• Kardinalnost potenčne množice: #(𝒫S) = 2#S
• Osnovne operacije nad množicami vključujejo testiranje pripadnosti elementa množici, testiranje vsebovanosti podmnožice, unijo, presek in razliko množic.
• Programski jezik Pascal je eden od redkih, ki neposredno podpira potenčne množice.
• Primer: type Barva = (rdeca, zelena, modra); Odtenek = set of Barva;
• Množica vrednosti tipa Odtenek je {{}, {rdeca}, {zelena}, {modra}, {rdeca, zelena}, {rdeca, modra}, {zelena, modra}, {rdeca, zelena, modra}}.

Kazalci in reference

• Kazalci oz. reference so abstrakcija pomnilniških naslovov.
• Kazalec je pomnilniška lokacija, v kateri je zapisan naslov pomnilniške lokacije, kjer je shranjena vrednost.
• Vrednost kazalca je torej pomnilniški naslov, zaloga pa množica celoštevilčnih vrednosti, ki označujejo pomnilniške naslove.
• Na naslovu, kamor kaže kazalec, je lahko vrednost poljubnega tipa (osnovnega ali sestavljenega).
• Obstajajo kazalci na polja, strukture, objekte, funkcije in tudi na kazalce.
• Programski jeziki običajno definirajo posebno vrednost (NULL, null, nil), ki ne predstavlja nobenega pomnilniškega naslova, temveč pove, da kazalec ne kaže na nobeno vrednost.
• Najpomembnejša operacija nad kazalci je operacija dostopa do vrednosti, na katero kazalec kaže oz. dereferenciranje.
• S pomočjo kazalcev učinkovito upravljamo s pomnilniškimi lokacijami.
• Nad kazalci je možna kazalčna aritmetika.
• Določene operacije, kot je npr. dereferenciranje se pri referenci izvedejo vedno (implicitno)
• Tako imenovani varni kazalci ("safe pointers"), ne omogočajo kazalčne aritmetike.
• Programski jezik java kazalcev sploh ne omogoča.

Razlika med kazalcem in referenco

• Razlika med kazalcem in referenco je majhna (referenca je konstanten kazalec, pri kateri se derefenciranje izvede implicitno).
• Prav tako v jeziku C++ reference niso vrednosti prvega razreda.
• Ne more se ustvariti polja referenc, kazalce na reference in reference na void.
• V polje je dejansko shranjen naslov prvega elementa.

Rekurzivni tipi

• Rekurzivni tip ("recursive type") je tisti, katerega vrednosti so sestavljene iz vrednosti tipa samega (definiran je sam s seboj).
• Kardinalnost mu je neskončna.
• Običajna predstavnika rekurzivnega tipa sta seznam (List) in drevo.
• Definicija v jeziku ML je: datatype seznam = nil | cons of int * seznam.
• Osnovne operacije nad seznami so testiranje, ali je seznam prazen, izbira prvega elementa in preostanka, konstrukcija novega seznama iz elementa, računanje dolžine seznama in stikanje seznama.
• Seznami se pogosto uporabljajo.
• V C++ in Ada rekurzivne tipe definirajo s kazalci.
• V novejših programskih jezikih zapišemo rekurzivne tipe neposredno.

Nizi (angl. string)

• Zaporedje znakov, ki je implementirano v mnogih programskih jezikih
• Vendar je implementacija niza zelo različna
• Možni so : Je niz osnovni ali sestavljeni tip in katere operacije nad nizi so določene.
• Primeri implementacije: Niz je lahko že vgrajen tip, polje znakov (char) ali seznam znakov (prolog).
• Tipične operacije nad nizi pa so:
  • Stikanje dveh nizov (konkatenacija) in
  • Izbira znaka ali podniza pri leksikografski ureditvi nizov.

Python

• S pomočjo operatorja : lahko polja razrežemo

Sistemi tipov

• Združevanje vrednosti v tipe omogoča uspešnejše opisovanje podatkov.
• Programi so tako zaščiteni pred izvajanjem nesmiselnih operacij, kot je na primer množenje znaka z logično vrednostjo
• Prav v tem pogledu se visokonivojski programski jeziki očitno razlikujejo od nizkonivojskih programskih jezikov, kjer je edini 'tip' zlog ali beseda".
• Preverjanje tipov se lahko izvaja:
  • V času prevajanja (statično preverjanje tipov) in
  • v času izvajanja (dinamično preverjanje tipov).
• Jezični statičnih tipov ("statically typed languages") in
• jeziki dinamičnih tipov ("dynamically typed languages").
• Vsaka spremenljivka in vsak parameter je natanko dno določena
• Pri statičnih tipih se preverja tipa pri prevajanji, v kolikor pa je jezik dinamičen, pa se tipi tipa ne rabijo ujemati, ker se lahko definirajo sproti

Sistemi tipov: močno in šibko izraženi jeziki

• Močno tipizirani jeziki (“strongly typed languages") in
• Šibko tipizirani jeziki (“weakly typed languages").
• Ne moremo prirediti vedndoti tipa, ki ni predviden.

Ekvivalenca tipov

• Nekatere operacije zahtevajo, da so tipi operandov ekvivalentni. Se pravi, da označimo T = T'. Je tip A enakovreden tipu B?
• Kaj natančno ekvivalenca tipov pomeni, je odvisno od programskega jezika.
  • Strukturno ekvivalenco: T = T', če imata T in T' isto množico vrednosti in
  • Ekvivalenco po imenu: T = T', če sta T in T' definirana na istem mestu.
• Strukturno ekvivalenco tipov najdemo v jeziku ML, ekvivalenco po imenu pa v jezikih C, C++ in ada.

Vrednosti drugega razreda

• Proceduralne in funkcijske abstrakcije obravnavamo kot vrednosti, zato jih lahko prenašamo kot argumente.
• Pri logičnih vrednostih, celih številih, zapiseh, poljih itd lahko uporabljamo vrednosti prvega razreda, medtem ko funkcijska abstrakcija ne.
• Jeziki, ki se več ne izogibajo delitvi vrednosti na razrede pa omogočajo uporabo vseh vrednostih pri vseh abstraktnih tipod.

Izrazi

• Literali,
• agregati,
• funkcijski klici,
• pogojni izrazi,
• bločni izrazi in
• dostopi do konstant in spremenljivk.

Literali

• Simbol, ki določa vrednost nekega tipa, kot so '$', POZDRAV, 365, 3.1416.

Agregat ili skupek

• je izraz, ki zgradi sestavljeno vrednost iz njenih komponent. Vrednosti komponent so določene z ovrednotenjem podizrazov.

Klic funkcije ("function call")

• Izračuna rezultat z uporabo funkcijske abstrakcije nad parametri.
• Klic funkcije ima običajno obliko F(AP), kjer identifikator F določa funkcijsko abstrakcijo, AP pa določa dejanski parameter oz. аргумент funkције. Аргумент је обично из.
• Pri večini jezikov je F le identifikator funkcijske abstrakcije. V jezikih, ki obravnavajo funkcijsko abstrakcijo kot vrednost prvega razreda, je F lahko kakršenkoli izraz, ki vrne funkcijsko abstrakcijo.

Operatorji

• Operator lahko obravnavamo podobno kot funkcijo.
• Konverzacije:
  • ΘΕ је еквивалентно ⊕(E)
  • Е1⊕Е2 је еквивалентно ⊕(Е1, Е2)
• Takšni jeziki omogočajo lažje učenje, saj se izogibajo različnim pravilom za operatorje in funkcije
• Dogovor, da pišemo binarne operatorje med operandoma, se imenuje infiksna notacija in jo podpira večina programskih jezikov.
• V jeziku Lisp pa je vsak funkcijski klic izražen v prefiksni notaciji, kjer je operator pred svojimi operandi.
• V postfiksni notaciji pa je operator za svojimi operandi.
• Operatorji pri katerim izvajamo operacijo prej kot ostale Prioriteto operaterjev
• Pozana še neasotiativne operatorje
• Z oklepaji v in zaklepaji pa lahko vedno prekrijemo privzeto prioriteto in asociativnost.

Pogojni izraz

• Včasih imenovani pogojne operaterje imajo podizraze pri kateri se izbere določen izraz.
• Pogojnega izreza v javi oziroma c++ je videti takole (x > y) ? x : y;
• Pogojni izrazi v Pythonu ponavadi delujejo skozi if Else zanke.