Langages Fonctionnels paresseux

Miranda
LML
Haskell

4.1 Langages Fonctionnels paresseux

4.1.1 Miranda

Miranda ([Tur85]) est un langage fonctionnel pur. C'est à dire sans effet de bord. Un programme Miranda est une suite d'équations définissant les fonctions et les structures de données. Par exemple la fonction fib se définit ainsi :

fib a = 1, a=0
      = 1, a=1
      = fib(a-1) + fib(a-2), a>1

La sélection des équations se fait soit par des gardes (expressions conditionnelles) comme ci dessus, soit par un filtrage de motif comme l'exemple suivant :

fib 0 = 1
fib 1 = 1
fib a = fib(a-1)+ fib(a-1)

Ces deux méthodes peuvent se mélanger.

Les fonctions sont d'ordre supérieur et peuvent être évaluées partiellement. L'évaluation est paresseuse. Aucune sous-expression n'est calculée jusqu'au moment où sa valeur est nécessaire pour le calcul.

Miranda a une syntaxe concise pour structures infinies (listes, ensembles) : [1..] représente la liste de tous les entiers. La liste des valeurs de la fonction de Fibonacci s'écrit brièvement : fibs = [a | (a,b) <- (1,1),(b,a+b)..]. Comme les valeurs ne sont calculées que pour leur utilisation, la déclaration de fibs ne coûte rien.

Il est fortement typé en utilisant un système de type à la Hindley-Milner. Sa discipline de type est essentiellement la même que ML. Il accepte la définition de données par l'utilisateur.

Miranda est le représentant des langages fonctionnels purs paresseux.

4.1.2 LML

LML, pour Lazy ML, est comme son nom l'indique un langage fonctionnel pur, paresseux, polymorphe et fortement typé. Les principales différences avec ML sont la paresse et l'absence d'effets de bord. La description complète du langage est donnée dans la thèse d'Augustsson ([Aug87]), pour sa sémantique formelle, et dans son manuel d'utilisation ([AJ87]).

4.1.3 Haskell

Haskell ([HW90]) est défini dans le rapport ([HW90]). Les premières implantations datent de 1991. C'est un langage qui reprend presque tous les nouveaux concepts des langages fonctionnels. C'est un langage fonctionnel pur (sans effets de bord), paresseux (non-strict), muni d'un polymorphisme ad hoc en plus du polymorphisme paramétrique à la ML.

Polymorphisme ad hoc

Ce système est différent de celui vu précédemment (ML, Miranda). En ML une fonction polymorphe ne regarde pas ses arguments polymorphes. Elle peut construire des objets les contenant mais à aucun moment elle ne fait de supposition sur le type de ces arguments. Le traitement est identique pour tous les types. En Haskell c'est le contraire. Une fonction polymorphe peut avoir un comportement différent selon le type de ses arguments polymorphes. Cela autorise la surcharge de fonctions.

L'idée de base est de définir des types de classes qui regroupent des ensembles de fonctions surchargées. Une déclaration de classe définit une nouvelle classe et les opérateurs que celle-ci autorise. Une déclaration d'instance (d'une classe) indique qu'un certain type est une instance d'une classe. Cela inclue la définition des opérateurs surchargé de sa classe pour ce type.

Par exemple la classe Num a la déclaration suivante :

classe Num a where
  (+)    :: a -> a -> a
  negate :: a -> a

contraire. Une fonction polymorphe peut avoir un comportement différent selon le type de ses arguments polymorphes. Cela autorise la surcharge de fonctions.

L'idée de base est de définir des types de classes qui regroupent des ensembles de fonctions surchargées. Une déclaration de classe définit une nouvelle classe et les opérateurs que celle-ci autorise. Une déclaration d'instance (d'une classe) indique qu'un certain type est une instance d'une classe. Cela inclue la définition des opérateurs surchargé de sa classe pour ce type.

Par exemple la classe Num a la déclaration suivante :

classe Num a where
  (+)    :: a -> a -> a
  negate :: a -> a

On peut maintenant déclarer une instance Int de la classe Num de cette manière :

instance Num Int where
  x + y    =  addInt x y
  negate x = negateInt x

Et l'instance Float

instance Num Float where
  x + y    =  addFloat x y
  negate x = negateFloat x

L'application de negate Num aura un comportement différent si l'argument est de l'instance Int ou Float.

L'autre intérêt des classes provient de l'héritage entre classes. La classe descendante récupère les fonctions déclarées par son ancêtre. Ses instances peuvent en modifier le comportement.

Autres caractéristiques

Les principales autres caractéristiques du langage Haskell sont les suivantes :

un système d'entrées/sorties purement fonctionnel intégrant les deux styles suivants : les streams paresseuses ou les continuations;
les tableaux sont aussi construits paresseusement;
les vues qui permettent différentes représentations d'un même type de données.

En fait il contient à peu près tous les nouveaux traits issus de la recherche auxquels peut prétendre un langage fonctionnel. C'est son avantage et son inconvénient.