Dans un article de 1936, Emil Post décrivait l'ancêtre des machines de Turing, sous la forme suivante :
| ☝️ |
Les instructions possibles sont
index est un mot latin, à l'origine des mots français
On peut représenter l'état initial de la machine de Post ci-dessus par un tableau :
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
En effaçant l'essentiel des bords haut et bas de ce tableau,
il ressemble à [0|0|0|1|0|1|1|0|0|1|0|0].
En Python ce sera [0,0,0,1,0,1,1,0,0,1,0,0].
En C on écrit {0,0,0,1,0,1,1,0,0,1,0,0} et
en Ocaml, [|0;0;0;1;0;1;1;0;0;1;0;0|].
Dans tous ces langages, la position initiale de l'index
est 0 et si l'index i pointe sur le troisième
élément (i = 2) on accède à cet élément
avec la notation t[2] en Python et en C,
avec la notation t.(2) en Ocaml. Par
écrit ce sera plutôt t2. De
manière générale, on gagne à considérer que tout
ce qui est entre crochets est indice. La première
lettre du mot index étant un i, les variables
de boucles sont souvent notées i.
Le programme
let tab = Array.make 11 0;;
for i = 0 to Array.length tab - 1 do
tab.(i) <- i*i
done;;
donne le tableau
| 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 |
Le programme C
int tab[10];
int i;
for (i=0; i<10; tab[i++]=i*i);
donne le tableau
| 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 |
Que ce soit en C ou en Ocaml, i est
une variable entière. On peut s'en apercevoir avec ces
modifications des programmes de création de tableaux :
let tab = Array.make 11 0;;
for i = 0 to Array.length tab - 1 do
print_int i;
print_string ","
done;;
#include <stdio.h>
int main(){
int tab[10];
int i;
for (i=0; i<10; printf("%d,",i++));
return 0;
}
On considère toujours le tableau tab
des carrés, construit avec
int tab[10];
int i;
for (i=0; i<10; tab[i++]=i*i);
Pour accéder à une variable en C, on écrit juste
le nom de la variable. C remplacera automatiquement
ce nom par la valeur de la variable. Mais si on
précède le nom de la variable par le caractère &,
C ira chercher l'adresse mémoire de la variable (un entier).
Par exemple, on a les termes d'une suite arithmétique
avec
for (i=0; i<10; i++) {
printf("%u\n", &tab[i]);
}
En fait on a exactement la même suite arithmétique de nombres entiers avec
int *pointeur = tab;
for (i=0; i<10; i++) {
printf("%u\n", pointeur);
pointeur++;
}
La variable pointeur est un entier
spécial (un pointeur). En l'initialisant à
tab, on lui donne comme valeur initiale,
l'adresse &tab de tab. Et
chaque fois qu'on l'« incrémente » avec
pointeur++, il augmente non pas d'une unité,
mais de la valeur qui convient pour qu'il aille directement
à l'élément suivant du tableau. Pour ce faire, on
l'a déclaré de type int * ce qui veut
dire « pointeur sur entier ».
Une variante du programme précédent affiche les carrés des entiers :
int *pointeur = tab;
for (i=0; i<10; i++) {
printf("%u\n", *pointeur);
pointeur++;
}
L'opération unaire * veut donc dire
suivez le doigt du regard :
*pointeur désigne, non la valeur du
pointeur, mais la valeur pointée par le pointeur.
Ainsi, au lieu d'écrire tab[2] on
peut écrire *(tab+2).
Les arbres binaires (et plus spécifiquement les listes) peuvent être implémentés par des pointeurs. Par exemple un arbre binaire peut être représenté par :
typedef struct {
int label;
struct binarytree *gauche;
struct binarytree *droite;
} binarytree;
Pour implémenter les feuilles de l'arbre binaire,
on utilise la valeur spéciale NULL pour
les pointeurs (une feuille n'ayant ni enfant gauche,
ni enfant droit). L'idée est à la base du langage de
programmation Lisp (McCarthy 1958).
Un pointeur est un graphe orienté :
Comme un pointeur peut pointer vers n'importe
quel type de variable, un pointeur (comme p
ci-dessous) peut même pointer vers un pointeur (
i ci-dessous) :
Un exemple classique est la liste des arguments d'une fonction, par exemple la fonction principale
int main(int argc, char **argv)
Après le doigt, voici donc la main 😂
On a vu que si p est un pointeur,
*p donne non pas le contenu de la
variable p, mais celui de la variable
pointée par p. L'opérateur *
est appelé opérateur de déréférencement.
Un opérateur comme * vu ci-dessus est
dit unaire. En fait il existe un opérateur
binaire en C, également noté * :
c'est la multiplication.
Les opérateurs unaires sont en fait des fonctions.
Par exemple l'opérateur unaire * de C
est la fonction qui, à tout pointeur, associe la
valeur pointée par le pointeur.
Cette fonction est notée $ en
bash. On verra plus bas comment elle
est notée en Ocaml, mais avant cela, une remarque
qui est à la base de la programmation fonctionnelle :
tous les opérateurs sont en réalité des fonctions.
L'idée remonte à Haskell Curry (1926).
La multiplication des entiers par exemple, est notée
de façon infixe (c'est une opération binaire). Le produit
de x par y est noté
x*y. Mais on peut aussi considérer
la multiplication notée préfixe : à deux entiers
x et y, elle associe un entier
qui est le produit de x par y.
La multiplication est alors une fonction qui, à un couple d'entiers, associe le produit de ces entiers :
# let mul1 (x,y) = x*y;; val mul1 : int * int -> int = <fun>
Le graphe ci-dessus décrit correctement la multiplication mais certaines opérations binaires ne sont pas commutatives et l'ordre dans lequel on regarde les variables a de l'importance.
Un couple (comme (x,y) où x
et y sont des entiers) est un élément
du carré cartésien de N. Ocaml lui
donne un type produit :
# let couple = (8,5);; val couple : int * int = (8, 5)
Dans un couple, on distingue le premier élément du couple, du second élément :
# fst couple;; - : int = 8 # snd couple;; - : int = 5
Un graphe n'est autre qu'un sous-ensemble d'un carré cartésien. Il possède donc un type produit. En fait, une fonction est aussi un sous-ensemble d'un carré (ou plus généralement, d'un produit) cartésien :
# let graphe x y = (x,y);; val graphe : 'a -> 'b -> 'a * 'b = <fun>
a pour effet de transformer 'a -> 'b
en 'a * 'b.
Un couple est lui-même un graphe (l'arc allant du premier élément au second). La signature de la multiplication des entiers est donc
La curryfication consiste à enlever le cercle extérieur :
L'approche de Curry consiste à voir la multiplication des entiers (fonction qui, à deux variables entières, associe leur produit), comme une fonctionnelle qui à un entier, associe une fonction linéaire sur les entiers :
# let mul2 x y = x*y;; val mul2 : int -> int -> int = <fun>
On convient que ce graphe revient au même que
Noter que le verbe curryfier est représentable en Ocaml par une fonction :
# let curry f = fun (x,y) -> f x y;;
val curry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>
La curryfication permet de programmer en Ocaml
des fonctions de plusieurs variables. Son inverse
(appelée décurryfication, en anglais
uncurry) permet de comprendre
la signature d'une fonction Ocaml en la voyant
comme une fonction de plusieurs variables. La version
curryfiée de la multiplication des entiers est
donc la décurryfication fait passer du graphe précédent au graphe de départ qui est :
Le verbe décurryfier peut lui aussi être traduit par une fonction Ocaml :
# let uncurry f = fun x y -> f(x,y);;
val uncurry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
La fonction ref associe, à toute
valeur de type 'a, une référence à
cette valeur
# ref;; - : 'a -> 'a ref = <fun>
# let i = ref 0;;
val i : int ref = {contents = 0}
i est maintenant une référence vers
l'entier 0 :
Les références modélisent la notion de variable : il est possible de modifier le contenu d'une référence mais pas la référence elle-même. Par exemple si on essaye
# let j = ref 0;;
val j : int ref = {contents = 0}
on a créé une nouvelle référence :
Si on modifie le contenu de i, cela ne
modifie pas celui de j :
# i := 1;;
- : unit = ()
# i;;
- : int ref = {contents = 1}
# j;;
- : int ref = {contents = 0}
# (!);; - : 'a ref -> 'a = <fun>
La fonction notée par un point d'exclamation en Ocaml associe, à une référence, son contenu (le point d'exclamation se lit à voix haute « le contenu de »). Il n'est pas possible d'additionner un nombre à une référence, mais si le contenu de cette référence est un entier, l'addition est possible :
# i+1;;
Error: This expression has type int ref
but an expression was expected of type int
# !i+1;;
- : int = 2
Pour incrémenter le contenu d'une référence on fait donc
# !i;; - : int = 1 # i := !i+1;; - : unit = () # !i;; - : int = 2
On peut bien entendu incrémenter en boucle :
# for n = 1 to 8 do i:=!i+1 done;;
- : unit = ()
# i;;
- : int ref = {contents = 10}
s
On peut créer des références vers tous les types, y compris vers des références :
# let k = ref j;;
val k : int ref ref = {contents = {contents = 0}}
# !k;;
- : int ref = {contents = 0}
# ! ! k;;
- : int = 0