La fermeture lexicale : le langage Scheme

Références : sur le langage Scheme [AbS 83] [Sch 87].

On présente en premier le langage Scheme parce qu'il répond de la manière la plus satisfaisante à l'interprétation "intuitive" qu'on peut donner d'une λ-expression. La recherche des identificateurs est réalisée statiquement (« lexical scoping ») : ceci facilite beaucoup le travail du compilateur.

1. Termes

2. Application

2. Application

Application

C'est l'application d'une fonction f sur un argument a :

Irep[env-0 (apply f a)]
     Irep[env-0 f] = Iλ[env-lex λu.(env-f rep-f)]
     Irep[env-0 a] = a
= Irep[env-f*:(u:→a):env-lex rep-f]
     où env-f* = Irep[env-f*:(u:→a):env-lex env-f]

env-f* est la forme évaluée de l'environnement local des définitions de f.

L'algorithme étant peu simple, le cas des λ-expressions compliquant encore davantage les choses, on n'a en Scheme qu'un pseudo-parallélisme d'évaluation :

• S'il s'agit de variables, l'évaluation échoue. Par exemple :
  (define x y) ; [1]
(define y 3) ; [2]
  L'évaluation échoue en [1], alors que si [1] était placé après [2] elle pourrait être valide : dans Scheme, pour des raisons d'homogénéité, elle échouerait aussi.
• S'il s'agit de fonctions, l'évaluation réussit. Ceci permet de définir des fonctions mutuellement récursives, ou même plus simplement récursives (ce qu'on était en droit d'attendre du langage).

Evaluation

S'agissant du langage Lisp, c'est-à-dire d'un domaine réflexif d'interprétation, on a deux autres fonctions "spéciales" : quote et eval.

Irep[env-0 (quote x)] = x

Irep[env-0 (eval x env)]
     Irep[env-0 x] = x
     Ienv[env-0 env] = env
= Irep[env x]

Scheme demande un environnement d'évaluation pour l'application de eval, qui lui servira de fermeture lexicale.

En particulier, concernant les λ-expressions :