Archive:
In this section: Subtopics:
Comments disabled |
Sat, 17 Nov 2018
How do you make a stella octangula?
Yesterday Katara asked me out of nowhere “When you make a stella octangula, do you build it up from an octahedron or a tetrahedron?” Stella octangula was her favorite polyhedron eight years ago. “Uh,” I said. “Both?” Then she had to make one to see what I meant. You can start with a regular octahedron: Then you erect spikes onto four of the octahedron's faces; this produces a regular tetrahedron: Then you erect spikes onto the other four of the octahedron's faces. Now you have a stella octangula. So yeah, both. Or instead of starting with a unit octahedron and erecting eight spikes of size 1, you can start with a unit tetrahedron and erect four spikes of size ½. It's both at once. [Other articles in category /math] permanent link Wed, 14 Nov 2018
Counting paths through polyhedra
A while back someone asked on math stack exchange how many paths there were of length !!N!! from one vertex of a dodecahedron to the opposite vertex. The vertices are distance 5 apart, so for !!N<5!! the answer is zero, but the paths need not be simple, so the number grows rapidly with !!N!!; there are 58 million paths of length 19. This is the kind of thing that the computer answers easily, so that's where I started, and unfortunately that's also where I finished, saying:
Another user reminded me of this and I took another whack at it. I couldn't remember what my idea had been last year, but my idea this time around was to think of the dodecahedron as the Cayley graph for a group, and then the paths are expressions that multiply out to a particular group element. I started by looking at a tetrahedron instead of at a dodecahedron, to see how it would work out. Here's a tetrahedron. Let's say we're counting paths from the center vertex to one of the others, say the one at the top. (Tetrahedra don't have opposite vertices, but that's not an important part of the problem.) A path is just a list of edges, and each edge is labeled with a letter !!a!!, !!b!!, or !!c!!. Since each vertex has exactly one edge with each label, every sequence of !!a!!'s, !!b!!'s, and !!c!!'s represents a distinct path from the center to somewhere else, although not necessarily to the place we want to go. Which of these paths end at the bottom vertex? The edge labeling I chose here lets us play a wonderful trick. First, since any edge has the same label at both ends, the path !!x!! always ends at the same place as !!xaa!!, because the first !!a!! goes somewhere else and then the second !!a!! comes back again, and similarly !!xbb!! and !!xcc!! also go to the same place. So if we have a path that ends where we want, we can insert any number of pairs !!aa, bb, !! or !!cc!! and the new path will end at the same place. But there's an even better trick available. For any starting point, and any letters !!x!! and !!y!!, the path !!xy!! always ends at the same place as !!yx!!. For example, if we start at the middle and follow edge !!b!!, then !!c!!, we end at the lower left; similarly if we follow edge !!c!! and then !!b!! we end at the same place, although by a different path. Now suppose we want to find all the paths of length 7 from the middle to the top. Such a path is a sequence of a's, b's, and c's of length 7. Every such sequence specifies a different path out of the middle vertex, but how can we recognize which sequences end at the top vertex? Since !!xy!! always goes to the same place as !!yx!!, the order of the
seven letters doesn't matter.
A complicated-seeming path like Since the paths we want are those that go to the same place as the trivial path !!c!!, we want paths that have an even number of !!a!!s and !!b!!s and an odd number of !!c!!s. Any path fitting that description will go to same place as !!c!!, which is the top vertex. It's easy to enumerate such paths:
Here something like “cccbbbb” stands for all the paths that have three c's and four b's, in some order; there are !!\frac{7!}{4!3!} = 35!! possible orders, so 35 paths of this type. If we wanted to consider paths of arbitrary length, we could use Burnside's lemma, but I consider the tetrahedron to have been sufficiently well solved by the observations above (we counted 547 paths by hand in under 60 seconds) and I don't want to belabor the point. Okay! Easy-peasy! Now let's try cubes: Here we'll consider paths between two antipodal vertices in the upper right and the lower left, which I've colored much darker gray than the other six vertices. The same magic happens as in the tetrahedron. No matter where we
start, and no matter what !!x!! and !!y!! are, the path !!xy!! always
gets us to the same place as !!yx!!. So again, if some complicated
path gets us where we want to go, we can permute its components into
any order and get a different path of the same langth to the same
place. For example, starting from the upper left, And again, because !!xx!! always make a trip along one edge and then
back along the same edge, it never goes anywhere. So the three paths
in the previous paragraph also go to the same place as We want to count paths from one dark vertex to the other. Obviously
To get paths of length 5, we must insert a pair of matching letters
into one of the paths of length 3. Without loss of generality we can
assume that we are inserting To get paths of length 7, we must insert two pairs. If the two pairs are the same, there are !!\frac{7!}{5!} = 42!! possible orders and 3 choices about which letters to insert, for a total of 126. If the two pairs are different, there are !!\frac{7!}{3!3!} = 140!! possible orders and again 3 choices about which pairs to insert, for a total of 420, and a grand total of !!420+126 = 546!! paths of length 7. Counting the paths of length 9 is almost as easy. For the general case, again we could use Burnside's lemma, or at this point we could look up the unusual sequence !!6, 60, 546!! in OEIS and find that the number of paths of length !!2n+1!! is already known to be !!\frac34(9^n-1)!!. So far this technique has worked undeservedly well. The original problem wanted to use it to study paths on a dodecahedron. Where, unfortunately, the magic property !!xy=yx!! doesn't hold. It is possible to label the edges of the dodecahedron so that every sequence of labels determines a unique path: but there's nothing like !!xy=yx!!. Well, nothing exactly like it. !!xy=yx!! is equivalent to !!(xy)^2=1!!, and here instead we have !!(xy)^{10}=1!!. I'm not sure that helps. I will probably need another idea. The method fails similarly for the octahedron — which is good, because I can use the octahedron as a test platform to try to figure out a new idea. On an octahedron we need to use four kinds of labels because each vertex has four edges emerging from it: Here again we don't have !!(xy)^2=1!! but we do have !!(xy)^3 = 1!!. So it's possible that if I figure out a good way to enumerate paths on the octahedron I may be able to adapt the technique to the dodecahedron. But the octahedron will be !!\frac{10}3!! times easier. Viewed as groups, by the way, these path groups are all examples of Coxeter groups. I'm not sure this is actually a useful observation, but I've been wanting to learn about Coxeter groups for a long time and this might be a good enough excuse. [Other articles in category /math] permanent link Tue, 13 Nov 2018
A puzzle about representing numbers as a sum of 3-smooth numbers
I think this would be fun for a suitably-minded bright kid of maybe 12–15 years old. Consider the following table of numbers of the form !!2^i3^j!!:
Given a number !!n!!, is is possible to represent !!n!! as a sum of entries from the table, with the following constraints:
For example, one may not represent !!23 = 2 + 12 + 9!!, because the !!12!! is in a lower row than the !!2!! to its left.
But !!23 = 8 + 6 + 9!! is acceptable, because 6 is higher than 8, and 9 is higher than 6.
Or, put another way: can we represent any number !!n!! in the form $$n = \sum_i 2^{a_i}3^{b_i}$$ where the !!a_i!! are strictly decreasing and the !!b_i!! are strictly increasing? Spoiler:
Sadly, the representation is not unique. For example, !!8+3 = 2+9!!, and !!32+24+9 = 32+6+27 = 8+12=18+27!!. [Other articles in category /math] permanent link Fri, 09 Nov 2018
Why I never finish my Haskell programs (part 3 of ∞)
I'm doing more work on matrix functions. A matrix represents a
relation, and I am representing a matrix as a $$ \require{enclose} \begin{pmatrix}1&2\\3&4\end{pmatrix}\enclose{circle}{\oplus} \begin{pmatrix}10&20\\30&40\end{pmatrix}= \begin{pmatrix} 11 & 21 & 12 & 22 \\ 31 & 41 & 32 & 42 \\ 13 & 23 & 14 & 24 \\ 33 & 43 & 34 & 44 \end{pmatrix} $$ No problem, this is what
gives But my matrices are nested lists, so I need to apply the
(The Now
does indeed produce the result I want, except that the type markers are still in there: instead of
I get
No problem, I'll just use
And now matrix addition is finished:
This works perfectly. But the
into this:
with the idea that I will now have The first sign that something is going wrong is that
where I was hoping for something more like this:
which is not reasonable to expect: how can Haskell be expected to
figure out I wanted two diferent functors in there when there is only one
Telling GHC explicitly what type I want for I get the same answers that Haskell got, but I can't see where the difference was coming from. So now, instead of defining matrix operations, I am looking into the
type unification algorithm and trying to figure out why And that is yet another reason why I never finish my Haskell programs. (“What do you mean, λ-abstraction didn't work?”) [Other articles in category /prog/haskell] permanent link Thu, 08 Nov 2018
Haskell type checker complaint 184 of 698
I want to build an adjacency matrix for the vertices of a cube; this
is a matrix that has
This compiles and GHC infers the type
Fine. Now I want to build the adjacency matrix, which is completely straightforward:
Ha ha, no it isn't; in Haskell nothing is straightforward. This
produces 106 lines of type whining, followed by a failed compilation.
Apparently this is because because To fix this I have to say explicitly what I mean by
Here's another way I could accomplish this:
Or how about this?
I think there must be something really wrong with the language design here. I don't know exactly what it is, but I think someone must have made the wrong tradeoff at some point. [Other articles in category /prog/haskell] permanent link
How not to reconfigure your sshd
Yesterday I wanted to reconfigure the Except, it didn't work. I added:
and signalled the server, then made a new connection to see if it
would print
which seemed straightforward enough, and I put some text into
I tried a couple of other things but none of them seemed to work. Okay, maybe the
This was a head-scratcher. Was I modifying the wrong file? It semed
hardly possible, but I don't administer this machine so who knows? I
tried Eventually I hit upon the answer, and I wish I had some useful piece of advice here for my future self about how to figure this out. But I don't because the answer just struck me all of a sudden. (It's nice when that happens, but I feel a bit cheated afterward: I solved the problem this time, but I didn't learn anything, so how does it help me for next time? I put in the toil, but I didn't get the full payoff.) “Aha,” I said. “I bet it's because my connection is multiplexed.” Normally when you make an There is a “multiplexing” option you can use instead. The handshaking
process still occurs as usual for the first connection. But once the
connection succeeds, there's no need to start all over again to make a
second connection. You can tell I had my local I verified this by telling
This time I saw the MOTD and when I reinstated that (It occurs to me now that I could have tried to SIGHUP the child server process that my connections were going through, and that would probably have reconfigured any future virtual connections through that process, but I didn't think of it at the time.) Then I went home for the day, feeling pretty darn clever, right up
until I discovered, partway through writing this article, that I can't
log in because all I get is [Other articles in category /Unix] permanent link Fri, 02 Nov 2018
Another trivial utility: git-q
One of my favorite programs is a super simple Git utility called
The current head ( From this V, it appears that what happened was: I pushed Except wait, what if that's not what happened? What if what
happened was, Formerly I would have used
and it produces the dates on which each commit was created:
Aha, it was as I originally thought: Although the commit date is the default output, the
and
The program is in my personal git-util repository but it's totally simple and should be easy to customize the way you want:
[Other articles in category /prog] permanent link Mon, 29 Oct 2018Warning: Long and possibly dull. I spent a big chunk of today fixing a bug that should have been easy but that just went deeper and deeper. If you look over in the left sidebar there you'll se a sub-menu titled “subtopics” with a per-category count of the number of articles in each section of this blog. (Unless you're using a small display, where the whole sidebar is suppressed.) That menu was at least a year out of date. I wanted to fix it. The blog software I use is the wonderfully terrible
Blosxom. It has a plugin system,
and the topic menu was generated by a plugin that I wrote some time
ago. When the When I regenerate the static site, the
The reason the menu wasn't being updated is that at some point in the
past, I changed the way
Over the years I had extended this to eight or nine, and I felt it was getting unwieldy, so at some point I changed it to pass a hash, like this:
When I made this conversion, I had to convert all the plugins. I
missed converting Anyway, this was easily fixed, or should have been easily fixed. All I needed to do was convert the plugin to use the new calling convention. Ha! One thing all my plugins do when they start up is write a diagnostic log, something like this:
Then whenever the plugin has something to announce it just does
If the article has already been seen, it remains silent. Later I can look in Blosxom has an option to generate pages on demand for a web browser,
and I use this for testing.
I didn't see this. I saw the startup message and nothing else. I did
a bunch of very typical debugging, such as having the plugin print a
message every time
Nothing. But I knew that
to
and discovered that each time I loaded the page, the plugin was run
exactly twice. When I had had But why was the plugin being run twice? This took quite a while to track down. At first I suspected that Blosxom was doing it, either on purpose or by accident. My instance of Blosxom is a hideous Frankenstein monster that has been cut up and reassembled and hacked and patched dozens of times since 2006 and it is full of unpleasant surprises. But the problem turned out to be quite different. Looking at the Apache server logs I saw that the browser was actually making two requests, not one:
Since the second request was for a nonexistent article, the
So I dug down into the This took a very long time to track down, and I think it was totally
not my fault. When I first wrote This magic tag was not in an Then began a tedious ten-year odyssey through the The end result this time was that it wasn't in any of the usual
places. It was 100% not my fault:
The output is:
No trace of the With that fixed I went back to finish the work on the But no, every article on the page, every article from 2018, was being processed every time I rebuilt the page. And the topic counts were going up, up, up. This also took a long time to track down, because again the cause was so unlikely. I must have been desperate because I finally found it by doing something like this:
Yep, it died. Either Berkeley DB, or Perl's I fixed this by discarding the entire database and rebuilding it. I
needed to clean out the I am sick of DB files. I am never using them again. I have been bitten too many times. From now on I am doing the smart thing, by which I mean the dumb thing, the worse-is-better thing: I will read a plain text file into memory, modify it, and write out the modified version whem I am done. It will be simple to debug the code and simple to modify the database. Well, that sucked. Usually this sort of thing is all my fault, but this time I was only maybe 10% responsible. At least it's working again. [ Addendum: I learned that discarding the [Other articles in category /prog/bug] permanent link Sun, 28 Oct 2018
More about auto-generated switch-cases
Yesterday I described what I thought was a cool hack I had seen in
Simon Tatham wrote to me with a technique for compile-time generation
of int set_the_mtime(...) { static int switch_step = 0; switch (switch_step) { #ifdef METHOD_1_MIGHT_WORK case ???: if (method_1_works(...)) break; switch_step++; /* FALLTHROUGH */ #endif #ifdef METHOD_2_MIGHT_WORK case ???: if (method_2_works(...)) break; switch_step++; /* FALLTHROUGH */ #endif ... etc. ... } return 1; } M. Tatham suggested this: #define NEXT_CASE switch_step = __LINE__; case __LINE__ You use it like this: int set_the_mtime(...) { static int switch_step = 0; switch (switch_step) { default: #ifdef METHOD_1_MIGHT_WORK NEXT_CASE: if (method_1_works(...)) break; /* FALLTHROUGH */ #endif #ifdef METHOD_2_MIGHT_WORK NEXT_CASE: if (method_2_works(...)) break; /* FALLTHROUGH */ #endif ... etc. ... } return 1; } The One possible drawback of this method is that if the file contains more
than 255 lines, the case labels will not fit in a single byte. The
ultimate effect of this depends on how the compiler handles You could use
Addendum 20181029: Several people have asked for an explanation of why
the
Wikipedia says:
[Other articles in category /prog] permanent link Sat, 27 Oct 2018
A fun optimization trick from rsync
I was looking at the
The key item here is the static The actual code is a little more sophisticated than this. The list of
cases is built depending on the setting of several compile-time config
flags, so that the code that is compiled only includes the methods
that are actually callable. Calling one of the methods can produce
three distinguishable results: success, real failure (because of
permission problems or some such), or a sort of fake failure
( case 7:
if (method_7_works(...))
break;
if (errno != ENOSYS)
return -1; /* real failure */
switch_step++;
/* FALLTHROUGH */
On top of this there's another trick: since the various cases are
conditionally compiled depending on the config flags, we don't know
ahead of time which ones will be included. So the #include "case_N.h" if (method_7_works(...)) break; ... #include "case_N.h" if (method_8_works(...)) break; ... The first time we
Unfortunately you can only use this trick one switch per file.
Although I suppose if you really wanted to reuse it you could make a
[ Addendum 20181028: Simon Tatham brought up a technique for
generating the [Other articles in category /prog] permanent link Fri, 26 Oct 2018
A snide addendum about implicit typeclass instances
In an earlier article I demanded:
“This” being that instead of raising a type error, Haskell quietly accepts this nonsense:
but it clutches its pearls and faints in horror when confronted with this expression:
Nobody did explain this. But I imagined
someone earnestly explaining: “Okay, but in the first case, the
Yeah, yeah, I know that. Hey, you know what else is a functor? The
identity functor. If I understand this is a terrible idea. To be clear, what I want is for it to collapse on the divan for both expressions. Pearl-clutching is Haskell's finest feature and greatest strength, and it should do it whenever possible. [Other articles in category /prog/haskell] permanent link Wed, 24 Oct 2018A few years back I asked on history stackexchange:
My question being: why 13½ pence? This immediately attracted an answer that was no good at all. The author began by giving up:
I've met this guy and probably you have too: he knows everything worth knowing, and therefore what he doesn't know must be completely beyond the reach of mortal ken. But that doesn't mean he will shrug and leave it at that, oh no. Having said nobody could possibly know, he will nevertheless ramble for six or seven decreasingly relevant paragraphs, as he did here. 45 months later, however, a concise and pertinent answer was given by Aaron Brick:
This answer makes me happy in several ways, most of them positive. I'm glad to have a lead for where the 13½ pence comes from. I'm glad to learn the odd word “loonslate”. And I'm glad to be introduced to the bizarre world of pre-union Scottish currency, which, in addition to the loonslate, includes the bawbee, the unicorn, the hardhead, the bodle, and the plack. My pleasure has a bit of evil spice in it too. That fatuous claim that the question was “historically unanswerable” had been bothering me for years, and M. Brick's slam-dunk put it right where it deserved. I'm still not completely satisfied. The Scottish mark was worth ⅔ of a pound Scots, and the pound Scots, like the English one, was divided not into 12 pence but into 20 shillings of 12 pence each, so that a Scottish mark was worth 160d, not 13½d. Brick cites William Hone, who claims that the pound Scots was divided into twelve pence, rather than twenty shillings, so that a mark was worth 13⅔ pence, but I can't find any other source that agrees with him. Confusing the issue is that starting under the reign of James VI and I in 1606, the Scottish pound was converted to the English at a rate of twelve-to-one, so that a Scottish mark would indeed have been convertible to 13⅔ English pence, except that the English didn't denominate pence in thirds, so perhaps it was legally rounded down to 13½ pence. But this would all have been long after the establishment of the 13½d in the Halifax gibbet law and so unrelated to it. Or would it? Maybe the 13½d entered popular consciousness in the 17th century, acquired the evocative slang name “hangman’s wages”, and then an urban legend arose about it being the cutoff amount for the Halifax gibbet, long after the gibbet itself was dismantled arond 1650. I haven't found any really convincing connection between the 13½d and the gibbet that dates earlier than 1712. The appearance of the 13½d in the gibbet law could be entirely the invention of Samuel Midgley. I may dig into this some more. The 1771 Encyclopædia Britannica has a 16-page article on “Money” that I can look at. I may not find out what I want to know, but I will probably find out something. [Other articles in category /history] permanent link Tue, 23 Oct 2018
Getting Applicatives from Monads and “>>=” from “join”
I conplained recently about GHC not being able to infer an
Applicative instance from a type that already has a Monad
instance, and there is a related complaint that the Monad instance
must define But both of these problems can be worked around. If I have a Monad instance, it seems to work just fine if I say:
Where this code is completely canned, the same for every Monad. And if I know
I suppose these might faul foul of whatever problem is being described in the documents I linked above. But I'll either find out, or I won't, and either way is a good outcome. [ Addendum: Vaibhav Sagar points out that my definition of [Other articles in category /prog/haskell] permanent link While I was writing up last week's long article about Traversable, I wrote this stuff about Applicative also. It's part of the story but I wasn't sure how to work it into the other narrative, so I took it out and left a remark that “maybe I'll publish a writeup of that later”. This is a disorganized collection of loosely-related paragraphs on that topic. It concerns my attempts to create various class instance definitions for the following type:
which notionally represents a type of very simple expression tree over values of type a. I need some function for making
which builds trees like these:
Now I wanted to To define an Applicative instance for Well, I can kinda make sense of it. If I apply one function to a
tree of inputs, that's straightforward, it's just
and since this is enough to define a Monad instance for
but I couldn't find out what it was. This gets back to my original
complaint: Haskell now wants every Monad instance to be an instance
of Applicative, but if I give it the (I later realized that building
So again, why can't GHC infer
This is not a rhetorical question.) (Side note: it seems like there ought to be a nice short abbreviation
of the
but that is not any help unless we can simplify the expression with
the usual tricks, such as combinatory logic and η-conversion. I was
not able to do this, and the automatic pointfree
converter produced
Anyway I did eventually figure out my
And when it's bigger than that we can break it up recursively:
Once this is written it seemed a little embarrassing that it took me so long to figure out what it meant but this kind of thing always seems easier from the far side of the fence. It's hard to understand until you understand it. Actually that wasn't quite the
I can map the whole tree of functions over each single leaf on the right, like this:
or I can map each function over the whole tree on the right, like this:
The code I showed earlier does the second of those. You can see it from
the
or
Now there's a simple answer to this which occurs to me now that I
didn't think of before, but I'm going to proceed with how I planned to
do it before, with
I need to do the main recursion on the values argument instead of on the functions argument:
(This is an interesting example: usually the base case is trivial and the recursive clause is harder to write, but this time it's the base case that's not perfectly straightforward.) Anyway, this worked, but there was an easier solution at hand. The difference between the first version and the second is exactly the same as the difference between
and
Digging deeper into why this worked this way was interesting, but it's bed time, so I'm going to cut the scroll here. [Other articles in category /prog/haskell] permanent link Sat, 20 Oct 2018
I struggle to understand Traversable
Haskell evolved a lot since the last time I seriously wrote any
Haskell code, so much so that all my old programs broke. My Monad
instances don't compile any more because I'm no longer allowed to
have a monad which isn't also an instance of Applicative. Last time I used
Haskell, Applicative wasn't even a thing. I had read the McBride and
Paterson paper that introduced applicative functors, but that was
years ago, and I didn't remember any of the details. (In fact, while
writing this article, I realized that the paper I read was a preprint,
and I probably read it before it was published, in 2008.) So to
resuscitate my old code I had to implement a bunch of Anyway I got that more or less under control (maybe I'll publish a
writeup of that later) and moved on to Traversable which, I hadn't realized
before, was also introduced in that same paper. (In the
prepublication version, Traversable was been given the unmemorable name
The traversable functor itself here is The first thing to try here is to make it less abstract. I was thinking about Traversable this time because I thought I might want it for a certain type of tree structure I was working with. So I defined an even simpler tree structure:
Defining a bunch of other cases wouldn't add anything to my understanding, and it would make it take longer to try stuff, so I really want to use the simplest possible example here. And this is it: one base case, one recursive case. Then I tried to make this type it into a Traversable instance. First we need it to be a Functor, which is totally straightforward:
Then we need it to be a Foldable, which means it needs to provide a
version of
but these days the list functor in the third place has been generalized:
The idea is that
and
The canonical examples for lists are:
(add up the elements, starting with zero) and
(ignore the elements, adding 1 to the total each time, starting with
zero). Also Anyway for
The I didn't write this off the top of my head, I got it by following the types, like this:
It turns out it is easier and more straightforward to write
and here I was stumped. What is this supposed to actually do?
For our
Okay, a function I scratched my head and read a bunch of different explanations and none of them helped. All the descriptions I found were in either prose or mathematics and I still couldn't figure out what it was for. Finally I just wrote a bunch of examples and at last the light came on. I'm going to show you the examples and maybe the light will come on for you too. We need two Traversable functors to use as examples. We don't have a Traversable
implementation for
Okay, I think I could have guessed that just from the types. And
going the other way is not very interesting because the output, being
a
If the !!x!! is even then the result is just half of !!x!!, and otherwise the division by 2 “fails” and the result is nothing. Now:
It took me a few examples to figure out what was going on here: When
all the list elements are even, the result is That pretty much exhausts what can be done with lists and maybes. Now
I have two choices about where to go next: I could try making both
functors
In the
which not only type checks but looks like it could even be correct.
So now I have a motto for what Which, now that I have said it myself, I realize it is exactly what
everyone else was trying to tell me all along: normal function
application takes an Okay, I can listen all day to an explanation of what an electric drill does, but until I hold it in my hand and drill some holes I don't really understand. Encouraged, I tried the hard clause:
and this time I had a roadmap to follow:
The
Clearly
let's try that:
This looks plausible. It compiles, so it must be doing something.
Partial victory! But what is it doing? We can run it and see, which
was the whole point of an exercise: work up a Traversable instance for Here are some example trees:
(I also tried First we'll try
but So try:
which yields:
It keeps the existing structure, and applies But where does that spoilage behavior come from exactly? It comes
from the overloaded behavior of
Once we get a I think that's one way to think of Now let's try the next-simplest Applicative, which is
Now
This is where the light finally went on for me. Instead of thinking
of lists as lists, I should be thinking of them as choices. A list
like The Traversing Now I finally understand how the
I asked “how the hell do I turn a tree of lists into a single list
of Okay! And indeed
and ending
That was traversing a list function over a What other functors do I know? One easy one is the functor that takes
type
Huh, I don't know what I was expecting but I think that wouldn't have
been it. But I figured out what was going on: the built-in Applicative
instance for the
But if we wanted it to multiply instead we could use the potato label,
which is called
There are three leaves, so we multiply three sevens and get 343. Or we could do the same sort of thing on a
Here instead of multiplying together a bunch of sevens we multiply together the leaf values themselves. The McBride and Paterson paper spends a couple of pages talking about
traversals over monoids, and when I saw the example above it started
to make more sense to me. And their
There's another useful way to traverse a list function. Instead of taking each choice at each leaf we make a single choice ahead of time about whether we'll take the first, second, or third menu item, and then we take that item every time:
There's a built-in instance for
Okay, I think I got it. Now I just have to drill some more holes. [Other articles in category /prog/haskell] permanent link Tue, 16 Oct 2018
I redesign the LA Times’ Hurricane Maria chart
This could have been a great chart, but I think it has a big problem: It appears that the death toll started increasing in early August, even though the hurricane didn't hit until 20 September. According to this chart, the hurricane was shortly followed by a drastic decrease in the death rate. What's actually going on is that the August value is a total for all of August and is typically low, the September value is a total for all of September and is atypically high, and the chart designer has drawn a straight line between the August and September values, implying a linear increase over the course of August. The data for August is at the mark “A” on the chart, which seems reasonable, except that one has to understand that “A” as marking the end of August instead of the beginning, which is the opposite of the usual convention. I think a bar chart would have been a better choice here. The lines imply continuous streams of data, but the reality is that each line represents only twelve data points. Maybe something like this instead? I'm not sure the historical range bars are really adding much. If I were designing this from scratch I think I might replace the blue bars with brackets (although maybe the LA Times knows that their readership finds those confusing?). Or maybe plot the difference between the 2017 data and ths historical average. But I think you get the point. [Other articles in category /IT] permanent link Mon, 15 Oct 2018
'The' reader monad does not exist
Reading over my recent article complaining about the environment functor I realized there's yet another terminology problem that makes the discussion unnecessarily confusing. “The” environment functor isn't unique. There is a family of environment functors, one for each possible environment type e. If g is the environment functor at type e, a value of type g t is a function e → t. But e could be anything and if g and h are environment functors at two different types e and e’ they are of course different functors. This is even obvious from the definition:
The functor isn't We should speak of
I should have said:
And instead of:
I should have said:
or
although I'm not sure I like the way the prepositions are proliferating there. The same issue affects ⸢the⸣ reader monad, ⸢the⸣ state monad, and many others. I'm beginning to find remarkable how much basic terminology Haskell is missing or gets wrong. Mathematicians have a very keen appreciation of the importance of specific and precise terminology, and you'd think this would have filtered into the Haskell world. People are forever complaining that Haskell uses unfamiliar terms like “functor”, and the community's response is (properly, I think) that these terms are pre-existing and there is no point to inventing a new term that will be just as unfamiliar, or, worse, lure people into thinking that the know what it means when they don't. You don't want to call a functor a “container”, says the argument, because many functors (environment functors for example) are nothing at all like containers. I think this is wise. But having planted their flag on that hill, the Haskell folks don't
then use their own terminology correctly. I complained years
ago that the term
“monad” was used interchangeably for four subtly different concepts,
and here we actually have a fifth. I pointed out that in the case of
[Other articles in category /prog/haskell] permanent link Fri, 12 Oct 2018
The more I think about “parcel” the happier I am with it. It strongly
suggests container types, of course, so that a
I coined “parcel” thinking that one would want different terminology
for values of type [Other articles in category /prog/haskell] permanent link Thu, 11 Oct 2018
I hate the environment functor
Here we have the well-known
It takes a single function and a (collection of input values / decorated input value / something something input value) and produces a (collection of output values / decorated output value / something something output value). Yow, that's not going to work. Is there any good terminology for a
value of type Starting over then. Here we have the well-known
It takes a single function, and an Here is a sort of reversed version of
It takes a parcel of functions, and a single input and produces a
parcel of outputs, by applying each function in the parcel
independently to the single
So far so good. Now I ask you to predict the type of
Certainly it should start out with
because the
The
and lifts it to a new function that operates in the
Here it has taken
and lifted it to a new function that operates in the
This is complicated but straightforward. Okay, that was
and when I saw this I said “What. Where did Then I paused and for a while and said “… I bet it's that goddamn environment thing again.” Yep, that's what it was. It's the environment functor, always turning up where I don't want it and least expect it, like that one guy we all went to college with. The environment functor, by the way, is yet another one of those things that Haskell ought to have a standard name for, but doesn't. The phrase “the reader monad” is fairly common, but here I only want the functor part of the monad. And people variously say “reader monad”, “environment monad”, and “evaluation monad” to mean the same thing. In this article, it will be the environment functor. Here's what happened. Here are
The first argument to When operating in the environment functor,
or shorter and more mysteriously
which follows by η-reduction, something Haskell enthusiasts never seem to get enough of. In In the application
so it can be understood as a parcel in the environment functor, where
the environment We wanted
and since Haskell has decided that
To apply this to
Where did The funny thing about the type of
and indeed, by some theorem or other, because the types are identical,
the functions themselves must be identical also! (There are some side
conditions, all of which hold here.) The two functions
Or, cleaning up some superfluous parentheses and inserting some new ones:
And putting !!c = p\to q!!:
Honestly, I would have preferred a type error: “Hey, dummy,
I mean, seriously, suppose you wrote [ Addendum 20181111: Apparently, everyone else hates it too. ] [Other articles in category /prog/haskell] permanent link Wed, 10 Oct 2018Minecraft makes maps in-game, and until now I would hold up the map in the game, take a screenshot, print it out, and annotate the printout. Now I can do better. I have a utility that takes multiple the map files direcly from the Minecraft data directory and joins them together into a single PNG image that I can then do whatever with. Here's a sample, made by automatically processing the 124(!) maps that exist in my current Minecraft world. Notice how different part of the result are at different resolutions. That is because Minecraft maps are in five different resolutions, from !!2^{14}!! to !!2^{22}!! square meters in area, and these have been stitched together properly. My current base of operations is a little comma-shaped thingy about halfway down in the middle of the ocean, and on my largest ocean map it is completely invisible. But here it has been interpolated into the correct tiny scrap of that big blue map. Bonus: If your in-game map is lost or destroyed, the data file still hangs around, and you can recover the map from it. Source code is on Github. It needs some work:
./dumpmap $(./sortbyscale map_*) | pnmtopng > result.png Patches welcome! [Other articles in category /games] permanent link Mon, 08 Oct 2018
Notes on using git-replace to get rid of giant objects
A couple of years ago someone accidentally committed a 350 megabyte
file to our Git repository. Now it's baked in. I wanted to get rid
of it. I thought that I might be able to work out a partial but
lightweight solution using Summary: It didn't work. DetailsIn 2016 a programmer commited a 350 megabyte file to my employer's repo, then in the following commit they removed it again. Of course it's still in there, because someone might check out the one commit where it existed. Everyone who clones the repo gets a copy of the big file. Every copy of the repo takes up an extra 350 megabytes on disk. The usual way to fix this is onerous:
I thought I'd tinker around with The
I can turn this small file into an object with
This creates
So far this doesn't help much. The checkout is smaller, but nobody was likely to have that commit checked out anyway. The large file is still in the repository, and clones and transfers still clone and transfer it. The first thing I tried was a wan hope: will Now comes the hacking part: I am going to destroy the actual object. Say for example, what if:
Now the repository is smaller! And maybe Git won't notice, as long as
I do not use Indeed, much normal Git usage doesn't notice. For example, I can make
new commits with no trouble, and of course any other operation that
doesn't go back as far as 2016 doesn't notice the change. And
But some things become wonky. You get an error message when you clone
the repo because an object is missing. The replacement refs are local
to the repo, and don't get cloned, so clone doesn't know to use the
replacement object anyway. In the clone, you can use No. Unfortunately, there is a show-stopper:
and it doesn't create the pack files. It dies, and leaves behind a
I think I've reached the end of this road. Oh well, it was worth a look. [ Addendum 20181009: A lot of people have unfortunately missed the point of this article, and have suggested that I use BFG or reposurgeon. I have a small problem and a large problem. The small problem is how to remove some files from the repository. This is straightforward, and the tools mentioned will help with it. But because of the way Git works, the result is effectively a new repository. The tools will not help with the much larger problem I would have then: How to get 350 developers to migrate to the new repository at the same time. The approach I investigated in this article was an attempt to work around this second, much larger problem. ] [Other articles in category /prog] permanent link Sun, 07 Oct 2018Last week we visited Toph's school and I saw a big map of Pennsylvania. I was struck by something I had never noticed before. Here's a detail of central Pennsylvania, an area roughly 100 miles (160 km) square: As you can see, a great many lines on this map start in the lower left, proceed in roughly parallel tracks north-by-northeast, then bend to the right, ending in the upper right corner. Many of the lines represent roads, but some represent county borders, and some represent natural features such as forests and rivers. When something like this happens, it is almost always for some topographic reason. For example, here's a map of two adjacent communities in Los Angeles: You can see just from the pattern of the streets that these two places must have different topography. The streets in Santa Monica are a nice rectangular grid. The streets in Pacific Palisades are in groups of concentric squiggles. This is because Pacific Palisades is hilly, and the roads go in level curves around the hills, whereas Santa Monica is as flat as a squid. I had never noticed before that all the lines in central Pennsylvania go in the same direction. From looking at the map, one might guess that central Pennsylvania was folded into many long parallel wrinkles, and that the roads, forests, and rivers mostly lay in the valleys between the wrinkles. This is indeed the case. This part of Pennsylvania is part of the Ridge-and-Valley Appalachians, and the pattern of ridges and valleys extends far beyond Pennsylvania. The wrinkling occurred over a long period, ending around 260 million years ago, in an event called the Alleghanian orogeny. North America and Africa (then part of the supercontinents Euramerica and Gondwana, respectively) collided with one another, and that whole part of North America crumpled up like a sheet of aluminum foil. People in Harrisburg and State College are living in the crumples. [Other articles in category /misc] permanent link Mon, 24 Sep 2018A long time ago, I wrote up a blog article about how to derive the linear regression formulas fro first principles. Then I decided it was not of general interest, so I didn't publish it. (Sometime later I posted it to math stack exchange, so the effort wasn't wasted.) The basic idea is, you have some points !!(x_i, y_i)!!, and you assume that they can be approximated by a line !!y=mx+b!!. You let the error be a function of !!m!! and !!b!!: $$\varepsilon(m, b) = \sum (mx_i + b - y_i)^2$$ and you use basic calculus to find !!m!! and !!b!! for which !!\varepsilon!! is minimal. Bing bang boom. I knew this for a long time but it didn't occur to me until a few months ago that you could use basically the same technique to fit any other sort of curve. For example, suppose you think your data is not a line but a parabola of the type !!y=ax^2+bx+c!!. Then let the error be a function of !!a, b, !! and !!c!!: $$\varepsilon(a,b,c) = \sum (ax_i^2 + bx_i + c - y_i)^2$$ and again minimize !!\varepsilon!!. You can even get a closed form as you can with ordinary linear regression. I especially wanted to try fitting hyperbolas to data that I expected to have a Zipfian distribution. For example, take the hundred most popular names for girl babies in Illinois in 2017. Is there a simple formula which, given an ordinal number like 27, tells us approximately how many girls were given the 27th most popular name that year? (“Scarlett”? Seriously?) I first tried fitting a hyperbola of the form !!y = c + \frac ax!!. We could, of course, take !!y_i' = \frac 1{y_i}!! and then try to fit a line to the points !!\langle x_i, y_i'\rangle!! instead. But this will distort the measurement of the error. It will tolerate gross errors in the points with large !!y!!-coordinates, and it will be extremely intolerant of errors in points close to the !!x!!-axis. This may not be what we want, and it wasn't what I wanted. So I went ahead and figured out the Zipfian regression formulas: $$ \begin{align} a & = \frac{HY-NQ}D \\ c & = \frac{HQ-JY}D \end{align} $$ Where: $$\begin{align} H & = \sum x_i^{-1} \\ J & = \sum x_i^{-2} \\ N & = \sum 1\\ Q & = \sum y_ix_i^{-1} \\ Y & = \sum y_i \\ D & = H^2 - NJ \end{align} $$ When I tried to fit this to some known hyperbolic data, it worked just fine. For example, given the four points !!\langle1, 1\rangle, \langle2, 0.5\rangle, \langle3, 0.333\rangle, \langle4, 0.25\rangle!!, it produces the hyperbola $$y = \frac{1.00018461538462}{x} - 0.000179487179486797.$$ This is close enough to !!y=\frac1x!! to confirm that the formulas work; the slight error in the coefficients is because we used !!\bigl\langle3, \frac{333}{1000}\bigr\rangle!! rather than !!\bigl\langle3, \frac13\bigr\rangle!!. Unfortunately these formulas don't work for the Illinois baby data. Or rather, the hyperbola fits very badly. The regression produces !!y = \frac{892.765272442475}{x} + 182.128894972025:!! I think maybe I need to be using some hyperbola with more parameters, maybe something like !!y = \frac a{x-b} + c!!. In the meantime, here's a trivial script for fitting !!y = \frac ax + c!! hyperbolas to your data:
[ Addendum 20180925: Shreevatsa R. asked a related question on StackOverflow and summarized the answers. The problem is more complex than it might first appear. Check it out. ] [Other articles in category /math] permanent link Fri, 14 Sep 2018
How not to remember the prime numbers under 1,000
A while back I said I wanted to memorize all the prime numbers under 1,000, because I am tired of getting some number like 851 or 857, or even 307, and then not knowing whether it is prime. The straightforward way to deal with this is: just memorize the list. There are only 168 of them, and I have the first 25 or so memorized anyway. But I had a different idea also. Say that a set of numbers from !!10n!! to !!10n+9!! is a “decade”. Each decade contains at most 4 primes, so 4 bits are enough to describe the primes in a single decade. Assign a consonant to each of the 16 possible patterns, say “b” when none of the four numbers is a prime, “d” when only !!10n+1!! is prime, “f” when only !!10+3!! is, and so on. Now memorizing the primes in the 90 decades is reduced to memorizing 90 consonants. Inserting vowels wherever convenient, we have now turned the problem into one of memorizing around 45 words. A word like “potato” would encode the constellation of primes in three consecutive decades. 45 words is only a few sentences, so perhaps we could reduce the list of primes to a short and easily-remembered paragraph. If so, memorizing a few sentences should be much easier than memorizing the original list of primes. The method has several clear drawbacks. We would have to memorize the mapping from consonants to bit patterns, but this is short and maybe not too difficult. More significant is that if we're trying to decide if, say, 637 is prime, we have to remember which consonant in which word represents the 63rd decade. This can be fixed, maybe, by selecting words and sentences of standard length. Say there are three sentences and each contains 30 consonants. Maybe we can arrange that words always appear in patterns, say four words with 1 or 2 consonants each that together total 7 consonants, followed by a single long word with three consonants. Then each sentence can contain three of these five-word groups and it will be relatively easy to locate the 23rd consonant in a sentence: it is early in the third group. Katara and I tried this, with not much success. But I'm not ready to give up on the idea quite yet. A problem we encountered early on is that we remember consonants not be how words are spelled but by how they sound. So we don't want a word like “hammer” to represent the consonant pattern h-m-m but rather just h-m. Another problem is that some constellations of primes are much more common than others. We initially assigned consonants to constellations in order. This assigned letter “b” to the decades that contain no primes. But this is the most common situation, so the letter “b” tended to predominate in the words we needed for our mnemonic. We need to be careful to assign the most common constellations to the best letters. Some consonants in English like to appear in clusters, and it's not trivial to match these up with the common constellations. The mapping from prime constellations to consonants must be carefully chosen to work with English. We initially assigned “s” to the constellation “☆•☆☆” (where !!10n+1, 10n+7,!! and !!10n+9!! are prime but !!10n+3!! is not) and “t” to the constellation “☆☆••” (where !!10n+1!! and !!10n+3!! are prime but !!10n+7!! and !!10n+9!! are not) but these constellations cannot appear consecutively, since at least one of !!10n+7, 10n+9, 10n+11!! is composite. So any word with “s” and “t” with no intervening consonants was out of play. This eliminated a significant fraction of the entire dictionary! I still think it could be made to work, maybe. If you're interested
in playing around with this, the programs I wrote are available on
Github. The mapping
from decade constellations to consonant clusters is in
[Other articles in category /math] permanent link Wed, 12 Sep 2018
Perils of hacking on mature software
Yesterday I wrote up an interesting bug in People complain that the trouble of working on mature software like Git is to understand the way the code is structured, its conventions, the accumulated layers of cruft, and where everything is. I think this is a relatively minor difficulty. The hard part is no so much doing what you want, as knowing what you want to do. My original idea for the fix was this: I can give I excavated the code and found where the change needed to go. It's
not actually in But then I ran into a roadblock. Diff already has an undocumented
flag called (See this commit for further details.) The roadblock is: how does If they should be controlled in unison, should
If we add new options, how do they interact with the existing and
already non-orthogonal flags that do something like this? They
include at least the following options of
Only Now suppose you would like to configure a default for this option in
your The thing to do at this point is to come up with some
reasonable-seeming proposal and send it to Jeff King, who created the
undocumented Doing any particular thing would not be too hard. The hard part is deciding what particular thing to do. [Other articles in category /prog] permanent link
Language fluency in speech and print
Long ago I worked among the graduate students at the University of Pennsylvania department of Computer and Information Sciences. Among other things, I did system and software support for them, and being about the same age and with many common interests, I socialized with them also. There was one Chinese-Malaysian graduate student who I thought of as having poor English. But one day, reading one of his emailed support requests, I was struck by how clear and well-composed it was. I suddenly realized I had been wrong. His English was excellent. It was his pronunciation that was not so good. When speaking to him in person, this was all I had perceived. In email, his accent vanished and he spoke English like a well-educated native. When I next met him in person I paid more careful attention and I realized that, indeed, I had not seen past the surface: he spoke the way he wrote, but his accent had blinded me to his excellent grammar and diction. Once I picked up on this, I started to notice better. There were many examples of the same phenomenon, and also the opposite phenomenon, where someone spoke poorly but I hadn't noticed because their pronunciation was good. But then they would send email and the veil would be lifted. This was even true of native speakers, who can get away with all sorts of mistakes because their pronunciation is so perfect. (I don't mean perfect in the sense of pronouncing things the way the book says you should; I mean in the sense of pronouncing things the way a native speaker does.) I didn't notice this unless I was making an effort to look for it. I'm not sure I have anything else to say about this, except that it seems to me that when learning a foreign language, one ought to consider whether one will be using it primarily for speech or primarily for writing, and optimize one's study time accordingly. For speech, concentrate on good pronunciation; for writing, focus on grammar and diction. Hmm, put that way it seems obvious. Also, the sky is sometimes blue. [Other articles in category /lang] permanent link Mon, 10 Sep 2018
Why hooks and forks in the J language?
And I think I now recall that the name of the language itself, J, is intended to showcase the hook, so he must have thought it was pretty wonderful. A helpful Hacker News
comment pointed me to
the explanation. Here Iverson explains why the “hook”
feature: it is actually the
S combinator in disguise. Recall that
$${\bf S} x y z = x z (y z).$$ This is exactly what J's hook computes
when you write As McBride and Paterson point
out, S
is also the same as the [Other articles in category /prog] permanent link
git log --follow enthusiastically tracks empty files
This bug I just found in I knew I'd written a draft of a blog article about the Watchmen movie, and I went to find out how long it had been sitting around:
The log stopped there, and the commit message says clearly that the
article was moved from elsewhere, so I used
Okay, it was moved, with slight modifications, from
Okay, the previous month I added some text to it. Then I skipped to the bottom to see when it first appeared, and the bottom was completely weird, mentioning a series of completely unrelated articles:
(The complete output is available for your perusal.) The log is showing unrelated files being moved to totally unrelated
places. And also, the log messages do not seem to match up. “First
chunk of linear regression article” should be on some commit that adds
text to My first thought was: when I imported my blog from CVS to Git, many years ago, I made a series of mistakes, and mismatched the log messages to the commits, or worse, and I might have to do it over again. Despair! But no, it turns out that
But if I do
This is easy to understand. The commit message was correct: the
I believe what happened here is this: In 2012 I “finally started article”. But I didn't create the file at that time. Rather, I had created the file in 2009 with the intention of putting something into it later:
This commit does appear in the
It appears that Git, having detected that At this point it has gone completely off the rails, because it is now
following the unrelated empty file Commit ff398402 created the empty file There is a As far as I can tell there is no option to set an absolute threshhold
on when two files are considered the same by The part I don't fully understand is how The problem appears in Git 1.7.11, 2.7.4, and 2.13.0. [ Addendum 20180912: A followup about my work on a fix for this. ] [Other articles in category /prog] permanent link Sun, 09 Sep 2018I very recently suggested a mathematical operation that does this: $$\begin{align} \left((\sqrt\bullet) \cdot x + \left(\frac1\bullet\right) \cdot 1 \right) ⊛ (9x+4) & = \sqrt9 x^2 + \sqrt4 x + \frac19 x + \frac14 \\ & = 3x^2 + \frac{19}{9} x + \frac 14 \end{align}$$ Here the left-hand argument is like a polynomial, except that the coefficients are functions. The right-hand argument is an ordinary polynomial. It occurs to me that the APL progamming lanaguage (invented around 1966) actually has something almost like this, in its generalized matrix product. In APL, if $$c_{ij} = a_{i1} \cdot b_{1j} + The APL With this feature, the ⊛ operator I proposed above would be something
like APL does have a $$c_{11} = a_{11} \cdot b_{11} + and similarly if !!a!! is !!n×1!! and !!b!! is !!1×m!! then !!a +.× b!! is the
outer product, the !!n×m!! matrix whose !!c_{ij} = a_i × b_j!!. But I
think APL doesn't distinguish between a !!1×n!! matrix and a vector,
though, and always considers them to be vectors, so that in such cases
!!a +.× b!! always gets you the dot product, if !!a!! and !!b!! are the same
length, and an error otherwise. If you want the outer product of two
vectors you use I applied for an APL job once; I went to a job fair (late 1980s maybe?) and some Delaware bank was looking for APL programmers to help maintain their legacy APL software. I was quite excited at the idea of programming APL professionally, but I had no professional APL experience so they passed me over. I think they made a mistake, because there are not that many people with professional APL experience anyway, and how many twenty-year-olds are there who know APL and come knocking on your door looking for a job? But whatever, it's probably better that I didn't take that route. The I was pleased to find out that Iverson had designed a successor language, J, and then quickly disappointed when I saw how little it added. For example, it has an implicit “hook” construction, which is a special case in the language for handling one special case of function composition. In Haskell it would be:
but in J the [ Addendum 20180910: The explanation. ] Meanwhile the awful APL notation has gotten much more awful in J, and
you get little in return. You even lose all the fun of the little
squiggles. Haskell is a much better J than J ever was. Haskell's
notation can be pretty awful too ( I thought I'd see about implementing APL's For a regular matrix product, !!C = AB!! means that !!c_{ij}!! is the dot product of the !!i!!th row of !!A!! and the !!j!!th column of !!B!!, so I implemented a dot product function:
OK, that was straightforward. The rows of !!A!! are right there, but we also need the columns from !!B!!, so here's a function to get those:
Also straightforward. After that I toiled for a very long time over the matrix product itself. My first idea was to turn !!A!! into a list of functions, each of which would dot-product one of the rows of !!A!! by a given vector. Then I would map each of these functions over the columns of !!B!!. Turning !!A!! into a list of functions was easy:
and getting the columns of !!B!! I had already done:
and now I just need to apply each row of functions in the first part to each column in the second part and collect the results:
I don't know why this turned out to be so damn hard. This is the sort of thing that ought to be really, really easy in Haskell. But I had many difficulties. First I wasted a bunch of time trying to get
whereas
and I needed to keep that extra structure. I tried all sorts of
tinkering with Another part of the problem was I didn't know any primitive for “map a list of functions over a single argument”. Although it's not hard to write, I had some trouble thinking about it after I wrote it:
Then the “map each function over each list of arguments” is
and this almost works, except it produces the columns of the results
instead of the rows. There is an easy fix and a better fix. The easy
fix is to just transpose the final result. I never did find the
better fix. I thought I'd be able to replace Anyway this did work:
but that So then I went down a rabbit hole and wrote nine more versions of
I finally settled on
The result was okay, but it took me so long to get there. Now I have
just use:
Except uh oh, that I tinkered a bit with requiring a Monoid instance for the matrix
entries, which seemed interesting at least, but to do that I would
need to switch monoids in the middle of the computation and I didn't
want to think about how to do that. So instead I wrote a version of
This fails on empty lists, which is just fine, since I wasn't planning on multiplying any empty matrices. Then I have the final answer:
It's nice and short, but on the other hand it has that mysterious As for the shortness, let's see what it looks like in a more conventional language:
Wow, that was amazingly easy.
Okay, that was kind of a mess. The I think the standard Python answer to this is that you don't need
I don't know how I feel about that argument in general but in this case the result was lovely. I have no complaints. While I was writing the Python program I got a weird bug that turned
out to be related to mutability: I had initialized
But this makes the rows of A lot of the mess in the code is because Python is so obstinate about extending lists when you need them extended, you have to say pretty please every time. Maybe I can get rid of that by using more list comprehensions?
Python's list comprehensions usually make me long for Haskell's, which are so much nicer, but this time they were fine. Python totally wins here. No wait, that's not fair: maybe I should have been using list comprehensions in Haskell also?
Yeah, okay. All that
Well, lesson learned. I really wish I could write Haskell faster. In the mid-1990s I wrote thousands of lines of SML code and despite (or perhaps because of) SML's limitations I was usually able to get my programs to do what I wanted. But when I try to write programs in Haskell it takes me a really long time to get anywhere. Apropos of nothing, today is the 77th birthday of Dennis M. Ritchie. [ Addendum: It took me until now to realize that, after all that, the operation I wanted for polynomials is not matrix multiplication. Not at all! It is actually a convolution: $$ c_k = \sum_{i+j=k} a_ib_j $$ or, for my weird functional version, replace the multiplication !!a_ib_j!! with function composition !!a_i ∘ b_j!!. I may implement this later, for practice. And it's also tempting to try to do it in APL, even though that would most likely be a terrible waste of time… ] [ Addendum 20180909: Vaibhav Sagar points out that my [Other articles in category /prog] permanent link Sat, 08 Sep 2018
Why I never finish my Haskell programs (part 2 of ∞)
Here's something else that often goes wrong when I am writing a Haskell program. It's related to the problem in the previous article but not the same. Let's say I'm building a module for managing polynomials. Say
Now clearly this is going to be a functor, so I define the Functor instance, which is totally straightforward:
Then I ask myself if it is also going to be an Applicative.
Certainly the
But what about
The first argument there is a polynomial whose coefficients are functions. This is not something we normally deal with. That ought to be the end of the matter. But instead I pursue it just a little farther. Suppose we did have such an object. What would it mean to apply a functional polynomial and an ordinary polynomial? Do we apply the functions on the left to the coefficients on the right and then collect like terms? Say for example $$\begin{align} \left((\sqrt\bullet) \cdot x + \left(\frac1\bullet\right) \cdot 1 \right) ⊛ (9x+4) & = \sqrt9 x^2 + \sqrt4 x + \frac19 x + \frac14 \\ & = 3x^2 + \frac{19}{9} x + \frac 14 \end{align}$$ Well, this is kinda interesting. And it would mean that the
Then the ⊛ can be understood to be just like polynomial
multiplication, except that coefficients are combined with function
composition instead of with multiplication. The operation is
associative, as one would hope and expect, and even though the ⊛
operation is not commutative, it has a two-sided identity element,
which is This is different from the failure mode of the previous article because in that example I was going down a Haskell rabbit hole of more and more unnecessary programming. This time the programming is all trivial. Instead, I've discovered a new kind of mathematical operation and I abandon the programming entirely and go off chasing a mathematical wild goose. [ Addendum 20181109: Another one of these. ] [Other articles in category /prog/haskell] permanent link Mon, 03 Sep 2018
Why I never finish my Haskell programs (part 1 of ∞)
Whenever I try to program in Haskell, the same thing always goes wrong. Here is an example. I am writing a module to operate on polynomials. The polynomial !!x^3 - 3x + 1!! is represented as
[ Addendum 20180904: This is not an error. The !!x^3!! term is last, not first. Much easier that way. Fun fact: two separate people on Reddit both commented that I was a dummy for not doing it the easy way, which is the way I did do it. Fuckin' Reddit, man. ] I want to add two polynomials. To do this I just add the corresponding coefficients, so it's just
Except no, that's wrong, because it stops too soon. When the lists
are different lengths,
and I can write this off the top of my head. But do I? No, this is where things go off the rails. “I ought to be
able to generalize this,” I say. “I can define a function like
as long as there is a suitable Monoid instance for the I could write So do I write Then I open a new file and start writing
And I go father and farther down the rabbit hole and I never come back
to what I was actually working on. Maybe the next step in this
descent into madness is that I start thinking about how to perform
unification of arbitrary algebraic data structures, I abandon Actually when I try to program in Haskell there a lot of things that go wrong and this is only one of them, but it seems like this one might be more amenable to a quick fix than some of the other things. [ Addendum 20180904: A lobste.rs
user
points out that I don't need Monoid, but only Semigroup, since
I don't need [ Addendum 20181109: More articles in this series: [2] [3] ] [Other articles in category /prog/haskell] permanent link Wed, 29 Aug 2018On long road trips I spend a lot of time listening to music and even more time talking to myself. My recent road trip was longer than usual and I eventually grew tired of these amusements. I got the happy idea that I might listen to an audiobook, something I've never done before. Usually the thought of sitting and listening to someone droning out a book for 14 hours makes me want to dig my heart out with a spoon (“You say a word. Then I think for a long time. Then you say another word.”) but I had a long drive and I was not going anywhere anyway, so thought it might be a good way to pass the time. The first thing I thought to try was Ann Leckie's Ancillary Justice, which everyone says is excellent, and which I had wanted to read. I was delighted to learn that I could listen to the first hour or so before paying anything, so I downloaded the sample. It was intolerable. The voice actor they chose (Celeste Ciulla) was hilariously inappropriate, so much so that, had I not gotten the book from the most unimpeachable source, I would have suspected I was being pranked. Ancillary Justice is a hard-boiled military story in which the protagonist is some sort of world-weary slave or robot, or at least so I gather from the first half of the first chapter. Everything that appears in the first chapter is terrible: the people, the situation, the weather. It opens with these words:
But Ms. Ciulla's voice… there's nothing wrong with it, maybe — but for some other book. I can imagine listening to her reading What Katy Did or Eight Cousins or some other 19th-century girl story. I found myself mockingly repeating Ciulla's pronunciation. And about twelve minutes in I gave up and turned it off. Here's a sample of that point. It ends with: Is Ciulla even capable of growling? Unclear. I figured that the book was probably good, and I was afraid Ciulla would ruin it for me permanently. Spotify had a recording of Sir Christopher Lee reading Dr. Jekyll and Mr. Hyde, so I listened to that instead. I think I could do a better job reading than most of the audiobook actors I sampled, and I might give it a try later. I think I might start with The 13 Clocks. Or maybe something by C.A. Stephens, which is in the public domain. [Other articles in category /book] permanent link Tue, 28 Aug 2018
[Other articles in category /misc] permanent link
How quickly did dentists start trying to use X-rays?
I had dental x-rays today and I wondered how much time elapsed between the discovery of x-rays and their use by dentists. About two weeks, it turns out. Roentgen's original publication was in late 1895. Dr. Otto Walkhoff made the first x-ray picture of teeth 14 days later. The exposure took 25 minutes. Despite the long exposure time, dentists had already begun using x-rays in their practices in the next two years. Dr. William J. Morton presented the new technology to the New York Odontological Society in April 1896, and his dental radiography, depicting a molar with an artificial crown clearly visible, was published in a dental journal later that year. Morton's subject had been a dried skull. The first dental x-ray of a living human in the United States was made by Charles Edmund Kells in April or May of 1896. In July at the annual meeting of the Southern Dental Association he presented a dental clinic in which he demonstrated the use of his x-ray equipment on live patients. The practice seems to have rapidly become routine. The following story about Morton is not dental-related but I didn't want to leave it out:
(Daniel S. Goldberg, “The Early Days of the X-Ray”) The first dental x-ray machine was manufactured in 1923 by Victor X-ray Company, which later became part of General Electric. In preparing this article I was fortunate to have access to B. Martinez, In a New Light: Early X-Ray Technology in Dentistry, 1890–1955, Arizona State University, 2013. [Other articles in category /tech] permanent link Mon, 27 Aug 2018
Linear mappings of projective space
[ Epistemic status: uninformed musings; anything and everything in here might be wrong or ill-conceived. ] Suppose !!V!! is some vector space, and let !!V_n!! be the family of all !!n!!-dimensional subspaces of !!V!!. In particular !!V_1!! is the family of all one-dimensional subspaces of !!V!!. When !!V!! is euclidean space, !!V_1!! is the corresponding projective space. if !!L!! is a nonsingular linear mapping !!V\to V!!, then !!L!! induces a mapping !!L_n!! from !!V_n\to V_n!!. (It does not make sense to ask at this point if the induced mapping is linear because we do not have any obvious linear structure on the projective space. Or maybe there is but I have not heard of it.) The eigenspaces of !!V!! are precisely the fixed points of !!L_n!!. (Wrong! Any subspace generated by an !!n!!-set of eigenvectors is a fixed point of !!L_n!!. But such a subspace is not in general an eigenspace. (Note this includes the entire space as a special case.) The converse, however, does hold, since any eigenspace is generated by a subset of eigenvectors.) Now it is an interesting and useful fact that for typical mappings, say from !!\Bbb R\to\Bbb R!!, fixed points tend to be attractors or repellers. (For example, see this earlier article.) This is true of !!L_1!! also. One-dimensional eigenspaces whose eigenvalues are larger than !!1!! are attractors of !!L_1!!, and those whose eigenvalues are smaller than !!1!! are repellers, and this is one reason why the eigenspaces are important: if !!L!! represents the evolution of state space, then vectors in !!V!! will tend to evolve toward being eigenvectors. So consider, say, the projective plane !!\Bbb P^2!!, under the induced mapping of some linear operator on !!\Bbb R^3!!. There will be (typically) three special points in !!\Bbb P^2!! and other points will typically tend to gravitate towards one or more of these. Isn't this interesting? Is the three-dimensional situation more interesting than the two-dimensional one? What if a point attracts in one dimension and repels in the other? What can the orbits look like? Or consider the Grassmanian space !!Gr(2, \Bbb R^3)!! of all planes in !!\Bbb R^3!!. Does a linear operator on !!\Bbb R^3!! tend to drive points in !!Gr(2, \Bbb R^3)!! toward three fixed points? (In general, I suppose !!Gr(k, \Bbb R^n)!! will have !!n\choose k!! fixed points, some of which might attract and some repel.) Is there any geometric intuition for this? I have been wanting to think about Grassmanian spaces more for a long time now. [Other articles in category /math] permanent link Sat, 25 Aug 2018
A software archaeology screwup
This week I switched from using the Uggggggh. Why did I put up with this bullshit for so long? (I know, someone is going to write in and say the problem isn't in So I switched terminals, but this introduced a new problem: Reaching back into my memory, to a time even before there were tabs, I
recalled that there used to be a simple utility I could run on the
command line to set a terminal title. I did remember It's not hard. There's an escape sequence which, if received by the terminal, should cause it to retitle itself. If the terminal receives
it will change its title to It didn't take long to write the program:
The only important part here is the last line. I named the program
A few minutes later I was looking for the tab that had an SSH session
to the machine Plover already had a
Here it is:
Why didn't I find that before I wrote the other one? The old program is better-written too. Instead of wasting code to print a usage message if I didn't use it right, I had spent that code in having it do something useful instead. This is not the first time I have done something like this. Oh well, at least I can reacquire the better UI now that I know about it. [Other articles in category /oops] permanent link Fri, 24 Aug 2018
Frank Baum's uncomfortable relationship with Oz
L. Frank Baum's The Wonderful Wizard of Oz was a runaway success, and he wrote thirteen sequels. It's clear that he didn't want to write 13 more Oz books. He wanted to write fantasy adventure generally. And he did pretty well at this. His non-Oz books like Zixi of Ix and John Dough and the Cherub are considerably above average, but were not as commercially successful. In the sequel to The Wonderful Wizard, titled The Marvelous Land of Oz, he brought back the Scarecrow, the Tin Woodman, and Glinda, with the other characters being new. But the fans demanded Dorothy (who returned in every book thereafter) and the Wizard (from book 4 onward). Book 3, Ozma of Oz, is excellent, definitely my favorite. It introduces the malevolent Nome King, whom Baum seems to have loved, as he returned over and over. Ozma of Oz has a superb plot with building dramatic tension involving a frightening magical competition. But by the fourth book, Dorothy and the Wizard in Oz, Baum had gone too many times to the well. The new characters (a workhorse, a farmhand, and a pink kitten) are forgettable and forgotten. There is no plot, just visits to a series of peculiar locations, terminating in the characters’ arrival in Oz. Steve Parker, whose summary review of the Oz books has stuck with me for many years, said:
Signs of this are already in The Wonderful Wizard itself. The original book is roughly in three phases: Dorothy and her associates journey to the Emerald City, where they confront the Wizard. The Wizard demands that they destroy the Wicked Witch of the West, which they do, but then abandons Dorothy. And then there is a third part in which they travel south to ask Glinda to help send Dorothy home. In the 1939 MGM movie, which otherwise sticks closely to the plot of the book, the third part was omitted entirely. Glinda arrives immediately after the Wizard absconds and wraps up the story. As a small child I was incensed by this omission. But if I were making a movie of The Wizard of Oz I would do exactly the same. The third part of the book is superfluous. The four companions visit a country where everyone is a decorative china figure (nothing happens), a forest where the trees refuse to admit them (the Woodman chops them), another forest where the denizens are being terrorized by a monster (the Lion kills the monster), and a hill guarded by surly armless men whose heads fly off like corks from popguns (they fly over). Having bypassed these obstacles, they arrive at Glinda's palace and the story can get moving again. But it isn't until Dorothy and the Wizard in Oz that the “twee travelogue” mode really gets going, and it continues in the fifth book, The Road to Oz. By the sixth book, The Emerald City of Oz, it was clear that Baum was sick of the whole thing. The story is in two parts that alternate chapters. In one set of chapters, Dorothy and her uncle and aunt go on a pointless carriage tour of twee locations in Oz, completely unaware that in the intervening chapters, the wicked General Guph is gathering armies of malevolent beings to tunnel under the desert, destroy Oz, and enslave the Oz people. These chapters with Guph are really good, some of the best writing Baum ever did. Guph is easily the most interesting person in the book and Baum is certainly more interested in him than in Dorothy's visit to the town where everything is made of biscuits, the town where everything is made of paper, the town where everyone is made of jigsaw puzzles, and the town where everyone is a rabbit. But Baum couldn't really go through with his plan to destroy Oz. At the end of the book Guph's plan is foiled. Baum nevertheless tried to throw Holmes down Reichenbach Falls. Glinda casts a powerful magic spell to seal off Oz from the rest of the world entirely:
But as for Conan Doyle, it didn't work. The public demanded more, and just as Holmes came back from the grave, so did Oz. After a delay of three years, the seventh book, The Patchwork Girl of Oz, appeared. By this time Baum had had an inspiration. This book is the sort of magical fantasy he wanted to write. People only wanted to read about Oz, so Baum has set it in the Oz continuity. Ojo and his uncle supposedly live in the Munchkin country, but must flee their home in search of food, despite the fact that nobody in Oz ever has to do that. They visit the magician Dr. Pipt. He is is stated to be the same as the anonymous one mentioned in passing in The Marvelous Land of Oz, but this is not a plot point. Until the second half there is no significant connection to the rest of the series. The characters are all new (the Patchwork Girl, the Glass Cat, and the Woozy) and go on a quest to restore Ojo's uncle, who has been accidentally turned to stone. (Dorothy and other familiar characters do eventually join the proceedings.) Baum apparently felt this was an acceptable compromise, because he repeatedly used this tactic of grafting Oz bits onto an otherwise unrelated fantasy adventure. The following book, Tik-Tok of Oz, takes the pattern quite far. Its main characters are Queen Ann and her subjects. Ann is Queen of Oogaboo, which is part of Oz, except, ha ha, fooled you, it isn't:
Oogaboo is separated from the rest of Oz by a mountain pass, and when Ann and her army try to reach Oz through this pass, it is magically twisted around by Glinda (who does not otherwise appear in the book) and they come out somewhere else entirely. A variety of other characters join them, including Polychrome and the Shaggy Man (from the awful Road to Oz), and Tik-Tok (from Ozma) and they struggle with the perennially villainous Nome King, of whom Baum seemingly never tired. But there is no other connection to Oz until the plot has been completely wrapped up, around the end of chapter 23. Then Ozma and Dorothy appear from nowhere and bring everyone to Oz for two unbearably sentimental final chapters. The ninth book, The Scarecrow of Oz, often cited as the best of the series, follows exactly the same pattern. The main characters of this one are Trot, Cap'n Bill, and the Ork, who had appeared before in two of Baum's non-Oz novels, which did not sell well. No problem, Baum can bring them to Oz, where they may find more popularity among readers. So he has them find their way to Oogaboo. Excuse me, to Jinxland.
The main plot takes place entirely in Jinxland, and concerns the struggles of Pon, the gardener's boy, to marry the Princess Gloria against the wishes of King Krewl. The Scarecrow is dispatched to Jinxland to assist, but none of the other Oz people plays an important part, and once the plot is wrapped up in chapter 20 Ozma and Dorothy arrange to bring everyone back to the Emerald City for a party at which Baum drops the names of all the characters who did not otherwise appear in the book. The excellent tenth book, Rinkitink in Oz, repeats the pattern. In fact, Rinkitink was written much earlier, around 1907, but Baum couldn't get it published. So in 1916 he appended a couple of chapters in which Dorothy and the Wizard appear from nowhere to resolve the plot, and then in chapter 22 Ozma brings everyone back to the Emerald City for a party at which Baum drops the names of all the characters who did not otherwise appear in the book. Well, you get the idea. The last few books are pretty good when they are in the "not really Oz but let's say it is" mode of The Scarecrow or Rinkitink, and pretty awful when they are in "twee travelogue" mode of The Road to Oz:
Glinda was published posthumously, and Baum, who had died in 1919, was free of Oz at last. [Other articles in category /book] permanent link Mon, 20 Aug 2018
Miscellaneous addenda about Catholic priest sex abuse
I hope and expect this will be my last post on this loathsome subject. Diocesan vs. religious priestsIn the previous article, I said:
Later I added a guess about why:
I think this is probably correct. The list of Pittsburgh priests has a section the the bottom headed “Religious Priests Serving in the Diocese”, but it is empty. Kennedy's Catholic DirectoryWhile attempting to get better estimates for the total number of active priests, I located part of The Official Catholic Directory of P.J. Kennedy & Sons for the year 1980, available on the Internet Archive. It appears that this is only one volume of many, and unfortunately IA does not seem to have the others. Luckily, though, this happens to be the volume that includes information for Philadelphia, Pittsburgh, and Scranton. It reports:
I have no idea how authoritative this is, or what is the precise meaning of “official” in the title. The front matter would probably explain, but it does not appear in the one volume I have. The cover also advises “Important: see explanatory notes, pp. vi–viii”, which I have not seen. The Directory also includes information for the Ukrainian Catholic Archepathy of Philadelphia, which, being part of a separate (but still Catholic) church is separate from the Philadelphia Roman Catholic dioceses. (It reports 127 total priests.) It's not clear whether to absorb this into my estimate because I'm not sure if it was part of the total number I got from the Pennsylvania Catholic Conference. But I am not going back to check because I feel there is no point in trying to push on in this way. An authoritative and accurate answer is available from the official census, and my next step, should I care to take one, should be to go to the library and look at it, rather than continuing to pile up inaccurate guesses based on incomplete information. Sipe's earlier estimateJonathan Segal points out that A.W. Richard Sipe, a famous expert on clergy sexual abuse, had estimated in 1990 that about 6% of U.S. priests has sexually abused children. This is close to my own estimate of 6.1% for the six Pennsylvania dioceses. Most of this agreement should be ascribed to luck. Final remarkIn 1992, Magda Davitt, the Irish singer formerly known as Sinéad O'Connor, became infamous for protesting systematic Catholic sex abuse by tearing up a photograph of John Paul II on live American television. She was almost universally condemned. (The Wikipedia article has a few of the details.) This week, America: The Jesuit Review, which claims to be “the leading Catholic journal of opinion in the United States”, reported:
(“Pope Francis issues new letter on sex abuse: ‘We showed no care for the little ones’”.) A lot of people owe Sinéad O'Connor a humble apology. [Other articles in category /religion] permanent link Fri, 17 Aug 2018
What fraction of Pennsylvania Catholic priests were child molesters?
The grand jury report on Catholic clergy sexual abuse has been released and I have been poring over it. The great majority of it is details about the church's handling of the 301 “predator priests” that the grand jury identified. I have seen several places the suggestion that this is one-third of a total of 900. This is certainly not the case. There may be 900 priests there now, but the report covers all the abuse that the grand jury found in examining official records from the past seventy years or so. Taking a random example, pages 367–368 of the report concern the Reverend J. Pascal Sabas, who abused a 14-year-old boy starting in 1964. Sabas was ordained in 1954 and died in 1996. I tried to get a good estimate of the total number of priests over the period covered by the report. Information was rather sketchy. The Vatican does do an annual census of priests, the Annuarium Statisticum Ecclesiae, but I could not find it online and hardcopies sell for around €48. Summary information by continent is reported elsewhere [2], but the census unfortunately aggregates North and South America as a single continent. I did not think it reasonable to try to extrapolate from the aggregate to the number of priests in the U.S. alone, much less to Pennsylvania. Still we might get a very rough estimate as follows. The Pennsylvania Catholic Conference says that there were a total of just about 2500 priests in Pennsylvania in 2017 or 2016. The Philadelphia Archdiocese and the Altoona-Johnstown Diocese are not discussed in the grand jury report, having been the subject of previous investigations. The official websites of these two dioceses contain lists of priests and I counted 792 in the Philadelphia directory and 80 in the Altoona-Johnstown directory, so let us say that there are currently around 1620 priests total in the other six dioceses. (This seems on the high side, since my hand-count of Pittsburgh priests contains only about 200. I don't know what to make of this.) [ Addendum 20180820: I wonder if it is because my hand counts, taken from diocesan directory pages, include only diocesan priests, where the total of 2500 also includes the religious priests. I should look into this. ] Suppose that in 1950 there were somewhat more, say 2160. The average age of ordination is around 35 years; say that a typical priestly career lasts around 40 years further. So say that each decade, around one-quarter of the priesthood retires. If around 84% of the retirees are replaced, the replacement brings the total number back up to 96% of its previous level, so that after 70 years about 75% remain. Then the annual populations might be approximately: $$\begin{array}{rrrrr} \text{year} & \text{total population} & \text{retirements} & \text{new arrivals} & \\ 1950 & 2160 & 540 & 453 \\ 1960 & 2073 & 518 & 434 \\ 1970 & 1989 & 497 & 417 \\ 1980 & 1909 & 477 & 400 \\ 1990 & 1832 & 458 & 384 \\ 2000 & 1758 & 439 & 368 \\ 2010 & 1687 & 421 & 354 \\ \hline \text{(total)} & & 3350 & 2810 \\ \end{array}$$ From the guesses above we might estimate a total number of individual priests serving between 1950 and 2018 as !!2160 + 2810 - 70 = 4900!!. (That's 2160 priests who were active in 1950, plus 2810 new arrivals since then, except minus !!354\cdot20\% \approx 70!! because it's only 2018 and 20% of the new arrivals for 2010–2020 haven't happened yet.) So the 301 predator priests don't represent one-third of the population, they probably represent “only” around !!\frac{301}{4900} \approx 6.1\%!!. The church's offical response is availble. [ Addenda: An earlier version of this article estimated around 900 current priests instead of 1620; I believe that this was substantially too low. Also, that earlier version incorrectly assumed that ordinations equalled new priests, which is certainly untrue, since ordained priests can and do arrive in Pennsylvania from elsewhere. ] [ Addendum 20180820: Some followup notes. ] [Other articles in category /religion] permanent link Tue, 14 Aug 2018A few years ago Katara was very puzzled by traffic jams and any time we were in a traffic slowdown she would ask questions about it. For example, why is traffic still moving, and why does your car eventually get through even though the traffic jam is still there? Why do they persist even after the original cause is repaired? But she seemed unsatisfied with my answers. Eventually in a flash of inspiration I improvised the following example, which seemed to satisfy her, and I still think it's a good explanation. Suppose you have a four-lane highway where each lane can carry up to 25 cars per minute. Right now only 80 cars per minute are going by so the road is well under capacity. But then there is a collision or some other problem that blocks one of the lanes. Now only three lanes are open and they have a capacity of 75 cars per minute. 80 cars per minute are arriving, but only 75 per minute can get past the blockage. What happens now? Five cars more are arriving every minute than can leave, and they will accumulate at the blocked point. After two hours, 600 cars have piled up. But it's not always the same 600 cars! 75 cars per minute are still leaving from the front of the traffic jam. But as they do, 80 cars have arrived at the back to replace them. If you are at the back, there are 600 cars in front of you waiting to leave. After a minute, the 75 at the front have left and there are only 525 cars in front of you; meanwhile 80 more cars have joined the line. After 8 minutes all the cars in front of you have left and you are at the front and can move on. Meanwhile, the traffic jam has gotten bigger. Suppose that after two hours the blockage is cleared. The road again has a capacity of 100 cars per minute. But cars are still arriving at 80 per minute, so each minute 20 more cars can leave than arrived. There are 600 waiting, so it takes another 30 minutes for the entire traffic jam to disperse. This leaves out some important second-order (and third-order) effects. For example, traffic travels more slowly on congested roads; maximum safe speed decreases with following distance. But as a first explanation I think it really nails the phenomenon. [Other articles in category /tech] permanent link Wed, 08 Aug 2018In my original article, I said:
Jeremy Yallop brought up an example that I had definitely seen before. In 2008 Conor McBride and Ross Paterson wrote an influential paper, “Idioms: applicative programming with effects” that introduced the idea of an applicative functor, a sort of intermediate point between functors and monads. It has since made its way into standard Haskell and was deemed sufficiently important to be worth breaking backward compatibility. McBride and Paterson used several notations for operations in an
applicative functor. Their primary notation was !!\iota!! for what is
now known as $$\iota f \circledast is_1 \circledast \ldots \circledast is_n$$ came up so often they wanted a less cluttered notation for it:
On page 5, they suggested an exercise:
They give a hint, intended to lead the reader to the solution, which
involves a function named
and have it mean
The haskell wiki has details, written by Don Stewart when the McBride-Paterson paper was still in preprint. The wiki goes somewhat further, also defining
so that
now does a I have certainly read this paper more than once, and I was groping for this example while I was writing the original article, but I couldn't quite put my finger on it. Thank you, M. Yallop! [ By the way, I am a little bit disappointed that the haskell wiki is not called “Hicki”. ] [Other articles in category /prog/haskell] permanent link In the previous article I described a rather odd abuse of the Haskell type system to use a singleton type as a sort of pseudo-keyword, and asked if anyone had seen this done elsewhere. Joachim Breitner reported having seen this before. Most recently in
LiquidHaskell, which defines a
so that they can end every proof with
This example is from Vazou et al., Functional Pearl: Theorem Proving
for All, p. 3. The authors
explain: “The Or see the examples from the bottom of the LH splash
page, proving the
associative law for I looked in the rest of the LiquidHaskell distribution but did not find any other uses of the singleton-type trick. I would still be interested to see more examples. [ Addendum: Another example. ] [Other articles in category /prog/haskell] permanent link
Is this weird Haskell technique something I made up?
A friend asked me the other day about techniques in Haskell to pretend
to make up keywords. For example, suppose we want something like a
(monadic)
This uses a condition Now suppose for whatever reason we don't like writing it as
Now we can write
and the But then I had a surprising idea. We can define it this way:
Now we write
and if we omit or misspell the For a less trivial (but perhaps sillier) example, consider:
The idea here is that we want to try a computation, and do one thing
if it succeeds and another if it throws an exception. The point is
not the usefulness of this particular and somewhat contrived exception
handling construct, it's the syntactic sugar of the
I was fairly confident I had seen something like this somewhere before, and that it was not original to me. But I've asked several Haskell experts and nobody has said it was familar. I thought perhaps I had seen it somewhere in Brent Yorgey's code, but he vehemently denied it. So my question is, did I make up this technique of using a one-element type as a pretend keyword? [ Addendum: At least one example of this trick appears in LiquidHaskell. I would be interested to hear about other places it has been used. ] [ Addendum: Jeremy Yallop points out that a similar trick was hinted at in McBride and Paterson “Idioms: applicative programming with effects” (2008), with which I am familiar, although their trick is both more useful and more complex. So this might have been what I was thinking of. ] [Other articles in category /prog/haskell] permanent link Thu, 02 Aug 2018
How to explain infinity to kids
A professor of mine once said to me that all teaching was a process of lying, and then of replacing the lies with successively better approximations of the truth. “I say it's like this,” he said, “and then later I say, well, it's not actually like that, it's more like this, because the real story is too complicated to explain all at once.” I wouldn't have phrased it like this, but I agree with him in principle. One of the most important issues in pedagogical practice is deciding what to leave out, and for how long. Kids inevitably want to ask about numerical infinity, and many adults will fumble the question, mumbling out some vague or mystical blather. Mathematics is prepared to offer a coherent and carefully-considered answer. Unfortunately, many mathematically-trained people also fumble the question, because mathematics is prepared to offer too many answers. So the mathematical adult will often say something like “well, it's a lot of things…” which for this purpose is exactly not what is wanted. When explaining the concept for the very first time, it is better to give a clear and accurate partial explanation than a vague and imprecise overview. This article suggests an answer that is short, to the point, and also technically correct. In mathematics “infinity” names a whole collection of not always closely related concepts from analysis, geometry, and set theory. Some of the concepts that come under this heading are:
I made a decision ahead of time that when my kids first asked what infinity was, I would at first adopt the stance that “infinity” referred specifically to the set-theoretic ordinal !!\omega!!, and that the two terms were interchangeable. I could provide more details later on. But my first answer to “what is infinity” was:
As an explanation of !!\omega!! for kids, I think this is flawless. It's briefand it's understandable. It phrases the idea in familiar terms: counting. And it is technically unimpeachable. !!\omega!! is, in fact, precisely the unique smallest number you can't count to. How can there be a number that you can't count to? Kids who ask about infinity are already quite familiar with the idea that the sequence of natural numbers is unending, and that they can count on and on without bound. “Imagine taking all the numbers that you could reach by counting,” I said. “Then add one more, after all of them. That is infinity.” This is a bit mind-boggling, but again it is technically unimpeachable, and the mind-bogglyness of it is nothing more than the intrinsic mind-bogglyness of the concept of infinity itself. None has been added by vagueness or imprecise metaphor. When you grapple with this notion, you are grappling with the essence of the problem of the completed infinity. In my experience all kids make the same move at this point, which is to ask “what comes after infinity?” By taking “infinity” to mean !!\omega!!, we set ourselves up for an answer that is much better than the perplexing usual one “nothing comes after infinity”, which, if infinity is to be considered a number, is simply false. Instead we can decisively say that there is another number after infinity, which is called “infinity plus one”. This suggests further questions. “What comes after infinity plus one?” is obvious, but a bright kid will infer the existence of !!2\cdot\omega!!. A different bright kid might ask about !!\omega-1!!, which opens a different but fruitful line of discussion: !!\omega!! is not a successor ordinal, it is a limit ordinal. Or the kid might ask if infinity plus one isn't equal to infinity, in which case you can discuss the non-commutativity of ordinal addition: if you add the “plus one” at the beginning, it is the same (except for !!\omega!! itself, the picture has just been shifted over on the page): But if you add the new item at the other end, it is a different picture: Before there was only one extra item on the right, and now there are two. The first picture exemplifies the Dedekind property, which is an essential feature of infinity. But the existence of an injection from !!\omega+1!! to !!\omega!! does not mean that every such map is injective. Just use !!\omega!!. Later on the kid may ask questions that will need to be answered with “Earlier, I did not tell you the whole story.” That is all right. At that point you can reveal the next thing. [Other articles in category /math] permanent link Mon, 30 Jul 2018
Lost and found authors: The Poppy Seed Cakes
As a very small child, I loved The Poppy Seed Cakes (1924), by Margery Clark. Later I read it to my own kids. Toph never cared for it, but it was by far Katara's favorite book when she was three. The illustrations are by Maud and Miska Petersham, who later won the Caldecott Medal. (At left, the protagonist, Andrewshek, meeting Auntie Katushka's new white goat, who has run home from the market without her. He is swinging on the gate, which his Autie Katushka has specifically told him not to do, or the chickens will run out into the road. At right, Auntie Katushka arriving from the Old Country. Depicted are the fine feather bed, the umbrella with the crooked handle, and probably the bag of poppy seeds, all of which are plot points.) As an adult I wanted to know if Margery Clark had written anything else. And the answer was, yes! Margery Clark, I learned, was a pseudonym for the two authors, Margery Closey Quigley and Mary E. Clark, who were librarians in Endicott, New York. The town was full of Russian and Polish immigrants who came there to make shoes, and Andrewshek and his Auntie Katushka were no doubt inspired by real library patrons. I looked up maps of Endicott in 1924 and found the little park with the stream where Andrewshek's picnic was nearly stolen by a swan. I spent way too much time trying to find out if Andrewshek was more likely to be Russian or Polish by poring over census data. And Quigley had written another book! After Endicott she became a librarian in Montclair, New Jersey and wrote Portrait of a Library (1936) about how the Montclair Public Library was run. I found it fascinating and compelling. One detail I remember is that when automobiles became common, they started to offer a pickup and delivery service, which the citizens loved:
She mentions that in 1934, over 3,000 books were delivered via Western Union messenger, with the borrower paying the 10¢ delivery fee. I think it's pretty awesome that they were able to press the A&P guy into library service. My favorite detail, though, concerned a major renovation to the library building. They took the opportunity to reorganize the layout of the sections and shelves:
“Oh, wow!” I said. “I know who that was!” That was a fun moment. (But I see now that I was wrong! Montclair was home to two world-famous efficiency engineers, but one of them had died in 1924, and the library renovation was done in 1931–1932. Quigley's efficiency engineer was surely Lillian Moller Gilbreth. Ooops!) Regrettably, the Internet Archive has only an abridged version of The Poppy Seed Cakes, with only three of the eight stories. I may have it professionally scanned. [Other articles in category /book] permanent link Sat, 28 Jul 2018When I was a kid I enjoyed a story called George Washington's Breakfast, which I have since learned was written in 1969 by Jean Fritz. The protagonist is a boy named George Washington Allen who is fascinated by all things related to his namesake. One morning at breakfast he wonders what George Washington ate for his own breakfast. He has read all the books in his school library about George Washington, but does not know this important detail. His grandmother promises him that when he finds out what George Washington had for breakfast, she will cook it for him, whatever it is. This launches the whole family on an odyssey that takes them as far as Mount Vernon, but even the people at Mount Vernon don't know. In the end George gets lucky: he finds an old book in the attic that authoritatively states that George Washington
George is thrilled, and, having looked up hoecake in the dictionary to find out what it is (a corn cake cooked in the fireplace, on a hoe), jumps up from the table. His grandmother asks him where he is going, and of course he is going to the basement to get the hoe. Grandma refuses to cook on a hoe; George objects. “When you were in George Washington's kitchen in Mount Vernon, did you see any hoes?” “Well no, but…” “Did you see any black iron griddles?” “Yes.” “Then that's what I'll use.” This stuck with me for many years, and thinking back on it one day as an adult, I was suddenly certain that George Allen and his family were black, notwithstanding the plump white kid in the illustrations. At some point I even looked up the original publication to see if the kid was black in the 1969 illustrations. Nope, they are by Paul Galdone and he has made George white. A new edition was published in 1998 with new illustrations by Tomie dePaola, again with a white kid. Ms. Fritz died last year at the age of 102, so it is too late to ask her what she had in mind. But it doesn't matter to me; I am sure George is black. There was a trend in the 1960s for white authors of children’s books to make an effort to depict black kids. (For example: The Snowy Day (1962) and its sequels (through 1968); Corduroy (1968); and many others less well-known.) Anyway, chalk this up as another story that could not happen in 2018. George's family would search on the Internet, and immediately find out about the hoecakes. I don't recall exactly book it was that George found in the attic, but in a minute’s searching I was able to find out that it was probably Paul Leicester Ford’s George Washington (1896), and the authoritative statement about Washington's hoecake-and-tea breakfast, on page 193, is quoted from Samuel Stearns, a contemporary of Washington's. The Stearns quotation definitely appeared in Fritz's story; I remember the wording, and even Samuel Stearns rings a bell now that I see his name again. For oddballs like me and George Washington Allen, who become obsessed by trivial questions, the Internet is a magnificent and glorious boon. I often think that for me, one of the best results of the rise of the Internet is that I can now track down all the books from my childhood that I liked but only half-remember, find out who wrote them and read them again. [Other articles in category /book] permanent link Thu, 26 Jul 2018There are well-known tests if a number (represented as a base-10 numeral) is divisible by 2, 3, 5, 9, or 11. What about 7? Let's look at where the divisibility-by-9 test comes from. We add up the digits of our number !!n!!. The sum !!s(n)!! is divisible by !!9!! if and only if !!n!! is. Why is that? Say that !!d_nd_{n-1}\ldots d_0!! are the digits of our number !!n!!. Then $$n = \sum 10^id_i.$$ The sum of the digits is $$s(n) = \sum d_i$$ which differs from !!n!! by $$\sum (10^i-1)d_i.$$ Since !!10^i-1!! is a multiple of !!9!! for every !!i!!, every term in the last sum is a multiple of !!9!!. So by passing from !!n!! to its digit sum, we have subtracted some multiple of !!9!!, and the residue mod 9 is unchanged. Put another way: $$\begin{align} n &= \sum 10^id_i \\ &\equiv \sum 1^id_i \pmod 9 \qquad\text{(because $10 \equiv 1\pmod 9$)} \\ &= \sum d_i \end{align} $$ The same argument works for the divisibility-by-3 test. For !!11!! the analysis is similar. We add up the digits !!d_0+d_2+\ldots!! and !!d_1+d_3+\ldots!! and check if the sums are equal mod 11. Why alternating digits? It's because !!10\equiv -1\pmod{11}!!, so $$n\equiv \sum (-1)^id_i \pmod{11}$$ and the sum is zero only if the sum of the positive terms is equal to the sum of the negative terms. The same type of analysis works similarly for !!2, 4, 5, !! and !!8!!. For !!4!! we observe that !!10^i\equiv 0\pmod 4!! for all !!i>1!!, so all but two terms of the sum vanish, leaving us with the rule that !!n!! is a multiple of !!4!! if and only if !!10d_1+d_0!! is. We could simplify this a bit: !!10\equiv 2\pmod 4!! so !!10d_1+d_0 \equiv 2d_1+d_0\pmod 4!!, but we don't usually bother. Say we are investigating !!571496!!; the rule tells us to just consider !!96!!. The "simplified" rule says to consider !!2\cdot9+6 = 24!! instead. It's not clear that that is actually easier. This approach works badly for divisibility by 7, because !!10^i\bmod 7!! is not simple. It repeats with period 6. $$\begin{array}{c|cccccc|ccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ %10^i & 1 & 10 & 100 & 1000 & 10000 & \ldots \\ 10^i\bmod 7 & 1 & 3 & 2 & 6 & 4 & 5 & 1 & 3 & 2 & 6 & 4 &\ldots \\ \end{array} $$ The rule we get from this is: Take the units digit. Add three times the ones digit, twice the hundreds digit, six times the thousands digit… (blah blah blah) and the original number is a multiple of !!7!! if and only if the sum is also. For example, considering !!12345678!! we must calculate $$\begin{align} 12345678 & \Rightarrow & 3\cdot1 + 1\cdot 2 + 5\cdot 3 + 4\cdot 4 + 6\cdot 5 + 2\cdot6 + 3\cdot 7 + 1\cdot 8 & = & 107 \\\\ 107 & \Rightarrow & 2\cdot1 + 3\cdot 0 + 1\cdot7 & = & 9 \end{align} $$ and indeed !!12345678\equiv 107\equiv 9\pmod 7!!. My kids were taught the practical divisibility tests in school, or perhaps learned them from YouTube or something like that. Katara was impressed by my ability to test large numbers for divisibility by 7 and asked how I did it. At first I didn't think about my answer enough, and just said “Oh, it's not hard, just divide by 7 and look at the remainder.” (“Just count the legs and divide by 4.”) But I realized later that there are several tricks I was using that are not obvious. First, she had never learned short division. When I was in school I had been tormented extensively with long division, which looks like this: This was all Katara had been shown, so when I said “just divide by 7” this is what she was thinking of. But you only need long division for large divisors. For simple divisors like !!7!!, I was taught short division, an easier technique:Yeah, I wrote 4 when I meant 3. It doesn't matter, we don't care about the quotient anyway. But that's one of the tricks I was using that wasn't obvious to Katara: we don't care about the quotient anyway, only the remainder. So when I did this in my head, I discarded the parts of the calculation that were about the quotient, and only kept the steps that pertained to the remainder. The way I was actually doing this sounded like this in my mind: 7 into 12 leaves 5. 7 into 53 leaves 4. 7 into 44 leaves 2. 7 into 25 leaves 4. 7 into 46 leaves 4. 7 into 57 leaves 5. 7 into 58 leaves 9. The answer is 9. At each step, we consider only the leftmost part of the number, starting with !!12!!. !!12\div 7 !! has a remainder of 5, and to this 5 we append the next digit of the dividend, 3, giving 53. Then we continue in the same way: !!53\div 7!! has a remainder of 4, and to this 4 we append the next digit, giving 44. We never calculate the quotient at all. I explained the idea with a smaller example, like this: Suppose you want to see if 1234 is divisible by 7. It's 1200-something, so take away 700, which leaves 500-something. 500-what? 530-something. So take away 490, leaving 40-something. 40-what? 44. Now take away 42, leaving 2. That's not 0, so 1234 is not divisible by 7. This is how I actually do it. For me this works reasonably well up to 13, and after that it gets progressively more difficult until by 37 I can't effectively do it at all. A crucial element is having the multiples of the divisor memorized. If you're thinking about the mod-13 residue of 680-something, it is a big help to know immediately that you can subtract 650. A year or two ago I discovered a different method, which I'm sure must be ancient, but is interesting because it's quite different from the other methods I described. Suppose that the final digit of !!n!! is !!b!!, so that !!n=10a+b!!. Then !!-2n = -20a-2b!!, and this is a multiple of !!7!! if and only if !!n!! is. But !!-20a\equiv a\pmod7 !!, so !!a-2b!! is a multiple of !!7!! if and only if !!n!! is. This gives us the rule: To check if !!n!! is a multiple of 7, chop off the last digit, double it, and subtract it from the rest of the number. Repeat until the answer becomes obvious. For !!1234!! we first chop off the !!4!! and subtract !!2\cdot4!! from !!123!! leaving !!115!!. Then we chop off the !!5!! and subtract !!2\cdot5!! from !!11!!, leaving !!1!!. This is not a multiple of !!7!!, so neither is !!1234!!. But with !!1239!!, which is a multiple of !!7!!, we get !!123-2\cdot 9 = 105!! and then !!10-2\cdot5 = 0!!, and we win. In contrast to the other methods in this article, this method does not tell you the remainder on dividing because it does not preserve the residue mod 7. When we started with !!1234!! we ended with !!1!!. But !!1234\not\equiv 1\pmod 7!!; rather !!1234\equiv 2!!. Each step in this method multiplies the residue by -2, or, if you prefer, by 5. The original residue was 2, so the final residue is !!2\cdot-2\cdot-2 = 8 \equiv 1\pmod 7!!. (Or, if you prefer, !!2\cdot 5\cdot 5= 50 \equiv 1\pmod 7!!.) But if we only care about whether the residue is zero, multiplying it by !!-2!! doesn't matter. There are some shortcuts in this method too. If the final digit is !!7!!, then rather than doubling it and subtracting 14 you can just chop it off and throw it away, going directly from !!10a+7!! to !!a!!. If your number is !!10a+8!! you can subtract !!7!! from it to make it easier to work with, getting !!10a+1!! and then going to !!a-2!! instead of to !!a-16!!. Similarly when your number ends in !!9!! you can go to !!a-4!! instead of to !!a-18!!. And on the other side, if it ends in !!4!! it is easier to go to !!a-1!! instead of to !!a-8!!. But even with these tricks it's not clear that this is faster or easier than just doing the short division. It's the same number of steps, and it seems like each step is about the same amount of work. Finally, I once wowed Katara on an airplane ride by showing her this:
To check !!1429!! using this device, you start at ⓪. The first digit is !!1!!, so you follow one black arrow, to ①, and then a blue arrow, to ③. The next digit is !!4!!, so you follow four black arrows, back to ⓪, and then a blue arrow which loops around to ⓪ again. The next digit is !!2!!, so you follow two black arrows to ② and then a blue arrow to ⑥. And the last digit is 9 so you then follow 9 black arrows to ① and then stop. If you end where you started, at ⓪, the number is divisible by 7. This time we ended at ①, so !!1429!! is not divisible by 7. But if the last digit had been !!1!! instead, then in the last step we would have followed only one black arrow from ⑥ to ⓪, before we stopped, so !!1421!! is a multiple of 7. This probably isn't useful for mental calculations, but I can imagine that if you were stuck on a long plane ride with no calculator and you needed to compute a lot of mod-7 residues for some reason, it could be quicker than the short division method. The chart is easy to construct and need not be memorized. The black arrows obviously point from !!n!! to !!n+1!!, and the blue arrows all point from !!n!! to !!10n!!. I made up a whole set of these diagrams and I think it's fun to see how the conventional divisibility rules turn up in them. For example, the rule for divisibility by 3 that says just add up the digits:
Or the rule for divisibility by 5 that says to ignore everything but the last digit:
[Other articles in category /math] permanent link Wed, 25 Jul 2018In my email today I found a note I sent to myself on 24 June 2015 that says only:
which would be useful, if you don't drink your sake so quickly that it is gone before it has cooled. As far as I know, these are not common and perhaps do not exist at all. Why not? Is this a billion-dollar idea? A few problems come to mind. If the bottle has a cord, it will be hard to pour and will be easily upset. Maybe the best choice here would be a special power supply with relatively high voltage and a thin cord such as is used for earbuds. But this might be dangerous, or impractical for other reasons I am not thinking of. I think battery power is also probably impractical. Heating requires a lot of energy and batteries don't supply enough. They would need to be frequently replaced, which gets expensive. Also temperature control might be troublesome. You would need some sort of thermostat in the bottle. Typical inexpensive heating containers and immersion heaters are for bringing water to a boil, which is much simpler than warming sake to the right temperature: just dump in as much heat as possible, as quickly as possible, and perhaps also arrange to have the heat shut off if the heating element gets up to 100°C. This is much too hot for sake. I think a more practical solution would be a tabletop hot water bath with a bottle-shaped depression in it. The hot water bath could have the thermostat and be permanently attached to a wall outlet. You insert the bottle in its bath to keep it warm when you are not pouring. This seems practical enough that I imagine it already exists. In fact it occurs to me that I owned a similar sort of warmer at one point, for warming baby bottles. But a quick perusal of available sake warmers suggests that this approach is not common. What gives? [Other articles in category /food] permanent link Mon, 23 Jul 2018
Operations that are not quite associative
The paper “Verification of Identities” (1997) of Rajagopalan and Schulman discusses fast ways to test whether a binary operation on a finite set is associative. In general, there is no method that is faster than the naïve algorithm of simply checking whether $$a\ast(b\ast c) = (a\ast b)\ast c$$ for all triples !!\langle a, b, c\rangle!!. This is because:
(Page 3.) But R&S do not give an example. I now have a very nice example, and I think the process that led me to it is a good example of Lower Mathematics at work. Let's say that an operation !!\ast!! is “good” if it is associative except in exactly one case. We want to find a “good” operation. My first idea was that if we could find a primitive good operation on a set of 3 elements, we could probably extend it to give a good operation on a larger set. Say the set is !!\{a_0, a_1, a_2, b_0, b_1, \ldots, b_{n-4}\}!!. We just need to define the extended operation so that if either of the operands is !!b_i!!, it is associative, and if both operands are !!a_i!! then it is the same as the primitive good operation we already found. The former part is easy: just make it constant, say !!x\ast y = b_0!! except when !!x,y\in\{a_0, a_1, a_2\}!!. So now all we need to do is find a single good primitive operation, and I did not expend any thought on this at all. There are only !!3^9=19683!! binary operations, and we could quite easily write a program to check them all. In fact, we can do better: generate a binary operation at random and check it. If it's not the primitive good operation we want, just throw it away and try again. This could take longer to run than the exhaustive search, if there happen to be very few good operations and if the program is unlucky, but the program is easier to write, and the run time will be utterly insignificant either way. I wrote the program, which instantly produced: $$ \begin{array}{c|ccc} \ast & 0 & 1 & 2 \\ \hline 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 2 & 0 & 1 & 2 \end{array} $$ This is associative except for the case !!1\ast(2\ast 1) \ne (1\ast 2)\ast 1!!. This solves the problem. But confirming that this is a good operation requires manually checking 27 cases, or a perhaps not-immediately-obvious case analysis. But on a later run of the program, I got lucky and it found a simpler operation, which I can explain without a table:
Now we don't have to check 27 cases. The operation is simpler, so the proof is too: We know !!b\ast c\ne 1!!, so !!a\ast(b\ast c) !! must be !!0!!. And the only way !!(a \ast b)\ast c \ne 0!! can occur is when !!a\ast b=2!! and !!c=1!!, so !!a=2, b=1, c=1!!. Now we can even dispense with the construction that extended the operation from !!3!! to !!n!! elements, because the description of the extended operation is the same. We wanted to extend it to be constant whenever !!a!! or !!b!! was larger than !!2!!, and that's what the description already says! So that reduces the whole thing to about two sentences, which explain the example and why it works. But when reduced in that way, you see how the example works but not how you might go about finding it. I think the interesting part is to see how to get there, and quite a lot of mathematical education tends to over-emphasize analysis (“how can we show this is a good operation?”) at the expense of synthesis (“how can we find a good operation?”). The exhaustive search would probably have produced the simple operation early on in its run, so there is something to be said for that approach too. [Other articles in category /math] permanent link Fri, 20 Jul 2018Volume was way down in May and June, mainly because of giant work crises that ate all my energy. I will try to get back on track now. May
JuneIn the past I have boldfaced posts that seemed more likely to be of general interest. None of these seem likely to be of general interest. Also, I think it is time to stop posting these roundups. By now everyone who wants to know about shitpost.plover.com is aware of it and can follow along without prompting. So I expect this will be the last of these posts. Shitposting will continue, but without these summaries. [Other articles in category /meta/shitpost] permanent link Tue, 17 Jul 2018[ I wrote this in 2007 and it seems I forgot to publish it. Enjoy! ] I eat pretty much everything. Except ketchup. I can't stand ketchup. When I went to Taiwan a couple of years ago my hosts asked if there were any foods I didn't eat. I said no, except for ketchup. "Ketchup? You mean that red stuff?" Right. Yes, it's strange. When I was thirteen my grandparents took me to Greece, and for some reason I ate hardly anything but souvlaki the whole time. When I got home, I felt like a complete ass. I swore that I would never squander another such opportunity, and that if I ever went abroad again I would eat absolutely everything that was put before me. This is a good policy not just because it exposes me to a lot of delicious and interesting food, and not just because it prevents me from feeling like a complete ass, but also because I don't have to worry that perhaps my hosts will be insulted or disappointed that I won't eat the food they get for me. On my second trip to Taiwan, I ate at a hot pot buffet restaurant. They give you a pot of soup, and then you go to the buffet and load up with raw meat and vegetables and things, and cook them at your table in the soup. It's fun. In my soup there were some dark reddish-brown cubes that had approximately the same texture as soft tofu. I didn't know what it was, but I ate it and tried to figure it out. The next day I took the bus to Lishan (梨山), and through good fortune was invited to eat dinner with a Taiwanese professor of criminology and his family. The soup had those red chunks in it again, and I said "I had these for lunch yesterday! What are they?" I then sucked one down quickly, because sometimes people interpret that kind of question as a criticism, and I didn't want to offend the professor. Actually it's much easier to ask about food in China than it is in, say, Korea. Koreans are defensive about their cuisine. They get jumpy if you ask what something is, and are likely to answer "It's good. Just eat it!". They are afraid that the next words out of your mouth will be something about how bad it smells. This is because the Japanese, champion sneerers, made about one billion insulting remarks about smelly Korean food while they were occupying the country between 1911 and 1945. So if you are in Korea and you don't like the food, the Koreans will take it very personally. Chinese people, on the other hand, know that they have the best food in the world, and that everyone loves Chinese food. If you don't like it, they will not get offended. They will just conclude that you are a barbarian or an idiot, and eat it themselves. Anyway, it turns out that the reddish-brown stuff was congealed duck's blood. Okay. Hey, I had congealed duck blood soup twice in two days! No way am I going home from this trip feeling like an ass. So the eat-absolutely-everything policy has worked out well for me, and although I haven't liked everything, at least I don't feel like I wasted my time. The only time I've regretted the policy was on my first trip to Taiwan. I was taken out to dinner and one of the dishes turned out to be pieces of steamed squid. That's not my favorite food, but I can live with it. But the steamed squid was buried under a big, quivering mound of sugared mayonnaise. I remembered my policy, and took a bite. I'm sure I turned green. So that's the food that I couldn't eat. [ Some of this 2007 article duplicates stuff I have said since; for example I cut out the chicken knuckles story, which would have been a repeat. Also previously; also previously; and another one ] [Other articles in category /food] permanent link Thu, 12 Jul 2018Here is another bit of Perl code:
The idea here is that we are expecting A relatively minor problem is that if someone passes an object with no
But the real problem here is that the function's interface is not simple enough. The function needs the string. It should insist on being passed the string. If the caller has the string, it can pass the string. If the caller has a cookie object, it should extract the string and pass the string. If the caller has some other object that contains the string, it should extract the string and pass the string. It is not the job of this function to know how to extract cookie strings from every possible kind of object. I have seen code in which this obsequiousness has escalated to
absurdity. I recently saw a function whose job was to send an email.
It needs an
Here the function needs an But that string could be passed in any of Oh, and by the way, that string might not be a string! It might be the actual object, so there are actually seven possibilities:
Notice that if We hope by the end of this rigamarole that All this because this function was not prepared to insist firmly that its arguments be passed in a simple and unambiguous format, say like this:
I am not certain why programmers think it is a good idea to have functions communicate their arguments by way of a round of Charades. But here's my current theory: some programmers think it is discreditable for their function to throw an exception. “It doesn't have to die there,” they say to themselves. “It would be more convenient for the caller if we just accepted either form and did what they meant.” This is a good way to think about user interfaces! But a function's calling convention is not a user interface. If a function is called with the wrong arguments, the best thing it can do is to drop dead immediately, pausing only long enough to gasp out a message explaining what is wrong, and incriminating its caller. Humans are deserving of mercy; calling functions are not. Allowing an argument to be passed in seven different ways may be
convenient for the programmer writing the call, who can save a few
seconds looking up the correct spelling of Novice programmers may ask “But what if this is business-critical code? A failure here could be catastrophic!” Perhaps a failure here could be catastrophic. But if it is a catastrophe to throw an exception, when we know the caller is so confused that it is failing to pass the required arguments, then how much more catastrophic to pretend nothing is wrong and to continue onward when we are surely ignorant of the caller's intentions? And that catastrophe may not be detected until long afterward, or at all. There is such a thing as being too accommodating. [Other articles in category /prog/perl] permanent link Sat, 07 Jul 2018[ This article has undergone major revisions since it was first published yesterday. ] Here is a line of Perl code:
This looks to see if That
It's easy to get this right. Instead of
one can simply use:
Moral of the story: programmers write too much code. I am reminded of something chess master Aron Nimzovitch once said, maybe in Chess Praxis, that amateur chess players are always trying to be Doing Something. [Other articles in category /prog/perl] permanent link Fri, 06 Jul 2018
In which, to my surprise, I find myself belonging to a group
My employer ZipRecruiter had a giant crisis at last month, of a scale that I have never seen at this company, and indeed, have never seen at any well-run company before. A great many of us, all the way up to the CTO, made a heroic effort for a month and got it sorted out. It reminded me a bit of when Toph was three days old and I got a call from the hospital to bring her into the emergency room immediately. She had jaundice, which is not unusual in newborn babies. It is easy to treat, but if untreated it can cause permanent brain damage. So Toph and I went to the hospital, where she underwent the treatment, which was to have very bright lights shined directly on her skin for thirty-six hours. (Strange but true!) The nurses in the hospital told me they had everything under control, and they would take care of Toph while I went home, but I did not go. I wanted to be sure that Toph was fed immediately and that her diapers were changed timely. The nurses have other people to take care of, and there was no reason to make her wait to eat and sleep when I could be there tending to her. It was not as if I had something else to do that I felt was more important. So I stayed in the room with Toph until it was time for us to go home, feeding her and taking care of her and just being with her. It could have been a very stressful time, but I don't remember it that way. I remember it as a calm and happy time. Toph was in no real danger. The path forward was clear. I had my job, to help Toph get better, and I was able to do it undistracted. The hospital (Children's Hospital of Philadelphia) was wonderful, and gave me all the support I needed to do my job. When I got there they showed me the closet where the bedding was and the other closet where the snacks were and told me to help myself. They gave me the number to call at mealtimes to order meals to be sent up to my room. They had wi-fi so I could work quietly when Toph was asleep. Everything went smoothly, Toph got better, and we went home. This was something like that. It wasn't calm; it was alarming and disquieting. But not in an entirely bad way; it was also exciting and engaging. It was hard work, but it was work I enjoyed and that I felt was worth doing. I love working and programming and thinking about things, and doing that extra-intensely for a few weeks was fun. Stressful, but fun. And I was not alone. So many of the people I work with are so good at their jobs. I had all the support I needed. I could focus on my part of the work and feel confident that the other parts I was ignoring were being handled by competent and reasonable people who were at least as dedicated as I was. The higher-up management was coordinating things from the top, connecting technical and business concerns, and I felt secure that the overall design of the new system would make sense even if I couldn't always understand why. I didn't want to think about business concerns, I wanted someone else to do it for me and tell me what to do, and they did. Other teams working on different components that my components would interface with would deliver what they promised and it would work. And the other programmers in my group were outstanding. We were scattered all over the globe, but handed off tasks to one another without any mishaps. I would come into work in the morning and the guys in Europe would be getting ready to go to bed and would tell me what they were up to and the other east-coasters and I could help pick up where they left off. The earth turned and the west-coasters appeared and as the end of the day came I would tell them what I had done and they could continue with it. I am almost pathologically averse to belonging to groups. It makes me uncomfortable and even in groups that I have been associated with for years I feel out of place and like my membership is only provisional and temporary. I always want to go my own way and if everyone around me is going a different way I am suspicious and contrarian. When other people feel group loyalty I wonder what is wrong with them. The up-side of this is that I am more willing than most people to cross group boundaries. People in a close-knit community often read all the same books and know all the same techniques for solving problems. This means that when a problem comes along that one of them can't solve, none of the rest can solve it either. I am sometimes the person who can find the solution because I have spent time in a different tribe and I know different things. This is a role I enjoy. Higher-Order Perl exemplifies this. To write Higher-Order Perl I visited functional programming communities and tried to learn techniques that those communities understood that people outside those communities could use. Then I came back to the Perl community with the loot I had gathered. But it's not all good. I have sometimes been able to make my non-belonging work out well. But it is not a choice; it's the way I am made, and I can't control it. When I am asked to be part of a team, I immediately become wary and wonder what the scam is. I can be loyal to people personally, but I have hardly any group loyalty. Sometimes this can lead to ugly situations. But in fixing this crisis I felt proud to be part of the team. It is a really good team and I think it says something good about me that I can work well with the rest of them. And I felt proud to be part of this company, which is so functional, so well-run, so full of kind and talented people. Have I ever had this feeling before? If I have it was a long, long time ago. G.H. Hardy once wrote that when he found himself forced to listen to pompous people, he would console himself by thinking:
Well, I was at ZipRecruiter during the great crisis of June 2018 and I was able to do my part and to collaborate with those people on equal terms, and that is something to be proud of. [Other articles in category /brain] permanent link Wed, 04 Jul 2018
Jackson and Gregg on optimization
Today Brendan Gregg's blog has an article Evaluating the Evaluation: Benchmarking Checklist that begins:
I found this striking because I took it to be an obvious reference Michael A. Jackson's advice in his brilliant 1975 book Principles of Program Design. Jackson said:
The intent of the two passages is completely different. Hanson and Crain are offering advice about what to optimize. “Don't do it” means that to make a program run faster, eliminate some of the things it does. “Do it, but don't do it again” means that to make a program run faster, have it avoid repeating work it has already done, say by caching results. And so on. Jackson's advice is of a very different nature. It is only indirectly about improving the program's behavior. Instead it is addressing the programmer's behavior: stop trying to optimize all the damn time! It is not about what to optimize but whether, and Jackson says that to a first approximation, the answer is no. Here are Jackson's rules with more complete context. The quotation is from the preface (page vii) and is discussing the style of the examples in his book:
Here's some code I dealt with this month:
Holy cow, this is wrong in so many ways. 8 lines of this mess, for
what? To cache a single database lookup (the
I was able to do a bit better than this, and replaced the code with:
My first thought was that the original caching code had been written by a very inexperienced programmer, someone who with more maturity might learn to do their job with less wasted effort. I was wrong; it had been written by a senior developer, someone who with more maturity might learn to do their job with less wasted effort. The tragedy did not end there. Two years after the original code was written a more junior programmer duplicated the same unnecessary code elsewhere in the same module, saying:
Thus is the iniquity of the fathers visited on the children. In a nearby piece of code, an object A, on the first call to a certain method, constructed object B and cached it:
Then on subsequent calls, it reused B from the cache. But the cache was shared among many instances of A, not all of which
had the same Brendan Gregg is unusually clever, and an exceptional case. Most programmers are not Brendan Gregg, and should take Jackson's advice and stop trying to be so clever all the time. [Other articles in category /prog] permanent link Mon, 18 Jun 2018Yesterday I presented as a counterexample the topology induced by the following metric: I asked:
Several Gentle Readers have written in to tell me that that this metric is variously known as the British Rail metric, French Metro metric, or SNCF metric. (SNCF = Société nationale des chemins de fer français, the French national railway company). In all cases the conceit is the same (up to isomorphism): to travel to a destination on another railway line one must change trains in London / Paris, where all the lines converge. Wikipedia claims this is called the post office metric, again I suppose because all the mail comes to the central post office for sorting. I have not seen it called the FedEx metric, but it could have been, with the center of the disc in Memphis. [ Addendum 20180621: Thanks for Brent Yorgey for correcting my claim that the FedEx super hub is in Nashville. It is in Memphis ] [Other articles in category /math] permanent link Sun, 17 Jun 2018
Bounded does not imply totally bounded
I somehow managed to miss the notion of totally bounded when I was learning topology, and it popped up on stack exchange recently. It is a stronger version of boundedness for metric spaces: a space !!M!! is totally bounded if, for any chosen !!\epsilon!!, !!M!! can be covered by a finite family of balls of radius !!\epsilon!!. This is a strictly stronger property than ordinary boundedness, so the question immediately comes up: what is an example of a space that is bounded but not totally bounded. Many examples are well-known. For example, the infinite-dimensional unit ball is bounded but not totally bounded. But I didn't think of this right away. Instead I thought of the following rather odd example: Let !!S!! be the closed unit disc and assign each point a polar coordinate !!\langle r,\theta\rangle!! as usual. Now consider the following metric: $$ d(\langle r_1, \theta_1\rangle, \langle r_2, \theta_2\rangle) = \begin{cases} r_1, & \qquad \text{ if $r_2 = 0$} \\ \lvert r_1 - r_2 \rvert, & \qquad\text{ if $\theta_1 = \theta_2$} \\ r_1 + r_2 & \qquad\text{ otherwise} \\ \end{cases} $$ The idea is this: you can travel between points only along the radii of the disc. To get from !!p_1!! to !!p_2!! that are on different radii, you must go through the origin: Now clearly when !!\epsilon < \frac12!!, the !!\epsilon!!-ball that covers each point point !!\left\langle 1, \theta\right\rangle!! lies entirely within one of the radii, and so an uncountable number of such balls are required to cover the disc. It seems like this example could be useful in other circumstances too. Does it have a name? [ Addendum 2018-07-18: Several Gentle Readers have informed me that this metric has not just one name, but several. ] [Other articles in category /math] permanent link Mon, 21 May 2018
More about disabling standard I/O buffering
In yesterday's article I described a simple and useful feature that could have been added to the standard I/O library, to allow an environment variable to override the default buffering behavior. This would allow the invoker of a program to request that the program change its buffering behavior even if the program itself didn't provide an option specifically for doing that. Simon Tatham directed me to the GNU Coreutils Roderick Schertler pointed out that Dan Bernstein wrote a utility
program, A later version of
Leonardo Taccari informed me that NetBSD's
Here's the discussion from the NetBSD Finally, Mariusz Ceier pointed out that there is an ancient bug report in
Thank you, Gentle Readers! [Other articles in category /Unix] permanent link Sun, 20 May 2018
Proposal for turning off standard I/O buffering
Some Unix commands, such as Maybe I should explain the putative use case here. You have some
command (or pipeline)
or
then the dribbles are buffered and only come out of Note that adding the One could imagine a program which would interpose a pseudo-tty, and
make
or whatever, one would do
which allocates a pseudo-tty device, attaches standard output to it,
and forks. The child runs
I don't think such a program exists, and anyway, this is all
ridiculous, a ridiculous abuse of the standard I/O library's buffering
behavior: we want line buffering, the library will only give it to us
if the process is attached to a TTY device, so we fake up a TTY just
to fool But it could easily expose this behavior as a controllable feature. Currently there is a branch in the library that says how to set up a buffering mode when a stream is opened for the first time:
To this, I propose a simple change, to be inserted right at the beginning:
Now instead of this:
you write this:
Problem solved. Or maybe you would like to do this:
which then it affects every program in every pipeline in the rest of the session:
Control is global if you want it, and per-process if you want it. This feature would cost around 20 lines of C code in the standard I/O
library and would impose only an insigificant run-time cost. It would
effectively add an Programming languages would all get this for free also. Python
already has
This proposal would fix every programming language everywhere. The Perl code would become:
and every other language would be similarly simple:
[ Addendum 20180521: Mariusz Ceier corrects me, pointing out that this will not work for the process’ own standard streams, as they are pre-opened before the process gets a chance to set the variable. ] It's easy to think of elaborations on this: This is an easy thing to do. I have wanted this for twenty years. How is it possible that it hasn't been in the GNU/Linux standard library for that long? [ Addendum 20180521: it turns out there is quite a lot to say about the state of the art here. In particular, NetBSD has the feature very much as I described it. ] [Other articles in category /Unix] permanent link Mon, 07 May 2018
Katara constructs finite projective planes
This weekend I got a very exciting text message from Katara: I have a math question for you Oh boy! I hope it's one I can answer.
there's this game called spot it where you have cards with 8 symbols on them like so Well, whatever my failings as a dad, this is one problem I can solve. I went a little of overboard in my reply:
ah thank you, I'm pretty sure I understand, sorry for not responding, my phone was charging I still couldn't shut up about the finite projective planes:
Katara was very patient: I guess, I would like to talk about this some more when i get home if that's okay
Anyway this evening I cut up some index cards, and found a bunch of stickers in a drawer, and made Katara a projective plane of order 3. This has 13 cards, each with 4 different stickers, and again, every two cards share exactly one sticker. She was very pleased and wanted to know how to make them herself. Each set of cards has an order, which is a non-negative integer. Then there must be !!n^2 + n + 1!! cards, each with !!n+1!! stickers or symbols. When !!n!! is a prime power, you can use field theory to construct a set of cards from the structure of the (unique) field of order !!n!!. Fields to projective planesOrder 2I'll describe the procedure using the plane of order !!n=2!!, which is unusually simple. There will be !!2^2+2+1 = 7!! cards, each with !!3!! of the !!7!! symbols. Here is the finite field of order 2, called !!GF(2)!!:
Okay, well, that was simple. Larger orderAfter Katara did the order 2 case, which has 7 cards, each with 3 of the 7 kinds of stickers, she was ready to move on to something bigger. I had already done the order 3 deck so she decided to do order 4. This has !!4^2+4+1 = 21!! cards each with 5 of the 21 kinds of stickers. The arithmetic is more complicated too; it's !!GF(2^2)!! instead of !!GF(2)!!:
When the order !!n!! is larger than 2, there is another wrinkle. There are !!4^3 = 64!! possible triples, and we are throwing away !!\langle 0,0,0\rangle!! as usual, so we have 63. But we need !!4^2+4+1 = 21!!, not !!63!!. Each sticker is represented not by one triple, but by three. The triples !!\langle a,b,c\rangle, \langle 2a,2b,2c\rangle,!! and !!\langle 3a,3b,3c\rangle!! must be understood to represent the same sticker, all the multiplications being done according to the table above. Then each group of three triples corresponds to a sticker, and we have 21 as we wanted. Each triple must have a leftmost non-zero entry, and in each group of three similar triples, there will be one where this leftmost non-zero entry is a !!1!!; we will take this as the canonical representative of its class, and it can wear a costume or a disguise that makes it appear to begin with a !!2!! or a !!3!!. We might assign stickers to triples like this: $$ \begin{array}{rl} \cancel{\langle 0,0,0\rangle} & \\ \langle 0,0,1 \rangle & \text{apple} \\ \hline \langle 0,1,0 \rangle & \text{bicycle} \\ \langle 0,1,1 \rangle & \text{carrot} \\ \langle 0,1,2 \rangle & \text{dice} \\ \langle 0,1,3 \rangle & \text{elephant} \\ \hline \langle 1,0,0 \rangle & \text{frog} \\ \langle 1,0,1 \rangle & \text{goat} \\ \langle 1,0,2 \rangle & \text{hat} \\ \langle 1,0,3 \rangle & \text{igloo} \\ \langle 1,1,0 \rangle & \text{jellyfish} \\ \langle 1,1,1 \rangle & \text{kite} \\ \langle 1,1,2 \rangle & \text{ladybug} \\ \langle 1,1,3 \rangle & \text{mermaid} \\ \langle 1,2,0 \rangle & \text{nose} \\ \langle 1,2,1 \rangle & \text{octopus} \\ \langle 1,2,2 \rangle & \text{piano} \\ \langle 1,2,3 \rangle & \text{queen} \\ \langle 1,3,0 \rangle & \text{rainbow} \\ \langle 1,3,1 \rangle & \text{shoe} \\ \langle 1,3,2 \rangle & \text{trombone} \\ \langle 1,3,3 \rangle & \text{umbrella} \\ \end{array} $$ We can stop there, because everything after !!\langle 1,3,3 \rangle!! begins with a !!2!! or a !!3!!, and so is some other triple in disguise. For example what sticker goes with !!\langle 0,2,3 \rangle!!? That's actually !!\langle 0,1,2 \rangle!! in disguise, it's !!2·\langle 0,1,2 \rangle!!, which is “dice”. Okay, how about !!\langle 3,3,1 \rangle!!? That's the same as !!3\cdot\langle 1,1,2 \rangle!!, which is “ladybug”. There are !!21!!, as we wanted. Note that the !!21!! naturally breaks down as !!1+4+4^2!!, depending on how many zeroes are at the beginning; that's where that comes from. Now, just like before, to make a card, we pick two triples that have not yet gone together, say !!\langle 0,0,1 \rangle!! and !!\langle 0,1,0 \rangle!!. We start adding these together as before, obtaining !!\langle 0,1,1 \rangle!!. But we must also add together the disguised versions of these triples, !!\langle 0,0,2 \rangle!! and !!\langle 0,0,3 \rangle!! for the first, and !!\langle 0,2,0 \rangle!! and !! \langle 0,3,0 \rangle!! for the second. This gets us two additional sums, !!\langle 0,2,3 \rangle!!, which is !!\langle 0,1,2 \rangle!! in disguise, and !!\langle 0,3,2 \rangle!!, which is !!\langle 0,1,3 \rangle!! in disguise. It might seem like it also gets us !!\langle 0,2,2 \rangle!! and !!\langle 0,3,3 \rangle!!, but these are just !!\langle 0,1,1 \rangle!! again, in disguise. Since there are three disguises for !!\langle 0,0,1 \rangle!! and three for !!\langle 0,1,0 \rangle!!, we have nine possible sums, but it turns out the the nine sums are only three different triples, each in three different disguises. So our nine sums get us three additional triples, and, including the two we started with, that makes five, which is exactly how many we need for the first card. The first card gets the stickers for triples !!\langle 0,0,1 \rangle, \langle 0,1,0 \rangle \langle 0,1,1 \rangle \langle 0,1,2 \rangle,!! and !!\langle 0,1,3 \rangle,!! which are apple, bicycle, carrot, dice, and elephant. That was anticlimactic. Let's do one more. We don't have a card yet with ladybug and trombone. These are !!\langle 1,1,2 \rangle!! and !!\langle 1,3,2 \rangle!!, and we must add them together, and also the disguised versions: $$\begin{array}{c|ccc} & \langle 1,1,2 \rangle & \langle 2,2,3 \rangle & \langle 3,3,1 \rangle \\ \hline \langle 1,3,2 \rangle & \langle 0,2,0 \rangle & \langle 3,1,1 \rangle & \langle 2,0,3 \rangle \\ \langle 2,1,3 \rangle & \langle 3,0,1 \rangle & \langle 0,3,0 \rangle & \langle 1,2,2 \rangle \\ \langle 3,2,1 \rangle & \langle 2,3,3 \rangle & \langle 1,0,2 \rangle & \langle 0,1,0 \rangle \\ \end{array}$$ These nine results do indeed pick out three triples in three disguises each, and it's easy to select the three of these that are canonical: they have a 1 in the leftmost nonzero position, so the three sums are !!\langle 0,1,0 \rangle,!! !!\langle 1,0,2 \rangle,!! and !!\langle 1,2,2 \rangle!!, which are bicycle, hat, and piano. So the one card that has a ladybug and a trombone also has a bicycle, a hat, and a piano, which should not seem obvious. Note that this card does have the required single overlap with the other card we constructed: both have bicycles. Well, that was fun. Katara did hers with colored dots instead of stickers: The ABCDE card is in the upper left; the bicycle-hat-ladybug-piano-trombone one is the second row from the bottom, second column from the left. The colors look bad in this picture; the light is too yellow and so all the blues and purples look black.x After I took this picture, we checked these cards and found a couple of calculation errors, which we corrected. A correct set of cards is: $$ \begin{array}{ccc} \text{abcde} & \text{bhlpt} & \text{dgmpr} \\ \text{afghi} & \text{bimqu} & \text{dhjou} \\ \text{ajklm} & \text{cfkpu} & \text{diknt} \\ \text{anopq} & \text{cgjqt} & \text{efmot} \\ \text{arstu} & \text{chmns} & \text{eglnu} \\ \text{bfjnr} & \text{cilor} & \text{ehkqr} \\ \text{bgkos} & \text{dflqs} & \text{eijps} \\ \end{array} $$ Fun facts about finite projective planes:
[Other articles in category /math] permanent link Sun, 06 May 2018Last month I regretted making only 22 posts but I promised:
I blew it! I tied the previous volume record. But I also think I did do a decent job promoting the better posts. Usually I look over the previous month's posts and pick out two or three that seem to be of more interest than the others. Not this month! They are all shit, except the one ghostwritten by Anette Gordon-Reed. If this keeps up, I will stop doing these monthly roundup posts.
[Other articles in category /meta/shitpost] permanent link Wed, 02 May 2018
Addenda to recent articles 201804
Thanks to all readers who wrote to me, and also to all readers who did not write to me. [Other articles in category /addenda] permanent link Tue, 01 May 2018
What's in those mysterious cabinets?
Last Monday some folks were working on this thing on Walnut Street. I didn't remember having seen the inside of one before, so I took some pictures of it to look at later. Thanks to the Wonders of the Internet, it didn't take long to figure out what it is for. It is a controller for the traffic lights at the intersection. In particular, the top module in the right-hand picture is a Model 170 ATC HC11 Controller manufactured by McCain Inc, a thirty-year old manufacturer of traffic control devices. The controller runs software developed and supported by McCain, and the cabinet is also made by McCain. The descriptions of the controllers are written in a dense traffic control jargon that I find fascinating but opaque. For example, the 170 controller's product description reads:
I think I understand what variable message signs are, and I can guess at changeable lane control, but what are the sprinklers and pumps for? What is ramp metering? [ Addendum 20180502: readers explain ] The eight-phase dual ring intersection, which I had never heard of before, is an important topic in the traffic control world. I gather that it is a four-way intersection with a four-way traffic light that also has a left-turn-only green arrow portion. The eight “phases” refer to different traffic paths through the intersections that must be separately controlled: even numbers for the four paths through the intersection, and odd numbers 1,3,5,7 for the left-turn-only paths that do not pass through. Some phases conflict; for example phase 5 (left-turning in some direction, say from south to east), conflicts with phase 6 (through-passing heading in the opposite direction) but not with phase 1 (left-turning from north to west). There's plenty of detailed information about this available. For example, the U.S. Federal Highway Administration publishes their Traffic Signal Timing Manual. (Published in 2008, it has since been superseded.) Unfortunately, this seems to be too advanced for me! Section 4.2.1 (“Definitions and Terminology”) is the first place in the document that mentions the dual-ring layout, and it does so without explanation — apparently this is so elementary that anyone reading the Traffic Signal Timing Manual will already be familiar with it:
But these helpful notes explain in more detail: a “ring” is “a sequence of phases that are not compatible and that must time sequentially”. Then we measure the demand for each phase, and there is an interesting and complex design problem: how long should each phase last to optimize traffic flow through the intersection for safety and efficiency? See chapter 3a for more details of how this is done. I love when I discover there is an entire technical domain that I never even suspected existed. If you like this kind of thing, you may enjoy geeking out over the Manual of Uniform Traffic Control Devices, which explains what traffic signs should look like and what each one means. Have you ever noticed that the green guide signs on the highway have up-pointing and down-pointing arrows that are totally different shapes? That's because they have different meanings: the up-pointing arrows mean “go this way” and the down-pointing arrows mean “use this lane”. The MUTCD says what the arrows should look like, how big they should be, and when each one should be used. The MUTCD is the source of one of my favorite quotations:
Words to live by! Programmers in particular should keep this in mind when designing error messages. You could spend your life studying this 864-page manual, and I think some people do. Related geekery: Geometric highway design: how sharply can the Interstate curve and still be safe, and how much do the curves need to be banked? How do you design an interchange between two major highways? How about a highway exit? Here's a highway off-ramp, exit 346A on Pennsylvania I-76 West: Did you know that the long pointy triangle thing is called a “gore”? What happens if you can't make up your mind whether to stay on the highway or take the exit, you drive over the gore, and then smack into the thing beyond it where the roads divides? Well, you might survive, because there is a thing there that is designed to crush when you hit it. It might be a QuadGuard Elite Crash Cushion System, manufactured by Energy Absorption Systems, Inc.. It's such a big world out there, so much to know. [Other articles in category /tech] permanent link Sun, 29 Apr 2018In August 2011, on a particular famous discussion forum (brought up on this blog again and again) an individual A, notorious for such acts, posts a quasi-philosophical inquiry, incurring unpopularity, antagonism, and many bad marks, although also a surprising quantity of rational discussion, including a thoughtful solution or two. Many months forward, a distinct party B puts up a substantial bounty on this inquiry, saying:
(My apology for any anguish you may go through at this point in my story on account of this quotation and its obvious and blatant faults. My wrongdoing was involuntary, but I had no way to avoid it and still maintain full accuracy.) By and by, a valiant third individual constructs a brilliant disquisition satisfying this surprising condition and thus obtains B's award. Now, this month, in our group's accompanying policy board, a fourth collaborator, a guy (or gal, for all I know) I shall call D, and who I think may lack a minimal inclination for fun, finds fault with A's original post and particularly with C's bounty, and complains as follows:
(Again, I must ask you for absolution. This is a word-for-word quotation.) A thorough dismissal of OP's complaint, from a fifth author, adds a fully satisfactory finish to our affair. [Other articles in category /lang] permanent link Fri, 20 Apr 2018Here is a list of March's shitposts. I don't recall what my excuse was for there being only 22, but in my defense, I will add that they were almost all terrible. There was one decent math post I maybe should have promoted. (And also Nancy and Squid, which was awesome, and also 100% Grade A shitpost. I thought when I posted it a crowd of people would burst into the room and carry me off on their shoulders. Instead, nobody seems to have noticed.) April will be better; I'm on pace to break the previous volume record, and I've also been doing a good job of promoting better posts to the major leagues.
[Other articles in category /meta/shitpost] permanent link Thu, 19 Apr 2018
Soldier fly protein: why so expensive?
There have been recurring news stories about the use of dried maggots as protein supplement in animal feed. For example Insects could feed the animals of tomorrow’s meat industry (maggots fed on slaughterhouse waste, particularly blood) or Insect farms gear up to feed soaring global protein demand (maggots fed on rotten fruit). Then they dry the larvae and either use them whole or grind them into meal. In particular the fly meal can be used as a replacement for fish meal, which is ground dried fish that is used as feed for fish in fish farms. (Yep, we grind up fish we don't like, to feed to other, better fish.) I was referred to that second article by Metafilter and The Google, in its infinite wisdom, decided to show me an advertisement for dried fly larvae. The ad was for NaturesPeck, which sells bagged fly larvae and fly meal for use as poultry feed or wild bird feed. They have a special “value pack” that contains 16 pounds of dried larvae for $88. That is $5.50 a pound! Holy cow, WTF? How can that even be possible when my local grocery store is selling boneless center cut pork chops for $2.50 per pound? Okay, I thought maybe NaturesPeck was some sort of boutique operation, charging a high markup for small quantities, maybe they claim to have sustainably-harvested fly meal from free-range organically-fed flies or something. So I went looking for an industrial wholesaler of bulk fly meal and quickly found Haocheng Mealworms Inc. in Xiangtan, China. This is definitely what I was looking for; they will be glad to sell you a standard 40-foot shipping container full of dried maggots or other larvae. The quoted price for dried mealworm larvae is $8400 per metric tonne, plus shipping ($170–200 per tonne). Prices, converted to U.S. dollars per pound, are as follows:
So it wasn't just that NaturesPeck was marking them up. Even the least expensive product costs as much as retail pork chops. I don't get it. There must be some important aspect of this that I am missing, because a market failure of this magnitude is impossible. BTW, Haocheng recommends that:
Not at those prices, buddy. [ Addendum 20180502: Some possible explanations ] [Other articles in category /food] permanent link Wed, 18 Apr 2018
Lower mathematics solves an easy problem
[ Warning: this article is mathematically uninteresting. ] I woke up in the middle of the night last night and while I was waiting to go back to sleep, I browsed math Stack Exchange. At four in the morning I am not at my best, but sometimes I can learn something and sometimes I can even contribute. The question that grabbed my attention this time was Arithmetic sequence where every term is prime?. OP wants to know if the arithmetic sequence $$d\mapsto a+d b$$ contains composite elements for every fixed positive integers !!a,b!!. Now of course the answer is yes, or the counterexample would give us a quick and simple method for constructing prime numbers, and finding such has been an open problem for thousands of years. OP was certainly aware of this, but had not been able to find a simple proof. Their searching was confounded by more advanced matters relating to the Green-Tao theorem and such like, which, being more interesting, are much more widely discussed. There are a couple of remarkable things about the answers that were given. First, even though the problem is easy, the first two answers posted were actually wrong, and another (quickly deleted) was so complicated that I couldn't tell if it was right or not. One user immediately commented:
which is very much to the point; when !!d=a!! then the element of the sequence is !!a+ab!! which is necessarily composite… …unless !!a=1!!. So the comment does not quite take care of the whole question. A second user posted an answer with this same omission, and had to correct it later. I might not have picked up on this case either, during the daytime. But at 4 AM I was not immediately certain that !!a+ab!! was composite and I think about it. I factored it to get !!a(1+b)!! and then I saw that if !!a=1!! or !!1+b=1!! then we lose. (!!1+b=1!! is impossible. !!a+ab!! might of course be composite even if !!a=1!!, but further argumentation is needed.) So I did pick up on this, and gave a complete answer, of which the important part is:
Okay, fine. But OP asked how I came up with that and if it was pure “insight”, so I thought I'd try to reconstruct how I got there at 4 AM. The problem is simple enough that I think I can remember most of how I got to the answer. As I've mentioned before, I am not a pure insight kind of person. While better mathematicians are flitting swiftly from peak to peak, I plod along in the dark and gloomy valleys. I did not get !!d=kb+k+a!! in a brilliant flash of inspiration. Instead, my thought process, as well as I can remember it, went like this:
I should cut in at this point to add that my thinking was nowhere near this articulate or even verbal. The thing about the sequence hitting all the residue classes was more like a feeling in my body, like when I am recognizing a familiar place. When !!a!! and !!b!! are relatively prime, that means that when you are taking steps of size !!b!!, you hit all the !!a!!'s and don't skip any; that's what relatively prime is all about. So maybe that counts as “insight”? Or “intuition about relative primality”? I think that description makes it sound much more impressive than it really is. I do not want a lot of credit for this. Maybe a better way to describe it is that I had been in this familiar place many times before, and I recognized it again. Anyway I continued something like this:
That was good enough for me; I did not even consider the next hit, !!45!!, perhaps because that number was too big for me to calculate at that moment. I didn't use the phrase “residue class” either. That's just my verbal translation of my 4AM nonverbal thinking. At the time it was more like: there are some good things to hit and some bad ones, and the good ones are evenly spaced out, so if we hit each position in the even spacing-ness we must periodically hit some of the good things.
Then I posted the answer, saying that when !!a=1!! you take !!d=1+k(1+b)!! and the sequence element is !!1+b+kb+kb^2 = (1+b)(1+kb)!!. Then I realized that I had the same feeling in my body even when !!a≠1!!, because it only depended on the way the residue classes repeated, and changing !!a!! doesn't affect that, it just slides everything left or right by a constant amount. So I went back to edit the !!1+k(1+b)!! to be !!a+k(1+b)!! instead. I have no particular conclusion to draw about this. [Other articles in category /math] permanent link Mon, 16 Apr 2018
A familiar set with an unexpected order type
I dreamed this one up in high school and I recommend it as an exercise for kids at an appropriate level. Consider the set of all Roman numerals $${ \text{I}, \text{II}, \text{III}, \text{IV}, \text{V}, \ldots, \text{XIII}, \text{XIV}, \text{XV}, \text{XVI}, \ldots, \\ \text{XXXVIII}, \text{XXXIX}, \text{XL}, \text{XLI}, \ldots, \text{XLIX}, \text{L},\ldots,\\ \text{C}, \ldots , \text{D}, \ldots, \text{M}, \ldots, \text{MM}, \ldots, \text{MMM}, \ldots, \text{MMMM}, \ldots, \text{MMMMM}, \ldots }$$ where we allow an arbitrarily large number of M's on the front, so that every number has a unique representation. For example the number 10,067 is represented by !!\text{MMMMMMMMMMLXVII}!!. Now sort the list into alphabetical order. It is easy to show that it begins with !!\text{C}, \text{CC}, \text{CCC}, \text{CCCD}, \ldots!! and ends !!\text{XXXVII}, \text{XXXVIII}!!. But it's still an infinite list! Instead of being infinite at one end or the other, or even both, like most infinite lists, it's infinite in the middle. Of course once you have the idea it's easy to think of more examples (!!\left\{ \frac1n\mid n\in\Bbb Z, n\ne 0\right\}!! for instance) but I hadn't seen anything like this before and I was quite pleased. [Other articles in category /math] permanent link Sun, 15 Apr 2018
On the smallest natural number
The earliest known mathematics book printed in Europe is an untitled arithmetic text published in Treviso in 1478, Originally written in Venetian dialect. The Treviso Arithmetic states unequivocally:
And a little later:
(English translations are from David Eugene Smith, A Source Book in Mathematics (1959). A complete translation appears in Frank J. Swetz, Capitalism and Arithmetic The New Math of the Fifteenth Century (1987).) By the way, today is the 311th birthday of Leonhard Euler. [Other articles in category /math] permanent link Sat, 14 Apr 2018
Colored blobs on electric wires
The high-voltage power lines run along the New Jersey Turnpike for a long way, and there is this one short stretch of road where the wires have red, white, and yellow blobs on them. Google's Street View shot shows them quite clearly.
A thousand feet or so farther down the road, no more blobs. I did Internet searches to find out what the blobs were about, and everyone seemed to agree that they were to make the wires more visible to low-flying aircraft. Which seemed reasonable, but puzzling, because as far as I knew there was no airport in the vicinity. And anyway, why blobs only on that one short stretch of wire? Last week I drove Katara up to New York and when I saw the blobs coming I asked her to photograph them and email me the pictures. She did, and as I hoped, there in the EXIF data in the images was the exact location at which the pictures had been taken: !!(40.2106, -74.57726675)!!. I handed the coordinates to Google and it gave me the answer to my question: The wires with blobs are exactly in line with the runway of nearby Trenton-Robbinsville Airport. Mystery solved! (It is not surprising that I didn't guess this. I had no idea there was a nearby airport. Trenton itself is about ten miles west of there, and its main airport, Trenton-Mercer Airport, is another five miles beyond that.) I have been wondering for years why those blobs were in that exact place, and I am really glad to have it cleared up. Thank you, Google! Dear vision-impaired readers: I wanted to add a description of the
view in the iframed Google Street View picture above. Iframes do not
support an
(The image is a wide-angle shot of a view of the right-hand shoulder of
a highway. There is a low chain-link fence in the foreground, and an
autumnal landscape behind. The sky is blue but partly obscured by
clouds. A high-voltage power pylon is visible at far left and several
sets of wires go from it rightward across the whole top of the
picture, reaching the top right-hand corner. On the upper sets of
wires are evenly-spaced colored balls in orange-red, yellow, and
white. Rotating the street view reveals more colored balls,
stretching into the distance, but only to the north. To the south
there is an overpass, and beyond the overpass the wires continue with
no balls.)
In the future, is there a better place to put a description of an iframed image? Thanks. [Other articles in category /tech] permanent link Fri, 13 Apr 2018As an undergraduate I wondered and wondered about how manifolds and things are classified in algebraic topology, but I couldn't find any way into the subject. All the presentations I found were too abstract and I never came out of it with any concrete idea of how you would actually calculate any specific fundamental groups. I knew that the fundamental group of the circle was !!\Bbb Z!! and the group of the torus was !!\Bbb Z^2!! and I understood basically why, but I didn't know how you would figure this out without geometric intuition. This was fixed for me in the very last undergrad math class I took, at Columbia University with Johan Tysk. That was the lowest point of my adult life, but the algebraic topology was the one bright spot in it. I don't know what might have happened to me if I hadn't had that class to sustain my spirit. And I learned how to calculate homotopy groups! (We used Professor Tysk's course notes, supplemented by William Massey's introduction to algebraic topology. I didn't buy a copy of Massey and I haven't read it all, but I think I can recommend it for this purpose. The parts I have read seemed clear and direct.) Anyway there things stood for a long time. Over the next few decades I made a couple of superficial attempts to find out about homology groups, but again the presentations were too abstract. I had been told that the homology approach was preferred to the homotopy approach because the groups were easier to actually calculate. But none of the sources I found seemed to tell me how to actually calculate anything concrete. Then a few days ago I was in the coffee shop working on a geometry problem involving an icosi-dodecahedron, and the woman next to me asked me what I was doing. Usually when someone asks me this in a coffee shop, they do not want to hear the answer, and I do not want to give it, because if I do their eyes will glaze over and then they will make some comment that I have heard before and do not want to hear again. But it transpired that this woman was a math postdoc at Penn, and an algebraic topologist, so I could launch into an explanation of what I was doing, comfortable in the knowledge that if I said something she didn't understand she would just stop me and ask a question. Yay, fun! Her research is in “persistent homology”, which I had never heard of. So I looked that up and didn't get very far, also because I still didn't know anything about homology. (Also, as she says, the Wikipedia article is kinda crappy.) But I ran into her again a couple of days later and she explained the persistent part, and I know enough about what homology is that the explanation made sense. Her research involves actually calculating actual homology groups of actual manifolds on an actual computer, so I was inspired to take another crack at understanding homology groups. I did a couple of web searches and when I searched for “betti number tutorial” I hit paydirt: these notes titled “persistent homology tutorial” by Xiaojin Zhu of the University of Wisconsin at Madison. They're only 37 slides long, and I could skip the first 15. Then slide 23 gives the magic key. Okay! I have not yet calculated any actual homology groups, so this post might be premature, but I expect I'll finish the slides in a couple of days and try my hand at the calculations and be more or less successful. And the instructions seem clear enough that I can imagine implementing a computer algorithm to calculate the homology groups for a big ugly complex, as this math postdoc does. I had heard before that the advantage of the homology approach over the homotopy approach is that the homologies are easier to actually calculate with, and now I see why. I could have programmed a computer to do homotopy group calculations, but the output would in general have been some quotient of a free group given by a group presentation, and this is basically useless as far as further computation goes. For example the question of whether two differently-presented groups are isomorphic is undecidable, and I think similar sorts of questions, such as whether the group is abelian, or whether it is infinite, are similarly undecidable. Sometimes you get a nice group, but usually you don't. For example the homotopy group of the Klein bottle is the quotient of the free group on two generators under the smallest equivalence relation in which !!aba = b!!; that is: $$\langle a, b\mid abab^{-1}\rangle$$ which is not anything I have seen in any other context. Even the question of whether two given group elements are equal is in general undecidable. So you get an answer, but then you can't actually do anything with it once you have it. (“You're in a balloon!”) The homology approach throws away a lot of information, enough to render the results comprehensible, but it also leaves enough to do something with. [Other articles in category /math] permanent link Tue, 10 Apr 2018
Inconceivable things and non-contingent facts
Philosophy makes a distinguish between necessary and contingent facts, but I'm not exactly sure what it is. I think they would say that the election of Al Gore in 2000 is contingent because it's easy to imagine a universe in which it went the other way and the other guy won. But that seems to depend on our powers of imagination, which doesn't seem very rigorous. Is the mass of the electron necessary or contingent? What about the fine-structure constant? What facts are necessary? Often in this context people fall back on mathematical truths, for example !!1+1=2!!, which does seem hard to assail. But I recently thought of something even farther down the scale, which seems to me even harder to argue. Mathematics deals with many sorts of objects which are more or less like the ordinary numbers. Some are more complicated, and ordinary numbers are special cases, for example functions and matrices. Some are simpler, and are special cases themselves. Mathematicians can and do define !!2!! in many different ways. There are mathematical systems with !!1!! and !!+!! in which there is no !!2!!, and instead of !!1+1=2!! we have !!1+1=0!!. Well, not quite; there is !!2!!, but !!2=0!!. So one can say that !!1+1=2!! still, but the !!2!! is not very much like the !!2!! that we usually mean when we say !!1+1=2!!. Anyway certainly there is such a system, and I can certainly conceive of it, so there might be a philosophical argument that could be made that !!1+1=2!! is a contingent fact about how numbers happen to work in the universe in which we happen to find ourselves: we are not living in a universe where numbers form a field of characteristic 2. But here's a fact that I think is unassailably necessary: rubies are red. Why? By definition! A ruby is a kind of gemstone, a type of aluminum oxide called a corundum, that has a deep red color. There are non-red corundums, but they are sapphires, not rubies, because a ruby is a red corundum. There is no such thing as a blue or a green ruby; a blue or green ruby is not a ruby at all, but a sapphire. How about over in Narnia, where rubies are blue? Well, maybe the Narnians people call hats “avocadoes”, but whether those things are hats or avocadoes depends not on what the Narnians call them but on their properties. If those things are made of felt and the Narnians wear them on their heads, they are hats, regardless of what the Narnians call them; they are avocadoes only if they are globular and can be eaten on toast. Narnians might put actual avocadoes on their heads and then there might be an argument that these things were hats, but if the avocado is a hat it is only because it is customarily worn on the head. And so too the Narnians can call !!2!! an avocado and say that !!1+1=\text{avocado}!! but that doesn't mean that !!1+1!! is an avocado, even in Narnia. Maybe the Narnians call avocadoes “rubies”, but they're still avocadoes, not rubies. And maybe the Narnians call blue corundums “rubies”, but they're still sapphires, not rubies, because rubies are red. So I think it might be conceivable that !!1+1=2!! is contingent, and it's certainly easy to conceive of a universe with no rubies at all, but I can't conceive of any way that a ruby could be other than red. [Other articles in category /misc/philosophy] permanent link Wed, 04 Apr 2018
Genealogy of the Saudi royal family
[ Note: None of this is a joke, nothing here is intended humorously, and certainly none of it should be taken as mockery or disparagement. The naming conventions of Saudi royalty are not for me to judge or criticize, and if they cause problems for me, the problems are my own. It is, however, a serious lament. ] The following innocuous claim appears in Wikipedia's article on Abdullah bin Abdul-Rahman:
Yesterday I tried to verify this claim and I was not able to do it. Somewhere there must be a complete and authoritative pedigree of the entire Saudi royal family, but I could not find it online, perhaps because it is very big. There is a Saudi royal family official web site, and when I found that it does have a page about the family tree, I rejoiced, thinking my search was over. But the tree only lists the descendants of King Abdulaziz Ibn Saud, founder of the modern Saudi state. Abdullah was his half-brother and does not appear there. Well, no problem, just Google the name, right? Ha! Problem 1: These princes all have at least twenty kids each. No, seriously. The Wikipedia article on Ibn Saud himself lists twenty-one wives and then gives up, ending with an exhausted “Possibly other wives”. There is a separate article on his descendants that lists 72 children of various sexes, and the following section on grandchildren begins:
Problem 2: They reuse many of the names. Because of course they do; if wife #12 wants to name her first son the same as the sixth son of wife #2, why not? They don't live in the same house. So among the children of Ibn Saud there are two Abdullahs (“servant of God”), two Badrs (“full moon”), two Fahds (“leopard”), two each of Majid (“majestic”), Mishari (I dunno), Talal (dunno), and Turki (“handsome”). There are three sons named Khalid (“eternal”). There is a Sa'ad and a Saad, which I think are the exact same name (“success”) as spelled by two different Wikipedia editors. And then they reuse the names intergenerationally. Among Ibn Saud's numerous patrilineal grandsons there are at least six more Fahds, the sons respectively of Mohammed, Badr (the second one), Sultan, Turki (also the second one), Muqrin, and Salman. Abdulaziz Ibn Saud has a grandson also named Abdulaziz, whose name is therefore Abdulaziz bin Talal bin Abdulaziz Al Saud. (The “bin” means “son of”; the feminine form is “bint”.) It appears that the House of Saud does not name sons after their fathers, for which I am grateful. Ibn Saud's father was Abdul Rahman (this is the Abdul Rahman of Abdullah bin Abdul-Rahman, who is the subject of this article. Remember him?) One of Ibn Saud's sons is also Abdul Rahman, I think probably the first one to be born after the death of his grandfather, and at least two of his patrilineal grandsons are also. Problem 3: Romanization of Arabic names is done very inconsistently. I mentioned “Saad” and “Sa'ad” before. I find the name Abdul Rahman spelled variously “Abdul Rahman”, “Abdulrahman”, “Abdul-Rahman”, and “Abd al-Rahman”. This makes text searches difficult and unreliable. (The name, by the way, means "Servant of the gracious one”, referring to God.) Problem 4: None of these people has a surname. Instead they are all patronymics. Ibn Saud has six grandsons named Fahd; how do you tell them apart? No problem, their fathers all have different names, so they are Fahd bin Mohammed, Fahd bin Badr, Fahd bin Sultan, Fahd bin Turki, Fahd bin Muqrin, and Fahd bin Salman. But again this confuses text searches terribly. You can search for “Abdullah bin Abdul-Rahman” but many of the results will be about his descendants Fahd bin Abdullah bin Abdul Rahman, Fahd bin Khalid bin Abdullah bin Abdul Rahman, Fahd bin Muhammad bin Abdullah bin Abdul Rahman, Abdullah bin Bandar bin Abdullah bin Abdul Rahman, Faisal bin Abdullah bin Abdul Rahman, Faisal bin Abdul Rahman bin Abdullah bin Abdul Rahman, etc. In combination with the reuse of the same few names, the result is even more confusing. There is Bandar bin Khalid, and Khalid bin Bandar; Fahad bin Khalid and Khalid bin Fahd. There is Mohammed al Saud (Mohammed of (the house of) Saud) and Mohammed bin Saud (Mohammed the son of Saud). There are grandsons named Saad bin Faisal, Faisal bin Bandar, Bandar bin Sultan, Sultan bin Fahd, Fahd bin Turki, Turki bin Talal, Talal bin Mansour, Mansour bin Mutaib, Mutaib bin Abdullah, and Abdullah bin Saad. I swear I am not making this up. Perhaps Abdullah was the seventh son of Abdul Rahman. Perhaps not. I surrender. [Other articles in category /lang] permanent link Sun, 25 Mar 2018Today I went to see The Death of Stalin. If someone is going to go to the trouble of making a comedy about the death of Stalin, that seems like a worthy attempt, and I will do them the courtesy of going to watch it. At least I can be sure it will not be the same old shit. I was interested to see if it was possible to make a comedy about the death of Stalin, and if so, would it would be funny? I got my answer: no, you can't, and it isn't. It was worth a shot, I guess, and I give the writers and director top marks for audacity. The cast was great. The acting was great. I thought Jason Isaacs as Marshal Zhukov stole every scene he was in. But yeah, it's hard to be funny when Lavrenty Beria is raping a bunch of fourteen-year-old girls, and the movie didn't work for me. There's a long and solid tradition of comedy about completely loathsome people, but I think most of it follows pretty much the same pattern: terrible stuff happens to the loathsome people and it is funny because the people are so loathsome and because they so richly deserve all the terrible stuff that happens to them. It can be fun to see a horrible person sabotage themselves with their own horribleness. (Examples off the top of my head: Fawlty Towers. Otto in A Fish Called Wanda. Jack Vance's Cugel books. Married With Children. I think this might have been the main attraction of Seinfeld, although if it is I didn't get the joke until after the series was over.) Unfortunately this movie, being historical fiction, has to stick to the history: Malenkov gets swept under a rug. Khrushchev seizes power. Molotov keeps on doing what he does. Beria is murdered, but there is nothing funny about it, and I found it unsatisfying. Indeed, all of these horrible people are suffering because of the horrible world they have created for themselves, but I found no fun in it because there were another 170 million people suffering much worse from the same horrible crap. The coyote's look of dismay as he falls of the cliff loses all its savor if he has the road runner's broken body in his jaws when it happens. So, eh. Sorry, Iannucci. I wanted to like your movie. [ Odd trivium: I started writing articles in the “movies” section of this blog back in 2007, but this is the first one that has seen publication. ] [Other articles in category /movie] permanent link Sat, 24 Mar 2018
Addenda to recent articles 201803
It's been a while since we had one of these. But gosh, people have sent me quite a lot of really interesting mail lately.
[Other articles in category /addenda] permanent link Fri, 23 Mar 2018Here is a list of February's shitposts, later than usual, but who cares? Boldface indicates the articles that may (may) be of more general interest (ha). I think that I did a better job of noticing when a post wasn't shitty enough and promoting it, pre-publication, to this blog, so you will have seen all the better stuff already. I'm pleased, volume over January is slightly up, and quality is definitely down, especially in the last half of the month. But I posted on only 21 of 28 days; I'll have to work on that.
[Other articles in category /meta/shitpost] permanent link Thu, 22 Mar 2018
Does Skaði choose the husband with the best butt?
(Warning: I do not know anything about Old Norse, so everything I say about it should be understood as ill-informed speculation. I welcome corrections.) In one of my favorite episodes from Norse mythology, the Æsir owe a payment to the Jötunn Skaði in compensation for killing her father. But they know she is very wealthy, and offer her an alternative compensation: one of their men in marriage. Skaði wants to marry Baldr, because he is extremely handsome. But Baldr is already married. Odin proposes a compromise: the Æsir will line up behind a short curtain, and Skaði will choose her husband. She will marry whomever she picks; if she can pick out Baldr by his legs, she can have him. Skaði agrees, assuming that the beautiful Baldr will have the best legs. (She chooses wrong. Njörðr has the best legs.) Thinking on this as an adult, I said to myself “Aha, this is like that horn full of milk that was actually mead. I bet this was also cleaned up in the version I read, and that in the original material, Skaði was actually choosing the husband with the best butt.” I went to check, and I was wrong. The sources say she was looking only at their feet. I was going to just quote this:
But then I got worried. This is of course not the original source but an English translation; what if it is inaccurate? Well, there was nothing else to do but ask Snorri about it. He says:
(Sætt is recompense or settlement; yfirbætr similarly. (Bætr is a cure, as in “I was sick, but I got better”.) The first (fyrsta) part of the settlement is that she “shall choose a man for herself” (skal kjósa sér mann) but choose by the feet (kjósa at fótum) seeing nothing else (sjá ekki fleira af).) The crucial word here is fótum, which certainly looks like “foot”. (It is the dative form of fótr.) Could it possibly mean the buttocks? I don't think so. It's hard to be 100% certain, because it could be a euphemism — anything could be a euphemism for the buttocks if you paused before saying it and raised one eyebrow. (Did the Norse bards ever do this?) Also the Norse seem to have divided up the leg differently than we do. Many of the words seem to match, which is sometimes helpful but also can be misleading, because many don't. For example, I think leggr, despite its appearance, means just the shank. And I think fótum may not be just the foot itself, but some part of the leg that includes the foot. But I'm pretty sure fótum is not the butt, at least not canonically. To do this right I would look at all the other instances of fótr to see what I could glean from the usage, but I have other work to do today. So anyway, Skaði probably was looking at their feet, and not at their butts. Oh well. However! the other part of Skaði's settlement is that the Æsir must make her laugh. In the version I first read, Loki achieves this by tying his beard to a goat's. Nope!
Skegg geitar nökkurar is indeed some goat's beard. But hann batt … ok öðrum enda um hreðjar sér is “he tied … the other end to his own scrotum”. Useful resources:
[Other articles in category /lang] permanent link Wed, 21 Mar 2018A couple of years ago I was reading Wikipedia's article about the the 1943 Bengal famine, and I was startled by the following claim:
It was cited, but also marked with the “not in citation” tag, which is supposed to mean that someone checked the reference and found that it did not actually support the claim. It sounded like it might be the sort of scurrilous lie that is widely repeated but not actually supportable, so I went to follow it up. It turned out that although the quotation was not quite exact, it was not misleadingly altered, and not a scurrilous lie at all. The attributed source (Tharoor, Shashi "The Ugly Briton". Time, (29 November 2010).) claimed:
I removed the “not in citation” tag, which I felt was very misleading. Still, I felt that anything this shocking should be as well-supported as possible. It cited Tharoor, but Tharoor could have been mistaken. So I put in some effort and dug up the original source. It is from the journal entry of Archibald Wavell, then Viceroy of India, of 5 July 1944:
This appears in the published version of Lord Wavell's journals. (Wavell, Archibald Percival. Wavell: The Viceroy's journal, p. 78. Moon, Penderel, ed. Oxford University Press, 1973.) This is the most reliable testimony one could hope for. The 1973 edition is available from the Internet Archive. A few months later, the entire article was massively overhauled by a group of anglophiles and Churchill-rehabilitators. Having failed to remove the quotation for being uncited, and then having failed to mendaciously discredit the cited source, they removed the quotation in a typical episode of Wikipedia chicanery. In a 5,000-word article, one sentence quoting the views of the then-current British Prime Minister was deemed “undue weight”, and a failure to “fairly represent all significant viewpoints that have been published by reliable sources”. Further reading: In Winston Churchill, Hollywood rewards a mass murderer. (Tharoor again, in last week's Washington Post.) [Other articles in category /wikipedia] permanent link Tue, 20 Mar 2018In English we can sometimes turn an adjective into a verb by suffixing “-en”. For example:
But not
(Note that I am only looking at -en verbs that are adjective-derived present tenses. This post is not concerned with the many -en verbs that are past participles, such as “smitten” (past participle of “smite”), “spoken” (“speak”), “molten” (“melt”), “sodden” (“seethe”), etc.) I asked some linguist about this once and they were sure it was purely morphological, something like: black, red, and white end in stop consonants, and blue, green, and yellow don't. Well, let's see:
There are some fine points:
but clearly the morphological explanation wins. I'm convinced. [ Addendum: Wiktionary discusses this suffix, distinguishing it from the etymologically distinct participial “-en”, and says “it is not currently very productive in forming new words, being mostly restricted to monosyllabic bases which end in an obstruent”. ] [Other articles in category /lang] permanent link Mon, 19 Mar 2018I had a fun idea this morning. As a kid I was really interested in polar coordinates and kind of disappointed that there didn't seem to be any other coordinate systems to tinker with. But this morning I realized there were a lot. Let !!F(c)!! be some parametrized family of curves that partition the plane, or almost all of the plane, say except for a finite number of exceptions. If you have two such families !!F_1(c)!! and !!F_2(c)!!, and if each curve in !!F_1!! intersects each curve in !!F_2!! in exactly one point (again with maybe a few exceptions) then you have a coordinate system: almost every point !!P!! lies on !!F_1(a)!! and !!F_2(b)!! for some unique choice of !!\langle a, b\rangle!!, and these are its coordinates in the !!F_1–F_2!! system. For example, when !!F_1(c)!! is the family of lines !!x=c!! and !!F_2(c)!! is the family of lines !!y=c!! then you get ordinary Cartesian coordinates, and when !!F_1(c)!! is the family of circles !!x^2+y^2=c!! and !!F_2(c)!! is the family !!y=cx!! (plus also !!x=0!!) you get standard polar coordinates, which don't quite work because the origin is in every member of !!F_2!!, but it's the only weird exception. But there are many other families that work. To take a particularly simple example you can pick some constant !!k!! and then take $$\begin{align} F_1(c): && x & =c \\ F_2(c): && y & =kx+c. \end{align} $$ This is like Cartesian coordinates except the axes are skewed. I did know about this when I was a kid but I considered it not sufficiently interesting. For a more interesting example, try $$\begin{align} F_1(c): && x^2-y^2 & =c \\ F_2(c): && xy & =c \end{align} $$ which looks like this: I've seen that illustration before but I don't think I thought of using it as a coordinate system. Well, okay, every pair of hyperbolas intersects in two points, not one. So it's a parametrization of the boundary of real projective space or something, fine. Still fun! In the very nice cases (such as the hyperbolas) each pair of curves is orthogonal at their point of intersection, but that's not a requirement, as with the skew Cartesian system. I'm pretty sure that if you have one family !!F!! you can construct a dual family !!F'!! that is orthogonal to it everywhere by letting !!F'!! be the paths of gradient descent or something. I'm not sure what the orthogonality is going to be important for but I bet it's sometimes useful. You can also mix and match families, so for example take: $$\begin{align} F_1(c): && x & =c \\ F_2(c): && xy & =c \end{align} $$ Some examples work better than others. The !!xy=c!! hyperbolas are kind of a mess when !!c=0!!, and they don't go together with the !!x^2+y^2=c!! circles in the right way at all: each circle intersects each hyperbola in four points. But it occurs to me that as with the projective plane thingy, we don't have to let that be a problem. Take !!S!! to be the quotient space of the plane where two points are identified if their !!F_1–F_2!!-coordinates are the same and then investigate !!S!!. Or maybe go more directly and take !!S = F_1 \times F_2!! (literally the Cartesian product), and then topologize !!S!! in some reasonably natural way. Maybe just give it the product topology. I dunno, I have to think about it. (I was a bit worried about how to draw the hyperbola picture, but I tried Google Image search for “families of orthogonal hyperbolas”, and got just what I needed. Truly, we live in an age of marvels!) [Other articles in category /math] permanent link Mon, 12 Mar 2018
Quick and dirty prime counting
I've been thinking for a while that I probably ought to get around to memorizing all the prime numbers under 1,000, so that I don't have to wonder about things like 893 all the time, and last night in the car I started thinking about it again, and wondered how hard it would be. There are 25 primes under 100, so presumably fewer than 250 under 1,000, which is not excessive. But I wondered if I could get a better estimate. The prime number theorem tells us that the number of primes less than !!n!! is !!O(\frac n{\log n})!! and I think the logarithm is a natural one, but maybe there is some constant factor in there or something, I forget and I did not want to think about it too hard because I was driving. Anyway I cannot do natural logarithms in my head. Be we don't need to do any actual logarithms. Let's estimate the fraction of primes up to !!n!! as !!\frac 1{c\log n}!! where !!c!! is unknown and the base of the logarithm is then unimportant. The denominator scales linearly with the power of !!n!!, so the difference between the denominators for !!n=10!! and !!n=100!! is the same as the difference between the denominators for !!n=100!! and !!n=1000!!. There are 4 primes less than 10, or !!\frac25!!, so the denominator is 2.5. And there are 25 primes less than 100, so the denominator here is 4. The difference is 1.5, so the denominator for !!n=1000!! ought to be around 5.5, and that means that about !!\frac2{11}!! of the numbers up to 1000 are prime. This yields an estimate of 182. I found out later that the correct number is 186, so I felt pretty good about that. [ Addendum: The correct number is 168, not 186, so I wasn't as close as I thought. ] [Other articles in category /math] permanent link Tue, 20 Feb 2018
Composition of utility pole ID tags
In a recent article discussing utility poles, and the metal ID plates they carry, I wondered what the plates were made of:
They are not ferrous. Probably they are aluminum. My idea that aluminum is too expensive to use for the plates was ridiculous. The pole itself costs a lot of money. The sophisticated electrical equipment on the pole costs thousands of dollars. The insulated wire strung from the pole is made of copper. Compared with all this, a ten-centimeter oval of stamped aluminum is not a big deal. 1.8mm aluminum sheet costs $100 per square meter even if you don't buy it in great quantity. Those aluminum tags probably cost no more than fifty cents each. [Other articles in category /oops] permanent link Wed, 14 Feb 2018I am almost always interested in utility infrastructure. I see it every day, and often don't think about it. The electric power distribution grid is a gigantic machine, one of the biggest devices ever built, and people spend their whole lives becoming experts on just one part of it. What is it all for, how does it work? What goes wrong, and how do you fix it? Who makes the parts, and how much do they cost? Every day I go outside and see things like these big cylinders: and I wonder what they are. In this case from clues in the environment I was able to guess they were electrical power transformers. Power is distributed on these poles at about seven thousand volts, which is called “medium voltage”. But you do not want 7000-volt power in your house because it would come squirting out of the electric outlets in awesome lightnings and burn everything up. Also most household uses do not want three-phase power, they want single-phase power. So between the pole and the house there is a transformer to change the shape of the electricity to 120V, and that's what these things are. They turn out to be called “distribution transformers” and they are manufactured by — guess who? — General Electric, and they cost a few thousand bucks each. And because of the Wonders of the Internet, I can find out quite a lot about them. The cans are full of mineral oil, or sometimes vegetable oil! (Why are they full of oil? I don't know; I guess for insulation. But I could probably find out.) There are three because that is one way to change the three-phase power to single-phase, something I wish I understood better. Truly, we live in an age of marvels. Anyway, I was having dinner with a friend recently and for some reason we got to talking about the ID plates on utility poles. The poles around here all carry ID numbers, and I imagine that back at the electric company there are giant books listing, for each pole ID number, where the pole is. Probably they computerized this back in the seventies, and the books are moldering in a closet somewhere. As I discussed recently, some of those poles are a hundred years old, and the style of the ID tags has changed over that time: It looks to me like the original style was those oval plates that you see on the left, and that at some point some of the plates started to wear out and were replaced by the yellow digit tags in the middle picture. The most recent poles don't have tags: the identifier is burnt into the pole. Poles in my neighborhood tend to have consecutive numbers. I don't think this was carefully planned. I guess how this happened is: when they sent the poles out on the truck to be installed, they also sent out a bunch of ID plates, perhaps already attached to the poles, or perhaps to be attached onsite. The plates would already have the numbers on them, and when you grab a bunch of them out of the stack they will naturally tend to have consecutive numbers, as in the pictures above, because that's how they were manufactured. So the poles in a vicinity will tend to have numbers that are close together, until they don't, because at that point the truck had to go back for more poles. So although you might find poles 79518–79604 in my neighborhood, poles 79605–79923 might be in a completely different part of the city. Later on someone was inspecting pole 79557 (middle picture) and noticed that the number plate was wearing out. So they pried it off and replaced it with the yellow digit tag, which is much newer than the pole itself. The inspector will have a bunch of empty frames and a box full of digits, so they put up a new tag with the old ID number. But sometime more recently they switched to these new-style poles with numbers burnt into them at the factory, in a different format than before. I have tried to imagine what the number-burning device looks like, but I'm not at all sure. Is it like a heated printing press, or perhaps a sort of configurable branding iron? Or is it more like a big soldering iron that is on a computer-controlled axis and writes the numbers on like a pen? I wonder what the old plates are made of. They have to last a long time. For a while I was puzzled. Steel would rust; and I thought even stainless steel wouldn't last as long as these tags need to. Aluminum is expensive. Tin degrades at low temperatures. But thanks to the Wonders of the Internet, I have learned that, properly made, stainless steel tags can indeed last long enough; the web site of the British Stainless Steel Association advises me that even in rough conditions, stainless steel with the right composition can last 85 years outdoors. I will do what I should have done in the first place, and go test the tags with a magnet to see if they are ferrous. Here's where some knucklehead in the Streets Department decided to nail a No Parking sign right over the ID tag: Another thing you can see on these poles is inspection tags: Without the Internet I would just have to wonder what these were and what OSMOSE meant. It is the name of the company that PECO has hired to inspect and maintain the poles. They specialize in this kind of work. This old pole was inspected in 2001 and again in 2013. The dated inspection tag from the previous inspection is lost but we can see a pie-shaped tag that says WOODFUME. You may recall from my previous article that the main killer of wood poles is fungal infection. Woodfume is an inexpensive fumigant that retards pole decay. It propagates into the pole and decomposes into MITC (methyl isothiocyanate). By 2001 PECO had switched to using MITC-FUME, which impregnates the pole directly with MITC. Osmose will be glad to tell you all about it. (Warning: Probably at least 30% of the surmise in this article is wrong.) [Other articles in category /tech] permanent link Tue, 13 Feb 2018(If you already know about reservoir sampling, just skip to the good part.) The basic reservoir sampling algorithm asks us to select a random item from a list, easy peasy, except:
Maybe the items are being read from a pipe or some other lazy data structure. There might be zillions of them, so we can't simply load them into an array. Obviously something like this doesn't work:
because it doesn't select the items with equal probability. Far from it! The last item is selected as often as all the preceding items put together. The requirements may seem at first impossible to satisfy, but it can be done and it's not even difficult:
The The good partLast week I thought of a different simple variation. Suppose each item !!s_i!! is presented along with an arbitrary non-negative weight !!w_i!!, measuring the relative likelihood of its being selected for the output. For example, an item with weight 6 should be selected twice as often as an item with weight 3, and three times as often as an item with weight 2. The total weight is !!W = \sum w_i!! and at the end, whenever that is, we want to have selected each item !!s_i!! with probability !!\frac{w_i}{W}!!:
The correctness proof is almost the same. Clearly this reduces to the standard algorithm when all the weights are equal. This isn't a major change, but it seems useful and I hadn't seen it before. [Other articles in category /prog] permanent link Mon, 12 Feb 2018
Philadelphia sports fans behaving badly
Philadelphia sports fans have a bad reputation. For example, we are famous for booing Santa Claus and hitting him with snowballs. I wasn't around for that; it happened in 1968. When the Santa died in 2015, he got an obituary in the Phildelphia Inquirer:
The most famous story of this type is about Ed Rendell (after he was Philadelphia District Attorney, but before he was Mayor) betting a Eagles fan that they could not throw snowballs all the way from their upper-deck seat onto the field. This was originally reported in 1989 by Steve Lopez in the Inquirer. (Lopez's story is a blast. He called up Rendell, who denied the claim, and referred Lopez to a friend who had been there with him. Lopez left a message for the friend. Then Rendell called back to confess. Later Rendell's friend called back to deny the story. Lopez wrote:
A few years later Rendell was elected Mayor of Philadelphia, and later, Governor of Pennsylvania. Anyway, I digress.) I don't attend football games, and baseball games are not held in snowy weather, so we have to find other things to throw on the field. I am too young to remember Bat Day, where each attending ticket-holder was presented with a miniature souvenir baseball bat; that was eliminated long ago because too many bats were thrown at the visiting players. (I do remember when those bats stopped being sold at the concession stands, for the same reason.) Over the years, all the larger and harder premiums were eliminated, one by one, but we are an adaptable people and once, to protest a bad call by the umpire, we delayed the game by wadding up our free promotional sport socks and throwing them onto the field. That was the end of Sock Day. On one memorable occasion, two very fat gentlemen down by the third-base line ran out of patience during an excessively long rain delay and climbed over the fence, ran out and belly-flopped onto the infield, sliding on the wet tarpaulin all the way to the first-base side. Confronted there by security, they evaded capture by turning around and sliding back. These heroes were eventually run down, but only after livening up what had been a very trying evening. The main point of this note is to shore up a less well-known story of this type. I have seen it reported that Phillies fans once booed Miss Pennsylvania, and I have also seen people suggest that this never really happened. On my honor, it did happen. We not only booed Miss Pennsylvania, we booed her for singing the national anthem. I was at that game, in 1993. The Star-Spangled Banner has a lot of problems that the singer must solve one way or another, and there are a lot of ways to interpret it. But it has a melody, and the singer's interpretation is not permitted to stray so far from the standard that they are singing a different song that happens to have the same words. I booed too, and I'm not ashamed to admit it. [Other articles in category /games] permanent link Wed, 07 Feb 2018
The many faces of the Petersen graph
(Actually the Petersen graph cannot really be said to have faces, as it is nonplanar. HA! HA! I MAKE JOKE!!1!) This article was going to be about how GraphViz renders the Petersen graph, but instead it turned out to be about how GraphViz doesn't render the Petersen graph. The GraphViz stuff will be along later. Here we have the Petersen graph, which, according to Donald Knuth, “serves as a counterexample to many optimistic predictions about what might be true for graphs in general.” It is not that the Petersen graph is stubborn! But it marches to the beat of a different drummer. If you have not met it before, prepare to be delighted. This is the basic structure: a blue 5-cycle, and a red 5-cycle. Corresponding vertices in the two cycles are connected by five purple edges. But there is a twist! Notice that the vertices in the red cycle are connected in the order 1–3–5–2–4. There are different ways to lay out the Petersen graph that showcase its many interesting properties. For example, the standard presentation, above, demonstrates that the Petersen graph is nonplanar, since it obviously contracts to !!K_5!!. The presentation below obscures this, but it is good for seeing that the graph has diameter only 2: Wait, what? Where did the pentagons go? Try this instead:
Again the red vertices are connected in the order 1–3–5–2–4. Okay, that is indeed the Petersen graph, but how does it help us see that the graph has diameter 2? Color the nodes by how far down they are from the root:
Looking at the pentagonal version, you would not suspect the Petersen graph of also having a sixfold symmetry, but it does. We'll get there in two steps. Again, here's a version where it's not so easy to see that it's actually the Petersen graph, but whatever it is, it is at least clear that it has an automorphism of order six (give it a one-sixth turn): The represents three vertices, one in each color. In the picture they are superimposed, but in the actual graph, no pair of the three is connected by an edge. Instead, each of the three is connected not to the others but to a tenth vertex that I omitted from the diagram entirely. Let's pull apart the three vertices and reveal the hidden tenth vertex and its three edges:
Here is the same drawing, recolored to match the tree diagram from before; the outer hexagon is just the 6-cycle formed by the six blue leaf nodes: But maybe it's easier to see if we look for red and blue pentagons. There are a couple of ways to do that: As always, the red vertices are connected in the order 1–3–5–2–4. Finally, here's a presentation you don't often see. It demonstrates that the Petersen graph also has fourfold symmetry:
Again, and represent single vertices stretched out into dumbbell shapes. The diagram only shows 14 of the 15 edges; the fifteenth connects the two dumbbells. The pentagons are deeply hidden here. Can you find them? (Spoiler) Even though this article was supposed to be about GraphViz, I found it impossible to get it to render the diagrams I wanted it to, and I had to fall back on Inkscape. Fortunately Inkscape is a ton of fun. [Other articles in category /math] permanent link Thu, 01 Feb 2018As I may have mentioned, I have started another
blog, called Last month I said:
I think I am doing better. I will continue my efforts to emphasize quantity over quality, with a multi-pronged approach:
It will be a struggle, but I resolve to do my best! Here is a list of January's shitposts. Boldface indicates the articles that may (may) be of more general interest (ha). There are fewer of these than last month because I promoted several of the better ones, so you have seen them already.
[Other articles in category /meta/shitpost] permanent link Tue, 30 Jan 2018Sapporo restaurant, on West 49th Street in New York, closed yesterday. There are 24,000 restaurants in New York, and for many, many years, Sapporo was my favorite. Sapporo was a ramen restaurant, probably the first in New York. I remember first hearing the word “ramen” in the early 1980s, when the Larmen Dosanko appeared near Lincoln Center. But Sapporo opened in 1975. I started going there around 1984. I didn't discover it on my own; I think my dad and I happened in one day when we were in the neighborhood. But it made a big impression on me, and I would regularly stop in whenever I was nearby, and sometimes I would walk downtown (about 45 minutes) just to eat there. When I was fifteen years old, I did somethinng fifteen-year-old boys often do: I grew six inches and added thirty pounds in one year. I ate all the time. I spent so much time eating that it wasn't enjoyable any more, and I complained that I was tired of it and didn't have enough time to do anything else. I would come home from school and eat a double-decker sandwich (sliced muenster with mayonnaise was my favorite), half a pound of feta cheese, three yogurts, and whatever leftovers I could find in the fridge, and then two hours later when my parents got home I would ask “What's for dinner? I'm starving.” I fell in love with Sapporo because it was the only restaurant where I could afford to order as much food as I could eat. I would come out of Sapporo full. Sometimes when I left Sapporo there was still some rice or noodles in my bowl, and I would stop thinking about food for an hour or two. On the table were three intriguing bottles, one brown, one pale yellow, and one bright red. The brown one was obviously soy sauce, but what were the others? I learned that the pale yellow one was vinegar and the bright red one was hot oil and had great fun trying them out in different combinations. I had never thought of using vinegar as a condiment, and I loved it. Sapporo was where I first had agedashi dofu, which is delectable cubes of soft tofu, dusted in flour or starch, fried brown and crisp, and served in savory broth. It is ephemeral: you have to eat it right away, before it gets cold and soggy. My favorite dish was the pork cutlet donburi. (They didn't call it “katsudon”; I didn't learn that until later.) The cutlet was embedded, with onions, in a fried egg that coverered and adhered to the top of the rice, and I can still remember how it tasted with the soy sauce and vinegar, and the texture of it. It was tricky to pick up the cutlet, with its attached fried egg, with chopsticks. I now use chopsticks as well as I use a fork, automatically and unconsciously, and I think Sapporo was probably where I learned to do it. Because of Sapporo, I became so enamored of vinegar that I started to put it on everything. I didn't like mustard, I thought, but one day I learned that the principal ingrediant in mustard, other than the mustard itself, was vinegar. This put a new light on things and I immediately decided I had better give mustard another try. I discovered that I did indeed like mustard (like vinegar, but with extra flavor!) and I have liked it ever since. (Around the same time of my life, I was learning about beer, and I eagerly tried Sapporo beer, which they feature, hoping that it would be as wonderful as Sapporo restaurant. I was disappointed.) I deeply regret that I missed my last chance to eat there. I was staying in Midtown with Toph last summer and suggested that we eat dinner there, but she chose to go somewhere else. It didn't occur to me that Sapporo might not always be there, or I would have insisted. Goodbye, Sapporo. I love you and I will miss you. [Other articles in category /food] permanent link Mon, 29 Jan 2018
The rubber duck explains coherence spaces
I've spent a chunk of the past week, at least, trying to understand the idea of a coherence space (or coherent space). This appears in Jean-Yves Girard's Proofs and Types, and it's a model of a data type. For example, the type of integers and the type of booleans can be modeled as coherence spaces. The definition is one of those simple but bafflingly abstract ones that you often meet in mathematics: There is a set !!\lvert \mathcal{A}\rvert!! of tokens, and the points of the coherence space !!\mathcal{A}!! (“cliques”) are sets of tokens. The cliques are required to satisfy two properties:
To beginning math students it often seems like these sorts of definitions are generated at random. Okay, today we're going to study Eulerian preorders with no maximum element that are closed under finite unions; tomorrow we're going to study semispatulated coalgebras with countably infinite signatures and the weak Cosell property. Whatever, man. I have a long article about this in progress, but I'll summarize: they are never generated at random. The properties are carefully chosen because we have something in mind that we are trying to model, and until you understand what that thing is, and why someone thinks those properties are the important ones, you are not going to get anywhere. So when I see something like this I must stop immediately and ask ‘wat’. I can try to come up with the explanation myself, or I can read on hoping for an explanation, or I can do some of each, but I am not going to progress very far until I understand what it is about. And I'm not sure anyone short of Alexander Grothendieck would have any more success trying to move on with the definition itself and nothing else. Girard explains shortly after:
Okay, fine. I understand the point of the project, although not why the definition is what it is. I know a fair amount about types. And Girard has given two examples: booleans and integers. But these examples are unusually simple, because none of the cliques has more than one element, and so the examples are not as illuminating as they might be. Some of the ways I tried to press onward were:
None of this was working. I had several different ideas about what the coherence spaces might look like for other types, but none of them seemed to fit with what Girard was doing. I couldn't come up with any consistent story. So I prepared to ask on StackExchange, and I spent about an hour writing up my question, explaining all the things I had tried and what the problems were with each one. And as I drew near to the end of this, the clouds parted! I never had to post the question. I was in the middle of composing this paragraph:
I decided I hadn't made enough of an effort to understand the direct product. So even though I couldn't see how it could possibly give me anything like what I wanted, I followed its definition for !!{{\mathcal B}ool}^2!! — and the light came on. Here's the puzzling coproduct-like definition of the product of two coherence spaces, from page 61:
That is, the tokens in the product space are literally the disjoint union of the tokens in the component spaces. And the edges in the product's web are whatever they were in !!{\mathcal A}!!'s web (except lifted from !!|{\mathcal A}|!! to !!\{1\}×|{\mathcal A}|!!), whatever they were in !!{\mathcal B}!!'s web (similarly), and also there is an edge between every !!\langle1, {\mathcal A}\rangle!! and each !!\langle2, {\mathcal B}\rangle!!. For !!{{\mathcal B}ool}^2!! the web looks like this: There is no edge between !!\langle 1, \text{True}\rangle!! and !!\langle 1, \text{False}\rangle!! because in !!{{\mathcal B}ool}!! there is no edge between !!\text{True}!! and !!\text{False}!!. This graph has nine cliques. Here they are ordered by set inclusion: (In this second diagram I have abbreviated the pair !!\langle1, \text{True}\rangle!! to just !!1T!!. The top nodes in the diagram are each labeled with a set of two ordered pairs.) What does this mean? The ordered pairs of booleans are being represented by functions. The boolean pair !!\langle x, y\rangle!! is represented by the function that takes as its argument a number, either 1 or 2, and then returns the corresponding component of the pair: the first component !!x!! if the argument was 1, and the second component !!y!! if the argument was 2. The nodes in the bottom diagram represent functions. The top row are fully-defined functions. For example, !!\{1F, 2T\}!! is the function with !!f(1) = \text{False}!! and !!f(2) = \text{True}!!, representing the boolean pair !!\langle\text{False}, \text{True}\rangle!!. Similarly if we were looking at a space of infinite lists, we could consider it a function from !!\Bbb N!! to whatever the type of the lists elements was. Then the top row of nodes in the coherence space would be infinite sets of pairs of the form !!\langle n, \text{(list element)}\rangle!!. The lower nodes are still functions, but they are functions about which we have only incomplete information. The node !!\{2T\}!! is a function for which !!f(2) = \text{True}!!. But we don't yet know what !!f(1)!! is because we haven't yet tried to compute it. And the bottommost node !!\varnothing!! is a function where we don't know anything at all — yet. As we test the function on various arguments, we move up the graph, always following the edges. The lower nodes are approximations to the upper ones, made on the basis of incomplete information about what is higher up. Now the importance of finite approximants on page 56 becomes clearer. !!{{\mathcal B}ool}^2!! is already finite. But in general the space is infinite because the type is functions on an infinite domain, or infinite lists, or something of that sort. In such a space we can't get all the way to the top row of nodes because to do that we would have to call the function on all its possible arguments, or examine every element of the list, which is impossible. Girard says “Above all, there are enough finite approximants to a.” I didn't understand what he meant by “enough”. But what he means is that each clique !!a!! is the union of its finite approximants: each bit of information in the function !!a!! is obtainable from some finite approximation of !!a!!. The “stable functions” of section 8.3 start to become less nebulous also. I had been thinking that the !!\varnothing!! node was somehow like the
!!\bot!! element in a Scott domain, and then I struggled to
identify anything like !!\langle \text{False}, \bot\rangle!!.
It looks at first
like you can do it somehow, because there are the right number of
nodes at the middle level.
Trouble arises in other coherence
spaces. Presented with a value from I think there isn't anything like !!\bot!! or !!W\ \bot!! in the coherence space. Or maybe they they are there but sharing the !!\varnothing!! node. But I think more likely partial objects will appear in some other way. Whew! Now I can move along. (If you don't understand why “rubber duck”, Wikipedia explains:
I spent a week on this but didn't figure it out until I tried formulating my question for StackExchange. The draft question, never completed, is here if for some reason you want to see what it looked like.) [Other articles in category /math/logic] permanent link Thu, 25 Jan 2018For me, a little of Samuel Johnson goes a long way, because he was a tremendous asshole, and the draught is too strong for me to take much at once. But he is at his best when he is in opposition to someone who is an even bigger asshole, in this case James Macpherson. Macpherson was a Scottish poet who perpetrated a major hoax for his own literary benefit. He claimed to have discovered and translated a collection of 3rd-century Gaelic manuscripts, written by a bard named Ossian, which he then published, with great commercial and critical success. Thomas Bailey Saunders, in The Life and Letters of James Macpherson (1894), writes:
Ossian and Macpherson did receive a great deal of criticism. Much of it was rooted in anti-Scottish bigotry, but many people at the time correctly suspected that Macpherson had written the "translations” himself, from scratch or nearly so. There was a great controversy, in which nobody participated more forcefully (or impolitely) than Johnson, a noted anti-Scottish bigot, who said that not only was the poems’ claimed history fraudulent, but that the poems themselves were rubbish. The argument raged for some time. Johnson took up the matter in Journey to the Western Islands of Scotland (1775), in which he said:
Macpherson was furious to learn, before it was published, what Journey to the Western Islands would say, and attempted to prevent the passage from appearing in the book at all. When he discovered he was too late for this, he suggested that a slip of paper be inserted into the printed copies, apologizing and withdrawing the paragraph. This suggestion was ignored, and Johnson's book was published with no alteration. Macpherson then challenged Johnson to a duel, and then, Johnson having declined, sent him a final letter, now lost, which a contemporary described as telling Johnson:
(John Clark, An Answer to Mr. [William] Shaw's Inquiry, p. 51. Reprinted in Works of Ossian, vol. 1, 1783.) Johnson's famous reply to this letter, quoted by Boswell, was:
Both Macpherson and Johnson are buried in Westminster Abbey. Some say Macpherson bought his way in. [Other articles in category /book] permanent link Mon, 22 Jan 2018
The gods of Stackexchange karma are fickle
A few years ago an se.math user asked why their undistinguished answer to some humdrum question had gotten so many upvotes. I replied:
If you're going to do Stack Exchange, I think it's important not to stress out about the whys of the votes, and particularly important not to take them personally. The karma gods do not always show the most refined taste. As Brandon Tartikoff once said, “All hits are flukes”. Today I got an unusually flukey hit. But first, here are some nice examples in the opposite direction, posts that I put a lot of trouble and effort into, which were clear and useful, helpful to the querent, and which received no upvotes at all. Here the querent asked, suppose I have several nonstandard dice with various labeling on the faces. Player A rolls some of the dice, and Player B rolls a different set of dice. How do I calculate things like “Player A has an X% chance of rolling a higher total”? Mathematicians are not really the right people to ask this to, because many of them will reply obtusely, informing you that it depends on how many dice are rolled and on how their faces are actually labeled, and that the question did not specify these, but that if it had, the problem would be trivial. (I thought there were comments to that effect on this question, but if there were they have been deleted. In any case nobody else answered.) But this person was writing a computer game and wanted to understand how to implement a computer algorithm for doing the calculation. There is a lot one can do to help this person. I posted an answer that I thought was very nice. The querent liked it, but it got zero upvotes. This happens quite often. Which is fine, because the fun of doing it and the satisfaction of helping someone are reward enough. Like that one, many of these questions are ignored because they aren't mathematically interesting. Or sometimes the mathematics is simple but the computer implementation is not. Sometimes I do them just because I want to know the particular answer. (How much of an advantage does Player A get from being allowed to add 1 to their total?) Sometimes there's an interesting pedagogical problem, such as: how do I give a hint that will point in the right direction without giving away the whole secret? Or: how do I wade through this person's confused explanation and understand what they are really asking, or what they are really confused about? That last person was given a proof that glossed over six or seven steps in the reasoning, focusing instead on the technically interesting induction proof in the middle. The six or seven steps are straightforward, if you already have enough practice with logical reasoning about quantified statements. But this querent didn't follow the reasoning that led up to the induction, so they didn't understand why the induction was useful or what it was for. Some people are just confused about what the question is. That person has a complicated-seeming homework exercise about the behavior of the logistic map, and need helps interpreting it from someone who has a better idea what is going on. The answer didn't require any research effort, and it's mathematically uninteresting, but it did require attention from someone who has a better idea of what is going on. The querent was happy, I was happy, and nobody else noticed. I never take the voting personally, because the gods of Stackexchange karma are so fickle, and today I got a reminder of that. Today's runaway hit was for a complete triviality that I knocked off in two minutes. It currently has 94 upvotes and seems likely to get a gold medal. (That gold medal, plus $4.25, will get me a free latte at Starbuck's!) The question asks how to find a prime factor of 7,999,973 without using a calculator. It's one of those easy-if-you-happen-to-know-the-trick things, and I just happened to get there before one of the (many) other people who happens to know the trick. As we used to say in the system administration biz, some days you're an idiot if you can't explain how to do real-time robot arm control in Unix, other days you're a genius if you fix their terminal by plugging it in. [ Addendum 20180123: I got the gold medal. Woo-hoo, free latte! ] [Other articles in category /math] permanent link Sat, 20 Jan 2018
I forgot there are party conventions
Yesterday I made a huge mistake in my article about California's bill requiring presidential candidates to disclose their tax returns. I asked:
Yes, yes I did. I forgot that party nominees are picked not by per-state primary elections, but by national conventions. Even had Ronnie won the California Republican primary election, rather than Trump, that would not be enough the get him on the ballot in the general election. In the corrected version of my scenario, California sends many Ronnie supporters to the Republican National Convention, where the other delegates overwhelmingly nominate Trump anyway. Trump then becomes the Republican party candidate and appears on the California general election ballot in November. Whoops. I had concluded that conceding California couldn't hurt Trump, and it could actually a huge benefit to him. After correcting my mistake, most of the benefit evaporates. I wonder if Trump might blow off California in 2020 anyway. The upside would be that he could spend the resources in places that might give him some electoral votes. (One reader pointed out that Trump didn't blow off California in the 2016 election, but of course the situation was completely different. In 2016 he was not the incumbent, he was in a crowded field, and he did not yet know that he was going to lose California by 30%.) Traditionally, candidates campaign even in states they expect to lose. One reason is to show support for candidates in local elections. I can imagine many California Republican candidates would prefer that Trump didn't show up. Another reason is to preserve at least a pretense that they are representatives of the whole people. Newly-elected Presidents have often upheld the dignity of the office by stating the need for unity after a national election and promising (however implausibly) to work for all Americans. I don't care to write the rest of this paragraph. The major downside that I can think of (for Trump) is that Republican voters in California would be infuriated, and while they can't directly affect the outcome of the presidential election, they can make it politically impossible for their congressional representatives to work with Trump once he is elected. A California-led anti-Trump bloc in Congress would probably cause huge problems for him. Wild times we live in. [Other articles in category /oops] permanent link Fri, 19 Jan 2018
Presidential tax return disclosure
The California state legislature passed a bill that would require presidential candidates to disclose their past five tax returns in order to qualify for California primary elections. The bill was vetoed by Governor Brown, but what if it had become law? Suppose Donald Trump ran for re-election in 2020, as seems likely, barring his death or expulsion. And suppose he declined once again to disclose his tax returns, and was excluded from the California Republican primary election. I don't see how this could possibly hurt Trump, and it could benefit him. It doesn't matter to Trump whether he enters the primary or wins the primary. Trump lost California by 30% in 2016. Either way he would be just as certain to get the same number of electors: zero. So he would have no incentive to comply with the law by releasing his tax returns. Most candidates would do it anyway, because they try to maintain a pretense of representing the entire country they are campaigning to lead, but Trump is really different in this way. I can easily imagine he might simply refuse to campaign in California, instead dismissing the entire state with some vulgar comment. If there is a downside for Trump, I don't see what it could be. Someone else (call them “Ronnie”) would then win the California Republican primary. Certainly Ronnie is better-qualified and more competent than Trump, and most likely Ronnie is much more attractive to the California electorate. Ronnie might even be more attractive than the Democratic candidate, and might defeat them in the general election, depriving Trump's challenger of 55 electoral votes and swinging the election heavily in Trump's favor. Did I miss anything? [ Addendum 20180120: Yeah, I forgot that after the primary there is a convention that nominates a national party candidate. Whooops. Further discussion. ] [Other articles in category /politics] permanent link Thu, 18 Jan 2018In autumn 2014 I paid for something and got $15.33 in change. I thought I'd take the hint from the Universe and read Wikipedia's article on the year 1533. This turned out unexpectedly exciting. 1533 was a big year in English history. Here are the highlights:
A story clearly emerges here, the story of Henry's frantic response to Anne Boleyn's surprise pregnancy. The first thing to notice is that Elizabeth was born only seven months after Henry married Boleyn. The next thing to notice is that Henry was still married to Catherine when he married Boleyn. He had to get Cranmer to annul the marriage, issuing a retroactive decree that not only was Henry not married to Catherine, but he had never been married to her. In 2014 I imagined that Henry appointed Cranmer to be Archbishop on condition that he get the annulment, and eventually decided that was not the case. Looking at it now, I'm not sure why I decided that.
Cranmer had been working on that annulment since at least 1527. In 1532 he was ambassador to Charles V, the Holy Roman Emperor, who was the nephew of Henry's current wife Catherine. I suppose a large part of Cranmer's job was trying to persuade Charles to support the annulment. (He was unsuccessful.) When Charles conveniently went to Rome (what for? Wikipedia doesn't say) Cranmer followed him and tried to drum up support there for the annulment. (He was unsuccessful in that too.) Fortunately there was a convenient vacancy, and Henry called him back to fill it, and got his annulment that way. In 2014 I thought Warham's death was just a little too convenient, but I decided that he died too early for it to have been arranged by Henry. Now I'm less sure — Henry was certainly capable of such cold-blooded planning — but I can't find any mention of foul play, and The Divorce of Henry VIII: The Untold Story from Inside the Vatican describes the death as “convenient though entirely natural”. [ Addendum: This article used to say that Elizabeth was born “less than seven months” after Henry and Boleyn's marriage. Daniel Holtz has pointed out that this was wrong. The exact amount is 225 days, or 32 weeks plus one day. The management regrets the error. ] [Other articles in category /history] permanent link Tue, 16 Jan 2018In an earlier article, I said:
This turns out to be no worry at all. The isotope in the pacemaker batteries is Pu-238, which is entirely unsuitable for making weapons. Pu-238 is very dangerous, being both radioactive and highly poisonous, but it is not fissile. In a fission chain reaction, an already-unstable atomic nucleus is hit by a high-energy neutron, which causes it to fragment into two lighter nuclei. This releases a large amount of nuclear binding energy, and more neutrons which continue the reaction. The only nuclei that are unstable enough for this to work have an odd number of neutrons (for reasons I do not understand), and Pu-238 does not fit the bill (Z=94, N=144). Plutonium fission weapons are made from Pu-241 (N=147), and this must be carefully separated from the Pu-238, which tends to impede the chain reaction. Similarly, uranium weapons are made from U-235, and this must be painstakingly extracted from the vastly more common U-238 with high-powered centrifuges. But I did not know this when I spent part of the weekend thinking about the difficulties of collecting plutonium from pacemakers, and discussing it with a correspondent. It was an interesting exercise, so I will publish it anyway. While mulling it over I tried to identify the biggest real risks, and what would be the most effective defenses against them. An exercise one does when considering security problems is to switch hats: if I were the bad guy, what would I try? What problems would I have to overcome, and what measures would most effectively frustrate me? So I put on my Black Hat and tried to think about it from the viewpoint of someone, let's call him George, who wants to build a nuclear weapon from pacemaker batteries. I calculated (I hope correctly) that a pacemaker had around 0.165 mg of plutonium, and learned online that one needs 4–6 kg to make a plutonium bomb. With skill and experience one can supposedly get this down to 2 kg, but let's take 25,000 pacemakers as the number George would need. How could he get this much plutonium? (Please bear in mind that the following discussion is entirely theoretical, and takes place in an imaginary world in which plutonium-powered pacemakers are common. In the real world, they were never common, and the last ones were manufactured in 1974. And this imaginary world exists in an imaginary universe in which plutonium-238 can sustain a chain reaction.) Obviously, George's top target would be the factory where the pacemakers are made. Best of all is to steal the plutonium before it is encapsulated, say just after it has been delivered to the factory. But equally obviously, this is where the security will be the most concentrated. The factory is not as juicy a target as it might seem at first. Plutonium is radioactive and toxic, so they do not want to have to store a lot of it on-site. They will have it delivered as late as possible, in amounts as small as possible, and use it up as quickly as possible. The chances of George getting a big haul of plutonium by hitting the factory seem poor. Second-best is for George to steal the capsules in bulk before they are turned into pacemakers. Third-best is for him to steal cartons of pacemakers from the factory or from the hospitals they are delivered to. But bulk theft is not something George can pull off over and over. The authorities will quickly realize that someone is going after pacemakers. And after George's first heist, everyone will be looking for him. If the project gets to the point of retrieving pacemakers after they are implanted, George's problems multiply enormously. It is impractical to remove a pacemaker from a living subject. George would need to steal them from funeral homes or crematoria. These places are required to collect the capsules for return to Oak Ridge, and conceivably might sometimes have more than one on hand at a time, but probably not more than a few. It's going to be a long slog, and it beggars belief that George would be able to get enough pacemakers this way without someone noticing that something was up. The last resort is for George to locate people with pacemakers, murder, and dissect them. Even if George somehow knows whom to kill, he'd have to be Merlin to arrange the murder of 25,000 people without getting caught. Merlin doesn't need plutonium; he can create nuclear fireballs just by waving his magic wand. If George does manage to collect the 25,000 capsules, his problems get even worse. He has to open the titanium capsules, already difficult because they are carefully made to be hard to open — you wouldn't want the plutonium getting out, would you? He has to open them without spilling the plutonium, or inhaling it, or making any sort of mess while extracting it. He has to do this 25,000 times without messing up, and without ingesting the tiniest speck of plutonium, or he is dead. He has to find a way to safely store the plutonium while he is accumulating it. He has to keep it hidden not only from people actively looking for him — and they will be, with great yearning — but also from every Joe Blow who happens to be checking background radiation levels in the vicinity. And George cannot afford to take his time and be cautious. He is racing against the clock, because every 464 days, 1% of his accumulated stock, however much that is, will turn into U-234 and be useless. The more he accumulates, the harder it is to keep up. If George has 25,000 pacemakers in a warehouse, ready for processing, one pacemaker-worth of Pu-238 will be going bad every two days. In connection with this, my correspondent brought up the famous case of the Radioactive Boy Scout, which I had had in mind. (The RBS gathered a recklessly large amount of americium-241 from common household smoke detectors.) Ignoring again the unsuitability of americium for fission weapons (an even number of neutrons again), the project is obviously much easier. At the very least, you can try calling up a manufacturer of smoke alarms, telling them you are building an apartment complex in Seoul, and that you need to bulk-order 2,000 units or whatever. You can rob the warehouse at Home Depot. You can even buy them online. [Other articles in category /tech] permanent link Sun, 14 Jan 2018
How do plutonium-powered pacemakers work?
I woke up in the middle of the night wondering: Some people have implanted medical devices, such as pacemakers, that are plutonium-powered. How the hell does that work? The plutonium gets hot, but what then? You need electricity. Surely there is not a tiny turbine generator in there! There is not, and the answer turns out to be really interesting, and to involve a bunch of physics I didn't know. If one end of a wire is hotter than the other, electrons tend to diffuse from the hot end to the cold end; the amount of diffusion depends on the material and the temperature. Take two wires of different metals and join them into a loop. (This is called a thermocouple.) Make one of the joints hotter than the other. Electrons will diffuse from the hot joint to the cold joint. If there were only one metal, this would not be very interesting. But the electrons diffuse better through one wire (say wire A) than through the other (B), and this means that there will be net electron flow from the hot side down through wire A and then back up through B, creating an electric current. This is called the Seebeck effect. The potential difference between the joints is proportional to the temperature difference, on the order of a few hundred microvolts per kelvin. Because of this simple proportionality, the main use of the thermocouple is to measure the temperature difference by measuring the voltage or current induced in the wire. But if you don't need a lot of power, the thermocouple can be used as a current source. In practice they don't use a single loop, but rather a long loop of alternating metals, with many junctions: This is called a thermopile; when the heat source is radioactive material, as here, the device is called a radioisotope thermoelectric generator (RTG). The illustration shows the thermocouples strung out in a long line, but in an actual RTG you put the plutonium in a capsule and put the thermocouples in the wall of the capsule, with the outside joints attached to heat sinks. The plutonium heats up the inside joints to generate the current. RTGs are more commonly used to power spacecraft, but there are a few dozen people still in the U.S. with plutonium-powered thermopile batteries in their pacemakers. In pacemakers, the plutonium was sealed inside a titanium capsule, which was strong enough to survive an accident (such as a bullet impact or auto collision) or cremation. But Wikipedia says the technique was abandoned because of worries that the capsule wouldn't be absolutely certain to survive a cremation. (Cremation temperatures go up to around 1000°C; titanium melts at 1668°C.) Loose plutonium in the environment would be Very Bad. (I wondered if there wasn't also worry about plutonium being recovered for weapons use, but the risk seems much smaller: you need several kilograms of plutonium to make a bomb, and a pacemaker has only around 135 mg, if I did the conversion from curies correctly. Even so, if I were in charge of keeping plutonium out of the wrong hands, I would still worry about this. It does not seem totally out of the realm of possibility that someone could collect 25,000 pacemakers. Opening 25,000 titanium capsules does sound rather tedious.) Earlier a completely different nuclear-powered pacemaker was tried, based on promethium-powered betavoltaics. This is not a heat-conversion process. Instead, a semiconductor does some quantum physics magic with the electrons produced by radioactive beta decay. This was first demonstrated by Henry Moseley in 1913. Moseley is better-known for discovering that atoms have an atomic number, thus explaining the periodic table. The periodic table had previously been formulated in terms of atomic mass, which put some of the elements in the wrong order. Scientists guessed they were in the wrong order, because the periodicity didn't work, but they weren't sure why. Moseley was able to compute the electric charge of the atomic nucleus from spectrographic observations. I have often wondered what else Moseley would have done if he had not been killed in the European war at the age of 27. It took a while to gather the information about this. Several of Wikipedia's articles on the topic are not up to their usual standards. The one about the radioisotope thermoelectric generator is excellent, though. Thermopile illustration is by FluxTeq (Own work) CC BY-SA 4.0, via Wikimedia Commons. [ Addendum 20180115: Commenters on Hacker News have pointed out that my concern about the use of plutonium in fission weapons is easily satisfied: the fuel in the batteries is Pu-238, which is not fissile. The plutonium to use in bombs is Pu-241, and indeed, when building a plutonium bomb you need to remove as much Pu-238 as possible, to prevent its non-fissile nuclei from interfering with the chain reaction. Interestingly, you can tell this from looking at the numbers: atomic nuclei with an odd number of neutrons are much more fissile than those with an even number. Plutonium is atomic number 94, so Pu-238 has an even number of neutrons and is not usable. The other isotope commonly used in fission is U-235, with 143 neutrons. I had planned to publish a long article today detailing the difficulties of gathering enough plutonium from pacemakers to make a bomb, but now I think I might have to rewrite it as a comedy. ] [ Addendum 20170116: I published it anyway, with some editing. ] [Other articles in category /tech] permanent link Sun, 07 Jan 2018Well, yesterday I wrote an article about the drinking contest in the Gylfaginning and specifically about what was in the horn. I was very pleased with it. In the article, I said several times:
A couple of my Gentle Readers have gently pointed out that I was wrong, wrong, wrong. I am deeply embarrassed. The punch line of the story is that the end of the horn is attached to the ocean, and Thor cannot empty it, because he is trying to drink the ocean. The horn is therefore not filled with mead; it is filled with seawater. How could I make such a dumb mistake? As I mentioned, the version I read first as a child stated that the horn was full of milk. And as a child I wondered: how could the horn be full of milk if it was attached to the sea? I decided that whatever enchantment connected the horn to the sea also changed the water to milk as it came into the horn. Later, when I realized that the milk was a falsehood, I retained my idea that there was an enchantment turning the seawater into something else. But there is nothing in the text to support this. The jötunns don't tell Thor that the horn is full of mead. Adam Sjøgren pointed out that if they had, Thor would have known immediately that something was wrong. But as the story is, they bring the horn, they say that even wimps can empty it in three draughts, and they leave it at that. Wouldn't Thor notice that he is not drinking mead (or milk)? I think certainly, and perhaps he is initially surprised. But he is in a drinking contest and this is what they have brought him to drink, so he drinks it. The alternative is to put down the horn and complain, which would be completely out of character. And the narrator doesn't say, and mustn't, that the horn was full of mead, because it wasn't; that would be in impermissible deceit of the audience. (“Hey, wait, you told us before that the horn was full of mead!”) I wrote:
No, it's not. It's because the narrator wants us to assume it is obviously mead, and then to spring the surprise on us as it was sprung on Thor: it was actually the ocean. The way it is told is a clever piece of misdirection. The two translators I quoted picked up on this, and I completely misunderstood it. I have mixed feelings about Neil Gaiman, but Veit Heller pointed out that Gaiman understood this perfectly. In his Norse Mythology he tells the story this way:
In yesterday's article I presented a fantasy of Marion French, the author of my childhood “milk” version, hearing Snorri tell the story:
But this couldn't have been how it went down. I now imagine it was more like this:
Thanks again to Adam Sjøgren and Veit Heller for pointing out my error, and especially for not wounding my pride any more than they had to. [Other articles in category /oops] permanent link When I was a kid I had a book of “Myths and Legends of the Ages”, by Marion N. French. One of the myths was the story of Thor's ill-fated visit to Utgard. The jötunns of Utgard challenge Thor and Loki to various contests and defeat them all through a combination of talent and guile. In one of these contests, Thor is given a drinking horn and told that even the wimpiest of the jötunns is able to empty it of its contents in three drinks. (The jötunns are lying. The pointy end of the horn has been invisibly connected to the ocean.) The book specified that the horn was full of milk, and as a sweet and innocent kiddie I did not question this. Decades later it hit me suddenly: no way was the horn filled with milk. When the mighty jötunns of Utgard are sitting around in their hall, they do not hold contests to see who can drink the most milk. Obviously, the horn was full of mead. The next sentence I wrote in the draft version of this article was:
In my drafts, I often write this sort of bald statement of fact, intending to go back later and check it, and perhaps produce a citation. As the quotation above betrays, I was absolutely certain that when I hunted down the original source it would contradict Ms. French and say mead. But I have now hunted down the canonical source material (in the Prose Edda, it turns out, not the Poetic one) and as far as I can tell it does not say mead! Here is an extract of an 1880 translation by Rasmus Björn Anderson, provided by WikiSource:
For comparison, here is the 1916 translation of Arthur Gilchrist Brodeur, provided by sacred-texts.com:
In both cases the following text details Thor's unsuccessful attempts to drain the horn, and Utgard-Loki's patronizing mockery of him after. But neither one mentions at any point what was in the horn. I thought it would be fun to take a look at the original Old Norse to see if the translators had elided this detail, and if it would look interesting. It was fun and it did look interesting. Here it is, courtesy of Heimskringla.NO:
This was written in Old Norse around 1220, and I was astounded at how much of it is recognizable, at least when you already know what it is going to say. However, the following examples are all ill-informed speculation, and at least one of my confident claims is likely to be wrong. I hope that some of my Gentle Readers are Icelanders and can correct my more ridiculous errors. “Höllina” is the hall. “Kallar” is to call in. The horn appears three times, as ‘horninu’, ‘horni’, and in ‘vítishorn’, which is a compound that specifies what kind of horn it is. “Þór í hönd” is “in Thor's hand”. (The ‘Þ’ is pronounced like the /th/ of “Thor”.) “Drekka”, “drukkit”, “drykk”, “drykkjum”, and “drykkjumaðr” are about drinking or draughts; “vel drukkit” is “well-drunk”. You can see the one-two-three in there as “einum-tveim-þrimr”. (Remember that the “þ” is a /th/.) One can almost see English in:
which says “some men drink it in two drinks”. And “lítill drykkjumaðr” is a little-drinking-person, which I translated above as “wimp”. It might be tempting to guess that “með horninu” is a mead-horn, but I'm pretty sure it is not; mead is “mjað” or “mjöð”. I'm not sure, but I think “með” here is just “with”, akin to modern German “mit”, so that:
is something like “next, the skutilsveinn came with the horn”. (The skutilsveinn is something we don't have in English; compare trying to translate “designated hitter” into Old Norse.) For a laugh, I tried putting this into Google Translate, and I was impressed with the results. It makes a heroic effort, and produces something that does capture some of the sense of the passage. It identifies the language as Icelandic, which while not correct, isn't entirely incorrect either. (The author, Snorri Sturluson, was in fact Icelandic.) Google somehow mistakes the horn for a corner, and it completely fails to get the obsolete term “hirðmenn” (roughly, “henchmen”), mistaking it for herdsmen. The skutilsveinn is one of the hirðmenn. Anyway there is no mead here, and none in the rest of the story, which details Thor's unsuccessful attempts to drink the ocean. Nor is there any milk, which would be “mjólk”. So where does that leave us? The jötunns challenge Thor to a drinking contest, and bring him a horn, and even though it was obviously mead, the story does not say what was in the horn. Because why would they bother to say what was in the horn? It was obviously mead. When the boys crack open a cold one, you do not have to specify what it was that was cold, and nobody should suppose that it was a cold bottle of milk. I imagine Marion N. French sitting by the fire, listening while Snorri tells the story of Thor and the enchanted drinking horn of Utgard:
(In preparing this article, I found it helpful to consult Zoëga's Concise Dictionary of Old Icelandic of 1910.) [ Addendum 2018-01-17: Holy cow, I was so wrong. It was so obviously not mead. I was so, so wrong. Amazingly, unbelievably wrong. ] [ Addendum 2018-03-22: A followup in which I investigate what organs Skaði looked at when choosing her husband, and what two things Loki tied together to make her laugh. ] [Other articles in category /lang] permanent link Fri, 05 Jan 2018Last month I wrote about the Turkish analog of “Joe Blow”. I got email from Gaal Yahas, who said
Sadly no. But M. Yahas did tell me in detail about the Hebrew version, and I did a little additional research. The Hebrew version of “Joe Blow” / “John Doe” is unequivocally “Ploni Almoni”. This usage goes back at least to the Book of Ruth, approximately 2500 years ago. Ruth's husband has died without leaving an heir, and custom demands that a close relative of her father-in-law should marry her, to keep the property in the family. Boaz takes on this duty, but first meets with another man, who is a closer relative than he:
This other relative declines to marry Ruth. He is not named, and is referred to in the Hebrew version as Ploni Almoni, translated here as “such a one”. This article in The Jewish Chronicle discusses the possible etymology of these words, glossing “ploni” as akin to “covered” or “hidden” and “almoni” as akin to “silenced” or “muted”. Ploni Almoni also appears in the book of Samuel, probably even older than Ruth:
The mission is secret, so David does not reveal the meeting place to Ahimelek. Instead, he refers to it as Ploni Almoni. There is a similar usage at 2 Kings 6:8. Apparently the use of “Ploni” in Hebrew to mean “some guy” continues through the Talmud and up to the present day. M. Yahas also alerted me to two small but storied streets in Tel Aviv. According to this article from Haaretz:
And so they remain, 95 years later. (M. Yahas explains that “Simta” means “alley” and is feminine, so that Ploni and Almoni take the feminine ‘-it’ ending to agree with it.) Wikipedia has not one but many articles on this topic and related ones:
My own tiny contribution in this area: my in-laws live in a rather distant and undeveloped neighborhood on the periphery of Seoul, and I once referred to it as 아무데도동 (/amudedo-dong/), approximately “nowhereville”. This is not standard in Korean, but I believe the meaning is clear. [Other articles in category /lang] permanent link Tue, 02 Jan 2018As I mentioned before, I have started another
blog, called The shitposts have been suffering quality creep and I am making an effort to lower my standards. I will keep you posted about how this develops. (I don't think the quality creep was the cause of lower volume this month; rather, I was on vacation for a week.) Here is a list of last month's shitposts. I have added a short blurb to those that may be of more general interest.
I plan to continue to post monthly summaries here. [Other articles in category /meta/shitpost] permanent link
Converting Google Docs to Markdown
I was on vacation last week and I didn't bring my computer, which has been a good choice in the past. But I did bring my phone, and I spent some quiet time writing various parts of around 20 blog posts on the phone. I composed these in my phone's Google Docs app, which seemed at the time like a reasonable choice. But when I got back I found that it wasn't as easy as I had expected
to get the documents back out. What I really wanted was Markdown.
HTML would have been acceptable, since Blosxom accepts that also. I
could download a single document in one of several formats, including
HTML and ODF, but I had twenty and didn't want to do them one at a
time. Google has a bulk download feature, to download a zip file of
an entire folder, but upon unzipping I found that all twenty documents
had been converted to Microsoft's Several tools will compose in Markdown and then export to Google docs, but the only option I found for translating from Google docs to Markdown was Renato Mangini's Google Apps script. I would have had to add the script to each of the 20 files, then run it, and the output appears in email, so for this task, it was even less like what I wanted. The right answer turned out to be: Accept Google's bulk download of
The The
Often, I feel that I have written too much code, but not this time.
Some people might be tempted to add bells and whistles to this: what
if the suffix is not delimited by a dot character? What if I only
want to change certain suffixes? What if my foot swells up? What if
the moon falls out of the sky? Blah blah blah. No, for that we can
break out Next time I go on vacation I will know better and I will not use Google Docs. I don't know yet what instead. StackEdit maybe. [ Addendum 20180108: Eric Roode pointed out that the program above has
a genuine bug: if given a filename like [Other articles in category /Unix] permanent link |