Haskell Scheme Python -Be a programmer for a lifetime

Wednesday, 7 November 2007

Syntax highlighting test

Finally I start to blog.

The main reason is that I'm learning Haskell and I need help. I have programmed in Python for about half a year and recently start to learn Scheme and Haskell. I will post code in these languages and if you think there's anything can be improved, just kindly drop me a line. Thanks in advance.

After reading Luke's greate article, I decide write articles in reStructuredText and use Pygments to highlight source code. This very first post is also act as a test that to see if everything works well. So let's have some fun with the factorial function.

From Wang Yin's Schemer page:

(define Y
(lambda (F)
(let ((W (lambda (x)
(F (lambda arg (apply (x x) arg))))))
(W W))))

(define fac
(lambda (fun)
(lambda (n)
(if (= 0 n) 1 (* n (fun (- n 1))))))))

My translation to Python:

Y = lambda F: (lambda x: F(lambda *args: x(x)(*args)))(lambda x: F(lambda *args: x(x)(*args)))
fac = Y(lambda fun: lambda n: n and n*fun(n-1) or 1)

From The Evolution of a Haskell Programmer:

-- a dynamically-typed term language

data Term = Occ Var
| Use Prim
| Lit Integer
| App Term Term
| Abs Var Term
| Rec Var Term

type Var = String
type Prim = String

-- a domain of values, including functions

data Value = Num Integer
| Bool Bool
| Fun (Value -> Value)

instance Show Value where
show (Num n) = show n
show (Bool b) = show b
show (Fun _) = ""

prjFun (Fun f) = f
prjFun _ = error "bad function value"

prjNum (Num n) = n
prjNum _ = error "bad numeric value"

prjBool (Bool b) = b
prjBool _ = error "bad boolean value"

binOp inj f = Fun (\i -> (Fun (\j -> inj (f (prjNum i) (prjNum j)))))

-- environments mapping variables to values

type Env = [(Var, Value)]

getval x env = case lookup x env of
Just v -> v
Nothing -> error ("no value for " ++ x)

-- an environment-based evaluation function

eval env (Occ x) = getval x env
eval env (Use c) = getval c prims
eval env (Lit k) = Num k
eval env (App m n) = prjFun (eval env m) (eval env n)
eval env (Abs x m) = Fun (\v -> eval ((x,v) : env) m)
eval env (Rec x m) = f where f = eval ((x,f) : env) m

-- a (fixed) "environment" of language primitives

times = binOp Num (*)
minus = binOp Num (-)
equal = binOp Bool (==)
cond = Fun (\b -> Fun (\x -> Fun (\y -> if (prjBool b) then x else y)))

prims = [ ("*", times), ("-", minus), ("==", equal), ("if", cond) ]

-- a term representing factorial and a "wrapper" for evaluation

facTerm = Rec "f" (Abs "n"
(App (App (App (Use "if")
(App (App (Use "==") (Occ "n")) (Lit 0))) (Lit 1))
(App (App (Use "*") (Occ "n"))
(App (Occ "f")
(App (App (Use "-") (Occ "n")) (Lit 1))))))

fac n = prjNum (eval [] (App facTerm (Lit n)))

It seems that everything works quite well. Thanks again, Luke! The color schemer is from Emacs color theme test.

I'm currently working on the Ball Clock puzzle. I have worked out the Python version, but write it in Haskell is hard for me (It's my first Haskell program!). As soon as I finish, I'll post them. You may look at the puzzle first. See you next time!

No comments: