A Practical Theory of Programming by Eric C.R. Hehner

By Eric C.R. Hehner

Figuring out programming and programming languages calls for wisdom of the underlying theoretical version. This publication explores points of programming which are amenable to mathematical evidence. the writer describes a programming thought that is a lot easier and extra finished than the present theories thus far. within the theoretical version, a specification is simply a boolean expression and refinement is simply a normal implication. the writer develops a realistic and huge approach for writing exact requisites and designing courses whose executions most likely fulfill the standards. starting with preparatory fabric in common sense, numbers, units, lists, services and kin, the e-book advances extra into software idea, the guts of the booklet. next chapters can be chosen or passed over in keeping with direction emphasis. The textual content can be helpful to scholars in classes on programming technique or verification on the complicated undergraduate or starting graduate point, in addition to for software program engineers within the box. All technical phrases are defined after which tested within the ebook anywhere attainable. No complex mathematical wisdom or programming language is thought. The ebook includes quite a few workouts and worked-out suggestions for particular workouts. Transparency masters and strategies for the remainder routines can be found from the writer.

Show description

Read Online or Download A Practical Theory of Programming PDF

Similar children's ebooks books

Write Your Own Poetry

No subject is off-limits in poetry. no matter if you must write poems that make humans snort out loud, gasp in shock, or see issues in a brand new manner, this booklet is for you. overcome the clean web page and convey your suggestions, emotions, and observations within the magical international of poetry.

What Can Live in a Grassland? (First Step Nonfiction: Animal Adaptations)

Lions, and zebras, and termites, oh my! See why a grassland is an ideal habitat for those animals and extra.

The Johnstown Flood of 1889 (Great Historic Disasters)

On may well 31, 1889, the folks of Johnstown, Pennsylvania, obtained the shock of the century, one who claimed the lives of greater than 2,200 males, ladies, and kids. within the mountains that missed the booming coal-and-steel city, the stressed waters of Lake Conemaugh churned in the back of the South Fork Dam, a rapidly outfitted earthen constitution.

Additional info for A Practical Theory of Programming

Sample text

For x′, y′, ... in S ) ∧ (substitute x′′, y′′, ... for x, y, ... in R ) 37 4 Program Theory Here's an example. In one integer variable x , the specification x′=x ∨ x′=x+1 says that the final value of x is either the same as the initial value or one greater. Let's compose it with itself. x′=x ∨ x′=x+1 . x′=x ∨ x′=x+1 = ∃x′′· (x′′=x ∨ x′′=x+1) ∧ (x′=x′′ ∨ x′=x′′+1) distribute ∧ over ∨ = ∃x′′· x′′=x ∧ x′=x′′ ∨ x′′=x+1 ∧ x′=x′′ ∨ x′′=x ∧ x′=x′′+1 ∨ x′′=x+1 ∧ x′=x′′+1 distribute ∃ over ∨ = (∃x′′· x′′=x ∧ x′=x′′) ∨ (∃x′′· x′′=x+1 ∧ x′=x′′) ∨ (∃x′′· x′′=x ∧ x′=x′′+1) ∨ (∃x′′· x′′=x+1 ∧ x′=x′′+1) One-Point, 4 times = x′=x ∨ x′=x+1 ∨ x′=x+2 If we either leave x alone or add 1 to it, and then again we either leave x alone or add 1 to it, the net result is that we either leave it alone, add 1 to it, or add 2 to it.

The exact precondition is therefore the necessary and sufficient precondition, and similarly for postconditions. 41 4 Program Theory Exercise 112(c) asks for the exact precondition and postcondition for x:= x2 to move integer variable x farther from zero. To answer, we must first state formally what it means to move x farther from zero: abs x′ > abs x (where abs is the absolute value function; its definition can be found in Chapter 11). We now calculate (the exact precondition for abs x′ > abs x to be refined by x:= x2 ) = ∀x′· abs x′ > abs x ⇐ x′ = x2 One-Point Law 2 = abs (x ) > abs x by the arithmetic properties of abs x and x2 = x –1 ∧ x 0 ∧ x 1 (the exact postcondition for abs x′ > abs x to be refined by x:= x2 ) = ∀x· abs x′ > abs x ⇐ x′ = x2 after several steps including domain splitting and variable change and using the arithmetic properties of abs x and x2 = x′ 0 ∧ x′ 1 If x starts anywhere but –1 , 0 , or 1 , we can be sure it will move farther from zero; if x ends anywhere but 0 or 1 , we can be sure it did move farther from zero.

P = 〈x→P〉e The Substitution Law says that an assignment followed by any specification is the same as the specification but with the assigned variable replaced by the assigned expression. Exercise 97 illustrates all the difficult cases, so let us do the exercise. The state variables are x and y . (a) x:= y+1. y′>x′ Since x does not occur in y′>x′ , replacing it is no change. = y′>x′ (b) x:= x+1. y′>x ∧ x′>x Both occurrences of x in y′>x ∧ x′>x must be replaced by x+1 . = y′ > x+1 ∧ x′ > x+1 (c) x:= y+1.

Download PDF sample

Rated 4.61 of 5 – based on 42 votes