[ Pobierz całość w formacie PDF ]
.Van Roy and S.Haridi.All rights reserved. 2.8 Exercises 111Check your understanding by running this example in Mozart.8.This exercise explores the relationship between linguistic abstractions andhigher-order programming.(a) Define the function AndThen as follows:fun {AndThen BP1 BP2}if {BP1} then {BP2} else false endendDoes the following call:{AndThen fun {$} expression 1 endfun {$} expression 2 end}give the same result as expression 1 andthen expression 2? Does itavoid the evaluation of expression 2 in the same situations?(b) Write a functionOrElsethat is toorelseasAndThenis toandthen.Explain its behavior.9.This exercise examines the importance of tail recursion, in the light of thesemantics given in the chapter.Consider the following two functions:fun {Sum1 N}if N==0 then 0 else N+{Sum1 N-1} endendfun {Sum2 N S}if N==0 then S else {Sum2 N-1 N+S} endend(a) Expand the two definitions into kernel syntax.It should be clear thatSum2 is tail recursive and Sum1 is not.(b) Execute the two calls {Sum1 10} and {Sum2 10 0} by hand, usingthe semantics of this chapter to follow what happens to the stack andthe store.How large does the stack become in either case?(c) What would happen in the Mozart system if you would call {Sum1100000000}or {Sum2 100000000 0}? Which one is likely to work?Which one is not? Try both on Mozart to verify your reasoning.10.Consider the following function SMerge that merges two sorted lists:fun {SMerge Xs Ys}case Xs#Ysof nil#Ys then Ys[] Xs#nil then Xs[] (X|Xr)#(Y|Yr) thenCopyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 112 Declarative Computation Modelif X=Y then Z=X else Z=Y endis declarative.Partition the statement s three free identifiers, X, Y, Z, into twoinput identifiers X and Y and one output identifier Z.Then, if X and Y are boundto any partial values, the statement s execution will either block or bind Z to thesame partial value.Therefore the statement is declarative.We can do this reasoning for all operations in the declarative model:" First, all basic operations in the declarative model are declarative.Thisincludes all operations on basic types, which are explained in Chapter 2." Second, combining declarative operations with the constructs of the declar-ative model gives a declarative operation.The following five compoundstatements exist in the declarative model: The statement sequence. The local statement. The if statement. The case statement. Procedure declaration, i.e., the statement x = v where v is a pro-cedure value.They allow building statements out of other statements.All these ways ofcombining statements are deterministic (if their component statements aredeterministic, then so are they) and they do not depend on any context.3.2 Iterative computationWe will now look at how to program in the declarative model.We start bylooking at a very simple kind of program, the iterative computation.An iterativecomputation is a loop whose stack size is bounded by a constant, independentof the number of iterations.This kind of computation is a basic programmingtool.There are many ways to write iterative programs.It is not always obviouswhen a program is iterative.Therefore, we start by giving a general schema thatshows how to construct many interesting iterative computations in the declarativemodel.3.2.1 A general schemaAn important class of iterative computations starts with an initial state S0 andtransforms the state in successive steps until reaching a final state Sfinal:S0 ’! S1 ’! · · · ’! SfinalAn iterative computation of this class can be written as a general schema:Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 3.2 Iterative computation 121fun {Sqrt X}Guess=1.0in{SqrtIter Guess X}endfun {SqrtIter Guess X}if {GoodEnough Guess X} then Guesselse{SqrtIter {Improve Guess X} X}endendfun {Improve Guess X}(Guess + X/Guess) / 2.0endfun {GoodEnough Guess X}{Abs X-Guess*Guess}/X 0 then {FactIter N-1 A*N}else raise domainError endendendin{FactIter N 1}endThe function that does the iteration, FactIter, has a second argument A.Thisargument is crucial; without it an iterative factorial is impossible.The secondargument is not apparent in the simple mathematical definition of factorial weused first.We had to do some reasoning to bring it in.3.4 Programming with recursionRecursive computations are at the heart of declarative programming.This sectionshows how to write in this style.We show the basic techniques for programmingwith lists, trees, and other recursive data types.We show how to make thecomputation iterative when possible.The section is organized as follows:" The first step is defining recursive data types.Section 3.4.1 gives a simplenotation that lets us define the most important recursive data types." The most important recursive data type is the list.Section 3.4.2 presentsthe basic programming techniques for lists." Efficient declarative programs have to define iterative computations.Sec-tion 3.4.3 presents accumulators, a systematic technique to achieve this." Computations often build data structures incrementally.Section 3.4.4 presentsdifference lists, an efficient technique to achieve this while keeping thecomputation iterative." An important data type related to the list is the queue.Section 3.4.5shows how to implement queues efficiently.It also introduces the basic ideaof amortized efficiency." The second most important recursive data type, next to linear structuressuch as lists and queues, is the tree.Section 3.4.6 gives the basic program-ming techniques for trees." Sections 3.4.7 and 3.4.8 give two realistic case studies, a tree drawingalgorithm and a parser, that between them use many of the techniques ofthis section.Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 3.4 Programming with recursion 1313.4.1 Type notationThe list type is a subset of the record type.There are other useful subsets ofthe record type, e.g., binary trees.Before going into writing programs, let usintroduce a simple notation to define lists, trees, and other subtypes of records.This will help us to write functions on these types.A list Xs is either nil or X|Xr where Xr is a list.Other subsets of the recordtype are also useful.For example, a binary tree can be defined as leaf(key:Kvalue:V)ortree(key:K value:V left:LT right:RT)where LTandRTareboth binary trees.How can we write these types in a concise way? Let us createa notation based on the context-free grammar notation for defining the syntax ofthe kernel language.The nonterminals represent either types or values.Let ususe the type hierarchy of Figure 2.16 as a basis: all the types in this hierarchywill be available as predefined nonterminals.So Value and Record both exist,and since they are sets of values, we can say Record ‚" Value.Now we candefine lists:List ::= Value ´|´ List| nilThis means that a value is in List if it has one of two forms.Either it is X|Xrwhere X is in Value and Xris in List.Or it is the atomnil.This is a recursivedefinition of List.It can be proved that there is just one set List that is thesmallest set that satisfies this definition.The proof is beyond the scope of thisbook, but can be found in any introductory book on semantics, e.g., [208].Wetake this smallest set as the value of List.Intuitively, List can be constructedby starting with nil and repeatedly applying the grammar rule to build biggerand bigger lists.We can also define lists whose elements are of a given type:List T ::= T ´|´ List T| nilHere T is a type variable and List T is a type function.Applying the type func-tion to any type returns the type of a list of that type.For example, List Intis the list of integer type [ Pobierz caÅ‚ość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl odbijak.htw.pl
.Van Roy and S.Haridi.All rights reserved. 2.8 Exercises 111Check your understanding by running this example in Mozart.8.This exercise explores the relationship between linguistic abstractions andhigher-order programming.(a) Define the function AndThen as follows:fun {AndThen BP1 BP2}if {BP1} then {BP2} else false endendDoes the following call:{AndThen fun {$} expression 1 endfun {$} expression 2 end}give the same result as expression 1 andthen expression 2? Does itavoid the evaluation of expression 2 in the same situations?(b) Write a functionOrElsethat is toorelseasAndThenis toandthen.Explain its behavior.9.This exercise examines the importance of tail recursion, in the light of thesemantics given in the chapter.Consider the following two functions:fun {Sum1 N}if N==0 then 0 else N+{Sum1 N-1} endendfun {Sum2 N S}if N==0 then S else {Sum2 N-1 N+S} endend(a) Expand the two definitions into kernel syntax.It should be clear thatSum2 is tail recursive and Sum1 is not.(b) Execute the two calls {Sum1 10} and {Sum2 10 0} by hand, usingthe semantics of this chapter to follow what happens to the stack andthe store.How large does the stack become in either case?(c) What would happen in the Mozart system if you would call {Sum1100000000}or {Sum2 100000000 0}? Which one is likely to work?Which one is not? Try both on Mozart to verify your reasoning.10.Consider the following function SMerge that merges two sorted lists:fun {SMerge Xs Ys}case Xs#Ysof nil#Ys then Ys[] Xs#nil then Xs[] (X|Xr)#(Y|Yr) thenCopyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 112 Declarative Computation Modelif X=Y then Z=X else Z=Y endis declarative.Partition the statement s three free identifiers, X, Y, Z, into twoinput identifiers X and Y and one output identifier Z.Then, if X and Y are boundto any partial values, the statement s execution will either block or bind Z to thesame partial value.Therefore the statement is declarative.We can do this reasoning for all operations in the declarative model:" First, all basic operations in the declarative model are declarative.Thisincludes all operations on basic types, which are explained in Chapter 2." Second, combining declarative operations with the constructs of the declar-ative model gives a declarative operation.The following five compoundstatements exist in the declarative model: The statement sequence. The local statement. The if statement. The case statement. Procedure declaration, i.e., the statement x = v where v is a pro-cedure value.They allow building statements out of other statements.All these ways ofcombining statements are deterministic (if their component statements aredeterministic, then so are they) and they do not depend on any context.3.2 Iterative computationWe will now look at how to program in the declarative model.We start bylooking at a very simple kind of program, the iterative computation.An iterativecomputation is a loop whose stack size is bounded by a constant, independentof the number of iterations.This kind of computation is a basic programmingtool.There are many ways to write iterative programs.It is not always obviouswhen a program is iterative.Therefore, we start by giving a general schema thatshows how to construct many interesting iterative computations in the declarativemodel.3.2.1 A general schemaAn important class of iterative computations starts with an initial state S0 andtransforms the state in successive steps until reaching a final state Sfinal:S0 ’! S1 ’! · · · ’! SfinalAn iterative computation of this class can be written as a general schema:Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 3.2 Iterative computation 121fun {Sqrt X}Guess=1.0in{SqrtIter Guess X}endfun {SqrtIter Guess X}if {GoodEnough Guess X} then Guesselse{SqrtIter {Improve Guess X} X}endendfun {Improve Guess X}(Guess + X/Guess) / 2.0endfun {GoodEnough Guess X}{Abs X-Guess*Guess}/X 0 then {FactIter N-1 A*N}else raise domainError endendendin{FactIter N 1}endThe function that does the iteration, FactIter, has a second argument A.Thisargument is crucial; without it an iterative factorial is impossible.The secondargument is not apparent in the simple mathematical definition of factorial weused first.We had to do some reasoning to bring it in.3.4 Programming with recursionRecursive computations are at the heart of declarative programming.This sectionshows how to write in this style.We show the basic techniques for programmingwith lists, trees, and other recursive data types.We show how to make thecomputation iterative when possible.The section is organized as follows:" The first step is defining recursive data types.Section 3.4.1 gives a simplenotation that lets us define the most important recursive data types." The most important recursive data type is the list.Section 3.4.2 presentsthe basic programming techniques for lists." Efficient declarative programs have to define iterative computations.Sec-tion 3.4.3 presents accumulators, a systematic technique to achieve this." Computations often build data structures incrementally.Section 3.4.4 presentsdifference lists, an efficient technique to achieve this while keeping thecomputation iterative." An important data type related to the list is the queue.Section 3.4.5shows how to implement queues efficiently.It also introduces the basic ideaof amortized efficiency." The second most important recursive data type, next to linear structuressuch as lists and queues, is the tree.Section 3.4.6 gives the basic program-ming techniques for trees." Sections 3.4.7 and 3.4.8 give two realistic case studies, a tree drawingalgorithm and a parser, that between them use many of the techniques ofthis section.Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 3.4 Programming with recursion 1313.4.1 Type notationThe list type is a subset of the record type.There are other useful subsets ofthe record type, e.g., binary trees.Before going into writing programs, let usintroduce a simple notation to define lists, trees, and other subtypes of records.This will help us to write functions on these types.A list Xs is either nil or X|Xr where Xr is a list.Other subsets of the recordtype are also useful.For example, a binary tree can be defined as leaf(key:Kvalue:V)ortree(key:K value:V left:LT right:RT)where LTandRTareboth binary trees.How can we write these types in a concise way? Let us createa notation based on the context-free grammar notation for defining the syntax ofthe kernel language.The nonterminals represent either types or values.Let ususe the type hierarchy of Figure 2.16 as a basis: all the types in this hierarchywill be available as predefined nonterminals.So Value and Record both exist,and since they are sets of values, we can say Record ‚" Value.Now we candefine lists:List ::= Value ´|´ List| nilThis means that a value is in List if it has one of two forms.Either it is X|Xrwhere X is in Value and Xris in List.Or it is the atomnil.This is a recursivedefinition of List.It can be proved that there is just one set List that is thesmallest set that satisfies this definition.The proof is beyond the scope of thisbook, but can be found in any introductory book on semantics, e.g., [208].Wetake this smallest set as the value of List.Intuitively, List can be constructedby starting with nil and repeatedly applying the grammar rule to build biggerand bigger lists.We can also define lists whose elements are of a given type:List T ::= T ´|´ List T| nilHere T is a type variable and List T is a type function.Applying the type func-tion to any type returns the type of a list of that type.For example, List Intis the list of integer type [ Pobierz caÅ‚ość w formacie PDF ]