Harjoitukset 7 - 16.5.2016
Näistä demoista voi saada 0-6 pistettä ja 3 bonuspistettä, joilla voi korvata aiemmista demoista saamatta jääneitä pisteitä.
Oppimistavoitteet
- Osaat kääntää lausekkeita ja lauseita välikielelle
- Osaat kääntää yksinkertaisia tietorakenteita välikielle
- (Osaat toteuttaa yksinkertaiselle kielelle Hindley-Milner tyylisen tyypinpäättelyn)
Tehtävä 1
Käännä seuraava ohjelmointikieli valitsemallesi välikielelle. Hyviä vaihtoehtoja on luennoilla käytetty välikieli ja LLVM
| Abstrakti muoto | Syntaksi | Selite | |
|---|---|---|---|
| Typ τ ::= | \(\text{num}\) | Number | Numerotyyppi |
| \(\text{str}\) | String | Merkkijonotyyppi | |
| \(\text{bool}\) | Bool | Merkkijonotyyppi | |
| Exp e ::= | \(x\) | x y tai z | 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 |
Huomaa, että voit olettaa tyyppitarkastuksen tehdyksi ja AST:n olevan korrektia
2pt
Tehtävä 2
Tee kieleen seuraavat laajennokset ja käännä ne välikielellesi.
| 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 |
Huomaa, että voit olettaa tyyppitarkastuksen tehdyksi ja AST:n olevan korrektia
2pt
Tehtävä 3
Tee kieleen seuraavat laajennokset ja käännä ne välikielellesi.
| Abstrakti muoto | Syntaksi | Selite | |
|---|---|---|---|
| Typ τ ::= | \(\text{cmd}(\tau)\) | cmd \(\tau\) | Komento |
| \(\text{ref}(\tau)\) | ref \(\tau\) | Muuttuvainen | |
| 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" |
Huomaa, että voit olettaa tyyppitarkastuksen tehdyksi ja AST:n olevan korrektia
2pt
-
Tehtävä 4-6
Lisätään yo. kieleen polymorfiset tyypit ja tyyppimuuttujat:
| Abstrakti muoto | Syntaksi | Selite | |
|---|---|---|---|
| Typ τ ::= | \(\alpha\) | \(\alpha\dots\omega\) | Tyyppimuuttuja |
| Poly σ ::= | \(\forall\alpha . \tau\) | forall \(\alpha\) . \(\tau\) | Polytyyppi |
| \(\tau\) | \(\tau\) | Polytyyppi voi olla myös monotyyppi |
Toteuta tehtävän 1 kielelle Hindley-Damas-Milner tyypinpäättely (3pt). Laajenna kieltä tehtävian 2 ja 3 mukaisesti ja toteuta tyypinpäättely molemmille (2pt/laajennos)
These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.