11/386.001 SICPTagged data• Why do we need tags• Concept of tags• Extended example2/38Manipulating complex numbersComplex number has:Real, imag, mag, angle(define (+c z1 z2)(make-complex-from-rect (+ (real z1)(real z2))(+ (imag z1)(imag z2))))(define (*c z1 z2)(make-complex-from-polar (* (mag z1) (mag z2))(+ (angle z1) (angle z2))))magnitudeangleReal partImagpartAddition easier in Cartesian coordinatesMultiplication easier in polar coordinates3/38Bert’s data structure(define (make-complex-from-rect rl im) (list rl im))(define (make-complex-from-polar mg an)(list (* mg (cos an))(* mg (sin an))))(define (real cx) (car cx))(define (imag cx) (cadr cx))(define (mag cx) (sqrt (+ (square (real cx)) (square (imag cx)))))(define (angle cx) (atan (imag cx) (real cx)))Note conversion to rectangular form before storingNeed to do some computation since stored in rectangular form4/38Ernie’s data structure(define (make-complex-from-rect rl im) (list (sqrt (+ (square rl) (square im)))(atan im rl)))(define (make-complex-from-polar mg an) (list mg an))(define (real cx) (* (mag cx) (cos (angle cx))))(define (imag cx) (* (mag cx) (sin (angle cx))))(define (mag cx) (car cx))(define (angle cx) (cadr cx))Note conversion to polar form before storingNeed to do some computation since stored in polar form5/38Whose number is it?• Suppose we pick up the following object12• What number does this represent?BertErnie6/38Labeled complex numbers(define (make-complex-from-rect rl im)(list ‘rect rl im))(define (make-complex-from-polar mg an)(list ‘polar mg an))(define (real sz)(cond ((eq? (tag z) ‘rect) (car (contents z)))((eq? (tag z) ‘polar) (* (car (contents z)) ;mag(cos (cadr (contents z))))) ;angle(else (error “unknown form of object”))))(define (tag obj) (car obj))(define (contents obj) (cdr obj))27/38The concept of a tag• Tagged data =• attach an identifying symbol to all nontrivial data values• always check the symbol before operating on the data(define (make-point x y) (list 'point x y))8/38Benefits of tagged data• data-directed programming:functions that decide what to do based on the arguments• example: in a graphics programarea: triangle|square|circle -> number• defensive programming:functions that fail gracefully if given bad arguments– much better to give an error message thanto return garbage!9/38Example: Arithmetic evaluation(define exp1 (make-sum (make-sum 3 15) 20))exp1 ==> (+ (+ 3 15) 20)(eval-1 exp1) ==> 38Expressions might include values other than numbersRanges:some unknown number between min and maxarithmetic: [3,7] + [1,3] = [4,10]Limited precision values:some value ± some error amountarithmetic: (100 ± 1) + (3 ± 0.5) = (103 ± 1.5)Create arithmetic expressionsEvaluate arithmetic expressions to reduce them to simpler form10/38Approach: start simple, then extend• Characteristic of all software engineering projects• Start with eval for numbers, then add support forranges and limited-precision values• Goal: build eval in a way that it will extend easily & safely• Easily: requires data-directed programming• Safely: requires defensive programming• Process: multiple versions of evaleval-1 Simple arithmetic, no tagseval-2 Extend the evaluator, observe bugseval-3 through -7 Do it again with tagged data 11/381. ADT (Abstract Data Type) for sums; type: Exp, Exp -> SumExp(define (make-sum addend augend)(list '+ addend augend)); type: anytype -> boolean(define (sum-exp? e) (and (pair? e) (eq? (car e) '+))); type: SumExp -> Exp(define (sum-addend sum) (cadr sum))(define (sum-augend sum) (caddr sum))• Type Exp will be different in different versions of eval12/381. Eval for numbers only; type: number | SumExp -> number(define (eval-1 exp)(cond((number? exp) exp)((sum-exp? exp)(+ (eval-1 (sum-addend exp))(eval-1 (sum-augend exp))))(else (error "unknown expression " exp))))(eval-1 (make-sum 4 (make-sum 3 5))) ==> 12; base case; recursive case313/38Example in gory detail(eval-1 (make-sum 4 (make-sum 3 5))) ==> 12+ 4+ 3 5Sum-exp? checks this using eq?(+ (eval-1 ) (eval-1 ))..Number? checks this(+ 4 ) Sum-exp? checks this using eq?(+ (eval-1 ) (eval-1 )). .(+ 4 (+ 3 5))14/382. ADT for ranges (no tags); type: number, number -> range2(define (make-range-2 min max) (list min max)); type: range2 -> number(define (range-min-2 range) (car range))(define (range-max-2 range) (cadr range)); type: range2, range2 -> range2(define (range-add-2 r1 r2)(make-range-2 (+ (range-min-2 r1) (range-min-2 r2))(+ (range-max-2 r1) (range-max-2 r2))))15/38Detailed example of adding ranges+ 37+ 13(list (+ )(+ ))... .410This is a range16/382. Eval for numbers and ranges (broken); type: number|range2|SumExp -> number|range2(define (eval-2 exp)(cond((number? exp) exp)((sum-exp? exp) (let ((v1 (eval-2 (sum-addend exp)))(v2 (eval-2 (sum-augend exp))))(if (and (number? v1) (number? v2))(+ v1 v2) ; add numbers(range-add-2 v1 v2)))) ; add ranges((pair? exp) exp) ; a range(else (error "unknown expression " exp))))17/382. Ways in which eval-2 is broken• Missing a case: sum of number and a range(eval-2 (make-sum 4 (make-range-2 4 6))) ==> error: the object 4 is not a pair18/382. Eval for numbers and ranges (broken); type: number|range2|SumExp -> number|range2(define (eval-2 exp)(cond((number? exp) exp)((sum-exp? exp) (let ((v1 (eval-2 (sum-addend exp)))(v2 (eval-2 (sum-augend exp))))(if (and (number? v1) (number? v2))(+ v1 v2) ; add numbers(range-add-2 v1 v2)))) ; add ranges((pair? exp) exp) ; a range(else (error "unknown expression " exp))))+ 44 6Range-add-2 expects two ranges, i.e. two lists!!419/382. Ways in which eval-2 is broken• Missing a case: sum of number and a range(eval-2 (make-sum 4 (make-range-2 4 6))) ==> error: the object 4 is not a pair• Not defensive: what if we add limited-precision valuesbut forget to change eval-2 ?(define (make-limited-precision-2 val err)(list val err))(eval-2 (make-sum (make-range-2 4 6)(make-limited-precision-2 10 1)))==> (14 7) correct answer: (13 17) or (15 2)Key point – doesn’t return an error, but gives us what appears to be a legitimate answer!!!20/382. Lessons from eval-2• Common bug: calling a function on the wrong type of data•typos•brainos• changing one part of the program and not another• Common result:
View Full Document
Unlocking...