5
\$\begingroup\$

I've written a data type to represent a word in the memory of a MIX computer. A MIX word has a sign bit and five six-bit bytes. So I created a data type and provided instances for all the common numeric typeclasses (that I could think of).

Some questions that came to mind:

  • A lot of my instantiations use dependencies in the opposite order of the typeclass inheritance. For example, the instance for Enum uses toInteger (which is defined in class (Real a, Enum a) => Integral a). I was worried about operations looping due to circular dependencies among the default implementations, but that didn't seem to happen. Is this practice safe? Is it good?
  • I tried to isolate the actual bit-manipulation to toInteger and fromInteger. Is this good? Is there a better way I could do this?
  • What about the logic for the weird signed-zero behavior (e.g., -1 + 1 = -0 but 1 - 1 = +0)? Do my signedOp function and its use seem appropriate?
  • I didn't export the data constructor because I didn't want users to be able to write things like MixWord True (0, 0, 0, 0, 65). Is it reasonable to force the use of fromIntegral and friends?
  • Finally, the Ord implementation: I'd prefer this to have fewer than five clauses! Usually, I'd try to implement this with <>-chained comparings, but I didn't immediately see a way to do this. Thoughts?

I've also included a very incomplete spec file.

Mix.hs

module Mix (MixWord, signBit) where

import Data.Word (Word8)
import Data.Ratio ((%))
import Data.List (intercalate)
import Data.Ix (Ix, range, index, inRange)

type Byte = Word8  -- really, we want Word6, but it doesn't exist

-- | A word in a MIX computer,
-- which contains a sign bit and four bytes,
-- where the first byte listed is the MSB.
data MixWord = MixWord Bool (Byte, Byte, Byte, Byte, Byte)

-- | The range of values that can be stored in a single byte
-- (i.e., one greater than the maximum value in a single byte).
byteSize :: Integral a => a
byteSize = 64

-- | Extract the raw sign bit from a MIX word,
-- returning True for semipositive numbers
-- and False for seminegative numbers.
signBit :: MixWord -> Bool
signBit (MixWord sign _) = sign

instance Show MixWord where
    -- e.g., show (68 :: MixWord) = "+ 00 00 00 01 04"
    show (MixWord sign (b1, b2, b3, b4, b5)) =
        intercalate " " (signString : map format [b1, b2, b3, b4, b5])
      where
        signString | sign       = "+"
                   | otherwise  = "-"
        format x =
            let shown = show x
            in  if length shown < 2
                    then '0' : shown
                    else shown

instance Eq MixWord where
    MixWord _ (0, 0, 0, 0, 0) == MixWord _ (0, 0, 0, 0, 0) = True
    MixWord sign1 bytes1 == MixWord sign2 bytes2 =
        (sign1, bytes1) == (sign2, bytes2)

instance Ord MixWord where
    compare (MixWord _ (0, 0, 0, 0, 0)) (MixWord _ (0, 0, 0, 0, 0)) = EQ
    compare (MixWord False _) (MixWord True _) = LT
    compare (MixWord True _) (MixWord False _) = GT
    compare (MixWord True bs1) (MixWord True bs2) = compare bs1 bs2
    compare (MixWord False bs1) (MixWord False bs2) = compare bs2 bs1

instance Real MixWord where
    toRational mw = toInteger mw % 1

instance Bounded MixWord where
    maxBound = MixWord True (byteSize, byteSize, byteSize, byteSize, byteSize)
    minBound = MixWord False (byteSize, byteSize, byteSize, byteSize, byteSize)

instance Enum MixWord where
    succ m
      | m == maxBound   = error
          "Enum.succ{MixWord}: tried to take `succ' of maxBound"
      | otherwise = m + 1
    pred m
      | m == minBound   = error
          "Enum.pred{MixWord}: tried to take `pred' of minBound"
      | otherwise = m - 1
    toEnum = fromInteger . toInteger
    fromEnum = fromInteger . toInteger

instance Integral MixWord where
    toInteger (MixWord sign (b1, b2, b3, b4, b5)) =
        signum *
            (fromIntegral b5 + byteSize *
            (fromIntegral b4 + byteSize *
            (fromIntegral b3 + byteSize *
            (fromIntegral b2 + byteSize * fromIntegral b1))))
      where
        signum | sign       = 1
               | otherwise  = -1
    quotRem m1 m2 =
        let (q, r) = quotRem (toInteger m1) (toInteger m2)
        in  (fromIntegral q, fromIntegral r)

instance Num MixWord where
    m1 + m2 = signedOp (+ (toInteger m2)) m1
    m1 * m2 = signedOp (* (toInteger m2)) m1
    abs = fromInteger . abs . toInteger
    signum = fromInteger . signum . toInteger
    negate (MixWord sign bytes) = MixWord (not sign) bytes
    fromInteger n =
        let magnitude       = abs n
            (rest5, byte5)  = quotRem magnitude byteSize
            (rest4, byte4)  = quotRem rest5 byteSize
            (rest3, byte3)  = quotRem rest4 byteSize
            (rest2, byte2)  = quotRem rest3 byteSize
            (_    , byte1)  = quotRem rest2 byteSize
        in  MixWord (n >= 0) ( fromInteger byte1
                             , fromInteger byte2
                             , fromInteger byte3
                             , fromInteger byte4
                             , fromInteger byte5
                             )

-- | Create a MixNum version of an Integer binary operator,
-- but when the output is zero
-- use the sign of the first operand
-- for the sign of the resulting zero.
signedOp :: (Integer -> Integer) -> MixWord -> MixWord
signedOp op m@(MixWord s0 _) = case op (toInteger m) of
    0       -> MixWord s0 (0, 0, 0, 0, 0)
    other   -> fromInteger other

instance Ix MixWord where
    range (a, b) = [a..b]
    index (a, _) x = (fromInteger . toInteger) (x - a)
    inRange (a, b) x = a <= x && x <= b

MixSpec.hs

module MixSpec (main, spec) where

import Test.Hspec
import Mix (MixWord, signBit)

spec :: Spec
spec = describe "MixWord" $ do
    describe "toInteger and fromInteger" $ do
        it "converts 0"     $ 0 `shouldBe` tofrom 0
        it "converts 7"     $ 7 `shouldBe` tofrom 7
        it "converts (-3)"  $ (-3) `shouldBe` tofrom (-3)
    describe "show" $ do
        it "shows zero as semipositive" $
            show (0 :: MixWord) `shouldBe` "+ 00 00 00 00 00"
        it "shows negated zero as seminegative" $
            show (negate 0 :: MixWord) `shouldBe` "- 00 00 00 00 00"
    describe "ordering" $ do
        it "lets 0 == -0" $
            compare (0 :: MixWord) (negate 0 :: MixWord) `shouldBe` EQ
        it "lets -0 == 0" $
            compare (negate 0 :: MixWord) (0 :: MixWord) `shouldBe` EQ
        it "lets -1 < -0" $
            compare (negate 1 :: MixWord) (negate 0 :: MixWord) `shouldBe` LT
        it "lets -1 < 0" $
            compare (negate 1 :: MixWord) (0 :: MixWord) `shouldBe` LT
        it "lets -3 < -2" $
            compare (negate 3 :: MixWord) (negate 2 :: MixWord) `shouldBe` LT
        it "lets 3 > 2" $
            compare (negate 3 :: MixWord) (negate 2 :: MixWord) `shouldBe` GT
    context "sign shenanigans" $ do
        it "lets  1 - 1  = +0" $ signBit (1 - 1)  `shouldBe` True
        it "lets -1 + 1  = -0" $ signBit (-1 + 1) `shouldBe` False
        it "lets pred 1  = +0" $ signBit (pred 1) `shouldBe` True
        it "lets succ -1 = -0" $ signBit (succ (-1)) `shouldBe` False
  where
    tofrom = toInteger . (fromInteger :: Integer -> MixWord)

main :: IO ()
main = hspec spec
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

A lot of my instantiations use dependencies in the opposite order of the typeclass inheritance. For example, the instance for Enum uses toInteger (which is defined in class (Real a, Enum a) => Integral a). I was worried about operations looping due to circular dependencies among the default implementations, but that didn't seem to happen. Is this practice safe? Is it good?

This is pretty normal. For example when defining a Monad instance, it's customary to define its Applicative instance as (<*>) = ap and pure = return. The type class hierarchy doesn't matter at all, you just need to make sure you won't get infinite loops, which can happen with or without type classes anyway.

I tried to isolate the actual bit-manipulation to toInteger and fromInteger. Is this good? Is there a better way I could do this?

It might be interesting to add a Bits instance, although I'm not sure how well this would play with the sign bit. Other than that it makes a lot of sense to contain the actual bit manipulation, to from/toInteger or elsewhere as much as possible.

What about the logic for the weird signed-zero behavior (e.g., -1 + 1 = -0 but 1 - 1 = +0)? Do my signedOp function and its use seem appropriate?

I'm not sure about this. It's indeed weird and breaks the usual expectations that Num is a ring, although it's probably not a big deal. I'd certainly note this in the docs for the instance.

I didn't export the data constructor because I didn't want users to be able to write things like MixWord True (0, 0, 0, 0, 65). Is it reasonable to force the use of fromIntegral and friends?

Definitely a good idea. You might later decide to internally represent the data type differently, for example in Word32, and this way you can do it without breaking the interface.

But depending on the expected usage, you might include such conversion functions.

Finally, the Ord implementation: I'd prefer this to have fewer than five clauses! Usually, I'd try to implement this with <>-chained comparings, but I didn't immediately see a way to do this. Thoughts?

I didn't know the <> trick, nice. Given the semantics, the 5-clauses don't seem to be really problematic. You need to branch on these conditions one way or another. Some ideas, neither seems to be perfect:

compare (MixWord _ (0, 0, 0, 0, 0)) (MixWord _ (0, 0, 0, 0, 0)) = EQ
compare (MixWord False bs1) (MixWord s2 bs2) = compare False s2 <> compare bs1 bs2
compare (MixWord True bs1) (MixWord s2 bs2) = compare True s2 <> compare bs2 bs1

or

compare (MixWord s1 bs1) (MixWord s2 bs2) =
    compare s1 s2 <> uncurry compare (if s1 then (bs2, bs1) else (bs1, bs2))

Great that you included the tests. I'd suggest to add property-based tests too, it seems highly appropriate for this.

One thing that could simplify the implementation would be to use heterogeneous tuples, like the ones provided by tup-functor, for example

data MixWord = MixWord Bool (Tup5 Byte)

Probably it'd be possible to implement a lot of the operations as folds/zips on tuples, although if you care about performance, you'd have to check if it won't degrade too much.

A small remark, for implementing the Show instance it's often better to implement showsPrec. It doesn't matter much for such data type that converts only to short strings, but it's a good practice.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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