1. kodused ülesanded

Üldinfo

Lahenduste esitamise tähtaeg on 14. 03, kell 11.59. Lahendused saata mailiga varmo@cs.ut.ee; subjektiks peab olema pk-kodu-1. Iga ülesande eest on võimalik saada kuni 10 punkti (seega kokku kuni 60 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 15. 03 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, mille nimeks on pk-kodu-1.s. Faili algusse lisada kommentaaridena kõigi rühmaliikmete nimed (rühmas võib olla max. 5 liiget) ja maili-aadressid. Kõigi ülesannete korral peavad protseduuride nimed ja argumentide arv/järjekord vastama täpselt ülesandes esitatule. Lahendused peavad olema loetavad ja piisavalt kommenteeritud (sh. kui kasutate abiprotseduure, siis see mida nad teevad peab olema selgelt välja toodud). Lisaks tuleb iga lahenduse lõppu lisada vähemalt 5 testi (selle protseduuri väljakutset) koos kommentaarina esitatud tulemusega. Näiteks:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; pk-kodu-1.s
;;; Programmeerimiskeeled - 1. koduülesannete lahendused
;;;
;;; Autorid:
;;;          Jaan    Tatikas   (tatikas@ut.ee)
;;;          Salomon Vesipruul (salomon@ut.ee)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; 1. ülesanne - ribassoc

(define ribassoc
   (lambda ...
     ... ))

;; Tests:

(ribassoc 'b '(a b c) '#(1 2 3) 'fail)
; ==> 2

(ribassoc 'c '(a b foo) '#(3 squiggle bar) 'fail)
; ==> fail

Ülesanded

[EOPL 2.2.7.5] Defineeri protseduur (ribassoc s los v fail-value), mis saab argumentideks sümboli s, sümbolite listi los, vektori v ja mingi väärtuse fail-value ning väljastab vektori v nii mitmenda elemendi, kui mitmes on sümbol s listis los. Kui s esineb listis mitu korda, siis väljastada tema esimesele esinemisele vastav element. Kui sümbolit s listis ei esine, siis väljastada väärtus fail-value. Lahenduses võid eeldada, et argumendid on õiget tüüpi ja et sümbolite list los ning vektori v on sama pikad.
```
> (ribassoc 'b '(a b c) '#(1 2 3) 'fail)
2
> (ribassoc 'c '(a b foo) '#(3 squiggle bar) 'fail)
fail
> (ribassoc 'i '(a i o i) '#(fx (fz) () (fm fe)) 'fail)
(fz)
	
```
[EOPL 2.2.9.4] Defineeri protseduur (compose p1 ... pn), mis saab argumentideks suvalise arvu üheargumendilisi protseduure ning väljastab nende kompositsiooni. Kui argumendina saadavaid protseduure on null, siis on tulemuseks identsusprotseduur; ühe protseduuri korral on tulemus see protseduur ise; kahe ja enama protseduuri korral on nende kompositsioon spetsifitseeritud järgenvalt:
```
          ((compose p1 p2 ...) x)  ==>  (p1 ((compose p2 ...) x))

> ((compose) '(a b c d))
(a b c d)
> ((compose car) '(a b c d))
a
> ((compose car cdr cdr) '(a b c d))
c
	
```
[EOPL 2.3.1] Kirjuta protseduurid free-vars ja bound-vars, mis saavad argumendiks lambda-avaldist esitava listi ning väljastavad vastavalt kõigi vabade/seotud muutujate listi (ilma kordusteta).
```
> (free-vars '(lambda (x) x))
()
> (free-vars '((lambda (x) y) x))
(x y)
> (bound-vars '(lambda (f) (lambda (x) (f x))))
(f x)
	
```
[EOPL 2.3.10] Vaatleme alljärgneva süntaksiga avaldisi (NB! lambda-abstraktsioonis võib olla null parameetrit!):
```
    <expr>  ::=  <variable>
              |  (if <expr> <expr> <expr>)
              |  (lambda (<{variable>}*) <expr>)
              |  ({<expr>}+)
	
```
Kirjuta protseduur lexical-address, mis saab argumendiks ülaltoodud süntaksiga avaldise ja väljastab avaldise, kus iga muutuja v on asendatud tema leksilise aadressiga kujul (v : d p). Kui tegemist on vaba muutujaga (allpool toodud näites muutujad eq? ja cons), siis käsitleda neid nagu oleks kogu avaldis ümbritsetud ühe suure lambdaga, mis seob kõiki vabu muutujaid. Näiteks allpool toodud näite korral (lambda (eq? cons) (lambda (a b c) ...)).
```
> (lexical-address '(lambda (a b c)
                      (if (eq? b c)
                          ((lambda (c)
                              (cons a c))
                           a)
                          b)))
(lambda (a b c)
  (if ((eq? : 1 0) (b : 0 1) (c : 0 2))
      ((lambda (c)
          ((cons : 2 1) (a : 1 0) (c : 0 0)))
       (a : 0 0))
      (b : 0 1))))
	
```
[EOPL 2.3.13] Kirjuta protseduur un-lexical-address, mis saab argumendiks leksiliste aadressitega märgendatud avaldise (kus muutujate nimed on antud parameetrite listis) ning väljastab ekvivalentse avaldise, kus aadressid on asendatud neile vastavate muutujatega. Kui ekvivalentset avaldist ei leidu, siis väljastada #f.
```
> (un-lexical-address '(lambda (a)
                         (lambda (b c)
                            ((: 1 0) (: 0 0) (: 0 1)))))
(lambda (a) (lambda (b c) (a b c)))
> (un-lexical-address '(lambda (a) (lambda (a) (: 1 0))))
#f
	
```
[EOPL 2.3.14] Kirjuta protseduur rename, mis saab argumentideks lambda-avaldise exp ja kaks muutujat var1, var2 ning väljastab exp[var1/var2], kui var1 ei esine vabalt avaldises exp. Kui var1 esineb vabalt avaldises exp, siis väljastada #f.
```
> (rename '(lambda (b) (b a)) 'c 'a)
(lambda (b) (b c))
> (rename '((lambda (x) x) x) 'y 'x)
((lambda (x) x) y)
>(rename '(a b) 'a 'b)
#f
	
```

Varmo Vene