Lecture 1: Design Recipe and DrRacket Review

Introduces the Design Recipe for designing functions in the context of designing static methods in Java.
Reviews the foldl and foldr loops in DrRacket and highlights the problems encountered in computing with inexact numbers.

     ExamplesAlgorithms.java      inexact.rkt   

Lecture 1 overview

There are no prerequisites for this lecture, but it assumes the reader has seen the Design Recipe in the context of HtDP2e and has a basic knowledge of programming in the teaching languages of DrRacket.

A reader who is starting without this background should be able to follow most of this lecture and fill in the missing pieces.

All programs shown here run as defined - in a regular Java environment, or within the DrRacket IDE - as appropriate.

Topics covered:

• Design Recipe for Methods in Java

• DrRacket loops: foldr, foldl

• Understanding accumulators:

  • the order of computation

  • the need to accumulate knowledge

  • documenting the meaning of accumulated knowledge

• Computing with inexact numbers

Static Methods: Design Recipe in Java

The first computers have been designed to perform computations of mathematical functions. These computations may represent physical behavior of objects (the location of a moving object at the given time, the size of the balloon as it is being inflated, etc.), financial calculations (e.g. the pay for a given number of hours worked at the known rate of pay, the cost of an order that consists of the given number of items at the known price, etc.), the statistical evaluation of data (e.g. computing the averages, means, the standard deviation, correlations, etc.) and other instances where the computation needs to be repeated a number of times, each time with the different given values.

Here is the simple problem: In a game, a car moves across the screen at the constant speed. (Later, we will add the chicken that wants to cross the road without getting hit.) What do we need to compute to model the car movement? We need to be able to determine the car’s location at any time.

The following steps will help us in designing the solution:

• Step 1: Consider all information available and represent it as data.

  Well, we have the location of the car and the time as the clock ticks to consider. If the car moves only at horizontal level, we need only its x-coordinate. We assume the clock ticks at an even rate, and so we need to know the tick count at each moment.

  We can represent both of these pieces of information as numerical data.

• Step 2: Define the purpose of the function and its signature.

  The purpose of our function will be to compute the location of the car at some given time. The information we need to supply is the car’s location at the start and the elapsed time since the start till now.

  That means, the function will consume the car’s location and the elapsed time and procude the car’s location after the given amount of time has elapsed.

  In Java, the purpose statement and the function signature (also known as header) will be

  // compute the location of the car,

  // given its location at the starts and the elapsed time

  static int carMove(int startLoc, int timeElapsed) {...}

• Step 3: Make examples of use of this function with expected outcomes.

  To compute the location of the car that starts at location 20 after 50 seconds have elapsed we invoke our function as follows:

  carMove(20, 50)

  But where will the car be in 50 seconds? Well, we do not know, because we forgot to provide any information about the speed at which the car is traveling.

  So, we revise the purpose and the header:

  // compute the location of the car,

  // given its location at the start given in pixels on the screen

  // the speed at which the car is traveling

  // given in pixels per clock tick

  // and the elapsed time, given in clock ticks

  static int carMove(int startLoc, int speed, int timeElapsed) {...}

  We can now finish making our examples. It is good to make at least two examples for simple functions, more for more complex functions.

  // starting at 20, at a speed 5, after 50 ticks:

  carMove(20, 5, 50) -> 270

  // starting at 10, at a speed 3, after 60 ticks:

  carMove(10, 3, 60) -> 190

• Step 4: Make an inventory of all data that can be used in solving the problem.

  In this case, this step is very simple: we have the original location, the speed, and the elapsed time. Later on, when the data will become more complex, this step will be more demanding as well as more helpful.

• Step 5: Design the solution as Java code.

  Our examples give us a hint on how to proceed. We need to add to the original location the multiple of the speed and the elapsed time.

  So, we complete the design of the method body and include the code inside the file Algorithms.java as follows:

  // a class for defining simple mathematical functions (methods)

  class Algorithms {

  // compute the location of the car,

  // given its location at the start

  // given in pixels on the screen

  // the speed at which the car is traveling

  // given in pixels per clock tick

  // and the elapsed time, given in clock ticks

  static int carMove(int startLoc, int speed, int timeElapsed) {

  return startLoc + speed * timeElapsed;

  }

  }

• Step 6: Test your work.

  We are not done! We need to make sure that our function works as intended. This is a very hard task (actually, an impossible one, as we will find out soon), but incredily helpful.

  We convert our examples into tests and include them in the file ExamplesAlgorithms.java that will be our place where we can see how our code will be used by others, and chack that the examples we have designed earlier work as we have predicted:

  // import the library that runs the tests

  // and reports the results

  import tester.*;

  // a class to test the functions(methods)

  // defined in the Algorithms class

  class ExamplesAlgorithms {

  ExamplesAlgorithms() { }

  // test the method carMove:

  boolean testCarLoc(Tester t) {

  return

  t.checkExpect(Algorithms.carMove(20, 5, 50), 270,

  "starting at 20, at a speed 5, after 50 ticks:") &&

  t.checkExpect(Algorithms.carMove(10, 3, 60), 190,

  "starting at 10, at a speed 3, after 60 ticks:");

  }

  }

  We now run our program and make sure all tests passed. If the did not pass, we look for errors: did we make a mistake in designing the method body? - or, was our prediction wrong? Both possibilities can happen and should be considered.

  If we cannot figure out the problem, we may want to add more tests to pinpoint the source of the error.

  Also, if during the design of the function we find that the problem is more complex that originally predicted, we add tests to cover at least one possible outcome for each category of possibe outcomes.

  For this problem we may consider what would the outcome be it the elapsed time given to us was a negative number? Or if the speed was negative? More about this type of issues later...

Conditionals

Let us consider another problem. We want to model the landing of a spaceship. When first seen at the top of the screen, the spaceship moves at some known (fixed) speed. It stops when it reaches the ground at the bottom of the screen.

We think of the problem, the information that is relevant, and what is it we need to model in our program. We come up with the following idea:

Determine the position of the rocket after one tick, given its current position (height) and its speed.

Rather than computing the position at some given time, we wory only about the change in the rocket’s position at each tick.

Our reasoning now follows the same steps as before:

• Step 1: Consider all information available and represent it as data.

  Well, we have done that.

  Again we can represent both of these pieces of information (the heights of the rocket above the ground, and its speed given in pixels er tick) as numerical data.

• Step 2: Define the purpose of the function and its signature.

  The purpose of our function was also described:

  Determine the position of the rocket after one tick, given its current position (height) and its speed.

  In Java, it will be

  // compute the height of the rocket after the next tick,

  // given its current height

  // and its seed in pixels per clock tick

  static int nextRocket(int startLoc, int speed) {...}

• Step 3: Make examples of use of this function with expected outcomes.

  To compute the location of the rocket that starts at location 100 andmoves 5 pixels per tick we invoke our function as follows:

  nextRocket(100, 5)

  and we expect the function to produce the 95.

  What do we expect when invoking the function in the following way:

  nextRocket(0, 5)

  Well, the rocket should land and stop, not move any more. So, the expected result is 0.

• Step 4: Make an inventory of all data that can be used in solving the problem.

  In this case, this step is again very simple: we have the original location, and the speed.

• Step 5: Design the solution as Java code.

  Here we need to think a bit. Most of the time the answer is easy: just subtract the speed value from the height.

  But we also need to check whether the rocket has landed, because then the height should not change. Our examples have already made us aware of this possibility.

  But what do we do if the atartLoc is greater than 0 but smaller than the speed? Well, we should just return 0 as the next location.

  So, our solution will be:

  // a class for defining simple mathematical functions (methods)

  class Algorithms {

  // compute the height of the rocket after the next tick,

  // given its current height

  // and its seed in pixels per clock tick

  static int nextRocket(int startLoc, int speed) {

  if (speed - startLoc >= 0)

  return 0;

  else

  return startLoc - speed;

  }

  }

• Step 6: Test your work.

  We again convert our examples into tests and include them in the file ExamplesAlgorithms.java. But during the design of the function we have come across a new possible situation, and so we should include at least one more test to check the solution for that case (i.e. if the startloc is smaller than or equal to speed). And the preceeding statement tells us we really need two additional tests.

  // import the library that runs the tests

  // and reports the results

  import tester.*;

  // a class to test the functions(methods)

  // defined in the Algorithms class

  class ExamplesAlgorithms {

  ExamplesAlgorithms() { }

  // test the method nextRocket:

  boolean testNextRocket(Tester t) {

  return

  t.checkExpect(Algorithms.nextRocket(100, 5), 95,

  "starts at 100, speed 5, the rocket descends to 95:") &&

  t.checkExpect(Algorithms.nextRocket(0, 5), 0,

  "starts at 0, speed 5, the rocket remains at 0:") &&

  t.checkExpect(Algorithms.nextRocket(20, 20), 0,

  "starts at 20, speed 20, the rocket lands at 0:") &&

  t.checkExpect(Algorithms.nextRocket(15, 20), 0,

  "starts at 15, speed 20, the rocket lands at 0:");

  }

  }

  We now run our program and make sure all tests passed.

Inexact computations: Review of DrRacket

The goal of this section is to recall some of the things you have learned in the first course, using DrRacket teaching languages. Read through this, run some of the examples, as we will refer to them at various times during the semester.

In our scientific measurement we came across a strange problem. We are given a list of points and the distances between them, and need to compute the total distance when traversing them in the given order:

• From A to B the distance is #i+9e23

• From B to C the distance is #i+8e23

• From C to D the distance is #i-1e23

• From D to E the distance is #i+6e23

To compute the distance traveled we can use one of the following two functions:

Run this and observe the results. Actually, both results are inaccurate! Try the following, and reason about the numbers yourself, to see what the correct result should be.

We have two problems here. The inaccuracies in compound computations with inexact numbers are inevitable and we will not solve this problem here - we just want to make sure you are aware of it when writing your own programs.

Finally, remember that the tests that anticipate an inexact value as the result need to specify not only the expected value, but also the range within which the result should fall:

Loops and accumulators: Review of DrRacket

The second problem can be illustrated as follows. Work out the steps the computer goes through when doing the following computations:

Notice the difference. The definition of foldr and foldl shows how the computation proceeds:

Define two functions sum-recipe and sum-accumulator that add the numbers in the given list - once from left to right, once from right to left. For the first method follow the design recipe. For the second one use an accumulator. Which one is which?

Now use the stepper to run the methods you designed on the following examples:

Sometimes you cannot solve the problem, unless you use some accumulator. The accumulator represents some information you need to remember from having seen the earlier steps of your program.

Suppose we ask you to compute the distance along some route, but give you just the locations of the points on the way. (Assume you travel between any two points in a straight line.)

We know that the distance between two posns is define as

Define the function total-distance that consumes a list of Posns that represent a route to travel and produces the total distance for the travel along this route.

Hint: What information do you need to remember as you traverse over the list of points?

Make sure you use helper functions as needed.

Make sure you describe in the purpose statement the meaning of the accumulator(s) that you need.

Recap: There are two key points to remember here:

• The computations with inexact number are indeed inaccurate and we cannot expect precise results. The tests for inexact numbers need to indicate the expected range for the result.

• There are two different ways we can traverse over a list of elements: in the first one the design follows the Design Recipe, in the second one we keep track of the accumulated knowledge, so that when we reach the last element of the list,the answer has been already computed.