pp-cb

• Scheme este un limbaj de programare functional, derivat din Lisp si bazat pe modelul formal al calcului lambda.
• Scheme este un limbaj de program de uz general,de nivel inalt cu suport pentru operatii cu numere, caractere, stringuri, liste, vectori.

• Elementul de baza pentru constructia de programe Scheme este lista. Un program este o succesiune de liste. In Scheme, listele sunt incadrate de '(). Simbolul ' interpreteaza o lista ca o structura de date. Absenta acestuia, interpreteaza lista ca un program.
• Exemple de liste:
  • '(a b c)
  • '(1 2 3)
  • '(1 a 3.14)
  • '(+ 1 2)
  • '(1 (+ 3 4) 2)

• Exemple de programe:
  • (+ 1 3) (= 4)
  • (+ 1 (- 1 2)) (= 0)

• 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)

• 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).
• Setarea/schimbarea valorii unei variabile este o lista de forma:
  • (set! <var_name> <expr>) unde <var_name> si <expr> au aceleasi semnificatie ca in cazul definirii unei variabile
• Exercitiu: Scrieti un program in Scheme care verifica existenta efectelor laterale.

• 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.

• 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))
    • Exercitiu: definiti comportamentul functiilor de mai sus(+ bonus: cadr, cdar)
  • 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?

• 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).

• Definiti o functie care determina factorialul unui numar
• Verificati daca o lista e palindrom

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)) ).

• 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)

DrRacket - Download