Garbage collecting the semantics of FRP

Ever since ActiveVRML, the model we’ve been using in functional reactive programming (FRP) for interactive behaviors is (T->a) -> (T->b), for dynamic (time-varying) input of type a and dynamic output of type b (where T is time). In “Classic FRP” formulations (including ActiveVRML, Fran & Reactive), there is a “behavior” abstraction whose denotation is a function of time. Interactive behaviors are then modeled as host language (e.g., Haskell) functions between behaviors. Problems with this formulation are described in Why classic FRP does not fit interactive behavior. These same problems motivated “Arrowized FRP”. In Arrowized FRP, behaviors (renamed “signals”) are purely conceptual. They are part of the semantic model but do not have any realization in the programming interface. Instead, the abstraction is a signal transformer, SF a b, whose semantics is (T->a) -> (T->b). See Genuinely Functional User Interfaces and Functional Reactive Programming, Continued.

Whether in its classic or arrowized embodiment, I’ve been growing uncomfortable with this semantic model of functions between time functions. A few weeks ago, I realized that one source of discomfort is that this model is mostly junk.

This post contains some partially formed thoughts about how to eliminate the junk (“garbage collect the semantics”), and what might remain.

Continue reading ‘Garbage collecting the semantics of FRP’ »

3D rendering as functional reactive programming

Another angle on functional future values

An earlier post introduced functional future values, which are values that cannot be known until the future, but can be manipulated in the present. That post presented a simple denotational semantics of future values as time/value pairs. With a little care in the definition of Time (using the Max monoid), the instances of Functor, Applicative, Monad are all derived automatically.

A follow-up post gave an implementation of Future values via multi threading. Unfortunately, that implementation did not necessarily satisfy the semantics, because it allowed the nondeterminism of thread scheduling to leak through. Although the implementation is usually correct, I wasn’t satisfied.

After a while, I hit upon an idea that really tickled me. My original simple semantics could indeed serve as a correct and workable implementation if I used a subtler form of time that could reveal partial information. Implementing this subtler form of time turned out to be quite tricky, and was my original motivation for the unamb operator described in the paper Push-pull functional reactive programming and the post Functional concurrency with unambiguous choice.

It took me several days of doodling, pacing outside, and talking to myself before the idea for unamb broke through. Like many of my favorite ideas, it’s simple and obvious in retrospect: to remove the ambiguity of nondeterministic choice (as in the amb operator), restrict its use to values that are equal when non-bottom. Whenever we have two different methods of answering the same question (or possibly failing), we can use unamb to try them both. Failures (errors or non-termination) are no problem in this context. A more powerful variation on unamb is the least upper bound operator lub, as described in Merging partial values.

I’ve been having trouble with the unamb implementation. When two (compatible) computations race, the loser gets killed so as to free up cycles that are no longer needed. My first few implementations, however, did not recursively terminate other threads spawned in service of abandoned computations (from nested use of unamb). I raised this problem in Smarter termination for thread racing, which suggested some better definitions. In the course of several helpful reader comments, some problems with my definitions were addressed, particularly in regard to blocking and unblocking exceptions. None of these definitions so far has done the trick reliably, and now it looks like there is a bug in the GHC run-time system. I hope the bug (if there is one) will be fixed soon, because I’m seeing more & more how unamb and lub can make functional programming even more modular (just as laziness does, as explained by John Hughes in Why Functional Programming Matters).

I started playing with future values and unambiguous choice as a way to implement Reactive, a library for functional reactive programming (FRP). (See Reactive values from the future and Push-pull functional reactive programming.) Over the last few days, I’ve given some thought to ways to implement future values without unambiguous choice. This post describes one such alternative.

Edits:

Continue reading ‘Another angle on functional future values’ »

Functional interactive behavior

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’ »

Trimming inputs in functional reactive programming

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’ »

Why classic FRP does not fit interactive behavior

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’ »

Sequences, segments, and signals

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

infinitefinite
discreteStream Sequence
continuousFunction ???

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’ »