Lecture: 1 Date: Jan 7, 2008 Three parts to today's lecture 1) Review of basics from 211 2) Class overview and administrative details 3) Refactor code from part 1 At the end there is a post scriptum with answers to questions that came up in class but were deferred. Part 1 ====== Q: What are the steps of the design process? We will be designing software for a radio station. The station broadcasts shows, which include some number of ads. We want to be able to do things like calculate the amount of time a show has to devote to the show itself (ie, after the ads have been played). Q: What is the difference between information and data? Q: What kind of information might we want to keep track of for our radio shows? Ads? Suppose we only care about a show's name, duration, and ads, and for the ads, we only care about the duration and cost (profit) of running the ad. Q: How do we represent 0 or more things? A: Lists. Q: What are good data definitions for representing this information? What should our structure definitions look like? A: ;; A Show is a (make-show String Number [Listof Ad]). (define-struct show (name duration ads)) ;; An Ad is a (make-ad Number Number). (define-struct ad (duration cost)) Suppose we have the following ads that should be running during the News (a 60 minute program): - Apple, 1 min, $500 - Nike, 1 min, $1,000 - Apple (again) - The Ad Council, 2 min, $50 - Nike (again) - Nike (again) Pair up, translate this information into data. Write it on the board. (define apple (make-ad 1 500)) (define nike (make-ad 1 1000)) (define ad-council (make-ad 2 50)) (define ads (list apple nike apple ad-council nike nike)) (define news (make-show "News" 60 ads)) Q: What is the contract/purpose of show-time? A: ;; show-time : Show -> Number ;; Determines the duration of the given show that is not taken up by ;; advertisements. Q: What does the template look like? A: It takes a struct, so we pull it apart. (define (show-time a-show) (show-name a-show) (show-duration a-show) (show-ads a-show) ...) Q: Do we have any data we can use for tests? A: Yes, news. (show-time news) => 53 Now let's write the code. Q: Informally, how do we compute this? A: Subtract from the show's duration the sum of durations for the ads. Sounds like we need to do some wishful thinking. Suppose we have: ;; ads-duration : [Listof Ad] -> Number ;; Sums the duration of the ads in the given list. Now write the code: (define (show-time a-show) (- (show-duration a-show) (ads-duration (show-ads a-show))) Now write the tests. Re-use the news example. *WE ARE NOW USING check-expect* (check-expect (show-time news) 53) ... (generate-report) ;; at the end of the program But wait... do we have a test for the base case? Q: (ads-duration empty) => ? A: 0 We're done with show-time, save our wishful thinking. So let's develop ads-duration. ;; ads-duration : [Listof Ad] -> Number ;; Sums the duration of the ads in the given list. Q: Do we have data we can use as an example? A: Yes, ads. Q: (ads-duration ads) => ? A: 7 Q: What does the template look like? A: We're given a [Listof Ad]. A [Listof Ad] is one of: - empty - (cons Ad [Listof Ad]) ;; draw arrow back to DD. This is a recursive union. We use cond to distinguish the cases in the union and recursion. (define (ads-duration ads) (cond [(empty? ads) ...] [(cons? ads) (first ads) (ads-duration (rest ads)) ...])) Q: What kind of this is (first ads)? A: Ad Q: (rest ads)? A: [Listof Ad] Q: (ads-duration (rest ads))? A: Number Q: From our examples, what should the base case be? A: 0 Q: How do we combine (first ads) and (ads-duration (rest ads)) to construct an answer in the recursive case? A: (+ (ad-duration (first ads)) (ads-duration (rest ads))) Now turn your examples into test using check-expect. Part 2 ====== Q: What do you think this class might be about? A: Designing programs? Q: Are we going to learn a new design recipe? Are there two recipes, one for Scheme programs and one for Java programs? A: No. This course is about the fundamental principles that underly design in *ANY* programming language. Only the style and language constructs change. We are simply learning a new dialect (another foreign language), but the process remains the same. This is *NOT* a course on Java (just as 211 was not a course on Scheme). If you know a lot of Java, you may be in trouble. This course is about how to design code, build abstraction, write and use libraries. Q: Why do we design abstractions? A: 1) code re-use 2) eliminate repetition Course web page: http://www.ccs.neu.edu/home/vkp/213-sp08/ Like last semester we will have labs. There are lab quizes and you must pass in order to have your homework graded. Homeworks and labs are done in pairs. Homeworks consist of "portfolio" problems (finger exercises) and actual problems. The portfolio is not graded (except at exam time). We have a large staff. See the course web page for office hours. Do not suffer alone. *THE MOMENT YOU GET OFF TRACK, COME TALK TO SOMEBODY*. There is a course wiki, to be used to communicate outside of class. *DO NOT POST SOLUTIONS OR PARTIAL SOLUTIONS TO THE WIKI* This will be considered a violation of the academic honesty policy and the requisite actions will be taken. If in doubt, email your instructor and they will post what they think is appropriate. The BOOK is How to Design Classes. It is sold through the NEU bookstore. Later chapters will be provided in class. It is not available online (like HtDP). Java Precisely and Effective Java are the only two references on Java you will ever need. Q: Where might you find any and all other relevant material to the class? A: The course website. Part 3 ====== We've done structural recursion on lists a bazillion times, so we designed abstractions. Q: What are they? A: The loop functions (andmap, ormap, map, foldl, foldr, ...) Q: How can we design ads-duration to use a loop function? A: With a fold. Q: Which one? A: Uh... it doesn't matter. No, foldl. No wait, foldr. Q: Which one captures the structural recursion of our previous code? A: foldr Q: What is the contract for foldr? A: (X Y -> Y) Y [Listof X] -> Y Q: What is the definition of foldr? A: (foldr f b (list x1 ... xn)) = (f x1 ... (f xn b)) Q: What are X and Y in our specific problem? A: X = Ad, Y = Number So we need a base value that is a (?) Number. And a combiner that takes a(n) (?) Ad and a (?) Number and produces a (?) Number. Q: Base? A: 0 Q: Combiner? A: (lambda (an-ad duration) (+ (ad-duration an-ad) duration)) OK, we're done using foldr. Could we have used foldl? ... grumbling ... What is the difference between foldr and foldl? Q: What is the contract for foldl? A: Same as foldr. Q: What is the definition of foldl? A: (foldr f b (list x1 ... xn)) = (f xn ... (f x1 b)) So, in our example, using foldl we get: (+ 1 (+ 1 (+ 1 (+ 2 (+ 1 (+ 1 0)))))) Versus with foldr: (+ 1 (+ 1 (+ 2 (+ 1 (+ 1 (+ 1 0)))))) Q: Is it safe to use foldr in place of foldl here? A: Yes, but only because we are dealing with integers. In general, it is not true that (= (+ a b) (+ b a)) when a and b can be inexact numbers (see Lab 10 from last semester, or tomorrow's Lab). Q: If foldr captured the pattern of structural recursion on lists, what pattern does foldl capture? ... crickets chirping ... Q: foldr is to structural recursion on lists as foldl is to ___? ... more crickets ... A: Accumulator style recursion on lists. Let's work backwards an develop the accumulator style ads-duration. (define (ads-duration-acc ads duration) ...) Q: What is (ads-duration-acc (cons (make-ad 3 1000) ads) 10)? A: (ads-duration-acc ads (+ 3 10)) OK, let's write the code: (define (ads-duration ads) (ads-duration-acc ads 0)) (define (ads-duration-acc ads duration) (cond [(empty? ads) duration] [(cons? ads) (ads-duration (rest ads) (+ (ad-duration (first ads)) duration))])) We'll pick up with more on accumulators next time and start talking about representing data in Java. Post scriptum ============= Q: Will there be in-class quizes? A: No. Q: Are laptops allowed in class? A: No. (See course web page).