Have you ever played Myst? The premise is that there's an Art for writing books that transport you to another reality. People skilled in the Art jot down coherent details about that reality and, in the process, become so involved with its conceptual visualization, like a radio's phase lock loop, that they manage to identify one reality uniquely and bridge the gap between semantics and substance.
A similar effect is achieved with constraint programming. You start to sketch out your problem, identify ambiguities, and resolve them until you've described a coherent system.
There's a Java CSP library called Choco. They're involved in the creation of JSR 331, which the 2010 JCP Awards body describes as pretty much the only innovative JSR in the 300's. Hah, faced. Ahem.
I work for a creative company and figured I'd try my hand at constraint programming, applying it to the old problem of text layout.
Line boundaries are determined by the bounds of line elements.
Lines may not exceed the boundaries of the text area.
Characters may be line elements. Their width is determined by font metrics and point size.
The space between characters is determined by font kerning.
The positional difference between adjacent lines is called leading.
If centering is enabled, the distance between a line and its bounding text area is the same on either side.
I want the point size to be as big as possible without exceeding X.
And so on... Then,
I'm interested in the position of individual line elements.
For PDF purposes, I'm also interested in greedily identifying each sequence of characters with identical formatting and no kerning.
The syntax wasn't beautiful*, but it was actually a pleasant programming experience. The kludgiest part was that I couldn't define adjacency constraints on ordered sets. (e.g. "The position of the next line element is equal to the position of the previous element plus the width of the previous element, plus the space between them.") To achieve that effect, I had to create individual constraints between each element. Unless Choco could identify that the constraints between the elements happened to be identical, there's no way it could handle that optimally.
But it worked. It told me everything I asked for.
Let's face it, you want this analysis happening at compile time, not runtime. In this simple form, the layout engine was usable as a one-off layout generation, but its suitability for real-time applications is dubious. Plus, I'm angling for solving well-constrained problems – problems to which constraint inference techniques can be applied to identify a single solution. I don't need something like Choco's incremental solver. I want my constraint compiler to write code that will take any compliant data model and produce the answers I want with as little processing as possible.
I also want it to only generate answers that code further down the pipeline specifically asks for. And I want the constraint compiler to discard constraints and relationships that aren't relevant to what's asked for. And I want the compiler to generate code that optimally handles the kinds of incremental changes to the data model that are possible in the application. And I want the compiler to infer which kinds of changes are possible. And I want to layer my constraint model in a modular, compositional way. And I want the cardinality and relationships of the components to be decided by an XSLT-flavored language that decouples the semantics of output and input data models. And I want useful circular dependencies – state that decides the view layer, and drag events that decide the state, with the compiler demanding the creation of handlers for drag events that over-constrain the problem space. And when the compiler's in debug mode, I want it to analyze the tree decomposition and inject a SillyWalk constraint that demonstrates readily to the developer where they failed to tighten things up.
And I want a pony.
*In all fairness, they created a parser to get around the syntax ugliness.
PS: Blogger HTML formatting is dead to me.
No comments:
Post a Comment