Séance 7
Utilisation de la sémantique du langage Oz

L'objectif de cette séance est d'utiliser la sémantique opérationnelle du langage Oz pour raisonner sur des programmes.

Enoncés des exercices

  1. 1 ou 2 ? Pour vous familiarisez à la sémantique opérationelle, exécutez à la main le petit programme suivant, en détaillant toutes les étapes. Rappelez vous qu'une instruction s'exécute dans un environement (notion d'opération sémantique), et observez le mécanisme permettant, lors du second {Browse X}, d'afficher la valeur 1. 
       
   local X in
      X=1
      local X in
         X=2
         {Browse X}
      end
      {Browse X}
   end

  2. Peloton d'exécution. En utilisant la sémantique formelle du langage, exécutez les deux programmes suivants. Faites attention à l'ordre des instructions dans chacun des cas! 

       % Programme 1
   local Res in
      local Arg1 Arg2 in

         Arg1=7          % 1
         Arg2=6          % 2
         Res=Arg1*Arg2   % 3
      end

      {Browse Res}
   end

       % Programme 2
   local Res in

      local Arg1 Arg2 in
         Arg1=7          % 1
         Res=Arg1*Arg2   % 3
         Arg2=6          % 2

      end
      {Browse Res}
   end

    Quel est précisément l'état final de chaque programme? Qu'affichent-ils chacun? Quelles sont les variables créées par chacun? Que deviennent ces variables lorsque les programmes se terminent?

  3. 2 fois 3... Considérez le programme ci-dessous : 

       local
      X=2
      fun {XFoisY Y}
         X*Y
      end
   in
      {Browse {XFoisY 3}}
   end
    Traduisez ce programme en langage noyau, puis exécutez-le en suivant les règles de la sémantique. Pour la traduction en langage noyau, n'oubliez pas que les fonctions sont des procédures, et que le calcul des sous-expressions nécessite l'introduction de variables.

  4. Récursion avec construction d'une liste. Soit la fonction Copy définie ci-dessous. Cette fonction renvoie une ``copie'' de la liste passée en argument. Il va de soi que la fonction n'a pas de véritable utilité, nous nous en servons pour étudier sa structure récursive. 

       fun {Copy Xs}
      case Xs of X|Xr then X|{Copy Xr} else nil end

   end
    Considérons maintenant deux traductions possibles de cette définition de fonction en langage noyau. Dans la traduction 1 à gauche, l'appel récursif {Copy Xr} est exécuté avant de construire la liste avec X. La traduction 2 à droite est une variante. L'unique différence est l'ordre inversé des instructions {Copy Xr Yr} et Ys=X|Yr. Expliquez pourquoi ces deux traductions s'exécutent sans problème. 

       % Traduction 1
   proc {Copy Xs Ys}
      case Xs of X|Xr then

         local Yr in
            {Copy Xr Yr}
            Ys=X|Yr
         end
      else
         Ys=nil
      end

   end

       % Traduction 2
   proc {Copy Xs Ys}
      case Xs of X|Xr then

         local Yr in
            Ys=X|Yr
            {Copy Xr Yr}
         end
      else
         Ys=nil
      end

   end

    Comparons maintenant les deux variantes. Y aura-t-il une différence notable entre les temps d'exécution des deux variantes? Quid de leur utilisation de la mémoire? Quelle variante le compilateur Oz utilise-t-il? A titre de vérification, écrivez un petit programme incluant la définition de la fonction Copy dans l'éditeur oz, et demandez au compilateur sa traduction en langage noyau (menu Oz/Core Syntax).

  5. Minimum d'une liste. Considérez le programme ci-dessous, qui définit une fonction MinLoop. L'appel {MinLoop X Ys} renvoie le minimum des éléments de la liste X|Ys. 

       local
      fun {MinLoop X Ys}
         case Ys of Y|Yr then

            if Y<X then {MinLoop Y Yr} else {MinLoop X Yr} end
         else X end

      end
   in
      {Browse {MinLoop 7 [5 8 3]}}
   end
    Traduisez ce programme en langage noyau, puis exécutez-le en suivant les règles de la sémantique. Pour la traduction en langage noyau, n'oubliez pas que les fonctions sont des procédures, et que le calcul des sous-expressions nécessite l'introduction de variables.

  6. A la chaîne... La fonction Concat définie ci-dessous prend en argument une liste de listes Ls et renvoie la concaténation de toutes ces listes. On peut voir Concat comme une généralisation de Append pour un nombre variable de listes. 

       fun {Concat Ls}
      case Ls of L|Lr then
         {Append L {Concat Lr}}
      else nil end

   end
    Cette définition, qui a l'avantage de la simplicité, a cependant une faiblesse lorsqu'on l'appelle avec une grande liste.