Oscar Del Ben

New blog

I've started a new personal development blog. Please check it out if you are interested in that argument.

New section for sicp posts

I'm going to port all the sicp exercises on the new site. If you are interested in them, you should follow this page. Enjoy

Routes 0.0.2 released

Routes is a simple library to deal with routes in ruby.

Changes includes:

• corrected lambda execution behaviour

You can browse the source code on github or install it as as gem with:

gem sources -a http://gems.github.com

gem install oscardelben-routes

SICP section 2.53

I will skip this last part of chapter 2 because it is to much work for me. If you are interested in it, you can take a look at this post.

SICP exercise 2.86

Introduction

Suppose we want to handle complex numbers whose real parts, imaginary parts, magnitudes, and angles can be either ordinary numbers, rational numbers, or other numbers we might wish to add to the system. Describe and implement the changes to the system needed to accommodate this. You will have to define operations such as sine and cosine that are generic over ordinary numbers and rational numbers.

Discussion

I don't know how to create this type of complex numbers but I know that we have selectors for the real part, imaginary part etc of a complex number, so the changes would affect only those parts meaning that the rest of the system will remain as is.

SICP exercise 2.85

Introduction

This section mentioned a method for "simplifying'' a data object by lowering it in the tower of types as far as possible. Design a procedure drop that accomplishes this for the tower described in exercise 2.83. The key is to decide, in some general way, whether an object can be lowered. For example, the complex number 1.5 + 0i can be lowered as far as real, the complex number 1 + 0i can be lowered as far as integer, and the complex number 2 + 3i cannot be lowered at all. Here is a plan for determining whether an object can be lowered: Begin by defining a generic operation project that ``pushes'' an object down in the tower. For example, projecting a complex number would involve throwing away the imaginary part. Then a number can be dropped if, when we project it and raise the result back to the type we started with, we end up with something equal to what we started with. Show how to implement this idea in detail, by writing a drop procedure that drops an object as far as possible. You will need to design the various projection operations53 and install project as a generic operation in the system. You will also need to make use of a generic equality predicate, such as described in exercise 2.79. Finally, use drop to rewrite apply-generic from exercise 2.84 so that it "simplifies'' its answers.

Discussion

First we define and install project:

(define (install-project)

  (define (project-complex x)

    (make-real (real-part x)))

  (define (project-real x)

    (make-rat (round x) 1))

  (define (project-rational x)

    (numer x))

  

  (put 'project '(complex) project-complex)

  (put 'project '(real) project-real)

  (put 'project '(rational) project-rational))

Then the procedures can-be-lowered? and drop:

(define (can-be-lowered? n)

  (and

    (not (= (type-tag n) 'scheme-number))

    (equ? n (raise (project n)))))




(define (drop n)

  (if (can-be-lowered? n)

    (drop (project n))

    n))

And finally the new version of apply-generic:

(define (apply-generic op . args)

  (let ((type-tags (map type-tag args)))

    (let ((proc (get op type-tags)))

      (if proc

          (drop (apply proc (map contents args)))

          (if (= (length args) 2)

              (let ((type1 (car type-tags))

                    (type2 (cadr type-tags))

                    (a1 (car args))

                    (a2 (cadr args)))

                (let ((t1->t2 (get-coercion type1 type2))

                      (t2->t1 (get-coercion type2 type1)))

                  (cond (t1->t2

                         (apply-generic op (t1->t2 a1) a2))

                        (t2->t1

                         (apply-generic op a1 (t2->t1 a2)))

                        (else

                         (error "No method for these types"

                                (list op type-tags))))))

              (error "No method for these types"

                     (list op type-tags)))))))

SICP exercise 2.84

Introduction

Using the raise operation of exercise 2.83, modify the apply-generic procedure so that it coerces its arguments to have the same type by the method of successive raising, as discussed in this section. You will need to devise a way to test which of two types is higher in the tower. Do this in a manner that is "compatible'' with the rest of the system and will not lead to problems in adding new levels to the tower.

Discussion

(define tower '(integer rational real complex))

(define (tower-pos symbol tower)

  (if (= (car tower) symbol)

    0

    (+ 1 (tower-pos symbol (cdr tower)))))

(define (apply-generic op . args)

  (let ((type-tags (map type-tag args)))

    (let ((proc (get op type-tags)))

      (if proc

          (apply proc (map contents args))

          (if (= (length args) 2)

              (let ((type1 (car type-tags))

                    (type2 (cadr type-tags))

                    (a1 (car args))

                    (a2 (cadr args)))

                (cond

                  ((< (tower-pos type1 tower) (tower-pos type2 tower))

                    (apply-generic op (raise (car args)) (cadr args)))

                  ((> (tower-pos type1 tower) (tower-pos type2 tower))

                    (apply-generic op (car args) (raise (cadr args))))

                  (else (error "No method for these types"

                    (list op type-tags)))))

              (error "No method for these types"

                     (list op type-tags)))))))

SICP exercise 2.83

Introduction

Suppose you are designing a generic arithmetic system for dealing with the tower of types shown in figure 2.25: integer, rational, real, complex. For each type (except complex), design a procedure that raises objects of that type one level in the tower. Show how to install a generic raise operation that will work for each type (except complex).

Discussion

(define (install-raise)

  (put 'raise '(scheme-number)

    (lambda (x) (make-rat x 1)))

  (put 'raise '(rational)

    (lambda (x)

      (make-real (* (/ (numer x) (denom x)) 1.0))))

  (put 'raise '(real)

    (lambda (x) (make-from-real-imag x 0))))

SICP exercise 2.82

Introduction

Show how to generalize apply-generic to handle coercion in the general case of multiple arguments. One strategy is to attempt to coerce all the arguments to the type of the first argument, then to the type of the second argument, and so on. Give an example of a situation where this strategy (and likewise the two-argument version given above) is not sufficiently general. (Hint: Consider the case where there are some suitable mixed-type operations present in the table that will not be tried.)

Discussion

(define (apply-generic op . args)

  (let ((type-tags (map type-tag args)))

    (let ((proc (get op type-tags)))

      (if proc

        (apply proc (map contents args))

        (if (> (length args) 2)

          (apply-generic op

            (apply-generic op (car args) (cadr args))

            (cddr args))

          ; I assume otherwise there are 2 arguments 

          (let ((type1 (car type-tags))

                (type2 (cadr type-tags))

                (a1 (car args))

                (a2 (cadr args)))

            (let ((t1->t2 (get-coercion type1 type2))

                  (t2->t1 (get-coercion type2 type1)))

              (cond (t1->t2

                     (apply-generic op (t1->t2 a1) a2))

                    (t2->t1

                     (apply-generic op a1 (t2->t1 a2)))

                    (else

                     (error "No method for these types"

                            (list op type-tags))))))

          (error "No method for these types"

                 (list op type-tags)))))))

SICP exercise 2.81

Introduction

Louis Reasoner has noticed that apply-generic may try to coerce the arguments to each other's type even if they already have the same type. Therefore, he reasons, we need to put procedures in the coercion table to "coerce" arguments of each type to their own type. For example, in addition to the scheme-number->complex coercion shown above, he would do:

(define (scheme-number->scheme-number n) n)

(define (complex->complex z) z)

(put-coercion 'scheme-number 'scheme-number

              scheme-number->scheme-number)

(put-coercion 'complex 'complex complex->complex)

a. With Louis's coercion procedures installed, what happens if apply-generic is called with two arguments of type scheme-number or two arguments of type complex for an operation that is not found in the table for those types? For example, assume that we've defined a generic exponentiation operation:

(define (exp x y) (apply-generic 'exp x y))

and have put a procedure for exponentiation in the Scheme-number package but not in any other package:

;; following added to Scheme-number package

(put 'exp '(scheme-number scheme-number)

     (lambda (x y) (tag (expt x y)))) ; using primitive expt

What happens if we call exp with two complex numbers as arguments?

b. Is Louis correct that something had to be done about coercion with arguments of the same type, or does apply-generic work correctly as is?

c. Modify apply-generic so that it doesn't try coercion if the two arguments have the same type.

Discussion

a. Let's evaluate step by step what happens:

(apply-generic 'exp comp1 comp2)

type-tags is set to (complex complex) inside of apply-generic

proc is nil because we didn't define a predicate 'exp for 'complex 'complex

t1->t2 is set to the result of complex->complex, which is again complex and so we call apply-generic again with the same arguments, resulting in an infinite loop.

b. Louis is correct in the case that apply-generic is called with an operations not defined for the arguments type

c. We add a condition for it:

(define (apply-generic op . args)

  (let ((type-tags (map type-tag args)))

    (let ((proc (get op type-tags)))

      (if proc

        (apply proc (map contents args))

        (if (and (= (length args) 2)

              (not (= (type-tag (car type-tags)) (type-tag (cadr type-tags)))))

          (let ((type1 (car type-tags))

                (type2 (cadr type-tags))

                (a1 (car args))

                (a2 (cadr args)))

            (let ((t1->t2 (get-coercion type1 type2))

                  (t2->t1 (get-coercion type2 type1)))

              (cond (t1->t2

                     (apply-generic op (t1->t2 a1) a2))

                    (t2->t1

                     (apply-generic op a1 (t2->t1 a2)))

                    (else

                     (error "No method for these types"

                            (list op type-tags))))))

          (error "No method for these types"

                 (list op type-tags))))))))