Sound and Software

J. Roger Hindley is coming to Maynooth

2011-10-11T13:34:00.000+01:00

I have recently learned that J. Roger Hindley (of Hindley-Milner) will be giving a talk next month on the history of Curry-Howard in the Mathematics Dept. at NUI Maynooth. I will definitely be there!

splaytree package released

2011-09-16T23:39:00.000+01:00

I've just uploaded a new package to Hackage, splaytree-0.1. Splaytree provides pure functional splay trees, implemented using monoidal annotations. A splay tree is a self-balancing tree with the property that recently-accessed nodes remain near the root, and thus subsequent accesses can be quite cheap. As for the monoid annotations, it's the same technique as used in finger trees (see here, here, and here). The idea is that each node of a tree holds an annotation in addition to data. If the type of the annotation is chosen properly, it can be used to prune branches when searching. One clever aspect of this technique is that different data structures can be implemented simply by choosing different annotations.

Currently three different data structures are available, Data.SplayTree.Set, Data.SplayTree.Seq, and Data.SplayTree.RangeSet. 'Set' provides a set with standard operations. Not much time has been spent optimizing this library, but performance is competitive with unordered-containers for many operations (inserts can be quite slow though). Seq is a sequence type, similar to Data.Seq.

RangeSet is perhaps the most interesting of the available containers. Similar to an IntervalSet, a RangeSet is used for storing a list of Ranges. A RangeSet, however, guarantees that all ranges are non-overlapping. When a new range is inserted into the RangeSet, it is combined with any ranges currently in the set with which it overlaps.

Example (Note that a Range is a starting point and duration):


Prelude Data.SplayTree.RangeSet Data.Foldable> let rs = singleton (range 0 4)
Prelude Data.SplayTree.RangeSet Data.Foldable> toList rs
[Range {rMin = 0, rang = 4}]
Prelude Data.SplayTree.RangeSet Data.Foldable> toList $ insert rs (range 3 2)
[Range {rMin = 0, rang = 5}]
Prelude Data.SplayTree.RangeSet Data.Foldable>

Comments and patches welcome.

My mind is blown

2011-09-02T13:00:00.000+01:00

Recently I've read two blog posts which have really started to change how I think about programming. A while ago I found a solution to the word numbers problem which completely stunned me with its simplicity and generality. Today I stumbled upon Apfelmus's "monoids and finger trees" blog post, which is very timely since I can use the same approach to both simplify and generalize a data structure I've been working on recently.

With this in mind, I would like to move from my current awareness (being able to follow along with these discussions) to being able to recognize and apply very general structures. Somewhat tongue-in-cheek, I'd like to know how to make good use of Edward Kmett's packages. Advice would be appreciated.

Circular Buffers

2011-07-06T21:09:00.002+01:00

An extremely useful tool in DSP programming is the circular buffer. Basically, a circular buffer is useful for keeping an array of n elements of a data stream. Implementing this in Haskell is not straightforward, because the usual implementation relies upon mutating arrays. As Haskell is a pure language, mutable data can only be used in restricted contexts, which can make a mutable circular buffer somewhat awkward. It offends my sensibilities if nothing else.

(Code presented in this article is basically the first thing I thought of. Improvements are welcome, provided they don't detract too much from readability. All code is placed in the public domain.)

The ideal Haskell implementation would be pure, and for certain cases a high-performance solution is available. If you only need access to the end of the buffer (i.e. a FIFO queue), real-time pure functional implementations are well-known (Okasaki). But what if you want to read from the middle of the buffer? In an imperative implementation, this is usually handled by either keeping multiple read pointers, or by using an absolute offset to the start of the buffer. It's not clear how to apply either of these techniques to Okasaki's queue implementation though, and the obvious approach of dequeueing as many times as required has O(n) complexity.

An obvious approach is to write an implementation using mutable data. The implementation would no longer be pure unfortunately. Here's a simple implementation which runs in IO, based upon mutable vectors:


module Data.RingBuffer.Mutable (
  RingBuffer
 ,newInit
 ,push
 ,length
 ,(!)
)

where

import qualified Data.Vector.Unboxed.Mutable as V

import Foreign.ForeignPtr
import Foreign.Storable
import Control.Applicative
import GHC.Prim

data RingBuffer a = RB (V.MVector RealWorld a) (ForeignPtr Int)

newFp :: Storable a => a -> IO (ForeignPtr a)
newFp a = do
  fp <- mallocForeignPtr
  withForeignPtr fp $ \p -> poke p a
  return fp

readFp :: Storable a => ForeignPtr a -> IO a
readFp fp = withForeignPtr fp $ \p -> peek p

writeFp fp a = withForeignPtr fp $ \p -> poke p a

newInit :: (V.Unbox a, Num a) => Int -> IO (RingBuffer a)
newInit sz = RB <$> (V.replicate sz 0) <*> newFp 0
{-# INLINE newInit #-}

(!) :: (V.Unbox a) => RingBuffer a -> Int -> IO a
(!) (RB vec ref) ix = do
  off <- readFp ref
  let len = V.length vec
  V.unsafeRead vec ((ix+off) `rem` len)
{-# INLINE (!) #-}

push :: V.Unbox a => RingBuffer a -> a -> IO ()
push (RB vec ref) el = do
  off <- readFp ref
  let len = V.length vec
  let off' = (off+1) `rem` len
  writeFp ref off'
  V.unsafeWrite vec off el
{-# INLINE push #-}

So what would an efficient pure implementation look like?

Probably the fanciest pure data structure is the finger tree, most commonly known by the implementation in Data.Sequence.Seq. Finger trees have many interesting attributes, including O(1) access to both ends. They do not have O(1) access to interior elements, but better than O(n). It's pretty simple to implement a similar interface with a Seq:


module Data.RingBuffer (
  RingBuffer
 ,new
 ,newInit
 ,push
 ,length
 ,(!)
)

where

import           Prelude hiding (length)

import qualified Data.Sequence as S

newtype RingBuffer a = RB (S.Seq a) deriving (Eq, Ord, Show)

-- | Create a new RingBuffer, initialized to all 0's, of the given size
new :: (Num a) => Int -> RingBuffer a
new = newInit 0
{-# INLINE new #-}

-- | Create a new RingBuffer from a given initial value
newInit :: a -> Int -> RingBuffer a
newInit i sz | sz <= 0 = error "can't make empty ringbuffer"
newInit i sz           = RB (S.replicate sz i)
{-# INLINE newInit #-}

-- | Get the total size of a RingBuffer.
length :: RingBuffer a -> Int
length (RB vec) = S.length vec
{-# INLINE length #-}

-- | Look up a value in a RingBuffer.
(!) :: RingBuffer a -> Int -> a
(!) (RB vec) = S.index vec
{-# INLINE (!) #-}

-- | Push a new value into a RingBuffer.  The following will hold:
--     NewRingBuffer ! 0 === added element
--     NewRingBuffer ! 1 === OldRingBuffer ! 0
push :: RingBuffer a -> a -> RingBuffer a
push (RB vec) el   = case S.viewr vec of
  v' S.:> _ -> RB $ el S.<| v'
  _         -> error "internal error"
{-# INLINE push #-}

Ok, so it's not quite the same, but close enough.

So how does this compare, performance-wise? I whipped up some criterion code to check it out.


module Main where

import Criterion.Main
import System.Random
import Control.Monad

import qualified Data.RingBuffer.Mutable as RM
import qualified Data.RingBuffer as R
import Data.Vector.Unboxed (Unbox)
import System.IO.Unsafe

rndSeed = 49872

-- test performance as a queue
queueMut :: (Unbox a, Num a) => Int -> Int -> a -> IO ()
queueMut reps sz a = do
  buf <- RM.newInit sz
  replicateM_ reps (buf RM.! (sz-1) >> RM.push buf a)

-- | test performance of multiple reads
multireadMut :: (Unbox a, Num a) => Int -> Int -> a -> IO ()
multireadMut nReads sz a = do
  let rs = take nReads $ randomRs (0,sz-1) $ mkStdGen rndSeed
  buf <- RM.newInit sz
  replicateM_ iters $ do
    mapM_ (\ix -> buf RM.! ix) rs
    RM.push buf a

queueP :: Int -> Int -> a -> a
queueP reps sz a = fst $ (iterate go (a, R.newInit a sz)) !! reps
 where
  go (a', buf) = a' `seq` (buf R.! (sz-1), R.push buf a)

multireadP :: Int -> Int -> a -> [a]
multireadP nReads sz a = fst $ (iterate go (replicate nReads a, R.newInit a sz)) !! iters
 where
  go (last, buf) = length last `seq` (map (buf R.!) rs, R.push buf a)
  rs = take nReads $ randomRs (0,sz-1) $ mkStdGen rndSeed
  

numReps = 100
numReads = 50

iters = 10000

main = defaultMain
  [
   bgroup "Mutable/Int" [
     bgroup "Queue" [
       bench "8"      $ queueMut numReps 8     (10::Int)
      ,bench "128"    $ queueMut numReps 128    (10::Int)
      ,bench "1024"   $ queueMut numReps 1024   (10::Int)
      ,bench "10240"  $ queueMut numReps 10240  (10::Int)
      ,bench "102400" $ queueMut numReps 102400 (10::Int)
     ]
     ,bgroup "Multiread" [
       bench "8"     $ multireadMut numReads 8     (10::Int)
      ,bench "128"    $ multireadMut numReads 128    (10::Int)
      ,bench "1024"   $ multireadMut numReads 1024   (10::Int)
      ,bench "10240"  $ multireadMut numReads 10240  (10::Int)
      ,bench "102400" $ multireadMut numReads 102400 (10::Int)
      ]
   ]
  ,bgroup "Mutable/Double" [
     bgroup "Queue" [
       bench "8"     $ queueMut numReps 8     (10::Double)
      ,bench "128"    $ queueMut numReps 128    (10::Double)
      ,bench "1024"   $ queueMut numReps 1024   (10::Double)
      ,bench "10240"  $ queueMut numReps 10240  (10::Double)
      ,bench "102400" $ queueMut numReps 102400 (10::Double)
     ]
     ,bgroup "Multiread" [
       bench "8"     $ multireadMut numReads 8     (10::Double)
      ,bench "128"    $ multireadMut numReads 128    (10::Double)
      ,bench "1024"   $ multireadMut numReads 1024   (10::Double)
      ,bench "10240"  $ multireadMut numReads 10240  (10::Double)
      ,bench "102400" $ multireadMut numReads 102400 (10::Double)
     ]
   ]
  ,bgroup "Pure/Int" [
     bgroup "Queue" [
       bench "8"     $ whnf (queueP numReps 8)     (10::Int)
      ,bench "128"    $ whnf (queueP numReps 128)    (10::Int)
      ,bench "1024"   $ whnf (queueP numReps 1024)   (10::Int)
      ,bench "10240"  $ whnf (queueP numReps 10240)  (10::Int)
      ,bench "102400" $ whnf (queueP numReps 102400) (10::Int)
     ]
     ,bgroup "Multiread" [
       bench "8"     $ nf (multireadP numReads 8)     (10::Int)
      ,bench "128"    $ nf (multireadP numReads 128)    (10::Int)
      ,bench "1024"   $ nf (multireadP numReads 1024)   (10::Int)
      ,bench "10240"  $ nf (multireadP numReads 10240)  (10::Int)
      ,bench "102400" $ nf (multireadP numReads 102400) (10::Int)
     ]
   ]
  ,bgroup "Pure/Double" [
     bgroup "Queue" [
       bench "8"     $ whnf (queueP numReps 8)     (10::Double)
      ,bench "128"    $ whnf (queueP numReps 128)    (10::Double)
      ,bench "1024"   $ whnf (queueP numReps 1024)   (10::Double)
      ,bench "10240"  $ whnf (queueP numReps 10240)  (10::Double)
      ,bench "102400" $ whnf (queueP numReps 102400) (10::Double)
     ]
     ,bgroup "Multiread" [
       bench "8"     $ nf (multireadP numReads 8)     (10::Double)
      ,bench "128"    $ nf (multireadP numReads 128)    (10::Double)
      ,bench "1024"   $ nf (multireadP numReads 1024)   (10::Double)
      ,bench "10240"  $ nf (multireadP numReads 10240)  (10::Double)
      ,bench "102400" $ nf (multireadP numReads 102400) (10::Double)
     ]
   ]
  ]

A few points about the benchmarks. First, both queue and multiread perform multiple cycles in each benchmark. Secondly, the pure benchmarks both seq outputs at each cycle to ensure that work is actually performed. So how do these implementations compare?

It looks like not only is the Seq-based implementation pure, it outperforms my mutable-vector implementation and scales better too. Completely unexpected.

Unless somebody points out a major flaw in my testing methodology or implementations, I'll be using Data.Sequence.Seq for my circular buffer needs from now on.

Benchmark data

Edit: thanks to Henning Thielemann for suggested improvements. I've updated the benchmark code with his suggestions regarding mkStdGen. I also have updated the mutable buffer to use a ForeignPtr to hold the offset rather than an IORef. The performance is better, but not drastically so. I haven't put up new images yet, although I have uploaded the new benchmark data.

Linux Audio Conference 2011

2011-05-06T14:14:00.003+01:00

Streams are live now. Check it out if you couldn't make it in person.

http://streamer.stackingdwarves.net/

GTK on OSX

2011-05-05T01:20:00.000+01:00

I finally got tired of the default gtk theme on my macbook, so I decided to do something about it. I've been using gtk2 no_x11 variant provided by macports, but unfortunately all the theme engines on macports require X11. I tried the GtkQuartzEngine, and it seems to work perfectly with a little tweaking.

1. Check out git://github.com/jralls/gtk-quartz-engine.git
2. Cd into the gtk-quartz-engine repo and run aclocal && autoreconf -vi && autoconf (I used the macports versions)
3. ./configure --prefix=/opt/local && make && make install
4. Copy the sample gtkrc file to ~/.gtkrc-2.0.

And it all just worked. It looks decent, albeit slightly buggy. It's necessary to set the prefix to /opt/local so the engine is installed into the same location as the macports gtk libs.

This seems like a relatively simple candidate for adding to macports.

Thoughts on FRP

2011-04-11T13:18:00.000+01:00

(N.B. Code presented in this post is theoretical. I haven't tried to compile it, although I do expect it would work.)

Although various implementations have been under development for some time, FRP has yet to reach a really satisfying breakthrough. The best semantic model has been that of Conal Elliot's Reactive, but unfortunately it lacks a Smart Enough Compiler and suffers from subtle space leaks. The most performant is probably Yampa, which is arrow-based. Arrows turn some people off; I personally find them too verbose and don't like the syntax for recursion.

Apfelmus has recently released a new FRP library, reactive-banana, which shows some early promise towards being a best-of-all-possible-worlds. In this post I'll examine some of the features of reactive-banana to see why I think this.

Introduction

Reactive-banana is very similar to the semantic model provided by Reactive, although much more minimal. One fundamental data type is the Event, which can be thought of as a list of values with their time of occurrence, i.e. Event a = [(Time, a)]. The other fundamental type is the Behavior, which can be thought of as a value that changes with time, i.e. Behavior a = \Time -> a. This is according to the reactive-banana documentation, which also notes that in this implementation Behaviors aren't continuous but are actually step functions.

So how does it look? Consider a simple system with a button and a toggle: when the button is pressed it generates a 0 if the toggle is off, and 1 when the toggle is on. We could model it like this:


togEvent :: Event Bool
buttonEvent :: Event ()

-- Upon receiving an Event (), mixEvents generates an Event Int
-- The value of the Int depends upon the most recent Event Bool status
mixEvents :: Event Bool -> Event () -> Event Int

The togEvent and buttonEvent sources are created by connecting to the window framework's event system (see reactive-banana-wx for an example), but mixEvents is more complex. We could model it with the pure function


mixEventsF :: Bool -> () -> Int
mixEventsF True _ = 1
mixEventsF _    _ = 0

so we just need to find a way to lift this into the FRP system. Behaviors have an Applicative instance, so let's try it:


mixEvents = apply (mixEventsF <$> behavior False togEvent) buttonEvent

and we've got it. If we prefer, we could define mixEventsF :: Bool -> Int, but then we'd need to fmap const onto the Behavior to create a Behavior (() -> Int) we could apply to an Event.

So how does this work? The Behavior functions as an Event Accumulator. It stores every Bool received from togEvent, and when a button press event is received creates an event from applying the Bool and () to the mixEventsF function. One clue that this is the proper way to think of Behaviors is by the different ways they can be constructed:

lifting pure values, and always (these are semantically equivalent, pure is defined as always)
the behavior smart constructor (only hold the most recent Event)
various accumulate functions on Events

So if a Behavior is an event accumulator, why do we need it at all? Why not just use events directly, explicitly storing values when we need them? In my view, the answer has to do with abstracting implementation from the user.

Push vs Pull

One tension in the FRP design space relates to a push-driven (data-driven) vs pull-driven (demand-driven) architecture. Push-driven offer theoretically better performance, as data sources typically change relatively slowly (e.g. mouse clicks relative to screen refresh), so this minimizes recomputation. However, pull-driven seems to fit the functional paradigm better. Also, if a Behavior models a continuous function, pushing updates at the sample rate could be very wasteful.

The Behavior type (at least in reactive and reactive-banana) moderates between these two models. We can see how this works by examining the semantics of our mixEvents function.


-- Upon receiving an Event (), mixEvents generates an Event Int
-- The value of the Int depends upon the most recent Event Bool status
mixEvents :: Event Bool -> Event () -> Event Int

Our implementation created a Behavior (() -> Int) by combining a pure function with the Event Bool stream. This behavior is then sampled whenever an Event () is received. By converting a discrete Event into something which can be later sampled, the Behavior localizes a change from push-driven to pull-driven. Thus Event Bools are stored and pulled from as necessary, while Event ()s are pushed through and become Event Ints, which are then pushed until they're also changed into Behaviors (or reactimate'd).

Continuous Time

Another Behavior feature is that semantically (traditionally, but not in reactive-banana) they are continuous functions over time. There are a lot of reasons to like this feature, which is notably missing from the reactive-banana semantic model. Originally I was somewhat skeptical, however I've come to the conclusion that the reactive-banana model of Behaviors as step functions is more correct. Since a Behavior is an accumulator of Events, it makes sense that the Behavior would change only when new Events are received. As an Event is a datum at a discrete time, the Behavior must therefore be a discrete-valued function. In particular, there is a conflict inherent in overloading the meaning of a Behavior to both respond to Events and be continuous in time.

Furthermore, I don't think the programmer loses anything by the reactive-banana model. It's still possible to write functions that are continuous in time and lift them to Behaviors. This is because the reactive-banana framework has no notion of time. If you want a time value, you need to provide one yourself, perhaps via a hardware clock.


-- a pure, continuous function
-- using UTCTime to conveniently tie in with getTime.
createShape :: UTCTime -> Shape

-- an event source tied to the window toolkit's redraw event
redrawScreen :: Event ()

-- function to draw a shape to the screen
drawShape :: Shape -> IO ()

getTime :: IO UTCTime
getTime = Data.Time.Clock.getCurrentTime

reactiveSystem :: Prepare ()
reactiveSystem =
 reactimate $ fmap drawShape
                   (apply (pure createShape) (mapIO getTime redrawScreen))

Let's examine how this works. Fundamentally, when the window system requests a screen redraw, we want to check the current time, generate the correct shape for the time, and finally update the display. Our system provides the redraw requests via an Event (), which is mapped to the current time, creating an Event UTCTime. The createShape function is first lifted to a Behavior then applied to the Event UTCTime, creating an Event Shape. Finally the drawShape function is mapped over this, creating an Event (IO ()) which can be reactimate'd, i.e. each IO () is performed as it becomes available. In my opinion, by removing time from the reactive-banana framework, both the described systems and the implementation are greatly simplified, with no loss of expressiveness.

Simultaneitys

One aspect that seems to cause a lot of difficulty is simultaneous events, multiple Events which occur at the same time. There are a few ways these can arise, such as long sampling periods, merging Event streams, and recursive definitions. reactive-banana specifies that the order of simultaneous events is undefined, providing the orderedDuplicate function to deal with certain cases where timing is important.

I don't like this solution. Semantically, it would be nice that an event stream were strictly increasing in time, disallowing simultaneous events entirely. I suspect that this could be made usable by providing the following two primitive functions:


mergeCombine :: (a -> a -> a) -> Event a -> Event a -> Event a

-- When two events arrive simultaneously, create two output events with the right event delayed slightly
mergeOrdered :: Event a -> Event a -> Event a

The mergeOrdered function introduces a slight delay to preserve discrete events, whereas mergeCombine has a function to combine two events to one. mergeCombine handles the common cases of dropping one event via const and combining with mappend, as well as more specialized functions. I think these functions, together with the guarantee that an Event stream only produces single events, are sufficient for a workable system.

Conclusion

So that's my initial reaction to reactive-banana. The library is quite minimal, but so far it's sufficiently expressive for every problem I've thought of. The new semantics of Behavior seem conducive to developing a correct model of how the implementation works, thereby making it simpler for users to reason about performance and operations. Requiring users to explicitly manage time may eventually become a burden, however it's a direction worth exploring. For many problems user code doesn't depend upon time anyway.

a better audio language

2011-02-03T18:14:00.006Z

One of my frequent frustrations with audio programming languages is that they're relatively unsafe, at least when compared to languages with sophisticated type systems. The problem is generally worsened with EDSLs. Consider this example csound:


  aNull delayr 2
  atap  deltap 1
        delayw asig

Most csound dsl's will provide 3 functions corresponding to delayr, deltap, and delayw, which are translated to the dsl in a very direct manner. If the delayr is left out, the dsl code is translated to invalid csound, detected only by the csound compiler. I find this frustrating because we can do better.

What if the delayr generates a token, which is then required by all functions that want to use it?


 -- Haskell-mode now
 myDelay asig = do
   (dtok, _) <- delayr 2     adelay <- deltap dtok 1     delayw dtok asig     return adelay

This is better, but it's still possible to accidentally omit a delayw from the Haskell code. Again, this is undetected except by the csound compiler at the final stage. What we really need is a way to ensure that a user can run delays freely within the context of a delay line, but only in that context. In Haskell, computations within contexts are generally represented by applicative functors. Let's try that approach:


 -- don't export the constructor
 newtype DelayCtxt a = DelayCtxt { unDelay :: CsoundInterp a }

 deltap' :: CsoundInterp KSig -> DelayCtxt ASig
 deltap' dtime = DelayCtxt $ dtime >>= deltap

 runDelay :: CsoundInterp ASig -> CsoundInterp Float -> DelayCtxt a -> CsoundInterp a
 runDelay mAsig mtime delcomp = do
   maxdel <- mtime     asig <- mAsig     delayr maxdel     rval <- unDelay delcomp     delayw asig     return rval

This is more like it. Since the DelayCtxt constructor isn't exported, the only way to create a DelayCtxt value is with deltap'. The only way to consume a DelayCtxt is with runDelay, which automatically adds the required delayr and delayw.

Unfortunately the user still needs to manually add the maximum delay time, but that's unavoidable if you're going to support varying delay times. Consider that the input signal could be coming from a controller in real-time; to statically guarantee it's under a given bound would require a bounded signal type, which would be equivalent to this static delay bound anyway.

This is the motivating example behind X-DSP, which was presented at the 2011 SEAMUS conference at the University of Miami.

installing gtkglext Haskell bindings with gtk-osx

2010-12-14T18:04:00.005Z

I just managed to install the Haskell bindings to gtkglext with the quartz-based gtk-osx, and I want to record the necessary steps so I don't forget. This assumes you have a working ghc (ghc-7), gtk-osx, and XCode. As a quick overview, I needed to do the following:

install gtkglext (c library)
install gtk (Haskell package)
install gtkglext (Haskell package)

1. Install gtkglext (c)

I downloaded the "Quartz hack full patched source" and followed the instructions at http://answerpot.com/showthread.php?324502-GtkGLExt+OS+X+Quartz+hack+patch. There are a few problems:
The file "docs/reference/gtkglext/html/index.sgml" doesn't exist.
The headers aren't installed.
Several references are made to undefined constants. Unfortunately this error doesn't show up until much later, when GHC tries to link every symbol under the sun.

jhbuild shell
tar -xf gtkglext-1.2.0.osx-hack.tar
cd gtkglext-1.2.0
patch -p1 < gtkglext_c.patch
./configure && make
touch docs/reference/gtkglext/html/index.sgml
sudo make install

2. Install gtk (Haskell)

The Haskell package "gtk" currently (as of gtk-0.12.0) doesn't build with a quartz-based gtk+. I downloaded the source ("cabal unpack") and edited the file "Graphics/UI/Gtk/General/Structs.hsc" to disable the drawableGetID function.


jhbuild shell
cabal unpack gtk
cd gtk
patch -p1 < gtk.patch
cabal install

If you installed the gtkglext libraries to a standard folder this should be all that's necessary. If cabal can't find gdkglext-quartz or gtkglext-quartz, you'll need to add the library paths at this stage.

3. Install gtkglext (Haskell package)

This was painful.

There are a few different problems to deal with:
1. The gtkglext install didn't install the headers, so we need to specify them manually.
2. We're not using pkg-config, so we edit the gtkglext.cabal file, remove the pkg-config check, and specify the libraries to link to.
3. Several symbols are undefined in gtkglext, so we need to remove references to them from the Haskell source. The undefined symbols are:

gdk_gl_config_get_screen
gdk_gl_config_get_depth
gdk_gl_context_get_gl_config
gdk_gl_context_get_share_list
gdk_gl_context_is_direct
gdk_gl_context_get_render_type

AFAICT these were never defined in gtkglext, although they're listed in the headers.

There's also another argument to glWindowNew, which we need to add.

Finally, the demo program needs to be patched, otherwise it just sits there and doesn't update.

So execute the following, replacing PATH_TO_GTKGLEXT with wherever you unpacked/built gtkglext:


jhbuild shell
cabal unpack gtkglext
cd gtkglext-0.12.0
patch -p1 < gtkglext.patch
cabal install --extra-include-dir="PATH_TO_GTKGLEXT" --extra-include-dir="PATH_TO_GTKGLEXT/gdk" --extra-include-dir="$PREFIX/include/cairo/" --extra-include-dir="$PREFIX/include/glib-2.0/" --extra-include-dir="$PREFIX/lib/glib-2.0/include/" --extra-include-dir="$PREFIX/include/gtk-2.0/" --extra-include-dir="$PREFIX/include/pango-1.0/" --extra-include-dir="$PREFIX/include/atk-1.0/" --extra-include-dir="$PREFIX/lib/gtk-2.0/include/"
cd demo
make
./RotatingCube

And you should get a new window with a colorful cube, spinning in full OpenGL glory.

I don't know why it's necessary to specify all the gtk+ header locations manually here, when they're automatically found for building gtk.

The patch files can be downloaded from here.

rant - Microsoft, why do you do this to me?

2009-12-09T23:55:00.004Z

(Recent discussions of the Windows platform have led me to disclose my opinion of a particular infelicity of ASP.Net)

Background: a few years ago, my day job consisted primarily of web development using ASP.Net v.2 and C#. Overall I quite enjoyed the experience. C# is IMHO a pretty decent language, and .NET is alright too. Everything works perfectly smoothly, until you travel off the beaten path.

If Perl's maxim is "There's more than one way to do it," then ASP.Net's is "There's more than one way to do it, but the likelihood of any given way working properly is inversely proportional to the number of ways to do it."

I had an interface, let's call it IHasData. This interface provided a function to pretty-print information associated with different types of events for a web calendar. So far so good. I wanted to display several different events in a GridView. "Simple," I said to myself, "just put them in a generic collection and assign the data source." So I did that, with code pretty much like this (apologies if the syntax is off; I haven't done C# for years):


GridView gv = new GridView();
ListSet events = new ListSet();

//code to fill the events set omitted.

gv.DataSource = events;

and everything should work like a charm. Except, now my page sometimes threw an exception.

It was an odd exception too, indicating that some particular IHasData instance didn't have an unrelated method (i.e. not exposed by IHasData) that wasn't supposed to be in that class anyway. My code was only using IHasData methods; the types ensured that nothing else could be accessed. So why was .Net trying to load something unrelated?

The actual problem was pretty clear. .Net was using reflection on the first element of the data source, and assuming that all remaining elements would have exactly the same type. .Net's reflection facilities are quite powerful, and once they're in play all members of a class are available, regardless of the type used to access it. Not necessarily a good idea for a generic list on interfaces. I have no idea why the GridView has this behavior, but it makes me sad. Particularly since it could have been done right and been that much more useful.

Ultimately this was only one of a host of problems that stemmed from trying to use NHibernate, persistent objects, and .Net built-in features like the ObjectDataSource. It would have been really slick if it worked as advertised, but there were some significant design flaws and the implementation was half-baked at best. I did eventually create a framework that filled most of the gaps, but I was making up for functionality the framework was supposed to provide and didn't. Not good.

iteratee status

2009-11-15T23:44:00.002Z

I haven't posted for a while, so I wanted to provide a small update. I've been working on the following updates:

1) Providing integrated pure and monadic iteratees. I've just implemented an iteratee class, but I don't yet know how performance compares to the original version. I'm also considering a GADT version, but I suspect it'll look ugly.

2) Exception and error handling. Haven't done much work, but I've been thinking about this and have some ideas to implement. Strings are not sufficient.

3) Reorganizing the modules. Most of this is done, although to some extent the final version will depend upon results of item 1.

4) Performance. I've been developing a benchmark suite utilizing Criterion. The ultimate goal is to use this suite to compare performance of multiple versions of the library.

5) Parsec integration. This resulted from a user request. It's useful enough that I'll probably integrate it into the main distribution.

Also, there's a trac instance available.

Restricted-element containers and maps

2009-08-12T12:16:00.003+01:00

Given the perspective we have now, I think it's a little hard to imagine how ground-breaking the concept of type classes were when they were first introduced in Haskell. I think it says a lot that, after the Haskell Committee decided upon their inclusion, they made type classes an integral part of the language. Lest you think that's an exaggeration, can you imagine what Haskell would like like today without, e.g. Num, Functor, or Monad?

As a consequence of using a new idea, some areas that Haskell (and Haskellers!) currently struggle with are related to type classes. One area in particular are containers and type classes. A "Holy Grail" of sorts for Haskellers is the creation of a container type class that provides all the useful container functions. Ideally, all useful container types would be able to be instances of this class.

One package that provides this sort of functionality is John Goerzon's excellent ListLike package, http://hackage.haskell.org/package/ListLike.

ListLike provides (in addition to many others), the functions "map" and "rigidMap". Why two? The difference is in the types:


> class ListLike full item | full -> item where
>   map :: ListLike full' item' => (item -> item') -> full -> full'
>   rigidMap :: (item -> item) -> full -> full

The standard map (and Functor's fmap) allow mapping from a container of any element type to a container of any other element type. rigidMap requires that both the input and output elements and containers have the same type. This is very useful for monomorphic containers. If you provide an instance for ByteString Word8, you can't use the native 'map' because it only maps over elements of the same type since Word8 is the only valid element type. ListLike's default 'map' function builds a new container by destructing and reconstructing the old one. This is highly inefficient compared to native maps, but is the only way to write the function that satisfies the type signature. Even though "ListLike ByteString Word8" is the only instance that can exist, there's no way to prove it to the compiler. 'rigidMap', by further restricting the types, can use the native map, and is therefore much more efficient when it can be used.

Unfortunately there is another case, one that I expect will become more common as certain high-performance libraries become more widespread. Many interesting containers are polymorphic but require class contexts on their elements. Examples are the UVector and StorableVector packages, which require elements to be instances of UA and Storable respectively.

Here's the problem. Using StorableVector as an example, these packages often provide the following map:


> map :: (Storable item, Storable item') => (item -> item') -> Vector item -> Vector item'

How can we use this in ListLike? It could certainly be used directly for 'rigidMap', but what about 'map'? Unfortunately that isn't possible because of the class restriction on the output element type. The type variable for that element isn't mentioned in the class definition (i.e. it doesn't appear in the instance head). Since it's not in the instance head, it isn't possible to put a class context on it. If you fall back to the default 'map' instance any possible efficiency gains are lost.

One solution is to include the output item type in the class definition, but that would require users to put an extra type variable in every time the class context is used, which is a waste for something that is only used for one function.

I think the correct approach is to create a new type class, call it LooseMap, as follows:


>  class (ListLike full item, ListLike full' item') => LooseMap full item full' item' where
>    looseMap :: (item -> item') -> full -> full'
>
> --StorableVector instance
>  instance (Storable el, Storable el') => LooseMap (Vector el) el (Vector el') el' where
>    looseMap = Data.StorableVector.map

Of course completely polymorphic containers (e.g. List) could easily be made instances of this class as well. I would think that "map" should be completely supplanted by "looseMap", although rigidMap would still be necessary for monomorphic types.

As a side note, there is another possible solution. I experimented with using type families to encode Functors (and thus a polymorphic map) as RFunctors, using the same approach as in the RMonad package. This worked fine for map, but I couldn't figure out how to write a fold that satisfied the typechecker. I think it's impossible, and would love to hear from anyone who knows how to make it work.

SEAMUS recap

2009-04-19T05:57:00.003+01:00

The 2009 SEAMUS Conference is over, and the finale featured the coolest thing ever. A video of an earlier concert is on Youtube already, of course (I didn't see the most recent concert posted yet).

http://www.youtube.com/watch?v=aOZEpP_zzaw&feature=related

future directions for iteratee

2009-03-12T02:44:00.003Z

I have recently completed two major projects that were taking up nearly all of my time. Now that they are done, I'd like to work on the next version of the iteratee package. Here are a few ideas that I hope to include soon.

1. Remove the explicit Maybes
This was suggested by Oleg, and it seems to be a good idea. Every iteratee that produces a value other than () uses Maybe to represent the possibility of failure (always an option when doing IO). By incorparating the Maybe into the type of IterateeG, these will no longer need to be explicit. This will also make IterateeGM an instance of MonadZero to the extent that Maybe is an instance of that class.

Status: I've made a patch that does this, but it doesn't yet work properly with convStream. I haven't managed to track down the problem. Likely to be included, assuming I can solve this issue in a reasonable time frame.

2. Stream type class (and simplify StreamChunk)
I keep hoping for a ListLike type class to enter common use. Barring that, I have some ideas for breaking up the necessary functions of StreamChunk into separate type classes, such as the patch to use a monoid instance submitted by Bas van Dijk.

Status: Changes will be made, it is likely that StreamChunk will be broken into multiple smaller classes. Any addition of a Stream type class will wait until after point 4 is resolved.

3. More utility iteratees (foldl, filter, others?)
Status: Likely to be included. Changes to StreamChunk will make these easier to support.

4. Type-safe seeking
If iteratees are parameterized by Stream, the type of the stream should indicate if seeking is supported. I have an outline for how to implement this, but haven't done any work yet.

Status: Needs research, this will probably wait for the next major version bump.

5. Improved error handling
Bas van Dijk submitted a patch to change the type of a stream error from String to Error a. Others have suggested other possible changes as well.

Status: Needs more research, this will likely wait for the next major version bump.

enumerator/iteratees and output

2009-03-12T00:22:00.009Z

I have recently received a few questions about writing output while using enumerator-based I/O. In some cases users have attempted to make enumerators (like enumFd) that will handle output as well, but have difficulty actually making it work.

I think these problems stem from an incorrect application of the enumerator model of I/O. When using enumerators, a file (or other data source) is a resource that can be enumerated over to process data, exactly as a list can be enumerated over in order to access the data contained in the list. Compare the following:

foldl f init xs

enumFd "SomeFile" ==<< stream2list

In the first function, 'xs' is the data to be processed, 'foldl' tells how to access individual items in the data collection, and 'f' and 'init' do the actual processing. In the second, "SomeFile" is the data, 'enumFd' tells how to access the data, and 'stream2list' does the processing. So how does writing fit in? The output file obviously isn't the data source, and it doesn't make sense to enumerate over your output file as there's no data there to process. So it must go within the Iteratee. It turns out that making an iteratee to write data is relatively simple:


> import Data.Iteratee
> import System.IO
> import Control.Monad
>
> writeOut :: FilePath -> IterateeGM [] Char IO ()
> writeOut file = do
>  h <- liftIO $ openFile file WriteMode
>  loop h
>  where
>  loop :: Handle -> IterateeGM [] Char IO ()
>  loop h = do
>   next <- Data.Iteratee.head
>   case next of
>    Just c -> liftIO $ hPutChar h c >> loop
>    Nothing -> liftIO $ hClose h

Add some error handling and you've got a writer. This version could be polymorphic over different StreamChunk instances by generalizing the type (FlexibleContexts may be required as well). Other stream-specific versions could be written that would take advantage of the specific StreamChunk instance (e.g. using Data.ByteString.hPut instead of hPutChar).

I hope this will serve as a very basic introduction to output when using enumerators. In addition to a generic writer like this, it may frequently be beneficial to define special-purpose writers. In a future post I will show a writer that seeks within the output file using a threaded State monad.

Build a better WAVE reader, pt 2

2009-02-03T00:50:00.002Z

In the last post, I looked at the beginnings of using an Iteratee to create a WAVE file reader. I achieved a runtime of 25 seconds, compared to 1.9 seconds for my benchmark code.

Oleg's Iteratee code uses a Stream type which internally represents data as Chunk [a]. Haskell lists have many great properties, but they are not particularly efficient for this type of numerical processing. There are many better options, including Arrays, UVectors, and StorableVectors.

Unfortunately all of these options I would want to use introduce a type class restriction on types of elements in the array. This isn't a problem for sound files in particular, although it does greatly limit the utility of the Iteratees in general. One of the Iteratee examples shows how Iteratees can be layered for text processing, using IterateeGM String m a iteratees layered on IterateeGM Char m a iteratees to provide operations on words in a text stream. This is no longer possible, as String is not an instance of the type classes necessary to use one of these more compact data structures. In the end, the performance benefits should be worth it.

I chose StorableVector to replace the basic list, because it seemed handy while I was experimenting. StorableVector turns out to have another good property which is key to achieving the goal of performance close to C.

Adapting the Iteratees to use StorableVector is straightforward. Unfortunately when we've finished, performance is actually worse! In fact, it's as bad as the original RBIO-based version. It turns out that one key function is the culprit: conv_stream.

conv_stream converts between two streams. It is capable of converting multiple elements from one stream to one (or no) elements of the other, using a user-supplied conversion function. The wave file reader uses conv_stream to convert from a stream of Word8's to a stream of Doubles so the user can operate on Doubles, with the library handling all conversions transparently. The original type of conv_stream is:

conv_stream :: Monad m =>
IterateeGM el m (Maybe [el']) -> EnumeratorN el el' m a

Unfortunately, this means our data needs to unpacked from the StorableVector Word8 into separate Word8's, those Word8's assembled into Just [Double], and finally packed into a StorableVector Double for the next Iteratee. This is very inefficient, but easily fixed. Just change the type of conv_stream to

conv_stream :: (Storable el, Storable el', Monad m) =>
IterateeGM el m (Maybe (Vec.Vector el')) -> EnumeratorN el el' m a

and we're done. In fact, the implementation doesn't change at all from the original, just the type. Now no packing or unpacking need take place.

With the new conv_stream, it's necessary to change the conversion function. This is the IterateeGM which converts Word8's into Doubles. I have actually split this code into two parts, a function (called unroller because the original list-based version was a manually-unrolled endian_read) which converts Word8s into Word16 or Word32 as necessary, and a normalization function to normalize the result and convert from Words to Double. The normalization function should be fine as is, all that's necessary to change is the unroller function. Ideally, it would operate on StorableVectors directly. Fortunately this is possible. All that's necessary is to get a ForeignPtr Word8 from a StorableVector, and cast it to ForeignPtr Wordn. A somewhat hackish 16-bit converter can be implemented as follows:

import qualified Foreign.Ptr as FP
import qualified Foreign.ForeignPtr as FFP
import qualified Data.StorableVector as Vec

unroll_16 :: (Monad m) => IterateeGM Word8 m (Maybe (Vec.Vector Word16))
unroll_16 = liftI $ IE_cont step
where
step (Chunk vec)
| Vec.null vec = unroll_16
| Vec.length vec == 1 = liftI $ IE_cont $ step' vec
| Vec.length vec `rem` 2 == 0 = liftI $ IE_done (convert_vec vec) (Chunk $ Vec.empty)
| True = let (h, t) = Vec.splitAt (Vec.length vec - 1) vec
in
liftI $ IE_done (convert_vec h) (Chunk t)
step stream = liftI $ IE_done Nothing stream
step' i (Chunk vec)
| Vec.null vec = liftI $ IE_cont $ step' i
| Vec.length vec `rem` 2 == 1 = let vec' = Vec.append i vec
in
liftI $ IE_done (convert_vec vec') (Chunk $ Vec.empty)
| True = let (h, t) = Vec.splitAt (Vec.length vec - 1) vec
in
liftI $ IE_done (convert_vec $ Vec.append i h) (Chunk t)
step' _i stream = liftI $ IE_done Nothing stream
convert_vec vec = let (fp, off, len) = VB.toForeignPtr vec
f = FP.plusPtr (FFP.unsafeForeignPtrToPtr fp) off
fp' = (FFP.castForeignPtr $ unsafePerformIO $ FFP.newForeignPtr_ f) :: FFP.ForeignPtr Word16
in
Just $ VB.fromForeignPtr fp' (len `div` 2)

and that's it! The big hack is that this only works on little-endian platforms. To be correct, the bytes would need to be swapped on big-endian systems only. Implementing a suitable swap function is currently an excercise for the reader. Note that unsafeForeignPtrToPtr should be safe as there is no finalizer associated with the ForeignPtr, and in any case the memory pointed to won't be GC'd until after the Iteratee is complete.

At this point, the data should be handled entirely as a StorableVector, with no conversions to or from any intermediate lists at any point. Here are results from running the test:

$ time ./test_iter_sb
Just (AudioFormat {numberOfChannels = 2, sampleRate = 44100, bitDepth = 16})
Just 0.977568895535142

real 0m1.661s
user 0m1.335s
sys 0m0.140s

And the proof is in the pudding. This is the fastest Haskell implementation yet, even faster than hsndfile in a lazy stream.

A bit of work remains to be done. It should be cleaned up, with the hack fixed properly. Also I've currently only implemented unroll_16. For 24-bit audio, I expect the creation of a Word24 type and Storable instance will be necessary in order to employ the same technique. However, I think I've proven that a pure-Haskell, high performance audio I/O library is possible.

Build a better WAVE reader, pt 1

2009-02-02T02:11:00.009Z

I have recently been working on creating an optimal audio I/O library in Haskell. By optimal, I mean the library should do all of the following:

Have a clean, functional, usable interface. Operations should be composable, and the user should not have to deal with recursion, folds or the like. Procedural-style interfaces (anything exposing filehandle-type operations to the user) are out too.
Be space efficient. Some Haskell implementations suffer from space leaks, or can have space leaks if the user isn't careful with data.
Have performance comparable to hsndfile, a Haskell binding to libsndfile.
Be implemented purely in Haskell. This makes it interesting.

The standard for audio I/O performance in Haskell has been hsndfile, as was discussed on haskell-cafe not long ago. Testing shows that using hsndfile to read data in a lazy stream fashion (similar to lazy ByteStrings) is about 10 times faster than the next-fastest implementation. Not good for Haskell's claim of having speed comparable to C! Still, I'm convinced it's possible to do better.

My test case consists of finding the peak normalized amplitude of a 16-bit stereo WAVE file. The audio duration is about 6 minutes, with a total file size of about 66 MB. This task involves reading and processing the entire file. The processing is quite minimal, so the speed of an implementation should depend primarily on the efficiency of reading and normalizing audio data.

Using hsndfile in a lazy stream does provide an interface which is familiar to many Haskell users, but I'm not particularly fond of it. If the user is not careful, the entire file can be retained in memory after processing. For a large audio file, this leads to an unacceptable situation. It should be impossible for data to be retained without explicit action from the user. Also, dependencies on foreign libraries can be difficult for some (i.e. Windows) users to resolve.

So having decided to create a native Haskell implementation, the first place to start is with the semantics and interface. I recently read Oleg K.'s presentations on Iteratee processing in Haskell, and I'm convinced this is the best model for functional I/O. It just feels right, what else can I say? Read the paper, see the code.

A preliminary version of Iteratee-based processing was benchmarked as "Enumerator" in the Haskell-art discussion. It was roughly comparable with other Haskell solutions, but has some problems. Notably it doesn't support seeking within the file, which would be nice. After I developed that, Oleg released a new version of Iteratee which does support seek operations via the RBIO monad. So I dropped Enumerator in favor of the new Iteratee + RBIO.

Oleg helpfully provides a TIFF reader with his Iteratee code. I based my wave reader on that, using the same technique of storing Enumerators for each wave sub-chunk in an IntMap. Since they aren't tagged, a list probably would have served just as well, but since most wave files only have 2 or 3 chunks anyway it doesn't seem like it matters much. Changes here aren't going to have a large performance impact.

The first version to use Iteratee + RBIO executes in about 45 seconds. Ouch.

RBIO uses IORef's to communicate seek requests and answers between Iteratees and Enumerators. Unfortunately IORefs are slow, so I'll start by getting rid of them. The data type

data IterateeG el m a = IE_done a (StreamG el)
| IE_cont (StreamG el -> IterateeGM el m a)

can be changed to

data IterateeG el m a = IE_done a (StreamG el)
| IE_cont (StreamG el -> IterateeGM el m a)
| IE_seek FileOffset (StreamG el -> IterateeGM el m a)

This also necessitates adding one more case to (>>=) on Iteratees:

iter_bind m f = m >>== docase
where
docase (IE_done a (Chunk [])) = f a
docase (IE_done a stream) = f a >>== (\r -> case r of
IE_done x _ -> liftI $ IE_done x stream
IE_cont k -> k stream
iter -> liftI iter)
docase (IE_cont k) = liftI $ IE_cont ((>>= f) . k)
docase (IE_seek off k) = liftI $ IE_seek off ((>>= f) . k)

After these changes, the provided Iteratees can be adapted to use the new structure relatively easily. The enumerator that reads from a file, enum_fd_random, must also be updated to understand seek requests. At this point we can remove RBIO entirely, and our execution time is about 33 sec. Adding a few carefully-chosen INLINE's and SPECIALIZATION's gets runtime down to 25 sec. Better, but we're very far from the goal of being comparable with C.

The next step is to change the Iteratee's internal representation of data.

Introduction

2009-02-02T01:57:00.000Z

Hi, and welcome. I've decided to start this blog as a way to share some of my findings with various communities I'm involved with. I will try to post when I have something important/interesting to say, so I may not update all that frequently.

My main interests are music and programming. Specifically, modern art music, electroacoustic music, and programming in order to serve some musical purpose. For the moment, my language of choice is Haskell, because it's far more interesting than other languages I know. If Perl is for people who want to Get Things Done, then Haskell is for people who want to Do Things Right, Eventually, After You Figure Out Exactly What That Means. Which suits me just fine.

So again, welcome and thanks for taking a look.

Sound and Software

J. Roger Hindley is coming to Maynooth

splaytree package released

My mind is blown

Circular Buffers

Linux Audio Conference 2011

GTK on OSX

Thoughts on FRP

a better audio language

installing gtkglext Haskell bindings with gtk-osx

*rant* - Microsoft, why do you do this to me?

iteratee status

Restricted-element containers and maps

SEAMUS recap

future directions for iteratee

enumerator/iteratees and output

Build a better WAVE reader, pt 2

Build a better WAVE reader, pt 1

Introduction

rant - Microsoft, why do you do this to me?