|
Chapitre
2
Fonction
processus Curryfication |
Chapitre
3
Théorie
des combinateurs (Présentation non formelle)
H.B. CURRY |
Chapitre
4
Théorie
des combinateurs (Présentation formelle)
L'INDUCTION |
Chapitre
5
Modélisation
Logico-Combinatoire
des réalités informatiques |
Chapitre
6
La machine SK de
D. TURNER |
|
VI
LA MACHINE SK
DE
D. TURNER
Exécuter
des combinateurs
On
a vu que tout processus de calcul peut être décrit avec des combinateurs
:
-
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.
Représentation
des termes
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).
Exemple
: S (K I) (K K I)
La
machine SK
La machine SK se compose d'une pile (présentée
tête en bas pour des raisons pratiques) et d'un registre pointant
sur une expression à réduire (une application).
Première
étape
-
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.
Cas
général
Tout
terme M s'écrit
sous la forme a
M1 ... Mn.
Avant...
Après
Le
cas de S : état initial
Le
cas de S : création de X Z
Le cas
de S : création de Y Z
Le
cas de S : écrasement de S X Y Z
Le
cas de S : rétablissement de la pile
L'évaluation
partielle
-
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
Le
cas de K : si X ≡ PQ
Le
cas de K : si X est atomique
La
cas de I
-
I
La réduction est terminée.
-
-
On
écrase le doublet I (P Q) par
le doublet (P Q).
-
-
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
:
Intérêts
Par des mécanismes très simples, la machine SK réalise
:
-
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 = (π (π1 L) (crible (elim_mult (π1
L) (π2 L))))
-
elim_mult
X L =
if = (mod (π1
L) X) 0
then (elim_mult X (π2 L))
else (π (π1 L) (elim_mult
X (π2 L)))
-
nth
K L =
if = K 1
then (π1 L)
else (nth (- K 1) (π2
L))
-
npremier
N = nth N (crible (entier 2))
|