Conal Elliott

I realized in the shower this morning that there’s a serious flaw in my unamb implementation as described in Functional concurrency with unambiguous choice. Here’s the code for racing two computations:

race :: IO a -> IO a -> IO a
a `race` b = do v  < - newEmptyMVar
                ta <- forkPut a v
                tb <- forkPut b v
                x  <- takeMVar  v
                killThread ta
                killThread tb
                return x
 
forkPut :: IO a -> MVar a -> IO ThreadId
forkPut act v = forkIO ((act >>= putMVar v) `catch` uhandler `catch` bhandler)
 where
   uhandler (ErrorCall "Prelude.undefined") = return ()
   uhandler err                             = throw err
   bhandler BlockedOnDeadMVar               = return ()

The problem is that each of the threads ta and tb may have spawned other threads, directly or indirectly. When I kill them, they don’t get a chance to kill their sub-threads. If the parent thread does get killed, it will most likely happen during the takeMVar.

My first thought was to use some form of garbage collection of threads, perhaps akin to Henry Baker’s paper The Incremental Garbage Collection of Processes. As with memory GC, dropping one consumer would sometimes result is cascading de-allocations. That cascade is missing from my implementation above.

Or maybe there’s a simple and dependable manual solution, enhancing the method above.

I posted a note asking for ideas, and got the following suggestion from Peter Verswyvelen:

I thought that killing a thread was basically done by throwing a ThreadKilled exception using throwTo. Can’t these exception be caught?

In C#/F# I usually use a similar technique: catch the exception that kills the thread, and perform cleanup.

Playing with Peter’s suggestion works out very nicely, as described in this post.

Continue reading ‘Smarter termination for thread racing’ »

: http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/ "blog post" : ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-454.pdf "Paper by Henry Baker" : http://conal.net/blog/posts/semantic-editor-combinators/ "blog post" I realized in the shower this morning that there's a serious flaw in my unamb implementation as described in **. Here's the code for racing two computations: ...

In a previous post, I presented a fundamental reason why classic FRP does not fit interactive behavior, which is that the semantic model captures only the influence of time and not other input. I also gave a simple alternative, with a simple and general model for temporal and spatial transformation, in which input behavior is transformed inversely to the transformation of output behavior.

The semantic model I suggested is the same as used in “Arrow FRP”, from Fruit and Yampa. I want, however, a more convenient and efficient way to package up that model, which is the subject of the post you are reading now.

Next, we took a close look at one awkward aspect of classic FRP for interactive behavior, namely the need to trim inputs, and how trimming relates to comonadic FRP. The trim function allows us to define multi-phase interactive behaviors correctly and efficiently, but its use is tedious and is easy to get wrong. It thus fails to achieve what I want from functional programming in general and FRP in particular, which is to enable writing simple, natural descriptions, free of mechanical details.

The current post hides and automates the mechanics of trimming, so that the intent of an interactive behavior can be expressed directly and executed correctly and efficiently.

Continue reading ‘Functional interactive behavior’ »

: http://conal.net/blog/posts/why-classic-FRP-does-not-fit-interactive-behavior/ "blog post" : http://conal.net/blog/posts/trimming-inputs-in-functional-reactive-programming/ "blog post" : http://conal.net/papers/genuinely-functional-guis.pdf "Paper: "Genuinely Functional User Interfaces"" : http://haskell.org/haskellwiki/Yampa "Wiki page" : http://www.haskell.org/yale/papers/haskellworkshop02 "paper by Henrik Nilsson, Antony Courtney, and John Peterson" : http://conal.net/blog/posts/simply-efficient-functional-reactivity/ "blog post" : http://www.haskell.org/yale/papers/pldi00/ "Paper ...

This post takes a close look at one awkward aspect of classic (non-arrow) FRP for interactive behavior, namely the need to trim (or “age”) old input. Failing to trim results in behavior that is incorrect and grossly inefficient.

Behavior trimming connects directly into the comonad interface mentioned in a few recent posts, and is what got me interested in comonads recently.

In absolute-time FRP, trimming has a purely operational significance. Switching to relative time, trimming is recast as a semantically familiar operation, namely the generalized drop function used in two recent posts.

Continue reading ‘Trimming inputs in functional reactive programming’ »

: http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Applicative.html "Haskell module documentation" : http://conal.net/blog/posts/semantic-editor-combinators/ "blog post" : http://conal.net/blog/posts/sequences-functions-and-segments/ "blog post" : http://conal.net/blog/posts/sequences-segments-and-signals/ "blog post" : http://conal.net/blog/posts/why-classic-FRP-does-not-fit-interactive-behavior/ "blog post" This post takes a close look at one awkward aspect of *classic* (non-arrow) FRP for interactive behavior, namely the need to *trim* (or ...

In functional reactive programming (FRP), the type we call “behaviors” model non-interactive behavior. To see why, just look at the semantic model: t -> a, for some notion t of time.

One can argue as follows that this model applies to interactive behavior as well. Behaviors interacting with inputs are functions of time and of inputs. Those inputs are also functions of time, so behaviors are just functions of time. I held this perspective at first, but came to see a lack of composability.

My original FRP formulations (Fran and its predecessors TBAG and ActiveVRML), as well as the much more recent library Reactive, can be and are used to describe interactive behavior. For simple sorts of things, this use works out okay. When applications get a bit richer, the interface and semantics strain. If you’ve delved a bit, you’ll have run into the signs of strain, with coping mechanisms like start times, user arguments and explicit aging of inputs, as you avoid the dreaded space-time leaks.

Continue reading ‘Why classic FRP does not fit interactive behavior’ »

: http://conal.net/Fran "Functional reactive animation" : http://conal.net/tbag/ ...

The post Sequences, streams, and segments offered an answer to the the question of what’s missing in the following box:

I presented a simple type of function segments, whose representation contains a length (duration) and a function. This type implements most of the usual classes: Monoid, Functor, Zip, and Applicative, as well Comonad, but not Monad. It also implements a new type class, Segment, which generalizes the list functions length, take, and drop.

The function type is simple and useful in itself. I believe it can also serve as a semantic foundation for functional reactive programming (FRP), as I’ll explain in another post. However, the type has a serious performance problem that makes it impractical for some purposes, including as implementation of FRP.

Fortunately, we can solve the performance problem by adding a simple layer on top of function segments, to get what I’ll call “signals”. With this new layer, we have an efficient replacement for function segments that implements exactly the same interface with exactly the same semantics. Pleasantly, the class instances are defined fairly simply in terms of the corresponding instances on function segments.

You can download the code for this post.

Edits:

• 2008-12-06: dup [] = [] near the end (was [mempty]).
• 2008-12-09: Fixed take and drop default definitions (thanks to sclv) and added point-free variant.
• 2008-12-18: Fixed appl, thanks to sclv.
• 2011-08-18: Eliminated accidental emoticon in the definition of dup, thanks to anonymous.

Continue reading ‘Sequences, segments, and signals’ »

: http://conal.net/blog/posts/sequences-streams-and-segments/ "blog post" : http://conal.net/blog/posts/prettier-functions-for-wrapping-and-wrapping/ "blog post" : http://conal.net/blog/posts/semantic-editor-combinators/ "blog post" : http://conal.net/blog/tag/type-class-morphism/ "Posts on type class morphisms" : http://conal.net/blog/posts/simplifying-semantics-with-type-class-morphisms "blog post" : http://haskell.org/haskellwiki/Reactive "Wiki page for the Reactive library" : http://cs.ioc.ee/~tarmo/papers/essence.pdf "Paper by Tarmo Uustalu and ...

The post Semantic editor combinators gave an example of a pattern that comes up a lot for me in Haskell programming. I want to apply functions inside of a newtype without cumbersome unwrapping and wrapping of the representation insides.

While chatting with Daniel Peebles in #haskell today, the realization hit me that these “higher-order wrappers” can not only make other code pretty, but can themselves be expressed more beautifully and clearly, using two of the combinators given in that post.

Continue reading ‘Prettier functions for wrapping and wrapping’ »

: http://conal.net/blog/posts/semantic-editor-combinators/ "blog post" : http://haskell.org/haskellwiki/TypeCompose "Wiki page" The post ** gave an example of a pattern that comes up a lot for me in Haskell programming. I want to apply functions inside of a `newtype` without cumbersome unwrapping and wrapping of the representation insides. While chatting with Daniel Peebles in #haskell today, the ...