Sample Problems for Midterm 1

With Solutions

fall 2004

Problem 1

Consider the procedure legal? below:

(define (legal? c)
(and (number? c) (> c 0)) )

Write a procedure not-legal? that returns true when legal? returns false, and vice versa. Your not-legal? procedure should be a combination of uses of the following procedures: and, or, >= (greater than or equal to), <= (less than or equal to), and not-number? (which returns true when number? returns false, and vice versa); it should not use cond, if, or not.


(define (not-legal? c)
  (or (not-number? c) (<= c 0)) )

Problem 2

Consider a procedure named double that, given a word as argument, returns a two-word sentence. The first word is two. The second word is the result of adding an "s" to the end of the argument. Some examples of how double should behave appear below.

expression

intended result

(double 'apple)

(two apples)

(double 'bus)

(two buss)

(double 'box)

(two boxs)

Now consider some incorrect implementations of double. For each one, indicate what the call

(double 'apple)

will return. If no value is returned because the procedure crashes, give the error message that results.
 

procedure

returned value or error message

a
(define (double wd)
(sentence 'two '(word wd s)))


b
(define (double wd)
(sentence 'two (sentence wd s)) )


c
(define (double wd)
(sentence 'two (wd 's)) )



a
(double apple) => (two word wd s)
b
(double apple) => ERROR "unbound variable: s"
c
(double apple) => ERROR "bad function"

 

Problem 3

Fill in the blanks in the procedure below so that the code agrees with the comments.

; Given dates date1 and date2 in the form used in the Difference
; between Dates programs, return true when date1 is earlier in
; the year than date2, and return false otherwise.
; For example, (precedes-in-year? '(february 1) '(march 3)) should
; return true, while (precedes-in-year? '(february 1) '(january 17))
; and (precedes-in-year? '(february 1) '(february 1)) should return
; false.
(define (precedes-in-year? date1 date2)
(<
(day-span _____ _____ )
(day-span _____ _____ ) ) )

There are several correct answers; some possibilities:
(define (precedes-in-year? date1 date2)

  (<
    (day-span '(january 1) date1)

    (day-span '(january 1) date2)))
(define (precedes-in-year? date1 date2)

  (<
    (day-span date1 date1)

    (day-span date1 date2)))

 

Problem 4

Using only calls to month-name, date-in-month, month-number, and numeric comparison procedures, complete the alternative version of precedes-in-year? below. Your solution should use as few comparisons as possible.

; Given dates date1 and date2 in the form used in the Difference
; between Dates programs, return true when date1 is earlier in
; the year than date2, and return false otherwise.
(define (precedes-in-year? date1 date2)
(cond

A correct version that needs three comparisons:
(define (precedes-in-year? date1 date2)
  (cond ((< (month-number (month-name date1))
            (month-number (month-name date2)) )
          #t)
        ((> (month-number (month-name date1))
            (month-number (month-name date2)) )
          #f)
        ;; dates must be in the same month
        ((< (date-in-month date1) (date-in-month date2))
         #t)
        (else #f)
        ) )

 

Problem 5

For the following Scheme expressions, write the value that the STk would output if you were to type it in. If an expression produces an error, then just write ERROR.

  1. (first '(things first))
    Answer: things
  2. (first (bf (item 3 '(thom colin johnny ed phil)))
    Answer: o, because (item 3 '(thom colin johnny ed phil)) is johnny. (bf 'johnny) is ohnny. (first 'ohnny) is o.
  3. (if (equal? 'that (or 'this 'that '(the other)))
          (se (word) (quote (to say)))
          (se (quote (+ 2 2)) 'always 'makes (se (word (word) 'a) '5)))
    Answer: (+ 2 2 always makes a 5), because (or 'this 'that '(the other)) returns this. or returns the first true thing it finds, and all words are true, so or returns this. (equal? 'that 'this) is false, so we do the last line. (word) makes a word with no letters, which is "". (word "" 'a) is a, since word takes all of the letters from all of the words and puts those letters into a new word. "" has no letters, so the only letter in the new word is a. Finally, (quote (+ 2 2)) is the same as '(+ 2 2), which is a sentence. It does not become 4.
  4. (and (not '(hello)) (or (and (/ 5 0)) #t))
    Answer: #f. (hello) is a sentence, so it is true. Remember, anything that is not #f is true. (not '(hello)) is #f, so and stops and returns #f. It never looks at anything else.
  5. (se ('tell 'me 'why))
    Answer: error, because Scheme thinks that ('tell 'me 'why) is a call to the procedure 'tell. Unfortunately, the quote means that tell is a word and not a procedure. The error would be something like "bad procedure" or "tell is not a procedure." The exact wording isn't important.

Problem 6

For this function:
(define (mystery x)
  (or  (and (zero? x) '(+ x 5))
       (and (= x 3) 5)
       (se 'o (mystery (- x 2)))))
Give the results of the following calls. If a call results in an error, write ERROR. If it results in an infinite recursion, write INFLOOP
  1. (mystery 1) gives INFLOOP: we go from (mystery 1) to (mystery -1) and then to (mystery -3) and so on. We never get to 3 or 0, so it never finishes.
  2. (mystery 2) gives (o + x 5). Why? Well, we start with the or. It looks at the first argument, (and (zero? x) '(+ x 5)). x isn't zero, so the and sees #f and stops. or gets the #f from and, so it goes to the next argument, (and (= x 3) 5). x is not 3, so again, and sees the #f and stops. or sees the #f and goes on to the third argument, (se 'o (mystery (- x 2))). This is a sentence, so it must be true. or returns whatever (se 'o (mystery 0)) is. (mystery 0) is the sentence (+ x 5), so we get (o + x 5).
  3. (mystery 3) is 5. Just like last time, we start with the first and. x is not 0, so we go to the next and. This time, x is 3, so the and keeps going. 5 is true, and it's the last argument to and, so and returns it. or sees the 5 from this and, so since 5 is true, or returns 5.
  4. (mystery 8) returns (o o o o + x 5). x isn't 0 or 3, so we go to (se 'o (mystery 6)). 6 isn't 0 or 3, so we go to (se 'o (se 'o (mystery 4))). 4 isn't 0 or 3, so we go to (se 'o (se 'o (se 'o (mystery 2)))). We already decided that (mystery 2) is (o + x 5), so the whole thing comes out to be (o o o o + x 5).
  5. (mystery 7) returns (o o 5). 7 is not 3 or 0, so we do (se 'o (mystery 5)). 5 is not 3 or 0, so we do (se 'o (se 'o (mystery 3))). We know (mystery 3) is 5, so we get (o o 5).o

Problem 7

Write a procedure called bunch-words, which takes in a sentence. If the last letter of one word is the same as the first letter of the following word, then the two words should be joined together with the common letter removed from one of them. See the examples: How do we start? Always think about how to stop. What if there is only one word in the sentence? We should leave it alone. This gives us
(define (bunch-words sent)
  (cond ((= (count sent) 1) sent)
Now what? Well, we want to see if the last letter of the first word is equal to the first word of the second letter. How do we get the last letter of the first word? (first sent) gives us the first word, so (last (first sent)) gives us the last letter of the first word. How about the first letter of the second word? Well, (bf sent) throws away the first word and (first (bf sent)) gets the word right after the first word, so (first (first (bf sent))) gets the first letter of the second word. This gets us to
(define (bunch-words sent)
  (cond ((= (count sent) 1) sent)
        ((equal? (last (first sent)) (first (first (bf sent))))
         ???)
What do we do once we find two words that should go together? Let's put them together and throw away the first letter of the second word. How do we throw away the first letter of the second word? (first (bf sent)) is the second word, so (bf (first (bf sent))) takes the butfirst of the second word.
(define (bunch-words sent)
  (cond ((= (count sent) 1) sent)
        ((equal? (last (first sent)) (first (first (bf sent))))
         (se (word (first sent) (bf (first (bf sent))))
             (bunch-words (bf sent))))
Now if the words don't match, we want to leave the first word alone and look at the rest of the words.
(define (bunch-words sent)
  (cond ((= (count sent) 1) sent)
        ((equal? (last (first sent)) (first (first (bf sent))))
         (se (word (first sent) (bf (first (bf sent))))
             (bunch-words (bf sent))))
        (else (se (first sent) (bunch-words (bf sent))))))
Let's test it: (bunch-words '(this stuff freaks me out)).
  1. The count isn't 1, but this and stuff should be put together. This takes us to
  2. (se 'thistuff (bunch-words '(stuff freaks me out))). The count still isn't 1, but stuff and freaks should be put together. This takes us to
  3. (se 'thistuff (se 'stufreaks (bunch-words '(freaks me out)))). At this point, I can see that the first two words of the sentence are thistuff and stuffreaks. However, I know the first word should be thistuffreaks. What's wrong?
The problem is that we wanted to keep adding words to thistuff, but the only way we can do that is to keep it as an argument to group-words. How do we do that? What if we combine the first two words and then put them back into the sentence? That would look something like
(define (bunch-words sent)
  (cond ((= (count sent) 1) sent)
        ((equal? (last (first sent)) (first (first (bf sent))))
         (bunch-words (se (word (first sent) (bf (first (bf sent))))
                          (bf (bf sent)))))
        (else (se (first sent) (bunch-words (bf sent))))))
Yeah, that would work. You should test it, just to make sure.

Problem 8

You and your partner have just expanded your day-span procedure to work with any two dates in any years, even years before zero which are currently represented as negative numbers (the year -1 refers to 1 BCE). Your partner suggests that you switch to the more conventional representation with CE and BCE. For example, instead of (may 1 1984) you would use (may 1 1984 ce), and instead of (august 3 -50) you would use (august 3 50 bce).

Part A: How would you change the following accessors to accomodate this change?

(define (year date)
  (item 3 date))

(define (month-name date)
  (first date))

(define (day-of-month date)
  (item 2 date))
Answer: Change year to read
(define (year date)
  (if (equal? (last date) 'ce)
      (item 3 date)
      (* -1 (item 3 date))))
That's it. The month and day haven't changed.

Part B: Is it necessary to change anything else in the case study? Why or why not?

Answer: You don't need to change anything else. The instructions said that you and your partner had it working for negative numbers, and the new year returns negative numbers for BCE and positive numbers for CE. That's why we use year, month-name, and day-of-month.