Informatique et recherche
opérationnelle
IFT2030

Concepts des langages de programmation

Automne 2002


Accueil

Professeur et
Démonstrateurs

Horaires et locaux

Notes de cours

Démonstrations
et devoirs

Examens

Liens utiles

Au sujet du
livre de cours

Consultez vos notes

Foire aux questions
(FAQ)

Démonstration 7: S'en sortir honnêtement avec Scheme

Note: Le "baratin" de la semaine est un sous-ensemble des notes de démonstrations du cours de Yoshua Bengio (http://www.iro.umontreal.ca/~bengioy/ift2030/A01/Demo1-scheme.htm)

Structures de données

Scheme utilise essentiellement les listes, mais d'autres structures de données sont aussi proposées.

a) Les listes et les paires

  • Une liste est un ensemble d'élement de types pas nécessairement homogènes entourés par des parenthèses et séparés par un espace. C'est une strcuture de données qui est  modifiable. Toute expression qui n'est pas une constante ou une variable est nécessairement une liste.

  • On peut construire une liste avec la procédure list, la procédure cons ou le quote:

        >(define a (cons 1 '()))
        >a
        (1)
        >(car a)
        1
        >(cdr a)
        ()
        >(list? a)    ; prédicat pour savoir si a est une liste
        #t
     

      La liste vide est représentée par `() et n'est pas une paire
    • Exemples de listes:


             (3 x 5)
             (+ 3 4)
     

    •     Exemple de construction avec la procédure list ou le quote:


        >(define x 1)
        >(define b (list 1 2 x))    ; ici x est évalué
        >(define c '(1 2 x))        ; ici x est un symbole
        >b
        (1 2 1)
        >c
        (1 2 x)
        >(car c) ; retourne le premier élément de la liste
        1
        >(cdr c) ; retourne une liste
        (2 x)
        >(cadr c)    ; équivalent à (car (cdr c))
        2
        >(cddr c)    ; équivalent à (cdr (cdr c))
        (x)
        >(caddr c)   ; équivalent à (car (cdr (cdr c)))
        x
        >(cdddr c)   ; équivalent à (cdr (cdr (cdr c)))
        ()
        >(define d '((1 2) 3 4))
        >(car d)
        (1 2)
        >(caar d)    ; équivalent à (car (car d))
        1

    • Pour utiliser une liste en tant que liste et non en tant qu'application préfixe d'une procédure ou forme spéciale, on utilise le quote, ou la procédure list:
              > (define l '(1 2 a))
         >l
         (1 2 a)
         >(define l (list 1 2 'a))

Remarque

Le nombre de compostion de car et/ou cdr est limité à 4.
  •     Une paire contient deux champs, on les nommes car et cdr.  On construit une paire avec la procédure cons :
        >(define a (cons 1 2))
    >a
    (1 . 2)
    >(car a)      ; retourne le champ car
    1
    >(cdr a)      ; retourne le champ cdr
    2
    >(pair? a)    ; prédicat pour savoir si a est une paire
    #t

Quelques opérations sur les listes:

  • Opérations append, length, reverse, list-ref
    >(define d '((1 2) 3 4))
    >(length d)    ; Nombre d'éléments dans la liste
    3
    >(append d '(5 (6 7) 8))    ; Concaténation
    ((1 2) 3 4 5 (6 7) 8)
    >(reverse d)   ; Renverse les éléments
    (4 3 (1 2))
    >(list-ref d 2)   ; Retourne le 3-ieme élément de la liste.
    4
    >(list-ref d 0)   ; Retourne le premier élément de la liste.
    (1 2)
  • Transformations list->string, string->list
    >(string->list "Hello"); Conversion chaîne de caractàres - liste
   (#\H #\e #\l #\l #\o)

    >(list->string '(#\H #\e #\l #\l #\o)); Conversion liste - chaîne de caractàres
   "Hello"

    Note: Extraire une sous-chaîne avec substring

        >(substring "Hello" 1 3); Extraire une sous-chaîne d'une chaîne de caractàres
       "el"

  • Recherche dans les listes:
    La recherche dans les listes peut être effectuée à l'aide des fonctions "member".  Ces fonctions retournent la sous-liste commençant par l'élément trouvé, et #f si l'élément n'a pu être trouvé.

    >(memq c '(a b c d e))    ; utilise eq? pour trouver l'élément
    (c d e)
    >(memv 3 '(1 2 3 4 5))    ; utilise eqv? pour trouver l'élément
    (3 4 5)
    >(member '(3 4) '((1 2) (3 4) (5 6)))  ; utilise equal? pour trouver l'élément
    ((3 4) (5 6))
    >(member 7 '(1 2 3 4 5))
    #f

Les expressions (suite)

b) Let, Let* et Letrec

Les commandes let, let* et letrec* permet la formation des blocs d'expressions en scheme. Ils sont syntaxiquement identique mais la portée des variables liées est différentes dans chacun des cas.
  • Dans le cas de let (let <bindings> <body>) les valeur initiales sont évaluées avant de lier les variables contenus dans la section de liens <bindings> Dans l'exemple suivant bien que x soit lié à la valeur 2 dans la section de liage, l'évaluation de y prendra la valeur initial de x qui est de 4 (define x 4) et donc le résultat sera 6 et non pas 4.
>(define x 4)
(let ((x 2) (y x)) (+ x y))
  • Dans le cas de let* le liage et l'évaluation se font séquentiellement de ce afit si on remplace l'instruction précédente let par let* on obtient :
       >(define x 2)
   >(let* ((x 0) (y x)) y)
    0

       La forme let*  (let*  <bindings> <body>) permet d'utiliser les variables précédemment définies dans la liste.

  • Dans le cas de letrec les liaisons sont déjà effective lorsque les valeurs initiales sont évaluées, ce qui permet une définition mutuellement  reccursive comme dans l'exemple suivant :
 >(letrec ((even?
    (lambda (n)
      (if (zero? n)
          #t
          (odd? (- n 1)))))
    (odd?
       (lambda (n)
         (if (zero? n)
            #f
            (even? (- n 1))))))
    (even? 88))
>#t

c) Lambda expression

Le lambda-calcul est fondamental en Scheme.  Brièvement, on peut dire qu'il s'agit de fonctions anonymes, c'est à dire des objets qui s'évaluent à
une fonction, sans nécessairement être liés à une quelconque variable.
    (lambda a b) ; définition d'une fonction. Arguments dans a et corps dans b.
    Exemples concrets:

    >(define succ (lambda (x) (+ x 1)))
    >(succ 2)
    3

    Je viens donc de définir une fonction qui retourne le successeur de son argument et j'ai assigné cette fonction à la variable succ, pour ensuite
pouvoir appeller succ normalement.  Il existe un moyen pour enlever cette assignation, c'est d'utiliser directement la définition de la fonction pour
l'appliquer:

    >((lambda (x) (+ x 1)) 2)
    3

    Ici j'ai tout simplement remplacé succ par sa définition.  Un autre exemple:

    >(define (make-adder x) (lambda (y) (+ x y)))
    >(define add1 (make-adder 1))
    >(define add5 (make-adder 5))
    >(add1 2)
    3
    >(add5 2)
    7

La fonction make-adder prend l'argument x et produit une fonction qui retourne son argument augmenté de x.  C'est ce qui explique que add1 soit
une fonction qui retourne le successeur de son argument.

d) map et apply

  • map
En Scheme, il peut être intéressant d'appliquer une procédure à tous les éléments d'une liste pour ensuite obtenir une liste contenant les résultats de ces applications.  On peut utiliser pour ce faire la fonction map, qui prend 2 arguments:     (map <func> <list>).  Map construit alors une liste contenant les résultats de l'application de <func> sur les éléments de la liste <list>.  Quelques exemples:
       >(map (lambda (x) (+ x 1)) '(1 2 3 4 5))
    (2 3 4 5 6)
    >(map car '((a b) (c d) (e f)))
    (a c e)

    De manière plus générale, on peut utiliser map sur plusieurs listes:

    >(map + '(1 2 3 4 5) '(2 3 4 5 6))
    (3 5 7 9 11)

    Il est à noter que les listes doivent alors avoir le même nombre d'éléments.
 

  • apply
Pour appliquer une procédure à une liste de paramètres, on peut utiliser la procédure apply.  La forme d'un appel à apply est la suivante:
   (apply <func> <arg1> ... <argn> <argf>).
D'abord, apply évalue la fonction <func> et chacun des ses arguments <arg1> ... <argn> et <argf>.  Elle appelle ensuite la fonction évaluée avec <arg1> ...<argn> comme n premiers paramètres et <argf> comme la liste contenant le reste des paramètres.
    • La première forme prend d'abord <func>, la procédure à appliquer, suivi d'une liste <args> d'arguments à passer en paramètre à <func>.
    • La deuxième forme est équivalente à:  (apply <func> (append (list <arg1> ... <argn>) <argf>)
Donc on passe les n premiers arguments suivis du reste des arguments dans la liste <argf>.  Les cas où n=0 ou argf='() sont aussi possibles:
        (apply <func> <argf>)
     
    Ici on appelle <func> avec la liste d'arguments <argf>.
        (apply <func> <arg1> ... <argn> '())
     
    Ici on appelle <func> avec la liste d'arguments (<arg1> ... <argn>). Cette dernière forme correspond à la forme mieux connue:
        (<func> <arg1> ... <argn>)

        Exemples:
        >(define (poly-degre-2 a b c) (lambda (x) (+ (* a x x) (* b x) c)))   ; Ici poly-degre-2 est une fonction qui génère des polynômes du second degré
        >((poly-degre-2 1 2 3) 2)
        11
        >((apply poly-degre-2 '(1 2 3)) 2)
        11
        >((apply poly-degre-2 1 (list 2 3)) 2)
        11
        >((apply poly-degre-2 1 2 '(3)) 2)
        11
        >((apply poly-degre-2 1 2 3 '()) 2)
        11

Recursivité dans Scheme

  • La récursivité en Scheme est très utile.  Les interprètes Scheme implémentent l'optimisation de récursivité terminale, ce qui permet d'obtenir des formes récursives aussi rapides que des formes itératives équivalentes.  Tout d'abord, un exemple simple, la fonction length qui calcule le nombre d'éléments d'une liste donnée. Je pourrais définir cette fonction de la façon suivante:
   >(define length (lambda (liste)
                    (if (null? liste)
                        0
                        (+ 1 (length (cdr liste)))))
 


Dernière mise à jour : Sun Nov 10 20:57:28 EST 2002
dift2030@iro.umontreal.ca