The 30th anniversary of the Long Island Challenge is now in the books, and as usual, long island did indeed challenge.
The ranks of our swimmers were very slightly battered and buffeted by time, nature, society, and other absolutes, but we did indeed complete the swim with all that set out on the day, and were thinking often of those who could not be there (Mary, Mark, Tricia, Andy, Brenna, and many more).
Boy, I’m making this sound like D-Day, or something. It really wasn’t quite as end-of-the-world as all that.
The water temperature was not as cold as it had been earlier in the summer, but it was surprisingly windy for 7 AM, and there was definitely a rolling motion to the water, I think the southwest wind managed to find a pretty solid gap between the islands. We finished the swim in about an hour and a half, which might be longer than usual.
Also, I found some sea stars out on long island, that was pretty cool.
Finally, a couple of swim-anniversaries for the swimmers as well as the event. It was my (John Clements) twentieth swim, Charlotte Clews’ tenth swim, and Alice and Lane’s fifth swim. In fact, Justice was the only swimmer not to have an anniversary, but he’s swum it so many times that we ran out of numbers. Let’s just call it infinity times.
The swimmers:
Alice Clements
Charlotte Clews
John Clements
Justice Pollard
Lane Lucas
The magnificent support crew who successfully prevented all deaths and (further) injuries:
We also have excellent photos from <all the people who sent photos> and I am personally deeply grateful to Mary Clews who organized the whole thing even though she didn’t get to swim.
I think I’m not alone in suggesting that the tree, and perhaps the binary tree specifically, is the most foundational data structure in computer science.
This raises the question of how binary trees should be introduced, and I’d like to make the case that introducing binary trees as a special case of undirected graphs is not a good idea.
I can see reasons why you might think this is a good idea; they both involve connecting circles with straight lines on the board. If you take the general notion of a graph, and you happen to arrange the lines and circles in a particular way, it’s a tree. That kind of suggests that graphs are a generalization of trees, and that you might want to introduce trees as a special case of these graphs.
Please do not do this.
Specifically, my claim is that this produces a complex definition of trees with many global constraints, a definition which makes it very hard to prove some simple things.
Let’s see why.
Trees as Undirected Graphs
To begin with, consider the definition of a graph, a set of nodes along with a symmetric binary relation on nodes that we call “edges”.
In order to construct the set of trees, we can restrict this definition in the following ways.
A tree is a graph with the following properties:
We designate one node as the root node,
it is connected, and
it has no cycles.
The last two of these are global cqnstraints requiring complex checks, and verifying the third is genuinely quite complex, especially for a first-year student.
Suppose now that we want to identify the descendants of a node. This is where things start to get really unpleasant. The descendants of a node are the adjacent nodes that are not the parent node. But which is the parent node? The root node has no parent node. For other nodes, it is the adjacent node which is the first along the path to the root node. Again, this is not a simple process; if we provide a symmetric edge relation and a parent node, determining the path to the root node (and thus the parent node (and thus, by elimination, the descendants)) requires potentially a full search of the tree. Yes, this can be cached. Yes, it doesn’t matter whether you do a depth-first or breadth-first search. It’s still a lot of work.
But wait! Suppose we want a binary tree? Firstly, we must ensure that every node has at most two descendants, which is the same as ensuring that the root node has at most 2, and every other node has at most 3. That’s the easy part, though. In a binary tree we typically care whether a child is the left child or the right child; adding this to a graph representation requires labeling every node as either a left child or a right child, and then checking to make sure that no node has more than one left or right child.
Inductively Specified Trees
Okay, so what’s the alternative?
The alternative is the inductive specification of a binary tree: a binary tree is either an empty tree, or it is a node containing a left tree and a right tree.
This representation is essentially a tree by definition; no global checks are required. Asking whether a binary tree specified in this way is a binary tree is genuinely trivial: only binary trees can be specified using this schema.
You could argue that inductive specifications are hard for students, and I wouldn’t completely disagree, but I would also argue that the overwhelming simplicity of this definition of binary trees powerfully outweighs the challenge of becoming comfortable with inductive specifications.
Identifying the descendants of a node here is essentially trivial; an empty tree has no descendants, a non-empty tree lists its two descendants.
Freebie: this representation also sidesteps the irritating issues around identity which bedevil programmers everywhere.
What about directed graphs?
Trees as Directed Graphs
Directed graphs are considerably better than undirected graphs. But still way worse than the inductive specification. Specifically, you need an undirected graph that is connected and with no directed cycles, and you also need an additional constraint that at most one node points to another one (making the arbitrary choice that the edges point from parents to children). Checking these constraints still requires examining the whole graph. Identifying the child nodes is much nicer. Distinguishing the left and right children is still a serious problem.
Done
To summarize; it’s reasonable to talk about the correspondence between these two representations. You might even want to try to prove them isomorphic. But please don’t introduce trees as a special case of graphs.
This is a short blog post about Prabakhar Ragde’s “Logic and Computation Intertwined”, or “LACI”, currently available online at
https://cs.uwaterloo.ca/~plragde/flaneries/LACI/
Here is a bad thing about LACI: every time I search for it, my search engine steers me toward articles about the tragic life of Laci Peterson.
Here is a good thing about LACI: everything else!
Specifically, LACI walks you through the process of building a small higher-order-logic theorem prover, using the same dependent typing bones as systems like Lean, and Agda, and Coq.
I have just finished using LACI as the first five weeks of a master’s-level course at Cal Poly, and I found it fantastic. Specifically, it has the part I most like about the definitional interpreter experience: you hear about a technical thing, and you think “yes, that sort of makes sense to me,” and then you try using or extending it and you realize “wow I didn’t understand that at all”, and then you figure out a fantastic new thing and you carry it around like a shiny stone for the rest of your life.
In fact, there are a number of shiny stones involved in LACI. Here are some of the ones that I appreciated the most.
First, intuitionistic proof theory (and maybe more specifically the BHK interpretation) comes up with a really fascinating way of talking about negation as an implication of bottom. Figuring out the propositional puzzles here, and how to prove certain things, is an absolute ton of fun (for a particular definition of fun, I grant you).
Second, dependent type theory pushes through a really mind-bending overlap between types and propositions: propositions are types. This leads to a really complete collapse between the boundary of terms and types. A quote from Moon over Morocco, presented in the show as a moroccan proverb and who knows maybe it is: “A devil takes one and makes two; a saint takes two and makes one.” In this case, collapsing the boundary between terms and types makes for some incredible richness, mixing lambda terms and forall terms (and many other things) in a mind-bending way.
For both of these, Ragde also provides a selection of excellent exercises. Formulating exercises in a domain like this is extraordinarily difficult; there are not a large pool of equivalent-difficulty problems that can be generated mechanically. A programming languages course has this same problem, if (like PLAI 2nd edition, for instance) the goal is to get you to implement an interpreter for some lambda-calculus-like language. Ragde does a very nice job of implementing core things, and then challenging you to implement satellite things that are hopefully just a bit out of reach, but not so far out of reach that things get hopelessly tangled. I’m in the final stages of coaching my students through an implementation of the natural numbers in Proust, and the problem is enlightening without being utterly soul-crushing.
I would also be remiss if I did not heap praise on the many side-notes and references that Ragde provides; many of the sections initiate potentially lifelong explorations of math and logic, and provide names and ideas for further investigation. This is the kind of thing that students sometimes complain about, but that curious thinkers delight in.
Another quote, this one from Ralph Sockman: “The larger the island of knowledge, the longer the shoreline of wonder.”
Yesterday was the election! It looks like Donald Trump is going to be our next president. The democrats lost.
As much as it pains me to write that, the simple truth is that it doesn’t help anyone or anything to be cynical, or to flip out, and it really doesn’t help anyone to doom-loop on terrible possible outcomes.
So, just to remind myself, here are some things I think are important, and worth fighting for:
Human Rights
Rule of Law
Freedom of the Press
Slowing Global Warming
Really, it all comes down to Human rights; I want to work hard(er) to ensure that others have the right to life, liberty, and the pursuit of happiness.
To be clear, I do think that these things are under threat, and probably will be for the forseeable future. In particular, the Rule of Law and Freedom of the Press are “enabling technologies” for Human Rights; I believe that the United States of America continues to be at the forefront of a grand political experiment in how best to ensure the rights of all its citizens, and that the Rule of Law and Freedom of the Press are vital cornerstones of our system; without them, other things can crumble quickly, as we’ve seen in dictatorships all over the world.
So there, I also said “dictatorship”. I do not think that we are somehow magically immune from dictatorship, and I do think that we are constantly called upon to bolster our government and to oppose attempts to seize control. I don’t know what shape those attempts will take, but I hope that I have the strength to raise my voice against them when they do.
I realize that I haven’t said anything about Global Warming.
Okay, quick aside: can we go back to just saying “Global Warming”? The “Climate Change” phrase is no longer helping, I don’t think.
Anyhow, I do think that climate change is potentially the most destabilizing force to governments and people today, with the potential to kill millions of people (this is already beginning) and to cause wars and famine. I think the evidence for global warming is almost comically solid at this point, and we need to be doing much much more to slow it down.
To go back to the title: I’ve seen this movie before. It sucked. But I didn’t die[*]. I can get through this, and it does not help to panic, and being angry all the time is probably not a recipe for health, sanity, or forward progress. I’m going to try to do what I can, and stay calm. I pray for you and for your family. Take care of yourselves.
Hmm… well, that was harder than it used to be. Probably I’m just getting old.
Okay, rewind. This year was the 29th swim! The water was a good deal colder than it has been in the last few, and the choice of date meant that the tide was not compatible with an inbound swim, so our swim was (for the second time ever) from the Becton’s dock out to the island. Besides meaning that swimmers couldn’t see much in the way of landmarks, it also meant that the water got colder and colder as we approached the finish.
Justice had the bright idea of borrowing race markers to help guide the swimmers and the chase boats, which was quite helpful. Who knows where we would have ended up otherwise.
I personally cannot comment much on the pointy end of the swim; I was slow slow slow, and by the time I crawled out of the water the rest of the swimmers were relaxing in easy chairs, sipping martinis. Not quite but pretty close. This was definitely a wet suit year.
Many kudos to two first-time swimmers: Mike Keene, and Laura Lutton. I would like to offer a huge shout-out to Laura for her entering-the-water howl, which kept me going for most of the swim. This was also the fifth swim for Ted Heyd and Pat Starkey, a tip of the swim cap to them.
This was also a year that honored Jeannie Becton, who is no longer among the living, and will be forever missed. Swimmers and others made donations to the Heritage Trust in her name.
Next year will be the 29th anniversary, and the 30th swim. Goodness.
The year is 2022. This is the 28th swim, and it was warm, and it was quite calm. Really, a balmy morning all around. The big news was that we picked up another multi-generational team, and there were a total of 3 “next-generation” swimmers: Ahren Michaud, Lucy Lawther, and Liadan Taylor, in addition to first-time swimmer Renee Michaud.
This was also Justice Pollard’s 20th swim, a pretty substantial milestone.
We did this one with not much tidal assist, starting only 15 minutes after dead low. Maybe next year we’ll go against the tide! No, no, just kidding.
In other news, we missed those of you that couldn’t make it. Come back next year!
Swimmers:
Ahren Michaud
Charlotte Clews
John Clements
Julie Forsyth
Justice Pollard
Liadan Taylor
Lucy Lawther
Mark Read
Mary Clews
Renee Michaud
Inimitable and priceless support crew:
Andy Wanning
Anika Clements
Charlotte Taylor
Charlotte Weir
Guy Ardrey
Hal Clews
Henry Becton
Jeannie Becton
Neddy Clews
Wing Taylor
A special mention here goes to the Becton crew, who arrived with hot chocolate and pastries at the moment above all others in the year when they are most most needed. Thanks so much!
Many thanks to Andy Wanning and Anika Clements for the pictures that appear here.
Finally, and this is very very literally true, this event would almost certainly NOT have happened without Mary Clews, who herded the mackerel into the chute successfully.
I don’t have time to write an actual essay here, so I’m just going to take a 5-minute break from what I should actually be doing to share with all of you (my millions of adoring readers) a thought that I’m having while teaching engineering non-majors how to program.
To wit: For the last fifty years, cleverness has been extremely important in programming a computer.
But that’s not really true any more, at least not for the vast majority of programmers.
But we still teach computer science like it is.
And I’ll stop starting my sentences with conjunctions now.
In the 1950s, 1960s, and 1970s, computers were generally speaking slow and small; fitting your desired computation into the time and space afforded by computation was a challenge. Programmers had to come up with clever encodings and clever algorithms. They did!
Now, in the 202s, computers are very large and very fast, compared to the programs that most of us want to run. There are exceptions, of course; weather simulations and “high-energy physics” still want as much computing power as they can get. Most of our computing tasks, though, are relatively more modest.
Unfortunately, we haven’t yet figured out how to teach programming in ways that focus on correctness and reliability.
Honestly, I think that’s because most of our teachers are still much more interested in working on problems that exercise their cleverness. There’s a strong parallel here to Math; for many math faculty, teaching a Calc 1 class doesn’t sound fun; there may not be much that’s challenging or interesting about the material, and much of the work is oriented around nurturing and caring for young minds, rather than inventing new and magical ways of thinking.
In computer science (which in many ways is just applied math), we haven’t yet reached this state, for the simple reason that we still have not developed the tools that allow people to efficiently generate correct and reliable programs. In other words, it’s not too late for cleverness! That cleverness, though, must be directed not at the students, teaching them how to write clever programs in complex and interesting languages; instead, it must be directed at the tools and materials that surround those students; we need to develop programming tools and teaching methods that efficiently endow those young minds with the ability to generate correct and
Another year! The 2021 swim is in the books. I must say, I’m still looking for a name for this event. Long Island Challenge is (it turns out) not a unique name. Granite Mon is unique but also very … dated? Also, a lot of the rock here isn’t granite. Okay, this isn’t a puzzle I can solve on my own.
Anyhow, predictions of a terrifying cold blob… did not come to pass. It was apparently very very cold (54F?) a few weeks ago, but the day itself—that would be yesterday—dawned cool and glassy with water that was just fine. It may be that in my dotage I have lost my ability to detect cold water, but I would have guessed 70s. Others said 60s.
The turnout was spectactular. We had fourteen swimmers, a new record! Here’s the list:
Alice Clements
Amanda Herman
Chris Guinness
George Pendle
Jerome Lawther
John Clements
Julie Forsyth
Justin Pollard
Lane Lucas
Lucy Lawther
Mark Read
Mary Clews
Pat Starkey
Tricia Sawyer
We had two new first-time swimmers, Julie Forsyth and, in the first ever intergenerational transfer, Lucy Lawther.
As always, there are many many people who get up at the crack of dawn in order to make this amazing thing happen. This year, that list included these amazing people and probably others that I’ve neglected to include (but lif so, let me know!):
Peaceful disagreement is the foundation of our American government.
It is not surprising that we disagree with each other. Each of us has individual opinions, circumstances, and understanding. Each of us sees a different part of the problems that surround us. Each of us has a different insight into the world, and sees different things that need to change.
And, for better or worse, pretty much all of us are justifiably angry about some aspect of government and society.
Our great virtue, as a nation, is that we have the ability to set that rancor aside; to suspend our anger, and to use the democratic process to decide upon a path forward. I don’t use the word “agreement”, because we may never truly agree. Fortunately, our nation and our government do not depend on our ability to agree with each other. They depend only on our ability to participate peacefully in a democratic process.
It has worked well since 1776. I have faith (and I do mean faith) that it will continue to work, and that America—the greatest nation on Earth—will continue to thrive and prosper, creating peace and prosperity and allowing each of us the pursuit of happiness.
So, this post isn’t very timely: hopefully COVID–19 will soon go away and we’ll all return to forms of education that actually work.
In the meantime, though, I’ve been learning things about online testing.
It probably goes without saying that there are many many differences between taking tests online and taking tests in person.
However, one of them that hadn’t occurred to me until very recently was how much more difficult it is… to not cheat.
Here’s what I mean. When you’re taking an in-person test in a classroom setting, your basic task is to focus your attention on your own desk. I’m not saying that’s easy for everyone, but I’ve come to realize that online testing presents an incredibly different experience.
Specifically, I think it’s safe to assume that most of the people in my courses taking exams still have their phones on. And what do you do if you’re taking a quiz, and you get a message from a friend, begging for help on a particular problem? You have to either deliberately snub them, or actually tell them “no”. Both of those are kind of hostile.
What this means is that we’ve taken an environment in which it’s incredibly easy to insulate yourself from those trying to cheat, and turned it into one where the burden is on those who don’t want to cheat to actively reject those who do.
So, I’m guessing that this is incredibly obvious to all of my students, but it sure wasn’t to me.
Is there an easy solution? Well, my easy solution would just be to turn off my phone during the test. But I suppose I wouldn’t do that unless the possibility of being asked for my answers occurred to me beforehand.
And, of course, this does absolutely nothing for the problem of students that actively conspire ahead of time to cheat.
So, although it’s a little late to do this now—the exam is in two days, and we can’t really discuss it in person—I’m going to make this suggestion now: please just turn off your phone and put it in another room, for the duration of the test?
