Prog&Data Struct EECS 280
Popular in Course
Popular in Engineering Computer Science
This 51 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 280 at University of Michigan taught by Staff in Fall. Since its upload, it has received 13 views. For similar materials see /class/231545/eecs-280-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Prog&Data Struct
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
Slides by Brian Noble M Jeff Ringenberg and Andrew DeOrio EECS 280 Programming and Introductory Data Structures Procedural Abstraction and Recursion Abstraction 0 Abstraction is a manytoone mapping that reduces complexity and eliminates unnecessary details by providing only those details that matter 0 For example there are several ways to implement a multiplication algorithm table lookup summing etc Each looks quite different internally than the other but they do the same thing In general a user won t care how it s done just that it multiplies 0 There are two types of abstraction 0 Procedural the topic of the next three weeks 0 Data Procedural Abstraction 0 Decomposing a program into functions is a way of providing computational abstractions Rather than simply being collections of commonly used code functions provide a useful tool for implementing procedural abstraction Within a program Procedural Abstraction For any function there is a person who implements the function the author and a person Who uses the function the client 0 The author needs to think carefully about What the function is supposed to do as well as how the function is going to do it 0 In contrast the client only needs to consider the What not the how Since how is much more complicated this is a Big Win for the client 0 In individual programming you will often be the author and the client Sometimes it is to your advantage to forget the details and only concentrate on higher levels of functionality Procedural Abstraction 0 Procedural abstractions done properly have two important properties 0 Local the implementation of an abstraction can be understood without examining any other abstraction implementation 0 Substitutable you can replace one correct implementation of an abstraction with another correct one and no callers of that abstraction will need to be modified 0 These properties only apply to implementations of abstractions not the abstractions themselves 0 It is CRITICALLY IMPORTANT to get the abstractions right before you start writing a bunch of code 0 If you change the abstraction that is offered the change is not local nor is the new version substitutable Procedural Abstraction 0 Unfortunately abstraction limits the scope of change 0 If you need to change What a procedural abstraction does it can involve many different changes in the program 0 However if a change can be limited to replacing the implementation of an abstraction with a substitutable implementation then you are guaranteed that no other part of the project needs to change This is vital for projects that involve many programmers Function Definitions vs Declarations In small programs often we just define functions before they are used 0 In larger programs it is useful to separate the declaration of a function from its definition A declaration provides the type signature of a function also called the function header 0 Function headers can be placed in their own file and accessed using the preprocessor directive include Function Definitions vs Declarations Example ioh double GetParamstring prompt double min double max 0 I iocpp quotioohquot double GetParamstring prompt double min include double max plcpp include quotiohquot int main GetParamprompt min max Function Details 0 All C functions take zero or more arguments and return a result of some type 0 There is a special type called void that means no result is returned void is still a type even though it is the type with no legal values 0 Typically a function39s signature de nes all of the state in the form of explicit arguments needed by the procedure to accomplish its goal However sometimes there are also implicit arguments elements of the global environment that are used by the procedure Function Details 0 The type signature of a function can be considered part of the abstraction if you change it customers callers must also change 0 However as long as a new implementation of an abstraction does the same thing as some old correct implementation you can replace the old one with the new one 0 Of course now we need to know what we mean by the same thing This boils down to describing the abstraction not implementation of the function We use speci cations to do this 1 Specifications 0 For a procedural abstraction a speci cation must answer three questions 0 What preconditions must hold to use the function 0 Does the function change any inputs even implicit ones If so how 0 What does the procedure actually do 0 We answer each of these three questions in a speci cation comment and we always include one with the declaration if it is separate from de nition Specification Comments 0 There are three clauses to the specification 0 REQUIRES the proconditions that must hold if any 0 MODIFIES how inputs are modi ed if any 0 EFFECTS what the procedure computes given legal inputs 0 Note that the rst two clauses have an if any which means they may be empty in which case you may omit them Specification Comment Example bool isEvenint n EFFECTS returns true if n is even false otherwise 0 This function returns true if and only if its argument is an even number We call functions that return true or false depending on some input property predicates 0 Since the predicate i sEven is welldefined over all inputs every possible integer is either even or odd there need be no REQUIRES clause 0 Since i sEven modifies no implicit or explicit arguments there need be no MODIFIES clause Specification Comment Example int factorialint n REQUIRES n gt 0 EFFECTS returns n 0 The mathematical abstraction factorial is only defined for non negative integers So we REQUIRE that the caller supply an argument greater than or equal to zero Factorial promises to compute n correctly for nonnegative integers only In other words the EFFECTS clause is only valid for inputs satisfying the REQUIRES clause Importantly this means that the implementation of factorial DOES NOT HAVE TO CHECK if n lt O The function specification tells the caller that she must pass a nonnegative integer More Function Details 0 Functions without REQUIRES clauses are considered complete they are valid for all input 0 Functions with REQUIRES clauses are considered partial some arguments that are quotlegalquot with respect to the type system are not legal with respect to the function 0 Whenever possible it is much better to write complete functions than partial ones 0 When we discuss exceptions we will see a way to convert partial functions to complete ones More Function Details 0 What about the MODIFIES clause 0 A MODIFIES clause identi es any function argument or piece of global state that might change if this function is called 0 For example this can happen with passbyreference as opposed to pass byvalue inputs Specification Comment Example void swapint ampx int ampy MODIFIES x y EFFECTS exchanges the values of x and y o The ampersand amp means that you get a reference to the caller39s argument not a copy of it This lets you to change the value of that argument ONOTEH w mamnumMcmmgnndhmmemgmmmjt must go in the MODIFIES clause Leave it out only if the function can never change it 0 This implies you should never use passby reference unless you intend to changetheinputnisonks ua on void swapintampx int ampy MODIFIES X y Call by reference 6 EFFECTS the values of X a d y int main int a4 b9 cout ltlt a ltlt ltlt b ltlt endl swapab cout ltlt a ltlt ltlt b ltlt endl 49 94 Call by reference example int main 29D void sw pint ampx int ampy i Call Stacks How function calls work 0 When we call a function using passbyvalue semantics the program follows these steps 1 Evaluate the actual arguments to the function order is not guaranteed 2 Create an activation record sometimes called a stack frame to hold the function39s formal arguments and local variables Copy the actuals39 values to the formals39 storage space Evaluate the function in its local scope Replace the function call with the result 9958 Destroy the activation record 21 Call Stacks 0 Activation records are typically stored as a stack 0 You can think of this process like plates in a cafeteria 0 Each time you clean a plate you add it to the top of the stack 0 Each time a new plate is needed it is taken from the top 0 Calling a function is like cleaning a plate 0 Returning from the function is like taking a plate 22 Call Stacks 0 Activation records work just like the plates example 0 When a function is called an activation record for this invocation is added to the top of the stack 0 When that function returns it39s record is removed from the top of the stack 0 In the meantime this function may have called other functions which create corresponding activation records These functions must return and destroy their corresponding activation records before this function can return 0 Note top is placed in quotes because by convention stacks are typically drawn growing down rather than up Call Stack Example int plusoneint X return xl int plustwoint X return 1 plusonex int main int result 0 result plustwoO cout ltlt result return O 24 Call Stack Example int plusoneint X return xl int plustwoint X return 1 plusonex int main int result 0 result plustwoO cout ltlt result return 0 Main starts outwith an activation record with room only for the local result main Z5 Call Stack Example int plusoneint X return xl int plustwoint X return 1 plusonex int main int result 0 result plustwoO cout ltlt result return 0 Then main calls plustw0 passing the literal value quot0 main plustw0 26 Call Stack Example int plusoneint X return xl int plustwoint X return 1 plusonex int main int result 0 result plustwoO cout ltlt result return 0 Which in turn calls p1us0ne main p1ustw0 x O p1usone Call Stack Example int plusoneint X return xl int plustwoint X return 1 plusonex int main int result 0 result plustwoO cout ltlt result return 0 p1us0ne adds one to X returning the value 1 main p1ustw0 p1usone x0 Z x39 Call Stack Example int plusoneint X return xl int plustwoint X return 1 plusonex int main int result 0 result plustwoO cout ltlt result return 0 p1usone s activation record is destroyed main p1ustwo 21 Call Stack Example int plusoneint X return xl int plustwoint X return 1 plusonex int main int result 0 result plustwoO cout ltlt result return 0 p1ustw0 adds one to the result and returns the value 2 main p1ustw0 Call Stack Example int plusoneint X return xl p1ustw0 s activation record is destroyed int plustwoint X InaHL lt1 plus CHEW int main int result 0 result plustwoO cout ltlt result return 0 Call Stack Example int plusoneint X return xl int plustwoint X return 1 plusonex int main int result 0 result plustwoO cout ltlt result return 0 main then prints the result main Some things to note 0 Even though plusone and plustwo both have formals called this presents no problem 0 Since environments are leXically scoped plusone cannot see plustwo39s X Instead a copy of plustwo39s X is passed to plusone and stored in plusone39s X 0 Neither plusone nor plustwo can see main39s result 0 Again environments are leXically scoped result is only accessible from Within main Recursion A convenient place for using stacks 0 Recursive just means refers to itself 0 So a function is recursive if it calls itself 0 Likewise a problem is recursive if 1 There is at least one trivial base or stopping case 2 All other cases can be solved by rst solving one or more smaller cases and then combining those solutions with a simple step Recursion A convenient place for using stacks 0 Recursive problems are those that are defined in terms of the problem itself and can be solved very elegantly simply and sometimes efficiently by recursive functions 0 This is the focus of the next few lectures and the core of the material you will need for project 2 Recursion Example 0 Consider the factorial function 0 C does not have a factorial operator neither do most other programming languages 0 So we have to gure out how to solve it 0 REQUIREMENT factorial is defined only for the domain of non negative integers this Will be assumed T1 3 niH 3 WHEN 3Hk1236 Iti391 k1 Recursion Example 0 Now consider the recursive de nition I n 0 quotI Z n nI n gt 0 o This is a recursive definition of factorial the function factorial is defined in terms of factorial itself Recursion Example I n 0 n nI n gt 0 0 There are two important features of this de nition 0 First there is one trivial stopping case that requires no computation 0 l 0 Second every other case can be solved by rst solving a smaller problem Where smaller means a problem that is closer to the trivial stopping case and then performing a simple additional computation on that smaller result to get the larger one This is called the recursive step or sometimes the inductive step 0 Because of these features converting to code is easy n lmLHIbUONH Recursion Example 1 n nI mw n n gt 0 int factorial int n REQUIRES n gt 0 EFFECTS computes n if n 0 return 1 base case else return nfactorialnl recursive step Recursion Example main X 0 Suppose we call our function as follows int main int x x factorial3 mme 40 Recursion Example 0 main calls factorial with an argument 3 0 We evaluate the actual argument create an activation record and copy the actual value to the formal main x factorial n m Recursion Example 0 Now we evaluate the body of factorial 0 n is not zero so we evaluate the alternate arm of the if statement Substituting for n and simplifying we get return 3 factorial2 0 So factorial must call factorial We follow the call a function protocol and create a new activation record for a new instance of factorial main x factorial n factorial r1 ilZ Recursion Example 0 Again n is not zero so we evaluate the arm again return 2 factorial1 main x factorial n factorial r1 factorial r1 Recursion Example 0 And again main x factorial n factorial r1 factorial r1 factorial n M Recursion Example 0 This time n is zero so we evaluate the consequence rather than the alternative 0 Return the value popping the most recent activation record off of the stack main x factorial n factorial r1 factorial r1 fa 39al nz Recursion Example 0 We called factorial with this statement as follows return 1 factorial0 0 But now we know the value of factorial0 so we can simplify to return 1 1 gt return 1 o This pops another frame off the stack main x factorial n factorial r1 f al a r1 46 Recursion Example Allowing us to complete this arm return 2 factorial1 gt return 2 1 gt return 2 0 Now pop off another frame main x factorial n f l a 39a n Recursion Example main X 0 Resolve the last pending fa a multiplication n return 3 factorial2 gt return 3 2 gt 0 That39s convenient since it is the correct answer 0 And don t forget that last pop il x39 Recursion Writing a function for the general case 0 Don t try to do it all in your head Instead treat it like an inductive proof 0 To write a correct recursive function do two things 1 Identify the trivial case or cases and write them explicitly 2 For all other cases rst assume there is a function that can solve smaller versions of the same problem then gure out how to get from the smaller solution to the bigger one 41 Recursion Another example 0 What if you needed to count the 1 bits in the binary representation of a nonnegative number 0 There are no 1 bits in the number zero so that39s our base case 0 To gure out the rest of the nonnegative integers let s think about the representation 0 There are 32 bits from least to most signi cant LSB to MSB The value of the number is 1LSB 22ndLSB 43rdLSB 231MSB Recursion Another example 0 Given the representation 1LSB 22ndLSB 43rdLSB 231MSB 1 If N is odd its least signi cant bit is 1 otherwise it is zero 2 An even number divided by two has the same number of ls Dividing N by two is the equivalent of shifting its bits one to the right The least signi cant gets thrown away and the most signi cant is lled with a zero 0 Given these two facts here is a recursive de nition of numOnes 0 ifN 0 base case numOnesN numOnesN2 Ngt0 N is even inductive step I numOnesN I2 Ngt0 N is odd inductive step Make N even by doing this 51 Recursion Another example 0 Now write some code for it 0 l39fN 0 base case nunu9nes v nunu9nes VCv f gt0PJnseven nduc veany 1inunu9nes l y gt0Afmuki ndbc veany The obvious way int numOnesint N REQUIRES N gt 0 EFFECTS returns number of quotlquots in N39s representation if N return 0 else if N 2 return 1 numOnesN l2 else return numOnesN2
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'