%% -*- latex -*-

\documentclass[display,semhelv]{seminar}
%% \documentclass{slides}

\newcommand \CourseName {IFT-2035}
\input{../myslides}

\usepackage{multirow}
\usepackage[normalem]{ulem}
\usepackage{alltt}
%% \usepackage{svg}

%% \newcommand \SMtilde{\ensuremath{{\color{black}_{\widetilde{~}}}}}
%% \newcommand \SMCenterLine[1] {\hfill #1 \hfill \mbox{}}

\begin{document}

%% REWRITE

%% Plusieurs parties:
%% - programmation impérative
%%   - modèle
%%   - passage d'arguments par référence
%%   - structures de contrôle
%%   - prog structurée
%% - pointeurs
%%   - indirection (?)
%%   - modèle de la mémoire
%%   - arithmétique (tableau =? pointeur)
%%   - allocation/déallocation
%%   - aliasing, pointeurs sur les variables
%%   - passage par référence
%%   - gestion mémoire (manuelle, RC, GC, régions)
%%     - pointeurs fous, fuites, ...
%%     - finalization, ptrs faibles
%% - C
%%   - syntaxes, types
%%   - CPP

%% END REWRITE

\begin{myslide}{Syntaxe Haskell - Syntaxe C}
  \begin{displaymath}
    \begin{array}{ll}
      \kw{if}~e_1~\kw{then}~e_2~\kw{else}~e_3 &
          \begin{array}{@{}l@{}}
            \kw{if}~(e_1)~\{e_2;\}~\kw{else}~\{e_3;\} \\
            e_1~?~e_2~:~e_3
          \end{array} \\
      f~x~y~=~e &
          \id{type}_e~f~(\id{type}_x~x, \id{type}_y~y)~\{e;\} \\
      \kw{let}~x=e_1~\kw{in}~e_2 & \{\id{type}_x~x~=e_1;~e_2;\}
    \end{array}
  \end{displaymath}
\end{myslide}

\begin{myslide}{Types en C}
  \begin{itemize}
  \item int, char, short, long, ...
  \item float, double, ...
  \item enum
  \item pointeurs, tableaux, ...
  \item void
  \item struct
  \item union
  \item fonctions
  \end{itemize}
\end{myslide}

\begin{myslide}{Un datatype en C}
  \vspace*{-14pt}
  {\small
  \begin{displaymath}
    \texttt{data Sexp}~\MAlign{
      \texttt{= Snil | Scons Sexp Sexp} \\
      \texttt{| Ssym String | Snum Int}
    }
\end{displaymath}
  }}
  \medskip
\begin{verbatim}
  typedef struct Sexp Sexp;
  struct Sexp {
    enum { SNIL, SCONS, SSYM, SNUM } tag;
    union {
      char *ssymname;
      int snumval;
      struct { Sexp *se1, *se2; } scons;
    } v;
  };
\end{verbatim}
}
\end{myslide}

\begin{myslide}{Un datatype en C, suite}
{\small
\begin{verbatim}
  #define XSCONS(se) (assert ((se)->tag == SCONS), \
                      (se)->v.scons)

  type *sexp_scons (Sexp *se1, Sexp *se2)
  {
    Sexp *se = malloc (sizeof (Sexp));
    se->tag = SCONS;
    XSCONS (se).se1 = se1;
    XSCONS (se).se2 = se2;
    return se;
  }
\end{verbatim}
}
\end{myslide}

\begin{myslide}{De l'assembleur au C}
  registres $\Longrightarrow$ variables

  adresses $\Longrightarrow$ pointeurs

  +struct

  +union

  +programmation structurée
\end{myslide}

\begin{myslide}{Programmation impérative}
  Même modèle que la machine: \emph{séquence} d'opérations sur la mémoire

  Les \emph{fonctions} (qui construisent un résultat) sont remplacées par
  des \emph{procédures} (qui opèrent par modification de leurs arguments).

  Concepts reliés:
  \begin{itemize}
  \item séquence: suite d'opérations à effectuer dans un ordre particulier,
    avec des dépendences implicites
  \item état: ce qui peut changer avec le temps
  \item effet de bord: modification apportée par une opération
  \item identité: ce qui distingue un objet d'une copie identique
  \item valeur: objet sans identité
  \end{itemize}
\end{myslide}

\begin{myslide}{Structure mémoire}
  La mémoire est composée d'un graphe d'objets

  Mémoire = un ensemble d'objets \\
  Objet = une séquence de bytes
  \begin{itemize}
  \item Code: ensemble de fonctions et procédures
  \item Pile: ensemble ordonné d'objets créés implicitement
  \item Tas: ensemble non-ordonné d'objets créés explicitement
  \end{itemize}
\end{myslide}

\begin{myslide}{Procédures}
  Une \emph{fonction} ou \emph{procédure} est un fragment de programme
  clairement délimité

  La \emph{signature} ou \emph{interface} d'une fonction est son type

  Le \emph{corps} d'une fonction est le code en soi

  Une définition de fonction donne son corps, sa signature, la liste des
  \emph{paramètres formels}

  Un appel de fonction indique la fonction et les \emph{paramètres actuels}
\end{myslide}

\begin{myslide}{Passage de paramètres}
  Lien entre un paramètre formel et un paramètre actuel
  \begin{itemize}
  \item par valeur (le plus répandu)
  \item par nom (Algol, Haskell)
  \item par référence (Pascal, C++, Modula-2)
  \item par valeur-résultat (Ada)
  \end{itemize}
\end{myslide}

\begin{myslide}{Passage par valeur}
  Le système le plus simple:

  Le paramètre formel est une nouvelle variable, initialisée avec une copie
  de la \emph{valeur} du paramètre actuel

  Les modifications faites sur le paramètre formel n'affectent pas le
  paramètre actuel

  I.e. l'appelé ne peut pas avoir d'effet sur l'appelant
\end{myslide}

\begin{myslide}{Passage par nom}
  Le paramètre actuel est une \emph{expression} passée sans être évaluée

  Le paramètre formel fait référence à l'\emph{expression}

  Chaque usage du paramètre formel cause l'évaluation de l'expression
\end{myslide}

\begin{myslide}{Passage par référence}
  Le paramètre actuel est un emplacement mémoire

  Le paramètre formel désigne le même emplacement

{\small
\begin{verbatim}
  PROCEDURE inc (VAR x : integer)
  BEGIN
    x = x + 1;
  END
  ... inc (z);  inc (y[3]); ...
\end{verbatim}
}
  On peut parfois le simuler en passant par valeur une référence:
{\small
\begin{verbatim}
  void inc (int *xp)
  { *xp = *xp + 1; }
  ... inc (&z);  inc (y+3); ...
\end{verbatim}
}
\end{myslide}

\begin{myslide}{Passage par valeur-résultat}
  A mi-chemin entre passage par valeur et passage par référence

  Le paramètre actuel est un emplacement mémoire

  le paramètre formel est une nouvelle variable initialisée avec la valeur
  contenue dans l'emplacement mémoire

  Lorsque la fonction termine, la valeur du paramètre formel est copiée dans
  l'emplacement du paramètre actuel

  On peut aussi le simuler en passant par valeur une référence:
{\small
\begin{verbatim}
  void inc (int *xp)
  { int x = *xp; x = x + 1; *xp = x; }
  ... inc (&z);  inc (y+3); ...
\end{verbatim}
}
\end{myslide}

\begin{myslide}{Alias}
  \begin{center}
    \emph{alias}: deux manière différentes de nommer une même entité
  \end{center}

  Example:
  {\small
\begin{verbatim}
  FUNCTION foo (VAR a : INTEGER) BEGIN ... END
  ... foo (b); ...
\end{verbatim}
  }
  Ou encore:
  {\small
\begin{verbatim}
  XAPP (e1).f = XTUP (e2).e1;
\end{verbatim}
  }
  Ou encore:
  {\small
\begin{verbatim}
  let x = (snd y, y) in ...
\end{verbatim}
  }
\end{myslide}

\begin{myslide}{Alias, suite}
  Une modification sur un objet affecte immédiatement tous ses alias

  Peut-être très utile

  Mais c'est aussi une source de problèmes difficiles

  Sans alias, passage par référence $\black{\equiv}$ passage par
  valeur-résultat

  La notion d'alias est intimement liée à celle de pointeur

  {\small
\begin{verbatim}
  int foo (int x[], int y[])
  { x[0] = 1;
    y[0] = 2;
    return x[0] + y[0]; }
\end{verbatim}
  }
\end{myslide}

\begin{myslide}{Pointeurs et références}
  Tout problème peut être résolu en ajoutant un niveau d'\emph{indirection}

  Utilisés de manière interne par les compilateurs

  Utilisés pour les structures de données plus complexes que les tableaux et
  les enregistrements

  Taille fixe (petite) indépendante de l'objet référencé

  Utilisé aussi pour éviter des copies coûteuses
  %%
  \begin{displaymath}
    *x \;\;\;\simeq\;\;\; \id{mem}[x]
  \end{displaymath}
\end{myslide}

\begin{myslide}{Opérations sur les pointeurs}
  Opérations principales:
  \begin{itemize}
  \item Allocation d'un objet, renvoie un nouveau pointeur sur un espace
    mémoire jusqu'alors inutilisé
  \item Indirection, pour accéder à l'objet pointé par le pointeur
  \item Récupération de l'espace alloué
  \end{itemize}
  Autres opérations parfois supportées:
  \begin{itemize}
  \item Arithmétique: $p+n$, $p_1 - p_2$, ...
  \item Obtention d'un pointeur sur un objet existant: $\&x$
  \end{itemize}
\end{myslide}

\begin{myslide}{Arithmétique sur les pointeurs}
  En C, on peut additionner un pointeur et un entier
  \vskip -15pt
  \begin{displaymath}
    *(x + n) ~~~\simeq~~~ \id{mem}[x + n*k]
  \end{displaymath}
  C'est utilisé pour les tableaux:
  \vskip -15pt
  \begin{displaymath}
    x[n] \equiv *(x + n) ~~~~\equiv *(n + x) \equiv n[x]
  \end{displaymath}
  Si $x$ pointe sur un tableau de taille 10, la valeur de $x + 11$
  est indéfinie

  On peut aussi faire la différence entre 2 pointeurs:
  \vskip -15pt
  \begin{displaymath}
    (x + n) - x == n
  \end{displaymath}
  La valeur de $x_1-x_2$ n'est pas définie si $x_1$ et $x_2$ pointent dans des
  objets différents
\end{myslide}

\begin{myslide}{Structures de contrôle}
  \emph{flux/flot de contrôle} = trajet suivi par le point d'exécution

  \emph{flux/flot de donnée} = trajet suivi par les données

  \begin{itemize}
  \item Sauts: $\kw{goto}$, $\kw{break}$, $\kw{continue}$, ...
  \item Tests: $\kw{if}$, $\kw{case}$, filtrage, $?:$, $\&\&$, $||$, ...
  \item Boucles: $\kw{for}$, $\kw{while}$, $\kw{loop}$, ...
  \item Fonctions
  \item Exceptions
  \item Non-déterminisme
  \end{itemize}
\end{myslide}

\begin{myslide}{Fonctions d'ordre supérieur}
  Les fonctions d'ordre supérieur permettent de créer de nouvelles structures de
  contrôle

\begin{displaymath}
  \Align{
    \kw{fun}~\Align{\id{for}~a~b~f = \\
      \kw{if}~a>b~\kw{then}~() \\
      \kw{else}~(f~a; \id{for}~(a+1)~b~f)} \\
    \dots \\
    \id{for}~1~10~(\kw{fn}~i\Rightarrow \id{print}~(\id{Int.toString}~i))}
\end{displaymath}
\end{myslide}

\begin{myslide}{Programmation structurée}
  L'usage abusif de $\kw{goto}$ mène à des programmes \emph{spaghetti}

  La \emph{programmation structurée} impose des règles qui assurent une
  certaine correspondance entre la structure syntaxique d'un programme et
  son flot de contrôle

  Structuration stricte: un point d'entrée et un point de sortie

  Structuration laxiste: un point d'entrée
\end{myslide}

\begin{myslide}{Le \id{switch} de C (\emph{Duff's device})}
  L'énoncé \id{switch} de C n'est pas très structuré
  {\small
\begin{verbatim}
  void copier (char *src, char *dst, int n)
  { while (n > 0) { *dst++ = *src++; n--; } }

  void copier (char *src, char *dst, int n)
  { switch (n & 3) {
      case 0: while (n > 0) { *dst++ = *src++;
      case 3:                 *dst++ = *src++;
      case 2:                 *dst++ = *src++;
      case 1:                 *dst++ = *src++;
                              n -= 4;
  }                }        }
\end{verbatim}
  }
\end{myslide}

%% \begin{myslide}{Récursion}
%%   La récursion est une forme généralisée de boucle

%%   {\small
%% \begin{verbatim}
%%   void toto ()
%%   {
%%     int c, fdl;
%%     fdl = TRUE;
%%     while ((c = getchar ()) != EOF) {
%%       if (c == '\n') {
%%         if (fdl) continue;
%%         fdl = TRUE;
%%       } else
%%         fdl = FALSE;
%%       putchar (c);      
%%   } }
%% \end{verbatim}
%%   }
%% \end{myslide}

%% \begin{myslide}{Récursion (suite)}
%%   {\small
%% \begin{verbatim}
%%   void toto_1 (int fdl)
%%   {
%%     int c;
%%     if ((c = getchar ()) != EOF) {
%%       if (c == '\n') {
%%         if (fdl) continue;
%%         fdl = TRUE;
%%       } else
%%         fdl = FALSE;
%%       putchar (c);
%%       toto_1 (fdl);
%%   } }
%%   void toto () { toto_1 (TRUE); }
%% \end{verbatim}
%%   }
%% \end{myslide}

%% \begin{myslide}{Récursion (continue)}
%%   {\small
%% \begin{verbatim}
%%     if ((c = getchar ()) != EOF) {
%%       if (c == '\n' && fdl)
%%         toto_1 (fdl);
%%       else {
%%         if (c == '\n')
%%           fdl = TRUE;
%%         } else
%%           fdl = FALSE;
%%         putchar (c);
%%         toto_1 (fdl);
%%     } }
%% \end{verbatim}
%%   }
%% \end{myslide}

%% \begin{myslide}{Récursion (nettoyage)}
%%   {\small
%% \begin{verbatim}
%%   void toto_1 (int fdl)
%%   {
%%     int c = getchar ();
%%     if (c != EOF) {
%%       if (c == '\n' && fdl)
%%         toto_1 (TRUE);
%%       else {
%%         putchar (c);
%%         toto_1 (c == '\n');
%%   } } }
%%   void toto () { toto_1 (TRUE); }
%% \end{verbatim}
%%   }
%% \end{myslide}

%% \begin{myslide}{Récursion (fin)}
%%   {\small
%% \begin{verbatim}
%%   void toto_1 (int fdl)
%%   {
%%     int c = getchar ();
%%     if (c != EOF) {
%%       if (c != '\n' || !fdl)
%%         putchar (c);
%%       toto_1 (c == '\n');
%%   } }
%%   void toto () { toto_1 (TRUE); }
%% \end{verbatim}
%%   }
%% \end{myslide}

%% \newcommand \Cstate [4] {(\black{#1};#2;\blue{#3}~|~\red{#4})}
%% \newcommand \Esel {\!\to\!}

%% \begin{myslide}{Tentative de sémantique impérative}
%%   \begin{displaymath}
%%     \begin{array}{l}
%%       \Cstate {} {} {R,x \mapsto v} {x = 3; I}
%%       \sto \Cstate {} {} {R,x \mapsto 3} {I} \\

%%       \Cstate {M, v \mapsto (v_1,v_2,v_3)} {} {R, x \mapsto v}
%%               {x\Esel{}tag = ATOM; I} \\
%%       \sto \Cstate {M, v \mapsto (ATOM,v_2,v_3)} {} {R, x \mapsto v} {I} \\

%%       \Cstate {M, v \mapsto (x)^{R_2} \{ I_2 \} } {S}
%%               {R_1, f \mapsto v} {f (1); I_1} \\
%%       \sto \Cstate {M, v \mapsto I_2} {S, I_1} {R_2, x \mapsto 1} {I_2} \\

%%       \Cstate {M} {S, (R_1, I_1)} {R_2} { return; I_2}
%%       \sto \Cstate {M} {S} {R_1} {I_1} \\

%%       \Cstate {M, v \mapsto (..., v_{11}, ...)} {} {R, x \mapsto v}
%%               {x[1]\Esel{}tag = ATOM; I} \\
%%       \sto \Cstate {M, v \mapsto (..., ATOM,...)} {} {R, x \mapsto v} {I}
%%     \end{array}
%%   \end{displaymath}
%% \end{myslide}

\begin{myslide}{Représentation des objets scalaires}
  Les objets tels que: \blue{pointeurs, entiers, caractères, booléens,
    \kw{enum}, nombres à virgule flottante, ...}

  Géneralement traités de manière atomique

  Pas de notion d'identité

  Représentés par un nombre fixe de bits

  Contraintes d'alignement, soit imposées par l'architecture, soit
  nécessaires pour des raisons de performance

  \emph{Alignement naturel} = adresse est un multiple de la taille de l'objet
\end{myslide}

\begin{myslide}{Représentation des tableaux}
  Noms: \blue{tableaux, vecteurs}

  Disposition contiguë en mémoire

  Chaque élément du tableau a la même taille

  adresse de $T[i] = \id{base} + (i - \id{min}) \times \id{size}$

  Selon les langages, la représentation peut ou non contenir un champ
  supplémentaire qui indique la taille totale du tableau

  Sans ce champ supplémentaire le compilateur ne peut pas vérifier les
  dépassements de bornes
\end{myslide}

\begin{myslide}{Représentation des structures}
  Les noms varient: \blue{structures, enregistrements, objets, tuples, ...}

  Dispositions contiguë des champs en mémoire:
{\small
\begin{verbatim}
  record
    a     : char;     (* adr relative = 0 *)
    b1,b2 : integer;  (* adr relative = 1 et 5 *)
    c     : real;     (* adr relative = 9 *)
  end
\end{verbatim}
}

  En réalité, du \emph{padding} sera ajouté pour aligner le champ
  \texttt{b1}, donc l'adresse relative de \texttt{b1}, \texttt{b2}, et
  \texttt{c} sera respectivement 4, 8, et 12

  Du \emph{padding} peut ausi être ajouté à la fin
\end{myslide}

\begin{myslide}{Effets de bord en Haskell}
  Problème:

  \begin{itemize}
  \item Déterminer si une expression est évaluée, combien de fois, et dans quel
    ordre, peut être très difficile en Haskell.

  \item Heureusement, cela ne change rien au résultat.

  \item Par contre, cela rend les effets de bord inutilisables.
  \end{itemize}

  Solution: \id{main} renvoie une liste de commandes à exécuter.

  L'exécution de ces commandes est faite ``en dehors''.

  $\kw{IO}~\tau$: type d'une commande qui renverra une valeur de type $\tau$.
\end{myslide}

\begin{myslide}{Entrées sorties en Haskell}
\begin{verbatim}
  getChar :: IO Char
  putChar :: Char -> IO ()
\end{verbatim}

L'opérateur $>>=$ permet de composer les opérations:

\begin{verbatim}
  (>>=)   :: IO a -> (a -> IO b) -> IO b
  getChar >>= (\c -> putChar (succ c)) :: IO ()
\end{verbatim}

Cela s'écrit habituellement avec le sucre syntaxique \kw{do}:

\begin{verbatim}
  do c <- getChar
     putChar (succ c)
\end{verbatim}

\end{myslide}

\begin{myslide}{Affectations en Haskell}
En plus de toutes les structures de données pures, Haskell a aussi des
cellules spéciales que l'on peut modifier à loisir:

\begin{verbatim}
  newIORef    :: a -> IO (IORef a)
  readIORef   :: IORef a -> IO a
  writeIORef  :: IORef a -> a -> IO ()
\end{verbatim}

$\kw{newIORef}~v$ crée une nouvelle cellule muable initialisée à $v$

$\kw{readIORef}~r$ lit le contenu de la cellule $r$

$\kw{writeIORef}~r~v$ affecte à la cellule $r$ la valeur $v$
\end{myslide}

\begin{myslide}{Distinguer une commande et son exécution}

La partie pure du langage est séparée de la partie impure

\begin{verbatim}
  a = map putChar ['a', .. 'z']
  b = (a,a)
  c = putChar '1'
  main = head (snd b)
\end{verbatim}

$a$ est une liste de commandes

$b$ est une paire de 2 listes de commandes

Le programme imprime seulement ``\texttt{a}''
\end{myslide}

\begin{myslide}{Monads et effets}
  \kw{IO} est un \emph{monad}

  \begin{itemize}
  \item Il y en a beaucoup d'autres (\id{ST}, \id{Maybe}, \id{Cont},
    \id{Parser}, \id{List}, \id{STM}, ...)

  \item Le monad indique quel genre d'effet peut être présent dans la
    commande correspondante.
  \end{itemize}

  Dans les langages impératifs, il existe un concept similaire: les
  \emph{systèmes d'effets}

  \begin{itemize}
  \item Chaque function est annotée avec les effets qu'elle peut avoir
  \item E.g. $\tau_1 \stackrel{\epsilon}{\to} \tau_2$ où les effets de
    bords sont décrits par $\epsilon$
  \item Les \emph{effets} peuvent inclure la liste des exceptions
    potentiellement levées, les régions utilisées, ...
  \end{itemize}
\end{myslide}

\end{document}
