MIC : Langage mini-Caml

abstraction concrète

Le langage mini-Caml (version francisée)

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 "réinitialiser();;" 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;;
    - : entier = 99
    # vrai;;
    - : booléen = vrai
    # a;;
    - : entier = 7
    # b;;
    Erreur : b est inconnu
    

    L'expression conditionnelle

    L'expression
    si condition alors expr_alors sinon expr_sinon
    évalue l'expression booléenne condition, et si elle vaut vrai 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.
    # si couleur = 2*u alors 1 sinon 0 ;;
    - : entier = 0
    # si couleur = 2*u+10 alors 1 sinon 0 ;;
    - : entier = 1
    

    L'expression conditionnelle par cas

    L'expression
    comparer expression avec
        motif_1 -> expr_1
       ...
      | motif_i -> expr_i
       ...
      | motif_n -> expr_n
    compare successivement la valeur de l'expression à filtrer expression avec les 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> !)
    
    # comparer (5*5-1) avec 16 -> 1 | 20 -> 2 | 24 -> 3 | 30 -> 4 ;; - : entier = 3 # comparer (5*5-1) avec 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.
    # comparer jour avec 1 -> 0 | n -> n * 3 ;;
    - : entier = 12
    

    L'expression fonctionnelle

    Une expression fonctionnelle
    fonction
        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> !)
    
    # fonction vrai -> 0 | faux -> 1 ;; - : (booléen -> entier) = <fun> # fonction x -> x*x ;; - : (entier -> entier) = <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> !)
    
    # (fonction x -> x*x) 8 ;; - : entier = 64 # (fonction vrai -> 0 | faux -> 1) vrai ;; - : entier = 0 # (fonction vrai -> 0 | faux -> 1) faux ;; - : entier = 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 soit 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> !)
    
    # soit x = 3 ;; x : entier = 3 # soit h = fonction u -> x*u + x ;; h : (entier -> entier) = # h 4 ;; - : entier = 15

    Les définitions imbriquées :

    Dans les expressions de la forme soit ident = expr dans expression la définition à gauche du mot-clé dans 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> !)
    
    # soit y = -8 dans 9 + y*y ;; - : entier = 73 # soit g = fonction x -> 5*x*x - 44*x + 1 dans (g 7);; - : entier = -62 # soit a = soit s = fonction x -> (x+4,x-4) dans s 3 ;; a : (entier * entier) = ( 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> !)
    
    # soit rec fact = fonction 0 -> 1 | n -> si(n<0) alors 1/0 sinon n*fact(n-1) ;; fact : (entier -> entier) = <fun> # fact 0;; - : entier = 1 # fact 6;; - : entier = 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> !)
    
    # soit rec mem = fonction x -> (fonction [] -> faux | a::r -> si x=a alors vrai sinon mem x r) ;; mem : ('a -> ('a list -> booléen)) = <fun> # mem 4 (0::1::3::[]) ;; - : booléen = faux # mem 4 (0::1::3::4::[]) ;; - : booléen = vrai

    Les valeurs et les types

  • Entiers
  • Booléens
  • Paires
  • Listes

    Les nombres entiers :

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

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

    Les booléens :

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

    >MIC : nouvelle session (just for <fun> !)
    
    # soit a = (0 = 1-1) ;; a : booléen = vrai # soit equiv = fonction vrai -> (fonction vrai -> vrai | faux -> faux) | faux -> (fonction vrai -> faux | faux -> vrai) ;; equiv : (booléen -> (booléen -> booléen)) = <fun> # equiv vrai vrai ;; - : booléen = vrai # equiv faux vrai ;; - : booléen = faux # equiv vrai faux ;; - : booléen = faux # equiv faux faux ;; - : booléen = vrai

    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> !)
    
    # soit fst = fonction(a,b) -> a ;; fst : (('a * 'b) -> 'a) = <fun> # fst(4,3);; - : entier = 4 # soit snd = fonction(a,b) -> b ;; snd : (('a * 'b) -> 'b) = <fun> # snd(4,3) ;; - : entier = 3

    Les listes :

    Une liste du type 'a liste 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 liste.

    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> !)
    
    # soit hd = fonction x::r -> x ;; hd : ('a liste -> 'a) = <fun> # hd (5::3::[]) ;; - : entier = 5 # hd ([]) ;; Erreur : Echec filtrage # soit tl = fonction x::r -> r ;; tl : ('a liste -> 'a liste) = <fun> # tl(2::0::5::[]) ;; - : entier liste = [ 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> !)

    # soit f = fonction x -> fonction y -> (x,y) ;;
    f : ('a -> ('b -> ('a * 'b))) = <fun>
    # f 8 5 ;;
    - : (entier * entier) = (8, 5)
    # f vrai [] ;;
    - : (booléen * 'a list) = ( vrai, [])
    # f vrai faux ;;
    - : (booléen * booléen) = ( vrai, faux)

    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.
    # soit _a = 9 ;;
    Erreur : erreur lexicale
    
    le mot "_a" n'est pas reconnu comme étant un identificateur valide.
    # soit alpha' = 5 ;;
    alpha' : entier = 5
    # soit beta_1 = 3 ;;
    beta_1 : entier = 3
    # soit gamma = alpha + beta ;;
    Erreur : alpha est inconnu
    # soit gamma = alpha' + beta ;;
    Erreur : beta est inconnu
    # soit gamma = alpha' + beta_1 ;;
    gamma : entier = 8
    
    Les identificateurs alpha et beta n'ont pas été déclarés.
    # soit g = fonction x -> x * x * 3 - 94 * x - 1 ;;
    g : (entier -> entier) = <fun>
    # g 7 ;;
    - : entier = -512
    # g vrai ;;
    Conflit de types : 
    incompatibilté entier avec booléen
    
    La fonction g reçoit un argument du type entier et ne peut donc pas être appliquée à une valeur booléenne.
    # soit rec a = 9 ;;
    Erreur : soit rec non fonctionnel
    
    La construction récursive "soit rec" ne peut être utilisée qu'avec une valeur fonctionnelle.

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

    dernière modification : 05/04/97