[PDF] Programmation Applicative et Récursive

View - Download Programmation Applicative et Récursive

Previous PDF

Next PDF

Universite Montpellier-II

UFR des Sciences - Departement Informatique

Licence Informatique - 2ieme annee

Programmation Applicative et Recursive

Notes de cours - 2007-2012

Christophe Dony1

2

Table des matieres

1 Introduction.5

1.1 Denitions

5

1.2 Lectures associees

11

2 Syntaxe des expressions. Types predenis. Bases de l'interpretation des expression.

13

2.1 Syntaxe de Scheme

13

2.2 Premieres phrases

14

3 Identicateurs, Fonctions, Premieres Structures de contr^ole.

19

3.1 Lambda-calcul

19

3.2 Identicateurs

19

3.3 Denition de fonctions

20

3.4 Premieres Structures de contr^ole

22

3.5 Fonctions de base sur les types predenis

23

3.6 Blocs, evaluations en liaison lexicale

24

4 Fonctions Recursives.29

4.1 Denitions

29

4.2 Iteration et recursion

30

4.3 Exemples de fonction recursives

30

4.4 Autres exemples : Calcul des termes de suites recurrentes

31

4.5 Interpretation d'un appel recursif

33

4.6 Decouverte d'une solution recursive a des problemes

34

4.7 Recursivite terminale et non terminale

34

4.8 Recursivite croisee

34

4.9 Exemples : dessins de gures fractales

35

5 Listes, Symboles, calcul Symbolique.

37

5.1 Types structures

37
3

5.2 Listes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.3 Symboles et Calcul

38

5.4 Calcul symbolique, Guillemets, Citations

39

6 Recursivite suite, Fonctions recursives sur les listes et arbres, Recursions arborescentes.

43

6.1 Fonctions recursives sur les listes

43

6.2 Recursivite enveloppee sur les listes : schema 1

44

6.3 Recursivite enveloppee - schema 2

45

6.4 Recursivite arborescente

46

7 Optimisation des fonctions recursives.

51

7.1 Rappels sur iterations

51

7.2 Equivalence iteration - recursions terminales

51

7.3 Transformation des recursions enveloppees simples

52

7.4 Recursion vers iteration, le cas des listes

55

7.5 Autres ameliorations de fonctions recursives

56

7.6 Transformation des recursions arborescentes, l'exemple de \b"

57

8 Abstraction de donnees, Arbres binaires, Dictionnaires

59

8.1 Abstraction de donnees

59

8.2 Denition de nouveaux types abstraits

59

8.3 L'exemple des Arbres binaires

61

8.4 L'exemple des Dictionnaires

62

9 Sequences et Eets de bord en programmation recursive.

65

9.1 Denitions

65

10 Fonctions recursives et Interpretation des programmes

69

10.1 Recursivite et Interpretation des programmes

69
4

Chapitre 1

Introduction.

Ceci est le premier d'une serie de 10 cours de 1h30 sur la programmation applicative et recursive, donnes en

licence seconde annee dans le contexte global de l'initiation a la programmation.

1.1 Denitions

Programmation Applicative

Programmation a veclaqu elleun texte de programme est un ensem bled ed enitiond efonctions et o u l'execution d'un programme est une succession, d'applicationde fonctions a des arguments au sens

algebrique du terme (calcul utilisant des operations, des lettres et des nombres) et selon la semantique

operatoire de l'application duLamba-Calcul;

programmation utilisan tp otentiellement(mais sans obligation) des v ariablesm utables(par opp osition a

la programmation fonctionnelle), programmation o utoute instruction est une expression (don tl ecalcul a u nev aleur).

Programmation recursive: programmation utilisant des fonctions recursives i.e. s'appelant elles-m^emes.

Une fonction recursive est appropriee pour implanter un algorithme pour tout probleme auquel peut s'appliquer

une resolution par recurrence, ou pour parcourir et traiter des stuctures de donnees elles-m^emes recursives telles

que les listes et les arbres. 5 Figure(1.1) {\Web site tree - une representation graphique du code HTML des pages WEB" - journal \Liberation", 23 janvier 2008

|Lisp,Scheme: Langages historiquement majeurs, a la syntaxe simple, a fort pouvoir d'expression, dedies

plus speciquement a la programmation applicative.

|Lisp, 1960, John Mc Carthy : \lists processing"pour du calcul numerique classique mais aussi symbolique,

calcul dont les donnees ne sont pas uniquement des nombres mais aussi des symboles et des collections de

symboles.

|Scheme, 1970, Gerald J. Sussman et Guy L. Steele : Heritier de LISP a liaison strictement lexicale :

enseignement de la programmation. \Structure and Interpretation of Computer Programs - Abselson, Fano, Sussman - MIT Press - 1984". bases, pr ealable al' etuded'autres for malismes,don tle formalisme ob jetplus large. CaracteristiquesdeLispet des langages applicatifs :

T outephrase syn taxiquementc orrectedu langage (y compris une instruction) est une expression alg ebrique

ayant une valeur calculable 1 2 . La m emoireest allou eeet r ecupereeautomatiquemen t si on le souhaite, programmation sans Eets de bords, lien avec la programmation dite \fonctionnelle pure" - Voir langage Haskell).

De nom breusesabstractions simplien tla v iedu programmeur. Exemple : les grands nom bres,les it erateurs,

etc.1(fact30)2= 2652528598121910586363084800000003(mapfact '(2 3 4 30))4= (2 6 24 265252859812191058636308480000000)1. M^eme une expression realisant un eet de bord (voir cours no 9).

2. Ceci n'est pas vrai dans les langages dits "imperatifs".

6 Figure(1.2) {Les langages de programmation - Vision Historique - extrait1 - http ://www.digibarn.com/collections/posters/tongues/tongues.jpg 7 Figure(1.3) {Les langages de programmation - Vision Historique - extrait 2- http ://www.digibarn.com/collections/posters/tongues/tongues.jpg 8 Figure(1.4) {Vision Historique et Thematique - extrait de :http://www.ctm.info.ucl.ac.be, \Concepts, Techniques, and Models of Computer Programming", P. Van Roy et S. Haridi. Langage Universel. Tous secteurs d'applications ouverts. 9 Figure(1.5) {Image Fractale dessinee par un programme Scheme - Girault Georoy - TER L2 2008

Contenu du cours :

Syn taxe.

T ypespr edenis,T ypage,Base de l'in terpretationdes expressions. Iden ticateurs,F onctions,Premi eresStructures de con tr^ole.

Blo cs,En vironnements,Liaisons.

F onctionsR ecursives.

T ypesstructur es- Listes

Listes et Sym boles: Calcul Sym bolique

F onctionsr ecursivessur les listes.

Arbres, R ecursionsarb orescentes.

Optimisation des fonction sr ecursives.R ecursionterminales, en veloppees. T echniquesde d erecursivation,transformations, me moization,con tinuations.

Abstraction de donn ees.Encapsulation.

In troduction al'in terpretationdes langages, ev alcomme exemple de f onctionr ecursive. 10

Un bloc est un espace de nommage. Il est possible d'utiliser sans ambiguite le m^eme identicateur dans des

blocs dierents.1(definex 12)2(define(carrex ) (xx ))3(define(cubex ) (xx x ))3.6.4 Cha^nage des environnements

Environnement ls: Un environnement E2 peut ^etre chaine a un environnement E1, on dit que E2 etends

E1, (on dit aussi que E2 est ls de E1). E2 herite alors de toutes les liaisons de E1 et y ajoute les siennes propres

(avec possibilite de masquage). La facon dont les environnements sont cha^nes denit la portee des identicateurs.

3.6.5 Portee lexicale

Le cha^nage est dit statique ou lexical quand un environnement d'un bloc est cree comme le ls de l'environne-

ment du bloc englobant lexicalement (inclusion textuelle entre zones de texte).

La portee des identicateurs est alors lexicale, i.e. un identicateur est deni dans toutes les regions de pro-

gramme englobee par le bloc ou se trouve l'instruction realisant la liaison. Scheme obeit a ce modele (voir exemples) ainsi que la pluspart des langages.

3.6.6 Portee dynamique

Le cha^nage entre environnements est dynamique, et la portee des identicateurs egalement, quand l'environ-

nement associe a une fonction devient, a chaque execution, le ls de celui associe a la fonction appelante.

La portee dynamique a presque disparue ...

3.6.7 Environnement lie a la boucle toplevel

Environnement global de scheme: environnement dans lequel sont denis tous les identicateurs lies

aux fonctions predenies. Tout autre environnement est indirectement (fermeture transitive) le ls, de cet

environnement global.

Environnement initial: environnement aecte a la boucle toplevel i.e. dans lequel sont interpretees les

expressions entrees au toplevel. Cet environnement est un ls de l'environnement global. Tout bloc denit \au

toplevel" cree un environnement ls de cet environnement initial. NB : les fonctions denies dans l'editeur sont conceptuellement denies au toplevel.

3.6.8 exemples

Variable denie ou indenie1>(definex 22);;liaison de x a22 dans l 'env.c ourant2>(+x1);;une expr essionE

quotesdbs_dbs18.pdfusesText_24

[PDF] algorithme pharma laval PDF Cours,Exercices ,Examens

[PDF] algorithme piece de monnaie PDF Cours,Exercices ,Examens

[PDF] algorithme plus court chemin graphe PDF Cours,Exercices ,Examens

[PDF] algorithme point sur une courbe 2nde Mathématiques

[PDF] algorithme polynome second degré ti 82 PDF Cours,Exercices ,Examens

[PDF] Algorithme pour calculer les taux d'évolution 1ère Mathématiques

[PDF] Algorithme pour calculer une distance de sécuité 2nde Mathématiques

[PDF] Algorithme pour conjecturer une limite 1ère Mathématiques

[PDF] Algorithme pour déterminer le minimum d'une fonction polynome 2nde Mathématiques

[PDF] Algorithme pour deux suites Un et Sn TS Terminale Mathématiques

[PDF] algorithme pour Gamy, Compostelle ou Chut 4ème Mathématiques

[PDF] algorithme pour i allant de 1 ? n PDF Cours,Exercices ,Examens

[PDF] algorithme pour les nuls PDF Cours,Exercices ,Examens

[PDF] algorithme pour prouver qu'un quadrilatère=losange 2nde Mathématiques

[PDF] algorithme pour tester la colinéarité de deux vecteurs PDF Cours,Exercices ,Examens