Comp 210 Lab 3: List of bits example, define-struct

Index: List of bits example, define-struct

List of bits example

In high school, you probably learned about binary numbers. If not, we will briefly review them. A binary number (or, number in base two) consists of only 0's and 1's, rather than 0's through 9's, as in decimal numbers. The right-most binary digit ("bit") represents the number of ones counted, the next-right-most bit represents the number of twos counted, and further bits represent increasing powers of two. E.g., 10110 (binary) = 16*1 + 8*0 + 4*1 + 2*1 + 1*0 = 22 (decimal).

Data definitions

We will represent binary numbers as a list of bits. Our data definitions are A Bit is either

A List of Bits (LoB) is either

We already have the functions zero?, null?, and cons?. It's convenient to also define 

   (define one?
     (lambda (b)
       (= b 1)))

The "meaning" of a list of bits is as follows:

If you think about it, we are really defining a "value" function on List of Bits, and the definition of the mathematical function is specified recursively, just like the data structure was.

Note that the list represents the binary number backwards. E.g., the binary number 10110 is represented by (cons 0 (cons 1 (cons 1 (cons 0 (cons 1 null))))). Furthermore, the above meaning says that this list represents the value 0 + 2(1 + 2(1 + 2(0 + 2(1 + 0)))) = 22, as expected.

Program Templates

We can do this much without even knowing what we are trying to write: 

;;   (define lob-function
;;     (lambda (lob)
;;       (cond ((null? lob) ...)
;;             (else        ...(car lob)...(lob-function (cdr lob))... ))))

Since there are two possibilities for (first lob), namely 0 and 1, we should also define a template for Bits, and use it: 

;;   (define bit-function
;;     (lambda (b)
;;       (cond ((zero? b) ...)
;;             (else      ...))))
;;
;;   (define lob-function
;;     (lambda (lob)
;;       (cond ((null? lob) ...)
;;             (else        ...(bits-function (car lob))...
;;                          ...(lob-function (cdr lob))... ))))

Functions

We can use our program templates to guide us in defining functions on Lists of Bits, e.g, log->num, addone, and subone.

Conversions

Functions to convert a list of bits into a number follow from our "meaning" we gave before: 

    (define bit->num
      (lambda (b)
        (cond ((zero? b) b)
              (else      b))))
    (define lob->num
      (lambda (lob)
        (cond ((null? lob) 0)
              (else        (+ (bit->num (first lob))
                              (* 2 (lob->num (cdr lob))))))))

The program templates led us to write a correct program. But, now observe that we can easily simplify it: 

    (define lob->num
      (lambda (lob)
        (cond ((null? lob) 0)
              (else        (+ (first lob)
                              (* 2 (lob->num (cdr lob))))))))

Going the other direction, converting a number into a List of Bits, follows the template for natural numbers, not the above template. 

   (define num->lob
     (lambda (n)
        (cond ((zero? n) null)
              (else      (cons (remainder n 2)
                               (num->lob (quotient n 2)))))))

Adding and subtracting

Writing addone and subone for Lists of Bits is more difficult. You already know how to do it, since it's just like addition and subtraction on decimal numbers. But we need to figure out how to write functions that deal with "carrying" in addition and "borrowing" in subtraction. 

   (define addone
     (lambda (lob)
       (cond ((null? lob) (cons 1 null))
             (else        (if (zero? (first lob))
                              (cons 1 (rest lob))
                              (cons 0 (addone (rest lob))))))))

To understand this, remember that if (null? lob) is true, then we are at the front of our binary number, since our list representation is backwards. Thus, the first case simply puts the 1 we are adding at the front when we are done. Otherwise, the list of bits is not empty, and we are looking at the first bit in the list. This represents the last bit in the number that we haven't looked at yet. If this bit we are currently looking at in the list is 0, we can do our addition since 0+1=1. Otherwise, the bit is a 1, and since 1+1=10 we have to continuing carrying to the next position.

Defining subone is very similar. For convenience, we assume that if we subtract 1 from 0 (or rather its representation), we get 0 again. 

   (define subone
     (lambda (lob)
       (cond ((null? lob) null)
             (else        (if (zero? (first lob))
                              (cons 1 (subone (rest lob)))
                              (cons 0 (rest lob)))))))

Things to think about

How would you define addition of two Lists of Bits? Hint: you'll want to use addone.

How would you define multiplication? Here's two alternative hints: