3
Evaluation Control and Recursion
3.1. Evaluation Control
(define (always-0 val) 0)
3.2. Short Circuit Evaluation
; = #t if ordinal b is between ordinals a and c
(define (between? a b c)
(or (and (real? a)
(real? b)
(real? c)
(or (< a b c) (< c b a)))
(and (char? a)
(char? b)
(char? c)
(or (char<? a b c) (char<? c b a)))
(and (string? a)
(string? b)
(string? c)
(or (string<? a b c) (string<? c b a)))))
(define (point? val)
(and (vector? val)
(= 3 (vector-length val))
(real? (vector-ref val 0))
(real? (vector-ref val 1))
(real? (vector-ref val 2))))
3.3. Conditional Evaluation
3.3.1. The if-structure
; $50,000 = maximum medium income:
(define max-medium 50000)
; 30% = rate for > max-medium incomes:
(define max-rate .3)
; 20% = rate for <= max-medium incomes
(define medium-rate .2)
; = tax owed on income dollars
(define (tax income) ??? )
; = tax paid on max-medium income
(define max-medium-tax (* max-medium medium-rate))
; = tax owed on income dollars
(define (tax income)
(if (> income max-medium)
(+ max-medium-tax
(* max-rate (- income max-medium)))
(* income medium-rate)))
Nesting if-structures
; $20,000 = maximum low income
(define max-low 20000)
; $5000 = maximum non-taxable income
(define max-min 5000)
; 10% = rate paid on max-min < $ <= max-low
(define low-rate .1)
; = tax on max-low income
(define max-low-tax (* low-rate (- max-low max-min)))
; = tax on max-medium income
(define max-medium-tax
(+ max-low-tax
(* medium-rate (- max-medium max-low))))
; = tax owed on income dollars
(define (tax income)
(if (> income max-medium)
(+ max-medium-tax
(* max-rate (- income max-medium)))
(if (> income max-low)
(+ max-low-tax
(* medium-rate (- income max-low)))
(if (> income max-min)
(* low-rate (- income max-min))
0))))
3.3.2. The cond-structure
; = tax owed on income dollars
(define (tax income)
(cond ((> income max-medium)
(+ max-medium-tax
(* max-rate (- income max-medium))))
((> income max-low)
(+ max-low-tax
(* medium-rate (- income max-low))))
((> income min)
(* low-rate (- income max-min)))
(else 0)))
3.3.3. Input Validation
; = tax owed on income dollars
(define (tax income)
(cond ((not (real? income))
(error "bad input" tax income))
((> income max-medium)
(+ max-medium-tax
(* max-rate (- income max-medium))))
((> income max-low)
(+ max-low-tax
(* medium-rate (- income max-low))))
((> income min)
(* low-rate (- income max-min)))
((>= income 0) 0)
(else (error "negative income" tax income))))
3.3.4. The case-structure
; = value denoted by exp
(define (evaluate exp)
(case (car exp)
((+ add sum) (apply + (cdr exp)))
((* mult) (apply * (cdr exp)))
((/ div) (apply / (cdr exp)))
((- sub) (apply - (cdr exp)))
((< less) (apply < (cdr exp)))
(else (error "unrecognized operator"
evaluate
(car exp)))))
3.4. Recursion
3.4.1. Example: Triangle Numbers
; = n-th triangle number
(define (triangle n)
(if (zero? n)
0
(+ n (triangle (- n 1)))))
3.4.2. Tracing
3.4.3. More on Input Validation
(define (triangle n)
(if (natural? n)
(if (zero? n)
0
(+ n (triangle (- n 1))))
(error "bad input" triangle n)))
(define (natural? val)
(and (integer? val) (<= 0 val)))
(define (triangle n)
(if (natural? n)
(unsafe-triangle n)
(error "bad input" triangle n)))
(define (unsafe-triangle n)
(if (zero? n)
0
(+ n (unsafe-triangle (- n 1)))))
3.4.5. Mathematical Induction
3.5. Thinking Recursively
3.5.1. Example: make-list
; = length n list: (val ... val)
(define (make-list n val)
(if (zero? n)
'()
(cons val (make-list (- n 1) val))))
3.5.2. Example: nat-expt
; = b^z where b & z are any numbers
(define (expt b z)
(cond ((natural? z) (nat-expt b z))
((integer? z) (int-expt b z))
((rational? z) (rat-expt b z))
((real? z) (real-expt b z))
((complex? z) (complex-expt b z)))
; = b^i where i is an integer & b is any number
(define (int-expt b i)
(if (>= i 0)
(nat-expt b i)
(/ (nat-expt b (- i)))))
; = b^n where n is a natural and b is any number
(define (nat-expt b n)
(if (zero? n)
1
(* b (nat-expt b (- n 1))))
3.5.3. Example: evaluate
; = value denoted by exp
(define (evaluate exp)
(if (number? exp)
exp ; exp denotes itself!
(case (car exp)
((+ add sum)
(apply + (map evaluate (cdr exp))))
((* mult)
(apply * (map evaluate (cdr exp))))
((/ div)
(apply / (map evaluate (cdr exp))))
((- sub)
(apply - (map evaluate (cdr exp))))
((< less)
(apply < (map evaluate (cdr exp))))
(else
(error "unrecognized operator"
evaluate
(car exp))))))
Appendices
Appendix 3.1. Sequential Evaluation
Appendix 3.2. Input and Output in Scheme
Input and Output Ports
Reading from the Keyboard
Writing to the Monitor
Interactive Procedures
Versatility
Unwanted Side Effects
(define (display&return val)
(display val)
(newline)
val)
The for-each Meta Procedure and writeln
(define (display+ val)
(display val)
(display #\space))
(define (display-vals vals)
(for-each display+ vals))
(define (writeln . vals)
(display-vals vals)
(newline))
Appendix 3.3. Defensive Programming
(define (error gripe location . irritants)
(writeln "Error!")
(writeln #\tab "gripe:" #\tab gripe)
(writeln #\tab "location:" #\tab location)
(if (not (null? irritants))
(begin
(writeln #\tab #\space
"irritant(s):"
#\tab #\space)
(display-vals irritants)))
(newline)
(return error-token))
(define (return val) val) ; for now
(define error-token 'error)
(define input-err "Illegal input(s)")
(define range-err "Input(s) out of range")
Continuations
(define (dist x y)
(if (and (real? x) (real? y))
(abs (- x y))
(error input-err dist x y)))
(define (small? z) (close? z 0))
(define (close? x y) (<= (dist x y) _delta))
; change return into a continuation
(define (receiver cont) (set! return cont))
(begin
(call-with-current-continuation receiver)
(writeln "returning to top level ..."))
Appendix 3.4. Debugging
Runtime Errors
(define (test num) (+ num "42"))
Logic Errors
(define (undefined) (undefined)) ; loops forever!
Diagnostics
; = tax owed on income dollars
(define (tax income)
(writeln "entering tax ... ")
(cond ((not (real? income))
(error input-err tax income))
((> income max-medium)
(writeln "income > max-medium)
(+ max-medium-tax
(* max-rate (- income max-medium))))
((> income max-low)
(writeln "income > max-low)
(+ max-low-tax
(* medium-rate (- income max-low))))
((> income min)
(writeln "income > min)
(* low-rate (- income max-min)))
((>= income 0) 0)
(else
(error "negative income" tax income))))
; = tax on income dollars
(define (tax income)
(writeln "entering tax procedure")
(if (> income max-medium)
(begin (writeln "income > max-medium")
(+ max-medium-tax
(* max-rate (- income max-medium))))
(begin (writeln "<= max-medium")
(* income medium-rate))))
Problems