4
\$\begingroup\$

I've set myself the task to write a function that parses Verilog-style number literals. In Verilog, numbers are written like this: 8'b10101100, 16'hffff, '789, 32'd0, 12'o7, etc.

The syntax is:

<size>'<radix>value

where <...> denotes an optional field, and

  • size is the binary representation length of the number (in bits). The default is 32.
  • radix is 'b' or 'B' for binary, 'o' or 'O' for octal, 'd' or 'D' for decimal, 'h' or 'H' for hexadecimal. The default is 'd'.
  • value is the appropriate number representation for the given radix.

I'm new to Haskell, so I really would appreciate a critical appraisal of the following implementation. I think it is correct. Is it also 'good' Haskell/Parsec? Can it be done better, i.e. more concisely, more clearly, using more appropriate idioms?

import System.IO
import System.Environment
import Data.Either (either)
import Data.Either.Extra (fromRight)
import Data.Char (digitToInt, toLower)
import Numeric (readInt, readOct, readHex)
import Text.Parsec.Combinator
import Text.ParserCombinators.Parsec
import Text.Parsec.Char (hexDigit, octDigit)

integerLog :: Integer -> Integer
integerLog = floor . logBase 2.0 . fromIntegral

-- |numberSize calculates the length (in bits) of the binary representation of Integer
numberSize :: Integer -> Integer
numberSize = (1+) . integerLog

-- |The type Number has a val (Integer value) and a len (binary representation length).
data Number = Number {val::Integer, len:: Integer} deriving Show

-- |makeNumber is a safe constructor of an Either String Number
makeNumber :: Integer -> Integer -> (Either String Number)
makeNumber v l
  | v < 0     = Left "makeNumber: Negative values not allowed in Number"
  | size > l  = Left $ "makeNumber: Value " ++ show v ++ " is " 
    ++ show size ++ " bits long, should be at most " ++ show l ++ " bits"
  | size <= 0 = Left $ "makeNumber: Size can't be negative or zero"
  | otherwise = Right $ Number v l
  where size = numberSize v

-- |readBin is not defined in Numeric (readInt, etc., are)
readBin = readInt 2 (`elem` "01") digitToInt

-- conversions String -> Number
hexToInteger x = fst $ readHex x !! 0 :: Integer
octToInteger x = fst $ readOct x !! 0 :: Integer
binToInteger x = fst $ readBin x !! 0 :: Integer

-- |binDigit is not in Text.Parsec.Char (hexDigit, octDigit are)
binDigit :: CharParser st Char
binDigit = oneOf "01"

-- |parse Verilog-style numbers <size>'<radix>value
parseNumber :: Parser Number
parseNumber = do
  size <- option "32" (many1 digit)
  char '\''
  radix <- option 'd' $ oneOf "hH" <|> oneOf "dD" <|> oneOf "oO" <|> oneOf "bB"
  let (thisDigit, convert_digits) =
        case toLower radix of
          'h' -> (hexDigit, hexToInteger)
          'o' -> (octDigit, octToInteger)
          'd' -> (digit   , read)
          'b' -> (binDigit, binToInteger)
          _  ->  error "parseNumber: Internal error"
  val <- many1 thisDigit
  let size' = read size :: Integer
      val' = convert_digits val :: Integer
      num = makeNumber val' size'
    in
    either fail return num


main :: IO ()
main = do
  args <- getArgs
  let results = map (parse parseNumber "parseNumber") args
  mapM_ print results

Note: In true Verilog numbers have the format <size>'<signed><radix>value but in my application negative numbers are not allowed, hence the omission of <signed>.

\$\endgroup\$
  • \$\begingroup\$ Unfortunately, I don't have time for a review, but here is some food for thought: Int (or even better Word) is more than enough for the number of bits, logBase 2.0 might give the wrong result (starting at 1024 bits, see zipWith (==) [0..] $ take 1500 $ map (floor . logBase 2) $ iterate (*2) 1), and some functions are partial or violate DRY. \$\endgroup\$ – Zeta Jul 22 '16 at 12:06
  • \$\begingroup\$ (Keep in mind that you should not change the code, though, even based on this comment, since someone might already write a complete answer; see codereview.stackexchange.com/help/someone-answers). \$\endgroup\$ – Zeta Jul 22 '16 at 12:14
  • \$\begingroup\$ Good point, thanks for the input. The alternative could be to make numberSize safe by not using floats at all: numberSize = length $ takeWhile (>0) $ iterate (`div` 2) \$\endgroup\$ – mcmayer Jul 22 '16 at 12:44
2
\$\begingroup\$

Let's start with your imports. You should get rid of those you don't need, e.g. System.IO, import Data.Either.Extra (fromRight). Next, you shouldn't mix integral and floating point calculations, unless you're fine with imprecise results. For example, integerLog will give the wrong answer around 1024:

ghci> integerLog (2^1023)
1023
ghci> integerLog (2^1024)
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

Next, record field names are functions:

data Number = Number {val::Integer, len:: BitSize} deriving Show

This gives you two functions,

val :: Number -> Integer
len :: Number -> Integer

Unless you're fine with those functions at global namespace, it's usually a better idea to either a) use a complete name, e.g. value, bitLength, or b) prefix/suffix them with the type's name, e.g. numberValue or lenNumber. The story slightly changes if you want to use lenses and Template Haskell, but that's for another post.

What follows afterwards are several top-level functions without type signature, which is considered bad style:

readBin = readInt 2 (`elem` "01") digitToInt

-- conversions String -> Number
hexToInteger x = fst $ readHex x !! 0 :: Integer
octToInteger x = fst $ readOct x !! 0 :: Integer
binToInteger x = fst $ readBin x !! 0 :: Integer

All those functions are partial, e.g.

ghci> hexToInteger "Hello"
*** Exception: Prelude.!!: index too large

Your use prevents this kind of error, since you're using ithexToInteger only on valid combinations, but you shouldn't export them either. That's not really an issue here since you've wrote a Main (main) module, but you should keep that in mind.

However, those functions would be a lot nicer with the appropriate type:

convertWith :: ReadS Integer -> String -> Maybe Integer
convertWith fn xs = case fn xs of
                      [(n,"")] -> Just n
                      _        -> Nothing

hexToInteger, octToInteger, binToInteger :: String -> Maybe Integer
hexToInteger = convertWith readHex
octToInteger = convertWith readOct
binToInteger = convertWith (readInt 2 (`elem` "01") digitToInt)

In this case we've dumped the plumbing into convertWith, added type signatures and made the functions non-partial. Now, let's step back to your smart-constructor:

-- |makeNumber is a safe constructor of an Either String Number
makeNumber :: Integer -> Integer -> (Either String Number)
makeNumber v l
  | v < 0     = Left "makeNumber: Negative values not allowed in Number"
  | size > l  = Left $ "makeNumber: Value " ++ show v ++ " is " 
    ++ show size ++ " bits long, should be at most " ++ show l ++ " bits"
  | size <= 0 = Left $ "makeNumber: Size can't be negative or zero"
  | otherwise = Right $ Number v l
  where size = numberSize v

While that's better than just a Maybe Number, it's still not optimal if you have an application that's creating those numbers. Since sum types aren't expensive to write, let's use one:

data NumberError = ENegative
                 | ENegativeSize
                 | EBitOverflow Integer Integer
 deriving (Show, Eq)

That way you can separate the formatting from the number handling:

makeNumber :: Integer -> BitSize -> (Either NumberError Number)
makeNumber v l
  | v < 0     = Left $ ENegative
  | size > l  = Left $ EBitOverflow v l
  | size <= 0 = Left $ ENegativeSize
  | otherwise = Right $ Number v l
  where size = numberSize v

You could also provide some functions, e.g.

eNegative    :: Either NumberError a
eBitOverflow :: Integer -> BitSize -> Either NumberError a

to ease the use of those, but that's an overkill here.

Speaking of overkills, did you notice the BitSize above? Many of your functions use Integer -> Integer -> …. But what do those Integer's mean? Which one is the value? Which one is the bitsize? And is Integer as bitsize really a good idea?

Therefore, try to add some documentation at the type level, even if it isn't a new type:

type BitSize = Int

Now, let's have a look at the parser:

-- |parse Verilog-style numbers <size>'<radix>value
parseNumber :: Parser Number
parseNumber = do
  size <- option "32" (many1 digit)
  char '\''
  radix <- option 'd' $ oneOf "hH" <|> oneOf "dD" <|> oneOf "oO" <|> oneOf "bB"
  let (thisDigit, convert_digits) =
        case toLower radix of
          'h' -> (hexDigit, hexToInteger)
          'o' -> (octDigit, octToInteger)
          'd' -> (digit   , read)
          'b' -> (binDigit, binToInteger)
          _  ->  error "parseNumber: Internal error"
  val <- many1 thisDigit
  let size' = read size :: Integer
      val' = convert_digits val :: Integer
      num = makeNumber val' size'
    in
    either fail return num

This is well done, except for two minor quirks: you can collect all oneOf <prefix> parsers into a single one:

oneOf "hHdDoObB"

and your use of error, which makes this parser partial again. Instead, you could have used

  (thisDigit, convert_digits) <-
        case toLower radix of
          'h' -> return (hexDigit, hexToInteger)
          'o' -> return (octDigit, octToInteger)
          'd' -> return (digit   , read)
          'b' -> return (binDigit, binToInteger)
          _  ->  fail "parseNumber: Internal error"

Note that parseNumber slightly changes if you use String -> Maybe Integer from above (you should use readMaybe instead of read in this case). Also note that parseNumber isn't a good name in this case, it indicates that you're parsing, but you only define a parser. numberParser is usually slightly better.

Also, make sure that your variables follow the same naming convention. convert_digits kind of falls of the rest of your names.

Last but not least, it's strange that you get your numbers as arguments, e.g.

$ ./MyApplication 32\'b100101001

Usually, you take those values from stdin and print them to stdout. The interact function will come in handy.

Bonus content: Separated concerns and an applicative Parser

So, now that we had a look at your code, how would I write it? I would probably introduce a function that takes the bitsize, the prefix, and the rest:

type BitSize      = Word
data NumberFormat = Bin | Oct | Dec | Hex

makeNumber :: BitSize -> NumberFormat -> String -> Either NumberError Number
makeNumber l d xs = do
  num <- readWith d xs
  case num of
   _ | num  < 0 -> eNegative
   _ | bits > l -> eBitOverflow num l
   _            -> return $ Number num l
  where num  = readWith d xs
        bits = fromIntegral $ numberSize num

readWith :: NumberFormat -> String -> Either NumberError Number
readWith d xs = maybeToEither $ case d of
                   Bin -> binToInteger xs
                   Oct -> octToInteger xs
                   Dec -> readMaybe    xs
                   Hex -> hexToInteger xs

Essentially that's still your code, only put into two functions and using the NumberError above. This makes it possible to later test the parts of your previously large parseNumber. Note that all those functions are rather small, and do only one thing (and one thing well).

Now what's left is the Parser. Instead of the previous Monad one, we can now easily use an Applicative one. For this, we provide three additional parsers that parse the sub-expressions <bits>'<format><digits>:

bitSizeParser :: Parser BitSize
bitSizeParser = option 32 $ fmap read $ many1 digits
-- read is fine here, since we use only digits

numberFormatParser :: Parser NumberFormat
numberFormatParser = option Dec $ fmap toFormat $ oneOf "hHoOdDbB"
  where toFormat c = case toLower c of
          'h' -> Hex
          'b' -> Bin
          'd' -> Dec
          'o' -> Oct

digitsParser :: Parser String
digitsParser = many1 $ oneOf "0123456789abcdef"

Now what's left is using those three parsers together and feeding them into makeNumber:

 import Control.Applicative ((<$>), (<*>)) -- not needed in GHC 7.10 or higher

numberParser' :: Parser (Either NumberError Number)
numberParser' = 
  makeNumber <$> bitSizeParser <*> numberFormatParser <*> digitsParser

numberParser :: Parser Number
numberParser = numberParser' >>= either fail return

Note that the parts of our parser are now reasonably dumb. They only get things, i.e. <bits>'<format><digits>. The logic is now in makeNumber, which can be used without actually parsing, which might be handy if you want to check values from a database or similar.

\$\endgroup\$
  • \$\begingroup\$ Are the two ls in makeNumber supposed to collide? You didn't tell maybeToEither what NumberError to use. You could replace NumberFormat by (String -> Maybe Number) and everything would get shorter. (For that database testing thing to keep working, you could make toFormat :: Char -> (String -> Maybe Number) top-level.) \$\endgroup\$ – Gurkenglas Jul 26 '16 at 11:33
  • \$\begingroup\$ @Gurkenglas: No, that was a copy-error. Fixed it locally, but not in the online draft at that time. A small problem I see with String -> Maybe Number directly is that you're not able to print functions. Also, it's trivial to get NumberFormat -> (String -> Maybe Number), but (String -> Maybe Number) -> NumberFormat is tricky (although possible, if we restrict the possible functions to the four above). But yeah, some of the code could get further improved. The bonus content is meant as a motivation, not a complete implementation. \$\endgroup\$ – Zeta Jul 26 '16 at 12:40
  • \$\begingroup\$ @Zeta First of a all: This is a fantastic, in-depth review. Thank you! I'm with you all the way to the definition of your makeNumber in the bonus content. There, both the compiler and I fail on this _ | num < 0 -> ENegative construct. It's something to do with pattern guards for case alternatives...? I've been reading about pattern guards, but I don't quite understand what this _ | ... does. (By the way, a minor detail: eNegative should be ENegative, etc.) \$\endgroup\$ – mcmayer Jul 27 '16 at 3:55
  • \$\begingroup\$ @mcmayer: "You could also provide some functions, e.g. eNegative :: ...". Those are handy if you want to change your errors later to ErrorT or back to Maybe. I'll have a look at the case later again, don't have a compiler atm \$\endgroup\$ – Zeta Jul 27 '16 at 5:59
  • \$\begingroup\$ @mcmayer: Hm, just tried it. It should work. case <expr> of [clause] will try to bind` to the first pattern, where the (optional) guard is also True. Since the pattern is _, I'm only using guards here to check the number. A MultiWayIf would be slightly more clean, but I didn't want to introduce language extensions. \$\endgroup\$ – Zeta Jul 27 '16 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.