51
CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Embed Size (px)

Citation preview

Page 1: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Le langage Scheme (2)

Un langage de programmation fonctionnelle

Page 2: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

• read – retourne une entrée du clavier

> (read)234 ; entrée de l’utilisateur234 ; valeur retournee par la fonction> (read)"hello world""hello world"

• display – affiche son parametre sur ecran

> (display "hello world")hello world> (display (+ 2 3))5

• newline – affiche une nouvelle ligne

Entrees / Sorties

Page 3: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

• Definir une fonction qui lit un nombre (si ce n’est pas un nombre, elle continue de demander un nombre):> (define (ask-number)

(display "Entrez un nombre: ") (let ((n (read)))

(if (number? n) n

(ask-number))))

> (ask-number)Entrez un nombre: aEntrez un nombre: (5 6)Entrez un nombre: “mais pourquoi ?"Entrez un nombre: 1212

Entrees / Sorties

Page 4: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

• Une fonction qui lit un entier, fait appel a fact(ortielle) et affiche le resultat:

(define (fact-interactive)(display "Entrez un entier: ")(let ((n (read))) (display “La factorielle de ") (display n) (display " est ") (display (fact n)) (newline)))

> (fact-interactive)Entrez un entier: 4La factorielle de 4 est 24

Entrees / Sorties

Page 5: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Port d’entrée

CSI2520

(let ((p (open-input-file "myfile.ss")))  (let f ((x (read p)))    (if (eof-object? x)        (begin          (close-input-port p)          '())        (cons x (f (read p))))))

Page 6: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Appel avec un port d’entrée

CSI2520

(call-with-input-file "myfile.ss"  (lambda (p)    (let f ((x (read p)))      (if (eof-object? x)          '()          (cons x (f (read p)))))))

Page 7: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Définition équivalente

CSI2520

(define call-with-input-file  (lambda (filename proc)    (let ((p (open-input-file filename)))      (let ((v (proc p)))        (close-input-port p)        v))))

Page 8: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Imprimer une liste

CSI2520

(let ((p (open-output-file "myfile.ss")))  (let f ((ls list-to-be-printed))    (if (not (null? ls))        (begin          (write (car ls) p)          (newline p)          (f (cdr ls)))))  (close-output-port p))

Page 9: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Ou encore

CSI2520

(call-with-output-file "myfile.ss"  (lambda (p)    (let f ((ls list-to-be-printed))      (if (not (null? ls))          (begin            (write (car ls) p)            (newline p)            (f (cdr ls)))))))

Page 10: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Définition équivalente

CSI2520

(define call-with-output-file  (lambda (filename proc)    (let ((p (open-output-file filename)))      (let ((v (proc p)))        (close-output-port p)        v))))

Page 11: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Attribuer des valeurs à des variables avec set!

• Cette fonction permet d’attribuer une valeur à une variable

(set! nombre (+ 3 4))(set! nombre (+ 1 nombre))

En SCHEME, les fonctions dont le nom se termine par ! sont des fonctions quimodifient la valeur de l'un des arguments (opérations destructives).

Page 12: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Exemple

(define light-switch (let ((lit #f)) (lambda () (set! lit (not lit)) (if lit 'on 'off))))

Encapsulation de la variable lit dans la définition de light-switch

Page 13: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Exemple impératif

CSI2520

(define secondesImp (lambda (h m s) (let ((sh 0) (sm 0) (total 0)) (set! sh (* 60 (* 60 h))) (set! sm (* 60 m)) (set! total (+ s (+ sh sm))) total)))

Page 14: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Exemple plus fonctionnel

CSI2520

(define secondes (lambda (h m s) (let ((sh (* 60 (* 60 h))) (sm (* 60 m)) ((+ s (+ sh sm))))))

Page 15: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

(define PILE ‘())

(define (vide?)

(null? PILE)) 

(define depiler

(lambda ()

(let (( res (car PILE)))

(set! PILE (cdr PILE))

res )))

(define empiler

(lambda (element)

(set! PILE (cons element PILE))))

(define (top)

(vide? `())

(else (car PILE)))

Pile en Schemeversion impérative

Page 16: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

• Les vecteurs en Scheme sont des structures hétérogènes qui permettent d’accéder aux différents éléments en utilisant un index.– Requière moins de mémoire

– Les éléments sont accédés en temps constant

Vecteurs en Scheme

(make-vector k ) ; afin de créer un vecteur de k éléments (make-vector k init ) ; dont les éléments sont initialisés à init

(vector? obj ) '#( element_0 ... element_k-1 ) ; afin de déclarer un vecteur constant Ex: '#(0 (2 2 2 2) "Anna")

Page 17: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

• Constructeurs and accesseurs> (define v (vector 1 (+ 1 2)))

#(1 3) > (vector ‘a ‘b ‘c)

#(a b c)> (vector-ref v 0)

1 > (vector-length v)

2 > (vector-set! v 3 10)

2

• L’index commence à 0.

Vecteurs en Scheme

Page 18: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

vector-set!

CSI2520

(let ((v (vector 'a 'b 'c 'd 'e)))  (vector-set! v 2 'x) v)  

#(a b x d e)

(define vector-fill!  (lambda (v x)    (let ((n (vector-length v)))      (do ((i 0 (+ i 1)))          ((= i n))        (vector-set! v i x))))) 

(let ((v (vector 1 2 3)))  (vector-fill! v 0) v)  #(0 0 0)

Page 19: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

conversion de listes à vecteurs

CSI2520

(list->vector L) (vector->list L)

(define vector->list  (lambda (s)    (do ((i (- (vector-length s) 1) (- i 1))         (ls '() (cons (vector-ref s i) ls)))        ((< i 0) ls)))) 

(vector->list '#(a b c))  (a b c) 

(let ((v '#(1 2 3 4 5)))  (apply * (vector->list v)))  120

Page 20: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Exemple

CSI2520

(let ((v '#(1 2 3 4 5)))  (let ((ls (vector->list v)))    (list->vector (map * ls ls))))  

#(1 4 9 16 25)

Page 21: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Exemple

(define vector-sum (lambda (vec) (let ((size (vector-length vec)) (position 0) (total 0)) (do () ((= position size) total)

(set! total (+ total (vector-ref vec position))) (set! position (+ position 1))))))

(define vector-sum (lambda (vec) (do ((remaining (vector-length vec) (- remaining 1))

(total 0 (+ total (vector-ref vec (- remaining 1))))) ((zero? remaining) total))))

Page 22: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tri des vecteurs et des listes

CSI2520

(quick-sort  '#(3 4 2 1 2 5) <)  #(1 2 2 3 4 5)

(merge-sort '(0.5 1.2 1.1) >)  (1.2 1.1 0.5)

On doit avoir:(and (test x y) (test y x))#f

Voyons maintenant le tri fusion de listes…

Page 23: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Extraire une sous-liste

CSI2520

(define (sub L start stop ctr) ; extract elements start to stop into a list (cond ( (null? L) L) ( (< ctr start) (sub (cdr L) start stop (+ ctr 1))) ( (> ctr stop) '() ) (else (cons (car L) (sub (cdr L) start stop (+ ctr 1))) ) ) )

Page 24: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Diviser une liste en deux

CSI2520

(define (split L) ; split the list in half: ; returns ((first half)(second half)) (let ((len (length L))) (cond ((= len 0) (list L L) ) ((= len 1) (list L '() )) (else (list (sub L 1 (/ len 2) 1)(sub L (+(/ len 2)1) len 1) ) ) ) ) )

Page 25: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Fusion de 2 listes triées

CSI2520

(define (mergelists L M) ; assume L and M are sorted lists (cond ( (null? L) M) ( (null? M) L) ( (< (car L)(car M)) (cons (car L) (mergelists (cdr L)M))) (else (cons (car M) (mergelists L (cdr M)))) ) )

Page 26: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tri fusion

CSI2520

(define (mergesort L) (cond ((null? L) '()) ((= 1 (length L)) L) ((= 2 (length L)) (mergelists (list (car L))(cdr L))) (else (mergelists (mergesort (car (split L)) ) (mergesort (car (cdr (split L))) ) )) ) )

Page 27: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

quicksort

CSI2520

(define (qsort e) (if (or (null? e) (<= (length e) 1)) e (let loop ((left null) (right null) (pivot (car e)) (rest (cdr e))) ; named let (if (null? rest) (append (append (qsort left) (list pivot)) (qsort right)) (if (<= (car rest) pivot) (loop (append left (list (car rest))) right pivot (cdr rest)) (loop left (append right (list (car rest))) pivot (cdr rest)))

Page 28: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Les arbres

• Un arbre binaire peut être représentée avec des listes imbriquées

a / \b c / \ d e

(a b (c d e))ou

(a (b () ()) (c (d () ()) (e () ()))ou

(a b.(c d.e))

Page 29: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

arbre?

CSI2520

(define tree? (lambda (t) (cond ((not (list? t)) #f) ((null? t) #t) ((not (= (length t) 3)) #f) ((not (tree? (cadr t))) #f) ((not (tree? (caddr t))) #f) (else #t)) ) ) (tree? '(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ())))(tree? '(73 (31 (5 () ()) ()) (101 (83 () (97 () () ())) ())))(tree? '(73 (31 (5 () ()) ()) (101 (83 () (97 ())) ())))

Page 30: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Parcours inordre

CSI2520

(define inorder (lambda (t)

(define do-inorder (lambda (t) (if (null? t) () (append (inorder (cadr t)) (cons (car t) (do-inorder (caddr t)))) ) ) ) (if (not (tree? t)) (list 'not-a-tree t) (do-inorder t)) ) )

(inorder '(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ())))

Page 31: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

recherche

CSI2520

(define search (lambda (x t)

(define do-search (lambda (x t) (cond ((null? t) #f) ((equal? x (car t)) #t) ((precedes? x (car t)) (do-search x (cadr t))) ((precedes? (car t) x) (do-search x (caddr t))) (else #f) ) ) )

(if (not (tree? t)) (list 'not-a-tree t) (do-search x t)) ) )

(define precedes? (lambda (x y) (< x y)))

(search 83 '(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ())))(search 84 '(73 (31 (5 () ()) ()) (101 (83 () (97 () ())) ())))

Page 32: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Recherche dans un arbre

(define (tree-search tree value) (cond ((null? tree) #f) ((equal? value (car tree)) #t) ((< value (car tree)) (tree-search (cadr tree) value)) (else (tree-search (caddr tree) value))))

Au lieu de <, on pourrait utiliser precedent?

(define precedent? (lambda (x y) (< x y)))

Page 33: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Insertion dans une liste

(define (tree-insert tree value) (cond ((null? tree) (list value '() '())) ((< value (car tree)) (list (car tree) (tree-insert (cadr tree) value) (caddr tree))) (else (list (car tree) (cadr tree) (tree-insert (caddr tree) value)))))

Page 34: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Détruire un nœud de l’arbre

CSI2520

(define delete (lambda (x t)

(if (not (tree? t)) (list 'not-a-tree t) (do-delete x t)) ) )

Page 35: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Détruire la racine d’un arbre(define do-delete (lambda (x t) (cond ((null? t) ()) ((and (equal? x (car t)) (null? (cadr t))) (caddr t)) ((and (equal? x (car t)) (null? (caddr t))) (cadr t)) ((equal? x (car t)) (let ((r (removemax (cadr t)))) (list (cdr r) (car r) (caddr t)) )) ((precedes? x (car t)) (list (car t) (do-delete x (cadr t)) (caddr t))) ((precedes? (car t) x) (list (car t) (cadr t) (do-delete x (caddr t)))) (else t) ) ) )

Page 36: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Détruire un nœud de l’arbre

(define removemax (lambda (t) (cond ((null? (caddr t)) (cons (cadr t) (car t))) (else (let ((r (removemax (caddr t)))) (cons (list (car t) (cadr t) (car r)) (cdr r)) )) ) ) )

Page 37: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Décompte du nombre d’éléments dans un arbre

(define (nsymbols tree) (if (list? tree)

(+ (nsymbols (car tree)) (nsymbols (cdr tree))) (if (symbol? tree) 1 0) ) )

> (nsymbols '(+ a (* b c))) 5

- Représentation sans les ( )

Page 38: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Avec récursivité terminale

(define (nsymbols tree) (nsymbolsb tree 0))

(define (nsymbolsb tree n) (if (list? tree)

(nsymbolsb (cdr tree) (nsymbolsb (car tree) n))

(+ n (if (symbol? tree) 1 0)) ) )

Page 39: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

D’arbre à liste

(define (tree->list tree) (reverse (tree->list2 tree '())))

(define (tree->list2 tree lst) (if (list? tree) (tree->list2 (cdr tree) (tree->list2 (car tree) lst)) (if (null? tree) lst (cons tree lst) ) ) )

Page 40: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Évaluation différée

• Ou évaluation paresseuse, consiste à ne pas évaluer immédiatement une expression

(delay exp) ; retourne une ‘promesse’ d’évaluation

(force promesse) ; force l’évaluation promise

Page 41: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Exemple

(define (produit x y)(if (negative? x) (* x x) (* x (force y))))

(produit v (delay (sqrt v)))

Page 42: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Avec les listes

• Dans certains cas, il est possible d’obtenir un résultat sans avoir à évaluer tous les éléments d’une liste.

(define (suite n1 n2 N)(if (zero? N) ()(cons (+ n1 n2) (suite n2 (+ n1 n2) (- N 1)))))

(suite 0 1 10)(1 2 3 5 8 13 21 34 55 89)

Page 43: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Exemple sans delay

(define (membre nbre L) (cond ((null? L) ()) ((< nbre (car L)) ()) ((= nbre (car L)) nbre) (#T (membre nbre (cdr L)))))

(membre 15 (suite 0 1 200)) ; tous les éléments sont examinés!

nil

Page 44: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

CSI2520

Exemple avec delay

(define (suite n1 n2 N) (if (zero? N) () (cons (+ n1 n2) (delay (suite n2 (+ n1 n2) (- N 1))))))

(define (membre nbre L)

(let ((premier (car L)))

(cond ((null? L) ())

((< nbre premier) ())

((= nbre premier) nbre)

(#T (membre nbre (force (cdr L)))))))

Page 45: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tours de Hanoi

CSI2520

(define (dohanoi n to from using) (if (> n 0) (begin (dohanoi (- n 1) using from to) (display "move ") (display from) (display " --> ") (display to) (newline) (dohanoi (- n 1) to using from) ) ) )

(define (hanoi n) (dohanoi n 3 1 2) )

Page 46: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tic Tac Toe

CSI2520

(define start ‘((1 2 3) (4 5 6) (7 8 9) (1 4 7) (2 5 8) (3 6 9) (1 5 9) (3 5 7)))X joue:((X 2 3) (4 5 6) (7 8 9) (X 4 7) (2 5 8) (3 6 9) (X 5 9) (3 5 7))O joue:((X 2 3) (4 5 6) (7 O 9) (X 4 7) (2 5 O) (3 6 9) (X 5 9) (3 5 7))

1 2 3

4 5 6

7 8 9

X

O

Page 47: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tic Tac Toe

CSI2520

(define subst (lambda (new old l) (cond ((null? l) (quote ())) ((atom? (car l)) (cond ((eq? (car l) old) (cons new (subst new old (cdr l)))) (else (cons (car l) (subst new old (cdr l)))))) (else (cons (subst new old (car l)) (subst new old (cdr l)))))))

La substitution:

Page 48: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tic Tac Toe

CSI2520

(define (all-equal? list) (cond ((null? list) `()) ((null? (cdr list)) (car list)) ((equal? (car list) (cadr list)) (all-equal? (cdr list))) (else #f)))

Egalité de tous les éléments d’une liste?

Page 49: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tic Tac Toe

CSI2520

(define (play board player position) (subst player position board))

(define (winner board) (map all-equal? board))

Page 50: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tic Tac Toe

CSI2520

(define (number-of-member x list) (cond ((null? list) 0) ((equal? x (car list)) (+ 1 (number-of-member x (cdr list)))) (else (number-of-member x (cdr list))))

Page 51: CSI2520 Le langage Scheme (2) Un langage de programmation fonctionnelle

Tic Tac Toe

CSI2520

X

X X

O O

(map (lambda (list) (number-of-member ‘X list)) ‘((X 2 3) (4 X X) (7 O O) (X 4 7) (2 X O) (3 X O) (X X O) (3 X 7))))(1 2 0 1 1 1 2 1)