MIC : Langage mini-Caml

abstraction concrète

Le langage mini-Caml

Bien que le langage mini-Caml soit défini à partir d'un sous-ensemble du langage fonctionnel Caml, il n'en conserve pas moins son caractère en implémentant la synthèse des types, la pleine fonctionnalité et le polymorphisme.

La pleine fonctionnalité considère les fonctions comme des valeurs fonctionnelles rendues par les expressions qui définissent ces fonctions. Les valeurs fonctionnelles peuvent être passées en arguments à d'autres fonctions ou retournées comme valeur de résultat d'autres fonctions.

Une fonction polymorphe est une fonction qui peut être appliquée à tous les types.

Les phrases

Les phrases acceptées par l'interprète sont des définitions ou des expressions du langage mini-Caml terminées par un double point-virgule ";;".

De plus, l'interprète reconnaît une unique commande "reset();;" qui produit le même effet que le bouton

L'évaluation des expressions et l'environnement

L'interprète type et évalue les expressions mini-Caml en effectuant les opérations indiquées sur les valeurs qu'elles contiennent. Lorsqu'un identificateur figure dans une expression, l'interprète tente de le remplacer par la valeur qui lui est associée dans l'environnement courant.

Les identificateurs

Ils commencent obligatoirement par une lettre soit seule soit suivie d'une séquence de caractères dont chacun d'entre-eux peut être :

- une lettre,
- un chiffre,
- le caractère "tiret_bas" ou "underscore" : `_`
- ou le caractère "apostrophe" ou "quote" : `'`.

Les lettres comprennent les lettres accentuées.

Les majuscules sont distinguées des minuscules.

Les expressions

  • Les expressions simples
  • L'expression conditionnelle
  • L'expression conditionnelle par cas
  • L'expression fonctionnelle
  • L'application

    Les expressions simples

    Il s'agit d'expression constituée soit d'une valeur, soit d'un identificateur. Elles rendent la valeur correspondante.

    Session en cours avec a = 7 dans l'environnement courant et b est inconnu.
    # 99;;
    - : int = 99
    # true;;
    - : bool = true
    # a;;
    - : int = 7
    # b;;
    Erreur : b est inconnu
    

    L'expression conditionnelle

    L'expression
    if condition then expr_alors else expr_sinon
    évalue l'expression booléenne condition, et si elle vaut true elle retourne la valeur de expr_alors, sinon elle retourne la valeur de expr_sinon.

    Session en cours avec u = 101 et couleur = 212 dans l'environnement courant.
    # if couleur = 2*u then 1 else 0 ;;
    - : int = 0
    # if couleur = 2*u+10 then 1 else 0 ;;
    - : int = 1
    

    L'expression conditionnelle par cas

    L'expression
    match expression with
        motif_1 -> expr_1
       ...
      | motif_i -> expr_i
       ...
      | motif_n -> expr_n
    compare successivement la valeur de l'expression à filtrer expression aux motifs motif_1 à motif_n.
    Si l'un des motifs est égal à la valeur de expression le résultat obtenu donné par la valeur de l'expression à droite de la flèche correspondant au motif sélectionné. expr_sinon.
    Si plusieurs motifs ont la même valeur que l'expression à filtrer, c'est le premier d'entre-eux qui est choisi.
    Si aucun motif ne peut correspondre à la valeur à filtrer, une erreur d'échec du filtrage est déclenchée.

    Un motif est une valeur, un identificateur, ou une construction formée par la combinaison de valeurs et/ou d'identificateurs avec le constructeur de paires "," et/ou le constructeur de listes "::".

    >MIC : nouvelle session (just for <fun> !)
    
    # match (5*5-1) with 16 -> 1 | 20 -> 2 | 24 -> 3 | 30 -> 4 ;; - : int = 3 # match (5*5-1) with 16 -> 1 | 20 -> 2 | 30 -> 3 ;; Erreur : Echec filtrage

    Si un identificateur apparaît dans un motif, il représente alors toute la gamme des valeurs du type qui lui est associé, et s'il est sélectionné, il est lié à la valeur filtrée.

    Session en cours avec jour = 4 dans l'environnement courant.
    # match jour with 1 -> 0 | n -> n * 3 ;;
    - : int = 12
    

    L'expression fonctionnelle

    Une expression fonctionnelle
    function
        motif_1 -> expr_1
       ...
      | motif_i -> expr_i
       ...
      | motif_n -> expr_n
    est une construction destinée à accepter un argument et à y faire correspondre un résultat par comparaison de la valeur de l'argument à la suite des associations (motif -> expression) en procédant à un filtrage comme pour l'expression conditionnelle par cas.

    >MIC : nouvelle session (just for <fun> !)
    
    # function true -> 0 | false -> 1 ;; - : (bool -> int) = <fun> # function x -> x*x ;; - : (int -> int) = <fun>

    L'application

    Une application est une expression formée par la juxtaposition de deux expressions dont la première est une expression fonctionnelle et la seconde son argument.
    L'application expr_fonction expr_arg rend la valeur prise par l'expression fonctionnelle expr_fonction pour la valeur de l'argument expr_arg.

    >MIC : nouvelle session (just for <fun> !)
    
    # (function x -> x*x) 8 ;; - : int = 64 # (function true -> 0 | false -> 1) true ;; - : int = 0 # (function true -> 0 | false -> 1) false;; - : int = 1

    Les définitions

  • Les définitions simples
  • Les définitions imbriquées
  • Les définitions récursives

    Les définitions simples :

    Les définitions de la forme let ident = expr installent, dans l'environnement courant, des associations (ident,valeur_expr) où valeur_expr est la valeur de l'expression expr.

    >MIC : nouvelle session (just for <fun> !)
    
    # let x = 3 ;; x : int = 3 # let h = function u -> x*u + x ;; h : (int -> int) = # h 4 ;; - : int = 15

    Les définitions imbriquées :

    Dans les expressions de la forme let ident = expr in expression la définition à gauche du mot-clé in ajoute l'association (ident,valeur_expr) à l'environnement courant pour former un environnement temporaire dans lequel expression est évaluée.

    >MIC : nouvelle session (just for <fun> !)
    
    # let y = -8 in 9 + y*y ;; - : int = 73 # let g = function x -> 5*x*x - 44*x + 1 in (g 7);; - : int = -62 # let a = let s = function x -> (x+4,x-4) in s 3 ;; a : (int * int) = ( 7, -1)

    Les définitions récursives :

    L'interprète accepte les constructions récursives pour la définition d'expressions fonctionnelles.

    1er exemple : la fonction factorielle.

    >MIC : nouvelle session (just for <fun> !)
    
    # let rec fact = function 0 -> 1 | n -> if(n<0) then 1/0 else n*fact(n-1) ;; fact : (int -> int) = <fun> # fact 0;; - : int = 1 # fact 6;; - : int = 720 # fact -2;; Erreur : division par 0

    Noter que dans le cas où un entier négatif est passé en argument, le calcul de l'expression n*fact(n-1) forme une boucle infinie. On utilise, ici, une division par zéro, pour déclencher une erreur qui provoque la sortie du programme.

    La gestion des exceptions ne fait pas partie de la définition de ce sous-ensemble du langage Caml.

    2eme exemple : la fonction mem.

    L'application (mem objet liste_explorée) vérifie si objet est membre de la liste liste_explorée.

    >MIC : nouvelle session (just for <fun> !)
    
    # let rec mem = function x -> (function [] -> false | a::r -> if x=a then true else mem x r) ;; mem : ('a -> ('a list -> bool)) = <fun> # mem 4 (0::1::3::[]) ;; - : bool = false # mem 4 (0::1::3::4::[]) ;; - : bool = true

    Les valeurs et les types

  • Entiers
  • Booléens
  • Paires
  • Listes

    Les nombres entiers :

    Les nombres entiers sont représentés par le type int,
    avec les quatre opérateurs arithmétiques (+, -, *, /)
    et les opérateurs de comparaison (<, <=, >, >=, =, <>)

    >MIC : nouvelle session (just for <fun> !)
    
    # let x=5 ;; x : int = 5 # let y = -3 in y*x - x*x + y*y ;; - : int = -31 # 19/x ;; - : int = 3

    Les booléens :

    Les booléens true et false sont représentés par le type bool,
    ils sont utilisés avec les opérateurs de comparaison (<, <=, >, >=, =, <>)

    >MIC : nouvelle session (just for <fun> !)
    
    # let a = (0 = 1-1) ;; a : bool = true # let equiv = function true -> (function true -> true | false -> false) | false -> (function true -> false | false -> true) ;; equiv : (bool -> (bool -> bool)) = <fun> # equiv true true;; - : bool = true # equiv false true;; - : bool = false # equiv true false ;; - : bool = false # equiv false false ;; - : bool = true

    Les paires :

    Une paire est constituée par un couple de valeurs de types 'a et 'b quelconques, et est representée par le type ('a * 'b).

    Si u est une valeur de type 'a et v une valeur de type 'b, en associant ces deux valeurs avec le constructeur de paires "," on obtient la valeur (u,v) qui est une paire du type ('a * 'b).

    >MIC : nouvelle session (just for <fun> !)
    
    # let fst = function(a,b) -> a ;; fst : (('a * 'b) -> 'a) = <fun> # fst(4,3);; - : int = 4 # let snd = function(a,b) -> b ;; snd : (('a * 'b) -> 'b) = <fun> # snd(4,3) ;; - : int = 3

    Les listes :

    Une liste du type 'a list est :
  • soit une liste vide,
  • soit formée d'une tête de liste et d'un reste de liste :
    • la tête de liste est une valeur de type 'a
    • le reste de liste est une liste du type 'a list.

    La liste vide a pour valeur []. La valeur x::r exprime une liste non vide dans laquelle x est la tête de la liste, "::" est le constructeur de listes et r est le reste de liste.

    Ce qui précède constitue la seule représentation des listes reconnue par l'interprète. En revanche l'interprète affiche les listes en énumérant tous leurs éléments entre crochets et séparés par des points-virgules.

    1. Exemple de liste reconnue par l'interprète : 1::2::3::[]
    2. Exemple de liste affichée par l'interprète : [ 1; 2; 3]
    Attention : l'interprète affiche mais ne reconnaît pas les listes sous la deuxième forme.

    >MIC : nouvelle session (just for <fun> !)
    
    # let hd = function x::r -> x ;; hd : ('a list -> 'a) = <fun> # hd (5::3::[]) ;; - : int = 5 # hd ([]) ;; Erreur : Echec filtrage # let tl = function x::r -> r ;; tl : ('a list -> 'a list) = <fun> # tl(2::0::5::[]) ;; - : int list = [ 0; 5] # tl [] ;; Erreur : Echec filtrage

    On remarque que dans la définition des fonctions hd et tl le cas de la liste vide n'est pas filtré, ce qui provoque un échec du filtrage lors de l'application de l'une de ces fonctions à la liste vide [].

    Le polymorphisme :

    Certaines fonctions sont polymorphes, c'est à dire qu'elles peuvent être appliquées à des types variés.

    Un exemple est donné, ici, avec la fonction qui construit une paire à partir de ses arguments.

    >MIC : nouvelle session (just for <fun> !)

    # let f = function x -> function y -> (x,y) ;;
    f : ('a -> ('b -> ('a * 'b))) = <fun>
    # f 8 5 ;;
    - : (int * int) = (8, 5)
    # f true [] ;;
    - : (bool * 'a list) = ( true, [])
    # f true false ;;
    - : (bool * bool) = ( true, false)

    Quelques cas d'erreurs

    >MIC : nouvelle session (just for <fun> !)
    
    # g 4 Erreur : syntaxe incorrecte ou phrase incomplète
    Il manque le double point-virgule pour terminer la phrase.
    # let _a = 9 ;;
    Erreur : erreur lexicale
    
    le mot "_a" n'est pas reconnu comme étant un identificateur valide.
    # let alpha' = 5 ;;
    alpha' : int = 5
    # let beta_1 = 3 ;;
    beta_1 : int = 3
    # let gamma = alpha + beta ;;
    Erreur : alpha est inconnu
    # let gamma = alpha' + beta ;;
    Erreur : beta est inconnu
    # let gamma = alpha' + beta_1 ;;
    gamma : int = 8
    
    Les identificateurs alpha et beta n'ont pas été déclarés.
    # let g = function x -> x * x * 3 - 94 * x - 1 ;;
    g : (int -> int) = <fun>
    # g 7 ;;
    - : int = -512
    # g true ;;
    Conflit de types : 
    incompatibilté int avec bool
    
    La fonction g reçoit un argument du type int et ne peut donc pas être appliquée à une valeur booléenne.
    # let rec a = 9 ;;
    Erreur : let rec non fonctionnel
    
    La construction récursive "let rec" ne peut être utilisée qu'avec une valeur fonctionnelle.

    Contacter l'auteur :
    <Jacques.Rouable@wanadoo.fr>

    dernière modification : 05/04/97