Retrograde Dynamic Tablature Assembly

It has been nearly 4 years since I wrote a post entitled “Things I Don’t Know”. After all this time, what is my progress on that list? Admittedly, I haven’t gone after the items in the list systematically. As is usually the case with a person’s interests, you follow up on some of them, and others fall by the wayside over time. In my case, I got more interested in programming language theory, and lost pretty much all interest in algorithms and computational complexity.

That is cool though, because when you’re doing your degree, at first the wide world of “Computer Science” seems so vast, you’re just interested in everything. As your knowledge catches up with the modern day, the state of any given field is more or less interesting to you, and for me, modern programming language theory is far more interesting than modern computational complexity. And so, I tended to lean in that direction in my studies.

But down to the list…

1.) “What monads are” Well this one was cleared up pretty much when I learned haskell. It’s of course very easy to understand the basic monad laws and therefore “understand what a monad is”, but if you aren’t actually using them to do some programming, it ends up being hard to get any intuition for what they are useful for.  The basic idea is that a monad is a wrapper type, or environment for some other data type. The basic operations of a monad are bind and return. Return just lets you wrap a value in the monad environment, and the bind operation allows you to chain together operations on the underlying data type, while preventing that datatype from escaping the monad. What bind does to chain together the operations is what makes the different monads interesting, and where they get their power.  Monads are good for IO in Haskell because Haskell is lazy, so sequential execution of side-effects is not guaranteed. The IO monad helps with this by giving an implicit sequence of actions. In order for the last IO action to be evaluated, the second-to last must be evaluated first, and so on, so that they are all causally linked and are therefore always executed in order. The IO monad also helps by not giving a way to pull values out of the IO environment and back into pure code (contrary to my previous understanding, side-effects aren’t avoided, just contained to the IO monad).

2.) “What currying is” I admitted in the original list that a brief trip to Wikipedia would have answered this one for me, but it turns out I really only got around to understanding it when I took a class on programming languages and we were learning how to use the functional language ML. Currying is essentially a way to make a function of multiple arguments into a function factory that takes the first argument and returns a new function that takes the next argument and so on. Only once all of the arguments are absorbed does the final result come out. Currying is possible in any language that has closures, but functional languages like Haskell and ML give you some very nice syntactic sugar to create curried functions.  In fact, it’s so easy, it’s rare for a function to be uncurried in Haskell (ML is a bit more mixed on the issue, with some standard library functions like fold taking uncurried helper functions).

3.) “What the minimal set of features for a Turing complete language are” Interesting that I put it this way, because it would be answered in almost that exact form when I took the aforementioned programming languages course. Of course, the pedantic answer is that if your language can simulate a Turing machine, then it is Turing complete. That is true, but not useful for evaluating a specific language quickly. It turns out that basically you need branching and looping (in an imperative language like C). Branching allows the machine to take different computation paths based on dynamic information, and looping allows the machine to return to a previous state, instead of being forced to move closer and closer to the end of the program. In other paradigms than imperative, instead of ifs and whiles, we look for features with similar abilities. In lambda calculus, these capabilities are handled by having first class functions and recursion. In object oriented languages, like featherweight Java (a language that strips object oriented languages to their core), you get branching by overloading in child classes, and looping by recursion again. If someone comes up with some radically different programming concept from these, looking for branching and looping is a good heuristic.

4.) “How to program in Smalltalk, Haskell, Scheme, Objective-C, OCaml, Tcl/Tk, Brainfuck, Befunge, and Python.”  Since the original post, I learned to program in Haskell, and Python quite well. To the point where I consider them both in my top 3 preferred languages. Smalltalk, Scheme, Objective-C, OCaml, Tcl/Tk, Brainfuck and Befunge are not really on my reading list, though perhaps another 4 years will change that.

5.) “How to program x86 with all the neat extensions like MMX, and SSE 1,2,3 etc. “  I still haven’t taken up learning x86, though I have had to dig through assembly dumps of some of my C programs from time to time, so I have a passing familiarity with it. I’ve taken a few intensive architecture courses since the original post, so my fascination with assembly language has waned somewhat due to it being less mysterious.

6.) “Whether P = NP “ Obviously, I still don’t know this for sure, but I feel a lot more confident understanding why the experts are doubtful that they are equal.  I also learned a bit about the results that depend on whether this is true or not, which makes you appreciate that it’s not just “we doubt these two classes are equivalent because we can’t come up with an example of an NP-complete problem that we have a polynomial-time algorithm for”, but rather that there are a web of interconnected results that all depend in one way or another on the answer, and that if P = NP, then it would mean a large number of unlikely results would come out of it. On their own, not necessarily a dealbreaker, but taken together it makes the prospects of P=NP very unlikely.

7.) “The exact relationship between time complexity and space complexity.”  Again, I haven’t learned any new universal equation that allows one to show how many extra megabytes of memory will be needed to shave a constant factor off of a time-complexity analysis, but it’s very likely such an exact equivalence doesn’t exist. As I stated above, my interest in algorithmics waned over time, but before I lost interest I did learn that PSPACE is a huge class, whereas P is relatively small (P being problems with solutions that take polynomial time, and PSPACE being problems with solutions that take polynomial amounts of space with no constraints on time). The problem with this discrepancy of proportion is that P is limited to polynomial space simply because you can only write to a polynomial amount of memory addresses in a polynomial number of steps. Space can be reused however, so polynomial space and unlimited time is a very powerful paradigm. If you give the ability to reuse time (like say in a computer that can send its results back in time to itself when the computation started), then you gain effectively polynomial space and infinite time.  It’s the difference between the arrow of time and the nature of space that gets us here.

8.) “enough about reversible computation.” Here is one area where I know almost exactly as much now as I did then. I think I perused a wikipedia article a year or so ago on the topic, but other than that, I still know very little about reversible computing. Although I have heard it is gaining more traction in architecture circles.

9.) “How to write a compiler.” By contrast, here is a topic I know truckloads more about. Mainly because I wrote a compiler as part of a compilers course I took. Lexing, Parsing, Type-Checking, optimization, Garbage collection and more are now in my list of things I understand.

10.)  “How to parallelize quicksort in Erlang.”  I still haven’t done it myself, but Wikipedia says it’s possible, although the speedup is only O(log n). Not worth it?

With that, I conclude my followup. But it wouldn’t be very interesting if I didn’t include a new top 10 list of “Things I don’t know 2011″.

Things I Don’t Know 2011:

1.) I really don’t understand Arrows all that well.

2.) Continuations give me a headache. I understand what they are, but I don’t have a good intuition about how to use callCC and such, or how the continuation monad gets its special powers under the covers.

3.) How dependent types work their magic. I can understand the basic Vec n type, but more complicated dependent types, and the foundational theory? Not so much

4.) How to program in Agda, Coq, Epigram, Ωmega, or Scala. Yes, I’m back to being interested in Scala.

5.) Whether type inference can be practical in a language without parametric polymorphism. Specifically, what is the best way to distinguish functionally identical types with different sizes (int16 versus int64)

6.)  Whether P = BPP. Ok there are a whole ton of these, but this one I might actually be interested in seeing the proof for (and it’s more likely to get one).

7.) Whether there is a way to randomly generate algebras with associative operations. Identity? Easy. Inverses? Easy enough. Operation associative? Aw mannnn… that’s hard.

8.) Whether there is a way to formalize the effectiveness of programming language features. It’s easy enough to prove correctness and type-safety, but how do you prove ease of use?

9.) The mathematics of quantum mechanics and quantum computing. Sure, we’ve all read the pop-science books about spooky action at a distance and double slit experiments, but how do physicists really model these things mathematically?

10.) What is best? Bears or beets?