Comp 210 Lab 6: local: Giving names, Avoiding re-computation

(Computers Can be Slow)

Using local in Donkey

(define e 2.718281828)
(local [(define root5 (sqrt 5))
        (define golden (/ (+ 1 root5) 2))
        (define goldenConj (/ (- 1 root5) 2))]
   (+ (expt golden 7) (expt goldenConj 7)))

The above example shows one use of local: to give names to temporary, local sub-expressions. Exercise: Write the function solve-quadratic, which takes three numbers a,b,c and returns a list of the real roots of ax^2+bx+c=0 (that is, what are all the real values of x that make this statement true?). You can do it as you like, though my let statement happened to use three placeholders: discriminant, denominator, and negB. Bonus: Make your function work correctly for degenerate cases like a=0, and give reasonable feedback for a=b=c=0 etc.

Local Subtleties

;; (fibX n)
;; return the nth Fibonacci number
;; (or a floating-point approximation thereof)
;;
(define fibX
  (lambda (n)
    (local [(define root5X (sqrt 5))
            (define goldenX (/ (+ 1 root5X) 2))
            (define goldenConjX (/ (- 1 root5X) 2))]
       (+ (expt goldenX n) (expt goldenConjX n)))))

;; (fibY n)
;; Return same thing as fibX.
;; How is it different?
;;
(define fibY
  (local [(define root5Y (sqrt 5))
          (define goldenY (/ (+ 1 root5Y) 2))
          (define goldenConjY (/ (- 1 root5Y) 2))]
  (lambda (n)
     (+ (expt goldenY n) (expt goldenConjY n)))))

Censoring Your Code

;; (min-slow nlon)
;; nlon is a non-empty list of numbers
;; Return the smallest number in the list
;;
(define min-slow
  (lambda (lon)
    (cond [(null? (cdr lon)) (car lon)]
          [else (if (< (car lon) (min-slow (cdr lon)))
                    (car lon)
                    (min-slow (cdr lon)))])))

Now evaluate (min-slow short1) and (min-slow short2). Are these the results you expected?

Let's test our function on a couple of medium-sized lists, m1 m2. Look at what these lists are, then pass them to min-slow. What happened?

You can use the function (bad-case n) to make a list with n items that will cause min-slow some difficulty. Exactly how long a list do you need to before you have to wait too long for an answer?

Note that our code contained some repeated code: in order to compute (min lon), we may compute the value of (min (cdr lon)) two times. In turn, each of those calls might call min on (cdr (cdr lon)) twice, for a total of four times. Similarly, (min (cdr (cdr (cdr lon)))) might be computed up to eight times, etc. No wonder things took so long! How can we avoid re-computing an answer?

You guessed it: local to the rescue! Writing the same code twice (like the two recursive calls to min-slow) should offend your sensibilities. In fact, a certain god of Scheme calls this repetition of code "obscene programming". Let's try "censoring" our code for min-slow, and compute the intermediate value (min (cdr lon)) only once.

(define min-fast
  (lambda (lon)
    (cond [(null? (cdr lon)) (car lon)]
          [else (local [(define min-of-rest (min-fast (cdr lon)))]
		  (if (< (car lon) min-of-rest)
		      (car lon)
		      min-of-rest))])))

local's little cousin let

The UNIX corner: grep, wildcards

grep

Some handy flags to grep are grep -i which makes searching case-independent, and grep -v which prints out all lines not containing the indicated pattern. You can also give grep more than one file to look through: grep define hw2.ss hw3.ss.

echo

owl% echo hello there
hello there

Wildcard Expansion

Try echo * and observe that before echo ever sees its arguments, * has been expanded to match all files in the current directory (which don't start with a dot). What about echo dot-files are .* or echo .??*?

For instance, if you have several scheme source files in the same directory, you could say grep define *.ss. If you you had your various programs in different subdirectories, like hw1/, hw2/, etc., then you could try grep define hw?/*.ss or even grep define */*.ss.

Exercise: Change your working directory to ~comp210/Labs and do an ls to orient yourself. Then, tell me how many times the word "symbol" occur any of the in the files "index.html", found inside each labXX subdirectory (where XX are any two characters). Which file contains the most occurrences?

Quoting: Occasionally you may want to have a character like * or ? (or quotation marks) that you type into the shell, without having them specially-interpreted as above. The most general solution is to quote them with a preceding backslash. Compare echo hello * with echo hello \*.