Sémantique « continuationnelle »

un aperçu

Qu’est-ce qu’une continuation?

• Exemple :– calculer (n), puis ensuite f((n))

• f est « la continuation » de la suite de calculs

• au moment où on termine avec , on ne sait pas ce qui vient après

• faire de « ce qui vient après » l’argument d’une fonction

-barre(n, f) = f((n))

Continuation et types

: a b

• f : b c-barre : a ((b c) c)

• cas particulier: c = -barre(n) : (b ) • logique classique : (b ) b

Ex: sémantique de Montague

Quantificateur

• tout : (e t) ((e t) t)

• tout chat : (e t) t

• initialement : SN de type e

• SN quantifié : de type (e t) t

• c’est le « continuisé » de [[SN]]

SN SV

SN SV

fonctionArgument

fonction Argument

Y X1

X2

X4

X3

Contextes successifs

utilités

• En programmation :– En cas d’erreur, sauver le calcul intermédiaire

et effectuer une opération (envoi d’un message)

– Cf. GOTO (aller directement à une instruction de programme, ici c’est comme si on donnait comme argument la suite d’instructions à partir d’une certaine étiquette)

Exemple• (define (produit L)• (if (null ? L) 1• (* (car L)(produit (cdr L))))

Pas efficace• (produit ‘(2, 3, 0, 1)) =• 2 * (produit ‘(3, 0, 1)) =• 2 * (3 * (produit ‘(0, 1))) = • 2 * (3 * (0 * (produit ‘(1)))) =• 2 * (3 * (0 * (1 * (produit ())))) =• 2 * (3 * (0 * (1 * 1))) =• 2 * (3 * (0 * 1)) =• 2 * (3 * 0)) = • 2 * 0 = • 0

Introduire une variable de continuation

• (define (produit-barre L k)• (cond ((null ? L) (k 1))• ((zero ? (car L)) 0)• (else (produit-barre (cdr L)(lambda (p) (k (* p (car

L)))))))

(produit-barre ‘(2, 3, 0, 1) id) =(produit-barre ‘(3, 0, 1)(lambda (p)(id (* p 2)))) =(produit-barre ‘(0, 1)(lambda (p)((lambda (p)(id (* p 2)))(* p

3)))) = 0

commentaire : partons de k = id, si la liste L n’est pas vide et si son premier élément n’est pas ‘0’, alors on applique la fonction au cdr, avec comme valeur de k : p. p(car L), puis si (cdr L) n’est pas vide et son premier élément n’est pas ‘0’, on applique la fonction au cdr du cdr mais cette fois avec comme valeur de k : p. (p. p(car L) p(car (cdr L))) = p. (p(car (cdr L)))(car L) etc.

Fonctions qui manipulent les contextes

Soit E = (… (call/cc (lambda(k) corps) …)

L’appel de call/cc lie k à la continuation qui suit (call/cc (lambda(k) corps) dans E

exemple

• (call/cc (lambda (k)(+ 2 (* 7 (k 3)))))contexte : identitérésultat : 3• (* 4 (+ (call/cc (lambda (k) (* 5 8))) 2))contexte : (lambda ([])(* 4 (+ [] 2)))résultat : (* 4 (+ (* 5 8) 2)), soit : 168• (* 4 (+ (call/cc (lambda (k) (* (k 5) 8))) 2))

même contexterésultat : ((lambda ([])(* 4 (+ [] 2))) 5) 28

( * 4 (+ (call/cc (lambda (k) (* 5 8))) 2))

( * 4 (+ (call/cc (lambda (k) (* (k 5) 8))) 2))

( * 4 (+ (call/cc (lambda (k) (* 5 8))) 2))

( * 4 (+ (call/cc (lambda (k) (* (k 5) 8))) 2))

E[call/cc(M)] E[M(z.E[z])]

M

M

E

((lambda ([])(* 4 (+ [] 2))) 5)

( * 4 (+ (* 5 8))) 2))

E[call/cc(M)] E[M(z.E[z])]

-calcul

• M. Parigot (1990)• continuations goto étiquettes d’instructions• point de vue logique :

– étiquettes d’instructions formules nommées

• variables « pour nommer » : les -variables

• Si une -variable « s’applique » à un terme : elle nomme ce terme :– ( t) : t est nommé par

-abstraction : les termes nommés par deviennent actifs– (M)(N) : N est passé aux sous-termes de M nommés par

exemple

(((y. . ( (y x. . ( x))) u) a) b)

((. ( (u x. . ( x))) a) b)

exemple

(((y. . ( (y x. . ( x))) u) a) b)

((. ( (u x. . ( x))) a) b)

(. ( (u x. . ( (x a)))) b)

exemple

(((y. . ( (y x. . ( x))) u) a) b)

((. ( (u x. . ( x))) a) b)

(. ( (u x. . ( (x a)))) b)

. ( (u x. . ( ((x a) b))))

NB: Le fait que l’étiquette soit conservée fait que l’on peut appliquer un tel -terme à une suite quelconque de termes : on n’est pas obligé comme dans le -calcul standard de prévoir exactement le nombre de termes auquel on veut appliquer l’opérateur.

intuition

• « The intuition for this term calculus is that each -sequent has exactly one active, or principal, formula, A, on the right-hand side, i-e., the leftmost one, which is the formula upon which all introduction and elimination rules operate »

de Paiva & Ritter, 2005

Extension de Curry-Howard

|- t : A, |- t : , A, |- ( t) : , A, |- . t : A,

1ère règle : distinguer une formule et lui donner un nom, en même temps on « gèle » la formule car elle n’est plus la première en partie droite

2ème règle : repérer une formule d’après son étiquette et la rendre active, en même temps, on « dégèle » la formule car elle apparaît maintenant en tête de la partie droite

à gauche : que des x : A – x une variable et A un type – à droite : que des A - un nom et A un type –

Interprétation de la négation

|- t : A, |- t : , A, |- ( t) : , A, |- . t : A,

|- t : A, A, |- t : , ,A |- ( t) : ,, |- . t : A,

|- t : A, |- t : A, |- ( t) : A, |- . t : A,

• geler une formule = appliquer la double négation• dégeler une formule = appliquer l’élimination de la

double négation

Règle d’échange

|- t : B, A, |- . ( t) : A, B,

Règle « d’échange » : rendre active A en gelant B

Exemple de déductionA |- A en logique classique

A |- A

|- A |- A, A

|- A

Obtention d’un -terme

t : A |- t : A

t : A |- ( t) : , A

|- M : A |- t. ( t) : A, A

|- M(t. ( t)) : , A

|- . M(t. ( t)) : A

variations

1. .M dans un contexte ([] N) :

 : ((.M) N) .M[( t) := ( (t N))]

2. .M dans un contexte (N []) :

’ : (N (.M)) .M[( t) := ( (N t))]

en ce cas, il n’y a plus la propriété de Church-Rosser

de Groote, 2001

• Toute personne aime un chat

Expression sémantique type

toute personne . x. personne(x) ( x) e

un chat . y. chat(y) ( y) e

aime x. y. ((aime y) x) e (e t)

Pourquoi « toute personne » de type e?

(supposer t = )

|- personne: et x : e |- x : e x : e |- x : e

x : e |- personne(x) : t x : e |- ( x) : t, e

x : e |- personne(x) ( x) : t, e

|- x personne(x) ( x) : t, e

|- . x personne(x) ( x) : e

supposé de type e (t t) supposé de type tt

Différentes lectures

1- ((x. y. ((aime y) x)

. y. chat(y) ( y))

. x. personne(x) ( x) )

Différentes lectures

1- ( y. ((aime y) . y. chat(y) ( y))

. x. personne(x) ( x) )

Différentes lectures

1- ((aime . x. personne(x) ( x) ) . y. chat(y) ( y))

Différentes lectures

1- ((aime

. x. personne(x) ( x) ) . y. chat(y)

( y))

contexte (N [] )

Règle ’

1- (( . x. personne(x) ( (aime x)) ) . y. chat(y)

( y))

1- (( . x. personne(x) ( (aime x)) ) . y. chat(y)

( y) )

contexte ([] N)

Règle

1- . x. personne(x) ( ((aime x) (. y. chat(y) ( y))))

contexte ([] N)

simplification

1- x. personne(x) ((aime x) (. y. chat(y) ( y)))

nouvelle application de ’

1- x. personne(x) . y. chat(y) ( ((aime x) y))

nouvelle simplification

1- x. personne(x)

y. chat(y) ((aime x) y)

Différentes lectures

2- ((. x. personne(x) ( (aime x)) ) . y. chat(y)

( y))

contexte (N [] )

Règle ’

2- (. y. chat(y) ( (. x. personne(x) ( (aime x))) y))

simplification

2- y. chat(y) (. x. personne(x) ( (aime x))) y)

Règle ’

2- y. chat(y) (. x. personne(x) ( (aime x))) y)

Règle ’

2- y. chat(y) (. x. personne(x) ( ((aime x) y )))

simplification

2- y. chat(y) x. personne(x) ((aime x) y ))

((aime . x. personne(x) ( x) ) . y. chat(y) ( y) )

N [ ]

((aime . x. personne(x) ( (aime x)) ) . y. chat(y) ( y) )

(. x. personne(x) ( (aime x)) . y. chat(y) ( y) )

(. x. personne(x) ( ((aime x) . y. chat(y) ( y) )))

(. x. personne(x) ( ((aime x) . y. chat(y) ( y) )))

(. x. personne(x) ( (. y. chat(y) ( ((aime x) y) )))

x. personne(x) y. chat(y) (aime x) y)

(. x. personne(x) ( (aime x)) . y. chat(y) ( y) )

(. x. personne(x) ( (aime x)) . y. chat(y) ( y) )

(. y. chat(y) ( (. x. personne(x) ( (aime x)) y) )

y. chat(y) x. personne(x) ((aime x) y)

intérêt

• Absence de Quantifier-Raising

• L’objet quantifié et le sujet quantifié sont traités de la même façon

Grammaires continuisées(Chris Barker)

• Transformations CPS– c de type e : c = k. k(c) de type <<e, t>, t> x. M de type <a, b> : x. M = k. k(x. M) de

type <<<a, b*>, b*>, b*> où b* type de M– (M N) = k. (M (m. N(n. (k (m n))))) 

• Exemple x. dort(x) de type <e, t> x. dort(x) = k. k(x. dort(x)) de type <<e, t>,

t>, t>

exemple

• Pierre dort

• old: pierre x. dort(x)

dort(pierre)

• new : u.u(pierre) k.k(x. dort(x)) u.u

x. dort(x)

dort(pierre)

exemple

• Pierre dort

• old: pierre x. dort(x)

dort(pierre)

• new : u.u(pierre) k.k(x. dort(x)) u.u

x. dort(x)

dort(pierre)

Continuation 1

exemple

• Pierre dort

• old: pierre x. dort(x)

dort(pierre)

• new : u.u(pierre) k.k(x. dort(x)) u.u

x. dort(x)

dort(pierre)

Continuation 1

Continuation 2

Schèmes de continuation

• Lemme : étant donnée une règle C AB, avec c = m(a, b) (où nous avons noté a, b et c les représentations sémantiques respectives de A, B et C et où m est l’opération qui relie a, b et c, ici l’application, c = b(a)), il existe deux règles : C AB, avec c* = m1(a*,b*) et C AB, avec c* = m2(a*,b*) qui sont telles que pour i=1, 2, mi(a*,b*)(x.x) = m(a, b).

• Il suffit que m1 et m2 vérifient la contrainte suivante, appelée schème de continuation :

• m1(a*,b*) = u.(a*(x. (b* (y u(m(x, y)))))))• m2(a*,b*) = u. (b*(y. (a* (x u(m(x, y)))))))

application

• S SN SVu. [[SV]]* (P. [[SN]]* (x. u (P x))) ouu. [[SN]]* (x. [[SV]]* (P. u (P x)))

• où [[X]]* est la continuisation de la sémantique de X

• Même résultat que de Groote, 2001

Continuisations et DRTd’après de Groote 2005

Problèmes avec DRT:– La fusion de deux DRS peut conduire à des

assignations de valeurs qui détruisent les valeurs précédemment assignées

– pour l’éviter: procéder à des renommages astucieux…

dans ce qui suit, on ne recourt pas à des variables

Continuisations et DRTd’après de Groote 2005

Un énoncé s’interprète en contexte

• contexte gauche : g

• contexte droite : g t

• énoncé : g ((g t) t)

discours

• D D E• But : trouver la bonne contrepartie sémantique

de cette règle– soit e une variable de contexte gauche– soit une variable de contexte droite

e’.. ([[D]] e’ (e.([[E]] e, ))) :

• Quel lien entre e et e’ ?

D

D

E

e’ e

DRS

• [[x1, …, xn] ; C1, …, Cm] x1, …, xn C1 … Cm Version continuisée: e. . x1, …, xn C1 … Cm (, e’)

• où e’ dépend (comment?) de e, x1, …, xn • et est une continuation (« droite ») qui s’applique au

nouveau contexte gauche fourni par e’

x1, …, xn

C1 … Cm

e

e’

exemple

• John1 loves Mary2. He1 smiles at her2

• désormais:– [[np]] = g ((g (e t)) t)

• deux cas :– Nom propre : introduit un nouvel indice dans le contexte gauche

qui sera utilisé par la continuation (push)– Pronom : sélectionne un indice dans le contexte gaucje (select)

NP VP

gg(et)

t

push

• prend pour argument un entier

• lui associe une fonction qui :– à un objet de type e associe– une fonction de changement de contexte

Type : N (e (g g))

select

• prend en argument un entier

• lui associe la fonction qui– Au contexte gauche existant associe l’objet

de type e qui correspond à cet entier

Type : N (g e)

select i (push j a l) = a si i = j

= select i l, sinon

Nom propre indicé

• [[Johni]] = e. . ((push i john e) john)

contexte gaucheold

continuation

Rappel : –[[np]] = g ((g (e t)) t)

contexte gauchenew

e

Pronom indicé

• [[hei]] = e. . ( e (select i e))

Verbe transitif

• [[np]] ([[np]] [[s]])

• (g ((g (e t)) t)) ((g ((g (e t)) t)) (g ((g t) t))))

o. s. e. . (s e (e’.x. (o e’ (e’’. y. (love x y) ( e’’)))))

dérivation• ((o. s. e. . (s e (e’.x. (o e’ (e’’. y. (love x y) ( e’’))))) [[Mary2]]) [[John1]])

e. . ([[John1]] e (e’.x. ([[Mary2]] e’ (e’’. y. (love x y) ( e’’))))) = e. . (e. . ((push 1 john e) john) e (e’.x. ([[Mary2]] e’ (e’’. y. (love x y) (

e’’))))) e. . ((e’.x. ([[Mary2]] e’ (e’’. y. (love x y) ( e’’))) (push 1 john e) john)) e. . ((x. ([[Mary2]] (push 1 john e) (e’’. y. (love x y) ( e’’))) john)) e. . (([[Mary2]] (push 1 john e) (e’’. y. (love john y) ( e’’))) = e. . ((e. . ((push 2 mary e) mary) (push 1 john e) (e’’. y. (love john y) (

e’’))) e. . ((. ((push 2 mary (push 1 john e)) mary) (e’’. y. (love john y) ( e’’))) e. . (((e’’. y. (love john y) ( e’’) (push 2 mary (push 1 john e)) mary)) e. . (((y. (love john y) ( (push 2 mary (push 1 john e))) mary)) e. . ((love john mary) ( (push 2 mary (push 1 john e))))

… he smiles at her !

• cf. e.. ([[D]] e (e’.([[S]] e’, )))

pour composer les deux parties

• avec he smiles at her :

e. . (smile (select 1 e)(select 2 e) ( e))

dérivation e.. ([[D]] e (e’.([[S]] e’ )) = e.. ([[D]] e (e’.(e. ’. (smile (select 1 e)(select 2 e)) (’ e) e’

)))) e.. ([[D]] e (e’.’. (smile (select 1 e’)(select 2 e’)) (’ e’) )) e.. ([[D]] e (e’. (smile (select 1 e’)(select 2 e’)) ( e’)))) = e.. (e. . ((love john mary) ( (push 2 mary (push 1 john e))))

e (e’. (smile (select 1 e’)(select 2 e’)) ( e’)))) e.. (. ((love john mary) ( (push 2 mary (push 1 john e))))

(e’. (smile (select 1 e’)(select 2 e’)) ( e’)))) e.. ((love john mary) ((e’.(smile (select 1 e’)(select 2 e’)) (

e’))) (push 2 mary (push 1 john e)))) e.. (love john mary) (smile (select 1 (push 2 mary (push 1 john

e))) (select 2 (push 2 mary (push 1 john e)))) ( (push 2 mary (push 1 john e)))

prolongements

• Eviter: Every man loves a woman. *He smiles at her

• Pour cela :– Prendre à égalité de traitement contextes

gauche et droit– Au lieu de

[[Maryi]] = e. . ((push i mary e) mary) [[Mariei]]= .e. . ( marie e (e’. (push i marie

e’)))

individucontexte gauche

contexte droit

contexte gauche individu