Greg Buchholz's blog

Search by Type

Quantum Programming

Lately I've been pondering the programming of quantum computers. Just because we don't have the hardware yet seems like an awfully bad excuse for not having languages and emulators/simulators. I really don't know much about quantum computing (book recommendations anyone?), but it seems to be based on a somewhat nondeterministic model. Is it going to be like programming in Prolog, but with backtracking that doesn't cost anything in terms of efficiency? Curious.

Do lispers use macros often?

Do lispers use macros often, or is that a misconception? I don't know, but here's one data point. Since Peter Seibel's book Practical Common Lisp is online, I thought I'd do a little investigation. With a little wget, lynx, and perl magic I analyzed the word frequency of the book. The word "macro" or one of its forms (such as macrophobic and macrophobia) occur 810 times. For reference, here are the words which occur more often...

• 854 => 1
• 875 => name
• 876 => or
• 914 => an
• 944 => code
• 949 => list
• 951 => are
• 1033 => by
• 1114 => t
• 1126 => if
• 1261 => lisp
• 1279 => value
• 1337 => function
• 1351 => be
• 1402 => this
• 1532 => as
• 1609 => can
• 1700 => with
• 1781 => for
• 1963 => it
• 2433 => is
• 2583 => that
• 3329 => in
• 3452 => and
• 3836 => you
• 4774 => of
• 5951 => a
• 5970 => to
• 12616 => the

*Note: For the record, I personally love macros. Well, appropriate macros. Reinventing a new language syntax should be a fairly rare event. A nice language will be built from a relatively small set of powerful axioms which will preclude the need to invent new axioms all the time. Certainly "until" isn't a good example of when they should be used.

Computer Assisted Programming

Thought I'd post a link to one of my static typing rants, since there will probably be more "true believers" on this site.

dy/dx

Over on comp.lang.lisp we have someone trying to use Haskell for a little symbolic differentiation problem. Since it doesn't even compile, I thought I'd throw my hat in the ring and clean it up a little (Is there a better way to display snippets on this site? I had to use <pre> tags instead of <code> tags)...

infixl 5 :+
infixl 6 :*
data Exp = Num Integer
         | Var Sym
         | Exp :+ Exp
         | Exp :* Exp deriving (Eq,Show)

data Sym = X | Y deriving (Eq,Show)

main = do let exp = (Num 4 :* Var X :* Var X)
          let deriv = d exp X
          putStrLn $ "Original expression : " ++ (show exp)
          putStrLn $ "Derivative : " ++ (show $ simplify deriv)
          putStrLn $ "Derivative evaluated at X=10 : "
                     ++ (show $ eval (d exp X) [(X,10)])

--take the derivative...
d (Num n)  x = Num 0
d (Var y)  x | x==y      = Num 1
             | otherwise = Num 0 
d (f :+ g) x = (d f x) :+ (d g x)
d (f :* g) x = (d f x) :* g :+ f :* (d g x)

--evaluate an Exp...
eval (Num x) env = x
eval (Var x) env = case (lookup x env) of 
                        (Just n)  -> n
                        (Nothing) -> error $ "no variable "++(show x)++" in env"
eval (x :+ y) env = eval x env + eval y env
eval (x :* y) env = eval x env * eval y env

--a few algebraic simplification rules
simp (x :+ y) | x == y = simp (Num 2):*x
simp ((Num 0) :+ x) = simp x
simp (x :+ (Num 0)) = simp x
simp ((Num x) :+ (Num y)) = Num (x+y)
simp (x :+ y) = simp x :+ simp y
simp ((Num 0) :* x) = Num 0
simp (x :* (Num 0)) = Num 0
simp ((Num 1) :* x) = simp x
simp (x :* (Num 1)) = simp x
simp ((Num x) :* (Num y)) = Num (x*y)
simp (x :* y) = simp x :* simp y
simp x = x

--apply simplification rules until the expression doesn't change anymore
simplify x = let a = iterate simp x
                 fix = dropWhile (\(c,d)->c/=d) $ zip a (tail a)
             in (fst.head) fix