Langages fonctionnels proches

Langages fonctionnels proches

Il existe plusieurs langages proches d'Objective CAML, soit par le côté fonctionnel, soit par le typage. Objective CAML est issu de la famille ML, et possède donc des cousins dont les plus proches sont outre-atlantique et outre-manche dans la lignée de SML (Standard ML). La famille Lisp, et en particulier le langage Scheme, diffère de ML principalement par son typage dynamique. Deux langages paresseux, Miranda et Haskell, reprennent ou étendent le typage de ML dans le cadre de l'évaluation retardée. Deux langages fonctionnels Erlang et SCOL développés respectivement par les sociétés Ericsson et Cryo-Networks sont tournés vers la communication.

Famille ML

La famille ML comprend deux branches principales : Caml (Categorical Abstract Machine Language) et ses dérivés Caml-Light et Objective CAML, SML (Standard ML) et ses descendants SML/NJ et mossml. Caml, l'ancêtre, a été développé entre 1986 et 1990 par le projet FORMEL de l'INRIA en collaboration avec l'Université Paris 7 et l'École Normale Supérieure. Son implantation reposait sur la bibliothèque d'exécution de Le_Lisp. Il intégrait dans le langage la définition de grammaires et d'afficheurs ce qui permet la communication de valeurs entre le langage décrit et Caml. Son système de types était plus contraignant pour les valeurs physiquement modifiables en ce qu'il n'autorisait pas que de telles valeurs fussent polymorphes. Son premier descendant, Caml-Light, n'utilisait plus la machine CAM, mais la Zinc pour l'implantation. Le nom a néanmoins été conservé pour montrer sa filiation. Il a apporté une implantation plus légère en optimisant l'allocation des fermetures et utilisait un GC performant précurseur du GC actuel. Cet allégement permettait de l'utiliser sur les micros-ordinateurs de l'époque. Les différentes versions de Caml-Light ont évolué vers le typage actuel des traits impératifs et se sont enrichies de nombreuses bibliothèques. Le rejeton suivant, Caml Special Light ou CSL, a introduit les modules paramétrés et le compilateur natif. Enfin le benjamin est actuellement Objective CAML qui ajoute principalement l'extension objet à CSL. Comme il n'y a jamais eu de spécification complète du langage Caml, ces différentes évolutions ont pu s'effectuer en toute liberté.

L'approche SML a été inverse. La spécification formelle [MTH90] a été donnée avant la première implantation. Elle est difficile à lire, et un deuxième livre en donne un commentaire ([MT91]). Cette démarche, spécification puis implantation, a permis la réalisation de plusieurs implantations, dont la plus connue est SML/NJ (Standard ML of New Jersey) de Lucent (ex-ATT). Dès l'origine, SML a intégré des modules paramétrés. Son système de typage initial était différent de celui de Caml pour les traits impératifs en introduisant un niveau de faiblesse sur les variables de type. Les différences entre les deux langages sont détaillées dans [CKL96]. Ces différences s'estompent avec le temps. Les deux familles ont le même système de type pour le noyau fonctionnel et impératif, Objective CAML possède maintenant des modules paramétrés. SML a aussi subi des évolutions, le rapprochant d'Objective CAML comme pour les types enregistrements. Si les deux langages ne fusionnent pas, cela provient principalement de leur développement séparé. Il est à noter qu'il existe un environnement de développement commercial pour SML, MLWorks, de chez Harlequin :

Lien

http://www.harlequin.com/products/

Une implantation de SML, mossml, reposant sur la bibliothèque d'exécution de Caml-Light a aussi été implantée.

Scheme

Le langage Scheme (1975) est un dialecte du langage Lisp (1960). Il est normalisé (IEEE Std 1178-1990). C'est un langage fonctionnel à évaluation stricte, muni de traits impératifs, typé dynamiquement. Sa syntaxe est régulière et particulière par l'usage des parenthèses. La structure de donnée principale est la paire pointée (équivalent du couple ML) avec laquelle on construit des listes possiblement hétérogènes. La boucle principale d'une boucle d'interaction Scheme s'écrit (print (eval (read))). La fonction read lit l'entrée standard et construit une expression Scheme. La fonction eval évalue l'expression construite et la fonction print affiche le résultat. Scheme possède un système de macro-expansion très pratique qui, associé à la fonction eval, permet de construire facilement des extensions du langage. Il permet non seulement d'effectuer des ruptures de calcul (exceptions) mais aussi des reprises de calcul grâce aux continuations. Une continuation correspond à un point de calcul. La forme spéciale call_cc lance un calcul avec la possibilité de reprendre celui-ci au niveau de la continuation courante, c'est à dire du retour de ce calcul. Il existe de très nombreuses implantation de Scheme. Il est même utilisé comme langage de macros pour le logiciel de retouche d'images GIMP. Scheme est un excellent laboratoire expérimental pour l'implantation de nouveaux concepts de programmation séquentielle ou parallèle (grâce aux continuations).

Langages à évaluation retardée

À la différence de ML ou Lisp, les langages à évaluation retardée ne calculent pas les paramètres d'appel des fonctions à leur passage, mais quand l'évaluation du corps de la fonction le nécessite. Il existe une version << paresseuse >> de ML appelée Lazy ML mais les représentants principaux de cette famille de langages sont Miranda et Haskell.

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.

Lien

http://www.engin.umd.umich.edu/CIS/course.des/cis400/miranda/miranda.html

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 dans l'exemple ci-dessous :

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

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 devient nécessaire. Ainsi, les listes Miranda sont naturellement des flots.

Miranda a une syntaxe concise pour les 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.

Miranda 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 l'archétype des langages fonctionnels purs paresseux.

Haskell

Le site principal du langage Haskell contient les rapports de définition du langage et de ses bibliothèques, ainsi que les principales implantations de celui-ci.

Lien

http://www.haskell.org

Plusieurs ouvrages sont consacrés à la programmation fonctionnelle en Haskell, un des plus récents est [Tho99].

C'est un langage qui reprend presque tous les nouveaux concepts des langages fonctionnels. Il est pur (sans effet de bord), paresseux (non-strict), muni d'un polymorphisme ad hoc (pour la surcharge) en plus du polymorphisme paramétrique à la ML.

Polymorphisme ad hoc

Ce système est différent du polymorphisme vu jusqu'à présent. En ML une fonction polymorphe ne regarde pas ses arguments polymorphes. 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 inclut la définition des opérateurs surchargés de sa classe pour ce type.

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

class 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 autres caractéristiques du langage Haskell sont principalement les suivantes :

un système d'entrées-sorties purement fonctionnel utilisant des monades;
les tableaux sont 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 traits pointus issus de la recherche dans le domaine des langages fonctionnels. C'est son avantage et son inconvénient.

Langages de communication

ERLANG

ERLANG est un langage fonctionnel typé dynamiquement pour la programmation concurrente. Il a été développé par la société Ericsson dans le cadre d'applications pour les télécommunications. Il est maintenant en open source. Le site principal d'accès au langage est le suivant :

Lien

http://www.erlang.org

Il est conçu pour que la création de processus et leur communication soient aisées. Les communications se font par envoi de messages et elles peuvent être soumises à des délais. Il est facile de définir des protocoles via des ports. Chaque processus possède son propre dictionnaire de définition. La gestion des erreurs utilise un mécanisme d'exceptions et de signaux qui peuvent se propager entre les processus. De nombreuses applications de téléphonie ont été réalisées avec Erlang, faisant gagner un temps de développement non négligeable.

SCOL

Le langage SCOL est un langage de communication pour la construction de mondes 3D. Il est développé par la société Cryo Networks :

Lien

http://www.cryo-networks.com

Son noyau est proche de celui de Caml : il est fonctionnel, statiquement typé, polymorphe paramétrique avec inférence de types. Il est << multimedia >> grâce à ses API pour le son, la 2D et la 3D. Le moteur 3D est très efficace. L'originalité de SCOL provient de la communication entre machines virtuelles au travers de canaux. Un canal est un couple (environnement, liaison réseau). La liaison est une socket (TCP ou UDP).

L'originalité de SCOL est d'avoir résolu simplement le problème de la sécurisation de code téléchargé : seul le texte des programmes circule sur le réseau. La machine réceptrice type le programme passé puis l'exécute garantissant que le code produit provient bien du compilateur officiel. Pour mettre en oeuvre une telle solution, sans sacrifier la vitesse de transfert et de réception, le choix d'un langage fonctionnel statiquement typé s'est imposé pour la concision des sources qu'il autorise.