laboratoare:07-introducere-in-scheme
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
laboratoare:07-introducere-in-scheme [2015/04/06 15:47] matei.popovici |
laboratoare:07-introducere-in-scheme [2016/04/18 23:56] (current) mihai_dan.masala |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ===== Laborator 7 - Introducere in Scheme ===== | ===== Laborator 7 - Introducere in Scheme ===== | ||
| + | ==== Despre Scheme ===== | ||
| + | * 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. | ||
| ==== Primitivele limbajului ==== | ==== Primitivele limbajului ==== | ||
| === Structura unui program === | === Structura unui program === | ||
| - | * Elementul de baza pentru constructia de programe Scheme este **lista**. Un program este o **succesiune de liste**. Exemple: | + | * 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. |
| - | * '''(1 2 3)'' | + | * Exemple de liste: |
| - | * '''(1 (2 3) 4)'' | + | * '''(a b c)'' |
| - | * '''(1 (+ 2 4) 5)'' | + | * '''(1 2 3)'' |
| - | * '''(+ 1 3)'' | + | * '''(1 a 3.14)'' |
| - | * Simbolul ''''' interpreteaza o lista ca **o structura de date**. Absenta acestuia, interpreteaza lista ca un program. Acest lucru se poate observa din exemplele anterioare. | + | * '''(+ 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: | * 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)'' | * ''`(1 ,(+ 2 3) 4)'' | ||
| Line 15: | Line 25: | ||
| * Definitia unei variabile este o lista de forma: | * 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). | * ''(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. | * **Exercitiu**: Scrieti un program in Scheme care verifica existenta efectelor laterale. | ||
| Line 38: | Line 50: | ||
| === Alte elemente === | === Alte elemente === | ||
| - | * conditionala (if) este o lista de forma: | + | * **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. | * ''(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 ==== | ==== 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)'' | ||
| + | |||
| + | ==== Download ==== | ||
| + | [[http://download.racket-lang.org/| DrRacket - Download]] | ||
laboratoare/07-introducere-in-scheme.1428324459.txt.gz · Last modified: 2015/04/06 15:47 by matei.popovici
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
