I have a new blog

I changed blog engines and sites, for reasons described in my previous post here. The new blog is already on Planet Haskell, but if you track my blog some other way, please switch to the new one. I'm very happy with my new set-up, which is much friendlier to Haskell code.

Blogging and formatted code

I'd like to hear from anyone who is happy with their blogging engine's treatment of code. I use Blogger, and it strips leading spaces from each line of my code on every edit/preview pass. I lose alignment, and eventually, all the code ends up at the left margin.

Tangible Functional Programming: a modern marriage of usability and composability

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.

"Tangible Functional Programming" -- icfp version

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.

Implementing a type for partial values

(Edit 2008-01-14: updated formatting.)

In my previous post, I gave an interface for a type of "partial values" and invited implementations. Here's mine, which surprised me in its simplicity. The whole module is online.

The trick is to represent Partial a as a -> a, i.e., a way to selectively replace parts of a value. Typically the replaced parts are bottom/undefined. I want Partial a to be a monoid, and Data.Monoid provides an instance:

-- | The monoid of endomorphisms under composition.
newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
 mempty = Endo id
 Endo f `mappend` Endo g = Endo (f . g)

So my definition is simply a synonym:

type Partial = Endo

Note that mempty and mappend do exactly what I want. mempty adds no information at all, while u `mappend` v adds (overrides) information with u and then with v.

The implementation of functions on Partial is trivial.

-- | Convenience for partial-manipulating functions
inPartial :: ((a->a) -> (a'->a')) -> (Partial a -> Partial a')
inPartial f = Endo . f . appEndo

valp :: c -> Partial c
valp c = Endo (const c)

pval :: Partial c -> c
pval (Endo f) = f undefined
unFst :: Partial a -> Partial (a,b)
unFst = inPartial first

unSnd :: Partial b -> Partial (a,b)
unSnd = inPartial second

unElt :: Functor f => Partial a -> Partial (f a)
unElt = inPartial fmap

I'm not sure I'll end up using the Partial type in Eros, but I like having it around. If you think of variations, extensions and/or other uses, please let me know.

A type for partial values

(Edit 2008-01-14: updated formatting.)

In simplifying my Eros implementation, I came across a use for a type that represents partial information about values. I came up with a very simple implementation, though perhaps not quite ideal. In this post, I'll present the interface and invite ideas for implementation. In the next post, I'll give the implementation I use.

First the type:

type Partial a

I require that Partial a be a monoid, for which mempty is the completely undefined value, and in u `mappend` v, v selectively replaces parts of u. (Lattice-wise, mempty is bottom, and mappend is not quite lub, as it lacks commutativity).

Now the programming interface:

-- | Treat a full value as a partial one.  Fully overrides any
-- "previous" (earlier argument to mappend) partial value.
valp :: c -> Partial c

-- | Force a partial value into a full one, filling in bottom for any
-- missing parts.
pval :: Partial c -> c

-- | Inverse to fst, on partial values.  Inject info into the
-- the first half of a pair, and leave the second half alone.
unFst :: Partial a -> Partial (a,b)

-- | Inverse to snd.
unSnd :: Partial b -> Partial (a,b)

-- | Inverse to "element" access, on all elements.  A way to
-- inject some info about every element.  For f, consider
-- [], (->) a, Event, etc.
unElt :: Functor f => Partial a -> Partial (f a)

That's it. I'd love to hear ideas for representing Partial a and implementing the functions above. In the next post, I'll give mine.

(July 3 edit: tweaked some indentation.)

Paper draft: "Applicative Data-Driven Computation"

I would love to get comments on a short (4.5 page) paper draft called "Applicative Data-Driven Computation" (Haskell wiki page), which describes a very simple approach to data-driven (push-based) computation and its application to GUI programming. There's a "Talk page" link for discussion. I'm also very interested in suggestions and (better yet) collaboration on other applications of data-driven computation beyond GUIs, say push-based internet apps.

Software releases: TypeCompose, Phooey, GuiTV

Three related software releases. I am very interested in comments and contributions. TypeCompose provides some classes & instances for forms of type composition. It also includes a very simple implementation of data-driven computation. I factored it out of a new implementation of Phooey. Phooey is a library for functional user interfaces. Highlights in this 0.3 release:

• Uses new TypeCompose package, which includes a simple implementation of data-driven computation.
• New Applicative functor interface.
• Eliminated the catch-all Phooey.hs module. Now import any one of Graphics.UI.Phooey.{Monad ,Applicative,Arrow}.
• Phooey.Monad has two different styles of output widgets, made by owidget and owidget'. The latter is used to implement Phooey.Applicative.
• Self- and mutually-recursive widgets now work again in Phooey.Monad. They wedge in Phooey.Arrow and Phooey.Applicative.

Phooey is also used in GuiTV, a library for composable interfaces and "tangible values". I've also just updated GuiTV to 0.3, to sync with Phooey 1.0.

ICFP '07 paper draft -- comments please

Warning: if you're on the ICFP program committee and want to preserve double-blind reviewing, please ignore this post. I've been working on an ICFP paper called “Tangible Functional Programming”, revising my last year's submission on Eros. If you're interested in taking a look, I'd greatly appreciate any comments, especially before the April 6 submission deadline. Abstract

We present a user-friendly approach to unifying program creation and execution, based on a notion of “tangible values” (TVs), which are visible and interactive GUI manifestations of pure values. Programming happens by gestural composition of TVs. Our goal is to give end-users the ability to create parameterized, composable content without imposing the usual abstract and linguistic working style of programmers. We hope that such a system will put the essence of programming into the hands of many more people, and in particular people with artistic/visual creative style.

In realizing this vision, we develop algebras for visual presentation and for “deep” function application, where function and argument may both be nested within a structure of tuples, functions, etc. Composition gestures are translated into chains of combinators that act simultaneously on statically typed values and their visualizations.

Here is a figure from the paper, showing one stage of an interactively composed interactive 2D region. The user selects compatibly-typed input and output widgets, typically in different TVs. The result is a new TV that merges the source TVs, except for the connected input and output, which vanish. The sliders control the disk and checker sizes and the checker's rotation angle.

Edit on March 28:I just added two relevant pointers to the paper's web page:

• The TV library page
• The DeepArrow library page

separating IO from logic -- example

This post is a teaser for an article in my TiddlyWiki-based journal. The article illustrates an approach to separating logic and IO using the TV library. The TV approach clarifies the pure logic part and the IO part and is more conveniently composable than the mixed logic/IO formulation. I've just released TV-0.2, which omits GUI functionality. That functionality is now present in the small new package GuiTV. The reason for this split is that the GUI support depends on wxHaskell, which currently can be difficult to install. Only TV (not GuiTV) is needed for this example. See the article here. Technorati tags: FunctionalProgramming, Haskell, Modularity, DeclarativeInterfaces. Edit of Feb 13: If you tried the TiddlyWiki article in Opera and got an error, please try again. Problem fixed. (Slight difference in regexp handling in Opera vs FF & IE.) Edit of March 5: This article was inspired by an example in Don Stewart's "Programming Haskell" post.

Software releases

Last week I released three Haskell libraries: DeepArrow 0.0, Phooey 0.1, and TV 0.0. These libraries came from Eros, which aims at creating a right-brain-friendly (concrete, non-linguistic) "programming" process. I've had a growing intuition over the last fifteen years that media authoring tools can be usefully looked at as environments for functional programming. I'd been wondering how to map a user's gestures into operations on a functional program. Lots of noodling led to ideas of composable interfaces and "tangible values" (term thanks to Sean Seefried) and gestural composition in Eros. Eros is more complicated than I like, so I started splitting it into pieces:

• Phooey is a functional GUI library that has much of Eros's GUI implementation techniques, but much more carefully structured than in the Eros paper.
• DeepArrow has the general notion of "deep application"
• TV has the algebra of composable interfaces, or visualizations of pure values, and it has tangible values, which are separable combinations of interface and value. It uses Phooey to generate GUIs very simply from interfaces

Although these libraries came from Eros, I'd like to see other applications as well. Where am I going with library development?

• Figure out how to support simple GUIs and Eros's gesturally composable GUIs, without code/library replication.
• Re-implement Eros on top of simpler pieces.
• Refactor Pajama into reusable libraries and release.
  • Building and optimizing "expressions"
  • Common sub-expression elimination
  • Generation of Java code
  • Perhaps other back-ends besides Java
  • Pajama, on top of these pieces

Technorati tags: FunctionalProgramming, Haskell, Libraries, DeclarativeInterfaces, FunctionalGUIs, Reuse. Edit of March 5, 2007: TV is now split into a core TV package, with no GUI functionality, and GuiTV, with Phooey-based GUI creation. The reason for the split is that Phooey depends on wxHaskell, which can be difficult to install.

New Pajama wiki

I set up a new wiki for Pajama (interactive, continuous, web-embeddable images). Please try it out and leave comments on the wiki or email them to me. I'm very interested in help with Pajama, particularly:

• Replacing the remaining old code from Pan (done while I was at Microsoft Research). Most of the code has been rewritten and simplified, including the complicated code motion stuff (common subexpression elimination and loop hoisting), code generation (nicely exploiting Java), and GUI construction.
• Getting it whipped into shape to be a open source project.
• Applying the (domain-independent) compiler to other domains (sound, 3D, ...).
• Improvements to the wiki, including easier uploading of examples and automatic generation of galleries.
• Integration of Pajama and Eros (end-user syntax-free authoring of functional prorams).

On wiki software selection: After looking around at different engines, including a visit to #wiki and WikiMatrix, I picked MoinMoin. It satisfies my requirements nicely: Java applet embedding (as generated by the Pajama compiler), free, wysiwyg page editing and a friendly implementation/extension language, namely Python. Then I started learning Python, which is a reasonably nice programming language for customizing the wiki server. My first Python program is a wiki macro that makes it fairly easy to embed Pajama effects in a wiki page.

Technorati tags: Pajama, FunctionalProgramming, Haskell, GraphicsProgramming, InfiniteGraphics, wiki.

Non-syntactic, end-user, 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 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)! Technorati tags: EndUserProgramming, TangibleValues, FunctionalProgramming

P.S. to "Pajama site improved"

Please see this this January post for an overview of Pajama. Pajama now runs on Java 1.4 and up, not just 1.5, thanks to Retroweaver, a class file rewriter.

Technorati tags: Pajama, FunctionalProgramming, Haskell, GraphicsProgramming.

Pajama site improved

The Pajama site is much prettier & friendlier now, thanks to Holly. She organized the image effects into several groups (with overlap), chose settings to show them off, and added “toy tips” suggesting what to try. I would love to get comments and suggestions.

Technorati tags: Pajama, FunctionalProgramming, Haskell, GraphicsProgramming.

Unifying and generalizing spatial transformation

(Edit 2008-01-14: updated formatting.)

I’m trying out an idea I had a while back for unifying and generalizing different notions of spatial transformation in Pan (and spatial & temporal transformation in Fran. The three notions are transforming a point, an image (which is a function from point to alpha), and an image filter (which is a function from image to image). A basic “transform” is a function from points to points. To transform a point, just apply the function. To transform an image, inversely transform the points fed into the image. To transform a filter, inversely transform the source image and forward transform the result image.

type VectorE       = (DoubleE,DoubleE)
type PointE        = (DoubleE, DoubleE)
type Image c       = PointE -> c
type HyperFilter c = Filter c -> Filter c

Then for instance, scaling has these three variants:

scaleP :: VectorE -> TransformE
scaleP (sx,sy) = \ (x,y) -> (sx * x, sy * y)

scale :: VectorE -> Filter c
scale (sx,sy) = (. scaleP (1/sx, 1/sy))

atScale :: VectorE -> HyperFilter c
atScale (sx,sy) xf =
  scale (sx,sy) . xf . scale(1/sx,1/sy)

Hyperfilters allow some beautifully modular formulations of filters.

Note how in scale and atScale, I’m inverting the scaling. Exactly this pattern of inversion happens for other types of transformations as well (translation, rotation, swirl, etc). The new idea is to capture this inversion pattern once in a general rule for transforming functions. A type class specifies types that can be spatially transformed, which is direct for points, a do-nothing for numbers and booleans, distributes over tupling, and works similarly to atScale above for functions. To make this fly, I’m changing my representation of points and vectors from pairs to data types, which makes the code less succinct but is more strongly typed.

There’s a big catch in this plan: I only know how to handle invertible transformations, which rules out, e.g., tiling.

Here’s the class of transformable values:

class ITrans a where
  iTrans :: ITransformE -> a -> a

and the handling of functions:

instance (ITrans a, ITrans b) => ITrans (a->b) where
iTrans xf f = iTrans xf . f . iTrans (invIT xf)

The type of invertible transforms simply has a pair of transforms:

data ITransformE =
  ITransformE { itForward  :: TransformE
              , itBackward :: TransformE }

invIT :: ITransformE -> ITransformE
invIT (ITransformE forw back) = ITransformE back forw

Besides doing what I already do more uniformly, this generalized approach to transformation should be just the thing for interactive images, which may be neatly formulated again, as functions.

Pajama!

I am working on a new implementation, called Pajama, of the image synthesis embedded language Pan, this time generating Java applets. The advantages over Pan will be

• Easy to run examples. Anyone with Java 1.5 or better can simply visit a web page to see and interact with the examples.
• Examples run on all major platforms (wherever Java 1.5 runs), while Pan ran on Windows only.
• The Pajama compiler runs on all platforms supporting GHC and the java compiler. In contrast, the Pan compiler ran only under Windows and only with Microsoft's Visual C++ compiler. Worse yet, Pan used a GUI library (WTL) that Microsoft no longer supports. I haven't been able to run the Pan compiler for quite a while now.

The disadvantage of Pajama over Pan is speed. Trig speed is quite a bit slower, and I suspect array accesses are also. Mustang (Java 1.6) improves trig performance considerably, though only with the server JVM, but almost everyone would be using the client JVM. I hope speed improves over time. Quite a lot of Pajama is already working. I have first examples running here. More on the way.

April 13 edit: Pajama now runs on Java 1.4 and up, not just 1.5, thanks to Retroweaver, a class file rewriter. Technorati tags: Pajama, FunctionalProgramming, Haskell, GraphicsProgramming.