On null

I’ve had an interesting conversation on the topic of null over the last few days, spurred by the logical disaster of null. I disagreed with the statement in the post that:

Logically-speaking, there is no such thing as Null

This is true in some logics, but not in all logics. Boolean logic as described in An Investigation of the Laws of Thought, admits only two values:

instead of determining the measure of formal agreement of the symbols of Logic with those of Number generally, it is more immediately suggested to us to compare them with symbols of quantity admitting only of the values 0 and 1.

…and in a later chapter he goes on to introduce probabilities. Anyway. A statement either does hold (it has value 1, with some probability p) or it does not (it has value 0, with some probability 1-p; the Law of the Excluded Middle means that there is no probability that the statement has any other value).

Let’s look at an example. Let x be the lemma “All people are mortal”, and y be the conclusion “Socrates is mortal”. What is the value of y? It isn’t true, because we only know that people are mortal and do not know that Socrates is a person. On the other hand, we don’t know that Socrates is not a person, so it isn’t false either. We need another value, that means “this cannot be decided given the current state of our knowledge”.

In SQL, we find a logic that encodes true, false, and “unknown/undecided” as three different outcomes of a predicate, with the third state being given the name null. If we had a table linking Identity to Class and a table listing the Mortality of different Classes of things, then we could join those two tables on their Class and ask “what is the Mortality of the Class of which Socrates is a member”, and find the answer null.

But there’s a different mathematics behind relational databases, the Relational Calculus, of which SQL is an imperfect imitation. In the relational calculus predicates can only be true or false, there is no “undecided” state. Now that doesn’t mean that the answer to the above question is either true or false, it means that that question cannot be asked. We must ask a different question.

“What is the set of all Mortality values m in the set of tuples (m, c) where c is any of the values of Class that appear in the set of tuples (x, c) where x is Socrates?”

Whew! It’s long-winded, but we can ask it, and the answer has a value: the empty set. By extension, we could always change any question we don’t yet know the answer to into a question of the form “what is the set of known answers to this question”. If we know that the set has a maximum cardinality of 1, then we have reinvented the Optional/Maybe type: it either contains a value or it does not. You get its possible value to do something by sending it a foreach message.

And so we ask whether we would rather model our problem using a binary logic, where we have to consider each question asked in the problem to decide whether it needs to be rewritten as a set membership test, or a ternary logic, where we have to consider that the answer to any question may be the “I don’t know” value.

Implementationally-speaking, there are too many damn nulls

We’ve chosen a design, and now we get to implement it. In an implementation language like Java, Objective-C or Ruby, a null value is supplied as a bottom type, which is to say that there is a magic null or nil keyword whose value acts as a subtype of all other types in the system. Good: we get “I don’t know” behaviour for free anywhere we might want it. Bad: we get that behaviour anywhere else too, so we need to think to be sure that in all places where “I don’t know” is not an answer, that invariant holds in our implementation, or for those of us who don’t like thinking we have to pepper our programs with defensive checks.

I picked those three languages as examples, by the way, because their implementations of null are totally different so ruin the “you should never use a language with null because X” trope.

  • Java nulls are terminal: if you see a null, you blew it.
  • Objective-C nulls are viral: if you see a null, you say a null.[*]
  • Ruby nulls are whatever you want: monkey-patch NilClass until it does your thing.

[*] Objective-C really secretly has _objc_setNilReceiver(id), but I didn’t tell you that.

Languages like Haskell don’t have an empty bottom, so anywhere you might want a null you are going to need to build a thing that represents a null. On the other hand, anywhere you do not want a null you are not going to get one, because you didn’t tell your program how to build one.

Either approach will work. There may be others.

In defense of `id`

Something you can’t see about my dotSwift talk on OOP in FP in Swift is that to make the conference more interesting while the AV was set up for the next speaker, Daniel Steinberg invited me over to a side table for a question and answer session. He had some great questions and I had some adequate answers; that is now lost to time.

One thing he asked was about how I do things differently when I’m working in Objective-C and in Swift, and I mentioned that I tend not to use the type system in ObjC and just call all of my variables id unless they are C types or the compiler asks otherwise. You can see an example of this in my UIKonf 1995 talk.

I argue (back in 2018, at dotSwift, in the bit that was videoed) that all objects have the same type. Just as I can define the “type” Set through its function signature:

typealias Set<T> = (T) -> Bool

so I can define the “type” object through its function signature. An object – any object – is a function that responds to messages by turning selectors into methods:

typealias Object = (Selector) -> IMP

Now if all objects have the same type, why would I want to use different types for different objects?

Of course, there are reasons to want to refine the definition of an object from “any object” to “an object like this”, but these refinements are inaccessible using Objective-C’s type system (or Java’s, or Swift’s, or most other programming languages). Any object responds to any message, but for the most part they respond by doing whatever the default error-raising behaviour is which is not particularly interesting and doesn’t solve your customer’s problem. So what we want to be able to say is “this object is one that responds to a particular collection of messages in a way that is what I need here”.

We have two tools available to us, and neither gives us an answer to that question. The first is the protocol (or Java interface): we can say “this object is one that has implementations of methods for a particular collection of messages”. That’s not the same as the question we want to answer – it says nothing about whether the object responds in the ways we want. It’s also not generally the correct answer – an object that has the methods we want and behaves in the expected way but that didn’t have the protocol conformance recorded at compile time (even if it conformsToProtocol: at run time) does not satisfy the compiler type check for protocol conformance.

Even less generally useful is using the class name as the type. Classes are ways to say “here is a collection of objects that all have common behaviour and data”; well for starters I don’t care about the data, but also just because those objects have the properties I want, doesn’t mean that others outside that place in the inheritance tree don’t.

I also can’t rely on subtypes behaving as I need, but the compiler type checker will pretend that if I asked for an instance of one class, and got an instance of a subclass, then I got the thing I wanted. Inheritance, in many languages including Objective-C, Java and similar, is a way to borrow behaviour from one class in another class. If we also want refinement from inheritance we have to add a bunch of rules that almost every programming language not named after the designer of the Garabit Viaduct does not support.

So there are three imprecise ways to ask for objects by behaviour in Objective-C, and I choose the one with the least typing. Even once you amortise the cost of this blog post.

machoo – Object-Oriented Programming in Object-Oriented Programming in the GNU HURD

For the last few weeks, my when-I-get-to-it project has been machoo, which is sort of an object-oriented system on the HURD but mostly an excuse to learn about how Mach messaging works.

I decided to build a Smalltalk-style “give me any old selector, and I’ll do something with it” messaging system on Mach, which is already a messaging system. I don’t yet know whether this is a good idea, but I like the design principle of highly loosely-coupled objects telling each other the names of the things to do.

The substrate for this system is MIG, the Mach Interface Generator. It takes descriptions of routines in an IDL that include the names of the supported routines and the argument names, types and return types. It’d certainly be possible to build each message I want to be able to send as a MIG routine, but then the client would have to import interfaces for every type it wanted to use: no bad thing, and many OO systems work that way, but not what I want.

MIG generates a ‘demuxer’ function that examines a message sent to a port, and dispatches it to a handler to the named routine. As an aside, it is highly likely that I’ve got one to many layers of indirection; that if I wrote my own function to take the place of the demuxer I could handle dispatch there without receiving arguments from a dispatcher to do more dispatch. OK, I could, but I don’t currently know how.

So what I ended up with is a two-level system, something like Smalltalk or ObjC. A “class” is a HURD translator registered on the filesystem, you send the zero-arguments message machoo_create_object to the class and get a send right to the new object. This is two-level in that if you need to initialise the object, you would then send an init message to the created object. Objects are messaged using the machoo_msg_send routine, which takes a string selector like Smalltalk.

There’s currently exactly one implementation of a class, a do-nothing null object class. It does the thing that I would extract out into a pattern for other classes: its response to a machoo_create_object message is to spawn a new thread to back the new object. So it’s like an Erlang-style system where each object has its own execution context, except that task switching is handled by the kernel rather than some virtual machine. All of the objects of a class are in a single task, and they are each on their own thread.

I still need to solve some problems, like how to return a reference to ‘this object’ from a message. I need to build more than one class of object, and extract out the common parts of class-ness so that a new class is only defined by its response to messages. So far this is proving to be an interesting and educational project.

Reasoning about reasoning about software

Functional programmers like to claim that you can’t reason about mutable state programs. Some thoughts:

  • the first half of the book A Discipline of Programming by Edsger W. Dijkstra tells you how to do it. That half of the book is approximately 100 pages (the remainder of the book is worked examples).
  • object-oriented programming breaks a software system up into separate systems running miniature, message-driven programs as if on separate computers. Therefore the consideration of “mutable state” can be split in two: the state internal to the object and the state external to the object which sends messages to the object but is ignorant of its internals. If you can’t split the state that way, you have bad encapsulation.
  • The reasoning done about the external and internal behaviours had better match at the interface. Design by contract probably helps here.
  • Given a state S, an operation O can be defined as \(O(args \times S) \rightarrow (R \times S’)\), i.e. it returns a result R and updates the state to S’.
  • However, Bertrand Meyer introduced Command-Query Separation in the 1980s, so you only need to know \(O(args \times S) \rightarrow (R \times S)\) and \(O(args \times S) \rightarrow (\emptyset \times S’)\).
  • Various history “traces” can be considered equivalent and therefore a lot of knowledge about the historical state transitions elided, simplifying the reasoning. For example, given a well-designed stack, it is impossible to distinguish the history of stack.push(3); stack.pop(); stack.push(7) from stack.push(7).
  • Various operations on the state are irrelevant to the behaviour of an operation under consideration. In reasoning about the final operation in a = 3; b = 7; c = 9; stack.push(2) you do not need to consider the assignment operations (and indeed their presence may indicate a cohesion problem in your design).
  • The one remaining source of difficulty is aliasing; I do need to know about the elided operations in the sequence x = 7; *y = &x; ...; z=f(x). This is aliasing, not mutable state.

Falsehoods programmers believe about programming

  • There is no ethical impact of my job; I build technological systems and it’s up to others how they use them.
  • Software is a purely technical discipline.
  • There is some innate affinity for computer programming which you must be born with, and cannot be taught.
  • Allowing people who are unlike me to program can only be achieved by “lowering the bar”.
  • Compiled languages are always faster.
  • floating point calculations will introduce non-deterministic errors into numerical results.
  • OK, they introduce some errors into numerical results.
  • alright I understand that floating point calculations are imprecise not inaccurate, Mister Pedantic Blog Author, but I cannot know what that imprecision is.
  • at least the outcome of integer maths is always defined.
  • fine, it’s not defined. But whatever it was, the result of doing arithmetic on two numbers that each fit in a data register itself fits in a data register.
  • every computer on sale today (2017) uses two’s complement notation for negative numbers.
  • every computer on sale today uses a register width that’s a multiple of eight bits.
  • the bug isn’t in my code.
  • the bug isn’t in the library.
  • the bug isn’t in the operating system.
  • the bug isn’t in the compiler.
  • the bug isn’t in the kernel.
  • the bug isn’t in the hardware.
  • bug-free computer hardware is completely deterministic.
  • the lines on the hardware bus/bridge are always either at the voltage that represents 0 or the voltage that represents 1.
  • if my tests cover 100% of my lines of code then I have complete coverage.
  • if my tests cover 100% of my statements then I have complete coverage.
  • if my tests cover 100% of my conditions then I have complete coverage.
  • if I have complete test coverage then I have no bugs.
  • if I have complete test coverage then I do not need a type system.
  • if I have a type system then I do not need complete test coverage.
  • no hacker will target my system.
  • information security is about protecting systems from hackers.
  • if the problem is SQL Injection, then the solution is to replace SQL; NoSQL Injection is impossible.
  • my project is a special snowflake; I can reject that technique I read about without considering it.
  • my project is much like that unicorn startup or public company’s project; I can adopt that technique I read about without considering it.
  • people who do not use my language, technique, framework, tool, methodology, paradigm or other practice do not get it.
  • any metaprogramming expansion will resolve in reasonable time.
  • any type annotation will resolve in reasonable time.
  • OK, well at least any regular expression will resolve in reasonable time.
  • can you at least, please, allow that regular expressions are regular?

I’m sure there must be more.

Update The following were added later; where they were supplied by others there is citing link. There are also good examples in the comments.

  • You need a computer science degree to be a good programmer.
  • A computer science course contains nothing useful to programmers.
  • Functional Programming is a silver bullet.
  • Rust is a silver bullet.
  • There is a silver bullet.
  • There can be no silver bullet.
  • Rewriting a working software system is a good idea.
  • I can write a large system in a memory unsafe language without introducing vulnerabilities.
  • I can write a large system in a memory safe language without introducing vulnerabilities.
  • Software is an engineering discipline.
  • Software is a scientific discipline.
  • Discourse on a topic is furthered by commenting on how I already knew a fact that was stated.
  • A falsehood about programming has no value unless the author of the falsehood provides supporting evidence to my satisfaction.

Two ways of thinking

I’ve used this idea in conversations for years, and can’t find a post on it, which I find surprising but there you go. There are, broadly speaking, two different ways to look at programming languages. And I think that these mean two different ways to select programming languages, which are asymmetric. However, they can lead to the same choice, but viewed in different ways: if you use one of those languages then you need to understand that these different views exist to understand decisions made by programmers working in those languages.

On the one hand, the Language Lawyer seeks out languages with plenty of esoterica and specifics, in order to become proficient at recalling those esoterica and demonstrating their correct application. The Language Lawyer loves that reference and value types in swift are actually called class and struct, or that the difference between class and struct in C++ is the default member visibility, and that neither is actually related to the words class or struct. They are delighted both to know and to explain that in Perl 5, @var, \var and $var refer to the same variable but are accessed in different contexts and what they evaluate to in those contexts. They are excited to explain that technically the admonition that you must always return a value from a non-void function in C is not true, because since C99 if you have a function called main that returns control without returning a value, the compiler will implicitly return 0.

The Language Lawyer seeks out a language with such esoterica. But learning it is complex and time-consuming, so they probably don’t change particularly often. In fact, changing language may be deleterious, because then other people will know the esoterica that they get caught out on. Imagine knowing how the function overloading rules in C++ work, then trying something similar in Java and finding that you’re wrong. And that somebody else knows that. The shame! Once their language is chosen, the Language Lawyer will form heuristic rules of which language feature to use when solving which problem.

Standing in the other corner, the Lazy Evaluator wants to avoid those edge cases, because it makes them think about the programming language, not the software problem. They’d much prefer to have an environment in which there’s as much as one way to express their solution, then worry about how to express their solution using that one tool. The Lazy Evaluator loves Ruby because Everything Is An Object (and they love Io more because in Ruby there are also classes). The Lazy Evaluator is delighted to know that in Lisp, Everything Is A List. They are excited to be programming in Haskell, where Everything Is A Function.

Both of these people can be happy with the same programming language, though clearly this will be for different reasons, and their different thought processes will bring them into conflict. The Lazy Evaluator will be happy enough using the third-most common C-family language, C++– (full name: “C++98 but never use exceptions or templates, avoid multiple inheritance, and [never/always] mark methods as virtual”). The Language Lawyer will enjoy demonstrating const-correctness and the difference between l-, r-, pr-, gl- and x-values, but the two will come to blows over whether the Lazy Evaluator is denying the full elegant expressiveness of the language by proscribing exceptions.

Similarly, the Lazy Evaluator can look at JavaScript, see the simple classless object model with dynamic dispatch remembered from Self or Io, even notice that Functions Are Objects Too and work in that Everything Is An Object paradigm. The Language Lawyer can be confident that at some point, all of the weird coercion behaviour, the Which this Is That this Anyway question, and the You Need That Flag With This Polyfill To Get That Language Feature issues will come up. But the Lazy Evaluator will notice that That Flag also enables class syntax and arrow functions, we already have prototypes and function functions, and disagreement will ensue.

So in what way are those ways of thinking asymmetric? Invoking Hickey’s Corollary, you can never be recomplecting. It’s easier to compromise on C++ But Without Exceptions than it is to compromise on Lisp But We’ll Add Other Atom Types. You can choose JavaScript But Never Use this, you can’t choose Haskell But With Type-Escaping Side Effects.

This isn’t really about programming languages, it’s about any form of model or abstraction. Languages are a great example though. I think it’s a mindset thing. Your task is to solve this problem, using this tool. Are you focusing on the bit that’s about the problem, or the bit that’s about the tool? Both are needed.

In defence of assertions

The year is 2017 and people are still recommending processing out assertions from release builds.

  1. many assertions are short tests (whether or not that’s a good thing): this variable now has a value, this number is now greater than zero), which won’t cost a lot in production. Or at least, let me phrase this another way: many assertions are too cheap to affect performance metrics in many apps. Or, let me phrase that another way: most production software probably doesn’t have good enough performance monitoring to see a result, or constrained enough performance goals to care about the result.

  2. The program counter has absolutely no business executing the instruction that follows a failed assertion, because the programmer wrote the subsequent instructions with the assumption that this would never happen. Yes, your program will terminate, leading to a 500 error/unfortunate stop dialog/guru meditation screen/other thing, but the alternative is to run…something that apparently shouldn’t ever occur. Far better to stop at the point of problem detection, than to try to re-detect it based on a surprising and unsupportive problem report later.

  3. assertions are things that programmers believe to always hold, and it’s sensible to take issue with the words always and believe. There’s an argument that goes:

    1. I have never seen this situation happen in development or staging.
    2. I got this job by reversing a linked list on a whiteboard.
    3. Therefore, this situation cannot happen in production.

    but unfortunately, there’s a flaw between the axioms and the conclusion. For example, I have seen the argument “items are added to this list as they are received, therefore these items are in chronological order” multiple times, and have seen items in another order just as often. Assertions that never fire on programmer input give false assurance.

Your build needs to be better

I’ve said it before, build systems are a huge annoyance. If your build is anything other than seemingly instantaneous, it’s costing you severe money.

Your developers are probably off reading HN, or writing blog posts about how slow builds cost them, while the build is going. When they finish doing that, which may be some time after the build completes, they’ll have forgotten some of what they were doing and need to spend some time getting back up to speed.

Your developers are probably suspicious of any build failure, thinking that “the build is flaky” rather than “I made a mistake”. They’ll press the button again and go back to HN. When the same error occurs twice, they might look into it.

Your developers probably know that the build is slow, but not which bit of the build is slow. And they don’t have time to investigate that, where it takes so long to get any work done anyway. So everyone will agree that “there is a problem”, but nothing will get done. Or maybe cargo-cult things will get done, things that speed up “builds” but are not the problem with your build.

The Joel test asks whether you can make a build in one test. Insufficient. If you notice when you’re making a build, you’re slowing your developers down.

…which is not always the worst thing, of course. Sometimes a lengthy translation step from some source language to some optimised form of a machine language program yields better results for your customers, because they get to use a faster program and don’t need to care about the time taken to prepare that program. But let’s be clear: that’s part of the release, and your developers don’t always need to be working from the released product (in fact, they’re usually not). Releases should be asynchronous, and the latency between having something ready to be released and having released it can be fairly high, compared with the latency between having created some source and being able to investigate its utility.

Nonetheless, that should all go off in the background. So really, builds and releases should both be non-events to the developers.