guile-sicp/exercise-2.01--abstraction-barriers--normalize-sign-and-reduce-fractions/solution.scm

;; Why compound data?

;; To raise the conceptual level at which we design programs.
;; To be able to handle many things as one thing and talk about as if it were really only one thing.
;; When there are too many different things to keep in mind, we will lose track and get confused.

;; Task

;; We imagine to design a system for performing arithmetic operations.

;; DATA ABSTRACTION:

;; Isolate the parts of the programm, which deal with how data objects
;; are represented frim the parts of the programm, that deal with how
;; data objects are used.
;; Using data abstraction we can make our programs work on abstract
;; data, making no assumptions about the data, which are not
;; necessary.
;; Selectors and constructors (procedures) implement abstract data in
;; terms of their concrete representation.

;; Example: Rational numbers can be represented as pairs of
;; integers. But the rest of the program should only think of them as
;; rationals and not have to care about how they are actually
;; represented. The rest of the program should instead use operations
;; on them, which abstract this detail away.

;; Example: Linear combination

#;(define (linear-combination-bad a b x y)
  (+ (* a x)
     (* b y)))

;; However, defined like this, it can only deal with things, that the
;; primitive + and * operations can process.

;; Suppose we want the linear combination of rational numbers, complex
;; numbers or polynomials. Then this will not do. Instead, we could
;; use more generic operations like `add` and `mul`, which can be
;; defined to be more complex operations, which work on many types of
;; arguments:

#;(define (linear-combination a b x y)
  (add (mul a x)
       (mul b y)))

;; NOTE:

;; We already learned about something called PROCEDURE ABSTRACTION:
;; Isolating the way a procedure is constructed from how the procedure
;; is used.

;; Example: Rational Numbers

;; make-rat is later changed to reduce the fractions
(define (make-rat-no-reduce numerator denominator)
  (cons numerator denominator))

;; make-rat is using the gcd procedure
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(define (make-rat-with-reduce n d)
  (let ((g (gcd n d)))
    (cons (/ n g)
          (/ d g))))

(define (numer rational-number)
  (car rational-number))

(define (denom rational-number)
  (cdr rational-number))

;; Now we can define more complex operations on top of the data
;; abstraction for rational numbers as follows:

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

;; We add an optional output port as argument here to be able to
;; better test the print procedure. It can be ignored in normal usage
;; and the procedure can be made to output to a string while testing.
(define* (print-rat x #:optional port)
  (display
   (simple-format #f
                  "~a/~a\n"
                  (numer x) (denom x))
   port))

;; ============
;; Exercise 2.1
;; ============

;; Define a better version of make-rat that handles both
;; positive and negative arguments. make-rat should normalize the sign
;; so that if the rational number is positive, both the numerator and
;; denominator are positive, and if the rational number is negative,
;; only the numerator is negative.

;; ============
;; Solution 2.1
;; ============

(define (sign num)
  (if (< num 0) - +))
;; Only defining `negative?` and `positive?` in case the Scheme
;; dialect does not support them already.
(define (negative? num)
  (equal? (sign num) -))
(define (positive? num)
  (equal? (sign num) +))

(define (reduce-numer-and-denom numerator denominator)
  (let ([g (abs (gcd numerator denominator))])
    (cons (/ numerator g)
          (/ denominator g))))

(define (normalize-sign numerator denominator)
  (cond
   ;; When there are 2 negative numbers, we want both signs to be
   ;; inverted, so that only positive numbers remain. Since we want
   ;; to invert sign if only the denominator is negative, so that
   ;; the numerator instead is the negative number, asking the
   ;; question, whether the numerator is negative and the
   ;; denominator is negative is irrelevant. This case is already
   ;; covered by only asking whether the denominator is negative.
   #;[(and (negative? numerator) (negative? denominator))
   (cons (/ (* -1 numerator) g)
   (/ (* -1 denominator) g))]

   [(negative? denominator)
    (cons (* -1 numerator)
          (* -1 denominator))]
   [else
    (cons numerator denominator)]))
;; -> `make-rat` shall not receive a sign as an argument, in order to
;; still conform to the interface we are currently assuming make-rat
;; to adhere to.
(define (make-rat numerator denominator)
  ;; By accessing car and cdr here, we do not assume that the
  ;; `normalize-sign` procedure returns a fraction, but instead
  ;; assume, that it will return a pair of numbers as a result. If the
  ;; fraction representation changes, the `normalize-sign` procedure
  ;; remains unchanged.

  ;; `reduce-numer-and-denom` takes 2 numbers as well, also remaining
  ;; independent of the actual fraction representation.
  (let ([normalized-numer-and-denom (normalize-sign numerator denominator)])
    (let ([numer-and-denom
           (reduce-numer-and-denom (car normalized-numer-and-denom)
                                   (cdr normalized-numer-and-denom))])
      ;; By "unpacking" numer-and-denom here again we express the
      ;; representation of fractions using cons explicitly, instead of
      ;; relying on the return value from reduce-numer-and-denom.
      (cons (car numer-and-denom) (cdr numer-and-denom)))))

;; =====
;; ASIDE
;; =====

;; In Guile Scheme we can also write it as follows:
;; A required import:
(use-modules (ice-9 receive))

(define (reduce-numer-and-denom-multi-value numerator denominator)
  (let ([g (abs (gcd numerator denominator))])
    (values (/ numerator g)
            (/ denominator g))))

(define (normalize-sign-multi-value numerator denominator)
  (cond
   [(negative? denominator)
    (values (* -1 numerator)
            (* -1 denominator))]
   [else
    (values numerator denominator)]))

(define (make-rat-guile-scheme numerator denominator)
  (receive (sign-norm-numer sign-norm-denom)
      (normalize-sign-multi-value numerator denominator)
    (receive (reduced-numer reduced-denom)
        (reduce-numer-and-denom-multi-value sign-norm-numer sign-norm-denom)
      (cons reduced-numer reduced-denom))))

;; This would avoid constructing and deconstructing pairs of numerator
;; and denominator multiple times, but I guess, it would create
;; lambdas instead in the `receive` macro.

;; =========
;; Tests 2.1
;; =========
(use-modules (srfi srfi-64))

;; (define (call-with-output-string procedure)
;;   (let ((port (open-output-string)))
;;     (procedure port)
;;     (get-output-string port)))

(test-begin "test-2.01")
(test-group
 "test-2.01"
 (test-assert
     (string=?
      (string-trim-both (call-with-output-string
                          (λ (port)
                            (print-rat (make-rat 1 2) port)))
                        char-set:whitespace)
      "1/2"))

 (test-assert
     (string=?
      (string-trim-both (call-with-output-string
                          (λ (port)
                            (print-rat (make-rat -1 2) port)))
                        char-set:whitespace)
      "-1/2"))

 (test-assert
     (string=?
      (string-trim-both (call-with-output-string
                          (λ (port)
                            (print-rat (make-rat 1 -2) port)))
                        char-set:whitespace)
      "-1/2"))

 (test-assert
     (string=?
      (string-trim-both (call-with-output-string
                          (λ (port)
                            (print-rat (make-rat -1 -2) port)))
                        char-set:whitespace)
      "1/2"))

 (test-assert
     (string=?
      (string-trim-both (call-with-output-string
                          (λ (port)
                            (print-rat (make-rat 10 -2) port)))
                        char-set:whitespace)
      "-5/1"))

 (test-assert
     (string=?
      (string-trim-both (call-with-output-string
                          (λ (port)
                            (print-rat (make-rat 10 -30) port)))
                        char-set:whitespace)
      "-1/3")))

(test-end "test-2.01")