Formularul specific și compoziția

Sursă Originală: http://www.cs.unh.edu/~charpov/Composition/

Corectitudinea în modelele compoziționale

Scopul unui design compozițional este de a putea construi un sistem din componente. Într-o oarecare măsură, toate desenele sunt compoziționale: sistemele sunt construite din declarațiile mașinilor, care pot fi văzute ca niște componente minuscule. Desigur, pentru ca compoziția să fie utilă, avem nevoie de ceva mai mult dintr-un design compozițional. O componentă trebuie să reprezinte o parte a proiectului, adică trebuie să rezulte dintr-un efort intelectual. Numai atunci compoziția este utilă, permițând designerilor să împărtășească acest efort intelectual.

Desenele compozite implică diferite tipuri de probleme. Aici suntem mai interesați de problema corectitudinii: Cum putem pretinde corectitudinea unui sistem din specificațiile componentelor sale sau, cu alte cuvinte, ce trebuie să știm din componente pentru a putea prezice comportamentul a unui sistem? Noi numim dovada compozițieio dovadă de corectitudine în cazul în care corectitudinea sistemului este dedusă din specificațiile componentelor. Din nou, orice dovadă de corectitudine este, într-un anumit sens, o dovadă a compoziției: întotdeauna folosim anumite cunoștințe ale componentelor pentru a dovedi un sistem. Ca și înainte, adăugăm o altă constrângere: Vrem ca componentele să conțină o parte din dovada corectitudinii, deoarece ar trebui să conțină o parte din design. Cu alte cuvinte, vrem să construim dovezi de compoziție din declarațiile deja demonstrate la nivelul componentelor, fără a trebui să repetăm ​​oricare dintre aceste dovezi. Această imagine descrie specificațiile și dovezile într-un design compozițional:

Intuitiv, cantitatea efortului de probă în probele de compoziție va depinde de modul în care sunt specificate componentele. Dacă o specificație a componentei este doar o descriere oficială a implementării (adică textul programului în sine, cu o semantică bine definită), cum ar fi un program UNITY sau un proces CSP, nici o parte din efortul de probă nu este realizată la componenta nivel și designerii trebuie să se ocupe de o descriere operațională și explicită a comportamentului componentelor atunci când construiesc dovada compoziției. Specificațiile componentelor trebuie să fie abstracții ale comportamentului componentelor. Ei trebuie să descrie fapte utile despre o componentă, fapte care trebuie demonstratedin textul componentei. Apoi, aceste fapte sunt folosite într-o dovadă a compoziției, fără obligația de a le dovedi din nou.

De fapt, împărțirea efortului de testare nu necesită un design compozițional. Este perfect posibil să se împartă efortul de a face dovada monolitică. În acest caz, se pornește de la o specificare a sistemului complet și o descriere operațională a sistemului complet și se deduce oobligație globală de probă. Această obligație de probă este ea însăși descompusă, iar dovada corectitudinii este construită din lemne și rezultate intermediare. Această abordare a fost investigată, de exemplu, de Leslie Lamport cu probe TLA +.

Cu toate acestea, abordarea pe care o considerăm aici, care presupune specificarea și dovedirea componentelor ca un prim pas și apoi construirea unei dovezi de compoziție, prezintă (potențial) un alt avantaj. Un obiectiv al proiectelor compoziționale, dar nerealizat, este de a reutiliza componentele, adică de a construi sisteme din componente deja existente, eventual componente deja folosite pentru a construi alte sisteme. Ideea este că nu se începe tăierea copacilor atunci când se construiește o casă: cerințele sunt specificate și componentele sunt cumpărate deja făcute (sau, cel puțin, sunt fabricate independent). Dacă o astfel de reutilizare a componentelor devine posibilă, atunci abordarea aleasă permite proiectanților să reutilizezepărți de dovadă de corectitudine atunci când reutilizează componentele, și anume dovada corectitudinii componentelor (“dovezile T” din imagine). Cu cât partea este mai mare (comparativ cu dovada compoziției în sine), cu atât mai bine, acesta fiind un alt motiv pentru care specificațiile componentelor ar trebui să fie abstracte și explicite explicit din textele programelor. (Totuși, un alt motiv este faptul că specificațiile abstracte permit proiectanților să exprime exact ceea ce așteaptă de la componente și să evite supra-specificarea cerințelor lor. Acest lucru este necesar dacă doresc să crească șansele lor de a găsi o componentă existentă care să le rezolve problema.)

Dificultatea unei astfel de abordări este că specificațiile nu se pot compune foarte bine. Este posibil ca nicio proprietate a sistemului (non trivial) să nu poată fi dedusă logic din proprietățile componentelor. Pentru abordarea de lucru, specificațiile componentelor trebuie să permită proiectanților să deducă proprietățile sistemului. Unele specificații ale componentelor, deoarece nu conțin suficiente informații, nu permit această deducere. Problema este că, pentru că vrem să fie abstracte , este posibil ca specificațiile componentelor să nu conțină suficiente informații. Există în mod clar un compromis între păstrarea specificațiilor abstracte și transformarea acestora într-o dovadă a compoziției: prea multe informații, prea multe detalii descoperite în caietul de sarcini și abstractizarea este pierdută; nu este suficient, iar compoziția este pierdută.

Cazul invariabil și întotdeauna

Pentru a ilustra echilibrul dintre abstractizare și abilitatea de a compune, luați în considerare cazul sistemelor (și componentelor) definite de calculul lor infinit (sisteme reactive), compuse prin compoziție paralelă. Pentru aceste sisteme, se folosesc deseori două tipuri de proprietăți strâns legate:

  • invariant: se spune că un predicat de stat este invariabil dacă:
    • acesta deține în starea inițială orice calcul și
    • adevărul său este păstrat de orice afirmație a sistemului.
  • întotdeauna: se spune că predicatul de stat este “întotdeauna adevărat” dacă este adevărat în orice stare de calcul al sistemului.

În lumea logicii temporale, proprietățile întotdeauna sunt deseori numite “invariante”, în timp ce proprietățile invariante sunt numite “invarianți inductivi”. În celălalt capăt, în lumea verificării secvențiale a programelor, proprietățile invariante sunt numite “invariante” și întotdeauna proprietățile de multe ori nu au un nume. (Totuși, ele se numesc “afirmații” în metoda B). Aceasta a dus la o anumită confuzie (a se vedea pagina axiomului de substituție ).

În mod natural, întotdeauna și invariabil sunt legate: orice predicat care este invariabil este de asemenea întotdeauna adevărat (prin inducție). Cu toate acestea, un predicat poate fi întotdeauna adevărat și nu poate fi invariabil. Aceasta înseamnă că întotdeauna proprietățile suntmai slabîn general, decât proprietățile invariabile. Ele sunt, de asemenea, mai abstracte: afirmă că un predicat este adevărat în orice stare de calcul, dar ei nu spun de ce. Proprietățile invariabile spun de ce. Cu alte cuvinte, proprietățile invariante reprezintă un instrument util pentru a dovedi întotdeauna proprietăți, dar ele nu sunt suficient de abstracte pentru a fi utilizate pentru a specifica componente.

În ceea ce privește compoziția, proprietățile invariabile și întotdeauna diferă. Deoarece declarațiile de program sunt conservate prin compoziție paralelă, predicatul de stare este invariabil într-un sistem de îndată ce este invariabil în toate componentele sistemului (în vocabularul nostru, proprietățile invariante se consideră universale ). Deoarece un sistem concurent poate avea mai multe stări accesibile decât componentele sale, acest lucru nu este valabil pentru proprietățile întotdeauna: un predicat poate fi întotdeauna adevărat în toate componentele unui sistem și falsificat de sistemul concurențial la nivel global.

Pentru a rezuma, proprietățile invariante pot fi compuse, dar ele sunt prea puternice (nu suficient de abstracte) pentru a fi utilizate în specificațiile componentelor; proprietățile întotdeauna sunt de fapt abstractizarea necesară, dar ele nu pot fi compuse. (O întrebare utilă este aceea de a determina ce proprietăți sunt mai slabe decât proprietățile invariabile, mai puternice decât întotdeauna proprietățile și care pot fi încă compuse.) Această întrebare nu este la fel de simplă cum se pare că cititorii sunt invitați să încerce să rezolve o întrebare provocatălegată de acest lucru problema.)

Cercetarea noastră

În studiul nostru, Mani Chandy și cu mine am abordat următoarea problemă: putem găsi proprietăți ale componentelor suficient de puternice pentru a fi compuse, dar suficient de slabe pentru a păstra abstractizarea? Mai precis, ne concentrăm pe două forme de compoziție: existențial (o proprietate existențială deținută într-un sistem de îndată ce se află în cel puțin o componentă) și universală (o proprietate universală deținută într-un sistem de îndată ce se află în toate componentele) . Considerăm aceste două forme de compoziție într-un context general. Componentele sunt entități abstracte, nu neapărat programe. Nu trebuie să aibă atribute precum “state” sau “calcule”. Ele sunt compuse dintr-o lege a compoziției care nu se presupune a fi compoziție paralelă (în special, nu se presupune că este simetrică sau idempotentă).

În aceste ipoteze pot fi explorate rezultate interesante (și chiar și întrebări mai interesante). Acest cadru poate fi aplicat sistemelor reactive și logicii temporale ; în special, cazul invarianților , discutat mai sus, poate fi frumos exprimat. Aceste idei pot fi, de asemenea, generalizate atunci când mai multe legi ale compoziției sunt utilizate împreună.