Reduce code complexity by restructuring
(case study)

In short:  As a case study, I reduce the code complexity of the one-line text editor with categorical combinators.

Motivation

Suppose that we begin to use a new, user-friendly application, and we get familiar with it under a few days. Suppose moreover, that someone explains us the application logic under a few weeks. More or less this means that the ‘what’ and ‘how’ of the application has a few days and a few weeks of perceived complexity, respectively. We still don’t know the perceived complexity of ‘how to do efficiently’ because we have no clue how the application works on the actual hardware:

   perceived complexity of the application
┌─┬─────┬──────────────────────── ─── ─── ───
│d│weeks│  ?        
│a│     │                               
│y│     │                               
│s│     │                               
│ │     │                               
│W│ HOW │  how to do efficiently
│H│     │  
│A│     │                               
│T│     │                               
└─┴─────┴──────────────────────── ─── ─── ───

In my experience more or less the code complexity of the same application looks like the following:

                   code complexity of the application
┌─── ─── ─── ─── ─── ─── ─── ─── ─── ─── ─── ─── ───┬─── ─── ─── ─── ───┐
│months or years                                    │                   │
│                                                   │                   │
│                                                   │     efficient     │
│                                                   │                   │
│        user interface        program logic        │  data structures  │
│                                                   │         &         │
│                                                   │    algorithms     │
│                                                   │                   │
│                                                   │                   │
└─── ─── ─── ─── ─── ─── ─── ─── ─── ───  ─── ──────┴─── ─── ─── ─── ───┘

There is a huge gap between learning the ‘what’ and ‘how’ in weeks vs. understanding the application’s user interface and program logic code in months or years. I see the following possible causes:

  1. The code is not documented. This can be mitigated somewhat by relying on the active developers to explain the code for us.
  2. The code is not properly structured.
  3. We learn the application faster because we already know other applications, and we have to learn just once what is common in applications. Code reuse has similar effect on code complexity, but the program logic is coupled with overwhelming efficiency complexity which cannot be eliminated from there by code reuse. On the other hand, the code complexity of efficient data structures has been reduced somewhat by programming libraries and compilers.

As a part of my bigger project, I try to narrow the gap between the perceived complexity and code complexity of applications. In this blog post I present a case study about cause 2. I plan to discuss cause 3. at another time.

The one-line text editor

The text editor is probably the most iconic interactive application. The one-line editor can edit a single line of text:

editor demo
editor demo

As a case study, I reimplement the one-line text editor. My goal is to minimise its code complexity such that I don’t count the complexity of independent, reusable parts.

Editor features

The user input is one of the following events:

event function details
Del | Backspace | Left | Right | ShiftLeft | ShiftRight control key
Char p printable character p: 'a' | 'b' | 'c' | …
Resize w window resize w: width (in characters)

I have selected the following editor features for the case study:

Corner cases

The set of corner cases is more vague than the set of features. A corner case for someone may be a feature or a common case for someone else. For me the editor has the following corner cases:

Perceived complexity of corner cases

Users predict the behaviour of the application in the corner cases and they note the surprising cases only. I conclude that the perceived complexity of corner cases correlates with the number of surprising corner cases – which should be minimal – plus the complexity of the inference process by which users predict the behaviour of the application.

There is an asymptotic (huge) difference between the number of corner cases and the perceived complexity of corner cases. The number of corner cases grows probably exponentially with the number of features because corner cases may arise as interactions between different features. On the other hand, in my experience the perceived complexity of corner cases grows not much faster than the number of features.

I want the code complexity to correlate with the pereceived complexity of the corner cases. For this I want to reflect and distill the inference process by which users predict the behaviour in corner cases. As a side-effect the number of surprising corner cases will be minimized too.

Editor state

For further analysis, let’s introduce the following definitions about the state of the editor:

t the editable text
c cursor position inside t (beginning with 0)
b start position of the visible area (in characters, counted from the beginning of t)
e end position of the visible area (in characters, counted from the beginning of t)
w width of the visible area (in characters)

The extended screenshot is a compact visualisation of these values. For example,

    Hello world!   

is a visualisation of

    {t = "Hello world!", c = 7, b = 5, e = 15, w = 10}

User input can be mapped to editor state perturbations. Some examples:

user input perturbation meaning
Left c = (-1) decrement c
Right c = (+1) increment c
ShiftLeft b = (-1) decrement b
ShiftRight b = (+1) increment b

The editor state should always fulfil these so-called invariant properties:

invariant explanation/feature
bc < e the cursor is inside the visible area
0 ≤ b the visible area cannot be shifted before the editable text
c ≤ length t the cursor is inside the editable text
e = w + b the meaning of ‘width’

These constraints are inherent parts of the editor state.

    Hello world!   

can be also seen as a visualisation of

    {t = "Hello world!", c = 7, b = 5, e = 15, w = 10 | 0 ≤ bc < e, c ≤ length t, e = w + b}

Side-note about the notation

The part after the vertical bar is static information which can be expressed by refinement types or dependent types. Expressing it by refinement types would look like this:

    {t = "Hello world!", c = 7, b = 5, e = 15, w = 10}
      : {t ∊ String; c, b, e, w ∊ ℤ | 0 ≤ bc < e, c ≤ length t, e = w + b}

I use a bit more compact notation in the examples.

The editor’s corner cases are closely connected to the constraints. Consider the corner case when the cursor is at the right end of the visible area and the user hits Right:

    Hello world! & Right

This stands for

    {c = 9, e = 10, … | c < e, …} & (c = (+1))

Here the application of the perturbation would invalidate c < e which is a signal for a corner case.

Handle corner cases by adjusting the perturbed state

The common approach to handle the editor corner cases is to perturb the state and adjust it afterwards by a dedicated program logic which is called adjustVisibleArea in the following example:

        Hello world! & Right
    = {c = 9, b = 0, e = 10, … | c < e, e = w + b, …} & (c = (+1))
    = adjustVisibleArea {c = 10, b = 0, e = 10, … | c < e, e = w + b, …}
    = {c = 10, b = 1, e = 11, … | c < e, e = w + b, …}
    = Hello world!

This approach has the following shortcomings:

Handle corner cases by perturbation propagation

Perturbation propagation is also known as constraint propagation. Maybe it is easier to understand perturbation propagation if we split it into two distinct phases first.

In the first phase the perturbations are propagated in all possible ways:

Hello world! + Right
= {c = 9, b = 0, e = 10, w = 10, … | c < e, e = w + b, …} & (c = (+1))

After the first phase we get several possible results. In the second phase the results are filtered and the first good result is chosen.

This two-phase approach is tightly connected with the constraints and avoids the ad-hoc adjusting logic but it has at least two drawbacks:

One-phase perturbation propagation

In the editor application we know in advance (= statically) the constraints and the valid propagation of different perturbations.

Examples of such static knowledge:

With the static knowledge perturbation propagation can done in one phase. The running example looks like now this:

    Hello world! & Right
= {c = 9, b = 0, e = 10, w = 10, … | c < e, e = w +’ b, …} & (c = (+1))
= {c = 10, b = 0, e = 10, w = 10, … | c < e, e = w +’ b, …} & (e = (+1))
= {c = 10, b = 0, e = 11, w = 10, … | c < e, e = w +’ b, …} & (b = (+1))
= {c = 10, b = 1, e = 11, w = 10, … | c < e, e = w +’ b, …}
= Hello world!

Either compilers may generate efficient code from the static knowledge, or better, we can structure the editor’s code such that it directly reflects the static knowledge. Let’s see how.

Avoid temporary invalidation of constraints

First I show how to avoid temporary invalidation of constraints.

The main idea is to compose complex constraints from basic ones. For this, constraints are represented as bidirectional stateful algorithms (see later). Each constraint has its own local state on which the constraint always holds. During the propagation of perturbations, the perturbations change the local state of the constraints as they are propagated by them.

Here are three steps of an example propagation:

  1.          │c  ∆c = (+1)
      ╔══════╧══════╗
      ║    c < e    ║ c = 9, e = 10
      ╚══════╤══════╝
             │e
      ╔══════╧══════╗
      ║  e = w +' b ║ e = 10, w = 10, b = 0
      ╚═══╤═════╤═══╝
          │w    │b

    The initial perturbation is c = (+1). There are two basic constraints composed together. The local states on the right of the boxes are in sync and the constraints hold on them.

  2.          │c
      ╔══════╧══════╗
      ║    c < e    ║ c = 10, e = 11
      ╚══════╤══════╝
             │e  ∆e = (+1)
      ╔══════╧══════╗
      ║  e = w +' b ║ e = 10, w = 10, b = 0
      ╚═══╤═════╤═══╝
          │w    │b

    c = (+1) was propagated by the c < e constraint whose local state was changed. The new perturbation to be propagated is e = (+1). At this point the values of e are different in the two local states, but the constraints still hold on the local states.

  3.          │c
      ╔══════╧══════╗
      ║    c < e    ║ c = 10, e = 11
      ╚══════╤══════╝
             │e
      ╔══════╧══════╗
      ║  e = w +' b ║ e = 11, w = 10, b = 1
      ╚═══╤═════╤═══╝
          │w    │b  ∆b = (+1)

    At the end of the propagation the local states are in sync again.

The final editor structure

At this point I am ready to show you the final editor structure which looks like this:

                               ┌─user input─┐
  ╭──────────────┬───◂ const w ↤ Resize w   ╎
  │              ╰──▸ screen   ╎            ╎
  │             ╭───▸ screen   ╎            ╎
 w│   ╭──────┬──┴──┬────◂ (-1) ↤ ShiftLeft  ╎
╔═╧═══╧═╗    │b    ╰────◂ (+1) ↤ ShiftRight ╎
║   +'  ║    │                 ╎            ╎
╚═══╤═══╝ ╔══╧══╗              ╎            ╎
    │e    ║  ≤  ║              ╎            ╎
 ╔══╧══╗  ╚══╤══╝              ╎            ╎
 ║  >  ║     │                 ╎            ╎
 ╚══╤══╝     │c    ╭────◂ (-1) ↤ Left       ╎
    ├────────┴─────┴────◂ (+1) ↤ Right      ╎
   c│   ╭──────◂▸ co-editing   ╎            ╎
  ╔═╧═══╧═╗  t                 ╎            ╎
  ║splitAt║                    ╎            ╎
  ╚═╤═══╤═╝  t₂                ╎            ╎
  t₁│   ╰──────┬──◂ deleteAt 0 ↤ Del        ╎
    ├───────╮  ╰────▸ screen   ╎            ╎
╔═══╧═══╗   ╰───────▸ screen   ╎            ╎
║reverse║                      ╎            ╎
╚═══╤═══╝  t₁'╭─◂ insertAt 0 c ↤ Char c     ╎
    ╰─────────┴───◂ deleteAt 0 ↤ Backspace  ╎
                               └────────────┘

Explanation:

Wires are translated to constraint combinators. The translation process is automatic and it can be done by the compiler. The translation process is stable if certain conditions hold. You can read more about this in the Appendix.

The circle in the wiring could have many interpretations. The interpretation of circles is connected to the scheduling of propagation. I allow only scheduling-independent networks, for which any scheduling gives the same result. Scheduling-dependent networks can be ruled out either by the programmer or by strong static typing which I don’t discuss here. The actual scheduling is determined by the translation process of networks.

This architecture handles all corner cases correctly. Let’s see the running example first:

    Hello world! & Right

The relevant part of the network looks like this after perturbation propagation is finished:

      w = 10
  ╭──────────────▸ -
  │   ╭──────┬───▸ (+1)
╔═╧═══╧═╗    │b = 0 & (+1)
║2. +'  ║    │
╚═══╤═══╝ ╔══╧══╗
e=10│&(+1)║3. ≤ ║
 ╔══╧══╗  ╚══╤══╝
 ║1. > ║     │
 ╚══╤══╝     │c = 9 & (+1)
    ├────────┴──────────────────◂ (+1) ↤ Right
    │   ╭────────▸ -
 ╔══╧═══╧══╗ t = "Hello world!"
 ║4.splitAt║
 ╚══╤═══╤══╝ t₂ = "ld!" & deleteAt 0
    │   ╰────────▸ deleteAt 0
    ╰────────────▸ insertAt 9 'l'
     t₁ = "Hello wor" & insertAt 9 'l'

Remarks:

In the second example the user tries to delete the character after the end of the text:

    Hello world!    & Del

The relevant part in this case is just the splitAt constraint:

  c=│12 ╭──────▸ -
  ╔═╧═══╧═╗  t = "Hello world!"
  ║splitAt║
  ╚═╤═══╤═╝  t₂ = ""
  t₁│   ╰──────◂ deleteAt 0 ↤ Del

Here the splitAt halts the propagation process because it is not possible to propagate the deletion of the first character of the empty text. Because the propagation is halted, nothing will happen, which is the right behaviour. Halting the propagation is an optional feature of constraint combinators. You can read more about halting in the Appendix.

Rendering the editor on the screen

The editor can be rendered on the screen from w (the editor width), b (the begin position of the visible area), t (the text before the cursor) and t (the text after the cursor).

Just for illustration, here is the Haskell code for rendering the output:

render w b t₁ t₂ =
  take w (                               -- drop invisible glyps at the end
    drop b (                             -- drop invisible glyps at the beginning
         map normalColor t₁              -- colour the characters before the cursor
      ++ mapHead invertColors (          -- invert the colours of the character right after the cursor
              map normalColor t₂         -- colour the characters after the cursor
           ++ repeat (reddishColor ' ')  -- unlimited reddish space after the text
         )
    )
  )

The functions normalColor and reddishColor map characters to glyphs (colored characters). invertColors maps a glyph to a glyph by exchanging it’s foreground and background colors. mapHead applies a function to the first element of a list.

Incremental rendering

We don’t want waste computation power by re-rendering the whole screen for each user input. This is even more important for GUI programs. Incremental rendering is important for co-editing too: if another user edits part of the text which is not in the visible area of the user, then the user’s screen should not be touched at all.

Fortunately, the render function can be converted to a ∆render function which maps the perturbations from the editor core into perturbation of the screen, which is what incremental rendering means. ∆render can also be constructed from combinators. For this we need simpler combinators than in perturbation propagation because ∆render contains one-way wires only.

Let’s see the running example:

    Hello world! & Right

The relevant output of the editor core is:

    b = (+1),  t = deleteAt 0,  t = insertAt 9 'l'

Without going into further details, ∆render will produce the following output:

    insertAt 8 (normalColor 'l') . insertAt 8 (invertColors (normalColor 'd')) . deleteAt 8 . deleteAt 0

Here the dot is the (reversed) composition of perturbations. If we apply the individual perturbations one by one we get to the final rendering from the previous rendering:

Hello worl
ello worl   – deleteAt 0
ello wor   – deleteAt 8
ello word   – insertAt 8 (invertColors (normalColor 'd'))
ello world   – insertAt 8 (normalColor 'l')

Implementation

You have to go through the Appendix if you want to understand the actual implementation. I encourage you to read it also if you have not heard about categorical combinators yet.

You can find the source code of the implementation here. Note that the implementation is not in sync with this blog post and incremental rendering is not implemented which should be fixed soon.

What’s next?

As a part of my bigger project, I am going to implement a multi-line text editor and a basic TUI (textual user interface) email client and browser with as small code complexity as I can.

Further reading

Conclusion