Thank you to the students who showed up so that we'll have notes that that other students can read over later.

Finding This Page

• Go to http://www.cs.grinnell.edu/~rebelsky/
• Click on "CSC 151" at the top of the page
• Click on "EBoard" in the "Current" row

Overview

• About the quiz.
• Your questions.
• Sample quiz questions.
• More of your questions.

The Quiz

Topics

• Files (and file recursion)
• Analyzing algorithms
• Higher-order procedures

Types of questions

• Write a procedure to do ....
  • Or fill in the blanks
• Interpret code
  • Document
  • What is the output?
• Analyze code
  • How many calls to x do you expect in the following?

Your Questions

Is there a general pattern for file recursion?

We almost always use a kernel, because we're going to take a file name as input and turn it into a port.

Generally have a form like the following.

(define file-procedure (lambda (fname other-info) (let ([source (open-input-file fname)]) ; Open input port to start reading (let kernel ([so-far starting-value]) (let ([val (read source)]) ; read a value; can also be read-cha ; Do something based on the value we've read (cond [(eof-object? val) (close-input-port source) so-far] [(test? val) ... (kernel (revise so-far))] [else ... (kernel (revise so-far))]))))))

"Interesting" triply nested let. Outer let to open the port, middle let for the recursive kernel, innermost let to read the value.

Let's do an example. Add all the numeric values.

(define file-sum (lambda (fname) (let ([source (open-input-file fname)]) (let kernel ([so-far 0]) (let ([val (read source)]) ; read a value; can also be read-cha (cond [(eof-object? val) (close-input-port source) so-far] [(number? val) (kernel (+ so-far val))] [else (kernel so-far)]))))))

Let's do another example: Print all the values in the file.

(define print-values (lambda (fname) (let ([source (open-input-file fname)]) (let kernel () (let ([val (read source)]) ; read a value; can also be read-cha (cond [(eof-object? val) (close-input-port source)] [else (display val) (newline) (kernel)]))))))

A variant

(define print-chars (lambda (fname) (let ([source (open-input-file fname)]) (let kernel () (let ([val (read-char source)]) (cond [(eof-object? val) (close-input-port source)] [else (write val) (newline) (kernel)]))))))

Sample Quiz Questions

File Output

Write a procedure, (entry fname courseid coursename faculty), that writes something like the following to the named file

CSC 151, Functional Problem Solving, is taught by SamR

More generally

courseid, coursename, is taught by faculty

File Input

Suppose the file /home/student/Desktop/file.txt contains the following values

23 "Hello" (1 2 3) zebra 11

What is the value of v1, v2, v3, and v4 after I execute the following code?

> (define src (open-input-file "/home/student/Desktop/file.txt"))
> (define v1 (read src))
> (define v2 (read src))
> (define v3 (read src))
> (define v4 (read src))
> (close-input-port src)

A Solution

v1: 23
v2: "Hello"
v3: '(1 2 3)
v4: 'zebra

File Output

Write a procedure, (rounder num fname), that takes as input a real number and a file name and writes to the file the four ways to "round" the number to the nearest integer. For example, with an input value of 3.4, the file would contain

Number: 3.4
Round: 3.0
Truncate: 3.0
Floor: 3.0
Ceiling: 4.0

Note that you should use display rather than write to write text to a file.

File Recursion

Write a procedure, (read-and-print-strings fname), that reads all of the values in fname and prints all of the strings it contains, one per line.

Combining Procedures

Write a procedure, (negate pred), that returns a new predicate that returns the opposite of whatever pred returns.

> (define non-integer? (negate integer?))
> (non-integer? 4)
#f
> (non-integer? null)
#t

Vector-Map

Write a procedure, (vector-map! vec fun), that replaces each value in vec by the result of applying fun to that value. (Template coming.)

(define vector-map!
  (lambda (vec fun)
    (let kernel ([pos (- (vector-length vec) 1)])
      (when (_______________)
        (vector-set! vec pos ___________________)
        (kernel (- pos 1))))))

A Solution

Analysis

How many calls to cons (direct and indirect) do you expect in the three variants of the following procedure.

(define select-vals
  (lambda (lst pred?)
    (cond
      [(null? lst) 
       null]
      [(pred? (car lst))
       (cons (car lst) (select-vals (cdr lst) pred?))]
      [else
       (select-vals (cdr lst) pred?)])))

(define select-vals-2
  (lambda (lst pred?)
    (let kernel ([so-far null]
                 [remaining lst])
      (cond
        [(null? remaining)
         (reverse so-far)]
        [(pred? (car remaining))
         (kernel (cons (car remaining) so-far)
                 (cdr remaining))]
        [else
         (kernel so-far (cdr remaining))]))))

(define select-vals-3
  (lambda (lst pred?)
    (let kernel ([so-far null]
                 [remaining lst])
      (cond
        [(null? remaining)
         so-far]
        [(pred? (car remaining))
         (kernel (append so-far (list (car remaining)))
                 (cdr remaining))]
        [else
         (kernel so-far (cdr remaining))]))))

a. For an input of (select-vals (1 2 3 4 5) odd?)

b. For an input of (select-vals (1 2 3 4 5) even?)

c. For an input of (select-vals (1 2 3 4 5) integer?)

A Solution

For the first select-vals, where are the calls to cons? Only in the second condition. When do we have the second condition? When the predicate holds. (The number is odd for a, the number is even for b, the number is an integer for c.)

a. v1: 3

b. v1: 2

c. v1: 5

For the second select-vals, where are the calls to cons? An explicit call in the second condition. Any implict calls to cons? reverse calls cons. To reverse a list of length N, it does N calls to cons. (Remember lab)

We do the second case each time the predicate holds.

Side node: Sam says "holds" for "is something other than false"

We do the first case (the reverse) once

a. v2: 3 explicit calls; 3 indirect calls in reverse: 6 total

b. v2: 2 explicit calls; 2 indirect calls in reverse: 4 total

c. v2: 5 explicit calls; 5 indirect calls in reverse: 10 total

For the third select-vals, where are the calls to cons? Both append and list call cons. Append calls cons once for every value in the first list. list calls cons once for every value in the list it is building.

a. v3: See the 1. Build a list of '(1) (one call). Append '() '(1). No additional calls. See the 2. Skip it. See the 3. Build the list '(3) (one call). Append '(1) '(3). Another. Up to three total calls. See the 4. Skip skip. See the 5. Build the list '(5) (one call). Append '(1 3) to '(5). Two more calls. Total of 6 calls.

b. v3: Total of three calls. (A lot like the '(1 3))

c. v3: 1 + 2 + 3 + 4 + 5 = 15 calls. (You'll see this pattern a lot.)