Lab 4
Lists of Bits

Spring 1996

Lists of bits
Recursion on numbers
define-structure

Lists of bits

We will practice writing recursive programs by manipulating lists of bits.

Data definition

     <bit> :=   0
              | 1
     <list-of-bits> :=   null
                       | (cons <bit> <list-of-bits>)

A list of bits represents a number. Every list of bits represents a particular number, and every (nonnegative) number has a list-of-bits representation.

You can recognize a list of bits as the binary representation for the number (in reverse order), or you can mechanically apply the rules regarding the relationship between numbers and lists of bits. Each strategy works for some people; neither is ``right'' or ``wrong''.

The representation relationship is as follows:

  null represents 0
  (cons b l) represents  b + 2 * <whatever-l-represents>
  in other words, if lst is non-null, lst represents
        (car lst) + 2 * <whatever-is-represented-by-(cdr-lst)>

In the other direction, the rules are:

  0 is represented by null
  2a+b is represented by (cons b <whatever-represents-a>)

For instance,

  (list 1)       represents 1
  (list 0 1)     represents 2
  (list 0 1 1)   represents 6
  (list 1 1 0 1) represents 11

A list of bits is just the reversed binary representation for a number. In ordinary decimal numerals, the digits stand for ones, tens, hundreds, thousands, etc. In binary numerals, the digits stand for ones, twos, fours, eights, etc. So (list 1 1 0 1) represents a number with one one, one two, zero fours, and one eight - or 11.

We have reversed the ordinary representation for convenience, because Scheme puts lists together at the front and takes them apart there, too.

Computers use binary arithmetic internally.

Program Schema

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

    (define lob-function
      (lambda (lob)
        (if (null? lob)
            ...
            ... (car lob) ... (lob-function (cdr lob)) ... )))

Since there are two possibilities for (car lob)--0 and 1--we may wish to add another test:

    (define lob-function
      (lambda (lob)
        (if (null? lob)
            ...
            (if (zero? (car lob))
                ... (lob-function (cdr lob)) ...
                ... (lob-function (cdr lob)) ...))))

We will also write some functions that take two lists of bits as arguments:

    (define ???
       (lambda (l1 l2)
           (cond 
              ((null? l1)
                  (cond 
                     ((null? l2)      ........... )
                     ((zero? (car l2))   ...... ..)
                     (else ...........)))
              ((zero? (car l1))
                  (cond 
                     ((null? l2)      ........... )
                     ((zero? (car l2))   .........)
                     (else ...........)))
              (else 
                  (cond 
                     ((null? l2)      ........... )
                     ((zero? (car l2))   .........)
                     (else ...........))))))

Complete the program

We will try to write the following functions:

lob-to-num converts a list of bits into the number it represents.
num-to-lob converts a number into the list of bits that represents it. You may wish to use the quotient and remainder functions to convert a number n=2a+b into its parts a and b.
Remember that breaking a value into smaller parts is the key to recursion. We know we can break a non-empty list into two smaller parts (the car and the cdr, which is itself a list), and we just learned that we can break a number n into two parts (the number 1 and the number n-1). Here we are breaking a number n into two parts in a slightly more complicated way, but the concept is the same. We break n=2a+b into two parts a and b. We use b right away and save processing of a for the recursive call.
lob-quotient2 converts a list of bits representing a number n into the list of bits representing the number (quotient n 2). (Hint: this one is extremely simple, as is the next one; but be sure to use the program schema, or you will make errors. You may wish to provide the test cases first, and determine what the results should be; that can occasionally reveal the solution to you.)
lob-times2 converts a list of bits into a list of bits representing a number twice as great.
lob-add1 converts a list of bits into a list of bits representing the next larger integer. For instance,
(lob-add1 (list 1 0 0 1)) => (lob-add1 (list 0 1 0 1))
You can solve this problem using either the intuition of binary arithmetic, or just using the equations relating lists of bits to numbers.
- Use the following equations to get your result:
  (0) + 1 = 1
  (2a + 0) + 1 = 2a + 1
  (2a + 1) + 1 = 2(a+1) + 0
- Remember grade-school math: to add to a number, start at the least significant digit, and perform addition for just that digit. You take the single-digit result of the sum for that column, and possibly carry the more significant digit to the next column. To add binary numbers, we carry a 1 digit if the column sum was more than 2 (and we subtract 2 from the sum to get the remainder, which stays in that column in the result). For instance, consider the following table:
```
   summands   remainder  carry
    0   0         0        0
    0   1         1        0
    1   0         1        0
    1   1         0        1
```
  You don't even need this much to program lob-add1. The solution falls very naturally out of the recursive program schema: just try it!
The solution is:
```
      (define lob-add1
        (lambda (lob)
          (if (null? lob)
              (list 1)
              (if (zero? (car lob))
                  (cons 1 (cdr lob))
                  (cons 0 (lob-add1 (cdr lob)))))))
```
You could also use cond instead of if:
```
      (define lob-add1
        (lambda (lob)
          (cond
            ((null? lob)  (cons 1 null))
            ((zero? (car l))  (cons 1 (cdr lob)))
            (else  (cons 0 (lob-add1 (cdr lob)))))))
```
add takes two lists of bits and returns the list of bits representing the sum of the numbers represented by its inputs. You might want to first solve this when the inputs are known to be of the same length (though dealing with different-length inputs is not much harder). Again, we will consider two cases:
- Use the equations:
  (0) + (0) = 0
  (0) + (2a + b) = 2a+b
  (2a + b) + (0) = 2a+b
  (2x + 0) + (2y + 0) = 2(x+y) + 0
  (2x + 1) + (2y + 0) = 2(x+y) + 1
  (2x + 0) + (2y + 1) = 2(x+y) + 1
  (2x + 1) + (2y + 1) = 2(x+y+1) + 0
- Use grade-school arithmetic. There are a few ways to think about this:
  - Add two digits at a time; if there is a carry, then also add one to the result of adding up the more significant digits. (Remember that we already have a function that does just that.)
  - Add three digits at a time (digits from the two numbers, plus a carry which might be zero or one). The sum of three binary digits (bits) is 0, 1, 2, or 3. If it is 0 or 1, the carry is 0. If the sum is 2 or 3, then the carry is 1 and the remainder is 0 or 1 (respectively). You can either break this down into eight cases, or you can use the quotient and remainder functions to tell you the carry and the remainder.
Here is a solution:
```
      (define lob-add
        (lambda (l1 l2)
          (cond 
           ((null? l1)
            l2)
           ((zero? (car l1))
            (cond 
             ((null? l2)
              l1)
             ((zero? (car l2))
              (cons 0 (lob-add (cdr l1) (cdr l2))))
             (else (cons 1 (lob-add (cdr l1) (cdr l2))))))
           (else 
            (cond 
             ((null? l2)
              l1)
             ((zero? (car l2))
              (cons 1 (lob-add (cdr l1) (cdr l2))))
             (else
              (cons 0 (lob-add1 (lob-add (cdr l1) (cdr l2))))))))))
```

lob-mult takes two lists of bits and returns the list of bits representing the product of the numbers represented by its inputs. We can write lob-mult using the standard shift-and-add multiplication technique taught in grade school, but it's probably easier to just use the equations:

(0) * (0) = 0
(0) * (2a + b) = 0
(2a + b) * (0) = 0
(2x + 0) * (2y + 0) = 4xy
(2x + 1) * (2y + 0) = 4xy+2y
(2x + 0) * (2y + 1) = 4xy+2x
(2x + 1) * (2y + 1) = 4xy+2x+2y+1

Here is a solution:

      (define lob-mult
        (lambda (l1 l2)
          (cond 
           ((null? l1)
            null)
           ((zero? (car l1))
            (cond 
             ((null? l2)
              null)
             ((zero? (car l2))
              (cons 0 (cons 0 (lob-mult (cdr l1) (cdr l2)))))
             (else
              (lob-add l1 (cons 0 (cons 0 (lob-mult (cdr l1) (cdr l2))))))))
           (else 
            (cond 
             ((null? l2)
              null)
             ((zero? (car l2))
              (lob-add l2 (cons 0 (cons 0 (lob-mult (cdr l1) (cdr l2))))))
             (else
              (lob-add1
               (lob-add
                (lob-add
                 (cons 0 (cdr l1))
                 (cons 0 (cdr l2)))
                (cons 0 (cons 0 (lob-mult (cdr l1) (cdr l2))))))))))))

Note that (lob-mult (list 1) (list 1)) returns

(list
    1 0)

, which still denotes the number 1, but the trailing zeroes are aesthetically unpleasant. Think about why this happens and fix the program to avoid the extraneous zeroes.

Supply test data

Don't forget to test your functions!

Recursion on numbers

Define a Scheme function fact that computes the familiar factorial (written as the postfix operator !) function defined by the rule

Make sure that the definition has the proper layout. Save your factorial function in a file fact.ss. Compute (fact 0), (fact 10), (fact 100), and (fact 1000).

define-structure

Scheme can represent several useful types of data: numbers, booleans (truth values), symbols, lists, strings, etc. But sometimes what Scheme gives us just isn't enough. In these cases, we can use define-structure to create a new datatype. The resulting type is sometimes called a compound datatype because it can be broken into its constituent pieces, just as a non-empty list can be broken into its car and its cdr. Other types are atomic, such as numbers and booleans.

Compound datatypes are especially useful when we want to group related data--such as my bowling scores and the dates on which I got those scores, or even the year, month, and day parts of a date.

We could just aggregate information in a list, then extract it using the proper sequence of calls to car and cdr, but that has a number of disadvantages:

It's tedious and error-prone to type all the cars and cdrs; how do you know when you have enough, or whether you have too many?
For the same reason, code is much easier to read if the selectors are given intuitive names rather than being messes of list operations.
If the representation changes (say, to add another field, or remove one), then we don't have to find every use of cdr in the program, and figure out whether it needs to be changed.
Structure selectors may do some error-checking; but list operations only check that their argument is a list, and if everything is a list, you delay your discovery of errors (and make finding the underlying cause more difficult).
Most implementations of define-structure produce code that is faster than the equivalent list operations would be, especially for large structures which contain many fields.

We supply define-structure with the name of the new type and the names of its components, all enclosed in parentheses. For instance,

(define-structure (date year month day))

creates a new type named date. We can create a new date by calling make-date (which we must supply with three arguments), we can test whether something is a date by using the predicate date?, and given a date, we can extract its components by passing it to the functions date-year, date-month, and date-day.

define-structure is not an ordinary function--it is magic, like lambda, if, and a few other special forms. Because define-structure is a special form, the parentheses in (date year month day) do not denote a function call, and the symbols date, year, month, and day are not evaluated. They are just treated as names from which the function names will be generated.

You might intend that the year field of a date contains a non-negative integer less than 1997, but you have no guarantee that that is how the function will be called: (make-date 'barney 'is-a 'dinosaur) is perfectly legal (and its value is a date object), because Scheme does not enforce any properties about the contents of structure (tuple) fields, any more than it enforces any properties about the value refereed to by an ordinary variable.

Lab 4 Lists of Bits

Lab 4
Lists of Bits