Melding Monads

2009 June 22

Control.Monad.Queue

Filed under: continuations, corecursion, haskell, monads, queues — lpsmith @ 8:41 pm

Haskell aficionados, take note! My library for corecursive queues has now been uploaded to Hackage. You can now cabal-install it.

I also have a substantially revised draft of the associated paper, Lloyd Allison’s Corecursive Queues, available. It has been re-organized so that it is hopefully easier to follow, it includes a careful performance comparison, and a tentative proof that mapCont cannot be expressed in terms of callCC, (>>=), return.

The library includes a somewhat crude micro-benchmarking program in the tests/ directory. Those who have read previous drafts, be warned that the few brief statements about performance were based on past notes, and I found some several issues with the testing methodology contained in the notes. Here the revised results:

Description Time (ms) -H500M Bytes allocated
GHC 6.10.3 mean σ mean σ per Branch
levelOrder’ 446 5 172 15 44.0
CorecQ 555 5 619 4 133.5
CorecQW _ 696 5 1128 6 213.6
CorecQW () 907 56 2235 11 213.6
Side Channel _ 959 3 1171 7 228.7
Side Channel () 1500 56 2171 7 276.4
STQ 1140 8 1087 14 371.2
TwoStack 1158 4 778 10 185.8
Okasaki 1553 7 1574 12 209.0
Data.Sequence 962 5 1308 5 348.1
GHC 6.8.3
levelOrder’ 461 2 173 15 44.1
CorecQ 458 4 267 13 67.5
CorecQW _ 526 5 713 5 141.2
CorecQW () 781 62 1775 62 141.3

These benchmarks come from performing breadth-first traversals repeatedly on the 34th fibonacci tree, on an Intel Core 2 Duo T9550. The first few data points were discarded, and the mean and standard deviation of the remaining times were computed. Note that getCPUTime was used to time each run, and this has a resolution of only 10 milliseconds.

If you would like to play with the queue transformer, which doesn’t appear in the library, or other bits of code exactly as they appear in the paper, you can download the source code here.

2009 May 3

Rocky’s Boots

Filed under: haskell — lpsmith @ 10:39 am

I ran across Logicly today, which is a Flash-based logic gate simulator. While it’s all very slick, I found it disappointing. It’s a mere shadow of Rocky’s Boots for the Commodore 64. The key differences are that Rocky’s Boots had D-flip flops, SR-latches, and simulated propogation delays, giving rise to glitches and hazards. While Logicly seems to handle self-reference somewhat well, enabling you to build your own flip flops, it doesn’t support any kind of abstraction so the overall support for sequential circuits is poor. (edit: Josh has added propagation delays, check it out!)

I could wax nostalgic about Rocky’s Boots; it was among my favorites when I was growing up, but I’ll spare you, dear readers. Truth be told, much like vintage BASIC, RB has a truly wretched user interface by modern standards, something that became painfully clear when I strolled through Rocky’s Boots a few years ago on a whim. I started into its sequel, Robot Odyssey, which I never got to play as a kid, but I didn’t get far due to the user interface.

Maybe Josh has plans for improving Logicly, I don’t know. Truth be told; it really is a travesty that Rocky’s Boots has not been remade and re-imagined many times over the last 27 years. At least it appears that Robot Odyssey has been remade a few times: here is a Java version that stays much too faithful to the original, down to replicating the same wretched interface. On the other hand, Gate seems reasonably promising… but it doesn’t appear to simulate propogation delay (then again, did Robot Odyssey?), nor does it have abstraction mechanisms like Robot Odyssey did.

So, if one was to remake Rocky’s Boots and/or Robot Odyessy, how would you do it? Might you use Functional Reactive Programming? How efficient would this be, and how large of a circuit could this handle? Could you make good use of modern SIMD and/or multiple cores? Although I daresay reaching children would be a particularly good goal for such a project, thus delivering it as Flash has definite appeal.

2009 April 7

Polynomial multiplication

Filed under: algorithms, corecursion, haskell — lpsmith @ 6:27 am

Alright, it’s been almost a month since I’ve last posted, and I wanted to post weekly. Perhaps bi-weekly would be a better goal, as long as I really can stick to it.

So, a few months ago, while working on a combinatorial problem for Project Euler, I was re-implementing polynomial arithmetic, and made an interesting observation. I was using a sparse list representation, with each element of the list being (M c k), representing the monomial cxk.

> data Mono = M !Integer !Integer  deriving (Eq, Ord, Show)

A polynomial is represented by a list of monomials, which is assumed to be sorted in ascending order of the power k above, and every power is assumed to be unique in our representation. Thus we can easily define addition and subtraction using standard techniques for dealing with ordered lists:

> mergeBy :: (Integer -> Integer -> Integer) -> [Mono] -> [Mono] -> [Mono]
> mergeBy f xs ys = loop xs ys
>   where 
>     loop [] ys = ys
>     loop xs [] = xs
>     loop (M c0 k0:xs) (M c1 k1:ys) 
>            = case compare k0 k1 of
>                LT -> M c0 k0 : loop xs (M c1 k1:ys)
>                EQ -> let c' = f c0 c1
>                       in if c' == 0 
>                           then loop xs ys
>                           else M c' k0 : loop xs ys
>                GT -> M c1 k1 : loop (M c0 k0:xs) ys

> add = mergeBy (+)
> sub = mergeBy (-)

It’s also very straightforward to multiply two monomials, and to perform a “scalar” multiplication of a single monomial with a polynomial. Note that the degree of each term is changed by a constant amount, so we don’t have to worry about re-ordering the list, and that the first case of smul is a completely optional minor optimization.

> mmul (M c0 k0) (M c1 k1) = M (c0 * c1) (k0 + k1)

> smul (M 1 0) ys = ys
> smul x ys = map (mmul x) ys

Taking into account the possibility of polynomials with an infinite number of terms, it’s now fairly easy to implement a polynomial multiplication program in terms of add and mmul:

> pmul _  []    = []
> pmul [] (_:_) = []
> pmul (x:xs) (y:ys) = mmul x y : add (smul x ys) (pmul xs (y:ys))

This is based around the algebraic identity (x + xs) * (y + ys) == x * y + x * ys + xs * (y + ys). It works on infinite polynomials because x and y are the terms of least degree to be multiplied, and every other product will have a higher degree. Unfortunately, this code turns out to be hopelessly inefficient.

The second thing I tried was simply changing the order in which arguments are passed to the recursive call to pmul:

> pmul2 _  []    = []
> pmul2 [] (_:_) = []
> pmul2 (x:xs) (y:ys) = mmul x y : add (smul x ys) (pmul2 (y:ys) xs)

Empirically, this is asymptotically faster than the first attempt. I do not know why. Any insight would be fun to read about!

2009 March 9

Lloyd Allison’s Corecursive Queues

Filed under: continuations, corecursion, haskell, monads, queues — lpsmith @ 9:34 pm

I’m proud to announce that a draft of the release of my paper, “Lloyd Allison’s Corecursive Queues: Why Continuations Matter“, is now available. (Source code available here, with a hackage package soon to come available here) Wouter Swierstra has informed me that he will publish it in the Monad Reader. However, it will appear in the next issue after the upcoming one, due to an unexpectedly large number of submissions this time around. Here is the abstract:

In a purely functional setting, real-time queues are traditionally thought to be much harder to implement than either real-time stacks or amortized O(1) queues. In “Circular Programs and Self-Referential Structures,” Lloyd Allison uses corecursion to implement a queue by defining a lazy list in terms of itself. This provides a simple, efficient, and attractive implementation of real-time queues.

While Allison’s queues are general, in the sense it is straightforward to adapt his technique to a new algorithm, a significant problem has been the lack of a reusable library implementation. This paper solves this problem through the use of a monadic interface and continuations.

Because Allison’s queues are not fully persistent, they cannot be first class values. Rather, they are encoded in particular algorithms written in an extended continuation passing style. In direct style, this extension corresponds to mapCont, a control operator found in Control.Monad.Cont, part of the Monad Template Library for Haskell. This paper conjectures that mapCont cannot be expressed in terms of callCC, return, and (>>=).

I intend to include a careful performance comparison before this becomes an official Monad Reader article. Allison’s queues come out very well; often better than two stack queues. I have conducted a careful performance comparison in the past, although with older versions of GHC, and older versions of my code. While I did take reasonably careful notes, things have changed. Haskell being what it is, figuring out why is often a challenge. In the meantime I am interested in feedback.

For fun, here is something I wrote right after I first came up with the basic idea behind the paper. It’s still the best error message I’ve gotten out of GHC. Kudos to whomever came up with that strategically placed bit of humor!

Thursday, August 25th, 2005, 5:22 am: Back to the Future

I’ve been up all night, but I now have a working fragment of computer code that is entirely too cute. It’s easily the cleverest bit I’ve written in years. I managed to implement… a queue.

Yes, a queue. One queue, not two. One purely functional queue, with one esoteric implementation! On my penultimate attempt, which was an utter failure except that it got me thinking in the right direction, I came by the most amusing error message I’ve seen to date out of GHC:

leon@deleon:~/Programs/snippets $  ghci -fglasgow-exts Queue.hs 
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.2.2, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Compiling Queue            ( Queue.hs, interpreted )

Queue.hs:84:
    My brain just exploded.
    I can't handle pattern bindings for existentially-quantified constructors.

...

Failed, modules loaded: none.
Prelude>

Yeah, mine did too. Even I don’t fully understand my own code yet.

It should be noted that I knew full well that the code I was trying wouldn’t work… but after hours of bewilderment, not even trying to load anything into GHCi, for amusement’s sake I simply had to try something.

Update: (March 23)
— Data.Sequence is not a real time queue: rather, they are amortized.
— Added citation to Chris Okasaki’s Purely Functional Data Structures
— Other minor changes

« Newer Posts

Create a free website or blog at WordPress.com.