The body of this article is a literate Haskell program. You can extract the text, then save it as a file with the extension .lhs, then execute it using GHCi.

This is a Haskell toy to visualize twos-complement binary numbers. In my previous articles on the subject of integer division, I alluded to underflow and overflow and the "weird number" -- well, now you can see them! Almost 30 years ago I wrote code on my Radio Shack TRS-80 to make my dot-matrix printer spit out bitmaps of binary numbers, which made pretty recursive patterns. This program commemorates that long-ago geekery from my early teenage hacking days. First, we need the bits library: >import Data.Bits We'll also need the list library later: >import List Let's simulate n-bit binary number in both a signed and unsigned interpretation. Given a number of bits, we want a function to make a list of the possible values. For example, in unsigned form 8 bits will give us a list of the values 0..255; in signed form, it will be an asymmetrical list from -128..127. Note that this function generates the whole list, so if you give it a numbits value higher than, say, 16, you might regret it. Our calculation fails for values of numbits <= 0, so we put in a guard case for that. We also want to discourage creating very large lists, so we put in a guard case for numbits > 16. >gen_n_bit_nums_unsigned numbits | numbits <= 0 = [] >gen_n_bit_nums_unsigned numbits | numbits > 16 = error "too many bits!" >gen_n_bit_nums_unsigned numbits = > [ n | n <- [(0::Int)..((2::Int)^numbits - 1)] ] >gen_n_bit_nums_signed numbits | numbits <= 0 = [] >gen_n_bit_nums_signed numbits | numbits > 16 = error "too many bits!" >gen_n_bit_nums_signed numbits = > [ n | n <- [-(2::Int)^(numbits - 1)..((2::Int)^(numbits - 1) - 1)] ] To test this we can execute: gen_n_bit_nums_unsigned 4 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] gen_n_bit_nums_signed 4 [-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7] That looks about right. Now we want a function to access the bits of those numbers from most significant to least significant and build a list of corresponding boolean values. This would be expressed more naturally if EnumFromTo operated descending sequences. I'm sure there's a better way, but for now I will just reverse the resulting list: >rightmost_bits num_bits val | num_bits > 16 = error "too many bits" >rightmost_bits num_bits val | num_bits <= 0 = error "too few bits" >rightmost_bits num_bits val = > reverse [ testBit (val::Int) bit_idx | bit_idx <- [0..(num_bits - 1)] ] Once we have a function which will do it with one number, doing it with a whole list of numbers is very easy. We will make a curried function and use map. Currying in Haskell is very easy, which makes sense given that the operation, "to curry" and the language, Haskell, are both named after Haskell Curry! Our rightmost_bits function takes two arguments, but we want to make a new function which we can hand off as an argument to map, along with a list. This new function will only take one parameter. We can ask GHCi what it thinks the type of the rightmost_bits function is: :type rightmost_bits It says: rightmost_bits :: Int -> Int -> [Bool] We can make a new function out of it by doing partial application: instead of supplying all its arguments, we just supply the first one. gen_rightmost_bits 4 If you do this in GHCi, you'll get an error message because the result is not printable (GHCi can't apply show to the result). But you can bind it: let bit_generator_4 = gen_rightmost_bits 4 And then ask GHCi what its type is: :type bit_generator_4 bit_generator_4 :: [Int] -> [[Bool]] Take a moment to make sure you understand what we've done here: Haskell has made us a curried function which takes a list of values instead of a single value, and generates a list of lists. This seems pretty close to magic! Let's make another function that takes the number of bits and a list, generates the curried function, then maps the list to the curried function: >gen_rightmost_bits num_bits ls = > map (rightmost_bits num_bits) ls As you can see, working with curried functions is completely effortless in Haskell. Here's a general function to generate a list of all the bit values for unsigned numbers of num_bits size: >gen_all_bits_unsigned num_bits = > gen_rightmost_bits num_bits (gen_n_bit_nums_unsigned num_bits) >gen_all_bits_signed num_bits = > gen_rightmost_bits num_bits (gen_n_bit_nums_signed num_bits) If we execute: gen_all_bits_unsigned 4 We get back the following (I have reformatted the output for clarity): [[False, False, False, False], [False, False, False, True], [False, False, True, False], [False, False, True, True], [False, True, False, False], [False, True, False, True], [False, True, True, False], [False, True, True, True], [True, False, False, False], [True, False, False, True], [True, False, True, False], [True, False, True, True], [True, True, False, False], [True, True, False, True], [True, True, True, False], [True, True, True, True]] This is recognizably a table of the unsigned binary values 0..15. This approach doesn't seem very "Haskell-ish" yet -- instead of generating the combinations as needed, I'm producing them all ahead of time. It also feels to me like I'm pushing uphill on the syntax, and having to use parentheses to force the order of evaluation. We can think more about that later, but let's get our pretty-printing working first. How can I turn all those boolean values into a string I can print? Well, we can take advantage of the fact that in Haskell, strings can be treated as lists, and the same methods apply. This is not efficient, but it allows us to use some of the standard functional techniques. One of these is "fold." Fold is a technique for boiling down a list into some kind of summary form. Just what form this summary takes is up to you, since you can supply your own function and a starting value. For example, to sum the elements in a list, I could use foldl like this: foldl (\ x y -> x + y) 0 [0, 1, 2] The first parameter to foldl is a function. In this case I'll use a lambda expression, which gives me a function I won't bother to name. The second paramter is the starting value. The starting value and the next item in the list are repeatedly passed to the function, which accumulates a value. In this case, the final result is 3. I can give foldl an empty string as the starting accumulator value and my function can concatenate strings onto it: >stringify_vals = > foldl (\ x y -> if y then x ++ "#" else x ++ " ") "" Now you might want to try to apply our list of lists to this function: stringify_vals (gen_all_bits_unsigned num_bits) If you do that, though, you'll get a type error like this: "Couldn't match expected type `Bool' against inferred type `[Bool]'" The reason can be seen if we examine the types: :type (gen_all_bits_unsigned 4) :: [[Bool]] (gen_all_bits_unsigned 4) :: [[Bool]] :type stringify_vals stringify_vals :: [Bool] -> [Char] We have a list of lists of bools, but we want to feed our stringification function a list of bools. To apply each element of (gen_all_bits_unsigned 4) to our stringification function, we can use map again: >stringify_all_unsigned_vals num_bits = > map stringify_vals (gen_all_bits_unsigned num_bits) >stringify_all_signed_vals num_bits = > map stringify_vals (gen_all_bits_signed num_bits) This will give us a list of strings, one for each list of boolean values. (I've reformatted the output). [" ", " #", " # ", " ##", " # ", " # #", " ## ", " ###", "# ", "# #", "# # ", "# ##", "## ", "## #", "### ", "####"] That's nice: we can start to see our recursive structure! But we really want that value to be turned into a single printable string. To achieve that, we can use the unlines function. >prettyprint_unsigned num_bits = > unlines (stringify_all_unsigned_vals num_bits) >prettyprint_signed num_bits = > unlines (stringify_all_signed_vals num_bits) When we interpret prettyprint_unsigned 3 we see a single string with newline characters escaped, like so: " \n #\n # \n ##\n# \n# #\n## \n###\n" This will give the results we want when we pass it to putStr, like so: putStr (prettyprint_unsigned 8) # # ## # # # ## ### # # # # # # ## ## ## # ### #### (etc.) Hmmm. That's nice, but it would be really cool if the results were rotated, so that we could see what it would look like if a printhead moving horizontally was printing out these values. To do this, we can actually start with our intermediate list of lists. If our four-bit numbers give us [[False, False, False, False], [False, False, False, True], [False, False, True, False], etc. we can see the values the other way using transpose. Let's write rotated versions of gen_all_bits_unsigned and gen_all_bits_signed: >gen_all_bits_unsigned_rot num_bits = > transpose > (gen_rightmost_bits num_bits (gen_n_bit_nums_unsigned num_bits)) >gen_all_bits_signed_rot num_bits = > transpose > (gen_rightmost_bits num_bits (gen_n_bit_nums_signed num_bits)) And make a new stringify function to play with: >stringify_all_unsigned_vals_rot num_bits = > map stringify_vals (gen_all_bits_unsigned_rot num_bits) >prettyprint_unsigned_rot num_bits = > unlines (stringify_all_unsigned_vals_rot num_bits) Now putStr (prettyprint_unsigned_rot 6) will give us: ################################ ################ ################ ######## ######## ######## ######## #### #### #### #### #### #### #### #### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # Now that's what I'm talking about! We can use the unsigned version to see the interesting transition point between negative and positive values: >stringify_all_signed_vals_rot num_bits = > map stringify_vals (gen_all_bits_signed_rot num_bits) >prettyprint_signed_rot num_bits = > unlines (stringify_all_signed_vals_rot num_bits) Now putStr (prettyprint_signed_rot 6) will give us: ################################ ################ ################ ######## ######## ######## ######## #### #### #### #### #### #### #### #### ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # Now let's give our program a main function using the IO monad and have it print out several of our results: >main :: IO () >main = do > print "Unsigned values (8 bits)" > putStr (prettyprint_unsigned 8) > print "Signed values (8 bits)" > putStr (prettyprint_signed 8) > print "Unsigned values (6 bits) rotated" > putStr (prettyprint_unsigned_rot 6) > print "Signed values (6 bits) rotated" > putStr (prettyprint_signed_rot 6) After using GHCi's :cd and :load command to read this file, just type: main

I would invite any readers to play around with the code, and if you can make it more concise and/or more "Haskellish," please leave a comment.

Now if only we could get Haskell to generate the appropriate sound! My dot-matrix printer was loud. But that's a task for another day.

Update: there is a followup aticle to this one which develops the code further; see http://praisecurseandrecurse.blogspot.com/2006/12/revised-dot-matrix-printhead.html Also, make sure to take a look at the comments on both this posting and the followup.
## 6 comments:

I was going to post my attempt here, but since blogger helpfully disallows the pre tag in comments, I decided to post it to my blog instead.

well, choosing short function names is "Haskellish", why? you know by now I guess...

also, "Haskellers" would prefer

foldl (+) ...

over

foldl (\x y -> x + y) ...

why? idunno 8-)

umm... also... why write [n | n <- [a .. b]] when you can write [a .. b]?

8-)

and guards are helpful...

Haskell syntax is like a box full of chocolates... *-)

These are great suggestions, thanks!

As to the question of fold, I guess I was writing a lambda to illustrate the parallels of addition to my string accumulation, but certainly if I really wanted "+" I should just use the existing function.

Short function names -- check. I have gotten used to writing quite long method names in C++ (for classes with a lot of methods). It has probably instilled habits that are not helpful in Haskell!

Jason, I appreciate your rewrite... it is definitely improved.

I will prepare a followup presenting an improved version.

"Now we want a function to access the bits of those numbers from most

significant to least significant and build a list of corresponding

boolean values. This would be expressed more naturally if EnumFromTo

operated descending sequences."

Doesn't Haskell support this? Lemme try:

$ ghci

Prelude> [5..1]

[]

Hmm. Oh yeah, you need to give it a hint:

Prelude> [5,4..1]

[5,4,3,2,1]

Yay!

Also, folding a [Bool] into a successively concatenated String doesn't seem ideal. Since String is equivalent to [Char], you could map each Bool directly to its equivalent Char:

$ ghci

Prelude> let stringify_vals = map (\x -> if x then '#' else ' ')

Prelude> stringify_vals [False, False, True, False]

" # "

If, however, your purpose was to demonstrate fold, then the version given is OK.

Also also, I'm pretty sure most of the _rot functions aren't strictly necessary. You should be able to transpose the [String] right before unlines-ing it. So you would only need the two prettyprint_blah_rot functions.

Also also also, I tried saving the body text as a .lhs, but GHCi choked on lines that started with '#'.

Also x 4 (*sigh*), short names are a matter of taste. I wouldn't dare discourage using more descriptive names!

Anyway, happy Haskelling!

Post a Comment