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 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
  * Verificati daca o lista e palindrom

=== 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)''
  * Transformati o lista de elemente consecutive identice, in liste de liste, fiecare continand exact elementele identice.
      * Exemplu: '''(1 1 1 1 1 2 2 2 3 4 5)'' => '''('' ''(1 1 1 1 1) (2 2 2) (3) (4) (5)'' '')''.
  * Pentru o lista ce poate contine doar elemente consecutive identice, construiti o lista de ''<element,nr_aparitii>''. 
      * Exemplu: '''(1 1 1 1 1 2 2 2 3 4 5)'' => '''('' ''(1 4) (2 3) (3 1) (4 1) (5 1)'' '')''.
  * Pentru o lista arbitrara, construiti o lista de elemente: ''<element,nr_aparitii>''.
      * Exemplu: '''(1 2 3 1 4 2 2 5)'' => '''('' ''(1 2) (2 3) (3 1) (4 1) (5 1))'' '')''.

=== Yawn ===
  * Implementati rotatia cu ''n'' pozitii la stanga/dreapta a unei liste:
      * Exemplu: o rotatie de ''3'' pozitii la stanga pentru '''(1 2 3 4 5 6 7)'' produce '''(4 5 6 7 1 2 3)''
pp-cb

User Tools

Site Tools

Page Tools
