TIES448 luento 14

Tietorakenteet

  • Ohjelmia on tylsä rakentaa pelkistä Int:eistä ja Bool:eista
  • Olennaisesti kaikki kielet sisältävät jonkinlaisen tietueen (struct, record, tjsp.) * Oliokielissä oliot ovat pohjimmiltaan tälläisiä
  • Taulukoita on myös suurimmassa osassa kieliä. Ne ovat hyvä primitiivirakenne
  • Variantteja on kasvavassa määrin ja nykyisin ne nähdään lähes yhtä perustavanlaatuisena kuin tietueet
  • Näiden kääntäminen ei ole ajatustasolla kovin haastavaa, mutta niissä on useampikin knoppi.

Tietue

Puhutaan siis tälläisistä

RECORD Pari BEGIN
 x : INTEGER;
 y : INTEGER
END

Mitä operaatioita tietueet tuovat mukanaan?

Tietueiden operaatiot

  • Kentän lukeminen
    • p.x ?
  • Kenttään sijoittaminen
    • p.x := jotain ?
  • Tietueen alustaminen
    • p = new Pari(15,15)?

Kentän lukeminen

  • eli Projektio
  • Syntaktisesti vasemmalle rekursiivinen. Jos jäsennin työkalusi osaa post-fix operaatioita, niin ne sopivat tähän.
  • Esim. h.c.x
test p1 . p2 . p1->p2 x x p1->x h h p2->h c c p2->c

Kentän lukeminen

  • h.c.x on lauseke, missä h on myös lauseke (esim. kutsu)
  • Kääntäjän kirjapidosta pitää selvitä tyypit h:lle ja h.c:lle, jotta tiedetään miten kentät löydetään

Kenttään sijoittaminen

Mitä tähän saa kirjoittaa?

BEGIN
...
??? := 15;
...
END.
  • Muuttujan?

Entäpä?

p.x    := 15;
f(0)   := 15;
f(0).z := 15;
a[1]   := 15;
p.f(0).z[1] := 15;

LHS

Yleensä = merkin vasen puoli voi olla:

  • muuttujan
  • viittauksen tietuemuuttujan kenttään
  • taulukkomuuttujan indeksoinnin

Konseptitasolla siellä voi olla ylipäänsä lauseke, joka sievenee viitteeksi, johon voi sijoittaa (C++ etenee tähän suuntaan).

Mutka 1

  • Jos = merkin vasen puoli voi olla viite kenttään, esim p.x = 15, niin syntaksipuusta + kirjanpidosta pitää voida selvittää:
    • Mitä tyyppiä p on (tyypitetty AST)
    • Mihin p on talletettu, rekisterit/muisti? (kirjanpito)
    • Miten p:n tyyppisestä tietueesta löydetään kenttä x? (kirjanpito)

Tietueen esittäminen ja alustaminen

  1. Päätetään laittaa kentät peräkkäin muistiin [I32 | <align> | I32] ja muuttujaan muistiosoite pötkön alkuun
    • p.y --> (p)*,
    • p.y --> (p + 32)* (align 4, ei rakoa)
    • Systemaattista!
  2. Päätetään sijoitettaa kentät muuttujiin / rekistereihin
    • Esim. kutsut käännetään niin, että argumenttitietueen kentistä tulee kustakin oma argumenttinsa
    • Voi välttää muistiliikennettä
    • Tietueet ovat olemassa vain etupäässä

Hyvä kääntäjä tekee molempia, riippuen tilanteesta.

Tietueen toteuttamisesta

  • Pääsääntöisesti kirjanpitoa (muuttujien tyypit, tietueiden rakenteet, kenttien sijainnit)
  • Kannattaa käyttää aikaa siihen, että tekee tämän itselleen helpoksi
  • LLVM: tietueet nimettömiä. Kenttiin viitataan indeksillä => kirjanpidosta pitää selvitä kentän indeksi nimellä haettaessa.

Taulukot

Taulukot lienevät jo tuttuja. Operaatiot:

  • Taulukon luominen/alustaminen
  • Taulukon indeksointi
  • Indeksiin sijoittaminen

Taulukon luominen ja indeksointi

  • Yksiulotteinen taulukko on vain pötkö muistia. Taulukkomuuttujassa on muistiosoite pötkön alkuun.
    • Indeksointi: a[5] = a + 5*<alkion_koko>
  • Kaksi- tai useampiulotteinen taulukko:
    1. Pötkö muistia.
      • indeksointi laskemalla, esim: a[5][3] == a[3+a_cols*5] (rivi vs. sarake ensin)
    2. Taulukollinen osoittimia, jotka osoittavat yksiulotteisiin rivi- tai saraketaulukoihin.
      • Indeksoidaan ensimmäistä taulukkoa, saadaan osoitin seuraavaan, indeksoidaan sitä... jne.

Sijoittaminen on muistiinkirjoitus, kunhan osoite selviää yo. keinoin

Taulukot

  • Vähintään kääntäjän kirjanpito tallettaa taulukon mitan
  • Erikoishaaste:
    • Taulukon ohi indeksoiminen on merkittävä tietoturvaongelma (heartbleed jne)
    • Jos teet kielen vuonna 2018, ohi-indeksoinnin mahdollisuutta ei voi sallia
    • Helppo ratkaisu: Koko talteen ajonaikaisesti + tarkastus kun indeksoidaan
    • Rautaratkaisu: Kikkoja kuten sijoittaa taulukko muistisivun loppuun, jolloin tulee page-fault kun menee ohi
    • Kikkaratkaisu: Baggy bounds yms. (google scholarista lähes loputtomasti näitä)

Variantit / Summatyypit / Tagged Union / Enum yms.

Esim.

  • Haskell: data AST = Plus AST AST | Constant Double

  • Rust enum AST { PLUS { left: AST, right: AST }, Constant { val: f32 } }

  • Tietue tallettaa kaikki annetut kentät kerralla.

  • Variantissa on kulloinkin yksi annetuista kentistä.

  • Nämä ovat yhtä hyödyllisiä kuin tietueet (nykykielissä tämä on jo huomattukin)

  • Niiden puute aiheuttaa saman asian koodaamisen käsin (perinnällä tjsp)

Variantti on tietueiden duaali

  • Tietueen luomiseen tarvitset kaikki kentät
  • Variantin voi luoda mistä tahansa kentästä
  • Tietueesta voit ottaa minkä tahansa kentän ja käsitellä sen
  • Variantin kanssa joudut kertomaan miten kaikki kenttä käsitellään

Varianttien rakenne ja operaatiot

Puhutaan nyt Rust/Haskell tyylisistä varianteista:

enum AST { Plus { left: AST, right: AST }
         , Constant { val: f32 } }
  • Sisältää tiedon mikä vaihtoehto on valittu ja mikä sen sisältö on
  • Luominen: `AST::Constant(14);
  • Projektio.
    • match f { Plus{left,right} => println!("Plussa") | Constant{val} => println!("Vakio")` }
  • perinteinen switch-case on tälläisen toukkamuoto

Variantin esitystapa

  • Hyvä perustapa: vaihtoehto koodattuna järjestysnumeroksi + osoitin varsinaiseen dataan muistissa
  • Pienet tietueet: Varataan muistia vaihtoehtokentälle + riittävästi suurimman alkion tallettamiseen
  • Yksinkertainen match voidaan toteuttaa hyppytauluna:
    • Generoidaan kaikkien tapausten koodit
    • Generoidaan hyppykäskyt kuhunkin tapaukseen
    • Tehdään epäsuora hyppy n:nteen hyppykäskyyn, missä n on vaihtoehto.
    • (pattern matching on oma lukunsa)
  • LLVM-huomio: LLVM ei tue variantteja suoraan. Joudut tekemään sopivan kokoisen tietueen ja bitcastaamaan sen tyypiksi, jota se oikeasti kulloinkin on.

Tietorakenteet ja IR

Suositus:

  • tietueet, taulukot ja variantit ovat olemassa vielä IR:ssä
  • varsinainen esitys päätetään IR -> konekoodi muunnoksen aikana

Esim. LLVM ratkaisee tämän näin. (Ja jos tähtäät LLVM:ään, pääsetkin aika helpolla tässä)

Mitä tapahtuu tässä?

PROCEDURE foo(x:INTEGER) BEGIN x := 2 END
...
x := 1;
foo(x);
WRITE(x)
...
  • Tulostuuko 1 vai 2?

Mitä tapahtuu tässä?

RECORD Point BEGIN x:Int; y:Int END
...
PROCEDURE foo(p:Point) BEGIN p.x := p.y END
...
p.x := 1;
p.y := 2;
foo(p);
WRITE(p.x)
...
  • Tulostuuko 1 vai 2?

Muistinhallinta

"Pitäs saada TIES448 harkka tehtyä":

  • Manuaalinen muistinhallinta. Käytä libc:n malloc ja free komentoja.
    • Manuaalisen muistinhallinan toteuttaminen itse ei ole hyvä ajatus (paitsi oppimiskokemuksena)
  • Automaattinen muistinhallinta. Käytä Boehm–Demers–Weiser keräintä. Yksinkertaisimmillaan, s/malloc/GC_malloc/g

Miksi GC?

  • Jos et tee rautatason reaaliaikakieltä, ei ole mitään syytä olla ilman
  • Esim:
    • dangling-pointers
    • vapauttamaton muisti
    • double-free
    • helpot (persistentit/monimutkaiset) rakenteet
    • ohjelmointi on helpompaa ja halvempaa
    • modulaarisuus kasvaa
  • (reaaliaikajärjestelmillekin on roskienkeruumenetelmiä, ihan käytössäkin)

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.