Type Systems and Incidental Versus Inherent Complexity


Notes (‘epistemic status’): This post is conjecture and hypothesis; the purpose of this post is for me to work through ideas. No authority is claimed.

I am dissatisfied with my throughput as a product engineer 1.

While I hope and believe that I am at least an above-average developer, by throughput 2, in my tool sets of choice, I do not believe my throughput has increased significantly in the last year. Additionally, I am troubled by a nagging feeling that there must be a better way to develop software.

As a (chiefly) Ruby programmer who has never used a strongly and statically typed language professionally, I have been exploring type systems, type theory, and category theory in order to determine if a type system may enable significant throughput increases.

In theory, the benefits of a type system are (a) reducing programming errors, and revealing errors sooner, using the type system, and (b) for statically typed languages, enabling more-powerful program analysis.

In practice, the benefits ability of a type system to reduce programming errors is restricted by the power 3 of the type system. The benefits of more-powerful program analysis are reduced by poor tools, and made unnecessary by powerful language features 4.

What both of these amount to is: a type system can make a programmer more effective in managing complexity. Ideally, they help the programmer manage inherent complexity, the complexity that is required by the problem.

The cost of a type system is incidental complexity. When programmers complain about the boilerplate that languages like Java and C++ force for defining interfaces, they are complaining about having to manage complexity not inherent to the problem they are solving.

The “loss of flexibility” complaint is, in my mind, a symptom of extra incidental complexity; more complex systems are harder to change, regardless of whether the complexity is incidental or inherent.

The question, then, is: does a type system provide more benefit in managing inherent complexity than it costs in incidental complexity?

When phrased this way, the problem is more clearly a matter of choice: a programmer’s method of managing complexity is personal to them.

  1. I use the term ‘product engineer’ to mean ‘a software engineer who has and takes responsibility for designing product features as well’.

  2. “Throughput” in the sense used by Eliyahu M. Goldratt in his books; I choose it to avoid the existing connotations and preconceptions of ‘productivity’.

  3. No precise definition of ‘power’ or ‘powerful’, but a. A type system’s power increases with its ability to correctly and automatically infer types. b. A type system’s power increases with the quantity of restrictions that can be placed on a type. That is, Liquid Haskell’s refinement types are more powerful than regular Haskell types; Idris’ dependent types are more powerful than both, in terms of specificity. The two senses of power can be made to trade off against each other; whether Liquid Haskell’s type system is more powerful than Idris’ is a matter of debate, as I do not know how precisely weight Idris’ dependent types against Liquid Haskell’s much better automatic type inference.

  4. “Powerful” language can be taken to be something like “expressive”; think of the trade off between Java with great IDE refactoring tools, and a ‘more powerful’ language like Ruby, where you rarely need to use those tools in the first place. The ability to manipulate the text of the language source easily is among the most powerful features. A good library for manipulating the AST of the language can substitute. This is why I consider lisp to be one of the most-powerful languages.

Debugging Input Lag on Ubuntu 17.10

linux, ubuntu

I recently had an issue with very slight display lag on my Ubuntu 17.10 desktop, which had a very interesting fix.

For context, I have an i5-4XXX series desktop with a nVidia GTX 970, and two 1080p Samsung BX24440 ‘SyncMaster’ monitors connected via DVI.

A few nights ago, I turned off my computer to move it so that I could switch to a new desk setup. By doing so, I allowed my OS to apply a few kernel updates that require a reboot to be fully applied.

After rebooting, my machine had a noticeable display lag, on everything from mouse movement to hardware-accelerated video playback on YouTube.

My first thought was that by updating my kernel I had inadvertently applied some update that did not agree with my system. In my experience, this is very, very rare on modern Linux distributions, especially Ubuntu, but with the recent Spectre / Meltdown patches, I figured it was still possible.

So, I began rolling back each package that had been updated, one by one. An hour or so later, and after an hour of cursing myself for not just installing NixOS already, I figured I had hit a dead end.

So I dove deeper. Two things were apparent: During the period of lag, Xorg was using about 30% of a core, which is very high for Xorg.

Inspecting the Xorg log in /var/log/Xorg.0.log revealed something curious. Hundreds of messages blocks like this;

[    12.049] (--) NVIDIA(GPU-0): Samsung SMBX2440 (DFP-4): connected
[    12.049] (--) NVIDIA(GPU-0): Samsung SMBX2440 (DFP-4): Internal TMDS
[    12.049] (--) NVIDIA(GPU-0): Samsung SMBX2440 (DFP-4): 330.0 MHz maximum pixel clock
[    12.049] (--) NVIDIA(GPU-0):

So what was the solution?

Tighten my DVI cable.

As far as I can tell, when I moved my computer, the DVI connection between my GPU and my monitor became ever so slightly loose, in such a way that the GPU was detecting the monitor to become disconnected and reconnected about once per second. Even though there was no perceptible monitor flicker or “disconnected” messages, the process of disconnecting and reconnecting appears to have been consuming enough resources to delay frame rendering slightly every time it happened.

So, lesson for you - if you have display lag on a Linux system that you just can’t debug, maybe you just need to tighten your monitor connections.

Notes on Bad Engineering Properties of Object-Oriented Languages

notes, papers

This post is a set of notes on Bad Engineering Properties of Object-Oriented Languages” by Luca Cardelli, available at the time of writing from Cardelli’s site.

This post is mostly intended for my own notes. You may not find it useful.

First, Cardelli opens by defining 6 areas in which one can informally evaluate a language’s effectiveness for software engineering.

He then comments on some areas in which “advancements in procedural programming” have created positive changes in those six areas. Of particular note;

Cardelli then lists ways in which Object Oriented languages fail or score poorly on the metrics in question:

Cardelli then states where work is happening and what still needs to be done:

Notes on Semantics of Multiple Inheritance (Cardelli, 1985)

notes, papers

This post comprises of my notes while reading Luca Cardelli’s 1985 Paper, Semantics of Multiple Inheritance. At the time of writing, a copy of this paper was available for free from ScienceDirect.

These notes are semi-structured, and are intended primarily for my own reflection.

Section 1 -

Here’s a statement that excites me:

The aim of this paper is to present a clean semantics of multiple inheritance and to show that, in the context of strongly typed, statically scoped languages, a sound typechecking algorithm exists. Multiple inheritance is also interpreted in a broad sense: instead of being limited to objects, it is extended in a natural way to union types and to higher-order functional types. This constitutes a semantic basis for the unification of functional and object-oriented programming.

Section 2 - Objects as Records

Section 3 - Records

Section 4 - Variants

The beginning of this section refers to a “disjoint sum”, This made sense to me after reading this page on chaos.org.uk and this explanation of Disjoint Union from Wikipedia. I believe that a ‘disjoint sum’ is just an element in the disjoint union of the two sets in question.

Section 5 - Inheritance Idioms

The first comment in this section is interesting - it shows that inheritance, as defined so far in the paper, is an implication of definitions, and need not be declared explicitly.

There is a paragraph: “The subtype relation only holds on types, and there is no similar relation on objects. Thus we cannot model directly the subobject relation used by, for example, Omega (Attardi, 1981), where we could define the class of gasoline cars as the cars with fuel equal to “gasoline.” This sounds like the author is talking about “dependent types” as used on the wikipedia page for dependent types.

The next paragraph after that introduces a solution by defining a set of fuel types and then defining “gasoline_car” as a subtype of “car”. My gut is that this sort of compile-time-versus-runtime type-checking (and type-definition?) distinction is related, at some level, to the “code versus data” issue that Lisp (partially?) addresses through homoiconicity.

Interesting note, in that “constructor” is “a vague term indicating that, in an implementation, computation can be temporarily suspended thereby avoiding some looping situations”. This makes me wonder; how does object initialization (construction) work in Ruby?

Possibly to be continued

[Note 2018-05-06] The paper has another 7 sections or so, but I put down and temporarily abandoned process back in December of 2017. I decided to publish these notes anyway, again, mostly for my own reflection and reference.

Why Do We Accept Partial Functions?