HNHacker News
TopNewBestAskShowJobs

sb

521 karma · joined June 19, 2008

submissionscomments
sb··on Want to Write a Compiler? Just Read These Two Papers.
While I agree with your point about starting, I think that parsing is a rather beautiful part of compiler construction by itself, with a nice theory behind it all, too.

Furthermore, if you are using Wirth style compilers, syntax-directed compilation comes rather naturally (at least to me). So I heartily second (and in fact have done so a number of times on HN) your initial recommendation for Wirth's "Compiler Construction", which is IMHO the canonical text to get somebody started. Instead of Appel's book, I find Cooper and Torczon's "Engineering a Compiler" much more comprehensive and illustrative (particularly the instruction selection and instruction scheduling parts.) Other interesting texts in the area are: Michael Scott's excellent "Programming Language Pragmatics" and Grune, Bal, Jacobs and Langendoen's "Modern Compiler Design" (both of which have a nice treatment of functional and logic programming languages [the latter one being more comprehensive])

sb··on Practical Foundations of Mathematics
tl;dr: Haven't read it but it's on top of my to-read stack. A slightly better version from the author's home page:

http://www.paultaylor.eu/~pt/prafm/

sb··on Why you should quit your technology job and get a Ph.D. in the humanities
While I agree with your suggestion of reading books (which is IMHO in general a good advice), I have to sort of disagree with your description of a PhD: The goal of getting a PhD at least in science, technology, engineering and mathematics is to autonomously advance the state-of-the-art of any chosen field, to contribute new knowledge to humanity without a supervisor giving directions.

Now, the process of advancing the state-of-the-art is unusually hard and there exists a good deal of very good write-ups of the intricacies involved (such as "So long and thanks for the PhD") which requires people to be driven and focused. But, at the same time, before actually starting the research that gets them their PhDs, gradute students spend time in advanced courses and later on read lots of research papers and additional textbooks. This is an invaluable process of unsupervised learning (hence the first paragraph), and I think that getting a PhD also gives you the abilities and experience to autonomously go from zero knowledge in an area to contributing new knowledge by reading. Of course, studying at a university saves you a lot of time, because somebody else--the professor--who is already very knowledgeable in the target area has already broken down his knowledge in edible--and ideally pedagogically-sound--pieces ready to be sucked up. But if time is not of the essence, and since you are already a driven and focused person, you should be able to do it by yourself.

So this was (quite unexpectedly) rather long, a more detailed discussion and probably a very good book to read for anybody can be found in: Mortimer Jerome Adler's wonderful "How to read a book". A brief summary for tl;dr reasons: I love and totally support your reading advice, but since the PhD experience enables you to work your way through literature in unknown territory, it might very well be worth the effort.

sb··on The Implementation of Functional Programming Languages
larsberg has already given several suggestions, however, since nobody else mentioned it yet, you might want to complete your view of functional programming language implementation by taking a look at "Lisp in Small Pieces" by Christian Queinnec (http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...).
sb··on The Implementation of Functional Programming Languages
In addition to the other comments (at the time of this writing: silentbicycle and dons), I would say:

- Regarding the importance of the book: it's discussion of the G-machine (probably also interesting is another paper by SPJ, "The spineless tagless G-machine") is very comprehensive and textbook style. I think this is very important to study/compare the other model of virtual machines used for implementing functional programming languages, viz. the SECD machine (named after the four stacks necessary, Stack, Environment, Code, Dump.) The book I first read about the SECD machine is Peter Kogge's "The Architecture of Symbolic Computers" and I recommend it dearly.

- Regarding the use of lambda calculus: It's not just the equivalent of a Turing machine, but much more fundamental in the theory of implementing programming languages: Aside of the eager/lazy evaluation of functional programming languages (corresponding to applicative and normal order evaluation of terms), the typed lambda calculus for instance is fundamental for studying type systems, one of the more important research areas of the last decade. Besides it is also the basis of LISP (eval and apply functions.)

sb··on Ask HN: What documentaries are worth watching?
"Enron - The Smartest Guys in the Room" seconded! It is by far my most favourite documentary.

In addition, I like the following documentaries:

- "Client 9: The Rise and Fall of Eliot Spitzer" http://www.imdb.com/title/tt1638362/

- "Planet Earth" IMHO one of BBC's best productions with some of the most amazing nature shots ever (e.g., a [presumably stratospheric] shot that looks like fog or fire but is really a swarm of flies) http://www.imdb.com/title/tt0795176/

- BBC has also two of the best documentary series regarding the second world war: "The World at War" (http://www.imdb.com/title/tt0071075/) and "The Nazis: A Warning from History" (http://www.imdb.com/title/tt0207907/)

- Errol Morris' "The Thin Blue Line" (http://www.imdb.com/title/tt0096257/) and "The Fog of War" (http://www.imdb.com/title/tt0317910/)

sb··on Raskin zoomable desktop manager for Mac OS X
An interesting concept, for programmers it would be great, if they supported something along the lines of 1996s "Software Visualization in the Large", by Thomas Ball and Stephen Eick [1]. I did something like that (i.e., marrying the visualization with a file management metaphor) quite a while back in Eclipse, but never got around to maintain it. Too bad, because I kind of liked it. (And it was different from AspectBrowser, too.)

[1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89....

sb··on Blunt and necessary review of programming language books.
Two of my favorites in the "best small books" area are from Niklaus Wirth:

- NW: Algorithms and Datastructures. 179 pages. PDF: http://www-old.oberon.ethz.ch/WirthPubl/AD.pdf

- NW: Compiler Construction. 131 pages. PDF: http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf

Both books are really brilliant and it always fascinates me how much content he packs into the books. Highly recommended. (I like "Project Oberon" too, but it has probably too many pages for this category [>400].)

sb··on Implementing a fast interpreter without resorting to assembly
EDIT: Of course, the question in the third paragraph should read:

Does a programming language implementation using a JIT subsystem require more or less energy than an interpreter?

sb··on Implementing a fast interpreter without resorting to assembly
I have just read the post and have to say that I would appreciate the post containing a more accurate description of the testing methodology. Some of the techniques described are known in interpreter optimization and his description of "threaded code" intepreter is actually not consistent with what it usually means (viz. threaded code interpreters have nothing to do with "threading" the decode for the successor instruction into the operation implementation of the current instruction, but just moving instruction decode and dispatch into the operation implementation.)

Aside of that, there have been papers detailing the software pipelining approach (cf. Hoogerbrugge et al.: "A code compression system based on pipelined interpreters", 1999), but I cannot for the love of god imagine that the loop shown in there is faster than a JIT compiler for a very simple reason: each of the interpreter operations is invoked via a function pointer, which means that the compiler emits an indirect branch instruction for implementing this. Now, these indirect branch instructions are very costly, and a simple JIT compiler could just take the actual values (callee target addresses) of the input program and generate direct call instructions instead. (And I am not even talking about inlining the function bodies of the operation implementation.)

sb··on Implementing a fast interpreter without resorting to assembly
Just for the record, while I agree at least in principle regarding your assessment of interpreters vs. JIT compilers, the situation seems to be far from clear though, and I think the last word is not yet spoken on that topic.

As far as I am concerned, most of the benchmark suites out there give an unfair advantage to JIT compilers. For example, all numeric JavaScript and Python benchmarks can be heavily optimized by JIT compilers (essentially removing all of their interpreters' weaknesses: (un-)boxing, dynamic typing, and in the case of Python, reference counting; plus removing the interpreter overhead [i.e., instruction dispatching]). Many of the benchmarks are numerical in nature, too, even if the actual workload is usually non-numerical. So it might very well be that your actual workload does not use any of the fancy numerical operations that a JIT can optimize heavily. In such a case, the additional memory consumption of the code caches and the additional memory requirements of a generational garbage collector may in fact not give you any practical speedups in comparison to a sophisticated interpreter using just reference counting (which is known to be very space efficient).

Aside of this unfair skewing of benchmarks towards numerical computations, there are other points to consider in the discussion of JIT vs. interpreters, such as energy consumption. Does a programming language implementation using a JIT subsystem require more or less memory than an interpreter? (I am positive that some companies have already measured this, but there are AFAIK no publications concerning this important question.)

Summing up, I think--as is so often the case in computer science--which of the two techniques give the best results depends heavily on a) what trade-offs you/your customers are willing to make [space vs. time] and b) the actual performance is of your workload [numerical vs. non-numerical].

sb··on Implementing a fast interpreter without resorting to assembly
At the time of writing, some of the other commentors have already provided answers regarding the ease of implementation aspect of interpreters. Another important advantage of implementing an interpreter is that it usually gives you portability for free (or with modest extra works).

The nice point of figuring out optimization of interpreters is that you get the speedup on all architectures, while in a JIT you usually have to change the backend (or worse if you have to create a new backend from scratch.)

edit: I am sorry, another commenter already hinted at the portability aspect.

sb··on Author of LuaJIT explains why compilers can't beat hand-coded assembly
This is a very interesting post that fits nicetly with many other interesting statements Mike Pall made (such as his reference to the LuaJIT2 interpreter being faster than the LuaJIT1 jit compiler on some cases [http://lambda-the-ultimate.org/node/3851#comment-57646].)

On a related note, a similar problem is highlighted in a paper by Anton Ertl and David Gregg ([1]), where they claim that the slowdowns of an efficient interpreter to an optimizing native code compiler is 1:10, whereas the slowdown between an efficient interpreter and an ineffcient one is 1:100. Consequently, there seems to be a lot of optimization potential (though I admit that depending on the kind of the interpreter, it might be unlikely to stay within a slowdown of 1:10)

[1]: Ertl, Gregg. "The Structure and Performance of Efficient Interpreters", 2001. (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69....)

sb··on Linus Torvalds on Garbage Collection (2002)
Recently, there has been some work on removing redundant reference count operations in the Python interpreter. The following paper describes how it can be done: http://portal.acm.org/citation.cfm?id=1869631.1869633.

Regarding the performance impact of reference counting, the following facts are important:

- Switching from immediate reference counting to deferred reference counting (L.P. Deutsch and D.G. Bobrow, 1976 [1]) eliminates about 90pct of all reference count operations in Smalltalk (Berkeley Smalltalk '82, that is) [2]

- A very good account of reference counting can be found in either Dave Ungar's excellent PhD thesis [3] and Dave Ungar and Dave Patterson's in-depth analysis of Smalltalk performance [4].

[1] An efficient, incremental, automatic garbage collector (http://www.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/p...)

[2] High performance storage reclamation in an object-based memory system (http://techreports.lib.berkeley.edu/accessPages/CSD-84-167.h...)

[3] The Design and Evaluation of A High Performance Smalltalk System (http://www.eecs.berkeley.edu/Pubs/TechRpts/1986/5376.html)

[4] Berkeley Smalltalk: Who knows where the time goes? (Chapter 11 of http://www.iam.unibe.ch/~ducasse/FreeBooks/BitsOfHistory/)

sb··on Linus Torvalds on Garbage Collection (2002)
Just for the record: Pramod Joisha did static analysis of redundant reference counting operations in 2006 in the Bartok C# research compiler (http://www.hpl.hp.com/personal/Pramod_Joisha/Publications/is...). IIRC, doing it improves performance significantly.
sb··on How to Ace Calculus: The Art of Doing Well in Technical Courses
That is exactly the reason why studying technical subjects is such a joy! Once you grasp a concept, you don't need to learn anything by heart (which I suck tremenduously at.)
sb··on Poll: Which pointing device do you prefer?
Regarding the trackball: I use a "Kensington Expert Mouse" highly recommended!
sb··on What is the single most influential book every programmer should read?
I agree with the missing parts of the book (btw: anyone interested in that might find "Programming Language Pragmatics" by Michael Scott interesting), however, I think that there is not enough experience on using functional programming languages in an industrial/professional setting.
sb··on What is the single most influential book every programmer should read?
Have you actually read CC?

Another point: Which books deal with "the most interesting aspects of designing programs" in your opinion?

sb··on Teaching programming languages: a novel approach
Shriram Krishnamurthi is a genius; I saw him at a conference last year and regardless of the topic of the talk given, he always had insightful comments and questions that were close to a level of having done the research himself. Honestly, I have never met anyone more competent in such a variety of topics.
sb··on Intel Launches Next Gen Itanium Monster Processor
While I certainly think this would make for interesting research, I think the runtime-complexity of VLIW algorithms (such as Monica Lam's "Software Pipelining") would definitely interfere with the upper-bounds for compilation time of JIT compilers.

(But, then again you could always use a background optimization thread...)

sb··on Intel Launches Next Gen Itanium Monster Processor
Regarding point 2: Last time I checked (IIRC 2006-ish), there seemed to be common resentiment among scientists working in the area of programming language implementation that there is just too little ILP for successful wide-spread VLIW adoption (modulo some special use cases.)

AFAI(K|R), Hennesy and Patterson's cannonical text (CA-AQA [1]) reflects this: going from 3rd to 4th edition, we find a new chapter "Limits on ILP", VLIW/EPIC elements have been moved from the main contents to the CD-ROM, too (which probably is not a good indicator, though: the 3rd edition was just too heavy to carry it around a lot ;)

[1]: http://www.amazon.com/Computer-Architecture-Quantitative-App...

sb··on The Development of the C Language
Just for the record (since I have recently stumbled upon and read up on the BCPL stuff): Martin Richards web site at the University of Cambridge contains valuable resources on BCPL (http://www.cl.cam.ac.uk/~mr10/index.html), including (relatively) recently updated manuals.
sb··on Nearly All US Universities Lose Money on Sports
While I cannot argue on any point of your post, I distinctly remember that sometime ago on HN there was a post how essentially Stanford and MIT "live" on military grants. The story was about Stanfrod being US-Army stronghold, while the Navy "sponsors" MIT (Just searched: http://news.ycombinator.com/item?id=1416348.)

I have no data, but I think that those DARPA grants are at least substantial, some concrete figures would be nice though.

sb··on Nearly All US Universities Lose Money on Sports
That's just appalling. In Europe, AFAIK there is usually no such thing as college/university sports--competition-wise, that is (aside of the known the Oxford/Cambridge rowing competition.)

I just recently discovered the following site, which just makes me sad: http://www.sacbee.com/statepay/?name=papadimitriou

Why are UC-Berkeley and UCLA head coaches earning more than 8 times as much as Christos Papadimitriou? Granted his salary is stellar by comparison, but there are a couple of other well-known UC professors who earn much less. (Richard Karp [of Rabin-Karp fame and Turing-Award winner] gets 166k [14 times less than the UC-Berkeley head-coach].) In addition, the professors from the med-schools seem to do a lot better; even though they are quite out of proportion, at least they're saving lives.

Previously, I supposed these were profitable investments, but when one head coach salaries buys you 14 Dick Karps or 8 Christos Papadimitrious, I really think it doesn't make any sense at all...

sb··on How to become Batman
Damn it, if I had known when I was 18!

OTOH, I guess since the common opinion is that most bad guys are boring drug dealers, it's fair to say that if there are people inquiring about how to be Batman, there probably are ones interested in becoming one of his arch-enemies (which is probably less difficult, too :)

sb··on On the fact that the Atlantic Ocean has two sides
http://www.youtube.com/watch?v=s7ROTJKkhuI

OOPSLA'97 keynote; mandatory watching :)

sb··on Great Math Books as Recommended by Our Readers
"Mathematics: Its Contents, Methods and Meaning", seconded! I bought it a couple of years ago when I first read about it on HN and have to say that it is a highly readable account of mathematics.
sb··on Engineering a Compiler, 2nd Edition is out
I agree that it is the best book on compilers for beginners. I think that parsing using a recursive descent parser for LL grammars with attributed grammars teaches you the most basic and important things (such that one is able to design and parse a nice DSL.)

Having said that the book's major draw back is that is "soft" on the major topics of today: optimizations. The book is very frontend centered and mentions some possible optimizations in the final chapter--no implementations given. Hence, while I always recommend this book as the first go-to book, interested compiler programmers have to find supplemental material elsewhere. (I love M. Scott's "Programming Language Pragmatics", respect Grune, Bal, Jacobs and Langendoen's "Modern Compiler Design", consult Muchnick's "Advanced Compiler Design and Implementation".)

Topic-wise, supplemental material to Wirth's CC-book, I suggest: LR-parsing (yacc) and in-depth study of instruction selection ([i]burg) and register-allocation (graph coloring) for important backend optimizations. I think that gives a firm understanding of compilers, suitable for further study (such as Muchnick "Advanced Compiler Design and Implemetation" 1997 or Morgan "Building an Optimizing Compiler" 1998.)

sb··on Why you should read academic papers
Another very important point to keep in mind: ACM helps students cover travel expenses to conferences if they cannot be covered by the students themselves.

This is a tremenduous help for students that are not employed by their universities or are not covered by a professor's grant. In addition to the access to ACM's digital library, I think that a membership is money well spent (and it should be tax deductible in most countries anyways...)

← PreviousPage 3 of 7Next →