Modelling Digital Logic in Haskell

scm 老師這次出的 Haskell 練習題是用 Haskell 寫 digital logic components。這正是 OUCL 大學部教 digital logic 的方式，真是太浪漫了 XD。一條接線是以一個 list 表示，其中每個元素是那條線在各個離散時間點的訊號值。

type Wire = [Bool]

也就是說，Wire 這個 list 的 index 是時間（單位是 infinitesimal 吧，我們暫時不考慮 physical delays XD）。另一種正交觀點是在同一個時間點看多條線（一般就是一個 bus）的 states，我稱之為 time slice（從 OS 借來的詞）。

type TimeSlice = [Bool]

此時 list 的 index 是線的編號。後面會發現區分這兩個型別是有意義的。

我們先從簡單的開始。以下的函式 binary c 把一個整數轉為 binary representation：

binary :: Int -> Integer -> TimeSlice
binary c = take c . map ((/= 0) . (`mod` 2)) . iterate (`div` 2)

這產生出線數為 c 的 time slice。binary c 有反函式 numeric c：

numeric :: Int -> TimeSlice -> Integer
numeric c = sum . tri (*2) . map bit2num . take c

tri f（就是出現在 Horner's rule 裡面的那個函式）和 bit2num 的定義是：

tri f = foldr (\x xs -> x : map f xs) []
bit2num False = 0 
bit2num True  = 1

我們也可以產生承載常數的 bus：

constant :: Int -> Integer -> [Wire]
constant c = map repeat . binary c

其中 repeat a = a : repeat a 是 Haskell 內建的函式（吧）。

接著我們試試加法器的核心功能。以下函式 add c 把兩個 time slices 視為二進位數字加在一起，產生一個新的 time slice：

add :: Int -> TimeSlice -> TimeSlice -> TimeSlice
add c = curry (binary (c + 1) . uncurry (+) . parallel (numeric c))

add c 把它收到的兩個 time slices 轉為數值加起來，然後轉換回長度 c + 1 的 time slice，多一位是最高位的進位。這其實是加法電路的 specification，以後我希望能從這裡導出 ripple adder, carry look-ahead adder 等等的。(Hope it's possible. XD)

加法器的型別是

adder :: Int -> [Wire] -> [Wire] -> [Wire]

[Wire] 是一條一條的線，但 add c 處理的是一個一個的 time slice，我們必須寫個函式在這兩個觀點間轉換。稍微想一想就會發覺，這其實就是 matrix transposition，所以我們可以寫

transpose = foldr (zipWith (:)) (repeat [])

然後我們就可以寫出加法器：

adder c = curry (transpose . uncurry (zipWith (add c)) . parallel transpose)

其中 parallel 是 "square" functor。

split f g a = (f a, g a)
cross f g = split (f . fst) (g . snd)
parallel f = cross f f

寫完了很高興，我們測試一下，在 GHCi 下輸入

map head (adder 5 (constant 5 7) (constant 5 8))

卻發現 adder is unproductive！（意思是什麼東西都吐不出來。）追蹤一下就會發現，add 產生出來的是個 infinite list of time slices，而 transpose 是個 foldr，找不到 base case 可以停下來。因此我們被迫寫另一個 transpose，功能一樣但用 unfoldr 實作：

wirewise :: [TimeSlice] -> [Wire]
wirewise = unfoldr f
           where f ([] : xss) = Nothing
                 f xss        = (Just . split (map head) (map tail)) xss

其中 unfoldr f 是標準的定義：

unfoldr f a = case f a of
                Nothing -> []
                Just (x, b) -> x : unfoldr f b

本來的 transpose 也改名一下：

timewise :: [Wire] -> [TimeSlice]
timewise = foldr (zipWith (:)) (repeat [])

adder 於是就變成

adder :: Int -> [Wire] -> [Wire] -> [Wire]
adder c = curry (wirewise . uncurry (zipWith (add c)) . parallel timewise)

這樣我們就有一個把兩條二進位數字流加起來的加法器，而且是 productive。例如剛剛在 GHCi 下輸入的算式現在就能正確輸出結果了：

*Main> map head (adder 5 (constant 5 7) (constant 5 8))
[True,True,True,True,False,False]

我刻意把各個部份寫得很 compositional，希望可以多做到一點 derivations ─ 雖然我覺得規模有點恐怖了，而且還有 infinite lists 和 unfold XD。

--
還有得玩，不過要過一陣子 XD。