Algorithmique et Programmation Fonctionnelle

en L1-Info (avec Scheme). Printemps 2013

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

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 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...

• Contrôle des connaissances : 4 contrôles continus SANS DOCUMENT en TP/TD (60% de la note), et un examen final en amphi SANS DOCUMENT (40% de la note). Un travail régulier est attendu.
• Ce cours ne suppose pas connu le cours Python. Les techniques utilisées ne sont pas les mêmes. Ne transposez pas à Scheme vos connaissances de Python, ce sont deux langages distincts. L'état d'esprit sera différent, plus proche de la pensée mathématique pure (hors de question d'écrire x=x+1, quasiment toutes les fonctions ont un résultat, raisonnement exclusivement par récurrence, etc).
• Le livre de cours PCPS 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, nous n'utilisons pas le vrai langage Scheme, mais un sous-ensemble simplifié du langage (Etudiant Avancé) destiné à l'enseignement, et utilisé dans le livre de cours.
• Entraînez-vous au fur et à mesure sur la page FLASH pour les cc-flash. Consultez les corrections des cc-flash.
• Voici deux anciens sujets d'examens terminaux pour vous préparer...
• AUCUN DOCUMENT A L'EXAMEN. Le sujet comportera un aide-mémoire sur les principales fonctions de Racket, dont vous êtes censés maîtriser l'utilisation et la complexité.

1. Expressions Préfixées
2. Programmer avec des Fonctions
3. Images Statiques
4. Animations
5. Programmation par Récurrence
6. Données Composées : les Listes
7. Compléments sur les Listes
8. Récurrence et Calculs Itératifs
9. Faire Abstraction
10. Arbres Binaires d'Expressions
11. Introduction au Calcul Formel
12. Révisions

Une option Programmation Fonctionnelle 2 [PF2, alias Programmation Scheme Avancée] sera ouverte 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 à partir de la rentrée 2012]. L'option PF2 abordera [en vrai Scheme] la programmation impérative, les macros, les objets, les interfaces graphiques, la programmation du Web, et bien d'autres choses plaisantes, intellectuelles et fort agréables...

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]