Normalisation par évaluation

En sémantique des langages de programmation , la normalisation par évaluation (NBE) est une méthode permettant d'obtenir la forme normale des termes dans le λ-calcul en faisant appel à leur sémantique dénotationnelle . Un terme est d'abord interprété dans un modèle dénotationnel de la structure du λ-terme, puis un représentant canonique (β-normal et η-long) est extrait en réifiant la dénotation. Une telle approche essentiellement sémantique, sans réduction, diffère de la description syntaxique plus traditionnelle, basée sur la réduction, de la normalisation en tant que réductions dans un système de réécriture de termes où les β-réductions sont autorisées au plus profond des λ-termes.

Le NBE a été décrit pour la première fois pour le calcul lambda simplement typé . Il a depuis été étendu à la fois à des systèmes de types plus faibles tels que le calcul lambda non typé en utilisant une approche théorique du domaine , et à des systèmes de types plus riches tels que plusieurs variantes de la théorie des types de Martin-Löf .

Considérons le calcul lambda simplement typé , où les types τ peuvent être des types de base (α), des types de fonctions (→) ou des produits (×), donnés par la grammaire de forme Backus–Naur suivante (→ en associant à droite, comme d'habitude) :

(Types) τ ::= α | τ ₁ → τ ₂ | τ ₁ × τ ₂

Ceux-ci peuvent être implémentés en tant que type de données dans le méta-langage ; par exemple, pour Standard ML , nous pourrions utiliser :

type de données 
ty 
= 
Base 
de 
chaîne 
| 
Flèche 
de 
ty 
* 
ty 
| 
Produit 
de 
ty 
* 
ty

Les termes sont définis à deux niveaux. Le niveau syntaxique inférieur (parfois appelé niveau dynamique ) est la représentation que l’on souhaite normaliser.

(Termes de syntaxe) s , t ,… ::= var x | lam ( x , t ) | app ( s , t ) | pair ( s , t ) | fst t | snd t

Ici, lam / app (resp. pair / fst , snd ) sont les formes intro / elim pour → (resp. ×), et x sont des variables . Ces termes sont destinés à être implémentés comme un type de données de premier ordre dans le méta-langage :

type de données 
tm 
= 
var 
de 
chaîne 
| 
lam 
de 
chaîne 
* 
tm 
| 
app 
de 
tm 
* 
tm 
| 
paire 
de 
tm 
* 
tm 
| 
fst 
de 
tm 
| 
snd 
de 
tm

La sémantique dénotationnelle des termes (fermés) dans le métalangage interprète les constructions de la syntaxe en termes de caractéristiques du métalangage ; ainsi, lam est interprété comme une abstraction, app comme une application, etc. Les objets sémantiques construits sont les suivants :

(Termes sémantiques) S , T ,… ::= LAM (λ x . S x ) | PAIR ( S , T ) | SYN t

Notez qu'il n'y a pas de variables ou de formes d'élimination dans la sémantique ; elles sont simplement représentées par une syntaxe. Ces objets sémantiques sont représentés par le type de données suivant :

type de données 
sem 
= 
LAM 
de 
( sem 
-> 
sem ) 
| 
PAIRE 
de 
sem 
* 
sem 
| 
SYN 
de 
tm

Il existe une paire de fonctions indexées par type qui se déplacent entre la couche syntaxique et la couche sémantique. La première fonction, généralement écrite ↑ _τ , reflète la syntaxe du terme dans la sémantique, tandis que la seconde réifie la sémantique en tant que terme syntaxique (écrit ↓ ^τ ). Leurs définitions sont mutuellement récursives comme suit :

Ces définitions sont facilement implémentées dans le méta-langage :

(* fresh_var : unité -> chaîne *) 
val 
variable_ctr 
= 
ref 
~1 
fun 
fresh_var 
() 
= 
( variable_ctr 
:= 
1 
+ 
!variable_ctr ; 
"v" 
^ 
Int . toString 
( !variable_ctr ))
(* refléter : ty -> tm -> sem *) 
fun 
refléter 
( Flèche 
( a , 
b )) 
t 
= 
LAM 
( fn 
S 
=> 
refléter 
b 
( app 
( t , 
( réifier 
un 
S )))) 
| 
refléter 
( Prod 
( a , 
b )) 
t 
= 
PAIR 
( refléter 
a 
( fst 
t ), 
refléter 
b 
( snd 
t )) 
| 
refléter 
( Basic 
_) 
t 
= 
SYN 
t
(* reify : ty -> sem -> tm *) 
et 
reify 
( Arrow 
( a , 
b )) 
( LAM 
S ) 
= 
let 
val 
x 
= 
fresh_var 
() 
dans 
lam 
( x , 
reify 
b 
( S 
( reflet 
a 
( var 
x )))) 
fin 
| 
reify 
( Prod 
( a , 
b )) 
( PAIR 
( S , 
T )) 
= 
pair 
( reify 
a 
S , 
reify 
b 
T ) 
| 
reify 
( Basic 
_) 
( SYN 
t ) 
= 
t

Par induction sur la structure des types, il s'ensuit que si l'objet sémantique S désigne un terme bien typé s de type τ, alors la réification de l'objet (ie, ↓ ^τ S) produit la forme β-normale η-longue de s . Il ne reste donc plus qu'à construire l'interprétation sémantique initiale S à partir d'un terme syntaxique s . Cette opération, notée ∥ s ∥ _Γ , où Γ est un contexte de liaisons, procède par induction uniquement sur la structure du terme :

Dans la mise en œuvre :

type de données 
ctx 
= 
vide 
| 
ajout 
de 
ctx 
* 
( chaîne 
* 
sem )
(* recherche : ctx -> chaîne -> sem *) 
recherche amusante 
( ajouter ( remdr , ( y , valeur ))) x = si x = y alors valeur sinon recherche remdr x
(* signification : ctx -> tm -> sem *) 
fun 
signification 
G 
t 
= 
cas 
t 
de 
var 
x 
=> 
recherche 
G 
x 
| 
lam 
( x , 
s ) 
=> 
LAM 
( fn 
S 
=> 
signification 
( ajouter 
( G , 
( x , 
S ))) 
s ) 
| 
app 
( s , 
t ) 
=> 
( cas 
signification 
G 
s 
de 
LAM 
S 
=> 
S 
( signification 
G 
t )) 
| 
pair 
( s , 
t ) 
=> 
PAIR 
( signification 
G 
s , 
signification 
G 
t ) 
| 
fst 
s 
=> 
( cas 
signification 
G 
s 
de 
PAIR 
( S , 
T ) 
=> 
S ) 
| 
snd 
t 
=> 
( cas 
signification 
G 
t 
de 
PAIR 
( S , 
T ) 
=> 
T )

Il est à noter qu'il existe de nombreux cas non exhaustifs ; cependant, si l'on applique la méthode à un terme fermé bien typé, on ne rencontre jamais aucun de ces cas manquants. L'opération NBE sur les termes fermés est alors :

(* nbe : ty -> tm -> tm *) 
fun 
nbe 
a 
t 
= 
réifier 
a 
( ce qui signifie 
t vide 
)

À titre d’exemple de son utilisation, considérons le terme syntaxique SKKdéfini ci-dessous :

val 
K 
= 
lam 
( "x" , 
lam 
( "y" , 
var 
"x" )) 
val 
S 
= 
lam 
( "x" , 
lam 
( "y" , 
lam 
( "z" , 
app 
( app 
( var 
"x" , 
var 
"z" ), 
app 
( var 
"y" , 
var 
"z" ))))) 
val 
SKK 
= 
app 
( app 
( S , 
K ), 
K )

Il s'agit du codage bien connu de la fonction identité en logique combinatoire . Sa normalisation à un type identité produit :

- 
nbe 
( Flèche 
( De base 
"a" , 
De base 
"a" )) 
SKK ; 
val 
it 
= 
lam 
( "v0" , var 
"v0" ) 
: 
tm

Le résultat est en fait sous forme η-longue, comme on peut facilement le voir en le normalisant à un type d'identité différent :

- 
nbe 
( Flèche 
( Flèche 
( De base 
"a" , 
De base 
"b" ), 
Flèche 
( De base 
"a" , 
De base 
"b" ))) 
SKK ; 
val 
it 
= 
lam 
( "v1" , lam 
( "v2" , app 
( var 
"v1" , var 
"v2" ))) 
: 
tm

L'utilisation des niveaux de Bruijn au lieu des noms dans la syntaxe résiduelle crée reifyune fonction pure dans la mesure où il n'y a pas besoin de fresh_var.

Le type de données des termes résiduels peut également être le type de données des termes résiduels sous forme normale . Le type de reify(et donc de nbe) indique alors clairement que le résultat est normalisé. Et si le type de données des formes normales est typé, le type de reify(et donc de nbe) indique alors clairement que la normalisation préserve le type.

La normalisation par évaluation s'adapte également au calcul lambda simplement typé avec des sommes ( +), en utilisant les opérateurs de contrôle délimités shift et reset.