énoncé première session 2003

uv16472

1-Preuves (3 points) :
vérifier par les tableaux sémantiques ou le calcul des séquents l'affirmation suivante :

Remarque : vous vous servirez des prédicats suivants :

(i) V(x) : x est une voyante
(ii) C(x, y) : x croit ce que dit y
(iii) S(x) : x est stupide
(iv) F(z) : z est franc


2-Prolog (3 points) :  Construire le prédicat freq/2 permettant de compter le nombre d'occurrences de chaque entier apparaissant dans une liste. Exemple :

?- freq([3,3,3,2,2,1,1,1,2,1,3,1,1] , A).

A=[6*1 , 3*2 , 4*3]

il y a donc 6 '1' et 3 '2' et 4 '3' dans la liste.

Remarque :Le résultat est une liste de " compteurs ". Vous utiliserez le prédicat maj/3 qui " met à jour cette liste de compteurs d'entiers " :

maj(N , [],[1*N]). %création du compteur pour le premier élément de la liste d'entiers

maj(N , [F*N|S],[F1*N|S]) :- ! , F1 is F+1. % on compte 1 N de plus

maj(N , [F*M|S],[1*N , F*M|S]) :- N<M , ! . %première apparition de N

maj(N , [F*M|S],[F*M|S1]) :- N=\=M , maj(N , S,S1). %N est dans la suite


3-DCG + Sémantique Structurelle (8 points) :  

Sémantique Structurelle

Rappel : Sémantique Structurelle d'un petit langage :

1- Catégories syntaxiques :

i,i1,i2 dans INST

e dans Exp ; be dans exp

x dans Var ; bx dans BVar

o dans O ; bo dans BO

n dans N ; b dans {vrai , faux}

2-Définitions

i ::= i1 ; i2 | x = e | if (be , i1 , i2) | while( be , i1)

Les définitions de e et be sont inchangées, supposées connues et vues en exercices…

Sémantique structurelle Prolog :

:- op(999 , xfx , ['-i->' , '-e->' , '-b->']).

% R-aff

(X = E, M) '-i->' [X=N|M1] :- (E, M) '-e->' N , delete(M, X=_,M1).

% cf. delete/3 prédéfini de SWI-Prolog

% R-si

(if(Be, I1, _), M) '-i->' M1 :- (Be, M) '-b->' vrai, (I1, M) '-i->' M1.

(if(Be, _, I2), M) '-i->' M1 :- (Be, M) '-b->' faux, (I2 , M) '-i->' M1.

% R-ptvir

((I1 ; I2), M) '-i->' M2 :- (I1, M) '-i->' M1, (I2, M1) '-i->' M2 .

% R-ttque

(while(Be, _), M) '-i->' M :- (Be, M) '-b->' faux.

(while(Be, I), M) '-i->' M1 :- (Be, M) '-b->' vrai,

((I ; while(Be, I)), M) '-i->' M1.

/** exemples :

? - ( z = 0 ; while(~(eq(x, 0)), (z = z + y ; x= x - 1) ), [x= 1, y= 3, z= 7]) '-i->' M.

*/

Soit l'instruction de boucle " for " qu'on trouve dans les langages de programmation comme java. Informellement sa syntaxe est :

for( <SUITE AFFECTATION1> ; <EXP. BOOL> ; <SUITE AFFECTATION2>) S

<SUITE AFFECTATION1> : initialisation (suite d'affectations séparées par ',')

<EXP. BOOL> : expression booléenne de contrôle de fin de boucle.

<SUITE AFFECTATION2> : incrémentation (suite d'affectations séparées par ',')

S : une instruction (i dans la syntaxe abstraite ci dessus)

Sa sémantique est celle de la boucle " for " Java

On introduit la boucle " for " dans la syntaxe abstraite ci dessus :

2-Définitions modifiées

i ::= i1 ; i2 | x = e | if (be , i1 , i2) | while( be , i1) |

for( sa1 , be , sa2 , i1)

sa ::= sa1 ; sa2 | x = e

remarque : sa : les suites d'affectations d'initialisation et d'incrémentations sont séparées par ' ;' pour pouvoir être traitées comme des suites normales d'instructions.

QUESTION 1 : Ajoutez à la sémantique structurelle ci-dessus les règles d'inférence Prolog pour cette instruction.

QUESTION 2 : Quelle question Prolog pour évaluer/exécuter le programme :

                              n := 10 ; for ( i :=0 , s :=0 ; i=<n ; i:=i+1) do s:=s+i end ?

et quel résultat ?

DCG : la syntaxe concrète des programmes ci-dessus est spécifiée par la grammaire augmentée pour construire l'AST de la syntaxe abstraite ci dessus :

prog(AST) --> inst(INST) , fp(S) , {sf(INST,S , AST)}.

sf(A,[] , A).
sf(I,S , (I;S)) :- S \= [] .

fp([]) --> [] .
fp(AST) --> [';'] , prog(AST).

inst(A=E) --> [A] , {atom(A)},[':='] , exp(E) .
inst(if(EB,A1,A2)) --> [if] , exb(EB), [then] , prog(A1), [else] , prog(A2), [end] .
inst(while(EB,A)) --> [while] , exb(EB), [do] , prog(A) , [end] .

exb(EB) --> … . % connue et vue en Exercices

exp(E) --> … . % connue et vue en Exercices

% la syntaxe de l'instruction "for" est spécifiée par :

inst --> [for] , ['('] , sa , [';'] , exb , [';'] , sa , [')'] , [do] , prog , [end] .

sa --> [A] , {atom(A)}, [':='] , exp , fsa.

fsa --> [] .
fsa --> [','] , sa.

QUESTION 1 : Augmentez ces nouvelles productions pour construire l'AST de la boucle " for " utilisable dans la sémantique structurelle que vous avez défini au-dessus.

QUESTION 2 : Quelle question Prolog pour analyser puis évaluer/exécuter le programme :

                                      n := 5 ; for ( i :=1 , f :=1 ; i=<n ; i:=i+1) do f:=f*i end ?

et quel résultat ?

4-Java (6 points) : Pattern Observateur/Observé 

En se basant sur les deux interfaces suivantes

package java.util ;
public interface Observer{
	void update(Observable o, Object arg) ;
}

package java.util ;
public class Observable{
	public void addObserver(Observer o);
	public void deleteObserver(Observer o);
 	public void notifyObservers();
	public void notifyObservers(Object arg);
	protected void setChanged();
	protected void clearChanged();
	public int countObservers();
}

QUESTION 1 : programmez une classe " SimpleCompteur " qui soit " observable " et dont toute incrémentation de la valeur de son attribut " compteur " provoque la notification des observateurs.

QUESTION 2 : programmez au moins une classe qui implémente l'interface Observateur, chargée d'imprimer la nouvelle valeur de l'attribut " compteur " de la classe " SimpleCompteur " à chacune de ses modifications.

QUESTION 3 : Vous fournirez également un programme de test de l'ensemble avec au moins deux observateurs sur le compteur.