[completed 2016-07-12] Oren Patashnik is well known as the creator of BibTeX; his graduate student days at Stanford overlapped with the TeX Project era and people.
[completed 2016-07-12]
Oren Patashnik is well known as the creator
of BibTeX; his graduate student days at Stanford overlapped with the
TeX Project era and people.
Dave Walden, interviewer: Please tell me a bit about your youth and education before Stanford.
Oren Patashnik, interviewee: I was born and raised in the Seattle area, growing up in Kirkland, a baseball-friendly suburb. Kirkland's 15 minutes of fame (expanded to an hour in 2010 by the ESPN 30-for-30 documentary Little Big Men) came in 1982 when the all-star team from the Kirkland National Little League, which I'd played in 16 years earlier, beat a heavily favored team from Taiwan to win the Little League World Series. It made national news, because in those days the team from the Far East routinely beat the U.S. team for the Little League world championship.
I attended Redmond High School, back when Redmond was closer to its farming days than its Microsoft days. My twin brother Ethan, who played on the 1966 Kirkland National all-star team — he was a better baseball player than I was — worked for many years at Microsoft (I don't necessarily agree with those who'd claim that that makes him the evil twin).
I went back east to college, Yale, graduating in 1976 in Mathematics and Computer Science. For my senior project I set out to prove that Qubic (4x4x4 tic-tac-toe) was, under optimal play, a win for the first player. People were interested in Qubic partly because of the February 1972 MIT AI Lab document HAKMEM. It had a list of twenty computational problems the authors thought were worth working on (I think Rich Schroeppel was the main creator of this list, Problems 77–96 on pages 30–35). Included in the list were some problems considered unfeasible, like chess and Go; the two hardest feasible problems, it said, were checkers and Qubic (Problem 92). Dan Hoey, who had seriously thought about the problem, was particularly encouraging, and pointed me to useful background information.
I graduated from Yale in May of 1976 short of a proof for Qubic, which was really too much for a senior project, but I stayed in New Haven for what turned out to be another year to work on it. My program ran on the Department PDP-10, and I was allowed to use the machine when it wasn't busy. (But far from complaining, I greatly appreciated access to the machine at all. At commercial rates — ten cents per kilo-core-second, I was told — the project would have cost about 50 million dollars.) Mostly I was competing for cycles with Roger Schank's AI graduate students. So I ran my program only late at night, and I had to put an alarm (many control-g's) into the code to wake me up when it needed input from me. And finally, early in the morning of Tuesday, May 24th, 1977, my program finished the search of a much condensed but complete game tree, proving Qubic a first-player win.
To support myself that year, I worked as a research assistant with some experimental psychologists. That led, the following year, to a job at Bell Labs in Murray Hill, NJ, also working with experimental psychologists. There I met Ron Graham, one of my eventual Concrete Mathematics coauthors. He put me in touch with Martin Gardner, who wanted to announce my Qubic proof in his Mathematical Games column in Scientific American if he could get someone to verify the proof. Any mathematical result needs verification, and for this result in particular he'd received many claims of proof that didn't stand up to scrutiny. Eventually Elwyn Berlekamp, who was working on the combinatorial games book Winning Ways with coauthors John Conway and Richard Guy, and who wanted to include the result in the book, got Ken Thompson, also at Bell Labs, to examine my game-tree data and verify that it was indeed correct and complete. Ken was one of the creators both of the Unix operating system and of Belle, which won the World Computer Chess Championship in 1980.
So I gave Ken a dictionary containing 2929 “strategic” moves — a very succinct distillation of the game tree — and he finished the verification in October 1978. Martin Gardner's announcement was a few months later in his January 1979 column (Scientific American, volume 240, number 1, pages 18–28), and Berlekamp, Conway, and Guy included the result in Winning Ways (chapter 22, Academic Press, 1982). My paper in Mathematics Magazine (volume 53, pages 202–216, September 1980) describes the proof.
DW: How long did you stay at Bell Labs?
OP: After three years at Bell Labs, grad school beckoned. I'd been debating between math and computer science, but computer science departments did the type of math I liked, so in the fall of 1980 I headed off to the Stanford CS Department. PhD students in the department typically got a research assistantship (RA) or teaching assistantship (TA) through a faculty member assigned to them in their intended area of study. There were 22 of us in our entering PhD class, as I recall, and Don Knuth was the faculty member assigned to me and to John Hobby (John was the one who, later, did MetaPost).
On my first RA project, I worked with Andy Bechtolsheim on a program involved in designing printed circuit boards. I don't know that anything useful came of my code, but eventually the project morphed into Sun Microsystems. The thing I do remember about that project was that I was writing code (in SAIL), that Monday evening, when our department's news ticker said that John Lennon had been shot.
During my second year, Ron Graham was visiting Stanford. He taught Knuth's Concrete Mathematics course in the fall of 1981, and I was the TA, which included writing up a full set of class notes. Ron and Don had for a while been planning a Concrete Math book based on the course, and after I TAed for Ron they thought I'd be a good person to synthesize a first pass of the book, using material from the decade that the course had existed. And I TAed the course again when Don taught it in the fall of 1984. By 1987 I had finished the first pass of the book. I wrote it in LaTeX, and when I gave it to Don — he became (and still is) keeper of the bits — he of course converted everything to TeX. Don and Ron then did their passes, including gobs of exercises, and Concrete Mathematics hit the presses at the end of 1988 (with a copyright date of 1989).
Eventually there was a second edition of the book (copyright 1994, four years after I graduated), for which my main job was updating the index. As many people know, Don likes to have people's full names in the index of his books, and there were a dozen or so people for whom we had incomplete names. The World Wide Web was in its infancy then, 1993, and it wasn't always easy tracking people down. My phone bill took a hit. I did have fun, though, for example getting to use my French in speaking with an operator in New Caledonia.
But the kicker was a fellow in Hyderabad, India, for whom we had only a first initial, D. The phone system there was erratic, accents were thick, and I wound up making 23 calls over several weeks. There also had been, shortly before I started calling, a tragic magnitude 6.2 earthquake in the area — a region that doesn't get many earthquakes — and almost 10,000 people died. Sprint, my phone company then, assumed with all those calls to India I must have had a friend or relative I was trying to reach, so they gave me a certificate to reimburse me: “We want to extend our sympathy during this difficult time, and hope this gesture will help in some small way.” Anyway, I did manage to track down his first name, Dekkata (Rameswar Rao), whose first three letters, coincidentally, are Don's initials.
But back to graduate school.
DW: Did BibTeX happen during that period?
OP: Yes. I'd started at Stanford in the fall of 1980, between versions of TeX that were called TeX78 and TeX82, and some students were pretty active in the TeX project. Knuth had a weekly informal discussion group about his work on TeX, and from my entering class alone John Hobby, Howard Trickey, Joe Weening, and Frank Yellin attended, and maybe others. But I wasn't one of them.
Instead, my work on BibTeX started in my third year. My paper from TUG 2003 (in TUGboat Volume 24, Number 1, pages 25–30) gives a pretty good history, so I won't repeat too much of it here. But it is fun to look at the original email, dated 9:08am on 15-Feb-83: “Oren, Leslie Lamport is working on a new macro package for TeX82, and needs someone to write a support program or two. We are volunteering you. His address is TEX82@SRI-CSL. Why don't you get in contact with him, and see whether his requirements are within the scope of what you're willing to do.”
It turns out I had met with Leslie weeks earlier. His macro package was called LaTeX by then (an earlier incarnation was PRETEX — a preprocessor for TeX), and it was similar in spirit to Brian Reid's Scribe system that he'd done at Carnegie Mellon in the late 1970s. I'd heard Brian give a very entertaining talk on it when I was at Bell Labs. Doing work for LaTeX sounded interesting.
I was to do the bibliography program, and it was originally described as a three-week project; but it grew. (I've been told that BibTeX was the third largest program written in WEB, behind TeX and Metafont, to come out of the TeX Project in the 1980s.)
My first working version of BibTeX came out in the summer of 1984. Besides BibTeX the program, there also needed to be bibliography styles. From a bibliography style designer's viewpoint, BibTeX interprets the instructions of the style (.bst) file, written in BibTeX's special .bst (postfix stack-based) language. Leslie Lamport had specified the first bibliography style, but it was Howard Trickey who did most of the work for what are now known as BibTeX's standard styles.
Between BibTeX's first working version in 1984 and BibTeX's first public release in March 1985, Howard and I had a good working relationship. Howard would tell me that for a style to do X more easily, the .bst language needed another primitive Y; so I'd add Y to BibTeX's .bst primitives. Bibliography styles today would be harder to program without Howard's influence.
And Howard and Joe Weening (along with Dave Fuchs, who entered the program two years earlier) were my go-to guys when I needed TeX advice.
Lots of people have done further BibTeX work since then — for example, Karl Berry wrote the btxmac macros to make BibTeX work with TeX, not just LaTeX (technically Karl and I maintain btxmac, though he does all the real work), and Nelson Beebe has greatly facilitated the use of BibTeX databases — but that's a glimpse of BibTeX's early days at Stanford.
Concrete Math and BibTeX were my two most time-consuming projects in grad school, and I continued working on both until shortly before I graduated.
DW: But those were not your thesis topic, right?
OP: Right, my thesis. It started as an RAship with Ed McCluskey in Electrical Engineering on a circuit-testing problem, which I looked at from a graph theory standpoint. Andy Yao was my thesis advisor. Unfortunately, he left Stanford in 1986 for Princeton; but fortunately, my wife's parents lived just half an hour from Princeton, so I could continue working on my thesis with him when we'd visit back east.
By the time I finished in 1990, my thesis (Optimal Circuit Segmentation for Pseudo-Exhaustive Testing) was the fifth largest thing I wrote in grad school. During my ten-year “tenure” at Stanford, I got married (I'd met my wife ten years earlier, at an NSF-sponsored summer program at Michigan State for high school juniors — we were both Mets fans) and had three kids.
Stanford was quite an idyllic place for grad students with families. Our back yard was an enclosed courtyard where our kids played with others from all over the world. And sports provided great entertainment. Stanford won its two NCAA baseball championships when we were there, and the women's basketball team came to national prominence then, winning their first NCAA championship the same month I turned in my thesis. Both Sunken Diamond (baseball) and Maples Pavilion (basketball) were five-minute walks from our apartment, and we took our kids there often.
The truth is, Stanford was the perfect place to raise a baseball fan then. Our oldest, Josh, was born October 1984 (the quarter I was TAing Concrete Math for Don Knuth and when I was trying to get the first public release of BibTeX out the door), and he was a very colicky baby. But the short walk to Sunken Diamond helped. The colic ended when he was five months old, but trips to Sunken Diamond continued, and by the time he was three he liked the baseball more than the snacks; we had a baseball fan. (Now he seems to bring baseball luck to wherever he goes: Stanford's only two NCAA baseball championships came when he was a toddler, the Red Sox broke the Curse of the Bambino and won the World Series in 2004 when he was in the Boston area for college, the San Francisco Giants won their first-ever World Series in 2010 when he was back at Stanford for law school, the Washington DC baseball team played in the post-season for the first time in 80 years the year he lived in DC, and then the Giants continued to win World Series when he came back to live in the Bay Area.)
Stanford grad-student life was idyllic, that is, except financially.
DW: What happened after Stanford?
OP: After graduating I went to work in San Diego at a math think tank (IDA Center for Communications Research) and I'm still here.
Perhaps the most interesting other thing I've done in San Diego is fire related. I'd been at Stanford when the Loma Prieta earthquake struck the Bay Area — I was sitting in a rocking chair with my two-year-old daughter at 5:04pm watching pre-game coverage of Game 3 of the 1989 World Series; my wife went out into the courtyard to make sure our son was okay. Though the damage to our apartment was negligible, when we went on our house-hunting trip to Southern California the next year, earthquake safety was on our minds. But in San Diego, it turns out, the main natural disaster is wildfires.
In October 2003 we went to freshman parents weekend back east for our older son. Our daughter and younger son were responsible kids, she'd just gotten her driver's license, what could go wrong? The Cedar Fire, the largest (by some accounts) in California recorded history, hit San Diego that weekend. Our kids and dog escaped, but 60% of the homes in our immediate neighborhood burned down (ours survived).
I wound up writing a statistical report on house survival in our neighborhood based on roof type. All the houses with wood (shake-shingle) roofs were destroyed, but surprisingly, the houses with Spanish-style curved-tile roofs (like this one) also did very badly, statistically speaking. Apparently, in these wind-driven wildfires, gaps between the curved tiles allow embers to infiltrate, smolder, and eventually burn down the house. Joe Mitchell, a physicist living in the Cedar Fire's path who devised an ingenious sprinkler system that wound up saving his house, saw my report and wanted to write a joint paper for the biennial Fire and Materials conference held in San Francisco. Our paper appeared in the 2007 conference proceedings, and since then I've attended that conference and kept up with the WUI (Wildland–Urban Interface) research people. I also wrote an op-ed for our local San Diego paper; punch line: it's the embers, stupid.
DW: Finally, BibTeX 0.99d is the current version; what about BibTeX 1.0?
OP: “Any decade now” is my standard reply. But seriously, 0.99d came out at the beginning of the decade in 2010, fixing a URL-handling bug, and I expect 1.0 around the end of the decade. I also expect some modernization updates to the standard styles within the next year.
DW: Thank you Oren for participating in our TUG interview series. I am going to miss our baseball talk that went along with our interview email exchanges.
