Archive for November 2008

Sequences, streams, and segments

What kind of thing is a movie? Or a song? Or a trajectory from point A to point B? If you’re a computer programmer/programmee, you might say that such things are sequences of values (frames, audio samples, or spatial locations). I’d suggest that these discrete sequences are representations of something more essential, namely a flow of continuously time-varying values. Continuous models, whether in time or space, are often more compact, precise, adaptive, and composable than their discrete counterparts.

Functional programming offers great support for sequences of variable length. Lazy functional programming adds infinite sequences, often called streams, which allows for more elegant and modular programming.

Functional programming also has functions as first class values, and when the function’s domain is (conceptually) continuous, we get a continuous counterpart to infinite streams.

Streams, sequences, and functions are three corners of a square. Streams are discrete and infinite, sequences are discrete and finite, and functions-on-reals are continuous and infinite. The missing corner is continuous and finite, and that corner is the topic of this post.

infinitefinite
discreteStream Sequence
continuousFunction ???

You can download the code for this post.

Edits:

  • 2008-12-01: Added Segment.hs link.
  • 2008-12-01: Added Monoid instance for function segments.
  • 2008-12-01: Renamed constructor “DF” to “FS” (for “function segment”)
  • 2008-12-05: Tweaked the inequality in mappend on (t :-># a).

Continue reading ‘Sequences, streams, and segments’ »

Early inspirations and new directions in functional reactive programming

In 1989, I was a grad student nearing completion at Carnegie Mellon. Kavi Arya gave a talk on “functional animation”, using lazy lists. I was awe-struck with the elegance and power of that simple idea, and I’ve been hooked on functional animation ever since.

At the end of Kavi’s talk, John Reynolds offered a remark, roughly as follows:

You can think of sequences as functions from the natural numbers. Have you thought about functions from the reals instead? Doing so might help with the awkwardness with interpolation.

I knew at once I’d heard a wonderful idea, so I went back to my office, wrote it down, and promised myself that I wouldn’t think about Kavi’s work and John’s insight until my dissertation was done. Otherwise, I might never have finished. A year or so later, at Sun Microsystems, I started working on functional animation, which then grew into functional reactive programming (FRP).

In the dozens of variations on FRP I’ve played with over the last 15 years, John’s refinement of Kavi’s idea has always been the heart of the matter for me.

Lately, I’ve been rethinking FRP yet again, and I’m very excited about where it’s leading me.

The semantic model of FRP has been based on behaviors of infinite duration and, mostly on absolute time. Recently I realized that some problems of non-modular interaction could be elegantly addressed by switching to finite duration and relative time, and by adopting a co-monadic approach.

Upcoming post will explore these ideas.

Semantic editor combinators

While working on Eros, I encountered a function programming pattern I hadn’t known. I was struck by the simplicity and power of this pattern, and I wondered why I hadn’t run into it before. I call this idea “semantic editor combinators”, because it’s a composable way to create transformations on rich values. I’m writing this post in order to share this simple idea, which is perhaps “almost obvious”, but not quite, due to two interfering habits:

  • thinking of function composition as binary instead of unary, and
  • seeing the functions first and second as about arrows, and therefore esoteric.

What I enjoy most about these (semantic) editor combinators is that their use is type-directed and so doesn’t require much imagination. When I have the type of a complex value, and I want to edit some piece buried inside, I just read off the path in the containing type, on the way to the buried value.

I started writing this post last year and put it aside. Recent threads on the Reactive mailing list (including a dandy explanation by Peter Verswyvelen) and on David Sankel’s blog reminded me of my unfinished post, so I picked it up again.

Edits:

  • 2008-11-29: added type of v6 example. Tweaked inO2 alignment.

Continue reading ‘Semantic editor combinators’ »

Merging partial values

Last year I stumbled across a simple representation for partial information about values, and wrote about it in two posts, A type for partial values and Implementing a type for partial values. Of particular interest is the ability to combine two partial values into one, combining the information present in each one.

More recently, I played with unambiguous choice, described in the previous post.

This post combines these two ideas. It describes how to work with partial values in Haskell natively, i.e., without using any special representation and without the use restrictions of unambiguous choice. I got inspired to try removing those restrictions during stimulating discussions with Thomas Davie, Russell O’Connor others in the #haskell gang.

You can download and play with the library shown described here. There are links and a bit more info on the lub wiki page.

Edits:

Continue reading ‘Merging partial values’ »

Functional concurrency with unambiguous choice

The Reactive library implements functional reactive programming (FRP) in a data-driven and yet purely functional way, on top of a new primitive I call “unambiguous choice”, or unamb. This primitive has simple functional semantics and a concurrent implementation. The point is to allow one to try out two different ways to answer the same question, when it’s not known in advance which one will succeed first, if at all.

This post describes and demonstrates unamb and its implementation.

Continue reading ‘Functional concurrency with unambiguous choice’ »

Enhancing a Zip

This post is part four of the zip folding series inspired by Max Rabkin’s Beautiful folding post. I meant to write one little post, but one post turned into four. When I sense that something can be made simpler/clearer, I can’t leave it be.

To review:

  • Part One related Max’s data representation of left folds to type class morphisms, a pattern that’s been steering me lately toward natural (inevitable) design of libraries.
  • Part Two simplified that representation to help get to the essence of zipping, and in doing so lost the expressiveness necessary to define Functorand Applicative instaces.
  • Part Three proved the suitability of the zipping definitions in Part Two.

This post shows how to restore the Functor and Applicative (very useful composition tools) to folds but does so in a way that leaves the zipping functionality untouched. This new layer is independent of folding and can be layered onto any zippable type.

You can get the code described below.

Edits:

  • 2009-02-15: Simplified WithCont, collapsing two type parameters into one. Added functor comment about cfoldlc'.

Continue reading ‘Enhancing a Zip’ »

Proofs for left fold zipping