TCLispers.org Up and Running June 15th, 2009
Patrick Stein

Just put up a little bit of a website for the Twin Cities Lisp User’s Group at tclispers.org. Right now, it’s light on content. I don’t expect it to be particularly high-volume. It should at least start accruing slides from meetings as we get more of those under our belts.

First TC Lispers Meeting A Success June 12th, 2009
Patrick Stein

The first meeting of the TC Lispers group was a big success, IMO. I was figuring on an attendance near 20. My estimate is that it was really right around 40. That left us a little cramped in the meeting room at the Cafe, but we managed. We also lost the room before the presentation portion of the meeting was completely done, so there wasn’t much time for mingling. Actually, there was apparently a patio where people mingled afterward. I didn’t see this and took off too early. Mea culpa.

The presentation at this first meeting was on NST (not an abbreviation or acronym, but a sound effect /unsst/) which is a testing framework for Common Lisp. John Maraist did the presentation. He was a lively presenter, definitely had a good grasp on some dark corners of Lisp (like exactly what’s involved in the underbelly of MOP). Being a Haskell hacker though, he had some strange opinion that Lisp would be better if only it had strong typing. Well, what can you do? I mean, it’s not like he kicks puppies, I suppose. 8^)

It was great to see so many Lispers at so many levels there. About six or seven folks worked at Honeywell at some point in the past. Apparently, Honeywell had lots of Lisp development at one point. Who knew? About six or seven folks (overlapping a bit with the previous group) currently work at SIFT. There were some University students, a University teacher, some Ruby folks who wanted to see what Lisp was all about, some Lisp hobbyists, some independent consultants, some folks who can get Lisp in under the radar in their jobs, and on and on.

The next meeting is going to be 6pm on Tuesday, July 14th at the Common Roots cafe on 26th and Lyndale in Minneapolis. The topic is not quite set yet, but it seems like it might be a series of short talks on introductory aspects of Lisp.

There’s much discussion going on on the mailing list about finding a bigger venue for August and onward. There’s much discussion about exact topics for next month’s meeting. If you’re able to make it to the Twin Cities on a Tuesday evening, mark your calendars and come on out.

(assert (>= tclispers-meeting +fun+))

Quaternions for Rotating, Scaling, and Translating Space June 11th, 2009
Patrick Stein

In earlier posts, I described how complex numbers can be used to rotate, scale, and translate the plane, how Clifford algebras can be used to rotate, scale, and translate the plane, and why I resorted to an awkward trick for the Clifford algebra rotations of the plane. In this post, I am going to explain what the quaternions are and describe how they can be used to represent a rotation in three-dimensional space.

What are the quaternions

Okay, remember how we got the complex numbers? We needed something that was the square root of negative one.

Now, imagine that you are Sir William Rowan Hamilton. The year is 1843. It is springtime. You know how to use the complex numbers to represent points in the plane. And, you know that when you do that, you can use complex numbers to rotate, scale, and translate the points. That’s all well and good, but you don’t live in a two-dimensional world. How are you going to do the same sort of thing with three-dimensional space? How are you going to multiply triples?

You spend months on this. If only you could say, How about I let there be another number that is different from i (and from -i) that has the same property that its square is negative one? You fight with this for months. You try to represent a point with coordinates (x,y,z) as x + yi + zj. But, nothing you come up with makes any sense.

Your kids are harassing you, Daddy, did you figure out how to multiply triples yet? You have to answer them every morning with a polite, No, not yet.

Then, you’re walking along the Royal Canal in Dublin. It’s mid-October already. My, how the year has flown by. Bam, it hits you. If you add a third number like i and j which is equal to i\cdot j, everything works out. You get so excited, that you carve your equations into a stone bridge over the canal:

i^2 = j^2 = k^2 = ijk = -1

Read the rest of this entry ⇒

What Was Up With That Rotation Trick? June 10th, 2009
Patrick Stein

In my prior post about using Clifford algebras to do plane rotations, I finished with a non-intuitive step at the end. Rather than multiplying on the right by an element representing a rotation of angle \theta, I multiplied on the left by an element representing a rotation of angle \frac{\theta}{2} and multiplied on the right by an element representing a rotation of angle -\frac{\theta}{2}.

Why did I do this? Well, I mentioned it would be awkward for the two-dimensional case, but that it will be important when we get to three or more dimensions. Well, work for a moment with \frac{\theta}{2} being a quarter rotation (ninety degrees, \frac{\pi}{2} radians). This means our total rotation is going to be a half turn (180 degrees, \pi radians).

For that \frac{\theta}{2}, r = e_1e_2 and so \overline{r} = -e_1e_2. Let’s just look at what it does to our unit vectors e_1 and e_2 to multiply on the left by r and on the right by \overline{r}.

For e_1, we get -e_1e_2e_1e_1e_2 = -e_1e_2e_2 = -e_1. Similarly, for e_2, we get -e_1e_2e_2e_1e_2 = -e_2.

So far, we were only working in two dimensions. As such, there wasn’t any e_3 to worry about. But, what if there were? What happens to the z-coordinate of something if you rotate things parallel to the xy-plane? It remains unchanged.

Well, what would happen if we multiplied e_3 on the right by \cos\theta + \sin\theta e_1e_2? We would end up with \cos\theta e_3 + \sin\theta e_3e_1e_2 = \cos\theta e_3 + \sin\theta e_1e_2e_3. We’ve ended up scaling e_3 and adding in a trivector e_1e_2e_3. We’ve made a mess.

Let’s try it instead with our trick. We’re going to start with -e_1e_2e_3e_1e_2. Every time we transpose elements with different subscripts, we flip the sign. Every time we get two elements next to each other with the same subscript, they cancel out. So, switching the e_3 with the second e_1, we get e_1e_2e_1e_3e_2. From there, we can switch the first two elements to get -e_2e_1e_1e_3e_2 which is just -e_2e_3e_2. We can switch the e_3 with the second e_2 to get: e_2e_2e_3 which is just e_3. So, our trick leaves e_3 unchanged.

In the above, there is nothing special about the subscript three. It would work for any subscript except one or two. So, the trick allows us to break the rotation up into two parts that still do what we want with e_1 and e_2 but leave our other directions unchanged (or, maybe it’s easier to think of them as changing them and then changing them right back).

A First Look at Relation Algebras by Games June 8th, 2009
Patrick Stein

On Saturday, I got Relation Algebras by Games by Hirsch and Hodkinson via Inter-Library Loan. I am still debating whether to use this book for a Study With Me blog series. I’ve only gotten through the preliminaries so far, so we’ll see.

From the title of the book, I was expecting the authors to take various games and use them to derive relation algebras. Instead, the authors are going to take several variants of one particular game and use them to show thing about pre-existing relation algebras or classes thereof. The approach sounds very much like Zero-knowledge proofs. I think I may have titled the book An Information Theoretic Approach To Relation Algebras.

The basic idea of the game is that there are two players: Abelard and Eloise. Eloise’s goal is to prove that her model of a relation algebra is complete. Abelard’s goal is to stump Eloise. On Abelard’s turn, he asks a question about Eloise’s model of the algebra. On Eloise’s turn, she adds whatever is needed to the model she’s presented thus far so that she can answer Abelard’s question. Abelard wins if he stumps Eloise. Eloise wins if she can answer every infinite series of questions Abelard poses.

This is an interesting concept. The two major variants seem to be: limiting the game to a certain number of rounds or limiting the blackboard space upon which the model is presented. In the prior, there are apparently situations where you can prove things like: If Eloise can win every game of length n, then she can win the infinite game. In the latter case, there may be turns where Eloise has to erase stuff from the board and put other stuff there. At any given time in the latter case, Eloise can only depend on what is on the board to answer Abelard’s question.

At the moment, I’m still trying to get my head around what kinds of things Abelard might ask and what kinds of things Eloise might answer. I’m also trying to think of what other sorts of open questions might benefit from this sort of reasoning. The Riemann hypothesis? The Goldbach conjecture?

RSS Feeds

l