Midterm 1: Solution

(1.) [5 points total] For the following Scheme expressions, show how the result prints out. If the expression results in a run-time error, say why.

(car (+ 1 2) (* 3 4))
=> Error! car expects a list.
(cons (+ 1 2) '(- 3 4))
=> (3 - 3 4) ;; not (3 -3 4) !!
(append '(1 2) (reverse '(3 4))))
=> (1 2 4 3)
(map (lambda (x) (>= x 10)) '(11 10 9 5 15 6 0))
=> (#t #t #f #f #t #f #f)
(list 3 (cdr 1 2))
=> Error! cdr expects a list!

(2.) [5 points] True / False

FALSE When garbage-collecting large objects, copy-collectors are preferable to mark-sweep collectors.
TRUE Mark-sweep collectors tend to fragment heap memory.
FALSE Scheme is dynamically typed, meaning that it cannot be strongly typed.
TRUE C is an example of a statically typed language.
FALSE In a C program, space for local variables is allocated in the static region of program memory.

(3.) [5 points] Short Answer. Answer ONLY one of the below. Correct, concise answers will be rewarded.

Describe three (3) salient differences between Scheme and another programming language of your choice (eg. C, C++, Java). One sentence per difference should suffice.
ANSWER: C is statically typed; Scheme is dynamically typed. C is weakly typed; Scheme is strongly typed. C forces the programmer to manage their own dynamic memory; Scheme does this for you via garbage collection. C supports passing functions as pointers to functions; but Scheme provides more generality by supporting functions as first-class citizens, meaning they can be generated, passed, and returned by/to/from other functions.
Define tail recursion and give an example of a function that is non-tail-recursive AND then show a tail-recursive version of that function.
A tail recursive function simply performs a recursive call on a smaller version of the problem; it doesn't need to wait around for a recursive call to return, like augmenting recursion does. Example:
```
;; non-tail-recursive length
(define (length x)
  (cond ((null? x) 0)
        (#T (+ 1 (length (cdr x))))))

;; tail recursive length
(define (length x result)
  (cond ((null? x) result)
        (#T (length (cdr x) (+ 1 result)))))
```
Dr. Dweezel has developed a copy-collected heap. He claims that it actually allocates memory faster than the standard (programmer-managed) heap used in a language such as C. Is he correct? Why? (HINT: There are interpretations of his claim that make it either true or false. Choose one and defend it.)
In the common case, he is correct. A copy-collected heap always knows exactly where to allocate the next object (at the "top" of the heap). The typical C heap becomes fragmented after a succession of malloc/free calls, meaning that it must search for a free-block that is a good fit for the requested blocksize.
In the uncommon case, he is incorrect. Every now and then, the copy-collected heap will run out of room and actually do a collection (which will certainly take a while!). Perhaps a better question is: What is the AVERAGE time PER allocation. In this case, the C heap would generally win out.

(4.) [7 points total] For each of the following Scheme expressions, show how the result prints out AND also draw the cons-cell box and pointer diagram of the result. For example, for (list 1 2 3) I would answer:

(1 2 3)

4.1)

'(((foo)) bar) => (((foo)) bar)

4.2)

(list (cons (+ 1 2) ()) 'foo) => ((3) foo)

4.3)

(let* ((x '(3 4))
       (y (cons '(1 2) x))
       (z '(4 5 6)))
   (list (+ (car x) (car (cdr y))) 
         (+ (car (cdr x)) (car (cdr (cdr z)))))) => (6 10)

(5.) [7 points] Write a function called char-count, which takes list of symbols. It returns a list of the lengths of the symbols in the original list. The function must be written recursively and cannot make use of any of Scheme's higher-order functions such as map. You should use the built-in functions symbol->string and string-length to determine the length of a symbol. Here are some examples:

(symbol->string 'foobar)                     => "foobar"
(string-length (symbol->string 'foobar))     => 6
(char-count '(Hello there my name is Bob))   => (5 5 2 4 2 3)

(define (char-count x)
  (cond ((null? x) x)
        (#T (cons (string-length (symbol->string (car x)))
                  (char-count (cdr x))))))

(6.) [7 points] Write count-chars again, this time using map. You must use a lambda expression (do not define extraneous helper functions).


(define (char-count x)
  (map (lambda (sym) (string-length (symbol->string sym)) x))

(7.) [7 points] If we represent documents in Scheme as lists of lists of symbols (where each inner list is a sentence), write a function called stats that takes a "document" and returns a list containing three items: total number of characters, total number of words, and total number of lines. For example, the below "document" contains 33 characters, 9 words, and 4 sentences.

HINTS: If you leverage char-count, as well as reduce, append, and length, this function is quick to write! If you couldn't write char-count, assume it's defined for you.

(stats '((Dear Sue) (I am learning Scheme) (See ya) (Bill)))  => (33 9 4)


(define (stats document)
  (let ((flat-doc (reduce append () document))) ; remove sentence structure
    (list
     (reduce + 0 (char-count flat-doc))   ; sum the lengths of the words
     (length flat-doc)                    ; count the number of words
     (length document))))                 ; count the number of sentences

(8.) [7 points] Write a function called map2, that takes three arguments: a function (which takes two arguments) and two lists. map2 should return a list that consists of the provided function applied to the corresponding elements of the two lists. Example:

(map2 (lambda (x y) (+ 1 (* x y))) '(1 2 3) '(4 5 6))   => (5 11 19)

;; assumes the lists are of equal length...
(define (map2 f x y)
  (cond ((null? x) x)
        (#T (cons (f (car x) (car y)) (map2 f (cdr x) (cdr y))))))