The Cassowary Linear Arithmetic Constraint Solving Algorithm [pdf] (2002) | Hacker News Reader

The Cassowary Linear Arithmetic Constraint Solving Algorithm [pdf] (2002)

constraints.cs.washington.edu

63 pointsandsoitis22 comments

Cassowary's big differentiator 25+ years ago was that it is robust against cycles in constraints and supported inequalities. Those two facts made it instantly way easier to use than the local-propagation-based solvers that predated it (think spreadsheet-style formulas referencing cells where you can only compute values using equality assignment and you can't create cyclic references).

Cassowary being able to solve that broader class of problems in an efficient and incrementally (using prior solutions to the problem to make subsequent solutions even faster) was why Apple chose it for Autolayout in the later '00s. Their Visual Formatting Language was a nice ease-of-use enhancement, too.

The original cassowary repo is https://github.com/gjbadros/cassowary and there was a nice improved port to Javascript 15 years ago: https://github.com/slightlyoff/cassowary.js/

Good memories! I used to use the Cassowary solver back in the day for planning multi-media presentations where you could specify constraints that were to hold between the different elements of the presentation. Think: "play this audio clip at most two seconds after this other video ended", while the inherent lengths of the elements were only available at run-time.

In addition, you could combine quantitative with qualitative, i.e., Allen-style constraints [0].

This all feels like ages ago to me now, but I suppose >20 years actually is quite a long time.

[0] https://en.wikipedia.org/wiki/Allen%27s_interval_algebra

I wish the web platform settled on constraints based layout rather than flex and grid. Autolayout on iOS was always so much fun to use and made intuitive sense in a way the css layout options never did. Constraint-based layout predates flex and grid so it’s a little weird it never caught on.

The limiting factor is what can the UI designer wrap their head around. If your system is pure and elegant but can only be understood by the top 5% of developers, it will never catch on. To be blunt, it has to be simple enough to be usable by the least smart hire-able developer. If it requires more thinking than writing FizzBuzz, forget about it.

This depends on how well this abstraction can be encapsulated. The systems with rigorous mathematical foundations often result in simple to use products that compose well. The 3d modelling relies on linear algebra, but the designers don't need to understand those details. The regular CSS involves very complex layout calculations too.

Eh, I understood AutoLayout back when I was a naive junior dev doing iOS. Formal definition of constraint solvers can be complex, but if you wrap it in an intuitive API, it’s consumable by a wide variety of people.

Is the limiting factor preventing all websites from being written in assembly also the intelligence of the developer base? What an obtuse take.

I see you're getting downvoted (wrongly, because you're discussing in good faith), but I agree with the sentiment. 5% is a bit harsh, but having been on multiple iOS teams where AutoLayout is essential, it has always been a challenge to get people to understand what's going on, do the correct thing, and write code that doesn't barf constraint conflict warnings to the console. Seasoned iOS engineers have learned to do the right thing, but it's easy for one person to introduce a new conflict that nobody notices until months later when it's tedious to debug.

A shorter way of saying this is that the ergonomics of the most broadly-deployed constraint solving UI layout system—AutoLayout for iOS—still cause pain. It's not better pain than the massive complexity of CSS, it's just different pain. And it's also not sufficient; Apple themselves introduced collection views and stack views, each of which has its own special behavior. Their new framework, SwiftUI, does not use AutoLayout. Even the maintainers don't consider AutoLayout "superior" enough to adopt in a fresh UI framework.

It's a shame, because there is elegance in having a layout system you can explain in one or two pages, with enough power to almost support an entire OS and ecosystem of apps. It's just not quite across the finish line for developer experience and education.

While I agree with this wholeheartedly, one aspect of the Web that constraint systems don't play nice with is flowing content. Typical example would be text.

The reason is that the width/height of an element with flowing content cannot be described by a linear constraint. (not even a quadratic constraint, since there's a discontinuous jump when text wraps from N lines to N+1 lines) So when you mix these kinds of elements into a Cassowary-based system, you're trying to fit a square into a circle-shaped hole, and run into weird edge cases that require workarounds like manually adjusting constraints based on ad-hoc logic, or running the layout solver multiple times to try different sizes for a flowing element, etc.

We use a cassowary based constraint solver within Ratatui [1]. It's kind of neat once you understand the algorithm and add your own UI rules system on top of it. Unfortunately the library[2] that we use for the actual solving is unmaintained for many years now. I've been meaning to rewrite[3] a bunch of things in the lib to be more ergonomic, but it hasn't bubbled to the top of my todo list yet.

[1]: https://github.com/ratatui/ratatui/blob/main/ratatui-core/sr...

[2]: https://crates.io/crates/cassowary/

[3]: https://crates.io/crates/kasuari

Fun fact for any Seattleites out there: the co-author of this paper, Professor Alan Borning, was the advisor for the Ph.D. students who originally built OneBusAway and is on the board of the non-profit that runs it today.

n.b. I've been involved in the OneBusAway project for over a decade and run the non-profit as the very part time exec director today.

Oh wow - I met Alan back in 2012 when I was working on a project called WhichBus. How cool!

Thank you for your continued involvement and contributions to OneBusAway!

In the ancient times there was a startup called The Grid. Very hyped. They implemented the Cassowary layout algorithm for the web and called it GSS.

I loved the idea of GSS but it never caught on: https://gss.github.io/

> in the ancient times > 2014

Rage successfully baited - that was like three months ago, tops!

I wonder what ever happened with Grid - they were indeed very hyped, but fairly-obviously vaporware too IIRC. At least in terms of marketing, where they claimed AI web-property generation.

Very ahead of the times for 2014.

> GSS was created by Dan Tocchini, leader of the TheGrid, the first AI website platform.

I consulted with them briefly. Felt like it was stimulant-fueled hustleporn. They had an interesting concept, but not surprised they didn't turn out a sustainable product.

I programmed that gss thing. Fundamentally the issue is that cassowary can’t do 2d constraints and can’t do li e wraps. It’s dumb.

What course or resource should one look into if one is interested in learning more about constraint solving

Peter Stuckey, the co-author of this paper has a series of courses on modelling for constraint programming on coursera. https://www.coursera.org/learn/basic-modeling Pascal Van Hentenryck has another one https://www.coursera.org/learn/discrete-optimization Håkan K has a blog with a big collection of models for a wide variety of solvers https://www.hakank.org/

Poorly coded slow library that leaks memory. Wouldn't recommend.

Isn't the Cassowary a mean-ass bird

Reply on news.ycombinator.com