Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Technical Papers Every Programmer Should Read (At Least Twice)

blog.fogus.me

Post reply on HN
Print view View original

31–40 of 61 posts

Re: Technical Papers Every Programmer Should Read (At Least Twice)

#31

Post by gfodor »

ajross wrote: post #18

I don't mean to speak badly of this bibliography. Of the papers in the list I've read, they're all great. And I'll add the others to my list and make sure I get to them. But I think the premise of the blog post is a little flawed. Reading papers is a poor way to make yourself a better programmer. Read them in spare moments, sure, but spend your time reading code , not paper. At best, these things will help you avoid…

Not buying it. Programmers in our field could do worse than be up-to-date on the history of the major ideas in computer science, before they fire up their editor and start hacking stuff out. Obviously, you can do both, too.

Re: Technical Papers Every Programmer Should Read (At Least Twice)

#32

Post by daveed »

ajross wrote: post #18

I don't mean to speak badly of this bibliography. Of the papers in the list I've read, they're all great. And I'll add the others to my list and make sure I get to them. But I think the premise of the blog post is a little flawed. Reading papers is a poor way to make yourself a better programmer. Read them in spare moments, sure, but spend your time reading code , not paper. At best, these things will help you avoid…

I disagree with you. All the programmers I know have plenty of coding/reviews in their day-to-day. A much smaller amount of time is dedicated to reading papers - after all, it's not their job. If we can agree that both are valuable, why is the author wrong for pointing people to things that they likely focus less on?

Re: Technical Papers Every Programmer Should Read (At Least Twice)

#33

Post by jackowayed »

ajross wrote: post #18

I don't mean to speak badly of this bibliography. Of the papers in the list I've read, they're all great. And I'll add the others to my list and make sure I get to them. But I think the premise of the blog post is a little flawed. Reading papers is a poor way to make yourself a better programmer. Read them in spare moments, sure, but spend your time reading code , not paper. At best, these things will help you avoid…

They serve very different purposes.

You're completely right in your last sentence. Very few papers will help you get better at debugging. But programming is about a lot more than debugging.

I'm interested in distributed systems but am only vaguely familiar with locks. I could pull up the Hadoop codebase and trudge my way through some distributed systems code. But it would take forever, and I'd have to guess at a lot of core concepts after a lot of confusion and effort trying to build complex mental models of what the code is doing in my head.

I think I would get a lot farther a lot faster if I read some things, be they papers or textbooks or Wikipedia entries, about systems. Then, once I'm at least sort of familiar with the core concepts that one applies when writing distributed systems, I could get to reading and writing real code.

There's a time and a place for both, but if there's a complex idea that one is not familiar with, I think one can much more efficiently understand it at some level--and then maybe dive into the code--by reading a 20-page paper about it than by trying to understand the 100KLOC implementation thereof. Being exposed to the high-level picture makes it way easier to understand why each piece is there doing what it's doing.

Re: Technical Papers Every Programmer Should Read (At Least Twice)

#34

Post by ssp »

psykotic wrote: post #21
DigitalBison wrote: post #20

Earlier quoted context omitted.

>Then the result for (x:xs) is (r, n) where n = n' + 1 and r = x with probability 1/n or else r'. Do you mean r = x:r' instead of r = x?

No, r has the same type as x. The logic behind that probability split is simple: We have r' (the random sample taken from the tail list xs) and x, and we have to choose between them with some probability based on n. Clearly x should occur with a 1 in n chance. When you approach it inductively the way I did, there really isn't any choice in the matter, which is why this algorithm design technique is so powerful. Udi M…

This way of thinking also makes it easy to derive the max-sum algorithm from Programming Pearls:

We have to compute max-sum for (x:xs), so first solve it for xs. If the max-sum is within xs, we are done; if not, it somehow involves x. To find out, the recursion has to also return the best sum of the beginning of the list.

A small case analysis can find out what the new max-sum is: x, x + max-begin(xs), or max-sum(xs)? And the new max-begin is either x or x + max-begin (xs).

The naive recursive implementation will require linear space though, so there is an extra step to find out how to eliminate the recursion.

Re: Technical Papers Every Programmer Should Read (At Least Twice)

#35

Post by psykotic »

ssp wrote: post #34
psykotic wrote: post #21

Earlier quoted context omitted.

No, r has the same type as x. The logic behind that probability split is simple: We have r' (the random sample taken from the tail list xs) and x, and we have to choose between them with some probability based on n. Clearly x should occur with a 1 in n chance. When you approach it inductively the way I did, there really isn't any choice in the matter, which is why this algorithm design technique is so powerful. Udi M…

This way of thinking also makes it easy to derive the max-sum algorithm from Programming Pearls: We have to compute max-sum for (x:xs), so first solve it for xs. If the max-sum is within xs, we are done; if not, it somehow involves x. To find out, the recursion has to also return the best sum of the beginning of the list. A small case analysis can find out what the new max-sum is: x, x + max-begin(xs), or max-sum(xs)…

Yes, Manber derives the linear-time algorithm for the maximal subsum problem exactly like that in his textbook. As you say, if x is involved in a maximal subsum, it must extend the tail's maximal prefix sum, so you return that in addition to the maximal subsum.

Regarding recursion vs iteration, Manber generally develops the right induction hypothesis gradually, using informal language ("remove the element and solve the smaller problem") in the process, and only turns that into a precise algorithm once the final induction hypothesis has been found, so he doesn't present the recursion elimination as a separate step. That works well pedagogically. His main idea is to guide the student's intuitions rather than formally derive a program that's correct by construction the way someone like Richard Bird might have done it. (Bird has an interesting derivation of the maximal subsum algorithm that begins with the brute-force algorithm written as a combinator-based functional program and gradually transforms it in a correctness-preserving way using program calculation techniques until arriving at the fast linear-time program.)

Re: Technical Papers Every Programmer Should Read (At Least Twice)

#40

Post by Confusion »

ajross wrote: post #18

I don't mean to speak badly of this bibliography. Of the papers in the list I've read, they're all great. And I'll add the others to my list and make sure I get to them. But I think the premise of the blog post is a little flawed. Reading papers is a poor way to make yourself a better programmer. Read them in spare moments, sure, but spend your time reading code , not paper. At best, these things will help you avoid…

You're overlooking a few things:

- we're not all dealing with code written by people who haven't read these papers

- in the real world, other people are also dealing with your code and the better it is, the easier it is for them, which in turn makes things easier for you

- people that have read these papers are often in a position to teach others, so the future code of those taught will be better. I will definitely relay what I learn from a paper to my colleagues when applicable

- sometimes somebody that has read a paper is needed to solve the mess the others have created: a mess that is impossible to solve without reinventing what is stated in the appropriate paper. And even though it seems obvious after reading the paper, you wouldn't come up with it yourself.

- there are things to be learned from the thorough analysis of others that you wouldn't ever have dreamed up yourself.

- there are things to be learned from the thorough analysis of other that you wouldn't ever learn if all you've been doing is reading code by others that haven't read these papers. And even if you read code from people that have read the papers: understanding something from code is much harder than understanding them from a paper in which they are clearly expositioned. You wouldn't grasp the fundamentals behind Lamport's paper or the Dynamo paper nearly as fast.

Post reply on HN