Algorithmique et Programmation Fonctionnelle

en L1-Math (avec Scheme). Printemps 2014

Voir Programmation fonctionnelle

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

DERNIER CC-FLASH EN TD ou TP LA SEMAINE DU 6 MAI : 40 minutes, aucun document : ordre supérieur (map, apply, filter, andmap, etc), arbres binaires, système de particules utilisant l'ordre supérieur. Entraînez-vous sur les pages FLASH et CC-FLASH...

Le langage utilisé dans ce cours est Scheme [avec le logiciel gratuit Racket]. Il fonctionne à l'identique sous Linux, MacOS-X et Windows. Pour installer chez soi la dernière version, consulter la rubrique Installation (VERSION 5.3.6 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 de mon livre PCPS paru en 2010 :

Un cours en amphi de 1h30 le lundi matin + deux séances de TD/TP de 1h30 chaque semaine, durant 12 semaines. Voici un document sur l'usage d'un Mac pour le travail en salles 312-313 le cas échéant. En ce qui concerne les salles du PV au 2ème étage, les étudiants peuvent maintenant sauvegarder leur espace de travail sur les machines Windows (avec mot de passe bien entendu). Cet espace de travail est commun aux 2ème et 3ème étage (Linux, Mac, Windows).

Contrôle des connaissances : 4 contrôles continus en TP/TD (60% de la note), et un examen final en amphi (40% de la note). 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é).
• 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 L1, nous n'utilisons pas le vrai langage Scheme, mais un sous-ensemble simplifié du langage (Etudiant Avancé) destiné à l'enseignement, et utilisé dans la première partie du livre de cours.
• LISEZ (ET COMPRENEZ) ENTIEREMENT LES DOCUMENTS récurrence.pdf, complexité.pdf, animation.pdf et match.pdf.
• Regardez cette vidéo que j'ai montée (musique de Parov Stelar) à partir d'un exemple (techniquement un système de particules) que m'a envoyé un étudiant en Scheme du semestre 1.
Le MOOC Programmation Récursive de l'Université Pierre et Marie Curie (Paris 6) introduit la programmation par récurrence sur les nombres, les listes et les arbres, jusqu'à la structure d'un évaluateur simplifié du langage Scheme. Il augmentera vos connaissances et vous préparera aux cours utilisant Scheme en 2ème et 3ème années ! Attention, le Scheme utilisé n'est pas Racket, voici un document mooc.pdf sur les différences. L'examen du MOOC peut être passé vers le 20 mai sur machine en salles 212-213.

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

Valentin ne m'en voudra pas d'avoir modifié le vortex de son animation et d'avoir rajouté à la vidéo une musique de Bill Laswell (Nothing, 1997). Envoyez un peu la sono et prenez patience si l'image est noire un certain temps... S'il y a un problème audio, essayez le navigateur Chrome :-) Quant à moi, j'ai joué avec la fonction scene+curve sur les images (sur une musique de Györgi Ligeti) :

 

Une option Programmation Fonctionnelle 2 [PF2, alias Programmation Scheme Avancée] est ouverte en L2-Informatique au semestre 3. Elle est destinée aux futurs programmeurs, aux futurs ingénieurs, et à tous les scientifiques souhaitant ajouter une coloration informatique à leurs études [ceci concerne par exemple l'option D (Informatique) à l'agrégation de Maths, puisque l'informatique devient une spécialité de Terminale S enseignée par les profs de maths à partir de la rentrée 2012]. L'option avancée PF2 abordera [en vrai Scheme pro] la programmation impérative, 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 de Programmation pour comprendre le fonctionnement d'un langage de programmation et les diverses stratégies mises en oeuvre par celui qui construit un langage.

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]