Goto not that harmful

I use goto all the time. When I have a loop, I goto the top of the loop after each iteration. When a function delegates to another function, I just goto the other function.

Gotos that just transfer control have the problem that the context is implicit. It isn’t obvious from the code what parts of the context are expected to persist across the control transfer. But if you explicitly pass arguments along with your control transfer, then you can see exactly what is carried across the control transfer.

A tail call isn’t “optimized” to a goto, it is a goto. It is a goto that passes arguments. Gotos that pass arguments aren’t harmful.

Embrace the Suck

The key point here is our programmers are Googlers, they’re not researchers. They’re typically fairly young, fresh out of school, probably learned Java, maybe learned C or C++, probably learned Python. They’re not capable of understanding a brilliant language but we want to use them to build good software. So, the language that we give them has to be easy for them to understand and easy to adopt.
— Rob Pike

How sad. Google used to hire top-notch programmers. Now it appears that they have hired a bunch of mediocre programmers who can't even learn how to properly use exceptions or ternary conditionals. Programmers that need “training wheels” on their C.

And how insulting to Googlers to be told that they are not capable of understanding a brilliant language. To be seen as merely a fungible resource to be “used” to build software. I'm sure some of them are capable of understanding a brilliant language. I'm sure that some are capable of learning how to use Haskell or OCaml or Clojure (or F# or Rust or Erlang or Scala) whatever language is best for the task.

Does success come to those that strive for excellence or those that embrace mediocrity?

Decode a Float (Solution)

We can multiply or divide a floating point number by 2 without changing the bits in the mantissa. So we can rescale the number to be in the range [1, 2) by repeatedly multiplying or dividing by 2. The leftmost bit of the mantissa is always 1, but next bit determines whether the number is in the top half of the range or the bottom half. So if the number is equal to or greater than 1.5, the next bit is 1, otherwise it is 0.

If the number is in the range [1, 2), we can subtract 1 from it. The remaining bits will be shifted left until the leftmost bit is 1. If the number is greater than or equal to 1.5, then subtracting 1 will shift the bits left by one. But if the number is in [1, 1.5), we won’t know how many zero bits will be shifted out when we subtract 1. What we’ll do is add .5 to the number to turn on the next bit, then subtract 1 to shift the bits left by one.

Here is the code in Common Lisp:

(defun float->bits (float)
  (cons 1 (read-bits float 0)))

(defun read-bits (float count)
  (cond ((>= count 52) nil)
        ((> float 2.0d0) (read-bits (/ float 2.0d0) count))
        ((< float 1.0d0) (read-bits (* float 2.0d0) count))
        ((>= float 1.5d0) (cons 1 (read-bits (- float 1.0d0) (1+ count))))
        (t (cons 0 (read-bits (- (+ float .5d0) 1.0d0) (1+ count))))))

Note that all these operations are exact and do not cause round off.

Decode a Float

The leftmost bit of any positive binary number is always 1. So if you were to left-justify a positive binary number, the top bit would always be 1. If the top bit is always 1, there is no need to implement it. Floating point numbers use this trick.

You can determine the bits of an integer using only arithmetic operations by repeatedly dividing by two and collecting the remainders. Today’s puzzle is to determine the bits of a floating point number using only arithmetic operations (no decode-float or integer-decode-float).

D-day, 80 years ago today

More than 150,000 troops, 5,000 ships, 13,000 aircraft in the largest amphibious assault in history.

Multithreading and Immutable Data

I was amusing myself by looking at Lisp tutorials. They used the idea of a Tic-Tac-Toe service as a motivating example. You’d be able to play Tic-Tac-Toe against the computer or another opponent.

My immediate thought went to the issue of multithreading. If you were going to serve hundreds of people at once, you’d need to have a multi-threaded service. Multi-threaded code is hard to write and debug, and it is much better if you have a plan before you start than if you try to retrofit it later (that trick never works).

The magic bullet for multi-threading is immutable data. Immutable data is inherently thread-safe. It doesn’t need synchronization or locks. If all your data are immutable, you can pretty much ignore multi-threading issues and your code will just work.

Using a 2D array to represent a Tic-Tac-Toe board is the obvious thing that first comes to mind, but not only are arrays mutable, they virtually require mutation to be of any use. The Lisp tutorials I was looking at all used arrays to represent the board, none of them locked the board or used atomic operations to update it, and all had the potential for race conditions if two threads tried to update the board at the same time. Arrays are essentially inherently thread-unsafe.

I thought about alternative representations for the board. Different representations are more or less amenable for writing code that avoids mutation. I came up with a few ideas:

• Use a 2d array, but copy it before each mutation. This is horribly inefficient, but it is simple.
• Use a 1d array, again copying it before each mutation. This isn’t much different from the 2d array, but iterating over the cells in the board is simpler.
• Keep a list of moves. Each move is a pair of player and position. To determine the state of the board, you iterate over the list of moves and apply them in order. This is a bit more complicated than the array representations, but it is inherently immutable. It also has the advantage that you can rewind the board to any prior position.
• Encode the board as a pair of bitmaps, one for each player.
• Encode the board as a single bitmap, with each cell represented by two bits.
• There are only 3⁹ ways to fill out a Tic-Tac-Toe grid, so you could represent the board as an integer.

Each one of these representations has pros and cons. I wrote up some sample code for each representation and I found that the representation had a large influence on the character of the code that used that representation. In other words, there wasn’t a single general Tic-Tac-Toe program that ended up being specialized to each representation, but rather there were six different Tic-Tac-Toe programs each derived from its own idiosyncratic representation.

In conclusion, it is a good idea to plan on using immutable data when you might be working with a multi-threaded system, and it is worth brainstorming several different representations of your immutable data rather than choosing the first one that comes to mind.

Roll Your Own Syntax

Unlike most languages, Lisp represents its programs as data structures. A Lisp program is a set of nested lists. We can look at a Lisp program as a tree, with each nested list as a node in the tree. The first element of each list indicates the kind of node it is. For instance, a sublist beginning with LET binds local variables, a sublist beginning with IF is a conditional, and so on.

In most languages, it difficult or impossible to add new node types to the syntax tree. The syntax is wired into the language parser and if you even can add new syntax, you have to carefully modify the parser to recognize it. In Lisp, adding new node types is quite easy: you just mention them.

To give an example, suppose you wanted to add a new node to the syntax tree called COMMENT, which would have a string and a subexpression as components. You'd use it like this:

(comment "Avoid fencepost error" (+ x 1))

Here's how you could define the semantics of a COMMENT node in Lisp:

(defmacro comment (string expr)
  expr)

That's it. You can now insert arbitrary COMMENT nodes into your Lisp programs.

Compare that to what you would have to do in a language like Java to add a new kind of node to the syntax tree. You'd have to modify the parser, the lexer, the AST classes, and probably a bunch of other stuff. It's non trivial.

For a more complex example, consider adding transactions to a language. In a language like Java, you'd have to modify the parser to recognize the new syntax, and then you'd have to modify the compiler to generate the correct code. In Lisp, you can just define a new node type:

(defmacro with-transaction (body)
  <complex macro elided>)

And then use it like this:

(with-transaction
  (do-something)
  (do-something-else))

Now obviously you should put some thought into doing this. Adding dozens of random new node types to the language would be a bad idea: readers of the code wouldn't be expecting them. But in some cases, a new node type can be just what is called for to abstract out complexity or boilerplate. Lisp gives you that option.