[Scheme] Checking The Validity of The Number Passed to The List

6-1-2014

In many programming languages,
when we pass the number n to the array which the length is equal or less than n, we get an exception.

The following is the example of C:


int main(void){
    int hoge[] = {0,1,2,3};
    printf("%d", hoge[3]); // output: 3
    printf("%d", hoge[4]); // get a warning
    return 0;
}

We can implement this kind of exception in Scheme by using the procedure length which is introduced in SICP 2.2.1.

The code will be as follows:


; returns the length of a list
(define (length li)
  (define (length-iter n iter-li)
    (if (null? iter-li)
      n
      (length-iter (+ n 1) (cdr iter-li))))
  (length-iter 0 li))

; check if the value passed to the list is valid
(define (cdr-chk-err li n)
  (cond ((or (> n (length li)) (= n (length li)))
    (error "Invalid value passed to the list. "))))

(define (list-ref n)
  (lambda (x)
    (cdr-chk-err x n)
    (if (= n 0)
      (car x)
      ((list-ref (- n 1)) (cdr x)))))

This works correctly.


(define l1 (list 1 2 3 4))
((list-ref 3) l1) ; returns 4
((list-ref 4) l1) ; error!

[SICP 2.1.4] Some Observation about Exercise 2.16

5-31-2014

First time I saw this problem, I wondered how it works when I use fractions instead of decimals until the final operation is executed( if the number is not accurate one, then convert it to the fraction like 3.14 to 314 / 100 ).

To examine this, let’s define a function calculating some complex value.

 

(define (g n)
  (define (g-iter result i)
    (if (= i n)
      result
      (g-iter (+ (/ (/ (/ 312423 125531) (/ 2052712 7231400)) (/ 13222 113131)) result) (+ i 1)
  )))
  (g-iter 1 1)
)

The result of the operation is returned as a fraction:
(19358134129159 * 750189) * 5180721713949/19358134129159

Each term is absolutely determined value.
For getting the decimal number from this fraction value, we just need to multiply this by 1.0.


(* 1.0 (g 10000)) ; 750189.2676250552

If we use the decimal number in the calculation, the different result will show up:


(define (g n)
  (define (g-iter result i)
    (if (= i n)
      result
      (g-iter (+ (/ (/ (/ 312423.0 125531) (/ 2052712 7231400)) (/ 13222 113131)) result) (+ i 1)
  )))
  (g-iter 0 0)
)

(g 10000) ; 750189.2676250958

Then which number is more near the actual value?
Let’s calculate ((((312423 / 125531) / (2052712 / 7231400)) / (13222 / 113131)) * 10000) in the Wolframalpha.
Calc result

750189.2676250551516388667249372079289168657014682584005287499...

It seems that the former one is more accurate.

However, the fraction-version calculation will lose its speed when the number of calculation grows up. If we try to execute function g 10000000 times, the response of the fraction-version one is cruel in contrast to the decimal-version one which outputs the result within 0.5s.

[SICP 2.1.4] Exercise 2.11 Memo

5-30-2014

Exercise 2.11: Rewrite procedure mul-interval using Ben’s suggestion.

The default mul-interval executes 4 multiplications on every case of operations, because the process calculates p1 to p4 regardless of the signs of the endpoints.
So, the objective of this problem is to minimize the number of operations.


(define (mul-interval x y)
  (let
    ((mi make-interval)
     (lx (lower-bound x))
     (ux (upper-bound x))
     (ly (lower-bound y))
     (uy (upper-bound y)))
  (cond
    ((and (neg-int? x) (neg-int? y))
      (mi (* lx ly) (* ux uy)))
    ((and (neg-int? x) (zero-span? y))
      (mi (* lx uy) (* lx ly)))
    ((and (neg-int? x) (pos-int? y))
      (mi (* ux uy) (* lx ly)))
    ((and (zero-span? x) (neg-int? y))
      (mi (* ux uy) (* lx uy)))
    ((and (zero-span? x) (pos-int? y))
      (mi (* lx uy) (* ux uy)))
    ((and (pos-int? x) (neg-int? y))
      (mi (* ux uy) (* lx ly)))
    ((and (pos-int? x) (zero-span? y))
      (mi (* ux ly) (* ux uy)))
    ((and (pos-int? x) (pos-int? y))
      (mi (* lx ly) (* ux uy)))
    ((and (zero-span? x) (zero-span? y))
      (mi (min (* lx uy) (* ux ly)) (max (* lx ly) (* ux uy)))))))

(define i1 (make-interval -5 3))
(define i2 (make-interval -2 110))
(mul-interval i1 i2) ; (-550, 330)

Note that there will be no point to rewrite the procedure if you write the multiplication as the variable defined in the `let`, because variables we define in `let` are all executed whether or not we use them. In this case, if you write as follows, 4 multiplications are executed in mul-interval every time:

(define (mul-interval x y)
  (let
    ((mi make-interval)
     (lxly (* (lower-bound x) (lower-bound y)))
     (lxuy (* (lower-bound x) (upper-bound y)))
     (uxly (* (upper-bound x) (lower-bound y)))
     (uxuy (* (upper-bound x) (upper-bound y))))
  :
  :
  :

If you want to confirm this kind of behavior of `let`, try defining (zero-div (/ 1 0)) as an variable of `let`, and you’ll soon get zero-division error even if you aren’t using variable zero-div in the process.

[SICP 2.1.4] Some Observation about Exercise 2.10

5-29-2014

Exercise 2.10- Ben Bitdiddle, an expert systems programmer, looks over Alyssa’s shoulder and comments that it is not clear what it means to divide by an interval that spans zero. Modify Alyssa’s code to check for this condition and to signal an error if it occurs.

There were many blog posts which talks about Exercise 2.10, and I’ve found that there were 2 ways of understanding of the problem on the internet.

  • The problem literally tells us to implement an error that occurs when we pass two arguments that spans zero (like -5 and 3).
  • The problem tells us to implement errors by zero division.

So, which one is correct? After a straightforward survey, I’ve found that the answer seems to be the former one.

Then why people feel confused to understand the meaning of the problem?

At a first glance, not a few people might have thought that “OK, this is an problem that related to the procedure div-interval, right?”, then tried to pass arguments for div-interval like this:


(define i1 (make-interval 5 5))
(define i2 (make-interval -5 5))
(div-interval i1 i2) ; (-1.0 . 1.0)

The output seems to work correct ( in fact it does, because the procedure mul-interval properly extracts the result from p1 ~ p4, using the procedures min & mul ). Now we don’t know what the actual problem is.

The answer is simple. What we really had to check was not the procedure div-interval but the following process:


(make-interval (/ 1.0 (upper-bound x)) (/ 1.0 (lower-bound x)))

Let’s check the behavior of this process.


(define i (make-interval -5 5))
  (make-interval (/ 1.0 (upper-bound i)) (/ 1.0 (lower-bound i))) ; (0.2, -0.2)

The output is (0.2, -0.2), and now we know what we have to do is:


(define (reciprocal-interval x)
(if (< (* (upper-bound x) (lower-bound x)) 0) (error "The arguments spans 0") (make-interval (/ 1.0 (upper-bound x)) (/ 1.0 (lower-bound x))))) [/shell] I think this is the true understanding of the exercise 2.10. As long as we use the reciprocal-value for only the procedure div-interval, it works well, so we don't need to implement the error function. However, say we want to implement another procedure using the reciprocal interval --- the tragedy occurs. So we have to test the black-box thoroughly even if one of abstract procedures that using the black-box seems to work fine. They can sometimes hide the flaw of the implementation and make problem difficult, like this exercise.

[SICP 2.1.3] Exercise 2.5 Memo

5-26-2014

Exercise 2.5- Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2^a3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

So far, we’ve seen an implementation of these procedures using lambda expression. By the way, it seems that we can implement them with only numbers and some arithmetic operations according to the problem, so let’s create that version of the procedures.

First of all, We need a procedure that tells us the power of 2 and 3 from a value.

(define (find-times-of-n n x)
  (define (iter dev-x result)
    (let ((r (remainder dev-x n)))
      (if (= r 0) (iter (/ dev-x n) (+ result 1))
                  result)))
  (iter x 0))

What we have to do for getting the power of n( in this case, 2 or 3 would be passed ) from value x is only devide n from x until the remainder of the value / n is non-zero.

Next, we’ll create procedure cons. This is easy because we only need to create a procedure that takes two arguments ( a and b ), and returns 2^a3^b. The procedure will be as follows:


(define (pow x n)
  (define (iter i result)
    (if (= i n) result (iter (+ i 1) (* result x))))
  (iter 0 1))

(define (cons x y) (* (pow 2 x) (pow 3 y)))

Finally, we’ll create procedure car and cdr. Let’s use the procedure find-times-of-n:


(define (car cons) (find-times-of-n 2 cons))
(define (cdr cons) (find-times-of-n 3 cons))

If we want to get the output, you can implement the procedure like this:


(define (print-cons cons)
  (newline)
  (display "(")
  (display (car cons))
  (display ",")
  (display (cdr cons))
  (display ")"))

(define hoge (cons 61 22))
(print-cons hoge) ; (61, 22)