123
Programmation fonctionnelle en langage Scheme - Support PG104 - M.Desainte-Catherine et David Renault ENSEIRB-MATMECA, d´ epartement d’informatique January 25, 2016

Programmation fonctionnelle en langage Scheme - labri.fr · Historique Les langages des ann ees 1950 I FORTRAN (1954) : calcul scienti que, donn ees et calcul num erique. I Lisp (1958)

Embed Size (px)

Citation preview

Programmation fonctionnelle en langage Scheme- Support PG104 -

M.Desainte-Catherine et David Renault

ENSEIRB-MATMECA, departement d’informatique

January 25, 2016

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Objectifs pedagogiques

Objectif generalDecouverte de la programmation fonctionnelle pure a travers :

I Les formes qu’elle prend syntaxiquement (expressions, fonctions et listesrecursives)

I Les methodes qu’elle permet de deployer.

Competences generales attendues

I Specifier un calcul de facon fonctionnelle plutot qu’imperative : programmer aumoyen d’expressions plutot que d’instructions

I Specifier des calculs recursivement plutot qu’iterativement

I Specifier un calcul generique : abstraire un calcul au moyen de parametresfonctionnels et de retours fonctionnels

I Comparer des solutions selon le style et la complexite

Ce support est accessible en version electronique mise a jour regulierement a l’adresse :

http://www.labri.fr/perso/renault/working/teaching/schemeprog/schemeprog.php

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Concepts et terminologie

Concepts fonctionnels

I Ecriture fonctionnelle : programmation par applications de fonctions plutot quepar l’execution de sequences d’instructions

I Transparence referentielle : chaque expression peut etre remplacee par sonresultat sans changer le comportement du programme

I Programmation fonctionnelle pure : sans effets de bords, avec transparencereferentielle.

I Fonctions de premiere classe : type fonction, constantes fonction, operateurssur les fonctions

Autres concepts nouveaux

I Typage dynamique : Les variables sont typees au moment de l’execution et nonau moment de la compilation

I References : ce sont des adresses sur des objets, elles sont utilisees chaque foisque les contenus ne sont pas utiles (passages de parametres, retours defonctions)

I Garbage collector ou ramasse-miettes : gestion dynamique et automatique dela memoire. L’utilisateur ne s’occupe pas de desallouer la memoire.

Transparence referentielle en C

Ces fonctions de la bibliotheque C respectent-elles la transparencereferentielle?

I int abs(int j); oui ou non

I int rand(void); oui ou non

Transparence referentielle en C

int y = 0;

int f(x) {

return x + y++;

}

void g() {

int i= f(1);

int j= f(1);

}

I Ce code respecte-il latransparence referentielle?

oui ou non

I Si non a cause de quelle

instruction? int y = 0;

return x + y++;

int i= f(1);

int j= f(1);

int y = 0;

int f(x) {

return x + y;

}

void g() {

int i= f(1);

int j= f(1);

}

I Ce code respecte-il latransparence referentielle?

oui ou non

I Si non a cause de quelle

instruction? int y = 0;

return x + y;

int i= f(1);

int j= f(1);

Transparence referentielle en C

i n t y = 0 ;i n t f ( x ) {

r e t u r n x + y++;}v o i d g ( ) {

i n t i= f ( 1 ) ; /∗ i =1 ∗/i n t j= f ( 1 ) ; /∗ j =2 ∗/

}

——————————–

i n t y = 0 ;i n t f ( x ) {

r e t u r n x + y++;}v o i d g ( ) {

i n t j= f ( 1 ) ; /∗ j =1 ∗/i n t i= f ( 1 ) ; /∗ i =2 ∗/

}

int y = 0;

int f(x) {

return x + y;

}

void g() {

int i= f(1);

int j= f(1);

}

I Ce code respecte-il latransparence referentielle?

oui ou non

I Si non a cause de quelle

instruction? int y = 0;

return x + y;

int i= f(1);

int j= f(1);

Historique

Les langages des annees 1950

I FORTRAN (1954) : calcul scientifique, donnees et calcul numerique.

I Lisp (1958) : calcul symbolique, donnees et algorithmes complexes (IA), demonstrations automatiques,jeux etc.

I Algol (1958) : langage algorithmique et structure, recursivite.

Les langages lisp

I 1958 : John Mac Carthy (MIT)

I 1986 : common lisp ANSI (portabilite, consistence, expressivite, efficacite, stabilite).

I Les enfants de lisp :

I Logo (1968), langage visuel pedagogiqueI Smalltalk (1969, Palo Alto Research Center de Xerox) premier langage oriente objetsI ML (1973, R. Milner, University of Edinburgh), preuves formelles, typage statique, puis CaML

(1987 INRIA), projet coq, et Haskell purement fonctionnel, paresseux.I Scheme (1975, Steele et Sussman MIT) mieux defini semantiquement, portee lexicale, fermeture,

et continuations de premiere classe.I emace-lisp (Stallman 1975, Gosling 1982), langage d’extension de GNU Emacs.I CLOS (1989, Common Lisp Object System), common lisp oriente objets.

Le λ-calcul

Theorie des fonctions d’Alonzo Church (1930), modele universel de calcul, directeurde these d’Alan Turing (machines de Turing, theorie de la calculabilite).

Syntaxe – λ-termes

I Variables : x , y , ...

I Applications : si u et v sont des λ-termes uv est aussi un λ-terme. On peutalors voir u comme une fonction et v comme un argument, uv etant alorsl’image de v par la fonction u.

I Abstractions : si x est une variable et u un λ-terme alors λx .u est un λ-terme.Intuitivement, λx .u est la fonction qui a x associe u.

ExempleI Constante : λx .y

I Identite : λx .x

I Fonction renvoyant une fonction : λx .λy .a

I Application : xyz ou ((xy)z)

Remarques: les applications sont faites de gauche a droite en l’absence de

parentheses, une occurrence de variable est dite muette ou liee si elle apparaıt dans le

corps d’un λ-terme dont elle est parametre, sinon elle est dite libre.

Syntaxe du λ-calcul

Soient x et y des variables et u et v des λ-termes

I Les λ-termes suivants sont-ils bien formes : oui ou non

I xI λx . uI λλx. uI λx . yI λx uI (λx . u) yI (λu . u) yI (λx . u) vI ((x u) y)

I Dans les λ-termes suivants, les occurences de la variable x sont-elles

libres ou liees ?

I ((u x) y)I λy . u xI λx . u x

Le λ-calcul – la substitution

Cette operation permet de remplacer les occurrences d’une variable par un terme pourrealiser le calcul des λ-termes. On note t[x := u] la substitution dans un lambdaterme t de toutes les occurrences d’une variable x par un terme u.

ExempleDans ces exemples, les symboles x , y , z, a sont des variables.

I Dans une application : xyz[y := a] = xaz

I Dans une abstraction (cas normal) : λx .xy [y := a] = λx .xa

I Capture de variable libre : λx .xy [y := ax] = λz.zax(et non λx .xax),renommage de la variable liee

I Substitution inoperante (sur variable liee): λx .xy [x := z] = λz.zy = λx .xy

Definition

I Variable: si t est une variable alors t[x := u] = u si x = t et t sinon

I Application: si t = vw alors t[x := u] = v [x := u]w [x := u] si v et w sont destermes.

I Abstraction: si t = λy .v alors t[x := u] = λy .(v [x := u]) si x 6= y et y n’estpas une variable libre de u. Si y est une variable libre de u, on renomme y avantde substituer. Si x = y le resultat est t.

Substitution en λ-calcul

Soient x, y, z t et a des variables, votez pour une des reponses pour chaque resultat desubstitution.

I xzty [t := ax] = xzaxy ou xzty ou xzty

I xztyt[t := ax] = xzaxyt ou xzaxyax ou xztyt

I λz.xz[x := yz] = λz.yzz ou λz.xz ou λt.yzt

I λy .xyz[z := a] = λy .xya ou λz.xza ou λy .xyz

I λy .xyz[y := a] = λy .xaz ou λy .xyz ou λa.xaz

Le λ-calcul – la β-reduction

On appelle redex un terme de la forme (λx .u)v . On definit alors la β-reduction

(λx .u)v −→ u[x := v ]

I La reduction du terme (λx .u)v est la valeur de la fonction λx .u appliquee a lavariable v .

I u est l’image de x par la fonction (λx .u),

I L’image de v est obtenue en substituant dans u, x par v .

ExempleI (λx .xy)a donne xy [x := a] = ay

I (λx .y)a donne y [x := a] = y

Remarque Les termes sont des arbres avec des noeuds binaires (applications), desnoeuds unaires (les λ-abstractions) et des feuilles (les variables). Les reductionspermettent de modifier l’arbre, cependant l’arbre n’est pas forcement plus petit apresl’operation. Par exemple, si l’on reduit

(λx .xxx)(λx .xxx)

on obtient(λx .xxx)(λx .xxx)(λx .xxx)

β-reductions en λ-calcul

Soient x, y, z t et a des variables, votez pour un resultat de β-reductions.

I (λx.x) a −→ λa.a ou a

I (λx.x) (λy.a) −→ λy.a ou λx.x

I (λx.x) ((λy.a) z) −→ (λy.a) z ou a ou λx.x

I (λx.x) ((λy.a) (λy.yt)) −→ (λx.x) a ou (λy.a) (λy.yt) ou a

I (λxy.xay) z t −→ zat ou λxy .xay) z t

I (λx.(λy.xay)) z t −→ (λy.zay) t ou zat ou (λx.xaz) t

Le λ-calcul – la normalisation

Un lambda-terme t est dit en forme normale si aucune β-reduction ne peut lui etreappliquee, c’est-a-dire si t ne contient aucun redex. Ou encore, s’il n’existe aucunlambda-terme u tel que t −→ u.

Remarques

I On peut simuler la normalisation des λ-termes a l’aide d’une machine de Turing,et simuler une machine de Turing par des λ-termes.

I Differentes strategies de reduction sont definies dans le λ-calcul : strategieapplicative (par valeur, dans les langages lisp et scheme), strategie paresseuse(par nom, dans Haskell).

I La normalisation est un calcul confluent. Soient t, u1 et u2 des lambda-termestels que t −→ u1 et t −→ u2. Alors il existe un λ-terme v tel que u1 −→ v etu2 −→ v . Consequence : l’ordre d’evaluation des arguments d’une fonction n’apas d’influence sur le resultat.

ExempleLes symboles x , y , z, a sont des variables. Soit le terme (λx .y)((λz.zz)a)

I Strategie applicative : (λx .y)((λz.zz)a) −→ (λx .y)aa −→ y

I Strategie paresseuse :(λx .y)((λz.zz)a) −→ y

Lien avec la syntaxe lisp

La syntaxe lisp est completement basee sur le λ-calcul. Les parentheses servent adelimiter les termes et les applications.

I Variables : x, et constantes de types numeriques, symbolique, fonctionnel etc.

I Abstractions fonctionnelles : λx .xy s’ecrit (lambda(x) (x y))

I Application : uv s’ecrit (u v)

I Cas d’une abstraction fonctionnelle : ((lambda(x) (x y)) a)I Cas d’une fonction nommee f (variable) ; fx s’ecrit ( f x)

ExempleI Application d’une abstraction fonctionnelle

I ((lambda (x) (x y)) a) −→ (a y)I ((lambda (z) (x z)) a) −→ (x a)I ((lambda (x y) (x z y)) a b) −→ (a z b)

I Application d’une fonction nommee

I Soit f la fonction (lambda (x) (x y))

(f a) = ((lambda (x) (x y)) a) −→ (a y)I Soit f la fonction (lambda (x) (+ x 1)), avec + correspondant a

l’operation d’addition :(f 2) = ((lambda (x) (+ x 1)) 2) −→ (+ 2 1) −→ 3

Syntaxe et evaluation lisp

I ((lambda (z) (x z)) a) −→ (a z) ou (x a) ou incorrect

I ((lambda (z) (x z)) a x) −→ (a z x) ou (x a x) ou incorrect

I ((lambda (x) (+ 3 x)) 10) −→ (+ 3 10) −→ 13 ou incorrect ou

(+ 10 3) −→ 13

I ((lambda (z) (lambda (x) (x z))) a) −→ (lambda (x) (x a)) ou

(lambda (z) (a z)) ou incorrect ou (a z)

I ((lambda (x y) (z y)) a b) −→ (a b) ou (z b) ou incorrect

Environnement de developpement

Boucle Read Eval Print : REPL

1. Read : Lecture d’une expression

2. Eval : calcul (reduction) de l’expression

3. Print : affichage du resultat (forme normale)

4. Affichage du prompt > et retour a 1

I Top-level : niveau de la REPL, l’imbrication des expressions induit plusieursniveaux. Par exemple pour l’expression (+ 3 4 (* 1 2) 3)−→ evaluation de (* 1 2)−→ resultat 3−→ evaluation de (+ 3 4 3 3)−→ resultat 13

I Notation

> (+ 3 4 ( ∗ 1 2) 3)3

Expressions

Expressions symboliquesOn appelle expressions symboliques (sexpr) les formes syntaxiquement correctes :

I Objet (nb, chaıne, symbole, etc.)

I Expression composee (sexpr sexpr ... sexpr) : liste de sexpr. Utilise a la fois pourle code et les donnees :

I Notation de l’application d’une fonction a ses arguments.I Notation des listesa : ’(e1 e2 ... en)

aPour eviter l’application et fabriquer une liste, il faut la faire preceder d’une quote

Evaluation

I Objets auto-evaluants : objet lui-meme (nombres, booleens, caracteres, chaınesde caracteres).

I Symboles : valeur associee (identificateurs)

I Expression symbolique composee : application – evaluation de l’objet enposition fonctionnelle (la premiere), evaluation les arguments, puis applicationde la fonction aux arguments et renvoie du resultat.

Expressions

Strategie d’evaluation

Cet algorithme d’evaluation correspond a la strategie applicative : lesarguments sont evalues en premier et c’est leur valeur qui est utiliseedans l’application.

Formes speciales

Il existe des operateurs speciaux pour lesquels les arguments ne sont pasevalues selon l’algorithme precedent. Chacun a sa propre regled’evaluation. Notamment les operateurs booleens et conditionnels : or,and, if, cond... Ces expressions sont appelees formes speciales. On ytrouve aussi en particulier, les expressions avec effets de bord :affectation, declarations, affichage.

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Resume des constructions syntaxiques du langage

Types

I Simples : Boolean, Number,Character, String, Symbol

I Conteneurs : Pair, List , Vector

I Fonctions : Procedure

Variables et liaisons

I Locales : let , let∗, letrec, letrec∗,let−values, let∗−values

I Globales ou locales : define

FormesExpression ou formes define, let , lambda,if , cond, set!, etc.

Expressions

constante, (f a1 a2 ... an)

Procedureslambda

Macrosdefine−syntax

Continuationscall-with-current-continuation

Bibliothequeslibrary, import, export

Les types

Les booleens

I Constantes : #t et #f

I Toute valeur differente de #f est vraie

I L’objet #t est utilise comme valeur vrai, quand aucune autre valeurne paraıt plus pertinente.

I Predicat boolean?

Operations booleennes

I and : stop au premier argument evalue a faux

I or : stop au premier argument evalue a vrai

I not

I nand, nor, xor, implies

Les operateurs and , or , nand , nor et xoradmettent n arguments, n ≥ 0.

Exemple

> ( and )#t> ( or )#f

Les types

Tour des types numeriques

I Number

I Complex

I Real

I Rational

I Integer

Exactitude

I Predicat : exact?

Les nombres

Les entiers

I Taille non limitee (seulement par la memoire)

I Predicat : integer ?

Exemple

> ( i n t e g e r ? 1)#t> ( i n t e g e r ? 2 . 3 )#f> ( i n t e g e r ? 4 . 0 )#t> ( e x a c t ? 4)#t

Les nombres

Les rationnels

I 523/123

I Accesseurs : numerator, denominator

I Predicats : rational?

Les reels

I 23.2e10

I Predicat : real ?

Exemple

> ( r e a l ? 1)#t> ( e x a c t ? 4 . 0 )#f

Les nombres

Les complexes

I 3+2i

I Contructeurs : make−polar, make−rectangular

I Accesseurs : real−part, imag−part, magnitude, angle

I Predicat : complex?

Exemple

> ( s q r t −1)0+1 i> ( complex? −1)#t> ( r e a l ? 1+2 i )#f

Predicats numeriques

I Nombres : zero?, positive ?, negative?

I Entiers : even?, odd?

I Comparaisons : = < <= > >= sur les reels.

I Egalites et inegalites sur les complexes.

I Nombre d’operandes superieur a 2.

Exemple

> (= 1 2 3)#f> (= 1 1 1)#t

Operations numeriques

Arithmetiques +, −, ∗, / n arguments reels, n ≥ 0

Unaires add1, sub1 incrementation, decrementation

max et min n arguments reels, n > 0

Exponentiation sqr, sqrt, logexp exponentielle naturelle

expt base arbitraire, exposant

Modulaires moduloquotient, remainderquotient/remainder renvoie 2 valeurs

gcd, lcm, abs

Arrondis floor , ceiling ,truncate, round

Trigonometrie sin, cos, tan,asin, acos, atan

Les caracteres et les chaınes de caracteres

Constantes

I Caractere : #\aI Chaıne : ”de caracteres ”

Predicats

I Type :char?, string?

I Comparaisons : char=?, char<?, char>?,string=?, string<?, string>?.

Fonctions

I Constructeurs : make−string, string

I Accesseurs : string−ref

I Longueur : string−length

I Conversion : number−>string, string−>number

Les symboles

ConstantesSuite de caracteres alphabetiques et numeriques plus les caracteressuivants :

! $ % & * + - . / : < = > ? ˜Identificateurs de variables et de fonctions, donnees symboliques.

Predicats

I Type : symbol?

I Egalite : eq?

Conversions

I symbol−>string, string−>symbol

Expressions booleenes et symboles

Quels sont est les resultats des expressions suivantes?

I (and 1 2) : #t ou #f ou 1 ou 2

I (and 2 #f) : #t ou #f ou 2

I (and 1 (/ 1 0)) : 1 ou Division by zero

I (or 1 (/ 1 0)) : 1 ou Division by zero

I (symbol? 1) : #t ou #f

Les expressions conditionnellesif

La forme if

( i f 〈condition〉 〈alors〉 〈sinon〉)

I 〈condition〉, 〈alors〉 et 〈sinon〉 sont des expressions

I Si 〈condition〉 vaut vrai, le resultat est la valeur de l’expression 〈alors〉I Sinon, le resultat est la valeur de l’expression 〈sinon〉

Exemple

> ( i f 1 2 3)2> ( i f (= 1 2) 3 4)4> ( i f (= 1 2) 3); e r r o r −> i f : m i s s i n g an ” e l s e ” e x p r e s s i o n

Utilisation de l’expression if

Quels sont les resultats des expressions suivantes?

1. (if (> 1 2) 3 4) : 3 ou 4

2. (+ (if (> 1 2) 3 4) 5) : 8 ou 9 ou Error

Les expressions conditionnelleswhen - unless

La forme when

(when 〈condition〉 〈e1〉 . . . 〈en〉)

Cette forme evalue les expressions 〈ei 〉 et renvoie le resultat de la dernierequand l’expression 〈condition〉 vaut vrai.

La forme unless

( un less 〈condition〉 〈e1〉 . . . 〈en〉)

Meme chose mais quand l’expression 〈condition〉 vaut faux.

Les expressions conditionnellescond

La forme cond

( cond 〈c1〉 . . . 〈cn〉)

I Les 〈ci 〉 sont des clauses : [〈condition〉 〈e1〉 ... 〈en〉 ]

I 〈condition〉, 〈e1〉, ... 〈en〉 sont des expressions

I Evaluation des conditions des clauses dans l’ordre de 〈c1〉 a 〈cn〉I Soit ci =[c e1 ... en] la premiere clause dont la condition c vaut vrai,

les ei sont evaluees dans l’ordre et le resultat est celui de en.

Exemple

( cond [ ( number ? x ) ”X e s t un nombre ” ][ ( symbol ? x ) ”X e s t un symbole ” ][ e l s e ( . . . ) ] )

Les crochets definissant les clauses peuvent etre remplaces par desparentheses, conformement a la norme R6RS du langage Scheme

Utilisation de l’expression cond

Quels sont les resultats des expressions suivantes?

I (cond [(= 1 2) 1] [(< 2 3) 2] [else 3]) : 1 ou 2 ou 3

I (cond [(= 1 2) 1] [#f 2] [else 3]) : 1 ou 2 ou 3

I (cond [(= 1 2) 1] [0 2] [else 3]) : 1 ou 2 ou 3

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Les definitions

L’environnement est forme de liaisons symbole −→ valeur . Les symboles ne sont pastypes (non declares), mais leurs valeurs le sont. Il s’agit d’un typage dynamique.

La forme define

I Variables : (define 〈v〉 〈e〉)

I Fonctions : (define (〈f 〉 〈p1〉 〈p2〉 ... 〈pn〉) 〈e1〉 〈e2〉 ... 〈en〉)

I Resultat non specifie par la norme

Une definition etablit une liaison entre une variable et un objet resultant del’evaluation de l’expression, cet objet pouvant etre une fonction.

Exemple

> ( d e f i n e a 0)> ( d e f i n e ( f x ) x )> ( d e f i n e g ( lambda ( x ) ( ∗ 2 x ) ) )

> a0> ( f 1)1

> ( g 1)

1 2 error

Definitions et evaluation

I Quelle est la forme correcte pour definir une fonction :

(define g(x) x) ou (define (f x) x)

I Quelle est la forme correcte pour appliquer une fonction : f(1) ou (f 1)

I Le symbole e dans cette definition est-il relie a une fonction ou bien a un

numerique ? (define e (* 2 4))

I Le symbole e dans cette definition est-il relie a une fonction ou bien a un

numerique ? (define (e) (* 2 4))

I Soient les definitions suivantes :

(define (f) 1)

(define (g x) (* 2 x))

Parmi les expressions suivantes lesquelles sont valides :

I (f 1) (f) (f 1 2)

I (g 1) (g) (g #t)

Definitions de variables locales

La forme let

( l e t (〈l1〉〈l2〉. . .〈ln〉)

〈e〉)

I 〈li 〉 est une liaison : (〈si 〉 〈oi 〉)I 〈si 〉 est un symbole (id. de variable)

I 〈oi 〉 une valeur d’initialisation

I 〈e〉 est une expression

I Resultat de l’evaluation de l’expression 〈e〉dans l’environnement cree

L’evaluation des valeurs d’initialisation est effectuee en premierpuis les variables locales sont creees. Ce qui implique que lesvaleurs des variables locales definies dans un let ne sont pasutilisees dans l’evaluation des expressions d’initialisation.

Definitions de variables locales

La forme let∗

( l e t ∗ (〈l1〉〈l2〉. . .〈ln〉)

〈e〉)

I 〈li 〉 est une liaison : (〈si 〉 〈oi 〉)I 〈si 〉 est un symbole (id. de variable)

I 〈oi 〉 une valeur d’initialisation

I 〈e〉 est une expression

I Resultat de l’evaluation de l’expression 〈e〉dans l’environnement cree

L’evaluation des expressions d’initialisation est effectuee apresla creation des variables locales.

Definitions de variables locales

Equivalence des formes Let et Lambda

La forme let est une forme fonctionnelle car elle equivaut a l’applicationd’une fonction construite avec la forme lambda.

(let ((j 0))

(* x j))((lambda(j) (* x j)) 0)

Question

La forme let∗ est-elle fonctionnelle? oui ou non

Differencier les expressions let et let*

Quels sont les resultats des expressions suivantes?

( def ine b 0)( l e t ( ( b 1)

( c 2 ) )(+ b c ) )

2 ou 3

( def ine b 0)( l e t ( ( b 1)

( c b ) )(+ c b ) )

1 ou 2

( def ine b 0)( l e t ∗ ( ( b 1)

( c b ) )(+ c b ) )

1 ou 2

Strategies de recherche d’une liaison

Probleme: L’occurrence d’un symbole peut correspondre a plusieurs liaisonsdans l’environnement. Laquelle faut-il choisir?

Exemples : Que vaut i lors du calcul de f(3)?

Parametre d’une fonction

int i=0;

int

f(int i)

{return i; 3 0

}

Variable locale a une fonction

int i=0;

int f(int x)

{int i=3;

return i*x; 3 0

}

Variable libre d’unefonction : non defini dansl’environnement local.

int i=0;

int

int f(int x)

{return i*x; 2 0

}

Appel a la fonction f

int g()

{int i=2;

return f(3);

}

Strategies de recherche d’une liaison

Pour chercher la liaison correspondant a l’occurrence d’un symbole dans uneexpression, la recherche commence par l’environnement dans lequel apparaıtl’expression. Si l’expression apparaıt dans le corps d’une fonction et qu’aucune liaisonne correspond (cas d’une variable libre), deux strategies existent.

Strategie lexicaleLa strategie lexicale consiste a remonter les environnements locaux englobants duplus proche jusqu’a l’environnement global.La premiere liaison dont le nom de symbole correspond est retenue. Cette strategies’applique aussi a l’evaluation du corps d’une fonction lors d’une application. En effet,celui-ci est evalue dans l’environnement englobant de la fonction, dit environnementlexical.Cette strategie correspond au langage C et aux langages imperatifs en general et aulangage Scheme.

Strategie dynamiquePour chercher la liaison correspondant a l’occurrence d’un symbole dans uneexpression situee dans le corps d’une fonction, la strategie dynamique consiste arechercher sa liaison dans l’environnement dynamique, c’est-a-dire l’environnementd’application de la fonction.Cette strategie correspond par exemple a LaTeX, et beaucoup de lisp dont emacs-lisp.Common-Lisp implemente les deux strategies.

Portees lexicales et dynamiques

Racket> (define i 0)

> (define (f x) (* x i))

> (f 3)

0

> (let ((i 2)) (f 3))

0

> (let ((j 0))

(let ((g (lambda(x)

(* x j))))

(let ((j 3))

(g 3))))

0

emacs-lisp(defvar i 0)

(defun f(x) (* x i))

(let ((i 2)) (f 3)) -> 6

(f 3) -> 0

emacs-lisp(let ((j 0))

(flet ((g (x)

(* x j)))

(let ((j 2))

(g 3)))) -> 6

Common Lisp(defvar i 0)

(defun f(x) (* x i))

(let ((i 2)) (f 3)) -> 6

(f 3) -> 0

(let ((j 0))

(flet ((g (x)

(* x j)))

(let ((j 2))

(g 3)))) -> 0

Portee dynamique en LaTeX

I Style book : saute 2 pages avant la table of contents

I Style report : saute 1 page avant la table of contents

I On souhaite ne sauter qu’une page dans le style book

I Commande cleardoublepage saute 2 pages

I Commande clearpage saute 1 page

I Commande renewcommand redefinit une commande

Exemple%% creation d’un bloc avec environnement local

\begingroup

\renewcommand{\cleardoublepage}{\clearpage}

\tableofcontents

\endgroup %% sortie du bloc,

\cleardoublepage %% cleardoublepage restauree

Portee et duree de vie en Scheme

Portee lexicaleLa portee d’une liaison est la partie du code source dans laquelle il estpossible de l’utiliser.

I Les liaisons globales ont une portee egale a tout le programme.

I Les liaisons locales ont une portee limitee a la forme de definitionlet.

Duree de vieLa duree de vie d’un objet correspond a la periode de l’execution d’unprogramme comprise entre la creation de cet objet et sa destruction.

I Les objets definis globalement ont une duree duree de vie egale acelle du programme.

I Les objets definis localement ont une duree de vie potentiellementegale a celle du programme.

Les environnements

I La strategie lexicale implique que la portee d’une variable peut etre

determinee lors de : la lecture ou l’execution du programme

I Scheme est un langage lexical ou dynamique

I Dans la definition de la fonction f, la variable a est dite :libre ou liee

I Le resultat de l’expression suivante est : 1 ou 0

( l e t ( ( a 1 ) )( f 0 ) )

Exemple

( def ine a 0)( def ine ( f n )

( i f ( z e r o ? n )a0 ) )

Portee et paradigme fonctionnel

La portee lexicale correspond-elle au paradigme fonctionnel?

I Quelles sont les caracteristiques de la programmation fonctionnelle?

I Typage dynamique

I Fondement provenant du λ-calcul

I Programmation par applications de fonctions

I Transparence referentielle

I Reformulation de la question

Portee et transparence referentielle

Les deux applications (f 3) sont effectuees dans deux environnements differents. Lepremier lie i avec 0 et le second lie i avec 2.

Portee lexicale : Scheme

Les resultats des deux applications sont-ils les memes? oui ou non

> (define i 0)

> (define (f x) (* x i))

> (f 3)

> (let ((i 2)) (f 3) )

Portee dynamique : emacs-lisp

Les resultats des deux applications sont-ils les memes? oui ou non

(defvar i 0)

(defun f(x) (* x i))

(let ((i 2)) (f 3) )

(f 3)

Portee : formulation fonctionnelle

MethodeOn utilise la formulation fonctionnelle du let pour etudier le phenomenede portee en calculant le resultat sur les exemples precedents..

(let ((j 0))

(let ((g (lambda(x)

(* x j))))

(let ((j 3))

(g 3))))

((lambda(j)

((lambda(g)

((lambda(j)

(g 3))

3))

(lambda(x) (* x j))))

0)

Portee dynamique – RMS Stallman

Some language designers believe that dynamic binding should be avoided,and explicit argument passing should be used instead. Imagine thatfunction A binds the variable FOO, and calls the function B, which callsthe function C, and C uses the value of FOO. Supposedly A should passthe value as an argument to B, which should pass it as an argument to C.

This cannot be done in an extensible system, however, because the authorof the system cannot know what all the parameters will be. Imagine thatthe functions A and C are part of a user extension, while B is part of thestandard system. The variable FOO does not exist in the standard system;it is part of the extension. To use explicit argument passing would requireadding a new argument to B, which means rewriting B and everythingthat calls B. In the most common case, B is the editor commanddispatcher loop, which is called from an awful number of places.

What’s worse, C must also be passed an additional argument. B doesn’trefer to C by name (C did not exist when B was written). It probablyfinds a pointer to C in the command dispatch table. This means that thesame call which sometimes calls C might equally well call any editorcommand definition. So all the editing commands must be rewritten toaccept and ignore the additional argument. By now, none of the originalsystem is left!

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Recursivite

Un exemple de specification

fact(0) = 1fact(n) = n ∗ fact(n − 1)

Programme Scheme recursif

( d e f i n e ( f a c t n )( i f ( z e r o ? n )

1( ∗ n ( f a c t ( sub1 n ) ) ) ) )

Recursivite

Evaluation

> ( f a c t 4)( ∗ 4 ( f a c t 3) )( ∗ 4 ( ∗ 3 ( f a c t 2) ) )( ∗ 4 ( ∗ 3 ( ∗ 2 ( f a c t 1) ) ) )( ∗ 4 ( ∗ 3 ( ∗ 2 ( ∗ 1 ( f a c t 0) ) ) )24

Une pile est necessaire pour stocker les valeurs successivesde n qui sont utilisees dans le calcul lors du retour des appelsrecursifs.

Recursivite terminale

Specification

fact-t(0, r) = rfact-t(n, r) = fact-t(n − 1, n ∗ r)

Programme Scheme recursif terminal

( d e f i n e ( f a c t− t n r )( i f ( z e r o ? n )

r( f a c t− t ( sub1 n ) ( ∗ n r ) ) ) )

Recursivite terminale

Evaluation

> ( f a c t− t 4 1)( f a c t− t 3 4)( f a c t− t 2 12)( f a c t− t 1 24)( f a c t− t 0 2 4 ) ) ) )24

Les valeurs successives de n sont utilisees dans les calculs quisont effectues avant les appels recursifs. Il est inutile de lesconserver dans une pile.

Les appels recursifs sont dits terminaux car aucun calcul n’est effectueapres leur retour.

Reconnaıtre des fonctions recursives terminales

Les fonctions suivantes sont-elles recursives terminales?

( d e f i n e ( sum1 n )( i f ( z e r o ? n )

0( add1 ( sum1 ( sub1 n ) ) ) ) )

OUI ou NON

( d e f i n e ( sum2 n r )( i f ( z e r o ? n )

r( sum2 ( sub1 n ) (+ n r ) ) ) )

OUI ou NON

( d e f i n e ( f n )( cond ( ( z e r o ? n ) 0)

( ( even ? n ) ( add1 ( f ( sub1 n ) ) ) )( e l s e ( f ( sub1 n ) ) ) ) )

OUI ou NON

Calculer par exemple : (sum1 3), (sum2 3) et (f 3)

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Les objets Scheme

Les objets

Les atomes

I Numeriques,

I Booleens,

I Symboles,

I Chaınes de caracteres

I Liste vide : ()

Les paires pointees

I Constructeur : cons

I Accesseurs : car, cdr(argument paire pointee uniquement)

I Predicats : pair?, cons?

I Abbreviation : cddr, caadr,..., cadddr, ..., list−ref

Forme quote et symboles

> ( quote P i e r r e )’ P i e r r e> ’ P i e r r e’ P i e r r e> ( d e f i n e a ’ P i e r r e )> a’ P i e r r e> P i e r r eP i e r r e : u n d e f i n e d ;> ’ ( d e f i n e a ’ P i e r r e )’ ( d e f i n e a ’ P i e r r e )

Exemple> ( cons 1 2)’ ( 1 . 2)> ( cons ( cons ( cons 1 2) 3) 4)

’ ( ( ( 1 . 2) . 3) . 4)> ( cons 1 ( cons 2 ( cons 3 4 ) ) )’ ( 1 2 3 . 4)> ( c a r ( cons 1 2 ) )1> ( c d r ( cons 3 ( cons 1 4 ) )’ ( 1 . 4)

Affichage des paires pointees

I (a . (pp)) −→ (a pp) si pp est une paire pointee.

I (a . ()) −→ (a)

Exemple

> ’ ( 1 . (2 3 ) )’ ( 1 2 3)> ( def ine f ’ ( def ine ( f x ) x ) )> f’ ( def ine ( f x ) x )> ( cons ’ ( 1 2) 3)’ ( ( 1 2) . 3)

Utilisation de cons, car et cdr

I Quel est le resultat de l’expression (cons 1 (cons (2 (cons 3 ’()))))?

I ’(1 2 3)

I ’(1 . (2 . (3 . ())))

I ’(1 . (2 . (3 . ’())))

I ’(1 2 . 3)

I ’(((1 . 2) . 3) . ())

I Soit l’expression (cons 1 (cons (2 (cons 3 ’())))). Quelle expressionpermet d’acceder a l’element 2?

I (car (cons 1 (cons 2 (cons 3 ’()))))

I (car (car (cons 1 (cons 2 (cons 3 ’()))))

I (car (cdr (cons 1 (cons 2 (cons 3 ’()))))

Les listes

Definition recursive des listes Scheme

I Liste vide : ’() ou null

I Une paire pointee dont le car est un element de la liste, et le cdr estune liste;

Autres types de structures

I Liste impropre : une liste qui ne se termine pas par la liste vide.

I Liste circulaire : une chaıne de cons sans fin;

Ces autres types de structures ne sont pas des listes

Definitions formelles

Atome

atome ::= number | symbol | string | ()

Paire pointee

paire-pointee ::= ( objet . objet )

Objet

objet ::= atome | paire-pointee

Liste

liste ::= () | liste

Liste impropre

liste-impropre ::= () | paire-pointee

Fonctions de base sur les listes

I Predicats list ?, empty? et null?

I Predicats d’egalite : eq?, equal?

I Fonction de construction : list , (voir aussi list ∗), make−list

I Fonctions predefinies : length, list−ref , list−tail , append,reverse, member, remove, first , ... tenth, nth, rest, last ,last−pair , take, drop, split−at , take−right, drop−right,split−at−right , flatten , remove∗, remove−duplicates, range,shuffle , permutations, remv, remq, memv, memq.

Exemple

> ( append ’ ( 1 (2 . 3 ) ) ’ ( 1 ) )’ ( 1 (2 . 3) 1)> ( append ’ ( ) ’ ( ) )’ ( )> ( append ’ ( 1 ) ’ ( ( ) 2 ) )’ ( 1 ( ) 2)

I Fonctions de a-listes : assq, assoc

Construction de listes

Soit les definitions suivantes

( def ine a 0)( def ine b 10)( def ine c 3)

Quels sont les resultats des expressions suivantes?

I (cons a (cons b (cons c ’()))) : (a b c) ou (0 10 3)

I (list a b c) : (a b c) ou (0 10 3)

I (list ’a b c) : (a b c) ou (0 10 3) ou (a 10 3) ou (0 b c)

I ’(a b c) : (a b c) ou (0 10 3)

I (make-list 3 a) : (a a a) ou (0 0 0)

Differencier cons, list et append

Quels sont les resultats des expressions suivantes?

I (cons 1 ’(a b)) : (1 (a b)) ou (1 a b) ou ((1) a b) ou Erreur

I (cons ’(a b) 1) : ((a b) 1) ou (a b 1) ou ((a b) . 1) ou Erreur

I (list 1 ’(a b)) : (1 (a b)) ou (1 a b) ou ((1) a b) ou Erreur

I (list ’(a b) 1) : ((a b) 1) ou (a b 1) ou ((a b) . 1) ou Erreur

I (append 1 ’(a b)) : (1 (a b)) ou (1 a b) ou ((1) a b) ou Erreur

I (append ’(a b) 1) : ((a b) 1) ou (a b 1) ou (a b . 1) ou Erreur

I (append ’(1) ’(a b)) : (1 (a b)) ou (1 a b) ou ((1) a b) ou Erreur

Programmation recursive sur les listes

Definition recursiveI Soit liste vide

I Soit une paire pointee dont le carest un element de la liste et le cdrla suite de la liste, soit la listeprivee de son premier element.

Specification recursive d’uncalcul

I Si la liste est vide, calculer leresultat correspondant.

I Sinon, exprimer le calcul enfonction de l’element courant etdu resultat d’un appel recursif surla liste privee de son premierelement.

Somme des elements d’une liste

I somme-liste(’()) = 0

I somme-liste(l) = car(l) +somme(cdr(l))

Exemple

( d e f i n e ( somme l )( i f ( empty ? l )

0(+ ( c a r l )

( somme ( c d r l ) ) ) ) )

Programmation recursive sur les arbres

Definition recursiveI Soit un atome

I Soit une paire pointee admettant pour car et pour cdr un objet lisp (unatome ou une paire pointee)

Specification recursive d’un calcul

I Si l’arbre est vide, calculer le resultat correspondant.

I Sinon, exprimer le calcul en fonction du fils gauche (le car), et du filsdroit (le cdr).

Exemple

( d e f i n e ( n b− f e u i l l e s a )( cond ( ( n u l l ? a ) 0)

( ( not ( p a i r ? a ) ) 1)( e l s e (+ ( n b− f e u i l l e s ( c a r a ) )

( n b− f e u i l l e s ( c d r a ) ) ) ) ) )

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Systeme de type

Classification des valeurs en ensembles appeles types de maniere agarantir la correction de certains programmes.

Base types

NumberBooleanStringChar

Symbol

ComplexRealFloat

Integer

Function types

Procedure

t −> t eq. a −> t t

Complex types

StructU (Union)

Polymorphic types

Pairof s tListof t

Vectorof t

Any

Styles de typage

Styles de typage

I le typage dynamique : determine pendant l’execution par le runtime, ilne necessite aucune intervention du programmeur;

I le typage statique : fixe avant l’execution par le compilateur, il est soitinfere automatiquement, soit indique par des annotations dans le code.

Racket definit en fait plusieurs langages :

I En Racket classique, le typage est dynamique;

I En Typed/Racket, le typage est dynamique mais autorise desannotations statiques verifiees par le compilateur.

Comment typer ?

Afin d’annoter une valeur 〈val〉 par un type 〈typ〉, il suffit d’ecrire avantla definition de 〈val〉 :

I (: 〈val〉 〈typ〉) Ex : (: int exm Integer )

Les types primitifs contiennent en particulier : Number, Integer , Float,Char, String, . . .

Les types des fonctions sont ecrits a l’aide d’une des syntaxes suivantes :

I (〈arg1〉 〈arg2〉 ... 〈argn〉 −> 〈res〉) Ex : (Number Number −> Boolean)

I (−> 〈arg1〉 〈arg2〉 ... 〈argn〉 〈res〉) Ex : (−> Number Number Boolean)

Exemple

#l a n g typed / r a c k e t ; ; Cho ice o f t h e l a n g u a g e( : num−fun ( Number −> Number ) ) ; ; Type a n n o t a t i o n o f num−fun( d e f i n e ( num−fun n ) ( add1 n ) ) ; ; D e f i n i t i o n o f num−fun( : p r i n t− t y p e num−fun ) ; ; (−> Number Number )

Interets du typage

I Detection d’erreurs de type : passer une valeur de type String a unefonction Int −> Int est incoherent.

Exemple

( : num−fun ( Number −> Number ) )( d e f i n e ( num−fun n ) ( add1 n ) )( num−fun ” abc ” ) ; ; −> Type Checker e r r o r : t y p e mismatch

I Compatibilites de type : passer une valeur de type Integer a une fonctionNumber −> Number est coherent car un Integer est aussi un Number.

Exemple

( : i n t g I n t e g e r ) ; ; Type a n n o t a t i o n o f i n t g( d e f i n e i n t g 3)( num−fun i n t g ) ; ; −> 4

I Optimisations : le compilateur peut ecrire du code dedie a des typesparticuliers (exemple : nombre flottants et instructions FPU).

Exemples

Exemple

( : g r e a t e r− t h a n ( Number Number −> Boolean ) )( d e f i n e ( g r e a t e r− t h a n x y )

(> x y ) ) ; ; Type e r r o r : Number cannot be compared

En effet, un Number peut aussi etre un Complex, donc non comparable.

Exemple

( : p l u s ( Number Number −> Number ) )( d e f i n e ( p l u s x y ) (+ x y ) )

( : g r e a t e r− t h a n ( Rea l Rea l −> Boolean ) )( d e f i n e ( g r e a t e r− t h a n x y ) (> x y ) )

( g r e a t e r− t h a n ( p l u s 3 4) 5); ; Type e r r o r : Number cannot be compared

En effet, plus renvoie un Number, qui potentiellement n’est pas un Real.

Remarque : en realite, le type de l’operateur + est generique.

Definir ses propres types

Le code suivant definit un Struct representant des points du plan :

( s t r u c t : p o i n t ( [ x : Rea l ] [ y : Rea l ] ) )

( : d i s t a n c e ( p o i n t p o i n t −> Rea l ) )( def ine ( d i s t a n c e p1 p2 )

( s q r t (+ ( sqr (− ( point−x p2 ) ( point−x p1 ) ) )( sqr (− ( point−y p2 ) ( point−y p1 ) ) ) ) ) )

Cette construction definit en meme temps les fonctions suivantes :

I Un constructeur point permettant de construire des instancescomme par exemple (point 3 4).

I Deux accesseurs point−x et point−y permettant d’acceder auxchamps de la structure.

Types inductifs : les listes

Definition recursive des listes en Scheme (Rappel)

I Soit la liste vide : null ou ’()

I Soit une paire (car ,cdr) ou car est un element de la liste et cdr estune liste.

La definition de type pour les listes en Racket :

; ; A L i s t i s e i t h e r a P a i r o r Empty( def ine− type ( L i s t a ) (U ( P a i r a ) Empty ) ); ; A P a i r i s a s t r u c t w i t h c a r and cdr , and Empty i s empty( s t r u c t : ( a ) P a i r ( [ c a r : a ] [ c d r : ( L i s t a ) ] ) )( s t r u c t : Empty ( ) )

Remarque : le type pour les listes est un type polymorphe.

( : a l i s t ( L i s t I n t e g e r ) )( d e f i n e a l i s t ( P a i r 1 ( P a i r 2 ( P a i r 3 ( Empty ) ) ) ) )

Reconnaissance de motif

La forme match

( match t[ 〈pat1〉 res1 ][ 〈pat2〉 res2 ]. . .[ 〈patn〉 resn ][ default ]

)

La reconnaissance de motif ou pattern-matching :

I compare l’expression t a chacun des motifs 〈patk〉I et renvoie le resultat associe au premier indice

pour lequel t correspond.

Les motifs peuvent introduire des liaisons utiliseesdans le resultat.

Exemple pour calculer la longueur d’une liste :

( d e f i n e ( l i s t− l e n g t h l )( match l

[ ( Empty ) 0 ] ; ; Match Empty s t r u c t[ ( P a i r x xs ) ; ; Match P a i r s t r u c t

( add1 ( l i s t− l e n g t h xs ) ) ] ; ; and b i n d s x and xs) )

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Fonctionnelles

Higher-order functions

I Fonction anonyme : forme lambda

I Fonctions en arguments

I Fonctions en retour

La forme lambda

( lambda (〈p1〉 〈p2〉 . . . 〈pn〉)〈e〉)

Exemple

> ( lambda ( x y )(/ (+ x y ) 2 ) )

#<p r o c e d u r e>> ( ( lambda ( x ) ( sub1 x ) ) 1)0

Fonctions en arguments

I Appartenance : (memf 〈proc〉 〈lst〉)I Filtrage : ( filter 〈pred〉 〈lst〉)I Liste d’associations : ( assoc 〈v〉 〈lst〉)

( assoc 〈v〉 〈lst〉 〈pred〉)( a s s f 〈proc〉 〈lst〉)

I Constructeur : ( build−list 〈n〉 〈proc〉)I Iteration sur des listes : apply, map, andmap, ormap, foldl , foldr

Exemple

> (map sub1 ’ ( 1 2 3 4 5 ) )’ ( 0 1 2 3 4)> (map cons ’ ( 1 2 3 4) ’ ( a b c d ) )’ ( ( 1 . a ) (2 . b ) (3 . c ) (4 . d ) )> (map ( lambda ( x ) ( l i s t ( add1 x ) ) ) ’ ( 1 2 3 ) )’ ( ( 2 ) ( 3 ) ( 4 ) )

Fonctionnement de la forme apply

Quels sont les resultats des expressions suivantes?

> ( apply ∗ ’ ( 1 2 3) ’ ( 1 2 ) ) 12 ou erreur

> ( apply ∗ 1 2 3 ’ ( 1 2 ) ) 12 ou erreur

> ( apply ∗ 1 2 3 1 2) 12 ou erreur

> ( apply ∗ 1 2 3 1 2 ’ ( ) ) 12 ou erreur

> ( apply and ’ ( \#t \#f \#t ) ) #f ou erreur

> ( apply map l i s t ’ ( ( 1 2 3) (2 3 4 ) ) ) ’((1 2) (2 3) (3 4))

ou ’((1 2 3) (2 3 4))

ou erreur

Exemple de fonction n-aire avec apply

La fonction ou n-aire

( def ine ( ou . l )( cond ( ( n u l l ? l ) #f )

( ( c a r l ) )( e l s e ( apply ou ( c d r l ) ) ) ) )

Questions

I (apply ou ’(#f #t)) : #t ou erreur

I (ou #f #t #f (print #f)) : #t ou #f#t ou #t#f

Fonctions en retour de fonctions

Operations de composition

I Fonctions unaires : (compose1 〈proc1〉 〈proc2〉 ... 〈procn〉)I Arite quelconque : (compose 〈proc1〉 〈proc2〉 ...〈procn〉)

Le nombre de resultats de 〈proci 〉 doit correspondre a l’arite de 〈proci−1〉

Exemple

> ( ( compose1 s q r t add1 ) 1) ; ( s q r t ( add1 1) )1.414213562> ( d e f i n e (2 r x y ) ( v a l u e s (+ x y ) (− x y ) ) )> ( ( compose l i s t 2 r ) 1 2) ; ( l i s t (2 r 1 2 ) )’ ( 3 −1)

Questions

I ((compose - sqr sub1) 3) : -4 ou 8

I ((compose + 2r) 1 2) : 2 ou 3

I ((compose (lambda(x) (apply * x)) (lambda(x) (map sub1 x))) ’(1 2 3)) :

0 ou erreur

Fonctions en retour de fonctions

Operations sur l’arite

I Arite d’une fonction : (procedure−arity 〈proc〉)I Reduction d’arite : (procedure−reduce−arity 〈proc〉 〈arity〉)I Currification : (curry 〈proc〉)

Exemple

> ( d e f i n e ++ ( ( c u r r y +) 1 ) )> (++ 1)2> ( ( c u r r y l i s t ) 1) 2)(1 2)> ( d e f i n e make−map ( c u r r y map) )> ( d e f i n e map−sub1−sqr ( compose (make−map sub1 )

(make−map sqr ) ) )> ( map−sub1−sqr ’ ( 1 2 3 4 5 ) )’ ( 0 3 8 15 24)

Exemple de curryfication

On va curryfier la fonction filter de la bibliotheque pour la specialiser surle predicat even?

> ( f i l t e r even ? ’ ( 1 2 3 4 ) )’ ( 2 4)> ( def ine f i l t e r− e v e n ( ( c u r r y f i l t e r ) even ? ) )> ( f i l t e r− e v e n ’ ( 1 2 3 4 ) )’ ( 2 4)

Cela peut permettre de l’utiliser dans une fonctionnelle de liste commemap par exemple.

Exemple

> (map f i l t e r− e v e n ’ ( ( 1 2 3 4) (3 6 2 4 23 1 ) ) )’ ( ( 2 4) (6 2 4 ) )

Fonctionnement de compose, map et apply

Quels sont les resultats des expressions suivantes?

> (map ( ( c u r r y cons ) 1) ’ ( a b c ) ) ’((1 . a) (1 . b) (1 . c))

’(1 a b c)

erreur

> ( ( ( c u r r y apply ) ∗ ) ’ ( 1 2 3 ) ) 6

’(1 2 3)

erreur

> ( ( ( c u r r y map) ∗ ) ’ ( 1 2 3 ) ) 6

’(1 2 3)

erreur

> ( ( compose ( ( c u r r y apply ) ∗ )( ( c u r r y map) sub1 ) )

’ ( 1 2 3 ) )

0

erreur

Programmation de fonctionnelles

Composition de fonctions

f : A −→ B

g : B −→ C

La composee de f par g est la fonction h : A −→ C telle que h(x) = g(f (x)).Elle est notee h = gof .

( d e f i n e ( o g f )( lambda ( x )

( g ( f x ) ) ) )

Exemple

> ( o sqr sub1 )#<p r o c e d u r e>> ( ( o c a r r e sub1 ) 2)1> ( def ine carre−1 ( o c a r r e sub1 ) )> ( carre−1 2)1

Ecriture de fonctionnelles

Quelle est la version la plus efficace?

I (define (carre-1 x) ((o sqr sub1) x))

I (define carre-1 (o sqr sub1))

FermeturesSoit la session suivante :

> ( def ine ( g x ) (+ x 1 0 ) ) )> ( def ine ( f x ) ( ∗ 2 x ) )> ( def ine ( c a r r e x ) ( ∗ x x ) )> ( def ine carre−1 ( o c a r r e sub1 ) )

Supposons que la fonction carre-1 soit representee par son code :

( lambda ( x ) ( g ( f x ) ) )

Quel est le resultat de l’expression suivante : 1 ou 14 ?

> ( carre−1 2)

Notion de fermeture (closure)

Definitions

I L’environnement lexical d’une fonction est l’environnement danslequel elle est definie.

I Une fermeture (closure en anglais) est la representation d’unefonction sous forme d’un couple associant l’environnement lexical etle code de la fonction.

I En Scheme les fonctions sont representees par des fermetures pourconserver leur environnement de definition contenant des referenceseventuelles (ce n’est pas le cas par exemple du langage emacs-lisp).

I Les fermetures peuvent etre utilisees pour representer des etats, parmodification de l’environnement (voir chapitre suivant).

Emacs-lisp

Emacs-lisp n’a pas de fermetures, les fonctions ne sont representees que parleur code (sans l’environnement lexical). Soient les fonctions :

( defun o ( g f ) ( lambda ( x ) ( f u n c a l l g ( f u n c a l l f x ) ) ) )( defun c a r r e ( x ) ( ∗ x x ) )

Lors de l’application :

( f u n c a l l ( o #’ c a r r e #’1−) 2)

On obtient :

Debugger entered−−Lisp e r r o r : ( v o i d− v a r i a b l e g )( f u n c a l l g ( f u n c a l l f x ) )( lambda ( x ) ( f u n c a l l g ( f u n c a l l f x ) ) ) ( 2 )f u n c a l l ( ( lambda ( x ) ( f u n c a l l g ( f u n c a l l f x ) ) ) 2)e v a l ( ( f u n c a l l ( o ( f u n c t i o n c a r r e ) ( f u n c t i o n 1−)) 2) n i l )

Programmation de fonctionnelles recursives

Premiere ebauche d’ecriture d’une fonction de composition d’une liste defonctions : ici, tout le calcul est gele par la λ-expression. Il s’executeraentierement au moment de l’application de la fonction resultat.

Exemple

( d e f i n e ( bad1 . l )( lambda ( x )

( i f ( n u l l ? l )x( ( c a r l ) ( ( apply bad1 ( c d r l ) ) x ) ) ) ) )

> ( d e f i n e add2 ( bad1 add1 add1 ) )( lambda ( x ) ; l e r e s u l t a t e s t l a l ambda−expres s ion

( i f ( n u l l ? ’ ( add1 add1 ) )x( add1 ( ( bad1 add1 ) x ) ) ) )

Deuxieme ebauche d’ecriture : bad2

On sort le if de la λ-expression afin qu’il s’execute lors de l’application dela fonctionnelle.

( def ine ( bad2 . l )( i f ( n u l l ? l )

i d e n t i t y( lambda ( x )

( ( c a r l ) ( ( apply bad2 ( c d r l ) ) x ) ) ) ) )

Application de bad2 :

> ( def ine add2 ( bad2 add1 add1 ) )

( i f ( n u l l ? ’ ( add1 add1 ) )i d e n t i t y( lambda ( x )

( add1 ( ( bad2 add1 ) x ) ) ) )

Etape suivante : λ ou if ou recursion ou forme normale

Application de bad2 (1)

(if (null? ’(add1 add1))

identity

(lambda(x)

(add1 ((bad2 add1) x))))

β−→

( lambda ( x )( add1 ( ( bad2 add1 ) x ) ) )

Etape suivante : λ ou if ou recursion ou forme normale

Solution recursive terminale

Pour etre sur de mettre l’appel recursif dans la fonctionnelle, il fautrendre celle-ci recursive terminale.

( def ine ( o f . l )( i f ( n u l l ? l )

f( apply o ( lambda ( x ) ( ( c a r l ) ( f x ) ) )

( c d r l ) ) ) )

Lors de l’application de la fonctionnelle o, tous les calculs s’effectuent,sauf ceux qui necessitent de connaıtre l’argument de la fonction resultat.

Conclusion

Regles d’ecriture

I L’appel recursif doit etre effectue par la fonctionnelle plutot que parla fonction resultat. De cette facon, on effectue la boucle une seulefois au moment de la construction, sinon, la boucle est effectuee achaque application de la fonction resultat.

I Pour ne pas geler l’appel recursif de la fonctionnelle, il faut qu’il soitexterieur a toute fermeture (λ-expression), ce qui implique deconstuire les fermetures en arguments plutot qu’en valeurs de retourd’appels recursifs, et donc de rendre les fonctionnelles recursivesterminales.

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Formes imperatives

References

Une reference est un objet correspondant a une adressememoire et dont l’indirection est faite automatiquement danstoute situation ou une valeur est requise. L’adresse associee aune reference n’est pas directement manipulable en tant quetelle (il n’existe pas d’operations pour le programmeur sur lesreferences)

I Un symbole est lie a une reference, correspondant a un atome ouune paire pointee.

I L’evaluation d’un symbole renvoie une reference vers sa valeur.

I La reference est utilisee partout ou la valeur n’est pas requise.

I On trouve des references dans d’autres langages : Java, C++.

Passage d’arguments

Soit f une fonction, soient p1, p2, ... pn ses parametres formels. Soitl’application :

(f a1 a2 ... an)

Soient r1, r2, ..., rn les references vers les resultats des evaluationsrespectives des arguments a1, a2, ..., an.Lors de l’application, un environnement local est construit. Il estconstitue des liaisons entre les parametres formels pi de la fonction f etles references ri des arguments de l’application.

((p1 . r1)(p2 . r2)...(pn . rn))

Les references r1, r2, ..., rn sont utilisees comme des valeurs a travers lessymboles p1, p2, ..., pn, les indirections etant effectueesautomatiquement. Ainsi, il est impossible de modifier un parametre pi,car la modification reste locale a cet environnement.

L’affectation

La forme set!

(set! 〈id〉 〈e〉)

I La reference associee a l’identificateur 〈id〉 est remplacee par lareference du resultat de l’evaluation de l’expression 〈e〉.

I La valeur de retour de l’affectation est la valeur # < void > que lafonction read n’affiche pas. La procedure void rend ce memeresultat en prenant un nombre quelconque d’arguments.

Modification de paires pointees

On ne peut pas modifier les paires pointees de base dans la normescheme. En Racket, il faut utiliser le paquetage mpair

Exemple

> ( d e f i n e mp ( mcons 1 2 ) )> ( set−mcar ! mp 2)> mp( mcons 2 2)

Modification de parametres

On se donne la session suivante.

( def ine ( i n c r e m e n t e r x )( set ! x ( add1 x ) ) )

> ( i n c r e m e n t e r 2)> ( def ine i 0)> ( i n c r e m e n t e r i )

Quel est le resultat de cette expression? 0 ou 1

> i

Blocs d’expressions

Si x est plus petit que y, on veut echanger x et y et renvoyer x, sinon, on

veut renvoyer y. Cette expression est-elle correcte? oui non

( l e t ( ( tmp 0 ) )( i f (< x y )

( set ! tmp x )( set ! x y )( set ! y tmp )xy ) )

Blocs d’expressions

Certaines expressions pouvant effectuer des effets de bord, il devientpossible de les mettre en sequence. Certaines formes, telles le ifnecessitent d’utiliser une forme speciale de mise en sequence.

La forme begin

(begin e1 e2 ... en)

I Chaque expression ei est evaluee selon son ordre d’apparition.

I Le resultat de l’evaluation de la sequence est celui de la derniere.

I Les valeurs des evaluations des expressions precedentes sontperdues.

I Il existe une forme begin0 qui renvoie le resultat de la premiereexpression de la sequence.

Fermetures et affectations : en Common Lisp

On peut utiliser les fermetures pour modeliser des etats.

Generateurs en Common Lisp

( l e t ( ( i 0 ) )( defun g e n−e n t i e r ( )

( s e t f i (1+ i ) ) ) )

Exemple

∗ ( g e n−e n t i e r )1∗ ( g e n−e n t i e r )2∗ ( g e n−e n t i e r )3

Fermetures et affectations : et en Scheme?

I Quel est le resultat de la session suivante? 1 ou Erreur

( l e t ( ( x 1 ) )( def ine ( f )

x )( f ) )

1> ( f )

I Quel est le resultat de la session suivante? 1 ou 0 ou erreur

( def ine ( make−f )( l e t ( ( x 1 ) )

( lambda ( ) x ) ) )> ( def ine e ( make−f ) )> ( def ine x 0)> ( e )

Fermetures et affectations : generateurs en Scheme

Exemple

( def ine ( make−int−gen n )( l e t ( ( i n ) )

( lambda ( )( set ! i ( add1 i ) )i ) ) )

> ( def ine int−gen0 ( make−int−gen −1))> ( int−gen0 )0> ( int−gen0 )1> ( int−gen0 )2

Les memo-fonctions (memo functions, memoization)

La technique des memo-fonctions est utilisee pour optimiser le calcul desfonctions, en memorisant des resultats d’appels couteux.

Suite de Fibonacci

( d e f i n e ( make−memo−fib ) ; C r e a t i o n de l a f e r m e t u r e; I n i t i a l i s a t i o n de l a t a b l e dans l ’ e n v i r o n n e m e n t l e x i c a l( l e t ( ( memo−table ’ ( ( 1 . 1) (2 . 1 ) ) ) )

( d e f i n e ( memo−fib n ) ; d e f i n i t i o n de l a f o n c t i o n; Recherche dans l a t a b l e( l e t ( ( computed−value ( a s s o c n memo−table ) ) )

( i f computed−value( c d r computed−value ) ; l a v a l e u r e s t t r o u v e e; ; La v a l e u r e s t c a l c u l e e e t s t o c k e e( l e t ( ( new−value (+ ( memo−fib ( sub1 n ) ) ; c a l c u l

( memo−fib (− n 2 ) ) ) ) )( s e t ! memo−table ; s t o c k a g e

( cons ( cons n new−value )memo−table ) )

new−value ) ) ) ) ; r e t o u r de l a v a l e u rmemo−fib ) ) ; r e t o u r de l a f o n c t i o n

Les memo-fonctions : utilisation

Comme pour les generateurs, il faut creer la fermeture par une premiereapplication de la fonctionnelle.

Exemple

> ( def ine memo−fib ( make−memo−fib ) )> ( memo−fib 5)5> ( memo−fib 8)21> ( memo−fib 100)354224848179261915075

Portee et transparence referentielle

Les deux applications (f 3) sont effectuees dans deux environnements differents. Lepremier lie i avec 0 et le second lie i avec 2.

Portee lexicale : Scheme

Les resultats des deux applications sont-ils les memes? oui ou non

> (define i 0)

> (define (f x) (* x i))

> (f 3)

> (let ((i 2)) (f 3) )

Portee dynamique : emacs-lisp

Les resultats des deux applications sont-ils les memes? oui ou non

(defvar i 0)

(defun f(x) (* x i))

(let ((i 2)) (f 3) )

(f 3)

Portee et transparence referentielle

Les deux applications (f 3) sont effectuees dans deux environnements differents. Lepremier lie i avec 0 et le second lie i avec 2.

Portee lexicale : SchemeLes resultats des deux applications sont les memes : transparence referentielle.

> (define i 0)

> (define (f x) (* x i))

> (f 3) -> 0

> (let ((i 2)) (f 3) ) -> 0

Portee dynamique : emacs-lispLes resultats dependent de l’environnement : pas de transparence referentielle.

(defvar i 0)

(defun f(x) (* x i))

(let ((i 2)) (f 3) ) -> 6

(f 3) -> 0

Portee : formulation fonctionnelle

MethodeOn utilise la formulation fonctionnelle du let pour etudier le phenomenede portee en calculant le resultat sur les exemples precedents..

(let ((j 0))

(let ((g (lambda(x)

(* x j))))

(let ((j 3))

(g 3))))

((lambda(j)

((lambda(g)

((lambda(j)

(g 3))

3))

(lambda(x) (* x j))))

0)

Portee : formulation fonctionnelle

((lambda(j)

((lambda(g)

((lambda(j)

(g 3))

3))

(lambda(x) (* x j))))

0)

->

((lambda(g)

((lambda(j)

(g 3))

3))

(lambda(x) (* x 0)))

Portee : formulation fonctionnelle

((lambda(g)

((lambda(j)

(g 3))

3))

(lambda(x) (* x 0)))

->

((lambda(j)

((lambda(x) (* x 0)) 3))

3)

Portee : formulation fonctionnelle

((lambda(j)

((lambda(x) (* x 0)) 3))

3)

->

((lambda(x) (* x 0)) 3)

Portee : formulation fonctionnelle

((lambda(x) (* x 0)) 3)

->

(* 3 0)

->

0

Plan

Objectifs pedagogiques

Introduction

Types et constructions de base du langage

Environnements

Recursivite

Les listes

Types

Les fonctionnelles

Les formes imperatives

Les macroexpansions

Macroexpansions

Definition

( define−syntax−rule 〈pattern〉 〈template〉)

I 〈pattern〉 : (〈nom〉-〈macro〉 〈p1〉 ...)

I 〈pi 〉 : variables de la macro

I Remplacement des variables dans le template

I Le resultat est une forme

I Evaluation de la forme dans l’environnement d’appel

Macroexpansions

Exemple

( def ine−syntax− ru le ( i f n o t t e s t then e l s e )( i f ( not t e s t )

thene l s e ) )

> ( d e f i n e x 1)> ( expand−once # ’( i f n o t (= 1 2) 0 x ) )#<s y n t a x : 8 : 1 7 ( i f ( not (= 1 2 ) ) 0 x)>> ( syntax−>datum ( expand−once # ’( i f n o t (= 1 2) 0 x ) ) )’ ( i f ( not (= 1 2 ) ) 0 x )> ( i f n o t (= 1 2) 0 x )0

Macroexpansions

Citation

I Quote : ’

I Backquote : ‘

I Virgule : ,

I Arobase : @

Exemple

> ( def ine l ’ ( 1 2 3 ) )> ‘ ( 1 , l )(1 (1 2 3 ) )> ‘(+ , l )(+ 1 2 3)