Saturday, November 22, 2014

Exception handling and cleanup

So there's been a bit of a slog recently on whether or not cleanup actions (e.g. stuff you'd put in the second argument to bracket or finally) should be run in an implicit uninterruptibleMask. I have argued that this is a desirable change. I'm writing this post mostly to lay out the logic I've used to reach (and support) this position, because it's a bit tricky (much like the issue itself).

A bit of background: currently, if an interruptible function is used within an exception handler, asynchronous exceptions may arrive and cause the handler to behave in unexpected ways. In particular, if an async exception arrives during an interruptible period in a cleanup action run by bracket[1], you can get resource leaks. This is noted in the documentation, but it can be surprisingly difficult to get right. Notably, this has resulted in several bugs in GHC itself (details in the thread).

Two arguments have thus far been presented against the proposal, one that the change is undesired and secondly that more caution should be exercised before making such a silent semantic change, especially as it's possible that currently-working (although likely resource-leaking) programs would deadlock. I reject the first argument (for reasons explained below) and have some sympathy for the second, although I believe the benefits outweigh the costs. I'll refer to the argument that this change is undesired as Undesired below.

Basically there are two cases of "complex" cleanup actions that have been under discussion. Here are naive (incorrect) examples of each:

cleanup1 (Structure h1 h2) = hClose h1 >> hClose h2
cleanup2 var = withMVar var >>= hClose

The first, cleanup1, is a handler that has to perform multiple, unrelated actions. The second, cleanup2, is a handler that has to perform a blocking call to access a resource, then close that resource.

Undesired argues that cleanup1 is better written hClose h1 `finally` hClose h2. I agree that is a better solution (although I tend to use nested brackets myself). That structure is nearly fully exception-safe (except hClose itself isn't async-safe), and it handles synchronous exceptions properly. In particular, uninterruptibleMask is neither necessary nor sufficient to write cleanup1 properly[2].

There is no way to safely write cleanup2 without using uninterruptibleMask[3]. It is possible to write a much more sophisticated handler that could eventually time out and possibly take an alternative action, but I don't believe I've ever seen an example of such code. Even then, it still wouldn't close the handle.

Undesired further argues that adding an uninterruptibleMask to bracket will tend to make people think that the naive handler in the first case is safe, even though it isn't, and therefore we shouldn't add it. Users should instead know to use finally appropriately in that case, and uninterruptibleMask appropriately in the second.

I reject this conclusion. I believe the second case is quite common, likely more common than the first. Both Handle and Process use this structure internally (and hence are both vulnerable to async-exception issues that can only be fixed with uninterruptibleMask, which their cleanup functions do not currently employ). I also think it's quite common in client code when there's a shared structure that requires cleanup. Such cleanups can only be handled safely via uninterruptibleMask, and in general use of that function should be discouraged.

If we want to be leak-free (in the second case, and with hClose), we need to call uninterruptibleMask somewhere. Where should we call it? The obvious choices are in the cleanup action (e.g. within hClose), within bracket, or manually by the user. I reject the last as being undesired and error-prone; we certainly don't want the common idiom to be .. `finally` (uninterruptibleMask_ (hClose h)). I believe within bracket is better than within hClose. First of all, we really only expect exception-safety in the context of a function like bracket. Having a bare hClose is already not regarded as a safe idiom, so having it be vulnerable to async exceptions in another manner should not be a problem. Given that, I believe it's better to change the semantics of bracket so that all such handlers will work properly, rather than requiring that Handle, Process, and others be fixed (and countless 3rd-party libraries audited. I have at least two of my own I need to audit.).

Some opponents of the proposal have presented various control-flow constructs built upon bracket that would lead to deadlock under the proposed semantics. If hClose et al used uninterruptibleMask internally, those control flows would not be expressible at all, unless a new function "interruptibleHClose" were added. Similarly for Process and 3rd-party code. If instead bracket is changed, then we'd need to preserve the current semantics as "interruptibleBracket". Anyone relying on this specific control flow would just need to change from bracket to interruptibleBracket to preserve the current semantics, instead of needing to change hClose, process termination functions, dbClose, etc.[4]

Changing bracket means we'll probably fix a bunch of currently-buggy code (anything like cleanup2 that doesn't use uninterruptibleMask, including Handle and Process cleanups), and it will be less work to adapt for anyone relying upon the current semantics.

As I mentioned above, IMHO there is merit to the argument that we should be cautious when making a silent change like this. However, I think the pain is unavoidable. The current situation is not async-safe, and cannot be made async-safe without changing semantics (i.e. adding uninterruptibleMask somewhere). Here are all the alternative possibilities that have thus far been discussed:

  1. Users need to be intimately familiar with exceptions and interruptible operations to write truly exception-safe code, including knowing when to wrap built-in functions in uninterruptibleMask (the status quo).
  2. Add uninterruptibleMask internally to hClose, certain process-related functions, and anywhere else similar "cleanup2". Anyone relying upon the current interruptible behavior must audit their code, and (if available) switch to interruptible variants. 3rd-party code must all be audited. Concerns about unkillable threads/deadlocks apply.[5]
  3. Add uninterruptibleMask internally to bracket, finally, etc. Anyone relying upon the current interruptible behavior must audit their code, and switch to interruptible variants. 3rd-party code will be async-safe, although if it's currently vulnerable to sync exceptions it will remain vulnerable. (the proposal). Concerns about unkillable threads/deadlocks apply.

Of these choices, I consider the first untenable. I simply do not believe we should expect this level of async exception sophistication from most users. I will gladly accept the possibility of unkillable threads in this context to achieve the greater exception safety of 2 or 3, of which I contend 3 is better. It places the least burden of knowledge on the greatest number of users, involves less code-change than the second option, and also leads to the greatest safety by default.

[1] From now on I'll just write "bracket", but will generally mean the whole cleanup-handler family of functions.

[2] Except uninterruptibleMask is the only way to make hClose fully async-exception-safe.

[3] Or its semantic equivalent. It's often possible to change from a blocking operation to looping over a non-blocking operation under mask, but this has the same effect of making the code unresponsive to async operations.

[4] Given the examples that have been presented thus far, I strongly believe that any user relying upon the interruptibility of cleanup operations understands the Haskell exception system intimately and therefore is in the best position to adapt to any semantic changes of exception-handling functions.

[5] I expect the extra risk from changing bracket to be uninterruptible to be minimal over changing hClose etc, as Handles are ubiquitous.

Thursday, October 4, 2012

runtime meta-programming in Haskell

In the spirit of Edward Yang, half-baked ideas lie ahead

There are many reasons programmers may want to use metaprogramming facilities, but one of the most common is for greater efficiency.  The premise is simple: if runtime data becomes available at different times, a metaprogramming environment may allow the programmer to generate specialized versions of code based upon certain data which is known sooner, leading to more efficient computations.

A running example in a great deal of literature is the power function.   Given pow a b = b ^ a, for certain values of a a much more specialized function can be created, e.g.

pow 1 b = b
pow 2 b = b*b
pow 4 b = let sq = b*b in sq*sq
pow n b = b ^ n

but writing out all possible cases like this is far from ideal.  It's tedious and error-prone, and it still won't result in the hoped-for performance gains.  Another problem is that it's generally not possible for the programmer to enumerate every possible case.  A better solution is desired.

Template Haskell is generally disparaged as a possible solution because it's a compile-time facility.  A meta-programming approach to the pow function would be this Template Haskell expression:

mkPow 0 = [| const 1 |]
mkPow n = [| \x -> x * $(unMeta $ mkPow (n-1)) x |]

while this works, Template Haskell splices may only be evaluated at compile-time.  For a wide range of interesting metaprogramming problems, template haskell simply isn't available.  However, by using the GHC API, we can make use of Template Haskell during runtime.  By using a package like plugins or hint, the code is remarkably simple.

I've placed a proof-of-concept implementation on github.  meta-expressions are created in the Meta newtype, which wraps Template Haskell's ExpQ type.  The Meta monad has an extra phantom type parameter to assist with type safety and inference.  Here's a simple example of Meta in use, with mkPow essentially as defined above:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -Wall #-}

module Data.Meta.Example where

import Data.Meta.Meta
import Data.Meta.ExampleExpr

main :: IO ()
main = do
  n1 <- readLn
  let expr1 = mkPow n1 :: Meta (Int -> Int)
  n2 <- readLn
  let expr2 = mkPow n2 :: Meta (Int -> Int)
      expr3 = compose expr1 expr2
  result <- metaCompile expr3
  case result of
    Left err -> putStrLn "failed" >> putStrLn err
    Right fn -> do
      j <- readLn
      print $ fn j
      k <- readLn
      print $ fn k


Incidentally, this approach seems remarkably similar to the ideas in Geoffrey Mainland's presentation at ICFP 2012. The big differences are that he defines his own quasi-quoters instead of using Template Haskell, and he also uses a compiler other than GHC. Both of these are necessary if you want to metaprogram in a language other than Haskell, naturally.

Tuesday, June 12, 2012

Language-ObjC released

I have uploaded a new package to hackage, language-objc.  This package provides an AST, parser, and pretty-printer for Objective-C.  It's a fork of the excellent language-c package, so if you're familiar with that you should be able to pick up language-objc pretty quickly.

Source repository is on github.

If you "cabal unpack language-objc; cd language-objc-0.4.2.0/examples/", there are a number of examples that can get you started.  For the truly impatient:

import Language.ObjC
import qualified Data.ByteString.Char8 as B

-- parsing bytestrings
objcTranslUnit = B.pack "int a=0;"

errOrAST = parseC objcTranslUnit nopos

-- parsing from a file
fileAST sourceFile = do
    result <- parseCFile (newGCC "gcc") Nothing [] sourceFile
    return $ either (error . show) id result
A few things to note:
  1. Input files must be preprocessed.  'parseCFile' will do this for you.  Non-preprocessed source can only be parsed in very limited situations (did you know that 'id' is a typedef?  And 'id' is also commonly used as an identifier to methods/functions, even in system libraries, so it can't be a keyword?).
  2. The objective-C extensions have only been lightly tested, but I think most of the core functionality works.  I am unaware of a full specification for the language, which makes it difficult to say if it's complete.
  3. Most of the code in Language.ObjC.Analysis is not yet compatible with Objective-C extensions.
  4. One difference from language-c is that certain GNU attributes can no longer be parsed due to grammar ambiguities.
  5. Attempting to compile at -O2 requires a lot of memory due to the giant Happy parser that's produced.

I am most grateful to Benedikt Huber, Manuel Chakravarty, Duncan Coutts, Bertram Felgenhauer, and all contributors to language-c, as they're responsible for most of the code.  Bugs are mine.  Comments and patches welcome.

Monday, June 11, 2012

Understandings of Iteratees

Although still relatively new, iteratee/enumerator style I/O has achieved a fairly large userbase in the Haskell community.  Like many young technologies, the design space is fairly broad, with several different packages available from Hackage.  Upon surveying the alternatives, I came to realize that there are so many alternatives in part because different developers have chosen to focus on different properties of iteratees.  Doubtless this is a contributing factor to much of the confusion surrounding iteratees; when a user's mental model is closely aligned to the developer's, the package is likely to be much easier for the user to understand.

This post isn't meant to explain how to use iteratees, rather to explore what I believe are factors that influenced various design decisions in different packages.  In some cases I have first- or second-hand knowledge of those decisions, but sometimes I'm extrapolating from the code.  If you find one or two packages to be sensible and can't understand why anyone would use something different, you may find enlightenment here.  Or not.  For those who've never used an iteratee package, I hope that these posts might help point you to a good starting option.  Wizards probably know this already.  Note that just because I think the designers have a particular viewpoint for their code doesn't mean that other elements won't be present; these are all just different ways of looking at iteratees.  All packages will have these properties to some extent.

Glossary

Some definitions, to be perfectly clear (the adventurous can skip this)
  • iteratee: some sort of resource consumer.  The defining feature of an iteratee is that it provides a mechanism to pump it with data until it returns a result.  I may use "iteratee" generally, referring to code in an iteratee style.
  • enumerator: some sort of resource provider.  It stuffs data into an iteratee until it gets a result.
  • iteratee style, iteratee/enumerator style: writing code that makes use of iteratees, enumerators, and other associated functions
  • iteratee package: a library to provide functions used to write in iteratee style.
  • underlying monad: for iteratees that are monad transformers, the monad which is being transformed.  Often either IO or a monad stack based on IO.

1: Iteratees as Resource Managers


One of the design goals of Oleg Kiselyov's original iteratee work was improved resource management.  Lazy I/O can make it difficult to reason about resource management (half-closed?), while strict I/O traditionally does not compose well (compare to network programming in C).  With iteratees, these problems are much closer to being solved.  Input streams are opened on demand, evaluated strictly, and closed immediately, with no possibility of the handle or other resource leaking.(1)  And iteratees are quite composable (perhaps too much so!), solving the other issue as well.

These properties make iteratees extremely useful for network programming, as network sockets are a scarce resource.  However, this usage highlights a particular drawback: iteratees solve the resource management problem for input, but don't address it for output.

I believe that for this issue, all developers currently agree the best solution for output resource management is to use a monadic region, such as that provided by regions or ResourceT .  This is currently the only approach guaranteed to run cleanup code with complicated monad stacks in the presence of exceptions.(2)  In some cases Control.Exception.bracket can be used, however it's often not possible to call it at a convenient time, leaving resources open for longer than necessary.

Having established that a monadic region is necessary for output resource management, using the same mechanism for input resource management as well is a reasonable decision.  Developers taking this view may then write their package so that even input streams may cause resource leaks without the resource management layer, unlike the original design.(3)

2: Iteratees as Stream Processors


Iteratee packages with a stream processing bent focus on composibility as a design goal.  The libraries usually provide a multitude of stream processors. They are frequently designed with a UNIX-pipeline-style model in mind; data can be passed through one processor into the next and so on, until finally the last processor in the chain consumes the resulting data.  There may be clear demarcations between produces, consumers, and processors, or perhaps not.  There are frequently combinator functions to make these connections, sometimes with a syntax inspired by unix pipes.  Many of the functions will be similar to traditional Haskell list-processing functions, such as maps, accumulators, and filters.

People with this viewpoint tend to view stream processor composition, which Oleg refers to as an "Enumeratee", as the most important/useful means of composing iteratees.

Although I've presented stream processing and resource management as two different viewpoints, I addressed them together because packages generally can't exclude either element.  One approach is to divide responsibilities, with a dedicated resource manager and combinators that can use those resources.  Other packages may use the iteratee's own handling of input resource management, leaving output resource management to the user's discretion.

Conclusion


For the curious,  I would place conduit and iterIO squarely in the stream processor camp, with enumerator having strong leanings this way as well.  To some extent all iteratee packages provide similar stream-processing capability; I make these judgements based upon what I think the designers think iteratees are for.  If your favorite iteratee package hasn't shown up yet, maybe next time!

Notes

(1)  There is at least one way to force a resource to be open longer than intended.  Since iteratees are generally implemented as monad transformers, it is possible to craft an iteratee over ContT IO that generated a lazy stream from an input source, available within another iteratee.  The resource would be closed when the outer iteratee was evaluated, making the outer iteratee a type of monadic region.  I consider this an egregious abuse of Cont, however, and extremely unlikely to happen accidentally.

(2) I'm fairly outspoken in my dislike for exceptions.  They mostly shouldn't be used.  The main purpose of exceptions is to make it easy to reason about how to deal with various conditions, and they suck at this.  There are basically three kinds of exceptions:
  1. Stuff you can fix, like a file not existing.  This should be modeled by Either or Maybe or something similar.  It's much easier to reason about a Maybe than having to figure out where in IO some result will be evaluated.  This is by far the most common reason programmers use exceptions, and (in Haskell at least) it's the worst choice because Haskell provides a better mechanism for dealing with this problem.
  2. Stuff you can't fix, like out of memory conditions.  The only sensible thing to do is terminate the program and let the OS clean it up.  You shouldn't try to catch these, and if you do catch one you shouldn't try to do anything, because that might fail too.  I suppose it's okay to model these with an exception, but maybe they shouldn't be exposed to the program logic at all.
  3. Asynchronous exceptions.  I begrudgingly accept that these may need to be used in concurrent code.

(3)  The basic resource provided by an OS is generally a cursor, e.g. handle.  Oleg Kiselyov argues that cursors and enumerators are isomorphic, although enumerators have certain desirable properties that should make them preferred.  The traditional design of an iteratee package is to provide enumerators that wrap access to a cursor in a closure, preventing the cursor from leaking.  Packages like pipes or conduit that require a monadic region for safe access to input hold the cursor as data and don't provide enumerators-as-closures.  In essence they evolved from cursor to enumerator back to cursor.  Because of this I'm not entirely convinced they should be classed as "iteratee packages" at all, though they certainly occupy the same design space.

Sunday, April 29, 2012

Adding state support to BNFC

The BNF converter is pretty cool tool.  The idea is simple:  provide a grammer written in Labelled BNF, and it spits out a lexer, parser, pretty printer, and abstract syntax tree.  The very nice part is that the generated code can be in several formats: Alex/Happy/Haskell, flex/bison/C/C++, or JLex/CUP/Java.  It's especially convenient when you're developing a language, as you can make changes as you go and automatically keep your AST, parser, and printers in sync.

BNFC takes as input a file written in Labelled BNF, which is essentially a BNF grammar with a label attached to each production rule.  Brackets "[ ]" indicate lists rather than optional items, and there are few extensions from minimal BNF other than pragmas to define lexer tokens and positions.

Writing one grammar file instead of 4 separate modules is very attractive.  Unfortunately BNFC has a serious problem - only context-free grammars are supported.

LBNF is sufficient to represent context-free grammars, and within this domain the system works very well. But despite the claims of the LBNF Report, many interesting languages are not context-free, and they still need to be lexed and parsed.  The most notable example is probably C, in which a string can be lexed as an identifier or a type name, depending on previous typedefs and other things.  I present here a small set of extensions to enable support for passing state between the lexing and parsing stages, enabling a wider variety of parsers to be constructed from LBNF.

A darcs repository of BNFC, with state support as described here, is available from http://www.tiresiaspress.us/haskell/bnfc/.  These features are only supported in the Haskell/Alex backend (Alex-3 is required).

An initial examination

The approach I took is founded on two simple ideas.  First, the lexer needs to access to a state table to determine the correct token, and secondly, the parser needs to update the state table in response to certain rules.

Lexing rules

In LBNF, tokenizing rules are specified like this:
token Ident (alpha [alpha|digit|'_']*) ;
where "Ident" is the type of the token produced, and the remainder is a regular expression to determine valid "Ident" strings.

A stateful token rule is similar.  The implementation supports multiple sets of state, so it's necessary to specify which state set the tokenizer should check.
state token TypedefName typedefNameSet [alpha|digit|'_']+ ;
First the lexer matches the regular expression against the input string.  It then takes the match and checks if it's present in "typedefNameSet".  If so, a token of type "TypedefName" is produced.  Otherwise an "Ident" is produced.(1).

Parsing Rules

Standard production rules are extended with pragmas that specify state update annotations:
-- after this rule, the final Ident will be lexed as a TypedefName
Etypedef.  Declaration ::= "typedef" TypeName Ident <% state typedefNameSet add 3 %> ;
The number "3" specifies that a token string derived from the 3rd production (Ident) is to be added to the set "typedefNameSet".(2)

Similarly, names can be removed from a state set:
-- after this rule, the second token will be lexed as an Ident
UnTydeclarator. Direct_declarator ::= TypeName TypedefName <% state remove 2 %> ;
When removing a token from a set, it's unnecessary to specify the set the token is being removed from.

Extended support

Initial Values

Initial members of the state sets can be specified in the grammar via the pragma TODO.

Scoping

The implementation maintains a stack of state values in order to support lexical scoping of changes.  Two additional pragmas, "state push" and "state pop", provide access to stack manipulations.  A common usage would be:
PushParen.  PushParen ::= "(" <% state push %>
PopParen.   PopParen  ::= ")" <% state pop %>
It is an error to pop the last frame off the state stack.

The implementation only supports one stack for all state sets.  It is not currently possible to represent multiple state sets with differing scoping rules.

A drawback of the current implementation is that production rules such as PushParen and PopParen are no longer terminals.  Therefore the implementation creates abstract representations for them, although no additional meaning is conveyed than if they were omitted completely.  I hope to address this in the future.

Future Work

Deriving the state string

A major question is, how to determine which token is added to the state set for a given production?  The above cases are simple.  In a production rule like:
Etypedef.  Declaration ::= "typedef" TypeName Ident <% state typedefNameSet add 3 %> ;
"Ident" is a token, so it's simple to derive the string that should be added to the set.  However, it's frequently desirable to modify state based upon a non-terminal rule, such as:
Rule.  SomeProd ::= Declaration <% state stateset add 1 %> ;
How should the token be determined from the Declaration?

The current implementation only supports state adjustments based upon tokens and lists of tokens, e.g. [Ident].  Code generated from rules like the above "Rule" currently results in a compile-time error due to missing instances.  The instances can be manually provided in a separate file, although creating this file can be tedious.  I plan to add an additional pragma to the LBNF grammar that would allow for the necessary instances to be automatically generated.

Notes

(1) - The astute reader will notice that the TypedefName regex matches strictly more identifiers than the built-in "Ident" regex.  Therefore this match provides a "backdoor" into Ident, allowing strings that don't match the "Ident" regex to actually be produced as "Ident"s.  I find this behavior useful, and in any case it can be mitigated simply by using the Ident regex for state tokenizing rules.  Another possibility would be to use a user-provided alternative in case the match fails.

(2) - An alternative notation would omit the numbers and place the pragma adjacent to the production.

Sunday, March 25, 2012

Pure delay lines

While working on my dsp-extras project, I needed a pure delay line.  Based on previous work, I used Data.Sequence.Seq, and was somewhat surprised to see a very large performance hit when compared to an undelayed signal.  Obviously there was more to creating pure buffers in Haskell than my previous microbenchmarks revealed.  I resolved to get the performance back.

I created a test script to measure the performance of different delay line implementations in a real-world application.  The application simply reads in a sound file, applies a fractional delay, and writes the output.  I measured the performance with buffer sizes ranging from 1 to 10000 samples.  Due to interpolation (I used cubic interpolation for all my tests), I couldn't actually measure a 1-sample buffer; the program actually creates a 4-sample buffer for the smallest possible delay.  All other buffer sizes are accurate though.

I tested the following buffer types:
  • Data.Sequence.Seq - cons elements onto the front and drop from the tail as each element is pushed
  • Data.Vector.Unboxed.Vector - a naive copying implementation
  • T10 - a 10 element, strict data type (e.g. data T10 a = T10 !a !a ...)
  • T25 - a 25 element, strict data type
  • Evil - based upon Data.Vector.Unboxed.Vector, the Evil buffer thaws the vector, mutates a single element, and returns the updated vector.  This buffer is closest to an imperative circular buffer implementation, although it violates referential transparency.  Hence the Evil moniker.
  • ComboBuffer - the ComboBuffer consists of two unboxed vectors and an update list.  After the update last grows large enough, it's frozen into a vector and the oldest data is dropped.  Writing elements is performed in amortized O(1) time.  The read behavior is more complex.
The results are summarized online here.  A few notes about interpreting the results:
  • Given times are the result of a single run, although they are fairly stable over multiple executions.
  • The chart shows times in a log scale to help differentiate times for small buffers.  Otherwise the O(n) behavior of Vector obliterates these differences.
  • Current is the behavior of an algorithm that adaptively selects a buffer type based upon size.
  • All the results (except one) are for reading off the end of the buffer.  For most buffer types this shouldn't matter. It's optimal for Seq.  For the ComboBuffer, reads from the last half of the buffer can be done in O(1), but reads from the first half are more complex, as a list lookup may be required.  The Current - first quarter data is the result of accessing points 0.25 of the way into the buffer.
So for reads from the end of the buffer, my ComboBuffer is pretty good.  It needs some tuning though, especially for reads from near the front of the buffer.

Faking it with higher rank (Existential Quantification pt. 2)

In my previous post I provided a short background on Existential Quantification.  In this post, I'll provide an alternative for some uses and suggest why it may be preferred.

Suppose we want to create a data store that uses lists for small amounts of data, but otherwise uses vectors.  We can easily use E.Q.

import Data.Vector (Vector)
import qualified Data.Vector as V
class Buffer c where
  type El c :: *
  init :: Int -> El c -> c
  (!)  :: c -> Int -> El c
  push :: c -> El c -> c
 
instance Buffer [a] where
  type El [a] = a
  init = replicate
  (!)  = (!!)
  push lst el = el : init lst
 
instance Buffer (Vector a) where
  type El (Vector a) = a
  init = V.replicate
  (!)  = (V.!) 
  push vec el = V.cons el $ V.unsafeInit vec
 
data EBuffer a = forall c. (Buffer c, El c ~ a) => EBuffer c
 
initBuffer :: Int -> EBuffer Double
initBuffer sz
  | sz < 10   = EBuffer (init sz 0 :: [Double])
  | otherwise = EBuffer (init sz 0 :: Vector Double)
 
and now we have our existentially-quantified buffer.

Unfortunately this code doesn't offer anywhere near the hoped-for performance (at least not for the problem that led to this post).  The problem is that now that the actual type of buffer is hidden in the EBuffer data, the compiler is no longer able to inline function calls to (!) or push.  Instead it needs to go through the dictionary methods, adding a lot of extra overhead.  Even worse, a lot of further optimization opportunities are lost.

It turns out that there is another approach that doesn't suffer from this problem.  The approach is based on higher-rank types.  Normal Haskell code uses rank-1 type variables, which means that any variables in a type signature are instantiated by the calling code.  However, with the RankNTypes extension, it's possible to write code of any rank desired.  Consider the function
hr1 :: (forall a. a -> a) -> (Char, Int)
hr1 myId = (myId 'a', myId 0)
The first parameter to hr1 is a rank-2 function.  It needs to be a function that can take an input of any type, and return a value with the same type.  The only total function that can do this is id, and calling hr1 id returns exactly what we would expect.

(What happens if you change the type signature to hr1 :: (a -> a) -> (Char, Int) ? )

Armed with higher-rank types, we can replace the existentially-quantified type in two steps:

1.  Refactor whichever code uses the data so that it's in the form someFunc :: Buffer buf => buf -> AResult.  This part usually isn't too difficult.

2.  Create another function like following:
runWithBuffer
  :: Int
  -> (forall buf. (Buffer buf, El buf ~ Double) => buf -> b)
  -> b
runWithBuffer sz fn
  | sz < 10   = let buf = init sz 0 :: [Double]
                in fn buf
  | otherwise = let buf = init sz 0 :: Vector Double
                in fn buf

With our new runWithBuffer function, we've successfully decoupled the buffer selection algorithm from the usage site without using existential quantification.  Plus, in many cases GHC generates better code with more opportunities for further optimization.

A slightly more extensive example is available in my dsp-extras codebase.  The class and various buffer types are in the Data.RingBuffer modules.  The buffers are used in Language.AuSL.CompileArr, with the function optimizeBufType performing the duties of runWithBuffer.

Saturday, March 24, 2012

Existential Quantification pt. 1

If you have experience with OOP, you're already an expert on existential quantification.  In brief, existential quantification is the reason why you can write code like this pseudocode:

class MyList: 
  private List myList;
  init(Int sz):
    if sz < 10: 
      self.myList = new LinkedList();
    else:
      self.myList = new ArrayList();

In this example the private member variable myList is existentially quantified.  For any instance of MyList, after init is called the compiler knows that a data structure exists and that it implements the List interface, but it doesn't know the exact type of myList.  Any time you declare a variable of an interface type, the data structure referenced by the variable is existentially quantified.

One of the most common uses of existentially quantified data is in implementing the Strategy design pattern, which allows for an algorithm to be selected at runtime.  The MyList class above hints at this usage; for very small lists it uses a LinkedList but otherwise uses an ArrayList.  The idea of selecting an optimal algorithm at runtime based upon some known quantity is very common in high-performance code (e.g. fftw, Atlas, introsort, many others), and existential quantification is a very common way to implement it.

It's very common for programmers with an OOP background to assume that existential quantification and interfaces always go together, which leads to surprise that the following Haskell code doesn't compile:

getNum :: Num a => Char -> a
getNum 'd' = 0 :: Double
getNum _  = 0 :: Int

In OOP languages, this works.  Both Double and Int are instances of Num, and the only promise the type of getNum makes about its output is that it has a Num instance.  However, type variables aren't existentially quantified in Haskell.  This means that, instead of returning whichever Num instance it likes, getNum must be able to provide any Num that the caller demands.

However, thanks to the ExistentialQuantification language extension, e.q. is supported in Haskell (GADTs also provide this feature and more).  It can only be used within new data types however, not bare functions.  So we need to make a wrapper to hold existentially quantified data:
{-# LANGUAGE ExistentialQuantification #-}
data ENum = forall a. Num a => ENum a

getNum :: Char -> ENum
getNum 'd' = ENum (0::Double)
getNum _   = ENum (0::Int)

Now we have our existentially-quantified data, and all is right with the world.  For now.

Tuesday, October 11, 2011

J. Roger Hindley is coming to Maynooth

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!

Friday, September 16, 2011

splaytree package released

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.

Friday, September 2, 2011

My mind is blown


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.

Wednesday, July 6, 2011

Circular Buffers

(A followup with updated results is available)

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.

Friday, May 6, 2011

Linux Audio Conference 2011

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

http://streamer.stackingdwarves.net/

Thursday, May 5, 2011

GTK on OSX

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.

Monday, April 11, 2011

Thoughts on FRP

(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.

Thursday, February 3, 2011

a better audio language

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.

Tuesday, December 14, 2010

installing gtkglext Haskell bindings with gtk-osx

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:
  1. install gtkglext (c library)
  2. install gtk (Haskell package)
  3. 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.

Wednesday, December 9, 2009

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

(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.

Sunday, November 15, 2009

iteratee status

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.

Wednesday, August 12, 2009

Restricted-element containers and maps

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.