Notations

1. Généralités

2. Notations sur les environnements

3. Le cas de Lisp

3. Le cas de Lisp

Lisp n'implante pas à proprement parler le λ-calcul, parce que dans le langage on interprète les termes Lisp dans le même ensemble, à savoir S=S* (S* est alors dit réflexif). Ceci signifie que l'interprétation d'une formule est susceptible de modifier l'environnement d'interprétation par "effet de bord" – c'est encore plus vrai avec l'emploi des fonctions Lisp eval et apply (on prendra soin de distinguer la fonction Lisp apply du symbole du λ-calcul apply). Pour cette raison on ne peut pas donner de sémantique dénotationnelle "pure" aux expressions Lisp, puisqu'on doit faire intervenir le contexte d'évaluation.

Définition

On a par conséquent un autre symbole "spécial" de S : def, qui définit un nouveau symbole qui va compléter le contexte d'évaluation.

Le schéma général d'une définition est :

(def x val-x)

où x est le symbole défini, et val-x la définition proprement dite (elle sera généralement décomposable en deux champs : un champ env-x qui est l'environnement des définitions locales et un champ rep-x qui est la représentation – à nouveau décomposable).

L'interprétation d'une telle définition fournit l'environnement :

(x:→x)

qui est l'interprétation d'environnement du terme (def x val-x), x étant l'interprétation de valeur de ce même terme.

On distingue ainsi deux types d'interprétation des termes :

λ-expressions

L'une des difficultés essentielles dans l'interprétation des expressions Lisp est l'interprétation qu'on doit donner à l'évaluation d'une λ-expression Lisp, de la forme :

(lambda(x) E)

Tant qu'on n'applique pas cette forme évaluée, on en peut pas réellement la dénoter dans le modèle précédent. On introduit donc une troisième forme d'évaluation :

Irep[env (lambda(x) E)]
= Iλ[env λx.E]

la forme Iλ étant conservée "telle quelle" dans l'attente d'une application (de ce fait le domaine des termes Lisp peut ne pas être réflexif : la forme Iλ, avec la sémantique qu'on lui attache, n'étant jamais tout à fait un terme du langage).

Environnement

Un « environnement » (au sens des termes Lisp) est un ensemble de définitions connexes, qu'on note ici :

env = ((def x A) (def y B)···)

et dont l'interprétation d'environnement a principalement deux formes possibles :

• L'environnement simultané : c'est la syntaxe let :
  (let ((x A)
      (y B))
     ...)
  qui s'évalue :
  env0 = Ienv[env-0 env]
  
• L'environnement parallèle : c'est la syntaxe define :
  (define x A)
(define y B)
...
  qui s'évalue quant à lui :
  env* = Ienv[env*:env-0 env]
  C'est-à-dire que l'environnement est évalué sur lui-même.

  Plus formellement, on définit une suite d'environnements évalués :

  env0 = env
env1 = Ienv[env0:env-0 env]
env2 = Ienv[env1:env-0 env]
...
envn+1 = Ienv[envn:env-0 env]
...
env* = Ienv[env*:env-0 env]
c'est-à-dire que env* est la limite de la suite des envⁿ (sur la topologie des environnements, qu'on définirait en définissant une mesure sur les termes de S*, ...)

  Par exemple :

  env0 = ((def x (cons 1 y))       (def y (+ 2 z)) (def z 3))
  env1 = ((def x (cons 1 (+ 2 z))) (def y 5)       (def z 3))
  env2 = ((def x (cons 1 5))       (def y 5)       (def z 3))
  ...
  env* = env2