Seibel Peter. Coders at Work

Подождите немного. Документ загружается.

Guy Steele

365

Steele: I admit to being lazy—the first thing I will try is dropping in print

statements to see if it will help me, even though that is probably the least

effective for dealing with a complicated bug. But it does such a good job of

grabbing the simple bugs that it’s worth a try. On the other hand, one of the

great revelations in the evolution of my thinking about programming was

when I was working on that one project in Haskell. Because it was a purely

functional language, I couldn’t just drop in print statements.

This forced me to go 100 percent to a regimen of unit testing. So I

proceeded to construct thorough unit tests for each of my subprocedures.

And this turned out to be a very good discipline.

This has influenced the design of Fortress to try to include features that

would encourage the construction of unit tests. And recording them

alongside the program text, rather than in separate files. To that extent we

borrowed some ideas of say, Eiffel’s Design by Contract and similar things

where you can put preconditions and postconditions on procedures. There

are places where you can declare test data and unit-test procedures, and

then a test harness will take care of running those whenever you request.

Seibel: Since you just mentioned Design by Contract, how do you use

assertions in your own code?

Steele: I have a tendency to drop in assertions, particularly at the

beginnings of procedures and at important points along the way. And when

trying to—maybe “prove” is too strong a word—trying to justify to myself

the correctness of some code I will often think in terms of an invariant and

then prove that the invariant is maintained. I think that’s a fruitful way to

think about it.

Seibel: How about stepping through code in a debugger? Is that something

you’ll do if all else fails?

Steele: It depends on the length of the program. And of course you can

have tools that will help you to skip sections you don’t need to step through

because you’re confident that those parts are OK. And of course Common

Lisp has this very nice

STEP function, which is very helpful. I’ve stepped

through a lot of Common Lisp code. The ability to skip over particular

subroutines whose details you trust, of course, buys you a lot. Also the

Download at Boykma.Com

Guy Steele

366

ability to set traps and say, “I really don’t need to look at this until this

particular loop has gone around for the seventeenth time.” And there were

hardware tools to support that on the PDP-10, which was nice, at least at

MIT. They tended to modify their machines in those days, to add features.

And there’s a lot to be said for watching the actual execution of code in

various ways.

Seibel: Do you ever try to formally prove your code correct?

Steele: Well, it depends on the code. If I’m writing code with some kind of

tricky mathematical invariant I will go for a proof. I wouldn’t dream of

writing a sorting routine without constructing some kind of invariant and

proving it.

Seibel: Peter van der Linden in his book Expert C Programming has a sort of

dismissive chapter about proofs in which he shows a proof of something,

but then, ha ha, this proof has a bug in it.

Steele: Yes, indeed. Proofs can also have bugs.

Seibel: Are they at least less likely to have a bug than the code which they

are proving?

Steele: I think so, because you come at it in a different way and you use

different tools. You use proofs for the same reason you use data types, or

for the same reason that mountain climbers use ropes. If all is well, you

don’t need them. But they increase the chance of catching it if something

does go wrong.

Seibel: I suppose the really bad case would be if you had a bug in your

program and then a compensating bug in your proof. Hopefully that would

be rare.

Steele: That can happen. I’m not even sure it’s necessarily rare, because

you tend to construct the proof to match the structure of the code. Or

conversely, if you’ve got a proof in mind as you’re writing the code, that

tends to guide your construction of the program. So you really can’t say the

code and the proof are totally independent, in the probabilistic sense. But

you can bring different tools and different modes of thought to bear.

Download at Boykma.Com

Guy Steele

367

In particular, the details of the programming tend to take a local point of

view and the invariants tend to focus on the global point of view. It’s in

doing the proof that you cause those two things to interact. You look at

how the local steps of the program affect the global invariant you’re trying

to maintain.

One of the most interesting exercises in my career was the time I was

asked to review a paper for CACM by David Gries on proving a garbage-

collector algorithm correct, a parallel garbage collector. Susan Owicki was a

student of Gries’s and she developed some tools for proving parallel

programs correct, and he decided to apply these techniques to a version of

a parallel garbage collector that had been developed by Dijkstra. The whole

piece of code fit on, I think, a half a page. And then the entire rest of the

paper was the proof of correctness.

I cranked through the proof and tried to verify every step for myself. And

what makes it tricky is, in effect, every statement in the program has the

potential to violate any invariant because it’s a parallel program. So the

Owicki technique involves cross-checking these at all points. And it took me

about 25 hours to go through, and in the process I found a couple of steps I

couldn’t push through. So I reported this and it turned out they did

represent bugs in the algorithm.

Seibel: So they were bugs in the algorithm which the proof missed since

the result of the proof was, Q.E.D. this thing works.

Steele: Yes, the proof presented was a faulty proof. Because something had

been overlooked somewhere. It was some detail of formula manipulation—

the formula was almost right but not quite. And I think it was a matter of

correcting the order—the sequence of two statements or something.

Seibel: So it took you 25 hours to analyze the proof. Could you have found

the bug in the code in just 25 hours if you just had the code?

Steele: I doubt I would have even realized there was a bug. The algorithm

was sufficiently intricate that I would probably have stared at the code and

said, “Yeah, this makes sense to me” and not have spotted this very obscure

interaction. It was a multistep sequence that was necessary—a highly

unlikely interaction.

Download at Boykma.Com

Guy Steele

368

Seibel: And so that kind of interaction basically gets abstracted by the

process of making the proof so you don’t have to come up with this

scenario of what if this happens and then this and then this to realize that

there’s a problem.

Steele: Exactly. In effect the proof takes the global point of view and covers

all the possibilities, summarizing it in a very complicated formula. And you

have to do formula crunching to push it through. So the author resubmitted

the paper and it came back for rereviewing and even though I had done the

entire exercise, it took me another 25 hours to reverify the proof. This

time it all seemed to be sound.

I reported that and the paper was published and nobody’s found a bug in it

since. Is it actually bug-free? I don’t know. But I think having gone through

the exercise of the proof gives me a lot more confidence that the algorithm

is now sound. And I’m hoping that I wasn’t the only reviewer who actually

did the complete cranking through of the proof.

Seibel: There’s a Dijkstra quote about how you can’t prove by testing that

a program is bug-free, you can only prove that you failed to find any bugs

with your tests. But it sort of sounds the same way with a proof—you can’t

prove a program is bug-free with a proof—you can only prove that, as far as

you understand your own proof, it hasn’t turned up any bugs.

Steele: That’s true. Which is why there is a subspecialty in the discipline

having to do with mechanical proof verification. And the hope is that you

then reduce the problem to proving that the proof verifier is correct.

Which is—if you can write a small enough verifier—actually a much more

tractable problem that verifying the proof of any rather large program.

Seibel: And then the manually proved mechanical verifier would do the 25

hours of work you did of grinding out a verification of a specific proof of

some other piece of code?

Steele: Yes. Exactly.

Seibel: Is there anything that you would like to talk about?

Download at Boykma.Com

Guy Steele

369

Steele: Well, we haven’t talked that much about the beauty in programs,

and I wouldn’t want that to go without remark. I have read some programs

that really strike me as having a kind of beauty to them. TeX is one

example, the source code for TeX. METAFONT a little less so and I don’t

know whether it’s just because I use the program less or there’s something

subtly different about the organization of the code or about the design of

the program that I like less. I really can’t decide.

There are certain algorithms that strike me as just wonderful. I have seen

little pieces of program that were marvels of code compression back in the

days when that mattered—when you had only a megabyte of memory,

whether you used 40 words or 30 really mattered, and people would really

work hard sometimes to squeeze a program down. Bill Gosper wrote these

little four-line wonders that would do amazing things if you then connected

an amplifier to the low bits of some accumulator while it was twiddling the

bits.

This may seem like a terrible waste of my effort, but one of the most

satisfying moments in my career was when I realized that I had found a way

to shave one word off an 11-word program that Gosper had written. It was

at the expense of a very small amount of execution time, measured in

fractions of a machine cycle, but I actually found a way to shorten his code

by 1 word and it had only taken me 20 years to do it.

Seibel: So 20 years later you said, “Hey Bill, guess what?”

Steele: It wasn’t that I spent 20 years doing it, but suddenly after 20 years I

came back and looked at it again and suddenly had an insight I hadn’t had

before: I realized that by changing one of the op codes, it would also be a

floating point constant close enough to what I wanted, so I could use the

instruction both as an instruction and as a floating point constant.

Seibel: That’s straight out of “The Story of Mel, a Real Programmer.”

Steele: Yeah, exactly. It was one of those things. And, no, I wouldn’t want

to do it in real life, but it was the only time I’d managed to reduce some of

Gosper’s code. It felt like a real victory. And it was a beautiful piece of code.

It was a recursive subroutine for computing sines and cosines.

Download at Boykma.Com

Guy Steele

370

So that’s the kind of thing we worried about back then. When I

programmed on the IBM 1130, there was this concept of a boot card, which

is a single card you put on the front of your deck. You hit a start button on

the computer and the hardware would automatically read the first card and

put it in the first 80 locations in memory. And then start execution at a

given location. And the job of that card was then to be a real card-reader

routine to read the rest of the cards, and then that’s how you got yourself

bootstrapped.

What made it hard on the IBM 1130 was that cards have only 12 rows and

it was a 16-bit computer word. So the 12 bits were scattered throughout

the 16 bits of instructions, which meant that some instructions couldn’t be

represented on the card. Therefore any instructions that couldn’t be

represented on the card had to be built by using other instructions that

were on the card. So you had this very complicated trade-off—“What

instructions can I use, and if I use this instruction; I’m going to need several

other instructions on the card just to build it”—and this presented a

tremendous amount of pressure and you only got 80 words to write your

routine, and so you do tend to use things like reusing instructions as data,

using a piece of data for more than one thing. If you can manage to put this

little subroutine there in memory, then its address can also be used as a data

constant. This is what it took—it was origami and haiku and all that as a

style of programming. And I spent several years doing that.

Seibel: Do you think that people who went through that discipline are

better or worse programmers in the current environment?

Steele: They got experience at dealing with resource constraints and trying

to measure them accurately.

Seibel: Well, learning to measure them accurately is a good thing. But it

can also cut both ways where you develop habits of programming that are

now maladaptive.

Steele: It’s easy to become too fixated on optimizing something just

because you can, even though it’s not what you need to work on. That’s

indeed true. I’m glad that my son had the experience of programming TI

calculators when he was in high school. Because again, those had

moderately severe memory constraints. And so he had to learn how to

Download at Boykma.Com

Guy Steele

371

represent data in compressed forms to get it to fit in the calculator. I

wouldn’t want him to spend his whole programming career that way, but I

think it was a useful experience.

Seibel: Back to code beauty—that kind of haiku, origami programming is

beautiful for the reason that any intricate little thing is beautiful.

Steele: Yes. But I should emphasize that that piece of Gosper’s code is

beautiful not only because you can compress it in this way—one of the

reasons it’s so small to begin with is because it’s based on a beautiful

mathematical formula, a triple angle formula for the sine function. And that

recursion can be expressed very concisely on this particular architecture

because that architecture was designed to support recursion in a way that

other machines of its day weren’t. So there are several different aesthetics

melding together, combined in this one routine.

Seibel: You also mentioned Knuth’s TeX, which is obviously a much larger

program. What is it that makes that program beautiful?

Steele: He took a very, very complicated program with lots of special cases

and reduced it to a single, very simple paradigm: sticking boxes and glue

together. That was an immensely critical breakthrough. It turns out to be

flexible not only for typesetting text but for all manner of other things as

well that have to do with laying things out visually, two-dimensionally, on a

page. I wish that more GUI interfaces were based on boxes and glue for

laying out buttons and things like that.

Seibel: So there is beauty to be appreciated once you understand what

boxes and glue means, you can say, “Yeah, that’s a deep and righteous idea

and I appreciate the beauty of that and see how it would apply outside this

one program.” Is there further aesthetic quality that you get—and can only

get—by reading through the source code and seeing how that theme plays

out? Or is it more that you read the whole thing and then at the end you

say, “Wow, that was really all based on this one simple, but not simplistic,

idea.”?

Steele: It’s a combination of those. And Knuth is really good at telling a

story about code. When you read your way through The Art of Computer

Programming and you read your way through an algorithm, he’s explained it

Download at Boykma.Com

Guy Steele

372

to you and showed you some applications and given you some exercises to

work, and you feel like you’ve been led on a worthwhile journey. And

you’ve seen interesting sights along the way. Wandering through the code of

TeX I feel much the same way. I’ve learned some things about programming.

And some parts of them are mundane and perfunctory and so forth. And

other ones you say, “Wow, I didn’t think of organizing it that way.” It’s a

little of each.

Seibel: At the other end of the spectrum from code beauty, software is

also full of painful historical warts that we can’t get rid of, like differing line-

ending conventions.

Steele: Yes. We spent hours and hours in the Common Lisp committee

just debating the treatment of end of line in order to accommodate both

Unix, which used just newline, and the PDP-10 systems, which used CRLF.

And getting the definition of newline just right so it worked on both those

operating systems was a nightmare.

Seibel: So for the people who are reading this book and are going to be

writing some of the software of the future, is there any way to avoid that

stuff? Is there any way we can be smarter? Or is it just the nature of

evolutionary design?

Steele: Yeah. And not knowing the future. If I could change one thing—this

is going to sound stupid—but if I could go back in time and change one

thing, I might try to interest some early preliterate people in not using their

thumbs when they count. It could have been the standard, and it would have

made a whole lot of things easier in the modern era. On the other hand, we

have learned a lot from the struggle with the incompatibility of base-ten

with powers of two.

Download at Boykma.Com

C H A P T E R

Dan Ingalls

If Alan Kay is Smalltalk’s father, Dan Ingalls is its mother—Smalltalk may have

started as a gleam in Alan Kay’s eye, but Ingalls is the one who did the hard work

of bringing it into the world. Starting with the first implementation of Smalltalk,

written in BASIC and based on one page of notes from Kay, Ingalls has been

involved in implementing seven generations of Smalltalk from the first prototype to

the present-day open source implementation, Squeak.

Originally a physicist, Ingalls started programming with Fortran, made a business

selling a profiler he wrote while in grad school, and eventually found his way to

Xerox PARC, where he joined Kay’s Learning Research Group, which built

Smalltalk and explored the use of computers in children’s education.

While at PARC, Ingalls also invented the BitBlt operation used in bit-mapped

graphics and coded it in microcode for PARC’s Alto computer, allowing the high-

performance bit-mapped graphics that enabled UI innovations such as pop-up

menus that we now all take for granted. (At one of Ingalls’s in-house

demonstrations of the Smalltalk system, a pop-up menu caused the subject of my

next chapter, L Peter Deutsch, to leap to his feet and exclaim, “Did you just do

what I thought you did?”)

Now a Distinguished Engineer at Sun Microsystems, Ingalls is working on Lively

Kernel, a Smalltalk-like programming environment that runs completely in the

browser using JavaScript and browser-provided graphics. He received the

Download at Boykma.Com

Dan Ingalls

374

Association for Computing Machinery Grace Murray Hopper Award in 1984 and

the ACM Software System Award in 1987 for his work on Smalltalk. In 2002 he

won the Dr. Dobb’s Excellence in Programming Award.

In our conversation, we talked about the importance of interactive programming

environments, why it was a lucky thing he never learned Lisp, and why it’s better

to build flexible, dynamic systems and then lock them down rather than building

static systems and then trying to add dynamic features.

Seibel: To start at the start, how did you get involved in programming?

Ingalls: Let’s see. I grew up being an inventor in my basement, and physics

was the closest I could come to that so that was my college major. I went

to Harvard and there was a course on programming in Fortran, which I

took.

Seibel: What years would that have been?

Ingalls: I was at Harvard from ’62 to ’66. My two programming experiences

were this course on Fortran and there was a great lab in the basement of

one of the buildings where I took a course on analog computers. It makes

you think completely differently—you’ve got this big patch panel and then

just a bunch of circuits that are integrators, differentiators—things that you

can wire together to solve all sorts of problems in real time. But it began

with Fortran and I loved it from the get-go. I tried to see how much shorter

I could make programs, and stuff like that.

As a result I decided that maybe I was interested in electrical engineering.

So I came out to Stanford in double E and took some computer-science

courses there and really enjoyed that. I didn’t spend that much time with

double E. I got into Don Knuth’s course and he had a graduate course on

program measurement and I loved that. I actually worked on a program that

would analyze other programs and dropped out of Stanford to make a

business out of it. I got my master’s the next year, and then dropped out. So

we’re in ’68 now, I guess.

Seibel: So it was a PhD program you dropped out of?

Download at Boykma.Com