Planche : 1



Le langage Scheme

Revision: 1.11





  Itérateurs, l, letrec ...





Christian Queinnec   UPMC--LIP6

Planche : 2

A-listes ou liste d'associations


((un 1)(zero 0)(deux 2)) 


<Aliste> ::= ()
          |  ( <association> ... )

<association> ::= ( <clef> <valeur> ...) 

Planche : 3

Recherche dans une Aliste


(define (assoc cle aliste)
  (if (pair? aliste)
      (if (equal? cle (caar aliste))
          (car aliste)
          (assoc cle (cdr aliste)) ) 
      #f ) ) 

C'est un semi-prédicat.

(cadr p) º (car (cdr p)).

Planche : 4

« Modification » de Alistes

Modification logique par:
(cons (cons clef valeur)
      aliste ) 

Par exemple:
((deux 1 0) (un 1)
            (zero 0)
            (deux 2) ) 
Attention toujours à cons et list!

Planche : 5

Bloc local


(let ((variable1 forme1)
      ...
      (variablen formen) )
  forme... ) 

évalue (begin forme...) dans l'environnement où variablei vaut la valeur de formei.

Planche : 6

Itérateurs classiques sur listes


(define (map fn l)
  (if (pair? l)
      (cons (fn (car l))
            (map fn (cdr l)) )
      '() ) )
(define (for-each fn l)
  (if (pair? l)
      (begin (fn (car l))
             (for-each fn (cdr l)) ) ) )
(define (mapcan fn l) ; Non en R4RS
  (if (pair? l)
      (append (fn (car l))
              (mapcan fn (cdr l)) )
      '() ) ) 

Mais aussi:
(define (reduce fn end list) ; non en R4RS
  (if (pair? list)
      (fn (car list) (reduce fn end (cdr list)))
      end ) ) 
(define (combine fn list) ; non en R4RS
  (if (pair? list)
      (if (pair? (cdr list))
          (fn (car list) (combine fn (cdr list)))
          (car list) )
      (error 'combine "missing argument") ) )

Quelques exemples d'emploi:
? (map list '(1 2 3))= ((1) (2) (3)) 
? (for-each display '(1 2 3))
123
? (mapcan identity '((a) (b c) (d e f)))= (a b c d e f) 
? (combine + '(1 2 3 4))= 10 
? (reduce * 1 '(1 2 3 4))= 24  

Planche : 7

Fonctions anonymes

À la fonction mathématiquement définie comme:
(x,y) ® 1-x2 -y2

correspond la graphie (inspirée des notations du l-calcul:
(lambda (x y)
  (- 1 (+ (* x x)
          (* y y) )) ) 


? (map (lambda (x) (* x x)) '(1 2 3 4))= (1 4 9 16) 
? (let ((square (lambda (x) (* x x))))
  (map square '(1 2 3 4)))= (1 4 9 16) 

Planche : 8

Portée

La portée est la portion de texte où une notion est visible. La portée est lexicale ou globale.


Planche : 9

Portée dans un let


(let ((v1 p1)
      ...
      (vn pn) )
  p... ) 

est équivalent à:


((lambda (v1 ...vn)
   p... )
 p1 ...pn ) 

Planche : 10

Portée dans letrec


(letrec ((v1 p1)
         ...
         (vn pn) )
  p... ) 

évalue (begin p...) dans l'environnement où vi vaut la valeur de pi. Les formes pi sont évaluées dans ce même environnement.


? (map (letrec ((fact (lambda (n)
                      (if (= n 1)
                        1
                        (* n (fact (- n 1)))))))
       fact)
     '(1 2 3 4))= (1 2 6 24)  


(letrec ((even? (lambda (n) 
                  (or (= n 0) (odd? (- n 1))) ))
         (odd? (lambda (n)
                 (and (> n 0) (even? (- n 1))) )) )
  (odd? 5) ) 

Planche : 11

Syntaxes usuelles

Les « séquences implicites »:
(lambda v* p*) º (lambda v* (begin p*)) 

Les définitions de fonctions ne sont que des définitions de variables:
(define (f v1 ...vn)
  p* ) 

est équivalent à:


(define f
  (lambda (v1 ...vn)
    p* ) ) 

tandis que les définitions internes ne sont que des letrec déguisés:
(lambda v*
  (define v1 p1)
  ...
  (define vn pn)
  p* ) 

est équivalent à:


(lambda v*
  (letrec ((v1 p1)
           ...
           (vn pn) )
    p* ) ) 

La fonction assoc mieux écrite:
(define (assoc clef aliste)
  (define (chercher al)
    (if (pair? al)
        (if (equal? clef (caar al))
            (car al)
            (chercher (cdr al)) )
        #f ) )
  (chercher aliste) ) 

et dans sa version style Indiana:
(define assoc 
  (lambda (clef aliste)
    (letrec ((chercher 
              (lambda (al)
                (if (pair? al)
                    (if (equal? clef (caar al))
                        (car al)
                        (chercher (cdr al)) )
                    #f ) ) ))
       (chercher aliste) ) ) ) 

Planche : 12

Durée de vie -- fermeture


(define (faire-prefixeur msg)
  (lambda (list)
    (cons msg list) ) )

(define raleur
  (faire-prefixeur (list 'j 'aime 'pas 'les)) )

? (raleur '(schtroumpfs))= ((j aime pas les) schtroumpfs) 
? (set-car! (car (raleur '())) 't)
? (raleur '(malabars))= ((t aime pas les) malabars)   

Planche : 13

Arité variable

Principe libertaire: Tout ce que se permet le système, il vous le permet aussi!


(lambda variable corps) 

crée une fonction prenant un nombre quelconque d'arguments (un « paquet d'arguments ») réunis en une liste. Ainsi
(define list 
  (lambda list list) ) 

On peut également écrire pour définir une fonction au moins binaire:
(lambda (x y . z) ...) 

Planche : 14

Invocation calculée


(apply fonction p1 ...pn paquet) 

Cette fonction applique fonction à ses arguments, les premiers sont les valeurs de p1 ...pn les suivants ceux présents dans le paquet.


? (apply list '(1 2))= (1 2) 
? (apply + 1 2 '(3 4))= 10 
? (apply apply + 1 '(2 (3 4)))= 10 

Planche : 15

Résumé

Les fonctions anonymes sont des citoyennes de première classe.

Notion indépendantes de portée et de durée de vie.

Prééminence de la portée lexicale sans restriction et notion de fermeture.

Des syntaxes particulières essentielles prédéfinies et l'abstraction syntaxique.

Planche : 16

Terminologie

semi-prédicat
fonction pouvant être utilisée comme un prédicat mais qui retourne des résultats Vrais plus intéressants que #t.

bloc local
ou forme let.

séquence implicite
Une forme begin sous-entendue lorsque, syntaxiquement, une suite de formes peut apparaître (dans le corps d'un lambda, d'un let, d'un letrec, dans une clause de cond

définition
interne (par letrec) ou globale (notion d'environnement global dynamique et non hyperstatique).

principe libertaire
Hors lui point de salut.
Ce document a été traduit de LATEX par HEVEA.