pp-cb

This is an old revision of the document!

---

===== Laborator 7 - Introducere in Scheme ===== ==== Primitivele limbajului ==== === Structura unui program === * Elementul de baza pentru constructia de programe Scheme este **lista**. Un program este o **succesiune de liste**. Exemple: * '''(1 2 3)'' * '''(1 (2 3) 4)'' * '''(1 (+ 2 4) 5)'' * '''(+ 1 3)'' * Simbolul ''''' interpreteaza o lista ca **o structura de date**. Absenta acestuia, interpreteaza lista ca un program. Acest lucru se poate observa din exemplele anterioare. * Simbolii ''`'' (quasiquote) si '','' (comma), se pot folosi in tandem pentru a crea combinatii de liste-program cu liste-structuri de date, ca in exemplul urmator: * ''`(1 ,(+ 2 3) 4)'' === Variabile === * Definitia unei variabile este o lista de forma: * ''(define <var_name> <expr>)'' unde ''<var_name>'' si ''<expr>'' desemneaza un nume de variabila, respectiv expresie. De remarcat este ca ''<expr>'' este fie o variabila primitiva, fie o lista (date/program). * **Exercitiu**: Scrieti un program in Scheme care verifica existenta efectelor laterale. === Functii si apeluri de functii === * O **functie anonima** este o lista de forma: * ''(lambda <p-list> <expr>)'' unde ''<p-list>'' este o lista de parametri formali ai functiei, iar ''<expr>'' este corpul functiei. * Exemplu: ''(lambda (x y) (+ x y))'' * Definitia unei functii se poate face: * definind o variabla care sa o desemneze: * Exemplu: ''(define f (lambda (x y) (+ x y)))'' * folosind o varianta prescurtata ''(define <f-list> <expr>)'', unde ''<f-list>'' desemneaza o lista al carui prim element este numele functiei, iar elementele urmatoare sunt parametrii functiei si ''<expr>'' desemneaza corpul functiei: * Exemplu: ''(define (f x y) (+ x y))'' * **Apelul** unei functii este o **lista** in care primul element este numele functiei, iar urmatorii sunt parametrii acesteia. * Exemplu: ''(f 1 2)'' * O functie ''f'' ce primeste ''n'' parametrii este in forma: * **curry**: daca este de forma: ''(lambda (x1) (lambda (x2) (... (lambda(xn) <expr>)...)'' * **uncurry**: daca este de forma: ''(lambda (x1 x2 ... xn) <expr>)'' * **Exercitii**: * Definiti si apelati adunarea in forma //curry//. * Implementati o functie care primeste un operator binar in forma //curry//, si intoarce operatorul in forma //uncurry//. * Implementati o functie care primeste un operator binar in forma //uncurry// si intoarce acelasi operator in forma //curry//. === Alte elemente === * **liste**: * constructie (exemplu): ''(cons 1 '(2 3))'' * explorare (exemple): ''(car '(1 2 3))'', ''(cdr '(1 2 3))'', ''(caar '(1 2 3))'', ''(cddr '(1 2 3))'' * lista vida (exemple): ''(empty? '(1 2 3))'' si ''(empty? '())'' * egalitate: ''(eq? 1 2)'' * **conditionala** (if) este o lista de forma: * ''(if <bool-expr> <expr1> <expr2>)'' unde ''<bool-expr>'' este un sub-program care se evalueaza la o valoare booleana (''#t'' (true), ''#f'' (false)), iar ''<expr1>'', ''<expr2>'' sunt expresii. * String-urile sunt definite exact ca in Haskell, insa ele nu mai reprezinta liste de caractere, ci sunt tipuri primitive. * **Functiile de ordin superior**: ''map'', ''filter'', ''foldl'', ''foldr'' sunt disponibile si functioneaza (aproape) la fel ca in Haskell. * Realizati urmatoarele apeluri in Scheme: * ''(foldl cons '() '(1 2 3))'' * ''(foldr cons '() '(1 2 3))'' * Exista diferente intre Scheme si Haskell privind implementarea acestor functii? ==== Exercitii ==== === Particularitati ale limbajului === * Scrieti un program in Scheme care atesta faptul ca **tiparea este dinamica** (limbajul este slab-tipat (weakly-typed). * Scrieti un program in Scheme care atesta faptul ca **tiparea se face la runtime** (spre deosebire de Haskell, unde tiparea se face la compilare). === Warm-up === * Definiti o functie care determina factorialul unui numar === Prelucrari de liste === Rezolvati urmatoarele exercitii (folosind, pe cat posibil, functii de ordin superior): * Transformati o lista imbricata intr-o lista simpla. * Exemplu: '''(1 (2 3 (4 5) 6) 7 (8 9))'' => '''(1 2 3 4 5 6 7 8 9)'' * Verificati daca o lista e palindrom *