Comp 210 Lab 4: Data Definitions continued

Before starting today's lab, you'll need to start Dr. Scheme and from the Language menu, bump your level up to "intermediate". This allows you to use structures (as required for the next homework).

Table of Contents

  • Data Definition for List of Bits
  • Defining Structures
    • We will practice writing recursive programs by manipulating lists of bits. Recall that a list-of-bits is either
  • null, or
  • (cons b lob), where b is a bit, and lob is a list-of-bits.
    • Last week we also covered conversion between lists-of-bits and numbers; here's a synopsis. This week, we will also write some functions that take two lists of bits as arguments. Here's a template (there is some leniency in deciding what natural recursion should be mentioned in the template). 
    ;;    (define fun-for-2lob
;;       (lambda (l1 l2)
;;           (cond
;;              [(and (null? l1) (null? l2))
;;               ...]
;;              [(and (null? l1) (cons? l2))
;;               ...(car l2)...(cdr l2)...]
;;              [(and (cons? l1) (null? l2))
;;               ...(car l1)...(cdr l1)...]
;;              [(and (cons? l1) (cons? l2))
;;               ...(car l1)...(car l2)...(fun-for-2lob (cdr l1) (cdr l2))...
;;              [else
;;                (error "fun-for-2lob: Uh-oh, some case not handled" l1 l2)])))
    Yes, you're right, some of the above cases could be simplified; for instance the second condition could be just (null? l1) since passing the previous line implies l1 and l2 aren't both null so therefore (cons? l2) is clearly true. However, that's a bit of thinking i prefer to leave to the computer when possible. So i'll just blindly put down the four cases, and not worry that any fancy reasoning i do might have a loophole. (99.5% of the time my reasoning will be fine; but that .5% will cause me hours of trouble searching for some obscure bug.)

    As for the else case: I like to include the else condition whenever it isn't too much trouble, on the same theory that it's sometimes not needed, but if i've made some silly mistake then it can save me lots of effort. However, I won't bend over backwards to include an error-catching else; if determining the last "real" case is otherwise difficult (not something easy liking using null? or such, then I'll just use else for data extraction rather than a sanity check.

    Complete the programs

    Last week we wrote the functions lob->num and num->lob. Today we'll write the following functions:
  • lob-mult2 converts a list of bits into a list of bits representing a number twice as great. (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-quotient2 converts a list of bits representing a number n into the list of bits representing the number (quotient n 2).
  • 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.
  • add takes two lists of bits and returns the list of bits representing the sum of the numbers represented by its inputs. Use the equations: 
      (0) + (0) = 0
  (0) + (2a + b) = 2a+b
  (2a + b) + (0) = 2a+b
  (2x+b1) + (2y + b2) we consider for the various cases of b1,b2:
      (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
    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.
  • 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+b1) * (2y + b2) we consider for the various cases of b1,b2:
     (2x + 0) * (2y + 0) = 4xy
     (2x + 1) * (2y + 0) = 4xy+2y
     (2x + 0) * (2y + 1) = 4xy+2x
     (2x + 1) * (2y + 1) = 4xy+2(x+y)+1
    Remember to leverage off of functions you've already written, like mult2, add1, as well as the natural recursion. After writing your solution, you can check out this solution.

    • Supply test data

    Don't forget to test your functions!

    Let's just step back to see what you've done: you've written multiplication and addition from scratch -- we didn't use the built-in + or *. (Except in converting between the numeric format and the list-of-bits format.) 

    (define my-very-own-add
  (lambda (x y)
     (lob->num (lob-add (num->lob x) (num->lob y)))))
    Moreover, what is the biggest number you represent? It's limited only by the length of lists you can represent; you're not limited to a paltry 20 digits or so, like many calculators or the built-in arithmetic of most programming languages. Congratulations, software engineer!

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

    Try 

    (define-structure (date year month day))
(define groundhog (make-date 1997 'feb 2))
(date? groundhog)
(date? 3)
(date-month groundhog)
    That's all simple enough; you may want to try your hand at writing the function next-year, which takes a date, and returns what the date will be in a year:
    (next-year groundhog) = (make-date 1998 'feb 2).

    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. So really, define-structure makes a new data type, and defines several other functions: the corresponding constructor, predicate, and selectors.

    In lectures, we'll use structures to implement "tuples" of data, in data descriptions. Be sure to look at the page for generalized data descriptions, which can be reached from the Readings link of the Comp 210 home page.

    N.B. The book might mention define-struct; this is the same as define-structure except that it puts parentheses in slightly different places. Dr.Scheme understands both of these commands, but Donkey only understands define-structure, which is why we are using that one.

    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. It is up to (you) the programmer to ensure this is true.

    Notice that things made with cons (non-empty lists) are really just aggregate structures. You can pretend to yourself that somewhere inside Scheme there is a line define-structure (cons car cdr)). Then, to save typing, what should have been called make-cons, cons-car, cons-cdr have in this case been given shortened names cons, car, cdr. (The predicate cons? is named as would be expected.)

    Back to Comp 210 Home