116.001 SICPTagged data• Why do we need tags• Concept of tags• Extended example2Manipulating 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 coordinates3Bert’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)))4Ernie’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))5Whose number is it?• Suppose we pick up the following object12• What number does this represent?6Labeled 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))27The 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))8Benefits 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!9Example: 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)10Approach: 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• Today: multiple versions of evaleval-1 Simple arithmetic, no tagseval-2 Extend the evaluator, observe bugseval-3 through -7 Do it again with tagged data 111. 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 eval121. 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 case313Example 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))142. 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))))15Detailed example of adding ranges+ 37+ 13(list (+ )(+ ))... .410This is a range162. 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))))172. 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 pair182. 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!!4192. 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)202. 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: the function returns garbage• Why? Prim. predicates (number?, pair?) are ambiguous• Something fails later, but cause is hard to track down• Worst case: program produces incorrect output!!• Next: how to use tagged data to ensure the program halts immediately213. Start again using tagged data• Take another look at SumExp ... it's already tagged!(define sum-tag '+); Type: Exp, Exp -> SumExp(define (make-sum addend augend)(list sum-tag addend augend)); Type: anytype -> boolean(define (sum-exp? e) (and (pair? e) (eq?
View Full Document
Unlocking...