CSI3525: Concepts des Languages de Programmation

CSI3525: Concepts des Languages de Programmation

Paradigmes des Langages de Programmation Description Smantique des Languages 1 Rappel: Smantique Statique vs Smantique Dynamique La smantique statique reprsente les formes lgales des programmes qui ne peuvent pas tre facilement dcrites en grammaire BNF. On appelle cette smantique, statique, car elle est

vrifie pendant la compilation. La smantique dynamique dcrit la signification des programmes ou les effets encourus par lexcution dun programme. 2 Pourquoi Dcrire la Smantique Dynamique? Les programmeurs doivent savoir exactement ce que fait chaque portion de leur programme Les personnes qui crivent les compilateurs doivent aussi savoir ce que doit faire chaque instruction. Bien quelles soient imprcises, les programmeurs et

dveloppeurs de compilateurs doivent se servir de descriptions en Anglais car les descriptions de smantique formelle sont trs complexes. Nanmoins, la dfinition dune notation formelle et adquate serait importante car elle pourrait aider les dveloppeurs de compilateurs avec des descriptions plus prcises, et peut-tre, mme permettre la gnration de compilateur automatique. 3 Specification de la Smantique Dynamique simplement, Smantique) Il y a trois mthodes de spcification smantique: Description Oprationnelle: la signification dun programme est dtermine par lexcution de ses noncs sur une machine virtuelle. Description Dnotationelle: la signification dun

programme est dcrite a laide de fonctions montrant leffet de lapplication dun nonc sur ltat de la machin Description Axiomatique: la signification dun programm est dcrite a laide dassertions spcifiant les contrainte et relations quimposent un nonc. 4 Smantique Oprationnelle Lide de la smantique oprationnelle est de dcrire la signification dun programme en excutant ses instructions

sur une machine relle ou simule. Les changements qui prennent place dans ltat de la machine lorsquelle excute ces instructions reprsente la signification de cette instruction. Pour construire une machine simule idalise, il faut deux composantes: un traducteur qui traduit le langage L en langage de bas niveau et une machine virtuelle dont ltat change lorsque le code de bas niveau est excut. La smantique oprationnelle est effective. Nanmoins, elle nest pas formelle et peut crer des circularits. 5 Smantique Dnotationnelle

La smantique dnotationnelle est la mthode la plus rigoureuse de description smantique des programmes. Lide consiste dfinir, pour chaque entit du langage, un objet mathmatique et une fonction qui attache les instances de cette entit aux instances de lobjet mathmatique correspondant. Comme pour la smantique oprationnelle, le statut dune machine idalise (en fait la valeur des variables) reprsente la signification dune instruction La difficult de cette mthode est dans la cration dobjets et de fonctions pour ces objets. La notation est aussi difficile a lire quoi que trs concise. 6 Smantique Axiomatique I

La smantique axiomatique est dfinie en conjonction avec une mthode de preuve de validit de programmes. Lorsque le programme est correct, il existe une preuve de validit et dans cette preuve, chaque proposition est prcde et suivie dune expression logique (pre-condition et post-condition) qui spcifie des contraintes sur les variables du programme. Ce sont ces contraintes qui dfinissent la signification du programme. 7 Smantique Axiomatique II

La pre-condition la plus faible reprsente la pre-condition la moins restrictive qui garantie la validit de la post-condition associe a linstruction du programme. Si la pre-condition la plus faible peut tre calcule a partir de la post-condition dfinie pour chaque instruction du langage, preuves de validit peuvent tre construites pour les programmes de ce langage. Les preuves sont construites en partant de la fin dun programme et en remontant vers son dbut. La smantique axiomatique nest pas trs utile pour dcrire la signification des langages de programmation a cause de sa complexit. Nanmoins, elle est utile pour la recherche et pour le raisonnement sur les programmes. 8 Smantique Axiomatique III

Plus prcisment, la vrification de programmes se fait en deux tapes: lassociation dune formule avec chaque tape du calcul significatif. La dmonstration que la formule finale sensuit logiquement de la formule initiale grce aux tapes et formules intermdiaires. Les formules pour laffectation et les conditions sont les formules de base. Leffet de toutes les autres instructions en dcoulent logiquement. 9 Smantique Axiomatique IV: lAffectation

Supposons que x = E soit une instruction daffectation et que Q soit sa post-condition. Alors, sa pre-condition est dfinie par laxiome P=Q x --> E qui signifie que P est calcul comme Q avec toutes les instances de x remplaces par E. Comment peut-on prouver lexactitude de programmes (et en particulier dune instruction daffectation) avec de tels outils?

10 Smantique Axiomatique V: Justification de la procdure Une instruction daffectation avec sa precondition et sa post-condition peuvent tre considrs comme des thormes. Si laxiome daffectation, applique la postcondition et linstruction daffectation, produit la pre-condition donne, alors on peut dire que le thorme est prouv, et donc, le programme est exact ou correcte. 11 Smantique Axiomatique VI: la Rgle de Consquence (rtrcissement ou largissement)

Parfois, la pre-condition obtenue par la procdure ne correspond pas la pre-condition attendue. Dans ce cas, on peut se servir de la rgle de consquence qui est la rgle dinfrence suivante: {P} S {Q}, P => P, Q => Q {P} S {Q} 12 Smantique Axiomatique VII: Squences dinstructions Etant donn deux instructions adjacentes avec les pre- et post- conditions

suivantes: {P1} S1 {P2} {P2} S2 {P3} La rgle dinfrence pour une telle squence est: {P1} S1 {P2}, {P2} S2 {P3} {P1} S1 ; S2 {P3} 13 Smantique Axiomatique VIII: les Instructions de Slection If-then-else: {B and P} S1 {Q}, {(not B) and P} S2 {Q} {P} if B then S1 else S2 {Q} If-then: {B and P} S1 {Q}, {(not B) and P} => Q {P} if B then S1 {Q}

14 Smantique Axiomatique IX: Les Boucles a Test Initial Dans une boucle test initial (ou une boucle while), on a une rptition dinstruction. Le problme avec ces boucles, cependant, est quon ne sait pas combien de rptitions il y a => il est assez difficile de dterminer lexactitude de ces boucles. La mthode utilise est similaire la mthode

mathmatique dinduction. Lhypothse inductive sappelle linvariant de la boucle (loop invariant) 15 Smantique Axiomatique X: Les Boucles a Test Initial La rgle dinfrence qui permet de trouver la pre-condition dune boucle while est la suivante: {I and B} S {I} {I} while B do S end {I and (not B)} I reprsente linvariant de la boucle mais il nest . pas fourni. Cest a nous de le trouver! Comment? En calculant la pre-condition pour

un certain nombre de rptitions et en essayant de deviner un motif. 16 Smantique Axiomatique XI: Les Boucles Test Initial Mais trouver linvariant de boucle nest pas tout!!! Etant donn linstruction {P} while B do S end {Q}, et linvariant de boucle, I , voici un rsum de toutes les choses qui doivent tre dmontres afin de prouver lexactitude dune boucle while: P => I {I} B {I} {I and B} S {I} (I and (not B)) => Q La boucle se termine.

17

Recently Viewed Presentations

  • Testing and Debugging Microsoft SharePoint Applications with ...

    Testing and Debugging Microsoft SharePoint Applications with ...

    Unit Tests vs. Coded UI Tests. Unit Tests. Tests classes and methods at the API level. If it tests a UI, it's testing an abstraction. (not quite testing the UI) UI testing has been hard. Test stuff as you build...
  • Financial Abuse - rbsab.org

    Financial Abuse - rbsab.org

    Support for those who lack capacity to manage their money. Lasting Power of Attorney (LPA) An LPA is a legal document (created by the Mental Capacity Act 2005) that enables any individual over the age of 18 and who has...
  • Designing Sustainable Landscapes for Avian Conservation in ...

    Designing Sustainable Landscapes for Avian Conservation in ...

    Designing Sustainable Landscapes for Avian Conservation in the SAMBI area. original graphic art by: Griffin Shreves III ... SLAMM Output for SAMBI DSL Utilizing A1FI Emission Scenario, Decadal Predictions 2000-2100 (ESRI GRID) ... Designing Sustainable Landscapes for Avian Conservation in...
  • Coffee Break: Developing Programs In-House

    Coffee Break: Developing Programs In-House

    ALISON MCMILLAN TECHNOLOGY ASSISTANT * 1. 1. 1. 1. Thanks for attending this videoconference session * Welcome to the Zoo! Why a Petting Zoo? Important Terms Let Me Introduce You to Our Little Friends Which One is the "Best"? Considerations...
  • Слайд 1 - edufuture.biz

    Слайд 1 - edufuture.biz

    Епоха Середньовіччя пов'язана з поширенням християнства на Заході, а на Сході - буддизму, мусульманства Ознаки епохи Середньовіччя "велике переселення народів" Докорінна зміна ставлення багатьох народів до ...
  • Detecting the Unidentified Victims: Recognized Versus ...

    Detecting the Unidentified Victims: Recognized Versus ...

    The MASC and SPAI-C were used because they perform quite well in measuring anxiety while being developmentally appropriate for the age group in the study, adolescents. The MASC and the SPAI-C are accurate measures of anxiety in adolescents, but there...
  • Concession and Refutation

    Concession and Refutation

    Example Thesis Statement. Although many think The Great Gatsby shows the triumph of the American Dream, it actually reinforces the idea that it is difficult to move between social classes because wealth is not evenly distributed or respected, making it...
  • American Business Culture - Eminence

    American Business Culture - Eminence

    It is customary to begin and end business meetings with a brief but firm handshake. Maintaining direct eye contact is also essential. The exchanging of business cards is a casual affair in the US and as such demands no clear...