On a vu que tout processus de calcul peut être décrit avec des combinateurs :

• Existe-t-il un moyen efficace d'exécuter les termes formés de combinateurs ? OUI !

• Ce mécanisme d'exécution apporte-t-il quelque chose de plus par rapport
  aux mécanismes classiques ? OUI !

• Contrairement à ce que son nom pourrait laisser entendre, la machine SK est simplement
  un algorithme plutôt intelligent permettant de réduire des termes.

• La machine SK est ce que l'on appelle une machine de réduction de graphe.

Les termes sont représentés par des arbres binaires :

• une feuille de l'arbre est un atome (S, K, etc.) ;

• un noeud de l'arbre est une application (PQ).

• Le registre pointe sur une application (PQ) .

• Tant que P (la fonction) est une application :

  • empiler le contenu du registre, i.e. (PQ) ;

  • faire pointer le registre sur P.

Tout terme M s'écrit sous la forme a M₁ ... M_n.

• On a vu que l'on écrasait physiquement le doublet (S X Y Z) par le doublet (X Z (Y Z)).

• Autrement dit, un doublet est écrasé par sa valeur.

• Considérons l'exemple :
  f x y = x + 2*y
  g x = f x 2

• Il va devenir :
  g x = x + 4

• Ce phénomène d'écrasement d'un doublet par sa valeur est général dans la machine SK...
  C'est en presque le fondement !

Le cas de K : état initial

• I La réduction est terminée.

• I (PQ) ...

  • On écrase le doublet I (P Q) par le doublet (P Q).

• I x...

  • Le résultat est x ...

• I c ... où c est un combinateur (S, K, I, etc.).

  • On effecture une manipulation pour écraser le doublet (I c ...) par (c ...).

• En théorie, une équation récursive f x = E(f,x) est résolue grâce à l'opérateur
  Y : f =Y (λ⁺f. (λ⁺x. E(f,x))).

• Dans la machine SK, on pose : f = (λ⁺x. E(f,x)), cela donne un arbre :

• La réduction la plus à gauche des termes. Celle-ci permet d'obtenir la forme normale d'un terme
  lorsqu'elle existe. Elle porte le nom de " applicative order " si l'on parle du langage implémenté
  (en opposition à " normal order ").

• La réduction la plus à gauche correspond à l'appel par nom ou évaluation par nécessité
  qui n'est pas optimal du point de vue du nombre de réduction. Du fait que la machine écrase
  un doublet par sa valeur, elle réalise automatiquement de l'évaluation paresseuse.

• L'algorithme du crible d'Eratosthème permet de déterminer les nombres premiers, c'est-à-dire les nombres qui ne sont divisibles que par 1 et par eux-mêmes :
  • On prend la liste des entiers en commençant à 2 :
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ...
  • On conserve le premier de la liste (2) et on élimine ses multiples. On note en rouge ceux qui sont conserés et en vert ceux qui sont éliminés :
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ...
  • On recommenca avec le suivant : 3. On conserve 3 et on élimine ses multiples. On note en rouge ceux qui sont conserés et en vert ceux qui sont éliminés :
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ...
  • On recommenca avec le suivant : 5. On conserve 5 et on élimine ses multiples. On note en rouge ceux qui sont conserés et en vert ceux qui sont éliminés :
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ...
  • On continue ainsi de suite. On obtient une liste où les nombres qui sont conservés (en rouge) sont premiers et ceux qui sont éliminés (en vert) ne sont pas premiers :
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ...
• A présent, supposons que l'on veuille obtenir le n-ième nombre premier. On prend une liste d'entiers supérieurs à 2 assez grande pour contenir ce n-ième nombre premier et on crible cette liste avec la méthode ci-dessus.

  Le problème est qu'on ne sait pas exactement ce que signifie une liste assez grande. Les mathématiciens nous fournissent un ordre de grandeur déjà très élevé mais il faut prendre une liste encore plus grande si l'on veut être sûr de ne pas se tromper.

  Si l'on possède un langage avec évaluation paresseuse, on peut :

  • fabriquer la liste de tous les entiers supérieurs à 2 ; cette liste ne sera effectivement construite que si l'on demande de l'afficher par exemple ;
  • cribler cette liste ; on obtient la liste des nombres premiers mais cette liste ne sera pas réellement construite ;
  • extraire le n-ième élément de cette liste.

  L'extraction du n-ième élément de la liste provoquera juste assez de calculs pour que cet élément soit disponible.

• entier X = (π X (entier (+ X 1))) ;

• crible L = (π (π₁ L) (crible (elim_mult (π₁ L) (π₂ L))))

• elim_mult X L =
  if = (mod (π₁ L) X) 0
  then (elim_mult X (π₂ L))
  else (π (π₁ L) (elim_mult X (π₂ L)))

• nth K L =
  if = K 1
  then (π₁ L)
  else (nth (- K 1) (π₂ L))

• npremier N = nth N (crible (entier 2))