3. kodused ülesanded

Üldinfo

Lahenduste esitamise tähtaeg on 11. 06, kell 11.59. Lahendused saata mailiga varmo@cs.ut.ee; subjektiks peab olema pk-kodu-3. Kokku on ülesannete eest võimalik saada kuni 70 punkti. Hilinenud lahenduste korral väheneb punkti summa 10% iga hilinenud päeva kohta. Näiteks, kui lahendus on väärt 50 punkti, aga jõuab minuni 13. 06 kell 12.00 (so. kaks päeva hiljem), siis on tegelik punktisumma 50 * 0.9^2 = 41.

Vormistamisest

Kõigi ülesannete lahendused vormistada ühe Scheme failina, millede nimi on pk-kodu-3.s. Faili algusse lisada kommentaaridena kõigi rühmaliikmete nimed (rühmas võib olla max. 5 liiget) ja maili-aadressid. Lahendustes ümbritseda see koodi osa, mida modifitseerisite/lisasite selgesti eristatavate kommentaaridega.

Ülesanded


  1. [EOPL 13.1.5] (30p) Aluseks kasutada loengus esitatud tüübikontrollijaga interpretaatorit loeng23.ss.

    Laiendame keelt erivormidega:

       <form> ::= define <var> = <exp>        define (var exp)
                | definerec <decls> end       definerec (decls)
                | <exp>
    

    Nagu eelmise kodutöö esimeses ülesandes, saab erivormi define kasutada globaalsete mitte-rekursiivsete nimede defineerimiseks. Erinevuseks on see, et defineeriv avaldis peab olema assert-avaldis ning enne kui uus nimi lisatakse globaalsesse keskonda kontrollitakse tema definitsiooni tüübikorrektsust. Erivormi definerec on analoogne letrec-avaldisega millel puudub keha ning võimaldab korraga defineerida mitut (vastastikku) rekursiivset protseduuri.

    Modifitseeri 'read-eval-print' tsüklit selliselt, et ta loeb sisse erivormi; kui tegemist on avaldisega, siis ta kõigepealt kontrollib selle tüübikorrektsust ja seejärel väljastab tema väärtuse koos tüübiga (so.\ käitub nii nagu loengus esitatud interpretaator); kui tegemist on kas define või definerec erivormiga, siis ta kontrollib definitsioonide tüübikorrektsust ja kui kõik oli korras, siis lisab vastavad seosed globaalsesse keskonda ning trükib defineeritava nime koos tüübiga (definerec korral, kõik nimed koos tüüpidega) välja.

    --> "define add1 = assert (-> (int) int) :
                                     proc (x) +(x,1)"
    add1 :: (-> (int) int)
    --> "add1(3)"
    4 : int
    

  2. [EOPL 13.1.6] (20p) Lisada eelmises ülesandes realiseeritud interpretaatorile erivorm tüübilühendite (ehk tüübisünonüümide) defineerimiseks:

       <form> ::= definetypeabbrevation <type-name> <type>        definetypeabbreviation (name type)
    

    Selleks tuleb interpretaatorile (täpsemalt tüübikontrollijale) lisada uus globaalne keskond, mis seob tüübinimesid tüüpidega. Kui erivorm väärtustatakse, siis lisatakse uus tüübinimi koos tema definitsiooniga sinna keskonda. Seda nime saab edaspidi kasutada tüübiavaldistes vastava tüübi lühendina. Tüüpide kontrollimisel on tüübinimi täiesti ekvivalentne teda defineeriva tüübiga. Näiteks:

    --> "definetypeabbreviation intproc (-> (int) int)"
    --> "define compose = assert (-> (intproc, intproc) intproc) :
                           proc (f, g) assert intproc : proc (x) f(g(x))"
    compose :: (-> (intproc, intproc) intproc)
    --> "define mul2 = assert intproc : proc (x) *(x,2)"
    mul2 :: intproc
    --> "define f = assert (-> (int) int) : compose(add1,mul2)"
    f :: (-> (int) int)
    

    Tüübinime tohib kasutada alles pärast tema defineerimist (sh. on keelatud tüübinimede rekursiivne defineerimine).

    Tüübiavaldises on tüübinimede esitatud järgmiselt defineeritud kirjete abil:

    (define-record namedtype (name))
    

  3. (20p) Lisada eelmises ülesandes realiseeritud interpretaatorile erivorm abstraktsete tüüpide defineerimiseks:

       <form> ::= definetype <type-name> = <type>          definetype (name rep-type decls)
                      within <decls> end
    

    Erivormi definetype väärtustamisel seotakse tüübinimi teda defineeriva tüübiga ning seejärel töödeldakse protseduuride deklaratsioonid (deklaratsioonid võtmesõnade within ja end vahel) analoogselt erivormiga definerec. Seejuures, protseduuride tüüpide kontrollimisel kasutatakse defineeritud tüübinime tüübisünonüümina (so. analoogselt eelmise ülesandega). Pärast erivormi väärtustamist on tüübinimi kasutatav ainult abstraktselt; tüübikontrollija seisukohalt vastab siis sellele tüübinimele sama nimega ning ilma argumentideta tüübikonstruktor (analoogselt tüüpidega int ja bool). Näiteks:

    --> "definetype myint = int
           within fromint = assert (-> (int) myint) : proc(x) x;
                  toint   = assert (-> (myint) int) : proc(x) x;
                  mymult  = assert (-> (myint, myint) myint) :
                                              proc (x, y) *(x,y)
           end"
    fromint :: (-> (int) myint)
    toint :: (-> (myint) int)
    mymult :: (-> (myint myint) myint)
    --> "mymult(fromint(2), fromint(3))"
    6 : myint
    --> "mymult(2, 3)"
    Type error: Domain does not match formals
    

Varmo Vene