Wednesday, May 03, 2006

Macro Madness

The macros -- and madness -- I'm referring to today have little to do with Lisp, except as a cautionary tale. No, I'm talking about TeX and LaTeX, the other major language famous for its macros. I format my English résumé and French C.V. using a motley collection of LaTeX packages that I've found over the years. The English version uses resume.sty, originally by Stephen Gildea, and dates from 1988! The French one uses Didier Varna's CurVepackage which, I've found, does a good job of outputting a C.V. in a French / European style. His C.V. is a lot sexier than mine, but one has to start somewhere.

The style I adapted (i.e., copied) from Didier puts the years of an activity in the margin of an entry, bold faces the job title and company, puts the city in normal type in parentheses, and starts right in with the description. A consulting company asked me for my C.V. in a different format: months and years of dates (not in the margin), company and city in bold, job title on the next line, followed by the job description in bullet points. For this long-time TeX amateur it seems vastly preferable to conditionalize this somehow rather than keeping two different version of a document around. In terms of CurVe, I need the prologue of each entry to expand differently in each version and do something about establishing a list environment for the consulting version. Given this input from my wrapper macro:

\Entry{août 1999}{août 2001}{Software Design Engineer}{Amazon.com}{Seattle
WA, États-Unis}{blah blah}

I want:

\entry[1999 -- 2001]{\textbf{Software Design Engineer, Amazon.com}
(Seattle WA, États-Unis)}{blah blah}

in the regular version and:

\entry{\textbf{août 1999 -- août 2001 Amazon.com, Seattle WA, États-Unis}\par%
\textbf{Software Design Engineer:} blah blah}

in the consulting version. This doesn't seem too bad, but there are two big complications:


  • If the years of the date are the same, I only want one year in the margin of the regular version;
  • I want to be able to write \now instead of a date and get "présent".

Furthermore, I wanted to save some typing and write dates like "août 2001" and not as parameters to a macro like \date{août}{2001} or, worse, as separate parameters to the \Entry macro. This is one of those little decisions that, in retrospect, are incredibly stupid and lead to disaster or, at best, a lot more work, but otherwise I wouldn't have anything to write about today.

Like good Lisp programmers we'll attack this in a top-down and bottom-up manner at the same time. Assuming an \ifcvstyle conditional that chooses between the two styles, the LaTeX code I wrote above suggests these definitions:

\ifcvstyle%
\newcommand{\Entry}[6]{%
\entry[\@years{#1}{#2}]{\textbf{#3, #4} (#5) #6}}%
\def\@@cvdate#1 #2\relax{#2}
\else%
\newcommand{\Entry}[6]{\entry{\textbf{#1 -- #2 #4, #5}\par\textbf{#3:} #6}}
\def\@@cvdate#1 #2\relax{#1 #2}
\fi
\newcommand\@years[2]{\ifthenelse{\equal{\cvdate{#1}}{\cvdate{#2}}}{%
\cvdate{#1}}{%
\cvdate{#1} -- \cvdate{#2}}}
\newcommand\cvdate[1]{\@cvdate#1\relax}

\ifthenelse is LaTeX's all-purpose conditional macro; here we use it to compare two strings because plain TeX can't do that itself. OK, this isn't too bad; we can choose the basic form of the parameters to \entry and pick apart the parts of the date using TeX's powerful if bizarre macro parsing capabilities. But what about \@date, which we haven't defined yet? That submacro checks if the date argument is equal to \now and either returns that or proceeds with the date parsing.

My first try at \@date was something like:

\newcommand\@cvdate[1]{\ifthenelse{\equal{#1}{\now}}{#1}{\@@cvdate#1}}%

The intent is to look at the first "token" (basically, character or control sequence beginning with backslash); if it is \now, just use that, otherwise put the token back and let \@@cvdate go to town. But this exploded in some cryptic way. We have to enter the shady world of TeX "expandability" to understand why.

It's somewhat obvious that TeX macro definitions are simply templates into which parameters are substituted, although of course these templates can contain arbitrarily complicated code. In the course of this template substitution, called "expansion" (duh), some evaluation can take place; for example, primitive conditionals such as our \ifcvstyle can be evaluated and expanded. But many, many things in TeX can not be, such as definitions made with \def, and assignments to registers, things that complex macros invariably do. A macro is said to be expandable if it produces its intended result only through expansion. Many macros require their parameters to be expandable because they pick apart the results through various clever tricks. So, back to \ifthenelse: it is an extremely complicated macro that is not expandable, but the arguments passed to the predicate in its test part must be! Our \@cvsdate is used in \@years in the test of an \ifthenelse and therefore needs to be expandable. Oh well, can't use \ifthenelse.

TeX's primitive conditionals are expandable, so let's try again:

\def\@cvdate#1{\ifx#1\now\now\else\@@cvdate#1\fi}

\ifx compares characters or tokens and expands them, so it will work fine. This seems like it should work, but it doesn't. Aargh! After using TeX's \tracingmacros feature, which, compared to Lisp's macroexpand, sucks, it becomes clear that the \fi token that should end the conditional is sucked into \@@cvdate as part of the parameters. WTF? It turns out that when TeX expands a conditional it doesn't just replace it with the tokens in the appropriate branch and proceed; instead it skips the unsuccessful branch and starts expanding the taken branch, eventually noticing the ending \else or \fi token and discarding it. But it can't notice this token at the time it is gathering tokens for the argument of a macro, because it ignores the meaning of most tokens at that time... are we totally screwed?

No, there's a TeX idiom for handling this situation, using the somewhat bizarre \expandafter primitive. \expandafter reads one token without expanding it, then reads the next and expands it (which could consume other tokens if it takes arguments), then puts the first token in front of that expansion and carries on. This sounds promising: we want TeX to find the end if the conditional without beginning the expansion of \@@cvdate. Here's the final version of \@cvdate:

\def\@cvdate#1{\ifx#1\now\now\else\expandafter\@@cvdate\expandafter#1\fi}

Note the double use of \expandafter. We have two tokens to save up and put after the end of the \ifx; you can chain together uses of \expandafter to save up multiple tokens like this.

To Lisp hackers this is absolute brain damage. We could just gloat about the superiority of our macro system, but that would miss the point. The TeX macro language is designed to be usable by authors, not necessarily technical, with a syntax that seems "natural." That's why TeX supports complex parsing of arguments, as in our \@@cvdate macro. Since most of the world now uses LaTeX that has a much more regular macro syntax by convention this power is now wasted on end users, but at least the thought is there. Furthermore, there is a balance between writing simple substitution abbreviations and macros, which is easy in TeX, and more complicated packages that are likely to be written by motivated hackers that will invest the time to learn all the obscure incantations. And some novice macro writers will inevitably be sucked into the second category... Finally, it must be remembered that TeX was developed 25 years ago on machines that were incredibly puny by today's standards, so perhaps the strict separation between expansion and evaluation made sense. And, the objective is to put glyphs on paper, not write cool programs: yet another design constraint.

I don't know if ultimately I saved any time with all this macrology, but I did learn something about TeX and macros in general. If you were going to write a Lispy typesetting program with an expansion mechanism that didn't suck, what would you do?

Saturday, February 25, 2006

Names Aren't Forever

Dan Barlow refers to an article I wrote once on naming CLOS slot accessors, so I had better respond. Dan notes that choosing the name of a slot accessor or generic function is somewhat commiting because the name is used more globally than in other languages like e.g., Perl where a "slot name" is quite local. Xach responds that if you don't like a name, you can always change it later. I basically agree with this, but I want to point out that in large programs it may be difficult with text-based search-and-replace to make sure you're changing all -- and only -- what you need. Here our Java and Smalltalk friends are ahead with all the refactoring bells and whistles that come with integrated environments these days. Slime, the preferred environment for Lisp programming in GNU Emacs, doesn't even have a notion of all the files in a system. It does do a pretty good job of tracking the home package of symbols in a Lisp source file, based on the in-package forms in the file. It would be a cool hack to write a rename-symbol-in-system elisp function that visits all the files in an ASDF system, searches for a symbol and renames it if it's the symbol we care about i.e., in the right package. I call on my minions to make it so!

Wednesday, February 01, 2006

Dark Teapots

Once I had a Common Lisp / OpenGL interface working in glouton, I of course wanted to render the classic computer graphics model, the Utah Teapot. Glut has a glutSolidTeapot function, so I slavishly translated the C code from Mesa, which defines a big array of Bezier surfaces and uses OpenGL evaluator functions to render them, into Lisp and let 'er rip.

And got this interesting image. You can make out the murky outline of teapot if you squint hard. What's going wrong? With new teapot code, a new foreign function interface for the OpenGL bindings, running in Lisp, rather a lot could be going wrong. And I spent an embarrassingly long time chasing down various blind alleys until I did what I should have done first: read the man page for glutSolidTeapot (in my defense, I was on vacation without a broad-band connection, so googling wasn't my first instinct). Hey look, there's a big "Bugs" section!.

It turns out that we're looking at the inside surfaces of the teapot. Because their surface normals point away from the light source behind the viewer's head they are very dark. But those surfaces are supposed to be culled, and furthermore, the front surfaces of the teapot should not be! OpenGL can use the order of a polygon's vertices to decide if a polygon is facing away from the eye point and can be discarded. By default the order is assumed to be counterclockwise. If we turn off back-face culling we get a normal image, but that's not a happy state of affairs. In order to display the Glut teapot, according to the man page, you must change the vertex order to clockwise with (glFrontFace GL_CW) and then everything's happy. Fair enough, but why?

There's an unfortunate interaction between the OpenGL functions for evaluating Bezier meshes and the "quad strip" primitives that they use to display the approximation of the mesh on the screen. The quad strip looks like this:
That is, the vertices v0, v1, v2, v3, v4, ... are fed to OpenGL using glVertexf and the quads are drawn using the vertex order given by the arrow, which in this image is counterclockwise, making these quads front-facing. Now, the mesh produced by OpenGL for a Bezier surface might look like this (sorry for the lame diagram!):

u and v are the parameters of the mesh and increase in the directions of the arrows. The glEvalMesh2 function proceeds in the u direction of the mesh creating quad strips. That is, if we start at u = 0 v = 0 (do I need MathML here?), then the first few coordinates of the first quad strip will be (0,0), (0,dv),(du,0),(du, dv),(2du,0),(2du,dv),... and then another strip will be started at (0,dv). But look again at the diagram of quad strips above; this vertex order produces quads that are facing away from the viewer! We can't reorder the points and put the origin of the mesh parameters at another corner of the mesh because the same thing can happen. We could try to swap u and v, but that causes another, worse problem: we're relying on the evaluator to generate surface normals for us, and the normal direction is defined by the cross product of du and dv on the mesh. The right-hand rule rules here; if we swap u and v, the normals will point away from us, which is also not good. Are we doomed to live with this cheesy clockwise order?

Well, no. Actually we don't have to evaluate the mesh from 0 to 1 in u in v: the glMap2f function takes arguments for the start and end values of u and v. If we evaluate v from 1 to 0:

(loop
with u-order = (u-order patch)
and v-order = (v-order patch)
for patch-list in (patches patch)
do (loop
for patch in patch-list
do (glMap2f GL_MAP2_VERTEX_3 0.0 1.0 3 u-order 1.0 0.0 12 v-order
patch)
(glEvalMesh2 type 0 grid 0 grid)))

then the vertices in the quad strips define quads with the proper orientation:



Yay! We have our teapot.

Monday, January 23, 2006

Munching on OpenGL in Common Lisp

First post! I wonder if those are the most common words in the first post to a blog. I'm going to skip the introductions and instead describe something I'm working on. Well, more like "hacking on" in the best sense of those words.

I've written a package called "glouton" (which means "glutton" in French; can't resist including "g" and "l" with a little cross-language action!) to do some OpenGL programming in Common Lisp. Now, if you believe what you read on comp.lang.lisp this is trivial, many bindings already exist, you can write your own bindings in an hour, etc. Whatever. I know about the "nameless bindings"
of Knut Arild Erstad, but they don't have a free license. I looked at SDL, concluded (possibly in error) that the Lisp OpenGL bindings weren't very complete, and moved on. But for me, the deal breaker in existing OpenGL bindings is that they don't work with CLX , the defacto X Windows library for Common Lisp. CLX doesn't use the C Xlib library at all; it opens a socket and makes protocol requests directly to the X server. OpenGL and GLX, on the other hand, use a combination of exchanges with the server via Xlib's connection and, in the sexiest implementations, direct manipulation of the graphics hardware, called "direct rendering." I'd really like to support direct rendering while still using CLX event handling and X requests if at all possible.

It turns out that a hack is possible. The X server returns integer IDs for all interesting resources to its clients; these IDs are valid across different connections to the X server, or even in different clients. So we can create two connections to the server, one through CLX and one using Xlib, create the window using one or the other, create a GLX context and make in current in Xlib, then set the event mask in CLX and get events for it in the CLX-based event loop. Some synchronization is necessary between the two connections, particularly after a :configure-notify event; it seems like you need to call XPending() or something on the Xlib connection in order to notify the GLX client side of a reconfiguration of the frame buffer size. This was all more-or-less working on a Macintosh PowerBook, in my first try, currently here.
And then I bought a laptop with an Nvidia graphics card, and things stopped working...

I was creating the window in CLX, which was quite easy, but the results I was now seeing were very flakey: sometimes an image would appear, sometimes it wouldn't sometimes it appear only after a few mouse clicks or resizes. I googled around to no great effect, finally finding a clue that all GLX objects have to exist in the same address space. Well, that doesn't really apply here, but I changed things around to create the window in Xlib (more involved), then look up the window in CLX and set an event mask for it to get events. TaDa! There'll be some pretty pictures up here in a later post.

At some point I'd like to dig into the sources for GLX and the drivers to see what's going on for real, but that's a project for another day. I hope this hack is portable and will continue to work!

Incidently, I first saw the two connection trick in code Gilbert Baumann wrote to interface McCLIM to Cairo. Mad props also to cffi, which is a really solid portable foreign function interface package.