brian_hassinger

software developer

Introduction to Data Abstraction

February 19, 2013

Finishing Chapter 1 of The Structure and Interpretation of Computer Programs feels excellent! Let’s keep the mojo flowing and power on through to Chapter 2.

One thing I love about working through this book is developing a solution, and then comparing it to the work of other people. I’m often amazed at how different or similar our answers can be. There is only one exercise for the first section of chapter 2, so I will highlight the differences in answers from various sources.

Exercise 2.01

Define a better version of make-rat that handles positive and negative arguments, normalizing the signs.

(define (make-rat n d)
  (if (> 0 d)
    (make-rat (- n) (- d))
    (let ((g (gcd (abs n) (abs d))))
        (cons (/ n g) (/ d g)))))

My solution when the denominator is less than 0 is to flip both numerator and denominator and pass them back into the make-rat procedure. Also I found I had to use the abs values of n and d for the gcd otherwise the signs would not be preserved.

On to [Eli Bendersky][eli]. Keep in mind Eli is using Common Lisp. [eli]: http://eli.thegreenplace.net/2007/07/25/sicp-sections-211-212/

(defun make-rat (n d)
  (labels (
    (make-rat-reduce (n d)
      (let ((g (gcd n d)))
        (cons (/ n g) (/ d g)))))

    (cond ((and (< n 0) (< d 0))
            (make-rat-reduce (- n) (- d)))
          ((and (< d 0) (> n 0))
            (make-rat-reduce (- n) (- d)))
          (t
            (make-rat-reduce n d)))))

Here Eli has a condition to check when the numerator and denominator are both negative, or only the denominator is negative. In both cases the solution is to negate both numerator and denominator. If neither case is true then just proceed as normal. I haven’t run Eli’s code, but I suspect his gcd will not preserve the signs as he intends. This is similar to a problem I ran into with my solution which is why I use the abs for g.

On to [Bill the Lizard][bill]’s solution. [bill]: http://www.billthelizard.com/2010/09/sicp-21-rational-numbers.html

(define (make-rat n d)
  (let ((g (gcd n d)))
    (if (< d 0)
        (cons (/ (* n -1) g) (/ (* d -1) g))
        (cons (/ n g) (/ d g)))))

Bill’s solution is much simpler. Here the numerator and denominator are negated only if the denominator is less than zero. This negation is done directly in the cons procedure by the multiplication primitive.

On to [flaming0][flame]’s solution. [flame]: https://github.com/flaming0/SICP/blob/master/ch2/ex2-1.scm

(define (make-rat n d)
  (let ((g (gcd n d)))
    (if (< d 0)
        (cons (/ (- n) g) (/ (- d) g))
        (cons (/ n g) (/ d g)))))

Flaming0’s solution is identical to Bill’s except flaming0 uses the negative procedure to produce a negative value. Subtle difference, but I love it!

And finally, the [Scheme Community Wiki][scw] solution. [scw]: http://community.schemewiki.org/?sicp-ex-2.1

(define (make-rat n d) 
   (let ((g ((if (< d 0) - +) (gcd n d)))) 
     (cons (/ n g) (/ d g)))) 

This solution is a bit more clever than the rest. It will negate the gcd if the denominator is less than zero. This change of signs is applied to both numerator and denominator during the division by g in the cons process.

After running through all these solutions my favorite is flaming0’s for it’s simplicity and legibility. All the differences here are rather subtle, but each have their own merits and show how a self-taught course in SICP is interesting.