My week at Recurse Center
In late April I served a residency at Recurse Center, formerly known as
Hacker School. I want to write up what I did before I forget.
Recurse Center bills itself as being like a writer's retreat, but for
programming. Recursers get better at programming four days a week for
three months. There are some fulltime instructors there to help, and
periodically a resident, usually someone notable, shows up for a week.
It's free to students: RC partners with companies that then pay it a
fee if they hire a Recurser.
I got onto the RC chat system and BBS a few weeks ahead and
immediately realized that it was going to be great. I am really wary
about belonging to groups, but I felt like I fit right in at RC, in a
way that I hadn't felt since I went off to math camp at age 14.
Recurse Center isn't that different from math camp now that I think
about it.
The only prescribed duty of a resident is to give a halfhour talk on
Monday night, preferably on a technical topic. I gave mine on the
history and internals of lightweight hash structures in programming
languages like Python and Perl. (You can read all about
that if you want to.)
Here's what else I did:
I gave a bunch of other talks: two on Git, one on calculating with
continued fractions, one on how the Haskell type inferencer works,
one on the topology of data types, one on the Unix process
model, one on Alien
Horrors from the Dawn of
Unix. This was too many
talks. I didn't have enough energy and time to prepare all of them
properly. On the other hand, a lot of people were very
complimentary about the talks and said they were very glad that I
gave so many. Also, giving talks is a great way to get people
familiar with you so that they won't be shy about talking to you or
asking you to work with them. But I think I'll cut it down to one
per day next time.
Alex Taipale was inspired by my
hash talk to implement hashes synthetically in
Python, and I paired with
her on that for the first part and reviewed her code a couple of
times after. It was really fun to see how she went about it.
Libby Horacek showed me around the text adventure game she wrote in
Haskell. I had the first of several strokes of luck here. Libby
had defined an input format to specify the room layout and the
objects, and I observed that it was very similar to
Asherah, a project that
another Recurser, Michelle Steigerwalt, had done a couple of years
before. I found this out because I read everyone's selfposted bio
ahead of time and browsed the interestingsounding links.
Aditya Mukerjee was
implementing Git in Go.
He wanted help deciphering the delta format. Later I paired with
Aditya again and we debugged his implementation of the code that
expanded the deltas back into complete files. I hadn't known any
Go but it's easy to pick up.
Geoffrey Gilmore had read my
ancient article on how to write a regex
matcher. He had written his own
implementation in Scala and wanted to show it to me. I didn't know
any Scala but the code was very clear. Geoffrey had worked out a
clever way to visualize the resulting finite automaton: his
automaton object had a method that would dump out its graph in the
"dot" language, and he could feed that to
Graphviz to get it to
draw the graph.
I had a conference with Ahmed
Abdalla and Joel
Burget about SML. The main question they
wanted me to answer: Why might they want to look at SML instead of
Haskell? This was a stroke of luck: I was unusually wellprepared
to answer this question, having written many thousands of lines of
SML since about 1993. My answer was unequivocally that there was
no reason, SML was obsolete, because it had big problems which had
never been solved, and Haskell had been introduced in part to
solve, avoid, or finesse these problems.
For example, nobody knows how to incorporate references into a
HindleyMilner type system. SML has tried at least three methods
for doing this over the years. They all suck, and none of them
work right. Haskell avoids the whole issue: no references. If you
want something like references, you can build a monad that
simulates it locally.
I could probably write a whole blog article about this, so maybe
another time.
[ Addendum 20220425: The article is written! ]
Libby wanted to pair with me again. She offered me a choice: she
was building an ereader, controlled by a Raspberry Pi, and mounted
inside an antique book that she had hollowed out. I would have been
willing to try this, although I didn't know anything about
Raspberry Pi. But my other choice was very attractive: she was
reviving KiSS,
an ancient Windows paperdoll app that had been current in the
1990s. people had designed hundreds or thousands of dolls and
costumes, which were all languishing because nobody wanted to run
the app any more. She wanted to reimplement the dressup program
in Javascript, and port the doll and clothing cels to PNG files.
Here I had another stroke of luck. I was already familiar with the
program, and I think I have even been into its source code at some
point.
Libby had found that Gimp could load a KiSS cel, so we looked at
the Gimp source code to figure out the file format. She had been
planning to use libpng to turn the cel into a PNG, but I showed
her a better way: convert it into a PPM file and feed to to
ppmtopng . This saved a lot of trouble! (I have written a little
bit about this
approach in the
past.) Libby hacked in the Gimp code, grafting her PPM file
writing code into the Gimp cel reading code in place of Gimp's
internal pixmap operations. It worked!
I talked to Chris Ball about his GitTorrent
project.
Chris wants to make a decentralized github that doesn't depend on
the GitHub company or on their technical infrastructure. He spent
a long time trying to make me understand why he wanted to do the
project at all and what it was for. I think I eventually got it.
It also transpired that Chris knows way more about BitTorrent than
I do. I don't think I was much help to Chris.
Jesse Chen paired with me to fix
the layout problems that have been troubling my blog for years. We
redid the ancient tablebased layout that I had inherited from
Blosxom ten years ago, converting it mostly to CSS, and fixed a
bunch of scrolling problems. We also fixed it to be legible on a
phone display, which it previously wasn't. Thanks Jesse!
I had a discussion with Michelle
Steigerwalt about bigO notation
and how you figure out what an algorithm's bigOness is, either
from counting lines in the source code or the pseudocode, or from
running the algorithm on differentsize inputs and timing it. It's
fun that you can do the static analysis and then run the program
and see it produce the results you predicted.
There was a lot of other stuff. I met or at least spoke with around
90% of the seventy or so Recursers who were there with me. I attended
the daily standup status meetings with a different group each time.
I ate lunch and dinner with many people and had many conversations. I
went out drinking with Recursers at least once. The RC principals
kindly rescheduled the usual Thursday lightning talks to Monday so I
could attend. I met Erik Osheim
for lunch one day. And I baked cookies for our cookiedecorating
party!
It was a great time, definitely a high point in my life. A thousand
thanks to RC, to Rachel Vincent and Dave Albert for essential support
while I was there, and to the facilitators, principals, and especially
to the other Recursers.
[Other articles in category /misc]
permanent link
Math SE report 201505
A lot of the stuff I've written in the past couple of years has been
on math.StackExchange. Some of it is pretty mundane, but some is
interesting. My summary of April's interesting posts was
wellreceived, so here are the noteworthy posts I made in May 2015.
What matrix transforms !!(1,0)!! into !!(2,6)!! and tranforms
!!(0,1)!! into
!!(4,8)!!? was a
little funny because the answer is $$\begin{pmatrix}2 & 4 \\ 6 & 8
\end{pmatrix}$$ and yeah, it works exactly like it appears to,
there's no trick. But if I just told the guy that, he might feel
unnecessarily foolish. I gave him a method for solving the problem
and figured that when he saw what answer he came up with, he might
learn the thing that the exercise was designed to teach him.
Is a “network topology'” a topological
space?
is interesting because several people showed up right away to say
no, it is an abuse of terminology, and that network topology really
has nothing to do with mathematical topology. Most of those comments
have since been deleted. My answer was essentially: it is
topological, because just as in mathematical topology you care about
which computers are connected to which, and not about where any of
the computers actually are.
Nobody constructing a token ring network thinks that it has to be a
geometrically circular ring. No, it only has to be a topologically
circular ring. A square is fine; so is a triangle; topologically
they are equivalent, both in networking and in mathematics. The
wires can cross, as long as they don't connect at the crossings.
But if you use something that isn't topologically a ring, like say
a line or a star or a tree, the network doesn't work.
The term “topological” is a little funny. “Topos” means “place”
(like in “topography” or “toponym”) but in topology you don't care
about places.
Is there a standard term for this generalization of the Euler
totient function?
was asked by me. I don't include all my answers in these posts, but
I think maybe I should have a policy of including all my questions.
This one concerned a simple concept from number theory which I was
surprised had no name: I wanted !!\phi_k(n)!! to be the number of
integers !!m!! that are no larger than !!n!! for which !!\gcd(m,n) =
k!!. For !!k=1!! this is the famous Euler totient function, written
!!\varphi(n)!!.
But then I realized that the reason it has no name is that it's
simply !!\phi_k(n) = \varphi\left(\frac n k\right)!! so there's no need
for a name or a special notation.
As often happens, I found the answer myself shortly after I asked
the question. I wonder if the reason for this is that my time to
come up with the answer is Poissondistributed. Then if I set a time
threshold for how long I'll work on the problem before asking about
it, I am likely to find the answer to almost any question that
exceeds the threshold shortly after I exceed the threshold. But if
I set the threshold higher, this would still be true, so there is
no way to win this particular game. Good feature of this theory: I
am off the hook for asking questions I could have answered myself.
Bad feature: no real empirical support.
how many ways can you divide 24 people into groups of
two? displays a
few oddities, and I think I didn't understand what was going on at
that time. OP has calculated the first few special cases:
1:1 2:1 3:3 4:3 5:12 6:15
which I think means that there is one way to divide 2 people into
groups of 2, 3 ways to divide 4 people, and 15 ways to divide 6
people. This is all correct! But what could the 1:1, 3:3, 5:12
terms mean? You simply can't divide 5 people into groups of 2.
Well, maybe OP was counting the extra odd person left over as a sort
of group on their own? Then odd values would be correct; I didn't
appreciate this at the time.
But having calculated 6 special cases correctly, why can't OP
calculate the seventh? Perhaps they were using brute force: the
next value is 48, hard to bruteforce correctly if you don't have a
enough experience with combinatorics.
I tried to suggest a general strategy: look at special cases, and
not by brute force, but try to analyze them so that you can come
up with a method for solving them. The method is unnecessary for
the small cases, where brute force enumeration suffices, but you can
use the brute force enumeration to check that the method is
working. And then for the larger cases, where brute force is
impractical, you use your method.
It seems that OP couldn't understand my method, and when they tried
to apply it, got wrong answers. Oh well, you can lead a horse to
water, etc.
The other pathology here is:
I think I did what you said and I got 1.585times 10 to the 21
for the !!n=24!! case. The correct answer is
$$23\cdot21\cdot19\cdot17\cdot15\cdot13\cdot11\cdot9\cdot7\cdot5\cdot3\cdot1
= 316234143225 \approx 3.16\cdot 10^{11}.$$ OP didn't explain how
they got !!1.585\cdot10^{21}!! so there's not much hope of
correcting their weird error.
This is someone who probably could have been helped in person, but
on the Internet it's hopeless. Their problems are Internet
communication problems.
Lambda calculus
typing isn't
especially noteworthy, but I wrote a fairly detailed explanation of
the algorithm that Haskell or SML uses to find the type of an
expression, and that might be interesting to someone.
I think Special representation of a
number is the
standout post of the month. OP speculates that, among numbers of
the form !!pq+rs!! (where !!p,q,r,s!! are prime), the choice of
!!p,q,r,s!! is unique. That is, the mapping !!\langle
p,q,r,s\rangle \to pq+rs!! is reversible.
I was able to guess that this was not the case within a couple of
minutes, replied pretty much immediately:
I would bet money against this representation being unique.
I was sure that a simple computer search would find
counterexamples. In fact, the smallest is !!11\cdot13 + 19\cdot 29
= 11\cdot 43 + 13\cdot 17 = 694!! which is small enough that you
could find it without the computer if you are patient.
The obvious lesson to learn from this is that many elementary
conjectures of this type can be easily disproved by a trivial
computer search, and I frequently wonder why more amateur
mathematicians don't learn enough computer programming to
investigate this sort of thing. (I wrote recently on the topic of
An ounce of theory is worth a pound of search
, and this is an interesting
counterpoint to that.)
But the most interesting thing here is how I was able to instantly
guess the answer. I explained in some detail in the post. But the
basic line of reasoning goes like this.
Additive properties of the primes are always distributed more or
less at random unless there is some obvious reason why they can't
be. For example, let !!p!! be prime and consider !!2p+1!!. This
must have exactly one of the three forms !!3n1, 3n,!! or !!3n+1!!
for some integer !!n!!. It obviously has the form !!3n+1!! almost
never (the only exception is !!p=3!!). But of the other two forms
there is no obvious reason to prefer one over the other, and indeed
of the primes up to 10,000, 611 are of the type !!3n!! and and 616
are of the type !!3n1!!.
So we should expect the value !!pq+rs!! to be distributed more or
less randomly over the set of outputs, because there's no obvious
reason why it couldn't be, except for simple stuff, like that it's
obviously almost always even.
So we are throwing a bunch of balls at random into bins, and the
claim is that no bin should contain more than one ball. For that to
happen, there must be vastly more bins than balls. But the bins are
numbers, and primes are not at all uncommon among numbers, so the
number of bins isn't vastly larger, and there ought to be at least
some collisions.
In fact, a more careful analysis, which I wrote up on the site,
shows that the number of balls is vastly larger—to have them be
roughly the same, you would need primes to be roughly as common as
perfect squares, but they are far more abundant than that—so as you
take larger and larger primes, the number of collisions increases
enormously and it's easy to find twenty or more quadruples of primes
that all map to the same result. But I was able to predict this
after a couple of minutes of thought, from completely elementary
considerations, so I think it's a good example of Lower Mathematics
at work.
This is an example of a fairly common pathology of math.se
questions: OP makes a conjecture that !!X!! never occurs or that
there are no examples with property !!X!!, when actually !!X!!
almost always occurs or every example has property !!X!!.
I don't know what causes this. Rik Signes speculates that it's just
wishful thinking: OP is doing some project where it would be useful
to have !!pq+rs!! be unique, so posts in hope that someone will tell
them that it is. But there was nothing more to it than baseless
hope. Rik might be right.
[ Addendum 20150619: A previous version of this article included the delightful typo “mathemativicians”. ]
[Other articles in category /math/se]
permanent link
Math SE report 201506
[ This page originally held the report for April
2015, which has moved. It now contains
the report for June 2015. ]
Is “smarter than” a transitive
relationship?
concerns a hypothetical "is smarter than" relation with the
following paradoxicalseeming property:
most X's are smarter than most Y's, but most Y's are such that it
is not the case that most X's are smarter than it.
That is, if !!\mathsf Mx.\Phi(x)!! means that most !!x!! have property
!!\Phi!!, then we want both $$\mathsf Mx.\mathsf My.S(x, y)$$ and
also $$\mathsf My.\mathsf Mx.\lnot S(x, y).$$
“Most” is a little funny here: what does it mean? But we can pin it
down by supposing that there are an infinite number of !!x!!es and
!!y!!s, and agreeing that most !!x!! have property !!P!! if there
are only a finite number of exceptions. For example, everyone
should agree that most positive integers are larger than 7 and that
most prime numbers are odd. The jargon word here is that we are
saying that a subset contains “most of” the elements of a larger set
if it is cofinite.
There is a model of this property, and OP reports that they asked
the prof if this was because the "smarter than" relation !!S(x,y)!!
could be antitransitive, so that one might have !!S(x,y), S(y,z)!!
but also !!S(z,x)!!. The prof said no, it's not because of that,
but the OP want so argue that it's that anyway. But no, it's not
because of that; there is a model that uses a perfectly simple
transitive relation, and the nontransitive thing nothing but a
distraction. (The model maps the !!x!!es and !!y!!s onto numbers,
and says !!x!! is smarter than !!y!! if its number is bigger.)
Despite this OP couldn't give up the idea that the model exists
because of intransitive relations. It's funny how sometimes people
get stuck on one idea and can't let go of it.
How to generate a random number between 1 and 10 with a sixsided
die? was a lot of
fun and attracted several very good answers. Topscoring is Jack
D'Aurizio's, which proposes a completely straightforward method:
roll once to generate a bit that selects !!N=0!! or !!N=5!!, and
then roll again until you get !!M\ne 6!!, and the result is !!N+M!!.
But several other answers were suggested, including two by me, one
explaining the general technique of arithmetic
coding, which I'll
probably refer back to in the future when people ask similar
questions. Don't miss NovaDenizen's clever simplification of
arithmetic coding,
which I want to think about more, or D'Aurizio's suggestion that if
you threw the die into a Vshaped trough, it would land with one
edge pointing up and thus select a random number from 1 to 12 in a
single throw.
Interesting question: Is there an easytoremember mapping from
edges to numbers from 1–12? Each edge is naturally identified by a
pair of distinct integers from 1–6 that do not add to 7.
The oddlyphrased Category theory with objects as logical
expressions over !!{\vee,\wedge,\neg}!! and morphisms
as? asks if there is
a standard way to turn logical expressions into a category, which
there is: you put an arrow from !!A\to B!! for each proof that !!A!!
implies !!B!!; composition of arrows is concatenation of proofs, and
identity arrows are empty proofs. The categorial product,
coproduct, and exponential then correspond to !!\land, \lor, !! and
!!\to!!.
This got me thinking though. Proofs are properly not lists, they are
trees, so it's not entirely clear what the concatenation operation
is. For example, suppose proof !!X!! concludes !!A!! at its root
and proof !!Y!! assumes !!A!! in more than one leaf. When you
concatenate !!X!! and !!Y!! do you join all the !!A!!'s, or what? I
really need to study this more. Maybe the Lambek and Scott book
talks about it, or maybe the Goldblatt Topoi book, which I actually
own. I somehow skipped most of the Cartesian closed category stuff,
which is an oversight I ought to correct.
In Why is the Ramsey`s theorem a generalization of the Pigeonhole
principle I gave
what I thought was a terrific answer, showing how Ramsey's graph
theorem and the pigeonhole principle are both special cases of
Ramsey's hypergraph theorem. This might be my favorite answer of
the month. It got several upvotes, but OP preferred a different
answer, with fewer details.
There was a thread a while
back about theorems
which are generalizations of other theorems in nonobvious ways. I
pointed out the Yoneda lemma was a generalization of Cayley's
theorem from group theory. I see that nobody mentioned the Ramsey
hypergraph theorem being a generalization of the pigeonhole
principle, but it's closed now, so it's too late to add it.
In Why does the Deduction Theorem use
Union? I explained
that the English word and actually has multiple meanings. I know I've
seen this discussed in elementary logic texts but I don't remember
where.
Finally, Which is the largest power of natural number that can be
evaluated by
computers? asks if
it's possible for a computer to calculate !!7^{120000000000}!!. The
answer is yes, but it's nontrivial and you need to use some tricks.
You have to use the multiplyingbysquaring trick, and for the
squarings you probably want to do the multiplication with DFT. OP
was dissatistifed with the answer, and seemed to have some axe to
grind, but I couldn't figure out what it was.
[Other articles in category /math/se]
permanent link
