Remembering all the things I forgot
Yesterday evening, John, Jacob (though not Jingleheimer-Schmidt) and I had a bull shoot for an hour and a half. We started out with John proposing a memory caching system which was intended to make garbage collection and blocking irrelevant. From there, the conversation natuarally progressed to online algorithms, cache-oblivious algorithms, religion, free will, consciousness, Searle’s Chinese Room argument, Chalmers’ Zombie Planet argument, qualia, logic-based representations of object-oriented programming, the lambda calculus, machine learning, finite discrete universes, quines, the Gödel processor, complexity theory, the No Free Lunch theorems, and probably some other topics that I’m forgetting. It was fantastic.
However, this, along with a couple other conversations this week, have showed me just how much I have forgotten since college. I couldn’t remember the phrase “competitive analysis” when we discussed online algorithms. I couldn’t come up with a representation of linked lists that supported the head and tail functions in the lambda calculus, and worse, I mixed up the S and K combinators and couldn’t even give the definition for what turned out to be the S combinator. Last week I mixed up pipelining and instruction-level parallelism, and couldn’t come up with the phrase, “speculative execution.” Last week at lunch I couldn’t come up with the formal definition of temperature (something about the kinetic energy of the molecules relative to each other and maybe the amplitude of the interatomic vibrations within the molecules, but what do you do if you have a singe atom?). Today I couldn’t explain why (if?) bending a piece of metal makes it harder but more brittle, or why bending a polymer makes it more maleable (though in my defense, I could explain the difference between stress and strain, and what a polymer is as well as a bunch of examples of polymers). I remember why the X combinator is important, but can’t give the definition for it or the Y combinator. Yesterday I realized that something I was working with was a metric space, but couldn’t remember anything useful about metric spaces (I got as far as knowing that the triangle inequality holds, but I didn’t remember anything else). I can no longer use LaGrange multipliers to optimize a quantity subject to a constraint (you need the two to have parallel tangents at the extrema, but I don’t remember how to find the slopes of these tangents). Last week I forgot the name of Topological Sort, let alone how it works (something related to DFS, but that’s all I came up with).
Now that I’m writing this, I’m noticing all sorts of other things that I used to know but can’t quite remember (how Java does garbage collection, queen-asking continuations in Roman Keycard Blackwood, how the telephone lab in Baby Stems worked). It’s scary to realize how much I’ve already forgotten, and know that I’m only going to forget more things from here on out. Does anyone want to have a refresher session? If so, post your questions (or answers) here!
The Gödel processor spends half its time running your code and half its time looking for proofs that faster-running code has the same output as the code you gave it. If it finds a faster-running program, it stops running your code and switches to the faster algorithm. Given enough time, it will always find the provably fastest-running way to calculate whatever you’re trying to do. Since these proofs are independent of the size of the problem you’re calculating, they can be treated as a constant when calculating the running time, and the processor will always solve your problems with the best running time that can be proven. This is used to show that complexity analysis has some flaws, and in particular that constants matter when calculating running time.
Pipelining can occur when you have an instruction that takes more than one CPU cycle to complete. If your hardware is set up correctly, you can start a second (or third, etc) instruction in that circuitry before the first is finished. This is used in multiplies, divides, loads, and other long instructions. Instruction-level parallelism is when you have several different instructions that don’t depend on each other (such as an add, a multiply, and a load). You can execute them all in parallel because their order does not matter.
Speculative execution is a way of speeding up branching: instead of worrying about branch prediction, start executing the code for both branches, and then once you figure out which one you should have done, throw out the work you did on the wrong one and keep going on the right branch.