La programmation : une approche fonctionnelle et
récursive avec Scheme
Table des matières
Cours et exercices
1 Un premier contact
1 La syntaxe de Scheme
2 L'évaluation des expressions
3 La définition des variables
4 L'évaluation d'un symbole
5 L'application des fonctions
6 Des précisions au travers d'exemples
6.1 L'application pas à pas
6.2 Retour sur la définition et l'évaluation des variables
7 Quelques fonctions prédéfinies
7.1 Des fonctions élémentaires
7.2 Les fonctions conditionnelles
7.3 Définition et utilisation de variables temporaires
Exercices
2 Premières structures
1 Les paires pointées
2 Les listes
Exercices
3 La récursivité
1 Introduction à la récursivité
2 Un exemple géométrique
3 La récursivité sur les listes
4 Comment vérifier une fonction récursive ?
4.1 La vérification syntaxique
4.2 La vérification statique
4.3 Vérification de la terminaison
4.4 La vérification sémantique
Exercices
4 Variations sur les listes
1 Les listes d'associations
2 Des listes ordonnées
2.1 Listes de nombres ordonnées
2.2 Listes de couples ordonnés
3 Les parcours récursifs en profondeur
4 Des fonctions qui rendent plusieurs résultats
4.1 Des symboles et des nombres
4.2 Retour sur le nombre de points d'intersection
Exercices
5 Abstraction des données
1 Qu'est-ce-que l'abstraction des données ?
2 Des ensembles
2.1 Les primitives
2.2 Union de deux ensembles
2.3 Ensemble des parties d'un ensemble
3 Des multi-ensembles
3.1 Les primitives
3.2 Union de deux multi-ensembles
Exercices
6 Les arbres
1 Vocabulaire, structure et primitives
2 Les parcours d'arbres
3 Modification et création d'arbres
4 Les arbres ordonnés
Exercices
7 Programmation d'ordre supérieur
1 Des fonctions en arguments
1.1 Un exemple
1.2 Généralisation
1.3 La fonction map
2 L'abstraction des parcours de listes
3 L'abstraction des parcours d'arbres
4 Des fonctions comme résultats
4.1 Un premier exemple
4.2 Allons plus loin
4.3 Vers une évaluation minimale
4.4 Simulation d'une exécution parallèle
Exercices
8 L'envers du décor
1 L'affectation
2 Les environnements
3 Les fermetures
3.1 L'évaluation des lambda-expressions
3.2 Indépendance et partage
4 A l'intérieur de Scheme
4.1 Représentation des paires pointées
4.2 Modifications des paires pointées
5 Cellules et égalité
Exercices
Quelques applications
9 Un exemple concret d'arbres
1 Les arbres d'Huffman
1.1 Un peu de théorie de l'information : les codes
1.2 L'algorithme de codage d'Huffman
2 Une implantation des arbres d'Huffman
2.1 Les primitives
2.2 Codage
2.3 Décodage
2.4 Génération de l'arbre
2.5 Remarque
10 Réalisation d'un système expert
1 Définitions et exemple
2 Le moteur du système
3 Implantations de moteurs en chaînage arrière
3.1 Un moteur naif
3.2 Un moteur plus performant
11 Un système de calcul formel
1 Introduction
2 Une représentation des expressions
3 Vers une forme canonique
4 Premières simplifications
5 Les polynômes
6 Simplifications spécifiques
7 Simplification globale
8 Dérivation
9 Remarques diverses et compléments
Annexes
A Corrections des exercices
1 Un premier contact
2 Premières structures
3 Programmation récursive
4 Variations sur les listes
5 Abstraction
6 Les Arbres
7 Programmation d'ordre supérieur
8 L'envers du décor
B Corrections des applications
1 Les arbres d'Huffman
2 Un système expert
3 Un système de calcul formel
C Comment obtenir Scheme ?
Bibliographie
Index