Physicist Amok

I spent a little time this morning looking into source control management systems. Today I watched Linus Torvalds’s talk at Google. I’m going to use Git, for the same reason that C is still a standby in programming.

C is a terrible language. Compared to its contemporaries (ALGOL 68, Lisp 1.5, Smalltalk) it’s primitive. Compared to today’s top languages (Haskell, ML, Scheme) it seems ludicrous. C has something these languages lack. It is the codification of how a couple of smart and experienced programmers liked to write assembly. It provides support where its designers wanted support, and nowhere else. Such a language can never be planned or designed, nor should it, but it provides something to fall back if you can’t find a clean language appropriate for your project.

Git represents Linus implementing a system to support how he wants to do source code control, based on years of a large and particularly chaotic development process. Developing software within a laboratory is chaotic and unstructured. I have trusted Linus for years on the kernel of my operating system. I’ll trust him on version control.

The only other thing of real interest out there is darcs, which is version control based on a theory of patches as noncommuting operations in analogy to Hermitian operators in quantum mechanics. Intellectually, it’s very exciting, but I have become jaded and bitter and I need to finish my PhD, not mess with beautiful computer science.

I don’t want to write raw Java again, but I need to write ImageJ plugins. I’m on the hunt for a new language.

Almost a year ago, I wrote an interface between Kawa and ImageJ, but ImageJ’s design precludes giving Kawa the type annotations it needs to make the interface reasonably fast.

I am no longer appalled by languages like Java. They are muck heaps. The last good language in this family was ALGOL 68. I am appalled by Scala. It tries to be a modern language while still poking its tendrils into the muck heap, but managing the muck has contaminated the language.

Certain things tell me I have been in Haskell too long. I am mildly disturbed by assigning types as values. The case classes, which try to be algebraic data types, miss the point, since you can’t check if functions over them are total.

The primary horrors:

Covariant/contravariant types: Java isn’t strongly typed. You can cast a String to an Object, assign it an integer, and the compiler cannot tell. To escape this, Scala introduces covariant/contravariant types.

Consider the function cons :: a -> [a] -> [a]. The first argument can be any subclass of a. We call it "covariant." The second argument, any superclass of a works in the list. It is "contravariant."

The best solution is to remove inheritance entirely, but the muck monster won’t talk to anyone without inheritance.

Implicit parameters: A library call returns a list. You want to use it as a set, which you have set up as a subclass of list. Write a function which converts lists to sets, annotate it with the implicit keyword, and then you can happily treat the library’s return value as a set.

There are two uses for this. One lets you create typeclasses by defining "traits" (Java interfaces with arbitrary restrictions removed) and then implicitly coercing everything you want into this trait. The other lets you add fields and methods to existing classes and objects.

In the first use, the only claim the creators advance for this approach instead of typeclasses is that implicit parameters are scoped. I learned my lesson about implicit things when I had to maintain a large Perl code base, but this makes the implicit conversions in Perl look like child’s play.

The second use is ludicrous. In Smalltalk, if I want to extend a predefined class C with a method f, I just assign the function body to the field f of C. I can only use the public interface of C, so it isn’t dangerous.

Last night it occurred to me that, although I knew Landau’s derivation of conservation of energy in Lagrangian mechanics, I had never seen it done from Newton’s third law. A few minutes of scribbling produced a proof that might be of use to some poor physics student somewhere.

The overarching theme is Noether’s theorem. Consider some problem described by a differential equation (or an action principle, but for now let’s stay with differential equations), which has some continuous symmetry. The rotations that leave a square unchanged are a discrete symmetry. All displacements in time of a system which does not depend on any particular position in time are a continuous symmetry. Essentially, if we can construct a continuous function from the transformations to the real numbers, then it is a continuous symmetry.

Our program: change coordinates in the differential equation until the symmetry transformations we’re interested in are represented by a displacement in a single coordinate. For time displacement, this is simple. For spatial displacement, we use Cartesian coordinates with one axis along the direction of displacement. For rotation, we use polar coordinates.

Shift the coordinate infinitesimally, and Taylor expand to first order. For any solution of the differential equation, the zeroth order expansion cancels. Taylor’s remainder theorem makes the second and higher orders smaller than the first order, so to have invariance, the first order must vanish. The invariance must hold for different infinitesimal displacements, so the first order coefficient must vanish, and we may multiply this by something nonzero to get a cleaner form at the end. The integral of the first order coefficient with respect to the coordinate is a constant, then we integrate everything in sight by parts and occasionally use the original differential equation to substitute for things until we find a convenient form. The last part sounds vague, and it is. I don’t know if there is some algebraic structure that will yield an algorithm for getting clean, useable forms for conservation laws. How did I find this particular set of integrations and multipliers? I played around until it worked.

Conservation of energy comes from invariance under a displacement in time. Begin with Newton’s third law, . I use for the total time derivative. This is not the same as the partials, as (where is the partial derivative with respect to the argument). Let .

The first terms on each side are equal by the original differential equation, and they cancel. Now we multiply by sides by and rearrange to get

This must hold for different, nonzero values of , so the quantity in brackets must be zero.

Aside: There is a subtlety to note: it is also zero before we threw in the , so it remains zero after we multiply by , so long as the particle isn’t at infinity. If we were not already garunteed this, then we would have to set up the coordinates where was never zero. This requires symmetry under spatial displacement (which yields conservation of momentum), and the fact that in any finite time interval there are points which are not visited by the path. The whole of the path over infinite time may visit all the points in the space (this is called ergodicity), but we can break the whole of time into connected subsets, each of which have an unvisited point, prove it on each subset, and then stitch them together. Spaces where we can do this slicing and stitching are called manifolds, and we’ll use this trick later.

Now we integrate with respect to time. Integration by parts on the first term yields (everything is multiplied by , but we’ll just put it back in later):

There’s kinetic energy. The other term will cancel after we analyze the second integral.

where the next to last line follows by replacing the force with the mass times accelleration from Newton’s third law. Now we combine these, putting that we neglected in the first part back in. The [Unparseable or potentially dangerous latex formula. Error 5 : 573x40]

There’s conservation of energy. Now a few remarks to tie things up:

Remark. The second term looks unfamiliar. Try changing variables so that position is independent and time depends on it. This must be done carefully! If the path intersects itself, we break the integration into a sum of integrals over intervals of time where the path does not self-intersect, and change variables separately in each one so that is well defined. On any such interval , we get a term that looks like , which is more familiar.

Remark. If our force has the form , then the second integral takes the form . For potentials which are independent of time, this is particularly useful as the second integral vanishes. For many oscillating potentials, the integral takes on an average value over long times.

For extra credit, go learn the quantum calculus analog of Taylor expansion (John Baez has a nice description) and do the same thing for discrete symmetries.

There’s been a lot of controversy around James Watson over the last couple of days, to the point where emails have been flying around the Rockefeller University talking about boycotting his receipt of the Lewis Thomas Prize for Writing. I haven’t read his book, I find his statements somewhat ridiculous, and worse, I don’t think he actually made that big a contribution, even aside from stealing data. I think two points are enough:

1. Schrodinger wrote What is life? in 1944, nine years before the Watson and Crick paper, and laid out what was necessary for a molecule that carried hereditary structure. With the discovery of DNA methylation and other modifications, it’s become more and more clear that the pure double helix isn’t the sole carrier of hereditary character. Yes, it was nice to actually know what the molecule was, but it wasn’t one of the most important discoveries of the 20th century. The evolutionary synthesis was. The new quantum mechanics was. The structure of this molecule was not. It was a technical tour de force at the time, but Watson and Crick didn’t even do that.

2. I see far too many descriptions of figuring out the rough structure of DNA as “cracking the secrets of life.” It did no such thing. Before Watson and Crick, we knew that it was a polymer (Levene, 1919); we knew that it carried heritable structure (Avery, 1943); we knew that heritable structure was laid out linearly along the polymer (Morgan, no later than 1915). Crick laid out the “central dogma” of molecular biology in 1957, and everyone dug in and figured out how the encodings worked. The structure of DNA was a pleasant thing to have in your head for doing this, but the classical geneticists had been doing very well without such structures for many years. Unfortunately, having such a structure immediately made lots of people confuse genes (heritable traits, alleles of which are selected in evolution) with ORFs (pieces of DNA transcribed into RNA).

I’ve poked at the Cantos for years.
finally, made up my mind.
Ezra Pound:
anti-semite, lunatic;
remarkable literary technician - lousy poet;
a great work by formula.
the result?
the Michelin guide to literature.
perhaps useful to the touring poet.
There’s damnation by faint praise!
The young composer must come to grips
with Pierrot Lunaire and the Rite of Spring.

To start, a question: why are the expositions of Landau and Lifshitz compelling? Here are ten volumes, without data. Compare them to any number of disastrous texts with an equal amount of data. Why does Landau & Lifshitz leave us credulous and so many others make us peery?

I think the answer is physical intuition. Chapters one and two of Mechanics set forth are a reference on physical intuition. A physicist believe the world has this shape, or one near to it, no matter what object we embed. For the next four volumes we get physics justified only from this intuition, and then the first chapter of volume 5 - Statistical Physics - hammers in the next piece of intuition: here is how many particles behave. The road forward is probabilistic.

These are the preconceptions a physicist carries with him into biology, where at first they seem to fail him. Some physicists become cynical and jettison this baggage (often at the behest of some biologists). Others refuse and build models that fail, fail, and fail again.

Step back for a moment. Imagine a physicist who has internalized the intuition in Mechanics but not in Statistical Physics. What is his fate? Feynman tells us (Feynman Lectures on Physics, vol.1, p.39-2):

“Anyone who wants to analyze the properties of matter in a real problem might want to start by writing down the fundamental equations and then try to solve them mathematically. Although there are people who try to use such an approach, these people are the failures of the field; the real successes come to those who start from a physical point of view, people who have a rough idea where they are going and then begin by making the right kind of approximations, knowing what is big and what is small in a given complicated situation.”

In other words, don’t neglect the first chapter of Landau and Lifshitz, vol.5.

What must we bolt onto our intuition to handle biology? The key is in Dobzhansky’s statement “Nothing in biology makes sense except in the light of evolution.”

A biologist tells a physicist, “When you have enough of X, this happens.” The naive physicist takes this literally: there exists a concentration of X at which something physically happens. But the mechanism in question probably exists in several related species, from different environments, all of which rely on similar versions of X. X probably is transcribed at different levels, into a different environment, and yet the system functions roughly the same.

More importantly, the system had to evolve, and the system had to function in all the environments leading up to the present. This is what we must add to our intuition. Exact fixed points and thresholds don’t happen. Now when we hear, “When you have enough of X, this happens,” from a biologist we filter it to, “In a bunch of organisms and places, some level of increase of X causes this to happen.” We do this with (as-is) absurd statements about mechanics and ensembles of particles every day.

This can be made rigorous in the same way as the pieces of Landau and Lifshitz. I suspect that evolutionary game theory of some form may be the proper language to express this.

What follows is abject navel gazing.

I originally studied physics. I did a lot of mathematics. I dabbled in computer science (and programmed a lot, which is something else). Now I’m immersed in biology. What do I call myself when someone asks?

These days, a mathematician.

This strikes me as odd: I don’t define my occupation by what I work on. But I think I finally understand why.

Here is the best definition I know of a physicist: someone who has been through Jackson’s E&M. If you survived it, you cemented a mindset shared by a community. In physics, everything is about time series. Anything not about time series is a statistical property of a time series.

In biology — not biophysics — trees are the natural unit. The logic of genetics deals in trees. Time series are awkward and dangerous. If we go to behavior and psychology, even the tree is inadequate.

After I settled into biology, I found myself with two deep mental frameworks, one next to the other. I spend a lot of thought trying to mesh them, and I have not yet managed it.

But wait! This is half of mathematics. Gian-Carlo Rota pointed out that axiomatic frameworks in mathematics are a sort of “hardware” for a “software” of mathematical facts. Lisp wizards who think of programs as abstract, nigh Platonic objects will interpret this the way I mean it; I hesitate to throw this analogy to anyone used to a FORTRAN descended language. A new mathematical fact is desirable; a new framework that brings known facts closer to trivial is just as novel. It itself is a mathematical fact. This way lies category theory.

The scientific equivalent of a stateless expatriate is a mathematician.

The authors of Real World Haskell just posted the first drafts for reviewers, including me. Much of the book is spent trying to explain simple concepts, while addressing the subtleties that result from Haskell’s shorthands and abstracctions. Something occurred to me as I was reading: the easiest way to learn Haskell is to learn some Lisp.

But not traditional Lisp. This Lisp is lazy, has nothing but symbols, lists, and tuples, and enforces the type differences among them. There is a let form but no define, certainly no setq. It’s lambdas are curryable. The whole realm can be explored, its lessons learned, in a couple of days.

It’s a useless language, except for its purpose. It is Limbo to Haskell’s Inferno — not Haskell itself, but sitting on the edge, where the virtuous of the past go who did not survive to the monadic revolution…

After developing the patterns of lists and lambda calculus, and the basic habits of strong typing, in this realm, the first descent into Haskell is fast. In ten minutes, you discuss the slightly changed notation, point out that we have entirely hidden the underlying cons structure of the list, and arrive at the type system.

Now the type system is an obvious extension of a habit to handle this new, more complicated world. The first unexpected structure is the algebraic data type, a transformation of a piece of BNF. I think this is the only place in computer science where the BNF is the clearest way to teach something.

Then there’s a bumpy half an hour about the syntax for defining functions, a period of clarity in general but confusion in detail about type classes, and then you arrive at

MONADS

And I don’t know how to make this one easy. sigfpe has made the beginning clear, but the rest is still obscure.

On the other hand, if a newcomer picked up a book on Haskell and was told that they were going to spend two chapters learning a dialect of Lisp they would never use again, it might not sell well.

Larry Wall taught us the three great virtues: laziness, hubris, and ego. I have long cultivated this in my life, and continue to do so now that I am a biologist.

My latest act of virtue (or perhaps virtù) involves selecting restriction enzymes for some cloning. Starting with a plasmid and a sequence I want to replicate in it, I need enzymes A, B, C, D, E, and X with the following properties:

• A and B have compatible ends, but when those two ends are ligated, none of the enzymes can recut them.
• None of the others have compatible ends.
• A must appear one time in the plasmid without the insert.
• B and C must not appear in the plasmid.
• D, E, and X must appear one time in the plasmid.

Don’t worry about where these rules come from for now. I’ll explain another time. Instead, let us focus on my tool for laziness: Prolog. In Prolog, you write down a set of logical propositions and rules, and then query them. This sounds fairly trivial, but it’s in fact really, really useful.

I typed in NEB’s compatible cohesive ends table for their restriction enzymes, which consisted of many lines that looked like this:

compatible(spei, [avrii,nhei,styi,xbai], [bfai]).

This is an example of a fact in prolog. It consists of a label for the fact (compatible), and a series of arguments. The first argument is the enzyme, the second is the list of compatible enzymes (lists are enclosed in [], and the entries are separated by commas), and the third is the list of enzymes that recleave such a ligation. I can create as many facts as I like with the same label and different arguments. In this case, it’s one for every line of that NEB table. Then I can define rules which let Prolog derive more facts from the simple facts I have given it:

is_compatible(X,X) :- true.
is_compatible(X,Y) :- compatible(X,F,_), member(Y,F).

The first line says that any sites cleaved by the same enzyme are compatible. The second says two enzymes are compatible is the second is a member of the list of compatible enzymes of the first.

is_incompatible(X,Y) :- \+ is_compatible(X,Y).

And to be incompatible, they must not be compatible (\+ is ‘not’ in Prolog). Here’s another predicate which is fairly straightforwards:

is_recleaved_by(A,A,A) :- true.
is_recleaved_by(X,Y,Z) :- compatible(X,G,F),member(Y,G),member(Z,F).

Then I put in the list of the restriction enzymes I have on hand: ncutter(aatii). and so forth. I also declare two lists for sites in the plasmid: restriction sites which appear once in the plasmid, and sites that do not appear in the plasmid (among those enzymes I have on hand):

m361_1([aatii, ecori, hindiii, hpai, kpni, mlui, ndei, nhei, noti, pvuii, spei, sphi, xhoi, xmni]).
m361_0([asci, ecorv, ncoi, paci, sbfi, scai, sfoi, snabi]).
And some convenience predicates so I don’t have to dig into the lists all the time:

singleM361(A) :- m361_1(B), member(A,B).
zeroM361(A) :- m361_0(B), member(A,B).

As an exercise, try to figure out what these do:

unrecleavable_pair(A,B) :-
is_compatible(A,B),
\+ is_recleaved_by(A,B,A),
\+ is_recleaved_by(A,B,B).

incompatible_set([_]) :- true.
incompatible_set([X,Y|Xs]) :-
incompatible_with(X,[Y|Xs]),
incompatible_set([Y|Xs]).

Then I encode most of my rules into one query:

enzyme_set(A,B,C,X) :-
ncutter(A), ncutter(B),
unrecleavable_pair(A,B),
ncutter(C), ncutter(X),
incompatible_set([A,C,X]),
incompatible_set([B,C,X]).

Now I ask for sets of A, B, C, and X which work:

?- enzyme_set(A,B,C,X), singleM361(A), singleM361(X), zeroM361(B), zeroM361(C).

Prolog gives me every possible set. I look at my plasmid map and pick one that seems reasonable (A=MluI, B=AscI, C=EcoRV, X=AatII). Then I cheat a bit, look for a pair of enzymes in the polylinker that only appear once in the plasmid, and which are incompatible with everything else (which I check in Prolog as well).

It’s not as automated as it could be, nor is it elegant, but compare this to searching through enzymes descriptions by hand! Nor should you be intimidated by the language. I began this with a bare minimum of Prolog, which I picked up in about two hours by reading the first three chapters of Clocksin and Mellish’s Programming in Prolog.

Peter Norvig has addressed this question. Eric Raymond has his nice essay on the subject. But these don’t provide much guidance for the beginner who wants to know “which books do I sit down and churn through?”

The short answer: The Haskell Road to Maths, Logic, and Programming by Doets and van Eijck (what appears to be an earlier draft is available in PDF here), and then Abelson and Sussman’s Structure and Interpretation of Computer Programs (also available online).

The long answer:

Until you understand what Abelson and Sussman are about in their book, you’re missing the whole point of computer science. Peter Norvig wrote about it,

“…if you’re like me, you’re not looking for one more trick, rather you’re looking for a way of synthesizing what you already know and building a rich framework onto which you can add new learning over a career. That’s what SICP has done for me. I read a draft version of the book around 1982 and it changed the way I think about my profession.”

Unfortunately, SICP requires a fair degree of intellectual, indeed mathematical, maturity. That’s where Doets and van Eijck comes in. Hopefully it will guide you far enough up the slope where SICP makes sense.

After this, there remains only one development in programming languages which you won’t be able to take completely in stride: monads and all the apparatus around them. But that’s a story for another day.