Algorithmique et Programmation Fonctionnelle

en L1-Info (avec Scheme). Printemps 2017

Le cours est terminé !

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 le printemps ? Il s'agit de livecoding par Andrew Sorensen, qui génère de la musique en introduisant du code Scheme à la volée...
Masako Wakamiya, une japonaise de 81 ans apprend à programmer et vient de créer un jeu sur iPhone ! Sur le même site, je suis sorti un peu découragé : au lieu de programmer une animation, filmons comme les japonais des jouets-robots programmables... Ce sera pour votre génération, même si l'Europe a un certain retard (aux USA, l'excellent cours 6.01 du MIT mélange Python et robots).
• Attention, ces animations-là sont réservées aux pros :-)
• En prenant exemple sur piano-tones.rkt de John Clements, auteur de Rsound, j'ai bricolé un saxo-tones.zip. Si vous voulez essayer le saxo, sonorité chaude...
• Certains étudiants aimeraient faire tourner deux ou trois animations en même temps. C'est en principe impossible en niveau Etudiant avancé, mais possible en full racket avec les threads. Voici un exemple minimal, parfaitement hors-programme, dans threads.rkt...
• Bon plan : une bande de copains qui montent une belle application, et se font racheter (et embaucher) par un GROS...
Time for Experiment : EvanXMertz (auteur d'un bon livre sur l'audio en Java et Processing) imite des morceaux rythmiques à succès et vous en donne les éléments...

• 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.
• 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 forgeant qu'on devient forgeron, en lisant on reste un liseron...
• Lisez peu à peu les trois documents suivants : animation.pdf, recurrence.pdf et complexite.pdf. Ces documents semblent inconnus à beaucoup d'étudiants.
• Le cc1 a eu lieu, les corrigés sont dans cc1-cor.zip.
Tutorat par Pierre Lafortune du vendredi 10 mars au 14 avril, de 16h45 à 18h15, en salle PV201.
• Le cc2 a eu lieu, les corrigés sont dans cc2-cor.zip.
• L'examen terminal a eu lieu (notes de 0 à 20). J'espère que vous vous étiez bien entraînés sur les derniers sujets d'examen corrigés dans exams-old.zip. Il est IMPERATIF d'avoir résolu cet examen si vous passez des rattrapages en programmation !
• Pour la session de rattrapage, seule la note d'examen comptera. Même programme, les contenus des 12 semaines.
• Si vous avez apprécié la programmation fonctionnelle et souhaitez vous préparer au mieux au cours Paradigmes de L3-Info, je vous suggère de vous inscrire au MOOC Programming Languages de Grossman, qui débute le 26 juin (seul le certificat final est payant si vous le souhaitez). En plus de Racket, vous y apprendrez des rudiments de ML et Ruby au passage, un très bon investissement.

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 minimum 6.6) 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. Une petite introduction à la musique sur ordinateur sera introduite juste après les listes, histoire de souffler un peu (dans la trompette).

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

L'Académie des Sciences de Groland voulait savoir si les fourmis préféraient la confiture d'oranges ou celle de fraises. Facile, même pas besoin d'IA, juste le cc1 du groupe 2 avec les fourmis de Francis, bref une bonne simulation avec Racket, and the winner is : la FRAISE ! Le code source est dans cc1-gr2.rkt. Le montage audio-vidéo des animations ci-dessous a été réalisé avec l'excellent logiciel  payant Screenflow  gratuit iMovie.

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  Cours4  TP4  sol3.zip  <---
5. Programmation par Récurrence  Cours5  TP5  sol4.rkt  <---
6. Données Composées : les Listes (anims)  Cours6  TP6  sol5.rkt  <---
7. Compléments sur les Listes  Cours7  TP7  sol6.rkt  <---
☀ Intro. à l'Audio Numérique (INSTALL  Cours-Audio   TP-Audio   sol7.zip  <---
8. Récurrence et Calculs Itératifs  Cours8  TP8  sol-audio.zip  <---
9. L'Abstraction et l'Ordre Supérieur  Cours9  TP9  sol8.rkt  <---
10. Arbres Binaires d'Expressions  Cours10  TP10  sol9.rkt  <---
11. Révisions  Cours11  TD11  sol10.rkt

Suite à la demande de plusieurs étudiants sur le problème des collisions, voici une petite animation montrant comment les gérer, avec gravitation et frottements (cf dernier TD Python, en plus élaboré). Le source est dans collisions.zip (avec ou sans la sonorisation).

Une petite animation très simple jouant sur la transparence et un effet 3D, d'après un étudiant de l'année 2015 (salut Valentin, alors le Canada et l'IA c'est bien ? Si tu vois cette page, fais-moi signe...).

Deborah (2012) avait eu l'idée cette petite animation (que j'ai sonorisée). Pour déclencher des actions à des moments données, elle utilise une timeline en intégrant le nombre de ticks dans le monde. Vous y entendrez les voix de John Kennedy et de Neil Armstrong...

Mohamed Amine (2017) qui se passionne pour le style math-art, a codé l'animation de cette belle fractale ! A partir du 13 mars vous pourrez sonoriser vous-même vos animations. En attendant, j'ai opté pour Fractal Zoom de Brian Eno...

Et une petite animation personnelle en guise d'au revoir puisqu'il s'agissait de mon dernier cours en cette année 2016-2017 ! Mettez la sono...

Une option PF2 [alias Programmation Fonctionnelle Avancée] sera peut-être 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 !].

Vous trouverez sur Youtube certains projets PF2 (L2-Info) des années précédentes...

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]