pp-cb

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Laborator 9 - Întârzierea evaluării =====


=====Moduri de evaluare a unei expresii: =====
    * **evaluare aplicativa** - argumentele funcțiilor sunt evaluate înaintea aplicării funcției asupra lor.
    * **evaluare lenesa** - întârzie evaluarea parametrilor până în momentul când aceasta este folosită efectiv.
    * **promisiuni**

====Evaluare aplicativă vs. evaluare leneșă====

Fie urmatoarea expresie, scrisă într-o varianta relaxata a Calculului Lambda (in care valori numerice si operatii pe acestea sunt permise, iar functiile sunt in forma uncurry):

<code>(λx.λy.(x + y) 1 2)</code>

Evident, in urma aplicării funcției de mai sus, expresia se va evalua la 3.
Sa observam, insa, cazul in care parametrii functiei reprezinta aplicatii de functii:
 
<code>(λx.λy.(x + y) 1 (λz.(z + 2) 3))</code>

Desigur, evaluarea expresiei ''(λz.(z + 2) 3)'' va genera valoarea ''5'', de unde deducem ca rezultatul final al expresiei va fi ''6'' ( adunarea lui 1 cu rezultatul anterior ). În cadrul acestui raționament, am presupus că parametrii sunt evaluați înaintea aplicării funcției asupra acestora. Vom vedea, în cele ce urmează, că evaluarea se poate realiza și in alt mod.

====Evaluare aplicativă====

Evaluarea aplicativă (eager evaluation) este cea în care fiecare expresie este evaluată imediat. În exemplul de mai sus, evaluarea aplicativă va decurge astfel:

<code>(λx.λy.(x + y) 1 (λz.(z + 2) 3))
(λx.λy.(x + y) 1 5)
6</code>


====Evaluare normală====

Spre deosebire de evaluarea aplicativă, evaluarea normală va întarzia evaluarea unei expresii, până când aceasta este folosită efectiv. Exemplu:

<code>(λx.λy.(x + y) 1 (λz.(z + 2) 3))
(1 + (λz.(z + 2) 3))
(1 + 5)
6</code>

====Evaluarea in Racket====

Evaluarea in Racket este by default **aplicativă**.
Codul ''(+ 1 (+ 2 3))'' pentru a se evalua si a intoarce 6, urmează etapele:
  * ''(+ 2 3)'' se evaluează intai, al doilea parmetru al funcției ''+'' si produce 5
  * ''(+ 1 5)'' se evaluează si produce 6

Totuși, putem intarzia evaluarea expresiilor prin inchideri nulare

<code>(define suma
  (lambda (a b)
    (+ a b)))

(define suma_intarziata
  (lambda (a b)
    (lambda () (+ a b)
    )))</code>

  * ''(suma_intarziata 2 3)'' intoarce un ''#procedure'' (functie) care isi salveaza contextul ( inchidere functionala )
  * ''(''''(suma_intarziata 2 3)'''')'' intoarce rezultatul


====Aplicatii:====

=== Siruri in Scheme ===

  - Definiți un stream de numere 1 'ones_stream' folosind evaluarea lenesa din scheme care apeland
      * ''(ones_stream)'' => ''(1 . #procedure)'' unde dacă vom apela ''(#procedure)'', vom obtine:
      * ''(1 . #procedure)'' din nou.


  - Creati o funcție take care să funcționeze ca cea din Haskell (take 5 [1,1..] va intoarce [1,1,1,1,1] in haskell)
      * ''(take 5 ones_stream)'' => ''(1 1 1 1 1)''


  - Creati un stream de numere naturale care va fi reprezentat astfel:
      * ''(0 . #procedure)'', unde dacă vom apela procedure vom obtine
      * ''(1 . #procedure)'', unde dacă iar apelam procedure-ul nou obtinut, obtinem
      * ''(2 . #procedure)'' etc.
      * HINT: veți avea nevoie de o funcție ajutătoare
      * Testați: ''(take 5 naturals_stream)'' => ''(0 1 2 3 4)''

  - Definiți o funcție care sa adune două stream-uri:
      * ''(take 5 (sum_stream naturals_stream ones_stream))'' => ''(1 2 3 4 5)''
      * pentru acest task, implementati o functie ''zipWith'' care sa opereze pe stream-uri


  - Creați un stream de numere pare:
      * Testati: ''(take 5 even_stream)'' => ''(0 2 4 6 8)''
      * pentru acest task, implementati o functie ''map'' care sa opereze pe stream-uri


6. Creați șirul numerelor Fibonacci:
      * ''(take 5 fibo_stream)'' => ''(0 1 1 2 3)''
      * Observam ca fibonacci e definit prin adunarea stream-urilor anterioare.
              <code>
              Fibo        = t0 t1 t2 t3 ... t(k-2) ... +
              (tail Fibo) = t1 t2 t3 t4 ... t(k-1) ...
              ___________________________________________
              Fibo  = t0 t1 t2 t3 t4 t5 ... tk ...  </code>
      * Observam că, adunand elemente din sirurile (fluxurile) Fibo și (tail Fibo), obtinem sirul t2 t3 t4 .. tk . Dacă adăugam primele două elemente, t0 si t1 la inceput, obținem exact Fibo.

=== Siruri in Haskell ===
  - Construiti sirul numerelor naturale
  - Construiti sirul numerelor pare 
  - Construiti sirul numerelor lui Fibonacci 

=== Aproximatii (in Haskell) ===
  - definiti o functie ''build :: (a -> a) -> a -> [a]'' care primeste o functie 'generator' (pe care o numim ''g'' in continuare), o valoare initiala (''a0''), si generaza lista: ''[a0, g a0, g (g a0), g (g (g a0)), ... ''
  - definiti o functie ''select'' care primeste o toleranta ''e'', o lista, si intoarce valoarea ''an'' care satisface proprietatea: ''|an - a{n+1}| < e''
  - Aproximatie pentru ''sqrt(k)'':
      * Scrieti o functie care calculeaza ''sqrt(k)'' cu toleranta ''0.01'', exploatand faptul ca sirul: ''an = 1/2(a{n-1} + k/a{n-1})'' converge catre ''sqrt(k)'' cand ''n'' tine de la infinit.
  - Aproximatie pentru derivata unei functii ''f'' intr-un punct ''a''
      * Scrieti o functie care genereaza lista: ''[h0, h0/2, h0/4, h0/8, ...]''
      * Scrieti o functie care calculeaza lista aproximarilor lui ''f'(a)'', calculate astfel: ''f'(a)=f(a+h)-f(a)/h''
      * Scrieti o functie care calculeaza derivata in ''a'' a unei functii ''f'', cu toleranta ''0.01''
pp-cb

User Tools

Site Tools

Page Tools
