How to design programs/Problem set 2

From Wikiversity
Jump to navigation Jump to search

Overview[edit | edit source]

Programs operate on data. Sometimes that data comes from the world (the Internet, etc.), sometimes a database, and sometimes it is typed in by hand, by a user of our software. In every case, we need to represent that data in some way. How we choose to represent information greatly effects the way our code is written. A poor choice in the structure of our data can impact the efficiency and maintainability of our programs greatly. How and why this is the case is something that we will discuss and explore as you learn more about the representation of data in computer programs, and the design of algorithms that consume, manipulate, and generate structured data.

So far, you have seen three types of data: numbers, booleans, and symbols. We introduce structured data types, or compound data types, in this homework.

Instructions[edit | edit source]

Exercises flagged with a [pra] are flagged as viable for practice. If you're confident that you can, in your sleep, write code like the exercises previous to it, you may skip this exercise. Otherwise, it might be good to work the [p]s as well, as they provide you with an opportunity to get some repetition into your programming diet.

Exercises flagged with a [lab] are intended for your lab notebook. I will check your lab notebook in class; it receives a binary mark, as it is more for your learning than my evaluation.

Exercises flagged with a [*] are ephemeral, and mostly so you see how something works. They are often in the Interactions pane, and therefore have no permanence.

Design recipe[edit | edit source]

[lab] Without looking at your text, write down the design recipe in your lab notebook. Go back and look at section 2.5. How close were you?

section 6.1[edit | edit source]

[lab] 6.1.1, #2. This is not just busywork; part of being a successful programmer in any language is understanding what your code will do when executed. Work through #2 by hand, and then use the Stepper to see if you're on track. If you didn't get it, do #1 and #3 as well. If you still can't seem to figure out how the code will execute, drop me a note.

section 6.2[edit | edit source]

  • [*] 6.2.1
  • 6.2.2
  • 6.2.3
  • 6.2.4
  • 6.2.5

section 6.3[edit | edit source]

  • [lab] 6.3.1 Do any two. Do more if you feel it is good practice.
  • [lab] 6.3.2
  • 6.3.3 Jet fighters? Mercy. Choose something more world-friendly, and propose a reasonable function over that data. Preferably, draw on some previous experience that you've had at Olin, so I learn something interesting (but not incriminating) about you. For example, you might use a data structure to represent some critical dimensions of an effort to save the local orphanage (cash, food, band-members, etc.), and something that determines how far you can go on half a tank of gas and a pack of cigarettes (apologies to the Blues Brothers).

section 6.4[edit | edit source]

  • [lab] 6.4.1 #1, 4, 5 (Apparently, there is some kind of parity between boyfriends and cheerleaders that I don't quite understand.)
  • 6.4.2 As an extension, propose a data structure that is useful for capturing time more generally, and in greater detail. Justify your choice of structure definition with some examples (described or in code). In short, defend why you have proposed a good definition for representing time. Specify/constrain your context as necessary, if that makes the problem more tractable.

section 6.5[edit | edit source]

  • 6.5.2
  • 6.5.x1 The Olin lunch is kinda tricky if you don't have a universal food plan. For example, I know that you can choose a full lunch, soup, salad, sandwich, etc. Different combinations of these things cost different amounts. Propose a data definition for representing a lunch-goer's choice, and a function that calculates the cost of the lunch based on the choices they made.
  • 6.5.x2 Create a new, empty program, and call it something unique and original, like "date-test.scm". Switch from "Beginning Student" to "MzScheme (Textual)". (You'll want to switch back after this exercise.) At the top of your definitions window, type:
(require (lib "date.ss"))
(define now (seconds->date (current-second)))

First, a few questions:

  1. What do you think the first line is doing?
  2. What are all of the function names (operators) in this piece of code?
  3. When you run your program, you can then type "now" in the Interactions pane. Is this an accurate representation of the time? Why, or why not.
  4. Look in the Help Desk for the date library that you've just imported. What does it tell you about a date?

Now, let's invent our own date structure:

(define-struct mydate (year month day))

Using your new uber-knowledge of structures, write a function called same-day? that consumes:

  1. a mydate structure and
  2. a date structure

Your function should return 'true' if both structures represent the same date. Write enough tests to convince yourself you have things right. Use the structure design recipe to help break these things down.

section 6.6[edit | edit source]

The next sequence is important because you're asked to write a sequence of functions that rely on each-other. This is common practice in programming.

  • 6.6.1
  • 6.6.2
  • 6.6.3
  • 6.6.4
  • 6.6.5
  • 6.6.6 (You may skip this for superstitious reasons, if you wish.)
  • [pra] 6.6.7
  • [pra] 6.6.8
  • [pra] 6.6.9
  • [pra] 6.6.10
  • [pra] 6.6.11
  • [pra] 6.6.12

section 6.7[edit | edit source]

  • [pra] 6.7.* The hangman exercise is left to you as a possible practice exercise. It has you write a number of functions that handle different aspects of the hangman game, and then the hangman teachpack uses those functions to run the game. If you don't write the functions correctly, the game will not work.

section 7, part 1[edit | edit source]

  • 7.2.1
  • 7.4.* This is an exercise in refactoring. It is far from busywork: this is what happens when you decide to change the definition of your underlying data structures after you've already written your code. These exercises have you revisiting code you wrote previously, changing the underlying representation of data, and then reworking/rewriting the associated code.

I am going to make this a more challenging process than expressed in the text.

  • Write tests for the existing code from 6.6 (if you haven't already) that give you some sense that given a known set of inputs, you get a known set of outputs. If necessary, break apart the existing functions so you can test parts of them independent of the drawing functionality. (Tricky.)
  • Introduce your new data definitions.
  • Write tests for your existing code from 6.6 that makes use of the new data definitions. All of these tests should fail.
  • Begin refactoring the functions as described in 7.4.1, 7.4.2, but in doing so, make sure that all of your tests continue to pass.
  • When all of your tests pass, evaluate how your code looks now. Is it clear? Confused? Propose a possible way of reorganizing it (if necessary) and demonstrate this with one of the functions that you've just written.

Questions for reflection (writeup and include in "questions.txt" in your repos). Feel free to do a bit of Googling if it helps you formulate answers.

  • Is refactoring as easy as writing code from scratch? Why or why not?
  • What part of the software lifecycle do you think refactoring lives in? How does that relate to cost?
  • Why would software engineers and developers engage in this process?
  • How common do you suspect this process is "in the real world?" Is that good or bad?
  • What do you see as the relationship between testing and refactoring?

section 7, part 2[edit | edit source]

These last two hint at some more powerful tools you'll see later, and relate to a process that is actually built into some other languages (eg. Java, Haskell, ML), but not languages like C and Python (to name just two). These are a breath of fresh air after the last question.

  • 7.5.2
  • 7.5.3

A note on submission[edit | edit source]

Create a directory in your repository called 'hw2', and do your work in this directory. That is, create one or more files in that directory where you do the exercises and save them. There might be one file called "all-hw2.scm", or perhaps you'll end up with "sec6.scm" and "sec7.scm"... I am only asking that all of your homework for this set of exercises ends up in a directory called "hw2".

If you feel you need to tell me about how you organized things, create a file called "layout.txt" (assuming it is a file written in Notepad) that tells me what is where. Most likely, I'll be able to figure out that the ".scm" files are your Scheme files containing code.