Compositionality, Concurrency and Partial Correctness: Proof Theories for Networks of Processes, and Their Relationship

تجزیه سلسله مراتبی برنامه ها به برنامه های کوچکتر معمولاً برای تسلط بر پیچیدگی برنامه های بزرگ ضروری است. تأثیر این اصل تجزیه برنامه بر مشخصات و تأیید برنامه های اجرا شده موازی موضوع این مقاله است. دو معیار مهم برای روش‌های راستی‌آزمایی، ترکیب‌بندی و مدولار بودن، دقیق ساخته شده‌اند. مشکل استفاده مجدد از نرم افزار با معرفی مفهوم تطبیق مشخصات مورد توجه قرار می گیرد. در این زمینه، روش‌های مختلفی برای تعیین رفتار قابل مشاهده با توجه به صحت جزئی فرآیندهای ارتباطی در نظر گرفته می‌شود و به ویژه تضاد بین پارادایم‌های \"برنامه‌ها محمول هستند\" و \"برنامه‌ها ترانسفورماتورهای محمول هستند\" نشان داده می‌شود. سیستم‌های اثبات رسمی مرتبط با توجه به معنی‌شناسی معنایی زبان برنامه‌نویسی از نظر معانی مختلف سالم و کامل هستند و برای مقایسه عمیق بین سبک‌های مختلف تأیید برنامه با یکدیگر مرتبط هستند. زبان برنامه نویسی TNP که در اینجا استفاده می شود نزدیک به زبان های واقعی مانند Occam است. این برنامه‌نویسی مبتنی بر ارتباط به سبک CCS/CSP را با برنامه‌نویسی مبتنی بر حالت ترکیب می‌کند و به طور پویا امکان گسترش و کوچک شدن شبکه‌های فرآیندها را می‌دهد.

The hierarchical decomposition of programs into smaller ones is generally considered imperative to master the complexity of large programs. The impact of this principle of program decomposition on the specification and verification of parallel executed programs is the subject of this monograph. Two important yardsticks for verification methods, those of compositionality and modularity, are made precise. The problem of reusing software is addressed by the introduction of the notion of specification adaptation. Within this context, different methods for specifying the observable behavior with respect to partial correctness of communicating processes are considered, and in particular the contrast between the "programs are predicates" and the "programs are predicate transformers" paradigms is shown. The associated formal proof systems are proven sound and complete in various senses with respect to the denotational semantics of the programming language, and they are related to each other to give an in-depth comparison between the different styles of program verification. The programming language TNP used here is near to actual languages like Occam. It combines CCS/CSP style communication based programming with state based programming, and allows dynamically expanding and shrinking networks of processes.