Hoare ( 1969) contains a generous acknowledgement to the influence of Floyd ( 1967) Footnote 3 but Hoare’s “axiomatic approach” offers a clear path to a development approach that is described in Sect. Footnote 2 As such, the approach to verification is “ post facto”: a program is written and only after its creation is it subjected to formal reasoning. The starting point for Floyd ( 1967) is a flowchart of a program to which “state assertions” are added that justify that any execution of the program will be in accord with the assertions. The assertion at the end of the program is a “post condition” describing the overall effect of the program few programs work for all possible inputs and the assertion at the beginning of the program is its “pre condition”.Īlthough strongly related, there is a crucial distinction between the approaches of Bob Floyd and Tony Hoare to the verification of sequential programs. State assertions can be used as annotations on a program and their consistency can be checked against the meaning of the program. Footnote 1 Common to both approaches is the use of state assertions that are predicates defining relationships between the values of variables. The reference points for formal verification of sequential (non-concurrent) programs are taken here as Floyd ( 1967) and Hoare ( 1969). One issue which dogs all three chosen approaches is “atomicity” and this is discussed in Sect. 2 and 3 are brief and are revisited in Sects. For this reason, the initial descriptions in Sects. This is attempted by bringing the three approaches to bear on a common example presented in Owicki’s PhD thesis. The objective is to convey-at least in outline-the technical contribution of each of the three approaches. Readers might find the apparent linearity of these ideas suspicious this point is addressed in the concluding section. The three chosen sources contain key insights on concurrency and represent progress in practicality. Extensive other work by, for example, Carl Adam Petri is not even referenced. There is no attempt in the current paper to identify “firsts”. ![]() ![]() 3 and Susan Owicki’s contribution in Sect. 2, a solo publication by Ashcroft in Sect. The main purpose of the current paper is to review three early approaches to the verification of concurrent programs (joint work by Ed Ashcroft and Zohar Manna is described in Sect. “Interference” is identified as a key technical challenge to reasoning about concurrency in Sect. Contextually there was pressure from machines becoming large enough to run multiple processes, from the ability to link machines and-crucially-from applications. Around 1970, the technical challenges of extending such formal approaches to tackle the verification of concurrent software came into focus. Research in the late 1960s provided a firm basis for showing that sequential programs satisfied their specifications (key papers by Bob Floyd and Tony Hoare are briefly outlined in Sects.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |