2008/03/20

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。

Labels:

Anonymous Anonymous3/21/2008 3:41 am 說:

其實我是希望把它弄得比較像電路一點:都用 and, or, xor 等等 gate 組出來。這樣才可以直接變成電路。

 
Blogger Josh Ko3/21/2008 4:27 am 說:

嗯,這是我的最終目標。現在 add 的實作還只是 specification,我希望從那邊導出電路實作。推導的過程中,我終究得證明 numeric (c + 1) (add c xs ys) = numeric c xs + numeric c ys 之類的東西,這其實就是 add 現在的 specification。或許 add 導出來之後還可以跟外面的兩個 transpose functions 融合起來(形狀剛剛好,unfold 在左邊,fold 在右邊),就會長得比較像 gates 了。

--
希望啦 XD。

 
Anonymous Anonymous3/21/2008 5:05 am 說:

我覺得滿有趣的, 真難得XD

 
Blogger Josh Ko3/21/2008 5:34 am 說:

嘿嘿,所以我才用中文寫啊 XD。

 

<< 回到主頁