Fundamentals of Computer Science I

Lab 4/5 - Lists, Style, Worlds

Purpose The purpose of this lab is to give you more experience with list-processing functions and programs. When you walk out of this lab, you should understand a variety of list-based data definitions and how to design functions for these.

We will also look at style in this lab. Style is important! Programs have remarkably long lifespans. Sometimes they even outlive their creators (!). A program will almost always be modified, extended and repaired countless times by many different people, so it is important that we write code that will be easily readable by other programmers.

If you don't think that's a good reason, consider that if a tutor can't figure out what your program does, then you won't get full credit. You (the brilliant student that you are) want to make your grader's life as easy as possible; don't tempt fate!

Notes

Chore Today we are pairing you up with new homework partner. When your lab TA pairs you with a new partner, sit down next to him/her and grab a computer. One of the TAs will come through and write down your Husky email addresses so that we know who is partnered up for the next few problem sets.

You may re-use whatever you did with your previous partner for this problem set but you must turn in the next solution set with your new partner.

This lab gives you a chance to get to know your partner, to exchange vital information (phone, twitter, facebook, email) and to make a first appointment (when/where you will meet to work on problem sets).

Hand-Rolled Lists

Last night, one of your TAs (who will remain nameless) was working on the BSL codebase and accidentally broke some functions and values related to lists. Since there hasn’t been time to fix it yet, we’ll have to create our own version of a list.

Sample Problem Your professors have asked your TAs to come up with a function that averages the scores on the last problem set so that they know how hard to make the next one. We were too busy trying to fix the broken BSL codebase. Design a function that averages an arbitrarily long list of numbers.

Using the design recipe, we will break down the above question into smaller steps: data definition, data examples, templates, design of function.

Sample Problem Develop a data definion for hand-rolled lists of numbers. Here is the one we came up with.

( define-struct   empty-lon  () )

( define-struct   cons-lon  ( left   right ) )

;   A HRLoN (Hand-rolled List of Numbers) is one of:

;  - ( make-empty-lon )

;   - ( make-cons-lon Number HRLoN )

Create three examples of HRLoNs

Structure type definitions without fields look strange but empty is really just such a thing. The key idea is that you get empty?, and it identifies a unique piece of data in BSL.

Note The idea of using structure type definitions without fields shows how to apply the ideas of this course to object-oriented languages such as Java. There you define classes without fields for a similar purpose.

Sample Problem Develop a template for HRLoNs. Remember that the template follows from the data definition via four questions: how many cases, what are the tests to distinguish them, do we need selectors in any of the cases, and does the data definition involve self-references.

Sample Problem Now you are ready to design the function average. Remember to ask the following questions? What kind of inputs does it consume? What type of data does it output? What does this output mean?

Decide with your partner to have one of you write down the signature and purpose. The other partner should be able to come up with functional examples.

Exercise 1 Good news, everyone. We just got word from upstairs that all the components of lists are working again! Good job Racket devs! Now, this Hand-rolled List of Numbers thing seems a bit unnecessary. Develop a new data-definition for a List of Numbers, using cons and empty.

Exercise 2 Now re-write average so that it accepts your new type of data as input rather than HRLoNs.

Switch roles.

Exercise 3 Design the function sum that consumes a list of numbers and returns the sum of its elements.

Exercise 4 Design the function overlay-all, which takes a list of images. It overlays each image onto the next image in the list. (TA: explain how to read the documentation, especially the arrow notation for overlay.) Giving the function an empty list should produce an empty scene of some size. You can choose how big it should be. Hint: Remember to follow the design recipe and come up with a data definition for a list of images.

Switch roles.

Exercise 5 Design the function sum-all that consumes a list of lists of numbers and returns the sum of all the numbers in all of the lists.

Style Guidelines

Guideline 1: Break Lines

Consider the data definition for Time:

;; A Time is (make-time Number Number)
(define-struct time (hours minutes))

Consider this program:

;; Time -> Image
;; Produce an image of the given time, as it appears on a digital clock.
(define(time->text a-time)
  (text(string-append(number->string(time-hours a-time))":"(cond[(< (time-minutes a-time)10)"0"]
  [else ""])(number->string(time-minutes a-time)))30'red))

1. How many arguments are there to text?
2. How many cond clauses are there?
3. What are the arguments to string-append?

This code is a disaster. Because the body is squeezed onto two lines, we cannot answer these questions within a few minutes. If we insert line breaks, the code becomes much more readable. We also want to limit our functions to "one job, one function", so factoring out a helper function increases readability as well.

;; time->string: Time -> String
;; Produce a string of the given time, as it appears on a digital clock.
(define (time->string a-time)
  (string-append (number->string (time-hours a-time))
                       ":"
                       (cond [(< (time-minutes a-time) 10) "0"]
                             [else ""])
                       (number->string (time-minutes a-time)))
	

;; time->image: Time -> Image
;; Produce an image of the given Time.
(define (time->image a-time)
  (text (time->string a-time)
        30
        'red))

With this code, it is easy to see the three arguments to text , the four strings being appended, and the two cond clauses.

In general, try to break long lines by

• Giving each cond clause its own line. [Always a good idea.]
• If a cond question or answer is long, then start the answer on the next line. [Often a good idea.]
• Giving each function argument its own line. [Less common, but string-append is a typical offender.]

If these formatting hints do not help, consider designing and using a helper function to make the code more compact/readable. For example, in time->text above, it's probably a good idea to factor out the (string-append ..) expression as a separate helper function.

Every line of code should be no more than 80 characters long. DrRacket can help you with this — Can you find where it indicates the current column of the cursor?

1. Rewrite the following function distance->text function by developing and using helper functions that compute the (string-append ...) and conditional portions of the body. Be sure to invent a good name for these helper functions.

;; A Distance is (make-distance Number Number)
(define-struct distance (feet inches))
;; Where feet is a Number from 0 - 99 and inches is
;; a Number from 0 - 12.

;; Distance -> Image
;; Produce an image of the given distance, as it appears on a digital interface.
;; Ex. 	(make-distance 5 9) 	-> '05ft09in'
;;	(make-distance 12 10)	-> '12ft10in'

(define(distance->text a-distance)
  (text(string-append(cond[(< (distance-feet a-distance)10)"0"]
  [else ""])(number->string(distance-feet a-distance))"ft"
  (cond[(< (distance-inches a-distance)10)"0"][else ""])
  (number->string(distance-inches a-distance))"in")30'red))

Guideline 2: Indentatation

Consider the following program:

;; LOS -> Number
;; Determine how many symbols are in a-los
(define (count a-los)
(cond
[(empty? a-los)0]
[(cons? a-los)
(+ 1 (count (rest a-los)))]))

This is not indented properly. Copy and paste this code into DrRacket. Then select the code and hit the Tab key. DrRacket will indent all the selected code automatically! (Note that this will not help you with long lines and/or line breaks.

Make good use of this feature as you develop your programs. Also note that the Tab key can be used to automatically indent the line the cursor is currently on. Indentation is a very important factor of readability because it denotes the structure of the program at a glance. And we can't grade what we can't read!!

Note: When you use the automatic indentation you may notice it seems wrong... this usually means that your program is mis-parenthesized. Move the cursor through your code and use the grey highlighting to be sure that your parentheses are matched as you intend.

Guideline 3: Parentheses Layout

Let's reconsider count from above. The indentation is technically correct, but the parentheses are arranged a poorly:

;; LOS -> Number
;; Determine how many symbols are in a-los
(define (count a-los)
  (cond
    [(empty? a-los) 0
    ]
    [(cons? a-los
     )
     (+ 1 (count (rest a-los)
          )
     )
    ]
   )
)

A programmer who arranges their parentheses like this is probably trying to use the vertical alignment of the open and closing parentheses to visually determine the code structure. It is much easier to compress the closing parentheses together, and then eyeball the program structure using its indentation. When you need to match parentheses visually, use DrRacket's grey highlighting instead.

;; LOS -> Number
;; Determine how many symbols are in a-los
(define (count a-los)
  (cond
    [(empty? a-los) 0]
    [(cons? a-los)
     (+ 1 (count (rest a-los)))]))

Proper indentation and parentheses placement render the parentheses and brackets nearly invisible to the trained eye.

Interpreting a Simple Programming Language

The goal is to design an interactive program that illustrates how a turtle moves when given a series of commands. That is, the program consumes a list of commands, sets up the turtle facing right in the center of the canvas, and then executes one of these commands per clock tick. Its return value is the last position of the turtle.

Our design is available on-line. Please download the program, open it in DrRacket, and read the sections on constant definitions, data representations, main function, and wish list. As you can see the wish list consists of two functions: render-turtle and execute-one-command. We would like you to design these functions. Do not hesitate to add new wishes to the wish list. We recommend that you finish execute-one-command first so that main’s tests pass. Then work on rendering.

Challenge: Random Walks