INFO421 : Programmation fonctionnelle

Ce wiki est un complément de cours pour le cours « info-421 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir ce guide pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

Détails techniques

Compléments de cours, TD et TP

Installer Ocaml

Si vous voulez installer OCaml sur votre ordinateur :

• Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets ocaml, ocaml-core, ocaml-mode, tuareg-mode et emacs.
• Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour ocaml, emacs et tuareg-mode.el.
• Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : Installation de OCaml (sur Windows XP). Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

Pour les exemples simples, vous pouvez aussi utiliser OCaml en ligne

Références supplémentaires

• Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : Développement d'applications avec Ocaml. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)
• La documentation de Caml, version 3.09 (utilisé en TP) : Documentation and user's manual.
• Le livre de Jason Hickey Introduction to Objective Caml (en anglais).

---

Introduction

Pour paraphraser un collègue dont je ne retrouve pas le nom :

Attention : il ne s'agit pas d'un cours de programmation fonctionelle

Il s'agit plutôt d'un cours de programmation fonctionnelle...

Petit historique censuré

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après ce site, qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

• années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à porter. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
• FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
• LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
• ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
• Pascal (1975).
• C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
• Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
• ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
• Smalltalk (fin des année 1983), début de la programmation objet.
• 1983 : ADA.
• année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé

à l'INRIA. (Dernière version en octobre 2012.)

• années '90 : Python (version 1.0 en 1994).
• années '90 : PHP (version 1.0 en 1995).
• années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : Computer Languages Timeline (ou découpé en pages A4).

Fonctionnel ??

L'adjectif fonctionnel a au moins deux sens :

1. qui fonctionne, en état de marche,
2. qui se rapporte aux fonctions.

=

Les langages fonctionnels sont bien entendus fonctionnels dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d'impératifs.

Un des slogans de la programmation fonctionnelle en général est

Les fonctions sont des valeurs comme les autres

et c'est de là que vient la terminologie... En particulier, il n'y a pas de différence entre les instructions (qui ont un effet) et les expressions (qui ont une valeur). Par exemple, en Python,

x = x+1

ou

if delta < 0:
    print("Il n'y a pas de solution")

sont des instructions : on ne peut pas les mettre dans une variable.

Comme nous le verront, cela a des conséquences sur l'expressivité du langage et la manière de programmer.

Le langage (O)Caml

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel strict (nous verrons ce que cela veut dire), statiquement typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

• fonctionnel bien sûr,
• mais aussi impératif,
• objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons principalement le style fonctionnel, et un peu le style impératif en fin de semestre.

Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

• fonctions comme valeurs,
• types de données algébriques
• polymorphisme,
• système d'exceptions,
• support pour des références et des données mutables (programmation « impure »),
• système de modules et de foncteurs,
• ...

La notion de récursivité sera fondamentale pendant toute la durée du cours...

Un aspect intéressant du langage est que c'est :

• un langage interprété (avec l'interpréteur OCaml),
• soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
• soit un langage compilé optimisé en binaire (dépendant de l'architecture).

Autres langages fonctionnels

Il existe de nombreux autres langages fonctionnels. Par exemple :

• SML (Standard ML) : Wikipedia, autre dialecte de la famille ML.
• LISP, dont les deux dialectes principaux sont :
  • Common LISP : Wikipedia,
  • Scheme : Wikipedia.
• Haskell : Wikipedia (inspiré en grande partie de Miranda).

Plusieurs langages impératifs intègrent maintenant des aspects propres des langages fonctionnels : Python, Scala, ...

Applications concrètes

Voici quelques exemples de logiciels développés en OCaml :

• Ocsigen, un serveur web,
• Unison, un logiciel de synchronisation de fichiers entre ordinateurs,
• MLDonkey, un logiciel de Peer-to-peer multiréseaux,
• Active DVI un visualisateur pour le format de fichier DVI,
• analyse de programmes critiques : Astrée,
• informatique financiere : Janestreet Capital et Lexifi.

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang (Wikipedia), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

Objectifs du cours

1. être capable de définir des fonctions récursives, et comprendre ce qu'elles font
2. comprendre le typage, les types algébriques et le polymorphisme à la ML
3. pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
4. être capable de décomposer un problème
5. commencer à réfléchir à la complexité de vos programmes