Not a paper, and not strictly CS, but Mythical Man-Month by Brooks. It solidified the connection in my mind between systems engineering and software engineering. Other readings since then have extended and changed this understanding, but this is where my approach to software development started to mature.
The first half of the paper is a spot-on critique of so many things that go wrong in the process of designing and implementing large-scale software systems. The second half, where the authors propose a solution, kind of goes off the rails a bit into impracticality... but they definitely point in a promising direction, even if nobody ever uses their concrete suggestions.
Definitely a gem. I loved their accurate comparison of the common programming paradigms, though I have to admit, that I didn't follow their idea of functional relational programming in detail.
It might be a cliche one to pick, but I really really really enjoy Alan Turing's "Computing Machinery and Intelligence"[1]. This paper straddles the line between CS and philosophy, but I think it's an important read for anyone in either field. And a bonus is that it's very well-written and readable.
Thanks for picking that one, that means I don't have to choose between it and my joint favourite, the snappily titled "Why Heideggerian AI Failed and how Fixing it would Require making it more Heideggerian".
Where Turing's paper put us on the journey towards AI, 57 years later Dreyfus points out how the direction chosen is not only wrong, but hopelessly misguided.
[quote]
As I studied the RAND papers and memos, I found to my surprise that, far from replacing philosophy, the pioneers in CS and AI had learned a lot, directly and indirectly from the philosophers. They had taken over Hobbes’ claim that reasoning was calculating, Descartes' mental representations, Leibniz's idea of a "universal characteristic" - a set of primitives in which all knowledge could be expressed, -- Kant’s claim that concepts were rules, Frege's formalization of such rules, and Wittgenstein's postulation of logical atoms in his Tractatus. In short, without realizing it, AI researchers were hard at work turning rationalist philosophy into a research program.
[endquote]
Exactly I worked my way backwards to this paper while exploring real world distributed systems like Kafka and Zookeeper and it was exceptionally well written paper that explained the basics of building distributed systems
Never did it for me. Always seemed totally trivial. What else could it possibly be!? It seems like a direct simplification of Einstein (... no global time ... spatially separated locations communicate with signals ... signals propagate in finite time ... proper time is an ordering along a world line ... relative time depends on communication ... there are spacelike separations where events do not have a defined temporal order ...). I guess they had first access to the fruit tree in those days.
I once spoke to Henri Gouraud after he gave a talk. He was very self-deprecating and acutely embarrassed that his name was attached to a blindingly obvious first-thing-that-comes-into-your-head shading expression-that-barely-deserves-the-name-algorithm. Sometimes that low hanging stuff gives you stomach ache.
A bit cliche for HN, but I really enjoyed RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I) by John McCarthy[0]. It was accessible to someone whose background at the time was not CS and convinced me of the beauty of CS -- and lisp.
I know Thompson's "Reflections on Trust" and Shannon's "Communication" papers are more famous but I believe BCS's "Correctness" paper has more immediate relevance to a wider population of programmers.
For example, I don't believe Ethereum's creator, Vitalik Buterin, is familiar with it because if he was, he would have realized that "code is law" is not possible and therefore he would have predicted the DAO hack and subsequent fork/reversal to undo the code.
Seriously, if you read BCS's paper and generalize its lessons learned, you will see that the DAO hack and its reversal as inevitable.
FWIW I think this is a very fair question. Parent's post veers a bit further toward defeatism than I think Smith's paper advocates for or justifies. In particular, of course the DAO hack wasn't inevitable -- a more careful programmer could've foreseen and prevented that attack and whole other classes of attack.
Part of the linked paper's point is that because computer systems involve many "levels of failure", even a more careful programmer cannot usually rule out every class of programs. The DAO hack, yes, possibly.
> Part of the linked paper's point is that because computer systems involve many "levels of failure", even a more careful programmer cannot usually rule out every class of programs.
But -- and this is the crucial point -- that doesn't mean we shouldn't strive to be better than we are now.
The impossibility of perfectly modeling the world hasn't prevented us from making enormous progress on software safety and security over the past 30 odd years. Today, if you care to, you can easily write code that is free of buffer overflows and command injection attacks. In the 00's SQL injection attacks were extremely easy to find; now they're comparatively rare.
Smith's paper tells us that code-as-law is probably a bad idea. But it is not -- and wasn't intended to be -- an indict of static analysis or model-based engineering more generally. Every structural engineer knows the difference between a bridge and a model of a bridge; a paper pointing out the difference without substantively critiquing the practical usefulness of a particular type of model would probably elicit eye-rolls. I'm not sure why these mundane observations receive such attention in computer science. Maybe because with software the model and the system look so similar.
But to be sure, the impossibility of codifying human morality is a pretty lame excuse for failing to use static analysis tools or better languages or quality frameworks to prevent known classes of attacks. So I doubt that's what Smith is advocating.
> How many "more careful" Ethereum programmers also check the compiler for correctness?
Yes, we should obviously check compilers for correctness, and we're making slow but sure progress toward a world where our critical infrastructure comes with strong --
of course, never perfect -- correctness guarantees.
> But -- and this is the crucial point -- that doesn't mean we shouldn't strive to be better than we are now.
Agreed! And I also agree that we are really making progress. But we're far from a world where people can crank out provably correct code (let alone the proofs).
> I'm not sure why these mundane observations receive such attention in computer science. Maybe because with software the model and the system look so similar.
Excellent point, and yes, I think that is the problem. Modeling the world in code is not much different from... er... modeling the world in code :-)
> Part of the linked paper's point is that because computer systems involve many "levels of failure", even a more careful programmer cannot usually rule out every class of programs.
The programmer only has to comply with the specification. The specification is a finite syntactic entity. If the specification doesn't capture what the user really wants, or compliance is undecidable, or <insert problem beyond the programmer's control here>, then the one at fault is the specification writer, not the programmer.
Given how bad the tooling is for Eth right now, it probably was inevitable. Their tooling isn't just a mess semantically and syntactically, it's was riddled with double-operation bugs.
i enjoyed skimming the paper, but i don't agree to your conclusions. It reminds me of an recent discussion i had about Dependent Types in Haskell, why not just check for termination instead of asserting it (I know about the halting problem)?
I think for many applications there is no binary answer, it's not just a good or bad idea. The question is how good can we get and is it any better than the state of the art? There are theoretical limits, but the interesting part is whether there exists a practical approximation. I don't believe in a fundamental difference between us and computers, i think everything we can reason about should be possible to algorithmically reason about. I think smart-contracts are a fundamental improvement over "non-code as law", i really believe in them. They are reproducible and exact. But it's a shame that solidity is so badly engineered, because they it is really hard to prove anything in it. I think they did the exact opposite of what would be the right language. I understand the reasoning behind "the limits of correctness", but does this means that proving anything is meaningless?
I would expect most contracts to be stupidly simpel, at least to a machine, with simpel properties that need to be proven comparable to testing Haskell with quickcheck. And i believe they are an improvement over "non-code as law", even if not provably correct.
The problem with bugs and smart-contracts is interesting. But implementing smart-contracts does not mean automating the judge.
My favorite paper in computer systems is "Memory Resource Management in VMware ESX Server". It identifies a problem and devises several clever solutions to the problem. I love papers that make your go "AHA!".
Dijkstra's shortest path algorithm in "A Note on Two Problems in Connexion with Graphs"
http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra....
Pure, mathematical and a great impact on both how to prove and define algorithms as well as the problem itself.
Our lab addressed some of the issues with Stabilizer [0], which "eliminates measurement bias by comprehensively and repeatedly randomizing the placement of functions, stack frames, and heap objects in memory".
My favorite topic was from an advanced user interfaces class. Describe 3 example of a bad user experience where the input in to the system does not give you the expected output. My poor example was a Kleenex box, I try to pull on one Kleenex and it tears or two come out at a time.
This is great -- I never knew about this paper but it reinforces a lot of things I learned. Namely, if you want to know how a company really works, ignore the org charts and map the systems architecture (a corollary to the author's thesis).
That it still holds true almost 50 years later is pretty amazing.
Hofstadter, D. R. and Mitchell, M. (1995). "The Copycat project: A model of mental fluidity and analogy-making." Chapter 5 in D. R. Hofstadter, Fluid Concepts and Creative Analogies.
"Copycat is a model of analogy making and human cognition based on the concept of the parallel terraced scan, developed in 1988 by Douglas Hofstadter, Melanie Mitchell, and others at the Center for Research on Concepts and Cognition, Indiana University Bloomington. Copycat produces answers to such problems as "abc is to abd as ijk is to what?" (abc:abd :: ijk:?). Hofstadter and Mitchell consider analogy making as the core of high-level cognition, or high-level perception, as Hofstadter calls it, basic to recognition and categorization. High-level perception emerges from the spreading activity of many independent processes, called codelets, running in parallel, competing or cooperating. They create and destroy temporary perceptual constructs, probabilistically trying out variations to eventually produce an answer. The codelets rely on an associative network, slipnet, built on pre-programmed concepts and their associations (a long-term memory). The changing activation levels of the concepts make a conceptual overlap with neighboring concepts." -- https://en.wikipedia.org/wiki/Copycat_(software)
264 comments
[ 3.0 ms ] story [ 283 ms ] threadhttps://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf
http://math.harvard.edu/~ctm/home/text/others/shannon/entrop...
"If the base 2 is used the resulting units may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey"
https://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thomp...
http://onlinelibrary.wiley.com/doi/10.1002/wcs.1269/full
http://www.melconway.com/Home/Committees_Paper.html
https://www-ee.stanford.edu/~hellman/publications/24.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.362...
http://www.jsoftware.com/papers/tot.htm
https://github.com/papers-we-love/papers-we-love/blob/master...
The first half of the paper is a spot-on critique of so many things that go wrong in the process of designing and implementing large-scale software systems. The second half, where the authors propose a solution, kind of goes off the rails a bit into impracticality... but they definitely point in a promising direction, even if nobody ever uses their concrete suggestions.
https://github.com/agentm/project-m36
[1] https://www.csee.umbc.edu/courses/471/papers/turing.pdf
Where Turing's paper put us on the journey towards AI, 57 years later Dreyfus points out how the direction chosen is not only wrong, but hopelessly misguided.
[quote] As I studied the RAND papers and memos, I found to my surprise that, far from replacing philosophy, the pioneers in CS and AI had learned a lot, directly and indirectly from the philosophers. They had taken over Hobbes’ claim that reasoning was calculating, Descartes' mental representations, Leibniz's idea of a "universal characteristic" - a set of primitives in which all knowledge could be expressed, -- Kant’s claim that concepts were rules, Frege's formalization of such rules, and Wittgenstein's postulation of logical atoms in his Tractatus. In short, without realizing it, AI researchers were hard at work turning rationalist philosophy into a research program. [endquote]
http://leidlmair.at/doc/WhyHeideggerianAIFailed.pdf
Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport.
http://amturing.acm.org/p558-lamport.pdf
My first introduction to time scales as a partial ordering. Very mind opening.
"Designing croquet's TeaTime: a real-time, temporal environment for active object cooperation", David Reed :
http://dl.acm.org/citation.cfm?id=1094855.1094861
I once spoke to Henri Gouraud after he gave a talk. He was very self-deprecating and acutely embarrassed that his name was attached to a blindingly obvious first-thing-that-comes-into-your-head shading expression-that-barely-deserves-the-name-algorithm. Sometimes that low hanging stuff gives you stomach ache.
[0] - http://www-formal.stanford.edu/jmc/recursive.html
I know Thompson's "Reflections on Trust" and Shannon's "Communication" papers are more famous but I believe BCS's "Correctness" paper has more immediate relevance to a wider population of programmers.
For example, I don't believe Ethereum's creator, Vitalik Buterin, is familiar with it because if he was, he would have realized that "code is law" is not possible and therefore he would have predicted the DAO hack and subsequent fork/reversal to undo the code.
Seriously, if you read BCS's paper and generalize its lessons learned, you will see that the DAO hack and its reversal as inevitable.
Honest naïve question. What's the proof?
But, for example, people have also lost money due to bugs in the Solidity compiler: https://np.reddit.com/r/ethtrader/comments/5foa5p/daily_disc... How many "more careful" Ethereum programmers also check the compiler for correctness?
Another paper in this vein is James Fetzer's "Program Verification: The Very Idea". http://lore.ua.ac.be/Teaching/SSPEC2LIC/critique2.pdf
But -- and this is the crucial point -- that doesn't mean we shouldn't strive to be better than we are now.
The impossibility of perfectly modeling the world hasn't prevented us from making enormous progress on software safety and security over the past 30 odd years. Today, if you care to, you can easily write code that is free of buffer overflows and command injection attacks. In the 00's SQL injection attacks were extremely easy to find; now they're comparatively rare.
Smith's paper tells us that code-as-law is probably a bad idea. But it is not -- and wasn't intended to be -- an indict of static analysis or model-based engineering more generally. Every structural engineer knows the difference between a bridge and a model of a bridge; a paper pointing out the difference without substantively critiquing the practical usefulness of a particular type of model would probably elicit eye-rolls. I'm not sure why these mundane observations receive such attention in computer science. Maybe because with software the model and the system look so similar.
But to be sure, the impossibility of codifying human morality is a pretty lame excuse for failing to use static analysis tools or better languages or quality frameworks to prevent known classes of attacks. So I doubt that's what Smith is advocating.
> How many "more careful" Ethereum programmers also check the compiler for correctness?
Yes, we should obviously check compilers for correctness, and we're making slow but sure progress toward a world where our critical infrastructure comes with strong -- of course, never perfect -- correctness guarantees.
Agreed! And I also agree that we are really making progress. But we're far from a world where people can crank out provably correct code (let alone the proofs).
> I'm not sure why these mundane observations receive such attention in computer science. Maybe because with software the model and the system look so similar.
Excellent point, and yes, I think that is the problem. Modeling the world in code is not much different from... er... modeling the world in code :-)
The programmer only has to comply with the specification. The specification is a finite syntactic entity. If the specification doesn't capture what the user really wants, or compliance is undecidable, or <insert problem beyond the programmer's control here>, then the one at fault is the specification writer, not the programmer.
I think for many applications there is no binary answer, it's not just a good or bad idea. The question is how good can we get and is it any better than the state of the art? There are theoretical limits, but the interesting part is whether there exists a practical approximation. I don't believe in a fundamental difference between us and computers, i think everything we can reason about should be possible to algorithmically reason about. I think smart-contracts are a fundamental improvement over "non-code as law", i really believe in them. They are reproducible and exact. But it's a shame that solidity is so badly engineered, because they it is really hard to prove anything in it. I think they did the exact opposite of what would be the right language. I understand the reasoning behind "the limits of correctness", but does this means that proving anything is meaningless?
I would expect most contracts to be stupidly simpel, at least to a machine, with simpel properties that need to be proven comparable to testing Haskell with quickcheck. And i believe they are an improvement over "non-code as law", even if not provably correct.
The problem with bugs and smart-contracts is interesting. But implementing smart-contracts does not mean automating the judge.
http://web.eecs.umich.edu/~mosharaf/Readings/ESX-Memory.pdf
https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia...
Immediately useful for anyone measuring compiler transformations performance!
[0] http://plasma.cs.umass.edu/emery/stabilizer.html "Stabilizer: Statistically Sound Performance Evaluation" by Charlie Curtsinger and Emery Berger, ASPLOS 2013
Full tail recursion scheme implementation by never "return" in C
https://www.cs.drexel.edu/~yfcai/CS451/RequiredReadings/Myth...
http://www.melconway.com/Home/Committees_Paper.html
That it still holds true almost 50 years later is pretty amazing.
https://arxiv.org/abs/1505.04714
http://web.cecs.pdx.edu/~mm/CopycatChapter.html
"Copycat is a model of analogy making and human cognition based on the concept of the parallel terraced scan, developed in 1988 by Douglas Hofstadter, Melanie Mitchell, and others at the Center for Research on Concepts and Cognition, Indiana University Bloomington. Copycat produces answers to such problems as "abc is to abd as ijk is to what?" (abc:abd :: ijk:?). Hofstadter and Mitchell consider analogy making as the core of high-level cognition, or high-level perception, as Hofstadter calls it, basic to recognition and categorization. High-level perception emerges from the spreading activity of many independent processes, called codelets, running in parallel, competing or cooperating. They create and destroy temporary perceptual constructs, probabilistically trying out variations to eventually produce an answer. The codelets rely on an associative network, slipnet, built on pre-programmed concepts and their associations (a long-term memory). The changing activation levels of the concepts make a conceptual overlap with neighboring concepts." -- https://en.wikipedia.org/wiki/Copycat_(software)
https://cogsci.indiana.edu/copycat.html