Harjoitukset 5 - 2.5.2016
Pisteytys
Näistä demoista voi saada 0-6 pistettä ja 3 bonuspistettä, joilla voit korvata aiemmissa demoista puuttuvia pisteitä.
Oppimistavoitteet
- Tunnistat Harpermaisen syntaksitaulun ja osaat jotenkin lukea sellaista
- Ymmärrät summa- ja tulotyyppien semantiikan (ts. recordit ja variantit)
- Osaat tyypittää määritelmiä ja operaatioketjut
- Osaat tyypittää muuttuvaisia (assignable, "ohjelmoijan muuttuja")
- Tutustut kieleen, jossa on lvalue/rvalue rajauksen sijaan sama asia tehty tyypeillä.
Kieli
Huom Voit käyttää myös omaa harjoitustyökieltäsi tässä kohtaa valitsemalla siitä vastaavan laajuisen osan.
Tarkastellaan edellisen demokerran kieltä pienin lisäyksin. Selvyyden vuoksi, esitetään ensin peruskieli ja sen jälkeen eri lisäykset tehtävittäin.
Abstrakti muoto | Syntaksi | Selite | |
---|---|---|---|
Typ τ ::= | \(\text{num}\) | Number | Numerotyyppi |
\(\text{str}\) | String | Merkkijonotyyppi | |
\(\text{bool}\) | Bool | Merkkijonotyyppi | |
Exp e ::= | \(x\) | alphanum | Muuttuja |
\(\text{num}[n]\) | n | Numero | |
\(\text{str}[s]\) | "s" | Merkkijono | |
\(\text{bool}[b]\) | b | Totuusarvo | |
\(\text{plus}(e_1;e_2)\) | \(e_1\) + \(e_2\) | Yhteenlasku | |
\(\text{mul}(e_1;e_2)\) | \(e_1\) * \(e_2\) | Kertolasku | |
\(\text{cat}(e_1;e_2)\) | \(e_1\) ++ \(e_2\) | Yhteenlasku | |
\(\text{len}(e)\) | \(e\).length() | Merkkijonon mitta | |
\(\text{null}(e)\) | null \(e\) | Onko tyhjä? | |
\(\text{let}(e_1;x.e_2)\) | let \(x\) be \(e_1\) in \(e_2\) | Lokaali sidonta | |
\(\text{if}(e_1;e_2;e_3)\) | if \(e_1\) then \(e_2\) else \(e_3\) | Ehtolause |
Huom Jos et voi/halua jatkaa edellisen demokerran tehtävääsi, voit toteuttaa vain seuraavat lisäykset. Testausta varten joudut kuitenkin toteuttamaan yo. kielestä vähintään literaalit ja ja tyypit.
Lisätään kieleen yksinkertaisimmat mahdolliset tietueet ja variantit. Yksinkertaisin tietue on tässä tapauksessa järjestetty pari kahdesta eri alkiosta ja yksinkertainen variantti on puolestaan kahden tyypin liputettu yhdiste (tagged union).
Tehtävä 1 -- Rakenteet
Abstrakti muoto | Syntaksi | Selite | |
---|---|---|---|
Typ τ ::= | \(\text{unit}\) | unit | 0:n alkion monikko |
\(\text{product}(\tau_1; \tau_2)\) | \((\tau_1,\tau_2)\) | Pari (2:n alkion monikko) | |
\(\text{void}\) | void | 0:n alkion variantti | |
\(\text{sum}(\tau_1; \tau_2)\) | either \(\tau_1\ \tau_2\) | Ripa (2:n alkion variantti) | |
Exp e ::= | \(\text{trivial}\) | () | 0:n alkion monikko |
\(\text{pair}[e_1;e_2]\) | \((e_1,e_2)\) | Pari | |
\(\text{fst}[e]\) | fst \(e\) | Parin ensimmäinen | |
\(\text{snd}[e]\) | snd \(e\) | Parin toinen | |
\(\text{left}[e]\) | left \(e\) | Injektio vasemmalle | |
\(\text{right}[e]\) | right \(e\) | Injektio oikealle | |
\(\text{case}[e;x_1.e_1;x_2.e_2]\) | case \(e\) of {left \(x_1\) -> \(e_1\); right \(x_2\) -> \(e_2\)} | Haarautuminen variantin mukaan |
Esimerkiksi seuraavat ohjelmat voitaisiin nyt kirjoittaa tällä kielellä:
let x be (42,True) in fst x
.. => 42
let x be left 5 in case x {left n -> "joku numero"; right s -> "merkkijono " ++ s}
.. => "joku numero"
Tässä vaiheessa on tosin vielä hieman hankala keksiä hauskoja ohjelmia..
Lisää ylläolevat rakenteet AST:hesi ja täydennä tyypintarkastimesi toimimaan niille. Dokumentoi millaiset tyypityssäännöt valitsit.
2pt jos teet vain parit ja 3pt jos teet myös variantit
Tehtävä 2 -- Muuttuvaiset ja komennot
Abstrakti muoto | Syntaksi | Selite | |
---|---|---|---|
Typ τ ::= | \(\text{cmd}(\tau)\) | cmd \(\tau\) | Komento |
Cmd m ::= | \(\text{pure}(e)\) | pure(\(e\)) | Komento joka laskee lausekkeen |
\(\text{bnd}(e;x.m)\) | \(x\) <- \(e\) ; \(m\) | Ketjutus | |
\(\text{dcl}(e;a.m)\) | new \(a\) = \(e\) ; \(m\) | Muuttuvaisen luominen | |
\(\text{get}[a]\) | \(@a\) | Muuttuvaisen lukeminen | |
\(\text{set}[a](e)\) | a := e | Muuttuvaiseen kirjoittaminen | |
\(\text{read}\) | read | Käyttäjän syötteen lukeminen | |
\(\text{print}(e)\) | print \(e\) | Tulostaminen konsoliin | |
Exp e ::= | \(\text{cmd}(m)\) | do \(m\) | Komento Expiksi |
Top T ::= | \(\text{toplevel}[x](m)\) | program \(x\) is \(m\) | Toplevel tjsp. "pääohjelma" |
Nyt ohjelmointikieli venyisi jopa seuraavankaltaisiin ohjelmiin, vaikka syntaksi onkin hieman kömpelöä
program Testi is
new laskuri = 0;
i <- read;
s <- @laskuri;
laskuri := s+i;
i2 <- read;
s2 <- @laskuri;
laskuri := s2+i2;
i3 <- read;
s3 <- @laskuri;
laskuri := s2+i3;
tulos <- @laskuri;
print tulos;
pure 0;
.. Käyttäjä syöttää "42" "41" "1"
.. Ohjelma tulostaa "84"
.. Ohjelma päättyy paluuarvolla 0
Laajenna AST:si kattamaan myös nämä lisäykset. Päätä soveltuvat tyypityssäännöt ja toteuta tyypintarkastaja.
2 pt
Ennen aloittamista mieti, mitä do m tekee? Mihin sitä tarvitaan? Mieti yksi esimerkki ennenkuin aloitat tehtävän. (Vinkki. yritä käyttää alkuperäisen kielen rakenteita komentojen kanssa.)
Tehtävä 3 -- Aliohjelmat
Lisätään kieleen vielä hieman "lambdamaiset" aliohjelmat:
Abstrakti muoto | Syntaksi | Selite | |
---|---|---|---|
Typ \(\tau\) ::= | \(\text{proc}[\tau]\) | proc \(\tau\) | Aliohjelma |
Cmd m ::= | \(\text{call}(e_1;e_2)\) | call \(e_1\) with \(e_2\) | Aliohjelman kutsuminen |
Exp e ::= | \(\text{proc}[x;\tau](x.m)\) | proc (x : \(\tau\)) {\(m\)} | Aliohjelman määritys |
Nyt ohjelmointikieli venyisi jopa seuraavankaltaisiin ohjelmiin, vaikka syntaksi onkin hieman kömpelöä
program Tuplaus is
new tulos = 0;
new kysy' = proc(x : (String,String)) {
_ <- print (fst x);
_ <- print " >>> ";
syöte <- read;
vanha <- @tulos;
tulos := syöte+vanha;
() <- print (snd x);
pure 0};
kysy <- @kysy'
_ <- call kysy with ("Anna 1 luku","Kiitos");
_ <- call kysy with ("Anna 2 luku","Kiitos");
_ <- call kysy with ("Anna 3 luku","Kiitos");
arvo <- @tulos;
() <- print arvo;
pure 0;
.. Ohjelma tulostaa "Anna 1 luku >>> "
.. Käyttäjä syöttää "42"
.. Ohjelma tulostaa "Kiitos"
.. Ohjelma tulostaa "Anna 2 luku >>> "
.. Käyttäjä syöttää "41"
.. Ohjelma tulostaa "Kiitos"
.. Ohjelma tulostaa "Anna 3 luku >>> "
.. Käyttäjä syöttää "1"
.. Ohjelma tulostaa "Kiitos"
.. Ohjelma tulostaa "84"
.. Ohjelma päättyy paluuarvolla 0
Laajenna AST:si kattamaan myös nämä lisäykset. Päätä soveltuvat tyypityssäännöt ja toteuta tyypintarkastaja.
2pt
Tehtävä 4 -- Olennaisia lisäyksiä (Bonus)
Lisää AST:hesi seuraavat ominaisuudet, päätä soveltuva tyypitys ja laajenna tyypintarkastintasi kattamaan nämä tapaukset. Tee myös esimerkkiohjelmat jokaiselle.
- 1pt. Sopiva toistorakenne
- 1pt. Paluuarvolliset aliohjelmat
- 1pt. Taulukot, indeksointi, alustus ja sijoitus
Bonuspiste jos täydennät syntaksitaulukot vastaamaan toteutustasi.
Yhteensä 0-3pt.
These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.