## 2009年5月4日星期一

### A Lambda Calculus Interpreter in Haskell

## 2009年2月6日星期五

### Delayed-Branch-Slot Optimization and the Result

## Background

*branch delay slot*.

*after* the execution of the instruction immediately following it. The position following the branch instruction is called the *branch delay slot*. This is one of the few occasions where hardware natures becoming visible to programmers.

*every* normal instruction, even though *most* instructions do not locate in the delay slot.

### Idea for Optimization

*instruction specialization* optimization technique typically found in instruction set simulators where an intermediate form of decoded instructions are utilized to avoid decoding the same stream of instructions over and over again. The difference is, in this case, instead of specializing on the bit pattern of an individual instruction group, we specialize over the spatial position of individual instructions relative to special (branch/jump) instructions.

### Implementation

To my surprise, the benchmark shows that the new simulator executes at 105 MIPS (Millions Instructions per Second) against 115 MIPS of the original one. The delayed-slot “optimization” I have labored with actually brings down the performance by almost ten percent!

## 2009年1月4日星期日

### Useful Shell Shortcuts

Here are some small, simple, but surprisingly useful shell commands that I use everyday. Hopefully, you may find it useful too.

## Change Directory and List Content

`alias cd..='cd ..' alias cd...='cd ../..' cl() { cd $1 && ls } `

The functions of these commands are self-explanatory and may seem trivial on the first sight. But since `ls`

and `cd`

are the most common shell commands we use everyday, these shortcuts will save you a tremendously amount of key stokes in the long run.

## List Sub-directories Only

`alias lsd=alias lsd='ls -F | grep / | sed -e '\''s/\///g'\'' | column' `

Say that you are in a large code base (for instance, the Linux kernel) and you want to see if a particular sub-directory exists but do not want to clutter the output from the `ls`

command with all the ordinary files, then this shortcut comes in handy.

## Trash instead of Delete

`alias trash="mv -t ~/.Trash --backup=t" `

This command moves files into a specific location instead of delete them permanently. It is the shell version t*rash can* utility usually found in a GUI environment. Note that in Ubuntu, you might want to replace `~/.Trash`

with`~/.local/share/Trash/files`

, the standard location for trashed objects.

## 2008年12月16日星期二

### A Simple Symbolic Differentiation Program in Haskell

`This program is inspired from, again, SICP. Comparing to the Scheme code (section 2.3.2 of SICP), my program has a front-end parser that converts external representation (a String) of an expression to its internal representation (AST). The purpose of writing this program is to get familiar with the Parsec library in particular and to gain a better understanding of monadic parsers in general.`

`Loading the program in Hugs, a simple session go like this:`

`Main> deriv_x "x+3"`

`1`

`Main> deriv_x "x*y"`

`y`

`Main> deriv_x "(x+3)*x*y"`

`((x)+((x)+(3)))*(y)`

`Main> deriv_x "(x+3)^2"`

`(2)*((x)+(3))`

`The output is unfortunately cluttered with a lot of unnecessary parenthesizes. This can be solved by writing a specific function that normalize expressions to a canonical form. I am sure there is well-defined algorithm to do this but as I said above, writing a well-polished program doing differentiations really is not the purpose here. The complete program is list below:`

-- Simple symbolic differentiation program

module Main where

import Text.ParserCombinators.Parsec

import Text.ParserCombinators.Parsec.Expr

import qualified Text.ParserCombinators.Parsec.Token as T

import Text.ParserCombinators.Parsec.Language

-- Symbolic Expression

type Symbol = Char

data Expr = Add Expr Expr

| Mul Expr Expr

| Exp Expr Integer

| Var Symbol

| Num Integer

deriving (Eq)

instance Show Expr where

show e = case e' of

Num x -> show x

Var x -> [x]

Add u v -> "(" ++ show u ++ ")" ++ "+" ++ "(" ++ show v ++ ")"

Mul u v -> "(" ++ show u ++ ")" ++ "*" ++ "(" ++ show v ++ ")"

Exp u n -> "(" ++ show u ++ ")" ++ "^" ++ show n

where e' = simplify e

-- Deriving

deriv_ :: Symbol -> Expr -> Expr

deriv_ x e = simplify $ deriv__ x e

where deriv__ _ (Num _) = Num 0

deriv__ x (Var s) | (s == x) = Num 1

| otherwise = Num 0

deriv__ x (Add u v) = Add (deriv__ x u) (deriv__ x v)

deriv__ x (Mul u v) = Add (Mul (deriv__ x u) v) (Mul u (deriv__ x v))

deriv__ x (Exp u n) = Mul (Mul (Num n) (Exp u (n-1))) (deriv__ x u)

-- Expression Simplifier

simplify :: Expr ->; Expr

simplify e = let e' = simplify' e

in if e == e' then e else simplify e'

where

simplify' e@(Num n) = e

simplify' e@(Var x) = e

simplify' (Add (Num 0) u) = u

simplify' (Add u (Num 0)) = u

simplify' (Add (Num n) (Num m)) = Num (n + m)

simplify' (Add u v) = Add (simplify' u) (simplify' v)

simplify' (Mul (Num 0) v) = Num 0

simplify' (Mul u (Num 0)) = Num 0

simplify' (Mul (Num 1) v) = v

simplify' (Mul u (Num 1)) = u

simplify' (Mul (Num n) (Num m)) = Num (n * m)

simplify' (Mul u v) = Mul (simplify' u) (simplify' v)

simplify' (Exp u 0) = Num 1

simplify' (Exp u 1) = simplify u

simplify' (Exp (Num m) n) = Num (m ^ n)

simplify' (Exp u n) = Exp (simplify u) n

-- Parser

lang = T.makeTokenParser emptyDef

natural = T.natural lang

operator c = T.lexeme lang (char c)

variable = T.lexeme lang lower

expr = buildExpressionParser table factor

"expression"

mkNode :: (Expr -> Expr -> Expr) -> Expr -> Expr -> Expr

mkNode op t1 t2 = op t1 t2

mkAdd = mkNode Add

mkMul = mkNode Mul

mkExp :: Expr -> Expr -> Expr

mkExp e (Num n) = Exp e n

mkExp e _ = error "exponent must be a number"

table = [[op '^' (mkExp) AssocRight]

,[op '*' (mkMul) AssocLeft]

,[op '+' (mkAdd) AssocLeft]

]

where

op c f assoc

= Infix (do{ operator c; return f} <?> "operator") assoc

factor = T.parens lang expr

<|> do {v <- natural; return $ Num v }

<|> do {v <- variable; return $ Var v}

<?> "factor"

-- Driver

parseExpr :: String -> Expr

parseExpr input = case parse expr "" input of

Left err -> error $ "parse error at " ++ show err

Right out -> out

deriv_x = deriv_ 'x' . parseExpr

## 2008年12月11日星期四

### "Game of Life" in Haskell

This post includes a Haskell implementation of Conway’s *game of life*. There is nothing particularly fancy here and the implementation is not of the most efficient one either but, hi, this is my first interactive Haskell program (and it is not hard at all).

typeSize = InttypeCell = (Int, Int)typeBoard = [Cell]dataLife = Life Size Board

instanceShow Lifewhere

show (Life size board) =

[ifc == sizethen'\n'

elseif(r, c) `elem` boardthen'@'

else'-' | r <- [0..size-1],

c <- [0..size]]

next_life :: Life -> Life

next_life (Life size board) = Life size new_boardwhere

new_board = survivors ++ births

survivors = [cell | cell <- board,

letn = living_neighbors cell

inn == 2 || n == 3]

births = [(r,c) | r <- [0..size-1],

c <- [0..size-1],

letcell = (r, c)

in(not (cell `elem` board)) && ((living_neighbors cell) == 3)]

living_neighbors cell = length $ filter is_living $ neighbors cell

is_living cell = cell `elem` board

neighbors (r, c) = [((r - 1) `mod` size, ((c - 1) `mod` size)),

((r - 1) `mod` size, c),

((r - 1) `mod` size, ((c + 1) `mod` size)),

(r , ((c - 1) `mod` size)),

(r , ((c + 1) `mod` size)),

((r + 1) `mod` size, ((c - 1) `mod` size)),

((r + 1) `mod` size, c),

((r + 1) `mod` size, ((c + 1) `mod` size))]

interactive :: Life -> IO ()

interactive life

=doprint life

c <- getChar

ifc == 'q'then

return ()

else

interactive $ next_life life

Loading the above program into Hugs and an interactive session goes like this:

`Main> interactive $ Life 5 [(1,3), (2,1), (2,3), (3,2), (3,3)]`

-----

---@-

-@-@-

--@@-

-----

-----

--@--

---@@

--@@-

-----

-----

---@-

----@

--@@@

-----

-----

-----

--@-@

---@@

---@-

q

Main>

Have fun!

## 2008年12月6日星期六

### Huffman Tree Decoder

The Scheme code:

(define (make-leaf symbol weight)

(list 'leaf symbol weight))

(define (leaf? object)

(eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (make-code-tree left right)

(list left

right

(append (symbols left) (symbols right))

(+ (weight left) (weight right))))

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)

(if (leaf? tree)

(list (symbol-leaf tree))

(caddr tree)))

(define (weight tree)

(if (leaf? tree)

(weight-leaf tree)

(cadddr tree)))

(define (decode bits tree)

(define (decode-1 bits current-branch)

(if (null? bits)

'()

(let ((next-branch

(choose-branch (car bits) current-branch)))

(if (leaf? next-branch)

(cons (symbol-leaf next-branch)

(decode-1 (cdr bits) tree))

(decode-1 (cdr bits) next-branch)))))

(decode-1 bits tree))

(define (choose-branch bit branch)

(cond ((= bit 0) (left-branch branch))

((= bit 1) (right-branch branch))

(else (error "bad bit -- CHOOSE-BRANCH" bit))))

The Haskell code that does the same thing:

data Bit = B0 | B1

deriving (Eq, Ord)

instance Show Bit where

show B0 = "0"

show B1 = "1"

type Symbol = Char

type Weight = Int

data Tree = Leaf Symbol Weight

| Node [Symbol] Weight Tree Tree

decode :: Tree -> [Bit] -> [Symbol]

decode tree [] = []

decode tree bits = s : decode tree rest

where (s, rest) = decode1 tree bits

decode1 :: Tree -> [Bit] -> (Symbol, [Bit])

decode1 (Node _ _ (Leaf sym _) _ ) (B0:rest) = (sym, rest)

decode1 (Node _ _ left _ ) (B0:rest) = decode1 left rest

decode1 (Node _ _ _ (Leaf sym _)) (B1:rest) = (sym, rest)

decode1 (Node _ _ _ right ) (B1:rest) = decode1 right rest

-- Test

sample_message :: [Bit]

sample_message = [B0, B1, B1, B0, B0, B1, B0, B1, B0, B1, B1, B1, B0]

sample_tree :: Tree

sample_tree = Node ['A', 'B', 'C', 'D'] 8

(Leaf 'A' 4)

(Node ['B', 'C', 'D'] 4

(Leaf 'B' 2)

(Node ['C', 'D'] 2

(Leaf 'C' 1)

(Leaf 'D' 1)))

-- decode sample_tree sample_message

-- "ACABBDA"

Comments:

I think everybody will agree that the Haskell code is much cleaner and more concise than the corresponding Scheme code. I attribute the cleanness and conciseness to Haskell's algebraic data type and pattern matching structure: where in Scheme one express any data structure in lists in Haskell one defines data structures more naturally in data types; where in Scheme one fetch fields of data structures using ca(d*)r, in Haskell one binds fields of data structures to formal parameters via pattern matching.

During the course of learning Haskell, I come to the feeling that Scheme is the assembly language for functional programming comparing with Haskell (or ML and the like) in the sense that assembly languages are low-level comparing to C or even C++ in the imperative languages world.

Saying Scheme is a low-level language by no means implies that Scheme is a bad functional language. No. I thought and still believe that Scheme is the one of the most elegant programming language in the world. Just as learning an assembly language will help make one a better C programmer, learning Scheme will get one closer to the underlying computation model (Lambda Calculus) that underpins all functional programming languages, so that one can distinguish the essentials from the non-essentials and don't get lost in the complex constructs offered by a modern language like Haskell (However, I do think typing is something essential but totally missing in Scheme).

All I am saying is that Scheme remains as a good (perhaps the best) programming language for educational purpose, but for real-world product development, Haskell (or the ML family) is probably a better candidate.

P.S.:

Philip Walder has a paper discussing the merit of statically typed, lazy functional programming languages (KRC/Miranda) over dynamically typed, eager evaluation languages (Scheme/Lisp). An enlightening reading.