Tengs-Fan/SICP

Structure and Interpretation of Computer Program

This is the answers to the SICP book, you can also check sicp-solutions

Building Abstraction with Data

Data Abstraction

1. Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible?

Mathematical Explanation We can see it as a problem of finding extrema of n-variate functions. for R1, R2, R_, … these are variables, The interval of R1, R2, R_, … are the definition fields. The operations on variables are the function. And we want to find the maximum and minimum of the function in the definition fields. For the general questions, It’s very clear that for most functions, their extrema won’t be found in the border, so we can’t simple get the result by operating on lower and upper bound. For the specific question there, the problem is that the functions Lem wrote assume the variables are independent. If the variables are dependent, the result is wrong. For example, R1 = [1, 2]; R2 = R1 + 1=[2, 3], then R1 and R2 are dependent, so R1 - R2 = 1, and (sub-interval R1 R2) = [0, 2] is wrong. Here, for par1, R1*R2 and R1+R2 are dependent, so (div-interval R1*R2 R1+R2) got wrong answer. But, for pa2, [1,1] and R1; [1,1] and R2; 1/R1 and 1/R2; [1,1] and 1/R1 + 1/R2; they are all independent, so the result is right. If we want let the result be correct, either we change the code fundamentally, or we need to ensure for each operation, their operands should be independent.

Hierarchical Data & Closure

1. Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:

#lang sicp
(define (last-pair items)
  (let ((rest (cdr items)))
    (if (null? rest)
        items
        (last-pair rest))
  ))

(last-pair (list 23 72 149 34))

1. Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:

#lang sicp
;; (define (reverse items)
;;   (let ((rest (cdr items)) (first (car items)))
;;     (if (null? rest)
;;         (cons items nil)
;;         (cons (reverse rest) first)
;;         )))
; Fail because the structure of the list, also it uses recursion and will like have low performance
(define (reverse items)
  (define (iter items result)
    (if (null? items)
        result
        (iter (cdr items) (cons (car items) result))))
  (iter items nil))
; Use loop instead of recursion

(reverse (list 1 4 9 16 25))

1. We want to rewrite the procedure cc so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency. We could then call cc as follows: (cc 100 us-coins), Define the procedures first-denomination, except-firstdenomination, and no-more? in terms of primitive operations on list structures. Does the order of the list coin-values affect the answer produced by cc? Why or why not?

   This is like a Non-deterministic Turing Machine, for each amount we have multiple ways to get this number, and each amount can add up to some amount, the order doesn’t matter.

#lang sicp
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (except-first-denomination values)
  (cdr values))
(define (first-denomination values)
  (car values))
(define (no-more? values)
  (null? values))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination
                 coin-values))
            (cc (- amount
                   (first-denomination
                    coin-values))
                coin-values)))))

(cc 100 us-coins)

1. The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument.

   #lang sicp
   (define (same-parity a . c)
     (define (same-with-first ele)
       (if (odd? a)
           (odd? ele)
           (even? ele))
       )
     (define (appends lst ele)
       (if (same-with-first ele)
           (append lst (list ele))      ;;The list structure inside LiSP is quite embrrassing
           lst)
       )
     (define (iter lst result)
       (if (null? lst)
           result
           (iter (cdr lst) (appends result (car lst))))
       )
     (iter c (cons a nil))
     )
   (same-parity 1 2 3 4 5 6 7)
   (same-parity 2 3 4 5 6 7)