Homework 4
Due Date: Friday February 19, 9pm
Purpose To design and use hierarchical data; to design simple recursive functions
Expectations
This will be your first pair assignment. Remember that working in pairs means that you both work on the problems together, ideally by one person developping the solution, while the other person observes and comments. Working in pairs does not mean to split up the work between the two of you.
As with all assignments, you must upload one .rkt file in the language specified at the top of the assignment to the Handin Server. Using the wrong language will invalidate your submission and result in a score of 0, so please be careful.
Unless otherwise stated, all data and functions you design must be designed according to the data and function design recipes, resp., following all four steps in each case.
-----------------------------------------------------------------------------
A hexadecimal ("hex" for short) number is a natural number represented using base 16. That is, instead of 10 digits, we have 16; they are denoted 0,1,...,9,A,B,C,D,E,F. The hex number 3D4, for example, equals the decimal number 3*162+13*161+4*160=980.
In this homework you will write functions to manipulate hex numbers.
Exercise 1 Design data HexLetter to represent the letters used as a digit in the hex system.
Exercise 2 Design data HexDigit to represent any digit in the hex system. Such a digit comes in two flavors. Consider how you represent the non-letter (numeric) digits in a hex number: the number 42 is not a digit.
Remember that, in the template for some data D, when we encounter designed data other than D, we call the template of that data.
Exercise 3 Design data 4-HexNum to represent a 4-digit hex number. Think about the order of the digits, and document your decisions. Give at least 5 examples, one of which must be the largest hex number you can represent using 4 digits, and one of which must be the smallest.
Exercise 4 Design a function render-4-hexnum that renders a 4-HexNum as a four-character string. You can denote the output type as 4-String. Since the result must be a 4-String, you must keep leading zeros in the output. For example, the hex number 0 should be returned as the 4-character string "0000".
The order of the digits must be human-readable, i.e. the hex number 12 must be printed as "0012", not as "2100"!
If you need to render parts of the 4-HexNum, you likely need (to design) a helper function. If so, follow the top-down function design principle: "caller first, callee later".
BSL function number->string may be helpful.
Use all examples defined in the 4-HexNum data definition as tests.
Exercise 5 Now we deal with the leading zero issue: "0012" is not a nice representation of the hex number 12. Design a function p-render-4-hexnum (the "p-" stands for "pretty-") that has the same signature as render-4-hexnum, but returns the number in string form without leading zeros. You can denote the output type simply as String.
Notes:
There may be multiple leading zeros: the hex number representation of the decimal 100 should be returned as "64" (reduced from "0064").
On the other hand, the leading zero must not be dropped if it is the only digit in the number. That is, the hex number 0 should be p-rendered as "0", not as the empty string! This is a highly recommended test case, since it tests the behavior of your function in a borderline situation, which is where typically the errors lurk.
Hint: this function is somewhat adventurous: the 4-HexNum template will not be very useful, since we are not processing the 4 digits of the hex number separately. We are just dropping leading zeros.
Instead, consider writing a helper function that drops a single leading zero from a non-empty string (NE-String) if there is one, otherwise returns the string unchanged. How can you use this helper function to drop the possibly mutiple leading zeros?
There are many good test cases for this function. We have to deduct points if your check-expects do not cover critical test cases for this or any other function you design.
Exercise 6 Design a function hex2dec that converts a 4-HexNum into a decimal number and returns it. The output is thus a natural number in a certain range (since the hex number has only four digits) – this must be reflected in your signature.
Now we of course do the reverse: we want a function that converts a decimal number to a 4-HexNum. This is a bit tricky, so we do it step by step (bottom-up, rather than top-down).
Exercise 7 Design a function dec2hexdigit that takes the decimal value of a hex digit as input (i.e. a number in what range?) and returns a HexDigit. This function is the inverse of hexdigit2dec.
Exercise 8 Design a function dec2hex-numerical that takes a decimal number d and a position i, i.e. i in {0,1,2,3}. The function returns the decimal value of the ith hexadecimal digit of d. You can assume that digit i is the largest digit position in d: d can be represented with no more than i hex digits in total.
Here is some starter code for this problem, including several examples:
; dec2hex-numerical : Nat[0..65535] Nat[0,3] -> Nat[0,15] ; the numeric value of the ith hexadecimal digit of d, ; assuming d < 16^{i+1}, i.e. d requires at most i hex digits (check-expect (dec2hex-numerical 65535 3) 15) (check-expect (dec2hex-numerical 2803 2) 10) (check-expect (dec2hex-numerical 109 1) 6) (check-expect (dec2hex-numerical 13 0) 13) (define (dec2hex-numerical d i) (...))
Exercise 9 Finally, using the results from the previous two exercises, design a function dec2hex that converts a decimal number to a 4-HexNum.
Your function must construct a 4-HexNum, so you better call the constructor. First compute the numerical value of each hex digit, using function dec2hex-numerical. Then convert the result to a true hex digit.
The only thing you need to figure out is what values of d and i to pass to dec2hex-numerical, for each digit you are computing.
Exercise 10 Enough of 4-digit hex numbers! Design data HexNum to hold a hex number of an arbitrary number of digits (even zero digits, which we interpret as 0). The least-order digit (the one with positional value 160 = 1) should appear last, the highest-order digit first, the same way we read numbers (from left to right).
HexDigit is your friend – do not reinvent it.
Exercise 11 Design a function has-A? that decides whether a given HexNum contains the hex digit "A".