Posted in Uncategorized by sarkology on May 19, 2018

Problem solving

How do we solve problems? We might say that there we aim to configure some portion of reality from some present state to some desired state.

The achievement of the desired state can in principle be as dumb and brute force as possible. Setting aside practicality, we can assume the totality of the design space at the lowest level is finite and that there exist configurations of reality which produce the desired state. Problem solving is then a brute force search through such a space.

But thanks to combinatorial explosion, this is impractical. In practice we design, which is to say we employ heuristics for breaking down a problem and to search for solutions to the subproblems thus produced.


But on what basis do we perform such decomposition?  Upon encountering a new problem, we are reminded of problems we have already struggled with. Past experience is rich a store of problems encountered and possibly solved.

If the new problem is some variation of the old, then we might assume that we could reuse the solution but with a slight modification. Thus we have decomposed the problem into a reuse and a search for an effective modification.

Or the new problem might not on the whole look like anything we encountered in the past, so we break it down into the subproblem of how to break the problem down and the subproblem of solving the subproblems generated having had broken it down. But before we can finally solve the original problem, we need to have already solved those subproblems we just invented for ourselves!

Decomposition then is about reuse. Nothing comes for free. We productively break down a problem only when we can solve the subproblems we thus inflict upon ourselves.

Atomic problems, definitive solutions

What makes a particular decomposition better or worse? Remember that you need to solve whatever subproblems you divided the original problem into. And so it would definitely be better if the subproblem were similar to something you have already solved. And it would be best if it were exactly the same as some problem you have completely solved.

What then does it take to conclusively solve a problem? Having already solved some problem, we might yet playfully elect to decompose it nonetheless. We may or may not succeed doing so, in such a way that all the subproblems are themselves completely solved. Even if we did not, the recursion would only stop making sense when we cannot further decompose and obtain some problem which could potentially be solved on its own.

We thus arrive at the atomic problems. For example, that of sorting a collection of elements in some total order. From which we might hope we have something we could simply re-employ to solve any other problem involving sorting out there.

Our atomic problems with solutions we have conclusively and definitively solved. It may be the case we cannot divide future problems cleanly into only those within our repertoire of solved atomic problems, but to any extent we can we have made some measure of progress.

A bit of both

Now what about the admittedly more common situation where we do not quite so cleanly decompose the problem into conclusively solved atomic problems? Well we force square pegs into round holds. Or perhaps more charitably we pack spheres into boxes. Or a menagerie of belongings into a suitcase. There is some residual wasted space, but we force-pack what we need into our luggage anyways.

But take two suitcases, does that make things easier? Only if you know that certain things should go into the first and all the others into the second. How could you know this? Perhaps one is cabin luggage and the other is to be check-in, so you might put more important things into the cabin luggage. Or even better: you need to bring your violin along and it can only fit into your violin case, which owing to its fragility you are forced to hand-carry. This latter is a solved atomic problem. It demonstrates orthogonality: it doesn’t matter how you pack anything else, you pack your violin only into your violin case, no debate.

But the problem otherwise of deciding to pack two suitcases and what to pack into each of them; that is a self inflicted problem. That is the problem of modularity.

Modularity is hence a design of design. The contours of the problem itself do not lend themselves into subdividing it naturally and convincingly into subproblems, so you have to impose your own subproblem structure upon it. You design your design in such a way that you perform object-level design only within the boundaries set by your meta-level design.

Modularity versus orthogonality

Which then better lends itself to reuse?

Modularity is something invented, you might hallucinate some decomposition in the problem, but there is no saying if the same hallucination might work for another problem. You may have to adapt your decomposition, and also how you go about solving each self-inflicted subproblem.

Orthogonality is something discovered, you hack away at reality until it does not yield to further attacks. Wherever else the problem occurs you have a definitive solution; if you can recognise it when you see it. It involves no work, only preparation, and a bit of luck.

Why then modularity?

But obviously we cannot rely on orthogonality alone. Not least since rarely do novel problems comprise exactly those already solved. How exactly then are we forced by necessity to modularise?

One reason might be ownership. When we cannot conclusively solve a problem we need to continuously deal with any unexpected complications which do arise. For example, software components have bugs and undependable dependencies and so require upkeep and a maintainer: someone who takes ownership of that component.

Unlike library dependencies which owing to them being inconclusive solutions to problems and so yet propagate stressors to our poor maintainer, the orthogonal concerns involved in that piece of software he can take for granted. An efficient sorting algorithm he can decide once to use and subsequently completely forget about.

So modules rot, abstractions don’t. But in this fallen state of the world ownership and maintenance of software is something which cannot be avoided.

But can our software maintainer hope to do better? Why yes. For though he can do nothing about compiled artefacts he does not himself produce, the source code he may compose out of orthogonal parts, so long as his compiled artefacts interact with other artefacts in the same old way.

He can for instance with lenses specify where in a data structure he performs his modifications completely orthogonally to how he performs those modifications.

Modularity may be about ownership but orthogonality is about obliviousness. A particular data transformation only cares about the form of its input and does not care where in some larger piece of data that portion which is its input reside. This isn’t an object oriented fetish about taking ownership of that piece of input. The pure function is total and its output is always well defined, no maintenance is required and so no ownership is necessary.

Your programming “abstraction” may involve hiding. But the real numbers are not hiding no Cauchy sequences or Dedekind cuts.

An orthogonal abstraction is synthetic in the sense of Euclidean geometry where the point is defined axiomatically in relation to other things, and is undefined in itself. In contrast to analytic geometry where it is defined with respect to some coordinate system. Of course in the case of analytic geometry the embedding is clean and there are not “abstraction leaks”, but most software modules don’t fare so well.

Every solitary, I told myself, is suspect: a pure being does not isolate himself. To seek the intimacy of the cell, one must have a heavy conscience; one must be afraid of one’s conscience. — Cioran on encapsulation

Inferior men guilt you into dealing with their problems. Superior men inspire you to adopt their solutions. Once Edward Kmett has written the lens library you will simply use it because he has genuinely put to rest a problem you might not even have had the perspicacity to recognise you were suffering. Not some fashionable UI framework which saves you from some boilerplate which was only ever necessary because of someone else’s confusion in the first place.

But can things get worse? Hell yes. Vertical integration is when orthogonal things get collapsed and sacrificed at the altar of a seamless end user experience. Hacks are made and cracks are plastered over in order to present a usable facade to the consumer. Usable that is, until it breaks. Eventually. Always.

So strive for orthogonality, and make do with some modularity if you must. But remember, in the long run, only the higher things are worthwhile.

But I now leave my cetological System standing thus unfinished, even as the great Cathedral of Cologne was left, with the crane still standing upon the top of the uncompleted tower. For small erections may be finished by their first architects; grand ones, true ones, ever leave the copestone to posterity. God keep me from ever completing anything. This whole book is but a draught—nay, but the draught of a draught. Oh, Time, Strength, Cash, and Patience. — Moby Dick


2 Responses

Subscribe to comments with RSS.

  1. jpt4 said, on May 1, 2020 at 5:53 am

    Are you familiar with formatting, a concept from Jean-Yves Girard?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: