24th February 2009, 12:05 am

I have another paper draft for submission to ICFP 2009.
This one is called *Beautiful differentiation*,
The paper is a culmination of the several posts I’ve written on derivatives and automatic differentiation (AD).
I’m happy with how the derivation keeps getting simpler.
Now I’ve boiled extremely general higher-order AD down to a `Functor`

and `Applicative`

morphism.

I’d love to get some readings and feedback.
I’m a bit over the page the limit, so I’ll have to do some trimming before submitting.

The abstract:

Automatic differentiation (AD) is a precise, efficient, and convenient
method for computing derivatives of functions. Its implementation can be
quite simple even when extended to compute all of the higher-order
derivatives as well. The higher-dimensional case has also been tackled,
though with extra complexity. This paper develops an implementation of
higher-dimensional, higher-order differentiation in the extremely
general and elegant setting of *calculus on manifolds* and derives that
implementation from a simple and precise specification.

In order to motivate and discover the implementation, the paper poses
the question “What does AD mean, independently of implementation?” An
answer arises in the form of *naturality* of sampling a function and its
derivative. Automatic differentiation flows out of this naturality
condition, together with the chain rule. Graduating from first-order to
higher-order AD corresponds to sampling all derivatives instead of just
one. Next, the notion of a derivative is generalized via the notions of
vector space and linear maps. The specification of AD adapts to this
elegant and very general setting, which even *simplifies* the
development.

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 have another paper draft for submission to ICFP 2009. This one is called Beautiful differentiation, The paper is a culmination of the several posts I’ve written on derivatives and...

18th February 2009, 06:34 pm

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

4th April 2008, 02:27 pm

I submitted a paper *Simply efficient functional reactivity* to ICFP 2008.

**Abstract:**

Functional reactive programming (FRP) has simple and powerful semantics, but has resisted efficient implementation. In particular, most past implementations have used demand-driven sampling, which accommodates FRP’s continuous time semantics and fits well with the nature of functional programming. Consequently, values are wastefully recomputed even when inputs don’t change, and reaction latency can be as high as the sampling period.

This paper presents a way to implement FRP that combines data- and demand-driven evaluation, in which values are recomputed only when necessary, and reactions are nearly instantaneous. The implementation is rooted in a new simple formulation of FRP and its semantics and so is easy to understand and reason about.

On the road to efficiency and simplicity, we’ll meet some old friends (monoids, functors, applicative functors, monads, morphisms, and improving values) and make some new friends (functional future values, reactive normal form, and concurrent “unambiguous choice”).

I submitted a paper Simply efficient functional reactivity to ICFP 2008. Abstract: Functional reactive programming (FRP) has simple and powerful semantics, but has resisted efficient implementation. In particular, most past...

Tags:

applicative functor,

continuous,

discrete,

events,

FRP,

functional reactive programming,

functor,

future value,

icfp,

implementation,

joinMaybes,

monad,

monoid,

multi-threading,

normal form,

paper,

reactive behavior,

reactive value,

semantics,

time,

type class,

type class morphism,

type composition |

33 Comments
20th November 2007, 08:54 pm

Earlier this month I gave a tech talk at Google, entitled “Tangible Functional Programming: a modern marriage of usability and composability”. Thanks to Google folks, the talk is now up on YouTube. I showed a way make functional programming “tangible” and visual, rather than abstract and syntactic and, in doing so, to fulfill the original Unix vision of simple, composable apps.

The key is to keep an app’s interface and functionality combined and separable. Combined yields usability, and separable yields composability. This principle applies not only to GUI-style interfaces, but to textual IO as well, and it applies to both direct composition and syntactic composition. See the TV page for examples of the latter. The common practice of mixing IO with functionality inhibits composability whether in C or in Haskell.

**Edit 2008-09-09**: The technical/theoretical basis for this tech talk is in the paper Tangible Functional Programming.

Earlier this month I gave a tech talk at Google, entitled “Tangible Functional Programming: a modern marriage of usability and composability”. Thanks to Google folks, the talk is now up...

11th September 2006, 09:26 am

(This is an edited version of a post made on April 11 that somehow became inaccessible from my main blog page.)

I have a draft paper called “Functional Programming by Interacting with Concrete Values”. I’m very excited about this research direction as a way to let people program without turning them into programmers. A concrete form of this goal is enable artists to make and share their own software tools (parameterized image effects), while staying in an artistic creative mode.

An excerpt from the introduction:

Suppose *users* of interactive programs could also create such programs with a simple extension of their current style of interaction. First, such a development would enable many more people to create and share computational content. Second, it would allow this content to be created without imposing the abstract, linguistic mode of creativity. This freedom may give birth to new kinds of programs whose creation is nurtured by a concrete and visual environment.

Comments please (related work, ideas, typos, unclear bits, etc)!

**Edit 2008-04-17**: The paper didn’t get accepted in 2006. Thanks to very helpful review comments, and a lot of rewriting, the paper did get accepted in 2007, under the title “Tangible functional programming”.

(This is an edited version of a post made on April 11 that somehow became inaccessible from my main blog page.) I have a draft paper called “Functional Programming by...