 By David Harel (auth.), Johan Jeuring (eds.)

ISBN-10: 3540645918

ISBN-13: 9783540645917

This booklet consitutes the refereed court cases of the 4th foreign convention on arithmetic of application development, MPC'98, held in Marstrand, close to Goteborg, Sweden, in June 1998. The 17 revised complete papers awarded have been chosen from fifty seven submissions; additionally incorporated are 3 invited contributions. the quantity is dedicated to using crisp, transparent arithmetic within the discovery and layout of algorithms and within the improvement of corresponding software program and undefined; varoius methods to formal tools for platforms layout and research are covered.

Read Online or Download Mathematics of Program Construction: 4th International Conference, MPC'98 Marstrand, Sweden, June 15–17, 1998 Proceedings PDF

Similar mathematics books

On the communication of mathematical reasoning by Bagchi, Wells. PDF

This text discusses a few tools of describing and concerning mathematical gadgets and of regularly and unambiguously signaling the logical constitution of mathematical arguments.

Additional info for Mathematics of Program Construction: 4th International Conference, MPC'98 Marstrand, Sweden, June 15–17, 1998 Proceedings

Sample text

In a regular datatype declaration, occurrences of the declared type on the right-hand side of the defining equation are restricted to copies of the left-hand side, so the recursion is “tail recursive”. In a nested datatype declaration, occurrences of the datatype on the right-hand side appear with different instances of the accompanying type parameter(s), so the recursion is “nested”. In a language like Haskell or ML, with a Hindley-Milner type discipline, it is simply not possible to define all the useful functions one would like over a nested datatype, even though such datatype declarations are themselves perfectly legal.

Let W be the pre-order that w induces on E. If ρ is the order on real numbers and w is conceived as function in the relational sense then W can be defined by the formula W =df wρw∪ . The relational expression describing the set of all minimal elements of a set p wrt a preorder W is well-known (see ): Lemma 15 If we define least(p) =df p ∩ W p then (7) holds for every p ∈ E. This completes the development of a minimum spanning tree algorithm. In the next section we will use Tarski’s relational calculus for rigorously proving the lemmata used in its derivation.

The type Term a is nested because Bind a appears as a parameter of Term on the right-hand side of the declaration. x (w y) may be represented by the following term of type Term Char : Abs (Abs (App (Var Zero, App (Var (Succ (Succ ‘w’)), Var (Succ Zero))))) The closed lambda terms – those containing no free variables – are elements of Term Empty, where Empty is the empty type containing no members. The function abstract, which takes a term and a variable and abstracts over that variable, can be defined in the following way: abstract :: (Term a, a) → Term a abstract (t , x ) = Abs (lift (t, x )) Nested Datatypes 55 The function lift is defined by lift :: (Term a, a) → Term (Bind a) lift (Var y, x ) = if x = y then Var Zero else Var (Succ y) lift (App (u, v), x ) = App (lift (u, x ), lift (v, x )) lift (Abs t, x ) = Abs (lift (t, Succ x )) The β-reduction of a term is implemented by reduce :: (Term a, Term a) → Term a reduce (Abs s, t) = subst (s, t ) where subst :: (Term (Bind a), Term a) → Term a subst (Var Zero, t ) =t subst (Var (Succ x ), t ) = Var x subst (App (u, v), t) = App (subst (u, t), subst (v, t)) subst (Abs s, t) = Abs (subst (s, term Succ t)) The function term f maps f over a term: term :: (a → b) → (Term a → Term b) term f (Var x ) = Var (f x ) term f (App (u, v)) = App (term f u, term f v) term f (Abs t) = Abs (term (bind f ) t) The subsidiary function bind f maps f over elements of Bind a: bind :: (a → b) → (Bind a → Bind b) bind f Zero = Zero bind f (Succ x ) = Succ (f x ) It is a routine induction to show that reduce (abstract (t , x ), Var x ) = t for all terms t of type Term a and all x of type a.