Divide and Conquer vs. Cognitive Loading

2025-01-29

Jan 29, 2025

Divide and Conquer

Divide and conquer is the idea of chopping a problem up into smaller sub-problems, each with their own solution. The smaller sub-solutions are combined to solve the greater problem.

Does Divide and Conquer Lead to Cognitive Loading?

The approach of divide and conquer sometimes seems to imply greater cognitive loading, because a greater number of pieces need to be managed.

The cognitive loading does not come from the small-ness of the procedures, but, is due to the flat-ness of the namespace, i.e. the "infinite canvas" mentality.

Layering

The UNIX shell gets around the problem of “state explosion” by allowing layering. A shell script can invoke commands or other shell scripts to an infinite depth (as opposed to infinite breadth).

The shell, though, fails to restrict this concept and fails to encourage this approach, though. Functional programming fails in the same way. Neither approach strongly enforces the kindergarten rule of no “colouring outside the lines” - which has resulted in work-arounds and name-spacing issues. Early UNIX is further described in this article.

For layering to work well and to be encouraged, there should be one kind of part to choreograph parts and another kind of part to do the work. Functions allow you to do this, but, functions don't restrict you from doing something broader, too. It's like the GOTO problem in the early days, you could write structured programs using GOTOs but the existence of GOTOs tempted one to break structuring. Here, it's the same, you can write layered programs, but, you tend not to. Simply trying to understand someone else's code points out the problem of lack of structuring. 90% of the time it's difficult to understand what’s intended. One must reverse-engineer the original intent from detailed bits of code meant to control machines instead of communicating DI (Design Intent) to other humans. Only a few programmers actually shine through as being capable of "writing good code”.

Complete Isolation

Extreme use of divide and conquer requires mental freedom. The freedom to know that sub-problems are completely isolated and do not depend on other parts explicitly nor implicitly.

The idea of “functions” breaks this rule. Due to a built-in protocol, functions are implicitly coupled to other functions that they call. Callers must wait for the callees to finish. On paper, the protocol is invisible, but, when implemented on a digital computer, this protocol is implemented using a callstack and leads to control flow issues in the code.

This callstack paradigm cannot scale well to distributed programming. You can use a callstack inside a node, but it is inefficient to use a callstack to implement communications between nodes. In other words, “functions” can be used to solve single-computer problems, but, the idea of using functions needs to be stretched out of shape to solve problems involving many distributed computers.

I think that this implies that the callstack needs to be entirely expunged for inter-part communications. This means that - at least semantically - functions must inhale input parameters from a queue and exhale results into another queue. Queue, not stack. LIFO, not FIFO. We don’t need to discard functions and start all over again, we just need to add another kind of thing to our programming languages - a send in addition to a call. Send can be used for inter-part (external) communication, while call can be reserved for intra-part (internal) communication and control-flow.

A completely different approach to conquering the “state explosion” problem is shown by Harel’s Statecharts.

Example

Imagine implementing an OSI 7-layer stack or an ethernet stack. If code at a bottom layer needs to pass information up to a higher-level layer it can do so by:

Calling functions in the upper layer.
Depositing information into an output queue, which the upper layers can peruse at will.

Calling a function in an upper layer doesn’t just pass data upwards, it, also, passes control-flow upwards, i.e. “you must deal with this now”. If the upper layer deals with the data by calling functions in some other lower-layer, the whole control-flow chain becomes a tangled mess. This is what led to the Mars Pathfinder fiasco.

If, instead, the lower-level code were to pass data upwards by sending a message via a queue, the lower-level code would not get its control-flow tangled up with whatever the upper layer needs to do, and, the lower-level code could continue doing what it was doing without waiting for the upper layer to finish its work.

Decoupling Software Parts

The queue idea leads to better divide-and-conquer. Queues act like automobile clutches between software units that are too tightly coupled, like interlocking gears in an automobile.

We see hints at this kind of thing in declarative languages and in relational languages, like PROLOG. PROLOG code does not use functions - it uses relations and allows the underlying engine to decide on the order that work gets done. Control-flow is not hard-wired into PROLOG code like it is in Functional code.

In UNIX pipelines, we see decoupled message-passing. Commands can only send data to stdin and stderr. Commands cannot hard-wire references to other commands into their code. Likewise, (well-written) shell scripts do not hard-wire references to commands and scripts into their code - other than references to their direct children. Again, an engine - the UNIX kernel - handles scheduling of which command/script gets to run at any time. There is no implied micro-management-sequencing in the code. The sequencing has been separated out into the “|” operator. Specification of sequencing is only done at a higher level “do this before you do that”, without specifying micro-level details of when the code must run.

The problem with UNIX pipelines is that they rely on heavy-weight processes and on heavy-weight operating-system supplied buffers. Can we do this kind of thing less expensively? Can we bolt this kind of thing into programming languages, without resorting to threads and other heavy-weight ideas?

Implicit Sequencing and Control Flow

Note that functional code does specify sequencing, but, this is hidden from view. Statements in code run sequentially one after the other, or, call other functions (leaving a return-to bookmark on the global callstack). Called functions then run their statements sequentially.

Sam Aaron, in his TEDx talk points this out in a humorous manner. At 09:37 he shows 3 simple lines of code, each of which produces a single note (a single pitch of sound). Aaron hits “RUN” and all 3 notes play - concurrently - at once. This is just a “chord” in music. Programmers, though, automatically assume that the lines of code will run sequentially from top to bottom. That is built-in, hidden, sequential control flow. The control-flow is wired into the code, but the control-flow remains invisible and is assumed to exist.

This kind of thing doesn’t happen implicitly in a UNIX shell pipeline. When pipeline programmers write pipelines using “|” operators, they only specify data-flow, leaving the control-flow decisions up to the dispatcher in the UNIX kernel. The “when will this run?” question is not decided by the programmer when writing pipelines. All that the pipelines specify is relative control flow, i.e. that the left-most part will run “sometime” before any of the right-hand parts. The pipeline programmer specifies that the left-most part produces data, and, when the next part in the pipeline runs, it will be able to see the data. But, the pipeline programmer does not get to specify exactly “when” the next part will run.

Functions, on the other hand, specify that a called function must run immediately. This embedded control flow causes a Rube-Goldberg chain of work-arounds, such as preemptive context-switching in operating systems.

Cognitive Loading

Programmers have become accustomed to the hidden control flow of functional code and they (unnecessarily) code everything that way, which has resulted in software bloat and operating systems that are some 50,000,000 lines of code in size.

The hand-waving argument used to justify such bloat is that the size is directly related to the number of features needed in a modern operating system.

I contend that the bloat comes from the over-use of functional thinking and that this leads to a deeper form of cognitive loading than does strongly-decoupled, queue-based divide and conquer.

All libraries supplied by the bloated operating system are written in one base paradigm - the Functional paradigm. If the libraries were written as fully-decoupled parts, one could snap together mini-OSs, like LEGO® blocks, using only the bits that were needed on end-users’ machines. I make more observations about code bloat in this article.

Conclusion

We can’t erase all existing code and start all over again, but, we can - easily - stop doing things the same way that we’ve always done them - something that Grace Hopper warned against..

Paul’s Substack

Discussion about this post