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.