↖潔牙ㄟ☆蕾絲↘: 2010

2010年11月27日星期六

[Hom] Few exercises of homomorphism - sumcap

這裡我只想專注在CS-generalization上面。所以，為了強調我們不太需要知道sumcap細節上是什麼，這邊故意不去解釋相關的函數。有關steep、rcap和sumcap，請參考 Determining List Steepness in a Homomorphism。

和上一篇一樣，這裡也使用 T 表示 term，同時繼續使用那四種箭頭。

根據sumcap的定義(我們不考慮empty-list的情況)：

sumcap [x] = ↔ Tb = (x,x)

For original definition of leftwards(foldr) and rightwards(foldl)：

⟨sum, rcap⟩ = foldr step (0, ∞) where step x (s, y) = (x + s, (x - s) ↓ y)
⟨sum, rcap⟩ = foldl step (0, ∞) where step (s, y) x = (s + x, (y - x) ↓ x)

we can obtain Tc and Ts as follows：

Tc ↔ sumcap (x << xs) = (x + (fst.sumcap xs), (x - (fst.sumcap xs)) ↓ (snd.sumcap xs))
Ts ↔ sumcap (ys >> y) = ((fst.sumcap ys) + y, ((snd.sumcap ys) - y) ↓ y)

Rb is defined as follows：

Rb = { a ↓ a → a }

GO!!!

σ1 = {
X0 ↦ (x,x) ⊛ (sumcap xs) ⇀ (x + (fst.sumcap xs), (x - (fst.sumcap xs)) ↓ (snd.sumcap xs))
}
σ2 = {
X0 ↦ (sumcap ys) ⊛ (y, y) ⇀ ((fst.sumcap ys) + y, ((snd.sumcap xs) - y) ↓ y)
}
Tg = X0

decomposition: ⊛, ⇀, (,) and ↓

σ1 = {
X1 ↦ (x,x)
X2 ↦ (sumcap xs)
X3 ↦ x + (fst.sumcap xs)
X4 ↦ x - (fst.sumcap xs)
X5 ↦ snd.sumcap xs
}
σ2 = {
X1 ↦ (sumcap ys)
X2 ↦ (y,y)
X3 ↦ (fst.sumcap ys) + y
X4 ↦ (snd.sumcap xs) - y
X5 ↦ y
}
Tg = X1 ⊛ X2 ⇀ (X3, X4 ↓ X5)

decomposition (+)
這邊特別標記一下，我在這邊用了一個rule term，
sumcap as ↔ ((fst.sumcap) as, (snd.sumcap) as)。
但是這個rule term其實並沒有出現在任何一個關於Rc,Rs,Rb甚至是R++的論述裡面。
充其量應該只能說這是從semantic equality來的..
這可能要找時間好好想想是怎回事 @@

σ1 = {
X1 ↦ (x,x)
X2 ↦ (sumcap xs)
↦ (fst.sumcap xs, snd.sumcap xs)
X4 ↦ x - (fst.sumcap xs)
X5 ↦ snd.sumcap xs
X6 ↦ x
X7 ↦ fst.sumcap xs
}
σ2 = {
X1 ↦ (sumcap ys)
↦ (fst.sumcap ys, snd.sumcap ys)
X2 ↦ (y,y)
X4 ↦ (snd.sumcap xs) - y
X5 ↦ y
X6 ↦ fst.sumcap ys
X7 ↦ y
}
Tg = X1 ⊛ X2 ⇀ (X6 + X7, X4 ↓ X5)

docomposition: (,) in left hand side

σ1 = {
X4 ↦ x - (fst.sumcap xs)
X5 ↦ snd.sumcap xs
X6 ↦ x
X7 ↦ fst.sumcap xs
X8 ↦ x
X9 ↦ x
X10 ↦ fst.sumcap xs
X11 ↦ snd.sumcap xs
}
σ2 = {
X4 ↦ (snd.sumcap ys) - y
X5 ↦ y
X6 ↦ fst.sumcap ys
X7 ↦ y
X8 ↦ fst.sumcap ys
X9 ↦ snd.sumcap ys
X10 ↦ y
X11 ↦ y
}
Tg = (X8,X9) ⊛ (X10,X11) ⇀ (X6 + X7, X4 ↓ X5)

decomposition: (-)
finding out agreements

σ1 = {
X5 ↦ snd.sumcap xs (agree with X11)
X6 ↦ x (agree with X8)
X7 ↦ fst.sumcap xs (agree with X10)
X8 ↦ x
X9 ↦ x
X10 ↦ fst.sumcap xs
X11 ↦ snd.sumcap xs
X12 ↦ x (agree with X9)
X13 ↦ fst.sumcap xs (agree with X10)
}
σ2 = {
X5 ↦ y (agree with X11)
X6 ↦ fst.sumcap ys (agree with X8)
X7 ↦ y (agree with X10)
X8 ↦ fst.sumcap ys
X9 ↦ snd.sumcap ys
X10 ↦ y
X11 ↦ y
X12 ↦ snd.sumcap ys (agree with X9)
X13 ↦ y (agree with X10)
}
Tg = (X8,X9) ⊛ (X10,X11) ⇀ (X6 + X7, (X12 - X13) ↓ X5)

agreement!

σ1 = {
X8 ↦ x
X9 ↦ x
X10 ↦ fst.sumcap xs
X11 ↦ snd.sumcap xs
}
σ2 = {
X8 ↦ fst.sumcap ys
X9 ↦ snd.sumcap ys
X10 ↦ y
X11 ↦ y
}
Tg = (X8,X9) ⊛ (X10,X11) ⇀ (X8 + X10, (X9 - X10) ↓ X11)

There is no any free variable!!
Tg = (X8,X9) ⊛ (X10,X11) ⇀ (X8 + X10, (X9 - X10) ↓ X11) .

2010年11月26日星期五

[Hom] Few exercises of homomorphism - max and scanr

為了方便, 下面用 T 表示 term，

Tb = base term
Tc = cons term
Ts = snoc term
Tg = generator term

箭頭方面，

↦ : variable-term binding
↔ : conversion relation
→ : rewriting relation
⇀ : some "arrow" operator
(for example, ⇀ could be ↔ or →)

另外，也使用下面的一些 function

(<<) : cons
(>>) : snoc
(↑) : max
(↓) : min

example 01 - max

Step 1 - To find out the base, cons and snoc term

max [a] ↔ Tb = a
Tc = x ↑ (max xs) ↔ Tb ⊛ (max xs) = x ⊛ (max xs)
Ts = (max ys) ↑ y ↔ (max ys) ⊛ Tb' = (max ys) ⊛ y

Step 2 - To find out base rule term, Rb
這個case因為用不到，剛好免了。

Step 3 - Initializing substitutions and generator term

σ1 = {X0 ↦ x ↑ (max xs) ⇀ x ⊛ (max xs)}
σ2 = {X0 ↦ (max ys) ↑ y ⇀ (max ys) ⊛ y}
Tg = X0

其實這邊看也看得出來 ⊛ 就是 ↑
不過我還是套了三次 decomposition (for ↔, ⊛ and ↑)
還有兩次的 agreement (x=x且max ys=max ys; max xs = max xs且y=y)
最後就會得到 Tg = x3 ⊛ x4 ⇀ x3 ↑ x4 .

example 02 - scanr

For simply, there fix the higher-order function argument of scanr, i.e. scr = scanr ⊕, mp a xs = map (⊕ a) xs.

Step 1 - To find out the base, cons and snoc term

For given definitions

scr (x << xs) = (x ⊕ (head (scr xs))) << (scr xs)
scr (ys >> y) = (mp y (scr ys)) >> y

we can obtain following rule terms:

scr [a] ↔ Tb = [a]
[x] ⊛ (scr xs) ↔ Tc = [x ⊕ (head (scr xs))] ++ (scr xs)
(scr ys) ⊛ [y] ↔ Ts = (mp y (scr ys)) ++ [y]

Step 2 - To find out base rule term, Rb

Rb = {
mp a [b] → [a ⊕ b]
head [a] → a
}

Step 3 - Initializing substitutions and generator term, and, run!!

σ1 = {X0 ↦ [x] ⊛ (scr xs) ⇀ [x ⊕ (head (scr xs))] ++ (scr xs)}
σ2 = {X0 ↦ (scr ys) ⊛ [y] ⇀ (mp y (scr ys)) ++ [y]}
Tg = X0

decomposition: ⊛, ⇀ and (++)

σ1 = {
X1 ↦ [x]
X2 ↦ (scr xs)
X3 ↦ [x ⊕ (head (scr xs))]
X4 ↦ (scr xs)
}
σ2 = {
X1 ↦ (scr ys)
X2 ↦ [y]
X3 ↦ (mp y (scr ys))
X4 ↦ [y]
}
Tg = X1 ⊛ X2 ⇀ X3 ++ X4

agreement: X4-X2

σ1 = {
X1 ↦ [x]
X2 ↦ (scr xs)
X3 ↦ [x ⊕ (head (scr xs))]
}
σ2 = {
X1 ↦ (scr ys)
X2 ↦ [y]
X3 ↦ (mp y (scr ys))
}
Tg = X1 ⊛ X2 ⇀ X3 ++ X2

decomposition: mp

σ1 = {
X1 ↦ [x]
X2 ↦ (scr xs)
X3 ↦ [x ⊕ (head (scr xs))] ↦ mp (head (scr xs)) [x] {by "mp a [b] → [a ⊕ b]"}
X4 ↦ head (scr xs)
X5 ↦ [x]
}
σ2 = {
X1 ↦ (scr ys)
X2 ↦ [y]
X3 ↦ (mp y (scr ys))
X4 ↦ y
X5 ↦ (scr ys)
}
Tg = X1 ⊛ X2 ⇀ (mp X4 X5) ++ X2

agreement: X5-X1

σ1 = {
X1 ↦ [x]
X2 ↦ (scr xs)
X4 ↦ head (scr xs)
}
σ2 = {
X1 ↦ (scr ys)
X2 ↦ [y]
X4 ↦ y ↦ head [y]
}
Tg = X1 ⊛ X2 ⇀ (mp X4 X1) ++ X2

decomposition: head

σ1 = {
X1 ↦ [x]
X2 ↦ (scr xs)
X4 ↦ (scr xs)
}
σ2 = {
X1 ↦ (scr ys)
X2 ↦ [y]
X4 ↦ [y]
}
Tg = X1 ⊛ X2 ⇀ (mp (head X4) X1) ++ X2

agreement: X4-X2

σ1 = {
X1 ↦ [x]
X2 ↦ (scr xs)
}
σ2 = {
X1 ↦ (scr ys)
X2 ↦ [y]
}
Tg = X1 ⊛ X2 ⇀ (mp (head X2) X1) ++ X2

There is no any free variable!!
Tg = X1 ⊛ X2 ⇀ (mp (head X2) X1) ++ X2 .

這兩個例子中，做 CS-generalization 的過程確實相當的機械化。任何需要的 term rewriting 都是直接套用Rb裡面的就好。
另外，過程中我發現幾個hint：

一旦產生出 ⇀ 之後，一概都以右手邊的free variable優先處理
需要term rewriting時，都是在Rb裡面找到一個合適的rule term。並且，很多時候都是先從rule term的右手邊去match一個合適的。
做decomposition的時候不要太貪心，有時候會因為一次decompose太多root function，而使的某一個free varable錯過一個好的binding時機。
term rewriting會很直接的影響到agreement。例如說scanr的例子，[x ⊕ (head (scr xs))]要寫成mp (⊕ x) [head (scr xs)]還是mp (⊕ (head (scr xs))) [x]，這會對後面造成很大的影響。而且這又取決於⊕是不是commutative之類的前提/假設。另外，在sumcap的例子裡面(請參考下一篇)，對(+)做decomposition的過程中，要不要把 a+b 換成 b+a 也會是個需要都嘗試看看的部份。因為和mp的情況一樣，有可能需要交換一下順序才做的下去，也有可能不交換才可以，當然也可能不管怎樣都可以做下去。所以，我想這裡是個比較難說「不需要人的輔助」的部份。

2010年11月22日星期一

M$ Font Sucks!!

前天吧，因故灌了M$ Office。Office本身難用與否就不提了，我倒是發現電腦裡面某些地方看起來怪怪的。直到今天突然在看新聞才發現問題是什麼。原來是字體啦，我的字體之前沒那麼難看呀，怎麼變成讓人看起來不太舒服的字體呢？隨手擷個圖：

真是難看死了，後來想說該不會是被M$偷灌了什麼字體進來所以被弄成難看的樣子。所以去 /Library/Fonts下面看一下。果然，多了一個什麼Microsoft的folder。砍掉以後就恢復到原本的樣子惹。

2010年11月17日星期三

[筆記]Haskell X Fractal

想做Fractal
但是仔細想想
Parallel Haskell不柔
Fractal沒真的仔細看過
GUI(現在只有wxHaskell可以選)只跑過demo
慘絕人寰之餘
紀錄一下還沒時間看的網頁吧

http://haskell.org/haskellwiki/WxHaskell/Quickstart#Painting

http://gregheartsfield.com/fractal-hs/

http://hackage.haskell.org/packages/archive/haskore/0.1.0.4/doc/html/src/Haskore-Example-Fractal.html

http://boson4.phys.tku.edu.tw/high_school/unit_fractals.htm

http://classes.yale.edu/Fractals/MandelSet/MandelDef/Definition/Definition.html

http://en.wikipedia.org/wiki/Mandelbrot_set

2010年11月1日星期一

[Note] The GUI Issue

gtk+，之前在Mac OSX上面跑太多次有問題，已經有點怕了說，不過這次用brew灌就可以用了！不過compile的時候要給的參數好多，照說應該link和load的路徑都不需要再給，改下次有空再來試好了。

裝qt，其實nokia往站上有binary可以裝，可是跑起來覺得怪彆扭的。重點是這樣就打壞了原本弄好的lib系統。所以還是看看homebrew有沒有，果然有，那就灌吧！
> brew install qt
然後，等超過一個半小時了還沒好，所以下次再寫qt筆記吧 XD

這兩天在弄gtk+，莫名其妙的弄半天以後發現，brew灌起來的gtk+應該是可以用。雖說會噴一個奇怪的error出來，但是至少有東西了(那個error好像和顯示裝置的驅動還是設定有關)。gtk可以跑，我當然一如往常的想去試一下多年的夢想「gtk2hs」！他官網晃一圈以後就想起一個慘忍的事實：gtk2hs在ghc 6.12上面有bug。Orz

好吧，只好忍痛和gtk2hs說掰掰。不甘心之餘又回頭去看看現在有什麼其他的GUI package可以用用看。東看西看，還是只有gtk2hs和wxHaskell比較大宗。Orz

無奈之下，試試看wxHaskell吧：
在開始裝wxhaskell之前，要先把mac os x內建的wxWidgets換掉：
> brew install wxmac
如果沒有做這一步，之後執行macosx-app出來的.app會不能執行(mac會該說這個東西格式不對)。

wxmac要build好一會兒(10~20分鐘左右)。然後就可以用cabal來install正主兒：
> cabal install wxcore 。
build的時候，有滿坑滿谷的cpp deprecated warning Orz。為保安全，紀錄下g++的version：

i686-apple-darwin10-g++-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5664)
Copyright (C) 2007 Free Software Foundation, Inc.

然後 > cabal install wx 。
我也不知道我幹麼分兩段裝，一定是白爛病發作了XD。裝好以後確定一下東西有進去ghc-pkg。
> ghc-pkg list

/usr/local/Cellar/ghc/6.12.3/lib/ghc/package.conf.d
..[略]..
/Users/Jaiyalas/.ghc/i386-darwin-6.12.3/package.conf.d
wx-0.12.1.6
wxcore-0.12.1.6
wxdirect-0.12.1.3

接下來才是問題所在，gui的東西似乎在mac上面都特別刁鑽。wx同樣也不是可以讓你乖乖跑一下就有結果可以開開心心用的。用ghc compile以後直接執行他會噴error如下，並且會跑出一個只能看不能用的視窗。

10:46:15: Debug: wxColour::Set - couldn't set to colour string 'GREY'
[Debug] 10:46:15: Adding duplicate image handler for 'PNG file'
[Debug] 10:46:15: Adding duplicate image handler for 'JPEG file'
[Debug] 10:46:15: Adding duplicate image handler for 'TIFF file'
[Debug] 10:46:15: Adding duplicate image handler for 'GIF file'
[Debug] 10:46:15: Adding duplicate image handler for 'PNM file'
[Debug] 10:46:15: Adding duplicate image handler for 'PCX file'
[Debug] 10:46:15: Adding duplicate image handler for 'Windows icon file'
[Debug] 10:46:15: Adding duplicate image handler for 'Windows cursor file'
[Debug] 10:46:15: Adding duplicate image handler for 'Windows animated cursor file'
[Debug] 10:46:15: Adding duplicate image handler for 'TGA file'
[Debug] 10:46:15: Adding duplicate image handler for 'XPM file'

解決的辦法是把原本的executable file包成.app再去打開它。不過這之前就需要macosx-app來作這件事。細節可以參考stackoverflow上的說明。這邊作個簡單的描述：
抓下macosx-app的模板順便改名字和操作模式
> wget http://code.haskell.org/wxhaskell/bin/macosx-app-template
> mv macosx-app-template macosx-app
> chmod a+x macosx-app
然後開個順手的editor把下面這段加到macosx-app的最上面：

#!/bin/sh

libdir=""

wxrezcomp="`wx-config --rezflags`"
wxrezfile=""
if test "$wxrezcomp"; then
for word in $wxrezcomp; do
temp="`echo $word | grep '[^_]*_mac-[^r]*r'`"
if test "$temp"; then
wxrezfile="$temp"
fi
done
fi

if test "$wxrezfile"; then
wxrezdir="`echo $wxrezfile | sed -e 's|$.*$/libwx_mac.*|\1|'`"
wxinstallrezcomp="`echo \"${wxrezcomp}\" | sed -e \"s|${wxrezdir}|${libdir}|g\"`"
wxinstallrezfile="`echo \"${wxrezfile}\" | sed -e \"s|${wxrezdir}|${libdir}|g\"`"
fi

rezcomp="$wxinstallrezcomp"
rezfile="$wxinstallrezfile"

直接執行macosx-app的話會看到他噴出一些warning
> ./macosx-app

Warning: --rezflags, along with Mac OS classic resource building is deprecated. You should remove this from your Makefile and build .app bundles instead.
error: you need to specify a program. Use "--help" to show valid options.

這邊可以不用理他(其實是我也不知道怎要怎麼解決，反正可以用 Orz)

以上都準備好以後就可以直接
> ghc -package wx -o helloworld HelloWorld.hs
> macosx-app -v helloworld
> open helloworld.app
感人的小視窗就會跳出來惹 OvQ

2010年7月28日星期三

[LLVM] LLVM-2.7 & LLVM-0.8.0.2

一直不停re-compile llvm實在是太痛苦了，
所以好不容易弄完之後，決定來紀錄一下這整件
痛苦的事。

話說要裝llvm-2.7很簡單，就
> brew install llvm。
輕鬆、快速又好吃~
然後就想要開開心心的灌一下llvm haskell binding
結果，config一直死掉：

...snip...
checking for unistd.h... yes
checking llvm-c/Core.h usability... yes
checking llvm-c/Core.h presence... yes
checking for llvm-c/Core.h... yes
checking for LLVMModuleCreateWithName in -lLLVMCore... no
configure: error: could not find LLVM C bindings
cabal: Error: some packages failed to install:
llvm-0.8.0.2 failed during the configure step. The exception was:
exit: ExitFailure 1

上網查了以後發現問題出在Mac上面，但是實際
原因不明。總之，作法很簡單：就是把llvm-2.7
重新build成universal binary就好了，以下
重現當時機歪的整個過程(含brew的link)：

[0] 砍掉原本brew install來的llvm 2.7
> brew uninstall llvm

[0.1] 準備給homebrew用的folder
(假設homebrew的prefix=/usr/local)
> cd /usr/local/Cellar
> mkdir llvm-gcc
> mkdir llvm-gcc/4.2
> mkdir llvm
> mkdir llvm/2.7

[1] 抓一下llvm和llvm-gcc
> wget 'http://llvm.org/releases/2.7/llvm-gcc-4.2-2.7-x86_64-apple-darwin10.tgz'
> wget 'http://llvm.org/releases/2.7/llvm-2.7.tgz'
> tar xzf llvm-gcc-4.2-2.7-x86_64-apple-darwin10.tgz
> tar xzf llvm-2.7.tgz

[2] 手動安裝(copy)一下llvm-gcc-4.2到/usr/local/Cellar下面去
> cd llvm-gcc-4.2-2.7-x86_64-apple-darwin10
> cp -R ./* /usr/local/Cellar/llvm-gcc/4.2
> brew link llvm-gcc
> cd ..

[3] make/make install llvm-2.7
> cd llvm-2.7
> ./configure --prefix=/usr/local/Cellar/llvm/2.7 --with-llvmgccdir=/usr/local/Cellar/llvm-gcc/4.2
(這邊要等一會兒)
> set -x UNIVERSAL 1
> make
(這邊要等一個小時左右)
> make install
> brew link llvm
> cd ..
至此，llvm-2.7和llvm-gcc-4.2就都裝好了。

llvm重灌好以後就直接
> cabal install llvm
就ok了

llvm haskell binding裝好以後，可以跑一下
他的example。看是要去這裡抓？還是要直接
解開~/.cabal/packages/hackage.haskell.org/
llvm/0.8.0.2/llvm-0.8.0.2.tar.gz這一個檔案。進去以後直接
> make
以後再看想要執行程式即可。
如果執行起來有問題可以參考這個。

以上參考自這篇和這篇

2010年7月26日星期一

[OSX 10.6]The Note! Cont.

接續上一篇

進入 fish_prompt.fish
> sudo vim fish_prompt.fish
fish_prompt.fish裡面描述了不同user登入以後prompt的長相。
預設上是"(user)@(hostname)(prompt_pwd)>"這樣一串。
P.S.只是prompt_pwd是縮短以後的pwd。

[增加顏色]
使用 set -l ooxx (set_color color) 增加區域色彩變數
顏色設定的方式基本上就是直接用%s輸出給printf

[換行]
在printf後面的'ooxx'加入 \n

[縮減user/hostname]
使用whoami或hostname，後面再接上 | cut -c 1-n

[顯示時間日期]
直接在prontf後面的參數中呼叫 date "+format"

我目前的設定

set -l _clrB (set_color blue)
set -l _clrC (set_color white)
set -l _clrR (set_color red)
set -l _clrY (set_color yellow)
printf '\n%s%s%s[' "$_clrR" (whoami|cut -c 1-3) "$_clrY"
printf '%s%s%s]%s[' "$_clrC" (date "+%H:%M") "$_clrY" "$_clrB"
printf '%s%s%s]%s' "$__fish_prompt_cwd" (prompt_pwd) "$_clrB" "$__fish_prompt_normal"
printf '\n> '

結果如下

P.S.色彩設定方面的補完就期待godfat來分享一下了 :)

[OSX 10.6]The Note!

前兩天重灌了一下Mac OS X 10.6。真的各方面都蠻不錯的，
除了那該死的中文字體。真的是難看死了...。

這次針對一些工具方面做了更新：首先是package managemant。
從原本的Macport換成Homebrew。這是因為我在手動make install ghc
以後突然想用port裝一下darcs，結果port竟然開開心心的開始幫
我build好久以前的ghc版本，囧。一怒之下就聽從godfat的讒言把port
及其他一堆自己make install(包括我記憶中我用.pkg裝的東西)給暴力
砍了，因為make install都去了/usr/local/下面，而port install都進了
/opt/local/底下，所以在godfat的鼓吹之下rm -R就給他用力打下去
啦～～～。而.pkg的部份我只記得我ghc-6.12.3是.pkg裝起來的，
所以就去/usr/bin/下面把ghc*的東西砍乾淨。最後才再灌上brew。

> ruby -e "$(curl -fsS http://gist.github.com/\

raw/323731/install_homebrew.rb)"

當然, 要順便開開心心的把用習慣的東西一併裝一裝。
> brew install fish
> brew install git
> brew install haskell-platform

Fish with Multiline Prompt：
fish shell本身沒有支援multiline prompt的處理，因為fish在
讀入自己內部用來存prompt訊息的prompt_list時，會將'\n'給忽略。
也就造成了在fish_prompt.fish裡面插入'\n'於printf後面會無效
這樣的問題。找了好一會以後，google到一個仁兄的解決辦法。
[1] 砍掉原本的fish: > brew uninstall fish
[2] 下載fish的source code
[3] 修改裡面的reader.c檔(細節)
[4] 重編fish
> ./configure --prefix=/usr/local/Cellar/fish/1.23.1 --without-xsel
> sudo make install
[5] 把brew連到自己裝的fish上面
> brew link fish
應該要有類似這樣的結果
30 links created for /usr/local/Cellar/fish/1.23.1
[6] 順便 > chsh -s /usr/local/bin/fish 一下。

灌好fish之後就可以開始改fish shell裡面的東西，也就是prompt
的output設定。fish相關的一些function都放置在/usr/local
/Cellar/fish/1.23.1/share/fish/functions目錄下，
而這裡的目的是要改有關prompt的設定，也就是檔案: fish_prompt.fish。

P.S. 有關fish_prompt.fish的設定就下回分解吧 XD

2010年6月29日星期二

[Flolac'10]Operational Semantics Ex1

今天講了一點基本的Operational Semantics的東西。出了一個簡單的Homework。反正不用交出去，OCaml也不熟，所以就用Haskell來玩一下看看。:)

type Number = String
type Variable = String
data AExp = Num Number
          | Var Variable
          | Add AExp AExp
          | Mult AExp AExp
          | Sub AExp AExp
          deriving (Show)

data BExp = T
          | F
          | Eq AExp AExp
          | LeEq AExp AExp
          | Not BExp
          | Conj BExp BExp
          deriving (Show)
          
data Stm = Ass Variable AExp
         | Skip
         | Seq Stm Stm
         | If BExp Stm Stm
         | While BExp Stm
         | Repeat Stm BExp
         deriving (Show)
         
type State = Variable -> Int

n :: Number -> Int
n m = (read m) :: Int

a :: AExp -> State -> Int
a e s  = case e of 
  Num m -> n m
  Var x -> s x
  Add e1 e2 -> (a e1 s) + (a e2 s)
  Mult e1 e2 -> (a e1 s) * (a e2 s)
  Sub e1 e2 -> (a e1 s) - (a e2 s)

b :: BExp -> State -> Bool
b e s  = case e of
  T          -> True
  F          -> False
  Eq e1 e2   -> (a e1 s) == (a e2 s)
  LeEq e1 e2 -> (a e1 s) <= (a e2 s)
  Not bexp   -> not (b bexp s)
  Conj b1 b2 -> (b b1 s) && (b b2 s)

data Configure = Inter Stm State
               | Final State
               

update :: Variable -> AExp -> State -> State
update x e s y = if (x==y) 
  then a e s 
  else s y

ns :: Configure -> Configure
ns c = case c of
  (Inter (Ass v e) s)     -> Final (update v e s)
  (Inter (Skip) s)        -> Final s
  (Inter (Seq st1 st2) s) -> let (Final s') = ns (Inter st1 s) in ns (Inter st2 s')
  (Inter (If bexp st1 st2) s) -> if (b bexp s) 
    then ns (Inter st1 s)
    else ns (Inter st2 s)
  (Inter (While bexp st) s)   -> if (b bexp s) 
    then ns (Inter st s)
    else (Final s)
  (Inter (Repeat st bexp) s)  -> let (Final s') = ns (Inter st s) in
    if (b bexp s') 
      then ns (Inter (Repeat st bexp) s')
      else Final s'

default_state x = error "NotFound"

x1_state = update "x" (Num "1") default_state

test1 = Seq Skip (Ass "x" (Num "5"))

new_state = let (Final sFun) = ns (Inter test1 x1_state) in sFun "x"

2010年4月21日星期三

[Note]Ray Tracing with Haskell using package:parallel

[草記=只是暫時紀錄,整篇會重寫]

這兩天都在弄ray tracing的事情
找了好幾個C/C++版本的code來參考
不過, 幾乎是看沒有懂
最後當然還是決定投靠haskell, XD

找了幾個版本的範例程式
其中一個用gtk作ui
這個版本暫時擱置
因為我gtk一直怪怪的,跑不出東西 Orz

另一個是平行版本

剩下一個是這個和這個

除了gtk那個, 剩下都是直接輸出ppm檔
所以沒有parallel的那兩個都不需要特別題什麼
而且他們也沒有import什麼package進來
簡直就是一整個貼心 XD

parallel那個就囧了
一開始compile一直說 parse error
所以把L49和L5?的兩個"!"給砍了
然後就發現package有問題
所以灌了 AC-vector 1.2.2 和 parallel-2.2.0.1
compile以後, 還是有問題
他說*<>沒定義而且*|重複定義...
弄了好一會兒以後發現
因為原作者是用AC-vector 1.1.1
而AC-vector每次改版都大改... @@
所以又用 ghc-pkg hide AC-Vector-1.2.2
把新版的AC-vector disable掉
一番折騰之後
終於ok了
但是跑一下發現, CPU 只吃了50% @@
所以想說該不會是因為沒有開ghc的選項
所以找了一下以前的資料：
在ghc --make ....... 後面加上一個「-threaded」
然後跑程式的時候加上 +SRT -N2 的選項
e.g. ./ray4-hs 5 50 +RTS -N2 > out.ppm
btw, parallel這個程式需要兩個參數, 遞迴的次數和邊長

而David J. King的那個版本則是>./ray 500 > out.ppm
500也是邊長參數

ps - .ppm閱讀 :
有人推薦xv, 不過因為它是x window所以難用
最後我裝了ToyViewer
雖說有一點點鈍鈍的
但是目前還不錯用

2010年4月9日星期五

[Temp]Parallel Functional Programming

http://www.mathematik.uni-marburg.de/~eden/
資料蠻多的
值得一試

2010年4月8日星期四

[AI]Learning categories in neural network

今天終於釐清了兩年前遇到的問題：程式在做參數式學習的時候都會需要根據已知的情況去調整參數向量，但是應該要「看完整本書在學起來？」還是「看完一段就學一次？」這一直是當時在實作Perceptron的時候卡到的小疑惑。不過那時候不是很熟悉整個情況，所以也說不出個很顯著的所以然來。最後是根據給定的演算法去做。

今天又遇到這個問題了，不過這次有比較清楚的腦海地圖了。

舉個例子來解釋：假設今天某個classify system吃3個參數作為input，所以該system應該具有一個weight vector長做這樣：
$\mathbb{W}=\left[\begin{array}{c}W_{0}\\W_{1}\\W_{2}\\W_{3} \\ \end{array}\right], W_{0}=bias$
並且我們有三個classified instance：
$\mathbb{X}_{\alpha}=\begin{bmatrix}1&X_{\alpha1}&X_{\alpha2}&X_{\alpha3}\end{bmatrix}$
$\mathbb{X}_{\beta}=\begin{bmatrix}{1} &{X_{\beta1}}&{X_{\beta2}}&{X_{\beta3}}\end{bmatrix}$
$\mathbb{X}_{\gamma}=\begin{bmatrix}{1}&{X_{\gamma1}}&{X_{\gamma2}}&{X_{\gamma3}}\end{bmatrix}$

而每一次W(weight vector)乘上(inner product)其中一個X(input instance(again, it is a vector))然後產生一個O(output)，並且我們已知該instance X具有一個正確的結果T。根據某個函數f(T-O), 我們可以得到∆W：「W目前應該更新的程度值」。舉例如下：
${\nabla}E(\mathbb{W})=\left[\begin{array}{c}\delta\\0\\0\\0\\\end{array}\right]=\Delta\mathbb{W}$
這表示產生出來的∆W的意思是「僅需要更新bias值」。

但是這裡就有個問題了，因為大多的learning model都會需要一再的對整個instance space去做運算。所以到底是每看完一筆instance就更新？
$\mathbb{W}'=(((\mathbb{W}+\delta\mathbb{W}_{\alpha})+\delta\mathbb{W}_{\beta})+\delta\mathbb{W}_{\gamma})$
還是看完整個instance space以後再去更新？
$\mathbb{W}'=\mathbb{W}+\Sigma(\Delta\mathbb{W})$

前面這種稱為針對資料做逐一學習的方法稱為：Incremental Learning，而相對地，對全部資料作一次性的學習稱為：Batch Learning。

另Batch Learning a.k.a. Epoch Learning。
而Incremental Learning則又被稱為
1. Pattern Learning
2. Instantaneous Learning

不過Pattern Learning會容易和Pattern Recognition產生混淆，而Instantaneous Learning容易造成「以為learning的行為是instantaneously」的誤會。所以兩者現在都已經不常使用了。

2010年2月3日星期三

[reStructuredText] Pygments Intro. & Install

參考了劍心的這篇，也弄了pygments來用用看。

不過我不是用port install來裝。原因不明地，> sudo port install py26-pygments以後，不知道怎麼打開它。@@
> pygmentize
> pygments
> py-pygments
> py26-pygments
等等的排列組合都試過了，但是就是不能用。
不知道是哪個地方跳針了還是如何? @@
最後解決的方法是去PyPI下載source code以後自己build就可以用了。(我的python版本=2.5.1)

> wget 'http://pypi.python.org/packages/source/P/Pygments/Pygments-1.2.2.tar.gz#md5=920e706a817437eae3a1406380421a3d'
> tar -xzf Pygments-1.2.2.tar.gz
> cd Pygments-1.2.2
> sudo python setup.py install

pygments有四個重要的元件：Lexers, Formatters, Filters和Styles。Lexers是source code parser；Formatters是output generator；Filters是針對特別需求時可以更改部份輸出結果用的工具；Styles是色彩字體等格式的定義。詳情可以參考Pygments Online Document中的Builtin components的部份。

(註：要使用有關圖檔的formatter都需要安裝PIL(Python Image Library)。build的方法幾乎和build pygments一模一樣。只是wget的target要換一下罷了。

> wget http://effbot.org/downloads/Imaging-1.1.7.tar.gz
> tar -xf Imaging-1.1.7.tar
> cd Imaging-1.1.7
> sudo python setup.py install

)

(註：在Mac上，style的定義檔存放在/Library/Python/2.5/site-packages/Pygments-1.2.2-py2.5.egg/pygments/styles/這裡面。劍心的twilight.py我就是直接賽進這邊就可以用了。)

pygmentize身上也有非常多參數可以下。最基本的兩個flag分別是-f和-o。-f 可以指定要使用的formatter(也就是指定輸出格式)；-o 則是和一般compiler一樣指定輸出檔名。當然，因為formatter本身就包含了format在內，所以也可以不要用-o，不過這樣一來就要自己做檔案輸出。以下兩個作法是等價的。
> pygmentize -f html -o setup_c.html setup.c
> pygmentize -f html setup.c > setup_c.html

-O可以進一步設定lexer和formatter的選項。-O可以一次接受複數個選項，但是這也造成了-O不能接受含有","或"="的選項。因此也就有了-P的出現，-P一次只能吃一個選項參數，但是選項參數中就可以包含","或"="。
> pygmentize -f html -O full,style=twilight,linenos=1 01.hs
> pygmentize -f html -P "heading=Pygments, the Python highlighter" full,linenos=1 setup.py
相似於-O和-P, -F是用來在token stream上面增加filter用的。用法大概是這樣-F keywordcase:case=upper,whitespace:spaces=True、-F whitespace:spaces=True。
(註，這三個參數都可以重複一直使用。)

pygmentize預設只會生出資訊而不會把style的定義也一併輸出，也就是說，
> pygmentize -f html setup.py > test.html
用browser打開test.html以後會發現是黑白的。
因此我們可以用
> pygmentize -f html -S twilight -a .pygments > style.css
來取得名為twilight的style的css檔

還有, 參數-N可以查詢某source code的lexer。
例如說> pygmentize -N Makefile會輸出make。

此外pygmentize也提供兩個flag, -L和-H, 可以查詢lexers, formatters和filters的資訊(-L還可以查詢styles)。例如
> pygmentize -L會傾印lexers, formatters, filters和styles的資訊
> pygmentize -L styles會指定印出styles的資訊
> pygmentize -H formatter html會印出html的help info.

這是測試的結果(原因不明的在blogger上面Line#和Code會有點錯開)

import GHC.Conc
import System.Info
import Text.Printf
import Data.Version

main = do
    printf "Compiled with %s-%s on %s/%s\n"
           compilerName
           (showVersion compilerVersion)
           os arch
    printf "Running with %d OS threads\n" numCapabilities

2010年1月29日星期五

[OS] Taste of House

今天早上google了一下發現已經有人拿haskell來寫OS了，叫做House。其細節還沒細看，不過倒是抓下來試了一下。測試的環境基本上和這篇是一樣的。

首先在House的網站上載 hOp-x.y.flp 然後暴力把.flp給改成.img，接著就直接用VirtualBox去掛載這個映像檔到flppy device上面去，然後開機就可以了。

開機以後會進入GRUB的選單，接著就看想要進text mode還是graphics mode就好。

graphics mode大概長這樣，非常明顯這只是一個展示用的範例。這裡只提供了一些固定的功能可以稍微玩玩看。我甚至連怎麼關機或是離開都不知道。XD

這裡還發現一篇paper: A Principled Approach to Operating System Construction in Haskell (ICFP 2005)。最近如果沒有其他壓力的話，蠻想來研究看看這怎麼做的。

訂閱：文章 (Atom)

↖潔牙ㄟ☆蕾絲↘

標籤

網誌存檔

2010年11月27日星期六

[Hom] Few exercises of homomorphism - sumcap

2010年11月26日星期五

[Hom] Few exercises of homomorphism - max and scanr

2010年11月22日星期一

M$ Font Sucks!!

2010年11月17日星期三

[筆記]Haskell X Fractal

2010年11月1日星期一

[Note] The GUI Issue

2010年7月28日星期三

[LLVM] LLVM-2.7 & LLVM-0.8.0.2

2010年7月26日星期一

[OSX 10.6]The Note! Cont.

[OSX 10.6]The Note!

2010年6月29日星期二

[Flolac'10]Operational Semantics Ex1

2010年4月21日星期三

[Note]Ray Tracing with Haskell using package:parallel

2010年4月9日星期五

[Temp]Parallel Functional Programming

2010年4月8日星期四

[AI]Learning categories in neural network

2010年2月3日星期三

[reStructuredText] Pygments Intro. & Install

2010年1月29日星期五

[OS] Taste of House

標籤

網誌存檔

2010年11月27日 星期六

2010年11月26日 星期五

2010年11月22日 星期一

2010年11月17日 星期三

2010年11月1日 星期一

2010年7月28日 星期三

2010年7月26日 星期一

2010年6月29日 星期二

2010年4月21日 星期三

2010年4月9日 星期五

2010年4月8日 星期四

2010年2月3日 星期三

2010年1月29日 星期五

2010年11月27日星期六

2010年11月26日星期五

2010年11月22日星期一

2010年11月17日星期三

2010年11月1日星期一

2010年7月28日星期三

2010年7月26日星期一

2010年6月29日星期二

2010年4月21日星期三

2010年4月9日星期五

2010年4月8日星期四

2010年2月3日星期三

2010年1月29日星期五