Algorithmique et Programmation Fonctionnelle

en L1-Math/Info (avec Scheme). Automne 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]

PAS DE COURS NI TD-TP LA SEMAINE DU 10 NOVEMBRE.
Le cc2 aura lieu le mardi 25 novembre (listes : récurrences, itérations, ordre supérieur, systèmes de particules).

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é.
Entraînez-vous au fur et à mesure sur la page FLASH pour les cc-flash à venir. Ne vous contentez pas de lire les solutions, l'important c'est de franchir les obstacles...
• Vous êtes invités à étudier de près les trois documents récurrence.pdf, complexité.pdf et animation.pdf qui seront supposés assimilés pour le prochain contrôle-flash (semaine du cours 10).
• Le LIVRE DE COURS PCPS [qui vous servira aussi peut-être 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.
• A partir de maintenant, envoyez des animations dont le monde est une liste (voir animations.pdf ci-dessus). Une telle animation se nomme un système de particules (voir un exemple de l'an passé au bas de cette page).
• Voici une correction du cc1. A première vue, certains manquent un peu d'entraînement personnel, mais ça viendra (enfin, on l'espère). La moyenne est de 10.7/20 et les notes vont de 2/20 à 17.5/20.
• TELECHARGEZ UNE NOUVELLE VERSION DU TEACHPACK VALROSE.RKT ! Il y avait un petit problème avec ma redéfinition de la structure posn qui entrait en conflit avec le module image de Racket.

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 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 de mon livre PCPS paru en 2010 :

Un cours en amphi (1h30), un TD (1h30) et un TP sur machine (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, nous travaillerons HELAS encore sous Windows-XP et oui, je sais, nous sommes bien en 2014 :-(

1. Expressions Préfixées  Cours1  TP1  Install
2. Programmer avec des Fonctions  Cours2  TP2  sol1.rkt
3. Programmation d'Images Fixes  Cours3  TP3  sol2.rkt
4. Animations (exemple du fil tendu)  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. L'Abstraction et l'Ordre Supérieur  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  Cours12  TP12  sol11.rkt

• Pour l'audio et la vidéo, le navigateur Chrome semble le plus adéquat.
• J'avais dit en TD que je me régalais avec la saison 1 d'une série du siècle dernier Sliders dont le thème tourne autour des univers parallèles et des trous de ver dans l'espace-temps réalisant des ponts d'Einstein-Podolsky-Rosen souvent cité dans les épisodes de la série :-)

Un système de particules par Valentin (L1-Info 2013). J'ai rajouté à son animation une musique de Bill Laswell (Nothing, 1997). Zoomez, envoyez un peu la sono, et prenez patience si l'image reste noire un certain temps, c'est voulu... 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 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]