Glossaire

application

C'est l'application d'une fonction sur ses arguments :

- notation traditionnelle	:	`M (e)`
- notation Lisp	:	`(M e)`
- notation du λ-calcul	:	`(M) e`
- notation adoptée	:	`(apply M e)`

On explicite l'application par le symbole apply.
Par exemple : (apply λx.(+ x 3) 2) retourne 5.

contexte d'évaluation

voir environnement d'évaluation

définition

C'est la définition, en Lisp, d'un nouveau symbole. Son évaluation retourne une valeur d'environnement.
Syntaxe : (def x val-x)
Par exemple : (def x (let ((a 3)) (+a 2))) définit x comme un symbole de valeur 5.

environnement

(d'évaluation) : c'est une fonction partielle d'interprétation des symboles, prolongée sur les termes par des règles qui varient selon les langages.

Par exemple :	`(x:→1):(y:→2):(x:→3)`
	est l'environnement qui à `x` associe la valeur `1` et à `y` la valeur `2`.

des définitions (locales) : ce sont des définitions locales à la définition d'un symbole, en Lisp.

Par exemple :	`(def x (let ((a 3)) (lambda(u) (+ a u))))`
	définit `x` comme un symbole de valeur la λ-expression : `λu.(+ a u)` où `a` vaut `3`.

indéfini

C'est une valeur conventionnelle qui symbolise les cas d'erreur à l'évaluation des termes du λ-calcul.

interprétation

C'est la donnée d'un ensemble de valeurs S et d'un ensemble d'environnements d'évaluation.
L'application d'une interprétation à un terme du λ-calcul retourne une valeur.

d'environnement : l'application retourne une valeur d'environnement.

de représentation : l'application retourne une valeur de représentation.

lambda-expression

C'est une abstraction sur un terme : on l'interprète intuitivement comme une fonction à appliquer sur ses arguments.
Par exemple : λx.(+ x 1) s'interprète intuitivement comme la fonction successeur.

parallèle (évaluation)

C'est l'évaluation d'une liste de définitions dans un contexte d'évaluation formé d'un contexte initial prolongé par cette liste de définitions : formellement, c'est la limite d'une suite d'évaluations.

Par exemple :

(define x 1)
(define y x)
(define z (+ x y))

est évalué en parallèle :

(define x 1)
(define y 1)
(define z 2)

primitif (symbole, fonction)

Ce sont des symboles du λ-calcul qui ont une interprétation intuitive (+,-,···,1,2,3,···) et pour lesquels, dans une interprétation, on choisit l'interprétation intuitive – on identifie alors dans les notations le symbole et sa valeur d'interprétation.

prolongement (d'environnement)

C'est le prolongement d'un environnement d'évaluation sur l'ensemble des symboles du λ-calcul.

Par exemple : (x:→1):env prolonge la fonction env en x.
(x:→2):(x:→1):env "prolonge" la fonction précédente, en redéfinissant la valeur de la fonction en x.

réflexif (domaine)

C'est un domaine interprété sur lui-même : Lisp est presque un domaine réflexif, exception faite des λ-expressions Lisp qui ne sont jamais tout à fait des éléments du langage.

représentation

C'est l'expression qui définit un nouveau symbole, abstraction faite des environnements des définitions qu'on trouve dans la définition du symbole.

Par exemple :

(define x (let ((a 1))
            (let ((b 2))
              (+ a b))))

La définition de x est :

l'environnement (a:→1)
l'expression (let ((b 2)) (+ a b)) qu'on décompose à nouveau :
- l'environnement (b:→2)
- l'expression (+ a b)

(+ a b) est la représentation du symbole x.

simultanée (évaluation)

C'est l'évaluation d'une liste de définitions dans un contexte d'évaluation initial commun à toutes les évaluations.

Par exemple :

(let ((x 1)
      (y x))
     ...)

est évalué en simultané
(si x est défini auparavant par la valeur 2)

(let ((x 1)
      (y 2))
     ...)

symbole

Un symbole est un objet du λ-calcul :

une lettre : a,b,c,···,x,y,z,··· ; en Lisp, il s'agit d'une variable ;
le symbole d'abstraction : λ, qui construit les λ-expressions.
La syntaxe des λ-expressions est : λx.E, où x est une lettre et E un terme du λ-calcul ; en Lisp, on écrirait plutôt : (lambda(x) E).
le symbole d'application : apply.
La syntaxe d'application est : (apply f x1···xn), où f,x1,···,xn sont des termes du λ-calcul.
les symboles primitifs : 1,2,3,···
les fonctions primitives : +,-,···
La syntaxe est par exemple : (+ x y), où x et y sont des termes du λ-calcul.
en Lisp, le symbole de définition : def.
La syntaxe de définition est : (def x val-x), où x est une lettre et val-x un certain nombre de termes du λ-calcul.

terme (du λ-calcul)

Un terme est un élément de S*, de la forme :

u (atomique)
u est soit une lettre, soit un symbole primitif (1,2,3,···)
(f x1···xn)
x1,···,xn sont des termes ; f est très précisément :
- lambda : x1 est alors une lettre, et on note :
  (lambda x1 x2···xn) = (lambda(x1) x2···xn) = λx1.x2···xn
- apply : x1 est un terme qui représente une λ-expression ;
- +,-,··· : une fonction primitive ;
- (en Lisp) def : x1 est alors une lettre.
En particulier, le "terme" f ne peut être ni un symbole ni un terme du λ-calcul autres que ceux mentionnés ci-dessus. Un paramètre fonctionnel demande l'utilisation explicite du symbole apply

valeur

C'est un élément du domaine d'interprétation S.

On note : I[env t]
où env est un environnement d'évaluation et t un terme du λ-calcul.

d'environnement : c'est un élément de l'ensemble [S → S] des fonctions partielles qui à un symbole associent une valeur.
On note : I_env[env t]

de représentation : c'est un élément de l'ensemble S ; on introduit cette notion pour distinguer cette valeur de la valeur d'environnement d'un terme.
On note : I_rep[env t]

de lambda-expression : c'est, formellement, un élément de S.
On note : I_λ[env λx.E]

valeur (en Lisp)

Le domaine d'interprétation est l'ensemble :
S ∪ [S → S] ∪ [S → S]×S*

un terme s'interprète dans `S` :	`I[env t] = I_rep[env t]`
une définition s'interprète dans `[S → S]` :	`I[env t] = I_env[env t]`
une λ-expression s'interprète dans `[S → S]×S*` :	`I[env t] = I_λ[env λx.E]`

Dire que Lisp est rélexif, c'est :

ignorer les valeurs d'environnement ; cela signifie :
- de ne pas décomposer le calcul d'interprétation d'un terme en une interprétation d'environnement suivie d'une interprétation de représentation ;
- de se restreindre à des λ-expressions bien formées, c'est-à-dire des termes qui ne contiennent pas d'occurrence de définition de symbole là où on n'en attend pas (cf. tous les langages présentés) ;
ignorer les valeurs de λ-expressions, ce qui revient :
- soit à poser : I_λ[env λx.E] = λx.E
  la λ-expression est quotée (cf. LeLisp par exemple) ;
- soit à poser : S = [S → S]×S*
  ce qui est mathématiquement possible, sachant qu'on ne considère que des fonctions partielles définies sur un nombre fini de symboles, mais ce qui ne se retrouve pas dans les langages Lisp présentés (en général, on ne peut pas évaluer une λ-expression évaluée).