Algorithmique et Programmation Fonctionnelle

en L1-Info (avec Scheme). Printemps 2016

Page obsolète. Prochain cours au Printemps 2017...

Voir Programmation fonctionnelle

The spirit of Lisp hacking can be expressed in two sentences :
Programming should be fun.
Programs should be beautiful.
[Paul Graham]

AU FIL DU TEMPS...
• Navigateur Web conseillé : Chrome (notamment pour l'audio et la vidéo).
• Un petit morceau de musique pour fêter la fin de l'année (en Scheme par Andrew Sorensen) ? Vous pouvez vous entraîner à la sonorisation de vos animations en lisant sonorisation.pdf.

• Un travail régulier est attendu. Si vous avez déjà programmé (par exemple en Python), tâchez d'avoir en Scheme un esprit de débutant, c'est très zen :-) Ce cours ne suppose en effet aucune connaissance préalable de programmation. Ne transposez pas à Scheme vos connaissances Python (ou alors seulement les principes algorithmiques purs que vous avez assimilés, comme la dichotomie ou la décomposition en sous-problèmes), l'état d'esprit sera assez différent, beaucoup plus proche de la pensée mathématique usuelle (hors de question d'écrire x=x+1, quasiment toutes les fonctions ont un résultat, raisonnement exclusivement par récurrence, pas de mots-clé while ou for inutiles, etc). Nous allons étudier la programmation fonctionnelle, qui est assez puriste.
• Le LIVRE DE COURS PCPS [qui vous servira aussi en L2 et L3] existe pour que vous puissiez aller plus vite et efficacement dans votre apprentissage du langage Scheme et de la programmation en général. Tous ses exercices sont corrigés sur ma page Web. Attention : dans ce cours de 1ère année, nous n'utilisons pas le vrai langage Scheme, mais un sous-ensemble simplifié du langage (Etudiant Avancé) destiné à l'enseignement en L1, et utilisé dans la première partie du livre de cours (la seconde partie du livre concerne L2 et L3).
AUCUN DOCUMENT AUTORISE en cc-flash et à l'examen, à l'exception de ce formulaire.pdf sur les principales fonctions de Racket, dont vous êtes censés maîtriser l'utilisation et la complexité. Il vous sera distribué lors de l'examen.
• Vous pouvez commencer à étudier les petits documents animation.pdf, récurrence.pdf et complexité.pdf...
• Entraînez-vous à fond sur les exercices corrigés de la page FLASH. Mais ne regardez pas (trop vite) les solutions, RESOLVEZ CES EXERCICES. C'est en faisant qu'on devient faiseron, en lisant on reste un liseron...

Le langage utilisé dans ce cours est Scheme [avec le logiciel gratuit Racket]. Il fonctionne à l'identique sous Linux, MacOS et Windows. Pour installer chez soi la dernière version, consulter la rubrique Installation (VERSION 6.x uniquement) ainsi que le document teackpack.pdf pour les réglages. La distribution de Racket contient une volumineuse doc en anglais, mais comme avec Python, nous n'en étudierons qu'une très petite portion, grosso modo les chapitres 1, 2, 3, 4, 5, 6, 8, 9, et 10.2 du livre PCPS paru en 2010 :

Un cours en amphi (1h30), un TD (1h30) et un TP sur machine (1h30) chaque semaine, durant 12 semaines.

1. Expressions Préfixées  Cours1 (4p)  TP1  INSTALL
2. Programmer avec des Fonctions  Cours2 (4p)  TP2  sol1.rkt
3. Programmation d'Images Fixes  Cours3 (4p)  TP3  sol2.rkt
4. Animations  Cours4 (4p)  TP4  sol3.rkt
5. Programmation par Récurrence  Cours5 (4p)  TP5  sol4.rkt
6. Données Composées : les Listes  Cours6 (4p)  TP6  sol5.rkt
7. Compléments sur les Listes (stuff)  Cours7 (4p)  TP7  sol6.rkt
8. Récurrence et Calculs Itératifs  Cours8 (4p)  TP8  sol7.rkt
9. L'Abstraction et l'Ordre Supérieur  Cours9 (4p)  TP9  sol8.rkt
10. Arbres Binaires d'Expressions  Cours10 (4p)  TP10  sol9.rkt
11. Introduction au Calcul Formel  Cours11 (4p)  TP11  sol10.rkt
12. Révisions  Cours12  TP12  sol11.rkt

A gauche et au milieu, un système de particules type (le monde diminue dans le premier). A droite l'image finale d'une animation où je m'amusais à faire pousser des cheveux sur un ballon bleu, histoire de faire un système de particules un jour où il pleut... Lorsque le monde est une liste (cours 6), on parle d'un système de particules. Mettez la sono (l'audio de la vidéo à gauche est programmée en Scheme dans l'animation avec la librairie rsound de Racket, et pour celle du robinet j'ai rajouté le son avec un logiciel de montage vidéo. Si vous avez des outils pour sonoriser une capture d'écran vidéo, pourquoi pas (au format MP4 uniquement svp...) ?

   

Une option PF2 [alias Programmation Fonctionnelle Avancée] est ouverte en L2-Informatique et L2-Math au semestre 3. Elle est destinée aux futurs programmeurs, aux futurs ingénieurs, et plus largement à tous les scientifiques souhaitant ajouter une coloration informatique à leurs études [de plus l'informatique devient une spécialité de Terminale S enseignée par les profs de maths depuis la rentrée 2012]. L'option avancée PF2 abordera [en vrai Scheme] les mutations, les macros, les objets, les interfaces graphiques, la musique électronique, la programmation du Web, et bien d'autres choses plaisantes, intellectuelles et agréables... En L3-Informatique, Racket est utilisé dans le cours Paradigmes et Interprétation de Julien Provillard pour comprendre le fonctionnement d'un langage de programmation et les diverses stratégies mises en oeuvre par celui qui construit le langage [on a l'habitude de dire que Racket est un langage de programmation programmable !].

Les langages de programmation ne devraient pas être conçus en empilant des tonnes de choses, mais en supprimant les faiblesses et les restrictions qui rendent toutes ces choses indispensables. Scheme démontre qu'un très petit nombre de règles pour former les expressions, sans aucune restriction sur la manière dont elles sont composées, suffit à former un langage de programmation pratique et efficace, qui soit suffisamment flexible pour accepter la plupart des paradigmes majeurs de programmation utilisés de nos jours. [R6RS]

By relieving the brain of all unnecessary work, a good notation
sets it free to concentrate on more advanced problems.
[Alfred North Whitehead]