Conal Elliott

The central question for me in designing software is always

What does it mean?

With functional programming, this question is especially crisp. For each data type I define, I want to have a precise and simple mathematical model. (For instance, my model for behavior is function-of-time, and my model of images is function-of-2D-space.) Every operation on the type is also given a meaning in terms of that semantic model.

This specification process, which is denotational semantics applied to data types, provides a basis for

• correctness of the implementation,
• user documentation free of implementation detail,
• generating and proving properties, which can then be used in automated testing, and
• evaluating and comparing the elegance and expressive power of design decisions.

For an example (2D images), some motivation of this process, and discussion, see Luke Palmer’s post Semantic Design. See also my posts on the idea and use of type class morphisms, which provide additional structure to denotational design.

In spring of 2008, I started working on a functional 3D library, FieldTrip. I’ve designed functional 3D libraries before as part of TBAG, ActiveVRML, and Fran. This time I wanted a semantics-based design, for all of the reasons given above. As always, I want a model that is

• simple,
• elegant, and
• general.

For 3D, I also want the model to be GPU-friendly, i.e., to execute well on (modern) GPUs and to give access to their abilities.

I hadn’t thought of or heard a model that I was happy with, and so I didn’t have the sort of firm ground I like to stand on in working on FieldTrip. Last February, such a model occurred to me. I’ve had this blog post mostly written since then. Recently, I’ve been focused on functional 3D again for GPU-based rendering, and then Sean McDirmid posed a similar question, which got me thinking again.

Continue reading ‘Thoughts on semantics for 3D graphics’ »

The central question for me in designing software is always What does it mean? With functional programming, this question is especially crisp. For each data type I define, I want...

I’ve just finished a draft of a paper called Denotational design with type class morphisms, for submission to ICFP 2009. The paper is on a theme I’ve explored in several posts, which is semantics-based design, guided by type class morphisms.

I’d love to get some readings and feedback. Pointers to related work would be particularly appreciated, as well as what’s unclear and what could be cut. It’s an entire page over the limit, so I’ll have to do some trimming before submitting.

The abstract:

Type classes provide a mechanism for varied implementations of standard interfaces. Many of these interfaces are founded in mathematical tradition and so have regularity not only of types but also of properties (laws) that must hold. Types and properties give strong guidance to the library implementor, while leaving freedom as well. Some of the remaining freedom is in how the implementation works, and some is in what it accomplishes.

To give additional guidance to the what, without impinging on the how, this paper proposes a principle of type class morphisms (TCMs), which further refines the compositional style of denotational semantics. The TCM idea is simply that the instance’s meaning is the meaning’s instance. This principle determines the meaning of each type class instance, and hence defines correctness of implementation. In some cases, it also provides a systematic guide to implementation, and in some cases, valuable design feedback.

The paper is illustrated with several examples of type, meanings, and morphisms.

You can get the paper and see current errata here.

The submission deadline is March 2, so comments before then are most helpful to me.

Enjoy, and thanks!

I’ve just finished a draft of a paper called Denotational design with type class morphisms, for submission to ICFP 2009. The paper is on a theme I’ve explored in several...

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

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

This note continues an exploration of arrow-friendly formulations of functional reactive programming. I refine the previous representations into an interactive dance with dynamically interchanging roles of follow and lead. These two roles correspond to the events and reactive values in the (non-arrow) library Reactive described in a few previous posts. The post ends with some examples.

The code described (with documentation and examples) here may be found in the new, experimental library Bot (which also covers mutant-bots and chatter-bots).

Continue reading ‘Functional reactive partner dancing’ »

This note continues an exploration of arrow-friendly formulations of functional reactive programming. I refine the previous representations into an interactive dance with dynamically interchanging roles of follow and lead. These...

In a few recent posts, I’ve been writing about a new basis for functional reactive programming (FRP), embodied in the Reactive library. In those posts, events and reactive values are (first class) values. A reactive system able to produce outputs from inputs might have type Event a -> Event b or perhaps Reactive a -> Reactive b.

Although I’m mostly happy with the simplicity and expressiveness of this new formulation, I’ve also been thinking about arrow-style formulations, as in Fruit and Yampa. Those systems expose signal functions in the programming interface, but relegate events and time-varying values (called “behaviors” in Fran and “signals” in Fruit and Yampa) to the semantics of signal functions.

If you’re not familiar with arrows in Haskell, you can find some getting-started information at the arrows page.

This post explores and presents a few arrow-friendly formulations of reactive systems.

Edits:

• 2008-02-06: Cleaned up the prose a bit.
• 2008-02-09: Simplified chatter-bot filtering.
• 2008-02-09: Renamed for easier topic recognition (was “Invasion of the composable Mutant-Bots”).
• 2008-02-10: Replaced comps by the simpler concatMB for sequential chatter-bot composition.

Continue reading ‘Functional reactive chatter-bots’ »

In a few recent posts, I’ve been writing about a new basis for functional reactive programming (FRP), embodied in the Reactive library. In those posts, events and reactive values are...

I just submitted the camera-ready version of “Tangible Functional Programming”, for ICFP ’07. I’m happy with this version. It’s improved drastically since my first submission to ICFP ’06, thanks to many helpful comments. I’ve also been recreating the implementation on top of DeepArrow, Phooey, and TV, in preparation for a software release. It’s getting simpler, but it’s not as simple as I want.

I just submitted the camera-ready version of “Tangible Functional Programming”, for ICFP ’07. I’m happy with this version. It’s improved drastically since my first submission to ICFP ’06, thanks to...