Zero G

I have to do this. I should be able to afford US$4,120 some day not too far into the future. Let me know if you want to go too

Creating a PDF for IEEE Xplore

I had to dig around for simple but non-obvious steps in order to get a paper to pass IEEE’s PDF eXpress validation tool, so I thought I’d share them. These steps are for latex/dvips/ps2pdf tools on windows.

First, if your paper size or margins appear incorrect in the .ps/pdf, (no matter what size you put on the dvips command line!), try adding the following to your .tex file after the \usepackage statements.

\special{papersize=8.5in,11in}

Next make sure the hyperref package is disabled since IEEE doesn’t like bookmarks, backrefs, or hyperlinks. If you use \url for formatting you can define your own replacement.

%\usepackage[...]{hyperref}
\newcommand{\url}[1]{{\small \tt #1}}

And finally page numbers should be disabled with the following

\pagestyle{empty} % disable page numbers
\begin{document}
...
\maketitle
\thispagestyle{empty} % spurious number on page 1

If your dvi looks fine, then force Type 1 (outline) fonts when converting to postscript via

> dvips -P pdf paper_final.dvi

and subset-embed all fonts (including standard ones) in the final PDF with

> ps2pdf -dEmbedAllFonts#true -dPDFSETTINGS#/printer
paper_final.ps paper_final.pdf

For some reason ps2pdf won’t embed standard fonts unless you output for `printer’. Add “-dAutoFilterColorImages#false -dColorImageFilter#/FlateEncode” to the command line if you want lossless image compression, or google “ColorImageDict” for nasty incantations that control JPEG compression quality.

Since hyperref is disabled, you can embed pdftitle and pdfauthor by adding the following after the papersize special if you really care.

\AtBeginDocument{%
\begingroup
\special{! /pdfmark where
{pop} {userdict /pdfmark /cleartomark load put} ifelse
[ /Author (Your Name Here)
/Title (Your Title Here)
/Subject (Booktitle Here)
/DOCINFO pdfmark
userdict /pdfmark /cleartomark load put
}
\endgroup
}

The Task of the Referee

A useful IEEE guideline for new referees in computing and engineering sciences. Discusses style, conferences versus journals, role of editors, irrelevant research, the importance of timeliness (appeal to the golden rule!), and how to get the most out of your own reviews.

“People who work in area X tend to believe that area X is inherently worthwhile. Referees who work in area X will usually evaluate papers in area X by the standards of area X; they will seldom, if ever, say that work in area X is pointless and should be discontinued. This is why an editor who wants to debunk a paper on alchemy sends the paper to a chemist, not an alchemist. Someone has to say the emperor has no clothes.”

Best thesis title ever

In a couple more years nobody will get this guy’s joke:

Computer Graphics Research Group Master’s Thesis Presentation

2008 Jan 15 at 15:30

DC2314

Snakes in the Plane

Paul Church, M.Math Candidate, David R. Cheriton School of Computer Science, University of Waterloo

History is cool

I just started reading A Radical Approach to Real Analysis by David M. Bressoud (there’s also a great preview at Google Books). The first lines contain a very encouraging quote,

The task of the educator is to make the child’s spirit pass again where its forefathers have gone, moving rapidly through certain stages but suppressing none of them. In this regard, the history of science must be our guide.

— Henri Poincaré

This is exactly what I was looking for: a text that weaves historical narrative into the theorems. If what I’m studying isn’t immediately intuitive to me, I always find that historical anecdotes help to keep me motivated and to have perspective on what ideas to are important. Besides, in this case it really is interesting to see examples of actual problems that motivated a revolution in mathematics.

Oh, and happy new year!

Human Computation

You may have heard of Luis von Ahn when all that ReCAPTCHA stuff was in the tech news a few months ago. Last summer he gave a Google TechTalk on using (not exploiting!) humans to solve hard computational problems, like labeling image data. It’s a really interesting area of research, especially the social aspects, and probably lots of cool stuff will be coming. Below is one slide he uses to put human effort into perspective… I love statistics like this…

I liked the first part of his talk, though if you already tried the “image labeling game” it gets boring when he goes over those details, but definitely start watching again at the 19:30 mark to see some interesting results and comments from players of that game. I also hadn’t heard of Peekaboom before and it’s très cool.

What I want for Christmas

Came across this awesome patent while searching for “high-rise parachute” (don’t ask). Check it out:

APPARATUS FOR SLOWLY AND SAFELY

DESCENDING FROM A HIGH-RISE BUILDING

[0013] Referring to FIGS. 1, 1A, 2, 6 and 6A, the present invention basically comprises a plurality of independent airbags 11, which are connected together to form an airbag jumpsuit 1. The jumpsuit 1 is composed of the airbags 11. A helmet 12 is connected and fixed on the top of the jumpsuit 1, a visor 13 is mounted on the front side of the helmet 12, a zipper 14 is fixed in the front side of the jumpsuit 1 in order for the user to wear the jumpsuit 1, and an air pipe 10 is connected to the jumpsuit 1 for filling air into the airbags 11.

A “very Googley” Waterloo

Check it out, Google is finally building a real development office near my alma mater, UW. At 9,000 square feet it’s not huge, but think of what this’ll mean to some lucky co-op students (who also won’t have to find a new place every 4 months).

Lamda expressions in C++0x

Argh, looks like the latest version of the proposal for C++ lambda expressions backs away from automatically inferring the types of the arguments from their usage inside the expression body. This means instead of this:

  std::list<std::vector<int>> l;

  int sum = std::accumulate(l.begin(), l.end(), 0,
      <>(s,v)( s + std::accumulate(v.begin(), v.end(), 0) )
      );

You’ll have to declare your lambda argument types explicitly, like this:

  std::list<std::vector<int>> l;

  int sum = std::accumulate(l.begin(), l.end(), 0,
      <>(int s, const std::vector<int>& v)
      ( s + std::accumulate(v.begin(), v.end(), 0) )
      );

Not the end of the world but redundant, verbose decltypes are one of the major things that hamper the expressiveness of C++ (I’ll just assume that’s a fact). The decision to cut back for C++0x was made with compiler implementers in mind, since apparently the ‘polymorphic’ lambda expressions would be too hard to get working. Having never hacked a C++ compiler myself, it’s hard for me to appreciate why this particular feature is be so difficult. On the surface it’s similar to the template type inference system and, as outlined in the June 2007 proposal (see Section 4), lambda expressions should be type checked at ‘coercion’-time (~specialization), either when called or when bound to a type-complete callable:

  int c = <>(a,b)(a < b ? a : b)(5,3);            // int a, b inferred

  auto incc = <>(x; &c)(x + c);

  auto d = incc(3.0);                             // double x inferred

  std::function<int(int)> fint = incc;            // int x inferred

  std::function<iterator(iterator)> fiter = incc; // iterator x inferred

  std::find_if(girls.begin(), girls.end(),     // const Girl& g inferred
           <>(g)(g.is_kind() && !g.likes_shopping()) );

At least the proposed ‘compromise’ is forward extensible in the future, but for now it’s hampered my enthusiasm for C++0x lambda expressions a bit. Being expressive in C++ often means working with unwieldy nested template types. The auto keyword fixes this for declarations (including of lambda closures), and there’s nothing they can do about arguments of regular non-templated methods, but a lambda expression’s type can and should be inferred anywhere at or below the lexical scope in which it was declared, so I don’t get why it was considered too ambitious for C++0x. Maybe there are lots of corner cases that are hard to get right, or something.

On a related subject, the other day I was wondering why the TR1 (i.e. boost) bind libraries don’t let me do something like this:

  bind<std::max> clamp(0, _1); // returns nonnegative via clamping

  clamp(-5); // instantiates std::max<int>

  clamp(-5.0); // instantiates std::max<double>

where the actual operation is instantiated at call time based on the arguments. This has the same problem with lexical scope as the polymorphic lambda expressions but what-evah. I tried to see how this might work (or rather was curious as to why it probably wouldn’t) so I wrote something like

  template <template <class T1> class F>
  struct bond1 {
     ...
     template <typename A1> // unary operator() for w/ arg1 bound
     typename tr1::result_of< F<A1> >::type operator()(const A1& a2) {
        return F<A1>(_bound_arg1, a2);
     }
  };

and tried to use it like above and… presto, a hard earned ICE. I love their shotgun advice:

  fatal error C1001: An internal error has occurred in the compiler.
  1>(compiler file 'msc1.cpp', line 1393)
  1> To work around this problem, try simplifying or changing the program
     near the locations listed above.

I tried just putting

   template <template <class T1> class F> struct bond1 { };

and without even instantiating I got the same ICE. What the? I’ve done this before in VS2003 with no problems — I must’ve confused the compiler via some earlier includes or something. Didn’t I just quote Stroustrup a couple of days ago about Microsoft’s C++ implementation being top notch? Oh well back to work.

C++0x intro by Stroustrup, at Waterloo!

How could I miss this?? I knew the standards meeting was happening in Toronto but CS at Waterloo managed to get Stroustrup to give this talk on C++0x in person. I should have figured out by now to keep an eye on guest speakers down the 401 at UW. Grrrrr self. If this post doesn’t make sense to you, browse the examples of what to expect on Wikipedia’s C++0x page and check out the working papers of the proposed standard.

He starts off with an overview of the ongoing WG21 meeting and the process by which standards are decided. Apparently you can buy a seat at the committee meetings (and vote) for $1200. Throughout the talk he keeps sniping at people who say performance doesn’t matter anymore, lol.

He talks briefly about how new language and library features are specifically designed to make programming for the latest “weird” computer architectures easier. I wish he’d focused on this instead of initialiser lists, because the new thread-local feature is a storage class specifier, not a type modifier, and I haven’t found any info on whether C++0x can help with the multiple-local-address-spaces memory model. Oh well I’m pretty ignorant on that front anyway.

Stroustrup makes an observation that I think applies to us all well beyond the world of programming and text editors:

“People don’t really want to argue about big things [like template type systems]. Now, if you discuss a for loop, you’ll get a really splendid discussion. If you start arguing about whether you should have a space in between the int and the star you get a really furious discussion. People love discussing things that don’t matter, because it’s so easy to have an opinion about those things.”

I love the way he says there’s lots of “gewde stoff” coming. Since I was too oblivious to be there in person I’m going to ‘live’-blog the rest of his talk, retroactively.

The technical stuff

38:20 Initialiser lists

Not super thrilling, but a clean, uniform new convention of using {} everywhere to initialise. Very worthwhile and probably easier to teach.

“If you have tedious, verbose and indirect code you make mistakes!”

46:30 Generic programming: The language is straining

“If you’ve ever seen some of the boost stuff… you don’t want to be that clever.”

Starts off with C++ Concepts. They’re checked at declaration time, not instantiation time (sweet). Adds the requires keyword, looks similar to C#’s where keyword for generics. Uses forward iterators as example. Concepts create a whole new infrastructure for introducing better error messages earlier. Zero compile time overhead.

66:00 Alias declarations and auto type declarations

Can finally avoid the “subclass and duplicate public interface” mess when trying to essentially bind some parameters of a template class.

The auto type inference (which in the case of variable declaration isn’t really inference at all) is SOOO sweet. I can’t wait.

69:00 Q & A session

- Thinks Microsoft’s implementation of C++ is one of the best, and that C++/CLI sucky sucky.

- “Will you ever design a new language?” His answer is so true…

“A lot of people design a new language to get a PhD or to get tenure, but if I do something [new] it will be to solve a real problem.”

- Concurrency should be done with standard libraries, built on a very thin layer of primitives.

- Expressed his disappointment at the lack of high level standard libraries (XML, networking etc).

- The 0x compilers will come very soon after 2009 because the standard is nearly feature complete (possibly by October 6th) and compiler/library venders have begun implementing almost every feature internally (except enum class).

81:00 - Talked about the new garbage collection standard and resource management in C++ versus C# (interesting fact: resources in C++ applications stay acquired for roughly half the time of C# applications). “Garbage collection is a performance virus” despite its advantages. I’ve always thought it had other disadvantages that go unacknowledged.

85:30 - Teaching 1st year undergrads C++ has inspired Stroustrup to write a textbook specifically for beginners, possibly coming out next year (!!)

85:40 - One student referred to consolidating template instantiations with a common void* implementation as “template hoisting,” which Stroustrup hadn’t even heard of so I guess I won’t bother using that name, though it would be nice if that practice had a name. He said that a few compilers DO detect this opportunity automatically (in the case of typed pointer arguments only); I wish he said which ones.

92:20 “Smart pointers are overused,” race conditions, and talks about the new std::unique_ptr class coming up (I wanted this in boost’s TR1, argh!).

Has not received death threats over language specs (that’s surprising, actually).

He likes underscores (gee, really!)