Greg Buchholz's blog

Search by Type

Submitted by Greg Buchholz on Mon, 12/05/2005 - 12:37pm.
Here's a random thought. What if we had a way to search for Haskell functions by type signature. Take the Hierarchical Libraries, slice/dice/index the type signatures so that you could search for "Num b => a -> b" and it would present you with a list of functions like length :: [a] -> Int. You'd also probably want to allow swizzling of the input arguments so that you could find "map" with a search like "[a] -> (a -> b) -> [b]". Then the next step would be to analyze your existing code to see if you've reinvented any wheels.

Quantum Programming

Submitted by Greg Buchholz on Fri, 12/02/2005 - 4:48pm.

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?

Submitted by Greg Buchholz on Fri, 11/11/2005 - 4:36pm.

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

Submitted by Greg Buchholz on Thu, 10/20/2005 - 2:46pm.

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

Submitted by Greg Buchholz on Thu, 10/20/2005 - 2:23pm.

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