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.

Haskell is not an academic toy, but it is not corporate ready either

Submitted by metaperl on Sat, 11/05/2005 - 6:15am.

Today in #haskell, Sylvan said that Haskell had a reputation as an academic toy and that books should start off with Monadic I/O and other "practical" concerns to eliminate that stereotype.

Cale responded by saying that GHCi's REPL provided adequate I/O facilities.

I responded by saying that the most practical thing you could do in learning Haskell is to obtain the ability to decompose a problem into a set of functions. Everything else about Haskell follows from pure lazy functions and until you are comfortable and conversant in this paradigm, you really can't develop any new and useful code. You will simply be an ignorant little monkey, aping things you saw in a tutorial which crippled your ability to analyze and synthesize strongly-typed, lazy functions.

I did not say this then, but I also have this response. The impression of Haskell will not change with another book with practical examples. It will only change when Haskell has huge corporate-ready libraries for every huge corporate issue: when Haskell has a CPAN locked and loaded and ready to go. When Haskell has something as widely used as Mailman. When every website you see is done with Haskell instead of PHP. When you can deploy CORBA apps with Haskell. When you can cache and pre-compute queries for a SQL database in Haskell. When you have the speed and flexibility and eager persistent data loading of mod_perl for Haskell. When you have the best or second best or third best or any high-quality fully functional efficient streaming media player sitting on everyone's Linux desktop. When the favorite free drawing program is written in Haskell. For Haskell equating CPAN. CGI has been a web standard for almost 10 years. Try matching the real-world ready-to-go functionality of - that's one CPAN module in the Perl toolbox. Just one. Then you have 4000 more to go.

Haskell is the most beautiful, elegant, and correctly designed programming language on this planet. It is also the most powerful at chopping apart new specs and writing reliable code in short periods of time - how else could it stomp every other language 2 years in a row in the ICFP? But the only way to remove an impression is with results - tangibles, deliverables and unfortunately the focus on beauty, elegance and correctness seems to get in the way of ever getting anything corporate-ready out the door.

I am grateful to be studying Haskell. It has done wonders for my corporate-level Perl development. The book to read is "The Haskell Road to Logic, Maths and Computer Programming." This book will force you to think clearly. It does not cover monads, but monads can wait until you can specify and solve problems. But my improved thought processes are one thing. Delivering projects on a deadline is another and Perl continues to deliver through a cooperative community based around CPAN. The Haskell community is based around the reason of masterminds doing the intelligent things. The Perl community is based around the needs of people doing practical things in the best way that they can.

Finally, getting corporate ready is not something you can plan. It happens. It happens by necessity. It happens when someone has to swim or sink.

Deriving the function to compute sublists of a list

Submitted by metaperl on Wed, 10/26/2005 - 12:42pm.

Earlier I discussed how = in Haskell is equational. Well, it certainly came to the rescue this time. I was trying to understand the given solution in "The Haskell Road to Logic, Maths, and Programming" for the problem of calculating all the sublists of a list.

powerList [] = [ [] ]
powerList (x:xs) = powerList xs ++ (map (x:) powerList xs)

So I looked at this program, but had no idea how in the world this was the solution. So what I did is I worked upwards from the most trivial case like so:

-- The powerlist of a list with no elements is a list consisting of
-- the empty list

powerList [] = [[]]

-- Now, let's work with a list with 1 element:

powerList [a] = [ [a], [] ]

-- Fair enough, now how about a list with 2 elements:

powerList [a,b] = [ [a,b], [b], [a], [] ]

-- Hmm, but let's rewrite that

[ [a,b], [b], [a], [] ] = powerList [a] ++ [ [a, b], [b] ]

-- And rewrite once again

powerList [a] ++ [ [a, b], [b] ] = powerList [a] ++ (map (b:) powerList [a])

-- Now let's try 3 elements just to make sure we have a pattern:

powerList [c,a,b] = [[c,a,b], [c,b], [c,a], [c]] ++ powerList [a,b]

-- but with order independance we have:

powerList [c,a,b] = powerList [a,b] ++ [[c,a,b], [c,b], [c,a], [c]]

-- but [[c,a,b], [c,b], [c,a], [c]] = map (c:) powerList [a,b] so:

powerList [c,a,b] = powerList [a,b] ++ map (c:) powerList [a,b]

-- generalizing we have:

powerList (x:xs) = powerList xs ++ (map (x:) powerList xs)

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.


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

Were there any bitter battles in the design of Haskell?

Submitted by metaperl on Sun, 10/16/2005 - 8:02pm.

I find it hard to believe that a language designed by committee did not have bitter furious fights over some issues in the language. Then again, I suppose the design goals with Haskell were fairly clear. Purely functional, types because they are necesary. Laziness because it fits with pure functions. End of discussion!

By the way, I have to comment that the Haskell community is so much friendlier than Perl.

Why is Clean faster than Haskell?

Submitted by metaperl on Sun, 10/09/2005 - 4:21pm.

If you compare Clean and Haskell in the Debian shootout, Clean is consistently faster than Haskell. These languages are spitting images of each other, save that Clean has some way of avoiding Monads. In addition, Clean I believe is based on graphs instead of lambda calculus - but both of these compute the same things so why would that matter?

The summary table (at bottom, horribly rendered in Firefox), shows Clean winning 10-0.

Also, which language came first? Clean or Haskell?

that's enough of SJT

Submitted by metaperl on Sun, 10/09/2005 - 2:20pm.

i'm tired of beating around the bush. i have played with not being able to think long enough.

learning haskell is not an obligation for me. it is a hobby. i can't ever expect it to compete with C++ in terms of popularity. I chose haskell because it forces you to think clearly. I need to see this as a hobby which might become a profitable job one day... Perl did. Haskell might as well. Haskell is gaining corporate attention. Microsoft has always had its eye on it.

better to master something I like than to keep rushing through this book. Funny "The Haskell Road..." does not cover monads, but I feel confident I will be able to handle them if/when I make it through Doets/van Eijck's book.

instance Read a, given a Parsec parser

Submitted by dtlin on Fri, 10/07/2005 - 1:46pm.

Given any type a, for which there exists an parsecRead :: Parser a, the instance Read a can be defined really easily.
But I didn't find it in the Parsec docs.  Maybe I wasn't looking hard enough.

{- This code is dedicated to the public domain. -}
import Text.ParserCombinators.Parsec
class ParsecRead a where
  parsecRead :: Parser a
instance (ParsecRead a) => Read a where
  readsPrec _ = either (const []) id . parse parsecRead' "" where
    parsecRead' = do a <- parsecRead
                     rest <- getInput
                     return [(a, rest)]

It could be used like this:
data Foo = Foo
instance ParsecRead Foo where
  parsecRead = string "foo" >> return Foo
-- instance Read Foo

Defining instance Read a requires GHC's -fallow-undecidable-instances, though.
Well, you could always just repeat the readsPrec definition for everything you want, but it seems to me that this should exist just because it's convenient and common enough.