- 浏览: 95396 次
- 性别:
- 来自: 海底
最新评论
-
e421083458:
请问,有没有json转table的代码?
Lua 生成 Json -
arust:
天地有情 写道请教大侠,编程成功后的.exe文件里可以直接操作 ...
一个美丽的发现wxSQLite3 -
天地有情:
请教大侠,编程成功后的.exe文件里可以直接操作加解密的功能吗 ...
一个美丽的发现wxSQLite3 -
icefire:
就是喜欢这样的。我就重来不设环境变量,污染我的环境。而且很早 ...
有必要设操作系统环境变量吗? -
arust:
昨天,fceu 在 ports 中的原有目录已经被移除,更新为 ...
FreeBSD 下玩 FC 游戏
引用
Andrew Binstock and Donald Knuth converse on the success of open source, the problem with multicore architecture, the disappointing lack of interest in literate programming, the menace of reusable code, and that urban legend about winning a programming contest with a single compilation.
Andrew Binstock: You are one of the fathers of the open-source revolution, even if you aren’t widely heralded as such. You previously have stated that you released TeX as open source because of the problem of proprietary implementations at the time, and to invite corrections to the code—both of which are key drivers for open-source projects today. Have you been surprised by the success of open source since that time?
Donald Knuth: The success of open source code is perhaps the only thing in the computer field that hasn’t surprised me during the past several decades. But it still hasn’t reached its full potential; I believe that open-source programs will begin to be completely dominant as the economy moves more and more from products towards services, and as more and more volunteers arise to improve the code.
For example, open-source code can produce thousands of binaries, tuned perfectly to the configurations of individual users, whereas commercial software usually will exist in only a few versions. A generic binary executable file must include things like inefficient "sync" instructions that are totally inappropriate for many installations; such wastage goes away when the source code is highly configurable. This should be a huge win for open source.
Yet I think that a few programs, such as Adobe Photoshop, will always be superior to competitors like the Gimp—for some reason, I really don’t know why! I’m quite willing to pay good money for really good software, if I believe that it has been produced by the best programmers.
Remember, though, that my opinion on economic questions is highly suspect, since I’m just an educator and scientist. I understand almost nothing about the marketplace.
Andrew: A story states that you once entered a programming contest at Stanford (I believe) and you submitted the winning entry, which worked correctly after a single compilation. Is this story true? In that vein, today’s developers frequently build programs writing small code increments followed by immediate compilation and the creation and running of unit tests. What are your thoughts on this approach to software development?
Donald: The story you heard is typical of legends that are based on only a small kernel of truth. Here’s what actually happened: John McCarthy decided in 1971 to have a Memorial Day Programming Race. All of the contestants except me worked at his AI Lab up in the hills above Stanford, using the WAITS time-sharing system; I was down on the main campus, where the only computer available to me was a mainframe for which I had to punch cards and submit them for processing in batch mode. I used Wirth’s ALGOL W system (the predecessor of Pascal). My program didn’t work the first time, but fortunately I could use Ed Satterthwaite’s excellent offline debugging system for ALGOL W, so I needed only two runs. Meanwhile, the folks using WAITS couldn’t get enough machine cycles because their machine was so overloaded. (I think that the second-place finisher, using that "modern" approach, came in about an hour after I had submitted the winning entry with old-fangled methods.) It wasn’t a fair contest.
As to your real question, the idea of immediate compilation and "unit tests" appeals to me only rarely, when I’m feeling my way in a totally unknown environment and need feedback about what works and what doesn’t. Otherwise, lots of time is wasted on activities that I simply never need to perform or even think about. Nothing needs to be "mocked up."
Andrew: One of the emerging problems for developers, especially client-side developers, is changing their thinking to write programs in terms of threads. This concern, driven by the advent of inexpensive multicore PCs, surely will require that many algorithms be recast for multithreading, or at least to be thread-safe. So far, much of the work you’ve published for Volume 4 of The Art of Computer Programming (TAOCP) doesn’t seem to touch on this dimension. Do you expect to enter into problems of concurrency and parallel programming in upcoming work, especially since it would seem to be a natural fit with the combinatorial topics you’re currently working on?
Donald: The field of combinatorial algorithms is so vast that I’ll be lucky to pack its sequential aspects into three or four physical volumes, and I don’t think the sequential methods are ever going to be unimportant. Conversely, the half-life of parallel techniques is very short, because hardware changes rapidly and each new machine needs a somewhat different approach. So I decided long ago to stick to what I know best. Other people understand parallel machines much better than I do; programmers should listen to them, not me, for guidance on how to deal with simultaneity.
Andrew: Vendors of multicore processors have expressed frustration at the difficulty of moving developers to this model. As a former professor, what thoughts do you have on this transition and how to make it happen? Is it a question of proper tools, such as better native support for concurrency in languages, or of execution frameworks? Or are there other solutions?
Donald: I don’t want to duck your question entirely. I might as well flame a bit about my personal unhappiness with the current trend toward multicore architecture. To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks! I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the "Itanium" approach that was supposed to be so terrific—until it turned out that the wished-for compilers were basically impossible to write.
Let me put it this way: During the past 50 years, I’ve written well over a thousand programs, many of which have substantial size. I can’t think of even five of those programs that would have been enhanced noticeably by parallelism or multithreading. Surely, for example, multiple processors are no help to TeX.[1]
How many programmers do you know who are enthusiastic about these promised machines of the future? I hear almost nothing but grief from software people, although the hardware folks in our department assure me that I’m wrong.
I know that important applications for parallelism exist—rendering graphics, breaking codes, scanning images, simulating physical and biological processes, etc. But all these applications require dedicated code and special-purpose techniques, which will need to be changed substantially every few years.
Even if I knew enough about such methods to write about them in TAOCP, my time would be largely wasted, because soon there would be little reason for anybody to read those parts. (Similarly, when I prepare the third edition of Volume 3 I plan to rip out much of the material about how to sort on magnetic tapes. That stuff was once one of the hottest topics in the whole software field, but now it largely wastes paper when the book is printed.)
The machine I use today has dual processors. I get to use them both only when I’m running two independent jobs at the same time; that’s nice, but it happens only a few minutes every week. If I had four processors, or eight, or more, I still wouldn’t be any better off, considering the kind of work I do—even though I’m using my computer almost every day during most of the day. So why should I be so happy about the future that hardware vendors promise? They think a magic bullet will come along to make multicores speed up my kind of work; I think it’s a pipe dream. (No—that’s the wrong metaphor! "Pipelines" actually work for me, but threads don’t. Maybe the word I want is "bubble.")
From the opposite point of view, I do grant that web browsing probably will get better with multicores. I’ve been talking about my technical work, however, not recreation. I also admit that I haven’t got many bright ideas about what I wish hardware designers would provide instead of multicores, now that they’ve begun to hit a wall with respect to sequential computation. (But my MMIX design contains several ideas that would substantially improve the current performance of the kinds of programs that concern me most—at the cost of incompatibility with legacy x86 programs.)
Andrew: One of the few projects of yours that hasn’t been embraced by a widespread community is literate programming. What are your thoughts about why literate programming didn’t catch on? And is there anything you’d have done differently in retrospect regarding literate programming?
Donald: Literate programming is a very personal thing. I think it’s terrific, but that might well be because I’m a very strange person. It has tens of thousands of fans, but not millions.
In my experience, software created with literate programming has turned out to be significantly better than software developed in more traditional ways. Yet ordinary software is usually okay—I’d give it a grade of C (or maybe C++), but not F; hence, the traditional methods stay with us. Since they’re understood by a vast community of programmers, most people have no big incentive to change, just as I’m not motivated to learn Esperanto even though it might be preferable to English and German and French and Russian (if everybody switched).
Jon Bentley probably hit the nail on the head when he once was asked why literate programming hasn’t taken the whole world by storm. He observed that a small percentage of the world’s population is good at programming, and a small percentage is good at writing; apparently I am asking everybody to be in both subsets.
Yet to me, literate programming is certainly the most important thing that came out of the TeX project. Not only has it enabled me to write and maintain programs faster and more reliably than ever before, and been one of my greatest sources of joy since the 1980s—it has actually been indispensable at times. Some of my major programs, such as the MMIX meta-simulator, could not have been written with any other methodology that I’ve ever heard of. The complexity was simply too daunting for my limited brain to handle; without literate programming, the whole enterprise would have flopped miserably.
If people do discover nice ways to use the newfangled multithreaded machines, I would expect the discovery to come from people who routinely use literate programming. Literate programming is what you need to rise above the ordinary level of achievement. But I don’t believe in forcing ideas on anybody. If literate programming isn’t your style, please forget it and do what you like. If nobody likes it but me, let it die.
On a positive note, I’ve been pleased to discover that the conventions of CWEB are already standard equipment within preinstalled software such as Makefiles, when I get off-the-shelf Linux these days.
Andrew: In Fascicle 1 of Volume 1, you reintroduced the MMIX computer, which is the 64-bit upgrade to the venerable MIX machine comp-sci students have come to know over many years. You previously described MMIX in great detail in MMIXware. I’ve read portions of both books, but can’t tell whether the Fascicle updates or changes anything that appeared in MMIXware, or whether it’s a pure synopsis. Could you clarify?
Donald: Volume 1 Fascicle 1 is a programmer’s introduction, which includes instructive exercises and such things. The MMIXware book is a detailed reference manual, somewhat terse and dry, plus a bunch of literate programs that describe prototype software for people to build upon. Both books define the same computer (once the errata to MMIXware are incorporated from my website). For most readers of TAOCP, the first fascicle contains everything about MMIX that they’ll ever need or want to know.
I should point out, however, that MMIX isn’t a single machine; it’s an architecture with almost unlimited varieties of implementations, depending on different choices of functional units, different pipeline configurations, different approaches to multiple-instruction-issue, different ways to do branch prediction, different cache sizes, different strategies for cache replacement, different bus speeds, etc. Some instructions and/or registers can be emulated with software on "cheaper" versions of the hardware. And so on. It’s a test bed, all simulatable with my meta-simulator, even though advanced versions would be impossible to build effectively until another five years go by (and then we could ask for even further advances just by advancing the meta-simulator specs another notch).
Suppose you want to know if five separate multiplier units and/or three-way instruction issuing would speed up a given MMIX program. Or maybe the instruction and/or data cache could be made larger or smaller or more associative. Just fire up the meta-simulator and see what happens.
Andrew: As I suspect you don’t use unit testing with MMIXAL, could you step me through how you go about making sure that your code works correctly under a wide variety of conditions and inputs? If you have a specific work routine around verification, could you describe it?
Donald: Most examples of machine language code in TAOCP appear in Volumes 1-3; by the time we get to Volume 4, such low-level detail is largely unnecessary and we can work safely at a higher level of abstraction. Thus, I’ve needed to write only a dozen or so MMIX programs while preparing the opening parts of Volume 4, and they’re all pretty much toy programs—nothing substantial. For little things like that, I just use informal verification methods, based on the theory that I’ve written up for the book, together with the MMIXAL assembler and MMIX simulator that are readily available on the Net (and described in full detail in the MMIXware book).
That simulator includes debugging features like the ones I found so useful in Ed Satterthwaite’s system for ALGOL W, mentioned earlier. I always feel quite confident after checking a program with those tools.
Andrew: Despite its formulation many years ago, TeX is still thriving, primarily as the foundation for LaTeX. While TeX has been effectively frozen at your request, are there features that you would want to change or add to it, if you had the time and bandwidth? If so, what are the major items you add/change?
Donald: I believe changes to TeX would cause much more harm than good. Other people who want other features are creating their own systems, and I’ve always encouraged further development—except that nobody should give their program the same name as mine. I want to take permanent responsibility for TeX and Metafont, and for all the nitty-gritty things that affect existing documents that rely on my work, such as the precise dimensions of characters in the Computer Modern fonts.
Andrew: One of the little-discussed aspects of software development is how to do design work on software in a completely new domain. You were faced with this issue when you undertook TeX: No prior art was available to you as source code, and it was a domain in which you weren’t an expert. How did you approach the design, and how long did it take before you were comfortable entering into the coding portion?
Donald: That’s another good question! I’ve discussed the answer in great detail in Chapter 10 of my book Literate Programming, together with Chapters 1 and 2 of my book Digital Typography. I think that anybody who is really interested in this topic will enjoy reading those chapters. (See also Digital Typography Chapters 24 and 25 for the complete first and second drafts of my initial design of TeX in 1977.)
Andrew: The books on TeX and the program itself show a clear concern for limiting memory usage—an important problem for systems of that era. Today, the concern for memory usage in programs has more to do with cache sizes. As someone who has designed a processor in software, the issues of cache-aware and cache-oblivious algorithms surely must have crossed your radar screen. Is the role of processor caches on algorithm design something that you expect to cover, even if indirectly, in your upcoming work?
Donald: I mentioned earlier that MMIX provides a test bed for many varieties of cache. And it’s a software-implemented machine, so we can perform experiments that will be repeatable even a hundred years from now. Certainly the next editions of Volumes 1-3 will discuss the behavior of various basic algorithms with respect to different cache parameters.
In Volume 4 so far, I count about a dozen references to cache memory and cache-friendly approaches (not to mention a "memo cache," which is a different but related idea in software).
Andrew: What set of tools do you use today for writing TAOCP? Do you use TeX? LaTeX? CWEB? Word processor? And what do you use for the coding?
Donald: My general working style is to write everything first with pencil and paper, sitting beside a big wastebasket. Then I use Emacs to enter the text into my machine, using the conventions of TeX. I use tex, dvips, and gv to see the results, which appear on my screen almost instantaneously these days. I check my math with Mathematica.
I program every algorithm that’s discussed (so that I can thoroughly understand it) using CWEB, which works splendidly with the GDB debugger. I make the illustrations with MetaPost (or, in rare cases, on a Mac with Adobe Photoshop or Illustrator). I have some homemade tools, like my own spell-checker for TeX and CWEB within Emacs. I designed my own bitmap font for use with Emacs, because I hate the way the ASCII apostrophe and the left open quote have morphed into independent symbols that no longer match each other visually. I have special Emacs modes to help me classify all the tens of thousands of papers and notes in my files, and special Emacs keyboard shortcuts that make bookwriting a little bit like playing an organ. I prefer rxvt to xterm for terminal input. Since last December, I’ve been using a file backup system called backupfs, which meets my need beautifully to archive the daily state of every file.
According to the current directories on my machine, I’ve written 68 different CWEB programs so far this year. There were about 100 in 2007, 90 in 2006, 100 in 2005, 90 in 2004, etc. Furthermore, CWEB has an extremely convenient "change file" mechanism, with which I can rapidly create multiple versions and variations on a theme; so far in 2008 I’ve made 73 variations on those 68 themes. (Some of the variations are quite short, only a few bytes; others are 5KB or more. Some of the CWEB programs are quite substantial, like the 55-page BDD package that I completed in January.) Thus, you can see how important literate programming is in my life.
I currently use Ubuntu Linux, on a standalone laptop—it has no Internet connection. I occasionally carry flash memory drives between this machine and the Macs that I use for network surfing and graphics; but I trust my family jewels only to Linux. Incidentally, with Linux I much prefer the keyboard focus that I can get with classic FVWM to the GNOME and KDE environments that other people seem to like better. To each their own.
Andrew: You state in the preface of Fascicle 0 of Volume 4 of TAOCP that Volume 4 surely will comprise three volumes and possibly more. It’s clear from the text that you’re really enjoying writing on this topic. Given that, what is your confidence in the note posted on the TAOCP website that Volume 5 will see light of day by 2015?
Donald: If you check the Wayback Machine for previous incarnations of that web page, you will see that the number 2015 has not been constant.
You’re certainly correct that I’m having a ball writing up this material, because I keep running into fascinating facts that simply can’t be left out—even though more than half of my notes don’t make the final cut.
Precise time estimates are impossible, because I can’t tell until getting deep into each section how much of the stuff in my files is going to be really fundamental and how much of it is going to be irrelevant to my book or too advanced. A lot of the recent literature is academic one-upmanship of limited interest to me; authors these days often introduce arcane methods that outperform the simpler techniques only when the problem size exceeds the number of protons in the universe. Such algorithms could never be important in a real computer application. I read hundreds of such papers to see if they might contain nuggets for programmers, but most of them wind up getting short shrift.
From a scheduling standpoint, all I know at present is that I must someday digest a huge amount of material that I’ve been collecting and filing for 45 years. I gain important time by working in batch mode: I don’t read a paper in depth until I can deal with dozens of others on the same topic during the same week. When I finally am ready to read what has been collected about a topic, I might find out that I can zoom ahead because most of it is eminently forgettable for my purposes. On the other hand, I might discover that it’s fundamental and deserves weeks of study; then I’d have to edit my website and push that number 2015 closer to infinity.
Andrew: In late 2006, you were diagnosed with prostate cancer. How is your health today?
Donald: Naturally, the cancer will be a serious concern. I have superb doctors. At the moment I feel as healthy as ever, modulo being 70 years old. Words flow freely as I write TAOCP and as I write the literate programs that precede drafts of TAOCP. I wake up in the morning with ideas that please me, and some of those ideas actually please me also later in the day when I’ve entered them into my computer.
On the other hand, I willingly put myself in God’s hands with respect to how much more I’ll be able to do before cancer or heart disease or senility or whatever strikes. If I should unexpectedly die tomorrow, I’ll have no reason to complain, because my life has been incredibly blessed. Conversely, as long as I’m able to write about computer science, I intend to do my best to organize and expound upon the tens of thousands of technical papers that I’ve collected and made notes on since 1962.
Andrew: On your website, you mention that the Peoples Archive recently made a series of videos in which you reflect on your past life. In segment 93, "Advice to Young People," you advise that people shouldn’t do something simply because it’s trendy. As we know all too well, software development is as subject to fads as any other discipline. Can you give some examples that are currently in vogue, which developers shouldn’t adopt simply because they’re currently popular or because that’s the way they’re currently done? Would you care to identify important examples of this outside of software development?
Donald: Hmm. That question is almost contradictory, because I’m basically advising young people to listen to themselves rather than to others, and I’m one of the others. Almost every biography of every person whom you would like to emulate will say that he or she did many things against the "conventional wisdom" of the day.
Still, I hate to duck your questions even though I also hate to offend other people’s sensibilities—given that software methodology has always been akin to religion. With the caveat that there’s no reason anybody should care about the opinions of a computer scientist/mathematician like me regarding software development, let me just say that almost everything I’ve ever heard associated with the term "extreme programming" sounds like exactly the wrong way to go...with one exception. The exception is the idea of working in teams and reading each other’s code. That idea is crucial, and it might even mask out all the terrible aspects of extreme programming that alarm me.
I also must confess to a strong bias against the fashion for reusable code. To me, "re-editable code" is much, much better than an untouchable black box or toolkit. I could go on and on about this. If you’re totally convinced that reusable code is wonderful, I probably won’t be able to sway you anyway, but you’ll never convince me that reusable code isn’t mostly a menace.
Here’s a question that you may well have meant to ask: Why is the new book called Volume 4 Fascicle 0, instead of Volume 4 Fascicle 1? The answer is that computer programmers will understand that I wasn’t ready to begin writing Volume 4 of TAOCP at its true beginning point, because we know that the initialization of a program can’t be written until the program itself takes shape. So I started in 2005 with Volume 4 Fascicle 2, after which came Fascicles 3 and 4. (Think of Star Wars, which began with Episode 4.)
Finally I was psyched up to write the early parts, but I soon realized that the introductory sections needed to include much more stuff than would fit into a single fascicle. Therefore, remembering Dijkstra’s dictum that counting should begin at 0, I decided to launch Volume 4 with Fascicle 0. Look for Volume 4 Fascicle 1 later this year.
Footnote
[1] My colleague Kunle Olukotun points out that, if the usage of TeX became a major bottleneck so that people had a dozen processors and really needed to speed up their typesetting terrifically, a super-parallel version of TeX could be developed that uses "speculation" to typeset a dozen chapters at once: Each chapter could be typeset under the assumption that the previous chapters don’t do anything strange to mess up the default logic. If that assumption fails, we can fall back on the normal method of doing a chapter at a time; but in the majority of cases, when only normal typesetting was being invoked, the processing would indeed go 12 times faster. Users who cared about speed could adapt their behavior and use TeX in a disciplined way.
Andrew Binstock is the principal analyst at Pacific Data Works. He is a columnist for SD Times and senior contributing editor for InfoWorld magazine. His blog can be found at: http://binstock.blogspot.com.
引用
近日,Andrew Binstock和Donald Knuth对一些话题进行了交流,包括开放源代码运动,极限编程,多核架构,可重用代码,以及Knuth自己编程时使用的工具等。
Andrew:无论你当初并是否意识到了,你其实都是开放源代码运动的发起者之一。你以前就声明过将TeX作为开放源代码项目发布,原因在于考虑到当时专有现实(proprietary
implementations)的问题,并且希望邀请更多的人来修改代码中的错误——这些都是今天开源代码项目关键的驱动力。你为开源项目从那时起的成功惊讶过么?
Donald:或许开放源代码的成功是过去几十年中计算机领域里唯一没有使我惊讶的事。但是开源运动还没有发挥出全部的潜力;我相信在整个产业经济越来越多地从产品转移到服务上的过程中,开源程序将完全占领支配地位,同时会有越来越多的志愿者会参与改进代码的质量。
例如,开放源代码能带来数以千计的二进制包,可以完美地针对每个独立用户进行配置,但是商业软件通常只有几种版本。一个通用的二进制可执行文件必须包含很多指令来“抹平”不同运行环境间的差异,这对于很多安装环境来说并不合适;然而源代码是高度可配置的,因此这种浪费也就随之消失了。这是开源软件的巨大优势。
但是我认为有少数软件,比如Adobe公司的Photoshop,够能比它开源的竞争者更优秀(比如Gimp)——由于某些原因,我真的不知道为什么!我非常乐意花很多钱去买真正好的软件,前提是我确认它出自最佳的程序员之手。
不过请记住,我对于经济问题的观点非常不可靠,因为我只是个教育者和科学家。我对于市场几乎一无所知。
Andrew:我听说你曾经参加过一次在斯坦福举办的编程大赛,你最终提交的那个获奖的作品,只经过一次编译就能正确运行了。这件事是真的么?在软件领域里,当今的开发者需要频繁地构建程序,每次只增加很少量的代码,过程中要依赖即时编译技术,并且要创建并运行大量单元测试。你怎么看待这种软件开发方法?
Donald:你听说的这个故事是一个典型的传说,它只有一个很小的“内核”是真的。事情的实际经过是这样的:John McCarthy于1971年决定举办一场“纪念日编程大赛(Memorial Day Programming Race)”。当时除我以外的所有参赛者都工作于斯坦福后山的AI实验室中。他们共同使用WAITS分时系统;我对校本部很不满,因为我当时能够使用的唯一的计算机是一台大型主机,我必须为卡打孔,然后提交给主机,它会以批处理的模式进行处理。我使用Wirth的ALGOLW系统(Pascal语言的前身)。我的程序第一次并不能工作,但幸运的是我可以使用Ed Satterthwaite的那个出色的ALGOLW离线调试系统,因此我只是运行了两次程序。另一方面,使用WAITS的家伙们一直没有得到足够的处理器周期,因为他们的机器负载太大了(我想,第二个完成的那个人,尽管使用了“现代的”方法,还是比使用老式方法却最终取胜的我晚了一个小时)。这并不是一场公平的竞赛。
谈到你刚才的问题,即时编译和“单元测试”的想法对我的吸引力非常有限,尤其在我身处完全未知的环境中时,这时我需要反馈,以确定什么可以工作,什么不可以。否则,我会在不需要做的事情和不必思考的问题上浪费很多时间。没有什么是需要“伪装(mock up)”的。
Andrew:对于开发者,尤其是客户端开发者,正在面临一个日渐明显的问题,即改变他们的思考方式,从线程的角度去编写程序。这个问题是由廉价的多核PC的出现导致的。它一定需要很多算法进行多线程化的改造,至少也需要做到线程安全的。到目前为止,从你已经发布的《计算加程序设计的艺术》(TAOCP)第4卷的大部分内容来看,还没有涉及到这方面内容。你接下来的工作会和并发与并行程序设计有关么?尤其是这个问题天生就与你现在研究的组合算法非常适合。
Donald:组合算法的研究领域非常庞杂,而我将有幸在三或四卷书中介绍它串行方面的内容,我认为串行方法的重要性不会降低。相反,并行技术的“半衰期”其实非常短,因为硬件总在快速地变化,每一个新的机器都需要一些不同的方法。所以,很久以前我就决定在书中保留我最了解的内容。有很多人比我更了解并行机器,他们可以指导你如何面对同时性的问题;程序员应该听听他们的建议,而不是我的。
Andrew:很多多核处理器的供应商都在帮助开发者转移到多核模型的过程中,表现得力不从心。做为一名著名的教授,你对于这种转变有什么看法?什么因素才能促使这种转变?如果有更好的工具可以解决问题么,比如在语言中加入对并发更好的本地支持,或者使用框架?或者还有其他的方案么?
Donald:我不想回避你的问题。也许我个人的一些观点会为当前流行的多核架构趋势泼一盆冷水。在我看来,这种现象或多或少是由于硬件设计者已经无计可施了导致的,他们将Moore定律失效的责任推脱给软件开发者,而他们给我们的机器只是在某些指标上运行得更快了而已。如果多线程的想法被证明是失败的,我一点都不会感到惊讶,也许这比当年的Itanium还要糟糕——人们基本上无法开发出它所需要的编译器。
这么说吧:在过去的50年间,我编写过一千多个程序,其中有很多规模都很可观。但是如果说哪些程序的性能可以在并行或多核环境下有明显的改进,我恐怕连五个都说不来。比如,多核处理器对TeX肯定没有什么帮助。
你听说过有多少程序员对这种未来一片光明的机器抱有强烈的兴趣?我几乎没有听说过,除了他们的诉苦。尽管我们学院那些搞硬件的家伙一直想让我相信我是错的。
我知道有很多重要的应用依赖于并行——图形渲染、密码破解、图像扫描、物理与生物过程模拟等等。但是这些应用需要非常专业的代码以及特定用途的技术,而这些技术无疑每隔若干年都要变化。即使我对那些方法非常了解,可以把它们写入TAOCP中,这对于我的时间也是巨大的浪费,因为过不了多久,这部分内容就没有什么价值值得别人去读它了。(类似地,当我在准备第3卷的第三版时,也打算删除掉关于如何在磁带上排序的内容。这些内容曾经是软件领域里最热门的主题,现在再把它印在书中就是巨大的浪费了。)
我今天所用的机器有两个处理器。而我只有在同时运行两个独立的作业时,才会用到这两个处理器;这样很好,不过每周这种情况只会发生几分钟而已。如果我有四个、八个甚至更多的处理器,我同样得不到任何好处,想一想我是做什么的——我几乎每天每时每刻都在使用计算机。所以,我为什么要为硬件供应商承诺的未来而高兴?他们认为多核的到来可以为我的工作提速,我认为这是“白日梦”(pipe dream)。(不——这个比喻不准确!我是会用“Pipeline”的,但是不会用线程。也许我应该说这是个“泡影(bubble)”)
不过,我认为Web浏览器可能会由于多核的出现而有所改变。我是从技术性的工作,而不是消遣的角度在说。我也承认我还没有什么很好的想法,到底硬件设计者应该给我们除多核以外什么样的产品,不过他们现在在串行计算上的确遇到了麻烦。(但是我的MMIX设计中包含了很多考量,可以有效地提高我最关注的一些程序当前的性能——代价是与遗留的x86程序无法兼容。)
Andrew:软件开发领域中有一个很少被提及的问题:面对全新领域的软件,如何进行设计?当你着手开发TeX时,应该遇到过这样的问题:没有现成的源代码可以参考,而且在这个领域中你也不是专家。你是如何完成设计的?在你顺利地进入编码阶段以前,设计工作花了多少时间?
Donald:这又是一个好问题!我在《Literate Programming》一书的第10章、以及《Digital
Typography》一书的第1章和第2章中已经详尽的探讨了问题的答案。我相信任何对这个问题真正感兴趣的人都将乐于阅读这些章节。(还可以参考《Digital Typography》的第24和25两章,它包含了我在1977年做的TeX初始设计的第一版和第二版草稿。)
Andrew:关于TeX的书和程序自身都清楚地表现了对有限内存使用的考量——这是那个年代系统的一个重要问题。今天,对内存使用的关注则更多地与缓存大小有关了。每当有人设计出了新的处理器,你一定会关注“可感知缓存”和“缓存透明”的算法的问题。在你最近的工作里,你会谈论,或者只是间接地介绍一下,处理器缓存在算法设计中所扮演的角色么?
Donald:在前面我提到过,MMIX提供了实验的平台,可以在上面尝试多种不同的缓存。它是由软件来实现的机器,因此我们可以执行一些实验,它们从今天起在100年内都是可重复的。可以肯定的是,在新一版的TAOCP 1-3卷中,将会讨论在不同的缓存参数下,基本算法的不同行为。目前在第4卷中,我大约收集了十多个缓存内存和缓存友好的方法(更不用说“memo cache”了,这是一个与软件相关但又不同的概念)。
Andrew:你在编著TAOCP时都用到哪些工具了?你使用TeX?LaTeX?CWEB?Word?你在编程的时候使用哪些工具?
Donald:我通常的工作方式是用铅笔和纸先把所有东西都写下来,然后在旁边放一个大废纸篓。然后我使用 Emacs将所有文本键入到机器中,当时要使用TeX风格。我使用TeX、dvips和gv查看结果,它们几乎可以瞬时显示出来。我使用 Mathematica检查数学运算的结果。
我使用CWEB编写每一个经过讨论的算法(这样我才能充分地理解它),CWEB和GDB调试器简直是天作之合。我使用MetaPost制作插图(或者,在极少数的情况下,会在Mac上使用 Adobe Photoshop或Illustrator)。我有一些自己创作的工具,比如我自己的TeX拼写检查器和内置在Emacs的CWEB。我自己设计了在 Emacs中使用的位图字体。我还有一些特殊的Emacs模式(mode),可以帮助我对文件中的好几万份论文和笔记进行分类;特定的Emacs快捷键使得写书的过程有点儿像演奏风琴。我喜欢用rxvt作为终端输出的窗口。从去年12月开始,我使用了一个名为backupfs的文件备份系统。我每天都需要对每一个文件进行归档,backupfs非常适合我的需要。
根据我机器上当前的目录来看,今年我已经写了68个不同的CWEB程序。其他的,2007年有100个左右,2006年90个,2007年 100个,2004年90个。而且CWEB有一个非常方便的“改变文件”机制,这样我可以快速地为一个主题创建多个版本和修改了;在2008年,我目前为止已经在这68个主题上创建了73个修改。(有几个修改非常短,仅有几个字节;其他则达到了5KB甚至更多。有些CWEB程序非常重要,比如我完成于一月前的BDD包,它有55页。)因此,你可以看出文法式程序设计对于我有多么重要。
我现在正在一台独立的Laptop上(没有网络连接)使用Ubuntu Linux。我偶尔会使用闪存驱动在Ubuntu Linux和Macs之间搬运数据。我用后者接入网络和处理图像;但是我相信我的“传家宝”只有Linux而已。顺便提一句,相对于GNOME和KDE环境,我更习惯把注意力留在键盘上,这样我可以能够使用经典的FVWM。不过似乎有很多人更喜欢GNOME和KDE。每个人都有不同的爱好。
Andrew:在你的站点上,你提到在Peoples Archive上最近制作了一系列视频,在其中你回顾了过去的生活。在第93段“给年轻人的建议”中,你提醒人们不应该只是简单地因为某件事时髦就去做它。有一点我们都心知肚明,软件开发比起其他学科,在产生时髦技术上有过之而无不及。你能举出两个当前正在流行的技术么?对于这些技术,也许开发者不应该简单地因为它们当前很流行,或者他们正在使用,就欣然接受它们。你是否愿意再举几个软件开发范围以外的例子呢?
Donald:这个问题非常矛盾。我通常都是建议年轻人要相信自己的判断,而不是其他人。我就是“其他人” 中的一员。大概每一位你要效仿的“伟大人物”的传记上都会记载,他或她曾经向当时的“传统智慧”发起过挑战。虽然如此,我并不想回避这个问题,尽管我也不想触动其他人敏感的神经——有一种软件方法学已经类似于某种宗教了。首先声明:没有任何人有任何理应该听信我这种计算机科学家/数学家对于软件开发的种种评论。我要说的是,几乎每一件我听说过的与术语“极限编程”相关的事情,看起来都绝对是错误的...除了一点例外。这个例外就是“团队工作”和“互相阅读源代码”的思想。这个想法非常关键,甚至可以弥补极限编程中其他匪夷所思的方面。那些令我很不安。
我还必须承认我对“可重用代码”的流行保有强烈的偏见。对我来说,“可重编辑的代码”要远远胜于一个无法触及的黑盒或工具集。就这个问题我还可以不断地说下去。如果你对可重用代码深信不疑,我可能丝毫无法动摇你,但是你也无法让我相信,可重用代码并不总是麻烦制造者。
还有一个问题你可能会问到:为什么新书的名为“第4卷 分册0”,而不是“第4卷
分册1”?答案是:计算机程序员将会明白——我还没有准备好从真正的起点开始写TAOCP的第4卷,因为我们知道不能贸然决定程序的初始设定,除非程序已经自身已经基本成形。因此在2005年,我开始编写第4卷的分册2,而在此之前已经有了分册3和4(想想星球大战,它是从第4部开始的)。
最后,我做好心理准备,可以编写前面的部分了,但是不久我又意识到简介部分就需要包含很多内容,它更适合成为一个独立的分册。因此,还记得Dijkstra的名言么,计数应该从0开始,于是就有了第4卷的分册0。今年晚些时候第4卷的分册1可以和大家见面。
相关推荐
高德纳(D. E. Knuth)教授是备受尊崇的系列巨著《计算机程序设计艺术》(The Art of Computer Programming)和数十篇受到高度赞誉的计算机科学论文的作者。2011年6月,结束了在英国的书籍研讨和系列演讲的高德纳...
标题:高德纳算法论文 描述:Knuth(高德纳)撰写的关于算法的论文,探讨了计算歌曲复杂度的问题。 在计算机科学领域,Donald E. Knuth(唐纳德·E·高德纳)是一位备受尊敬的人物,他不仅在算法理论与实践方面...
《计算机程序设计艺术》是计算机科学领域的一部经典著作,由美国计算机科学家唐·艾伦·高德纳(Donald Ervin Knuth)撰写。这部多卷本巨著深入探讨了算法设计、分析以及编程语言的设计原理,对于理解计算机科学的...
【高德纳——计算机程序设计艺术教授】 唐·埃克特·高德纳(Don E. Knuth),被誉为“编程教父”,是计算机科学领域的权威人物。他的学术成就卓越,从高中时期的数学爱好者到获得数学博士学位,再到成为计算机科学...
这部书被誉为20世纪最重要的20部着作之一,是计算机科学领域的权威着作.全书共分7卷,目前已经出版了3卷,被誉为"计算机程序设计理论的荷马史诗","可与牛顿的自然科学的数学原理>>媲美的巨着".作者数学方面的功底造就了...
这部书被誉为20世纪最重要的20部着作之一,是计算机科学领域的权威着作.全书共分7卷,目前已经出版了3卷,被誉为"计算机程序设计理论的荷马史诗","可与牛顿的自然科学的数学原理>>媲美的巨着".作者数学方面的功底造就了...
MDK的核心是MIX,一个由高德纳设计的模拟计算机模型,旨在帮助读者理解和实现书中介绍的各种算法。MIX是一种基于十六进制计算的虚拟机,具有简单的指令集,旨在模拟早期的计算机硬件。通过编程MIX,读者可以直观地...
《创造力、创新与卓越——2022年高德纳通信奖的启示》 2022年的高德纳通信奖已经落下帷幕,这是该奖项举办的第十二个年头,旨在表彰全球通信专业人士的杰出成就。今年,奖项进一步扩展,新增了品牌建设和营销传播...
高德纳-姚期智动态规划优化(Knuth-Yao DP Speedup)是计算机算法领域的一个重要概念,涉及动态规划这一算法设计技术的效率提升。动态规划是一类解决多阶段决策问题的算法策略,它将复杂问题分解为相对简单的子问题...
1 Selected.Papers.on.Computer.Languages(Donald.E.Knuth).djvu 2 Selected.Papers.On.Computer.Science.(Donald.E.Knuth).djvu 3 Selected.Papers.on.Discrete.Mathematics.(Donald.E.Knuth).djvu ...
《研究之美》是计算机科学大师、“算法分析之父”高德纳(Donald E.Knuth)在20世纪70年代旅居挪威时撰写的适用于计算机科学的一种全新基础数学结构的情景小品。全书以一对追求自由精神生活的青年男女为主人公,展开...
计算机程序设计艺术四卷全集作者(高德纳)据说读懂全书可入职微软
《计算机程序设计艺术》是计算机科学领域的一部经典著作,由世界著名的计算机科学家Donald E. Knuth撰写。Donald Knuth被誉为算法分析的大师,他的这部著作自出版以来,已经成为计算机程序员和学者不可或缺的参考书...
《算法I-IV(C++实现)基础、数据结构、排序和搜索》是由法国人塞奇威克(Robert Sedgewick)著作的一部计算机科学教材,他是美国计算机科学家唐纳德·克努特(Donald E. Knuth)的弟子,同时塞奇威克教授也因其在算法...
**Ahua_Calculator V1.2:一个基于VC++和MFC的计算器应用** Ahua_Calculator V1.2是一款用C++编程语言,结合Microsoft Foundation Classes (MFC)库开发的计算器软件。MFC是微软为Windows平台提供的一套面向对象的...
The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition) Donald E. Knuth Volume 2 of Donald Knuth's classic series The Art of Computer Programming covers seminumerical ...
The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition) Donald E. Knuth This magnificent tour de force presents a comprehensive overview of a wide variety of algorithms and the...