Streams are live now. Check it out if you couldn't make it in person.
http://streamer.stackingdwarves.net/
Friday, May 6, 2011
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.
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.
Introduction
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
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:
and we've got it. If we prefer, we could define
So how does this work? The
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
Our implementation created a
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.
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
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:
The
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.
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,pureis defined asalways) - the
behaviorsmart constructor (only hold the most recentEvent) - various
accumulatefunctions onEvents
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:
What if the delayr generates a token, which is then required by all functions that want to use it?
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.
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.
aNull delayr 2
atap deltap 1
delayw asig
What if the delayr generates a token, which is then required by all functions that want to use it?
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:
-- Haskell-mode now
myDelay asig = do
(dtok, _) <- delayr 2 adelay <- deltap dtok 1 delayw dtok asig return adelay
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.
-- 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
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:
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.
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.
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:
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:
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.
- install gtkglext (c library)
- install gtk (Haskell package)
- install gtkglext (Haskell package)
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.
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.
jhbuild shell
cabal unpack gtk
cd gtk
patch -p1 < gtk.patch
cabal install
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
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:
And you should get a new window with a colorful cube, spinning in full OpenGL glory.
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
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):
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.
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();
ListSetevents = 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.
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.
Subscribe to:
Posts (Atom)