Comp 210 Lab 3: Lists of Bits

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

Data definition

A bit is either
  • 0, or
  • 1.
    • A list-of-bits is either
  • null, or
  • (cons b lob), where b is a bit, and lob is a 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 might recognize a list of bits as the binary representation for the number (in reverse order), or you can just mechanically apply the rules regarding the relationship between numbers and lists of bits. Each strategy works for different 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, then lst represents (car lst) + 2 * [whatever-is-represented-by-(cdr-lst)]
    • (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.) To go in the other direction, from a natural number to the list-of-bits representing it,
  • 0 is represented by null
  • 2a+b is represented by (cons b [whatever-represents-a])
    • For examples,
    list-of-bits corresponding number
    (list 1) 1
    (list 1 1) 3
    (list 0 1 1) 6
    (list 1 0 1 1) 13
    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 happen to use binary arithmetic internally, though this is incidental to our purpose.

    Program Template

    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)) ...))))

    Complete the program

    We will try to write the following functions:
  • lob->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 template, 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, since 9+1=10,
    (lob-add1 (list 1 0 0 1))    =    (list 0 1 0 1)
    Write this function by using the template, according to the following rules: 
          (0) + 1 = 1
      (2a + 0) + 1 = 2a + 1
      (2a + 1) + 1 = 2(a+1) + 0
    Remember to follow the template, examining each of the cases, and you'll be led to correct code. (Don't try to outsmart yourself by combining cases; longer-and-simple is better than shorter-and-inscrutable.) After writing your solution, you can check out this solution.
    • We'll continue in next week's lab, writing functions such as add, which take two list-of-bits and return a list-of-bits representing the sum. Again, the code will follow from the template. (Next week's lectures will include writing templates for functions taking two complex arguments.)
    Back to Lab 3
    Back to Comp 210 Home