Ask HN: What are the most fundamental books on computer science?

[michalu]

I'm relatively new to CS (4 years) and I've seen a lot of great book recommendations here. But every discipline has it's most fundamental books ... e.g. philosophy -> Socrates, Plato, Aristotle, civil law -> code civil, christianity -> bible, etc. one should read to get a truly deep understanding.

What are those books for CS?

[reacweb]

Structure and Interpretation of Computer Programs (), Introduction to Automata Theory, Languages and Computation (Hopcroft Ullman), don knuth's art of computer programming, Tanenbaum's Modern Operating Systems, Compilers: Principles, Techniques, and Tools5 (Aho Sethi Ullman)

[einpoklum]

While "The Art of Computer Programming" is a great book, it's not a fundamental book. I'd say it's more of a re-distillation plus some of Knuth's personal take on things.

Also, I'd add, at least:

Introduction to Algorithms / Cormen, Leiserson & Rivest (and recently also Stein)

[vips7L]

> Tanenbaum's Modern Operating Systems

I found Operating Systems: Three Easy Pieces to be better.

http://pages.cs.wisc.edu/~remzi/OSTEP/

[jammygit]

What is it that makes each fundamental?

[amelius]

The "searching" volume of The Art of computer programming seems a bit outdated, though, in this age of search engines.

[omarhaneef]

CS is such a wide field, I think that fundamental texts mean different things to different people. These are some examples of various CS verticals (from off the top of my head), and each has canonical texts:

For instance, there is a whole subset devoted to turing machines, the halting problem, finite state machines, provability, incompleteness, the set of all sets, diagonalization proofs etc

There is a whole subset devoted to programming languages: computational complexity, reducing the time spent in loops, and so on.

Then there is a whole bunch spent on best practices: git and other version control, review, commenting style.

Then there is this actual thing called programming: learning different languages, arguing when functional is better than object oriented, please build a web server in prolog as an exercise, and so on.

Then there is a bunch about operating systems, and where the hardware meets the software, and garbage collection, and parsing and all that stuff.

Then databases are their own thing: boyce-codd normal form, ACID properties, is the web a database? how do you prove the ACID properties? Distributed databases, and B-trees time for storage and retrieval.

These are just various sort of "verticals".

I myself like to think of it in terms of specializations: data science/machine learning is one, web apps are another, mobile apps are another and so on. Each specialization depends on what useful thing you are trying to achieve.

[Anon84]

Speaking of specializations... sometime ago I asked a similar question about AI and ML. Unfortunately it never got much attention:

https://news.ycombinator.com/item?id=20920018

[crimsonalucard]

There are various verticals. But of all these verticals there are roots.

Sort of like how Set theory and Category theory make up the fundamental basis of all math, the fundamentals of computer science are encoded within your first example:

>For instance, there is a whole subset devoted to turing machines, the halting problem, finite state machines, provability, incompleteness, the set of all sets, diagonalization proofs etc

[bo1024]

CS is like math, not philosophy -- the fundamental ideas are gradually refined by a community, and eventually someone puts them into a book. Usually there are many books and people have different favorites.

So the closest parallels are original research papers like Turing's and Shannon's; but you're probably better off reading more recent textbooks.

That said, to balance out the heavy emphasis on programming and engineering books here, some recommendations:

- Sipser. Introduction to the Theory of Computation.

- Russell, Norvig. AI: A Modern Approach.

- For algorithms I don't have a preference. There is Dasgupta-Papadimitriou-Vazirani; Cormen-Leisersen-Rivest-Stein; Kleinberg-Tardos; and more.

A bit farther from core CS, I also like:

- Cover, Thomas. Elements of Information Theory.

- Li, Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications

[einpoklum]

Some of these are quite fundamental but not very popular. Which is good, because people forget those. I'm not much of a Sipser guy but maybe it's because they didn't use it at my alma mater when I took my Theory of Computation and Automata courses.

[kingkongjaffa]

Mathematics has a linear progression though.

You need to know numbers and simple algebra to tackle trig, you need to know all that to tackle calculus or linear algebra, you need to know those to tackle differential equations.

I would argue CS is closer to philosophy.

Sure you have programming building blocks like variables, loops, conditionals, objects blah blah.

But you quickly head into patterns and conventions that started out as someones opinion on how things should be set up, rather than some fundamental principle.

[qntty]

Structure and Interpretation of Computer Programs is frequently recommended here. I would especially recommend understanding section 3.2, which I've found very helpful for understanding the environment model of other languages.

Computer Systems: A Programmer's Perspective has a lot of good explanations of hardware/os subsystems that can be hard to find detailed explanations of elsewhere. I especially like the sections on virtual memory.

[srijanshetty]

The interesting bit is that the original author's no longer feel that SICP is the right way to approach programming any more. In their words, we've moved to 'programming by poking' and hence the latest incarnation of the course uses python and not LISP.

[archielc]

Code: The Hidden Language of Computer Hardware and Software by Charles Petzold

This one's for you if you want to learn or just recap principles of computers (and read on evolution as well). I just started reading it and found it suprisingly easy to follow. It's perfect if you like things explained step-by-step and in a simple way.

[todd8]

I see this book recommended often and I like Petzold's writing. I think this book is excellent introductory book.

However, I bought this book in 2013 and was disappointed. I kept the book in the hopes that my high school and college aged kids might get something out of it. This is a book appropriate for someone new to programming. I don't consider this a book for computer scientists that already have a university degree, since it provides only a very basic introduction to Boolean algebra, logic gates, computer arithmetic. If you know what a NAND gate is and what a XOR instruction does you don't need this book.

For the practicing professional or a serious CS student interested in bits and bytes I might recommend Hackers Delight, Second Edition by Hennry S. Warren Jr.

[ninjacatex]

I read this in high school and now I am working on my phd in computer architecture. This is definitely not a coincidence. I love how well it explains the low-level workings of computers.

Definitely would recommend!

[moonfleet]

What stands out about this book for me is how it starts with absolute basics like what electrons are and linearly builds complexity. It never lost me for a moment and I thoroughly enjoyed its lighthearted tone. This is a perfect book for those who had no formal CS education and are starting out with computers and programming.

[jtms]

This is one of my favorite books of all time! I built an 8 bit ALU and a few KB of ram and misc other parts of a computer in Minecraft using the schematics in this book and it was one of the most fun things I have ever done.

[onemoresoop]

I second this. Code: The Hidden Language of Computer Hardware and Software is also very ethically pleasing.

[FillardMillmore]

I'm going to cast a vote for 'Unix & Linux System Administration Handbook' - it's been around a long time and is currently on edition 5. It's the book that made me fall in love with system administration.

It's an extensive and well-rounded look at various fundamental system administration topics with examples included from multiple different *nix distributions (topics like work management, logging, networking, security, the kernel, systemd, permissions, etc.). If you're at all interested in Linux, this is a great book to have on your shelf.

https://admin.com/

[madhadron]

> every discipline has it's most fundamental books ... e.g. philosophy -> Socrates, Plato, Aristotle, civil law -> code civil, christianity -> bible, etc. one should read to get a truly deep understanding.

I dispute this idea. For some disciplines, this may be so. For other, such as physics, biology, chemistry, mathematics, civil engineering, poetry...actually, for most disciplines they aren't based on fundamental books. They're based on a living community of practice.

In these disciplines a book is important only insofar as it can be used to increase your abilities. No one goes and studies the textual details of Landau & Lifshitz as a guide to anything, any more than they do so with TAOCP.

Rather than worry about fundamental books, worry about opening up black boxes at a steady rate.

[pacbard]

Books here could be a stand-in for what Thomas Kuhn has called paradigms [1]. Broadly, each science has a core set of beliefs that are accepted by a majority of the scientists working within that discipline. Books can be seen as the formalization of a paradigm as a way to teach new people (e.g., undergraduates) how to operate within a discipline as opposed to research papers where the boundaries of current paradigms are tested and pushed (or opening up the black box, as you mention).

[1]: https://en.wikipedia.org/wiki/Paradigm_shift

[TheRealPomax]

Except there are. For example, biology has "Campbell Biology", formerly just called "Biology", and it gets frequent revisions to ensure it's still relevant as the field evolves.

The question as posed does not strike me as one of worry, but of curiosity: what ARE the seminal works that the different fields point to as being the "bibles" of their discipline? Comp. Sci. has Knuth, Russel and Norvig, etc. Other fields most certainly have their own, and knowing which those are is interesting and worth getting an answer to.

[znpy]

> every discipline has it's most fundamental books

I'd say: every discipline has it's most fundamental memes

[playing_colours]

Focusing on mathematics, I think about two kinds of foundational books.

1. Historically foundational: books that brought important ideas, introduced a new branch, progressed the maths significantly. You can read them these days, but their content, proofs, language, etc. is not up to date. Examples: Elements by Euclid, Philosophiae Naturalis Principia Mathematica by Newton, Disquisitiones Arithmeticae by Gauss.

2. Modern foundational books: The ones that can be used for studying now. Books that are clearly written, popular, cover their subject well. Examples: Visual Complex Analysis, Spivak’s Calculus, Linear Algebra Done Right, Hardy’s An Introduction to the Theory of Numbers.

[throwaway_bad]

I think you're right that you shouldn't learn from the "fundamental" books but there definitely are such a thing as fundamental books.

They are usually hugely influential in their times but have been refined or made easier to digest since. If you care deeply about your field you should read them at some point to see how ideas evolved historically.

English: Shakespeare

Biology: Darwin's Origin of Species

Math: Euclid's Elements

For OP's topic, I'd say Shannon's "A Mathematical Theory of Communication" is up there for computer science.

[physicsyogi]

I agree with a lot of this.

The one thing that I've found with some of these "fundamental" books is that there are gems of information that can be very helpful for specific problems.

For instance, Landau and Lifshitz's statistical mechanics book has first-rate description of entropy and multiplicity. And TAOCP has an incredibly thorough discussion of combinatorics that I found invaluable.

[ztree]

I've spent this entire year taking a break to learn fundamental CS(I'm not a CS graduate) Here are the books I found most useful/interesting: 1. The Annotated Turing by Charles Petzold : Used it because I had a hard time digesting the original Alan Turing paper 2. An Introduction to Formal Languages and Automata by Peter Linz : To grab the concept of state machines 3. The description of sequential processes by Iverson 4. Clrs: Have kept it for reference

Then I studied a matrix of math books, along with other CS books regarding compilers, operating systems etc. My aim was to get good enough understanding to comfortably digest the famous research papers.

I am yet to find definitive books that teach a way of thinking on their own merit as a single book. Cs like others is a matrix of knowledge that clicks as a whole 'chunk' of understanding, changing the way you have thought about things like programming in general. I'm having a hard time explaining this.

If you're not a CS graduate, I highly suggest simply going through academics of places teaching theoretical CS.

[fredophile]

Do you want to know about CS or do you want to know about programming? A lot of the suggestions I've seen so far in this thread are really about programming and not general CS. The basic math and principles for CS date back to before we had computers. I'd argue that if you want a real CS bible then you need to look at things published back when computer was a job and not an object. For example, you could check out "Introduction to a General Theory of Elementary Propositions" by Emil Post. Reading it will teach you about CS fundamentals but it will not make you a better programmer.

[guiraldelli]

I don't think there is a definitive answer for your question because computer science is a relative new area of knowledge and “fundamental books” are still being published.

If I had to say one text that is the fundamental one, I would go with a paper: “On Computable Numbers, with an Application to the Entscheidungsproblem” [1], by Alan Turing.

---

But if you just started your course in Computer Science, then I will give you some “bookshelf advice" based on my experience. I had the pleasure to study all the books I am going to recommend you, and most of them I was able to read cover-to-cover during the university years. And they are also in my bookshelf for reference.

The book order does not represent rank of importance.

* “Introduction to the Theory of Computation”, by Michael Sipser.

    * I also recommend the “Elements of the Theory of Computation”, by Christos Papadimitriou.

    * Another good complement is “Introduction to Automata Theory, Languages and Computation”, by Hopcroft and Ullman. (Thanks, @reacweb, for the reminder.)

* “Graph Theory”, by Reinhard Diestel.

    * If you feel you want to go deeper, and like a book which you cannot skip a single word, I strongly recommend “Modern Graph Theory”, by Béla Bollobás: it is one of my favorite textbooks ever!

* “The Algorithm Design Manual”, by Steven Skiena.

    * While a lot of people seems to praise either the Cormen et al. or the Sedgewick books, I have the feeling that “Algorithms” by Dasgupta, Papadimitriou  and Vazirani is my choice for “fundamental” book. But I decided to

* “Computer Architecture: a Quantitative Approach”, by Hennessy and Patterson.

* “Modern Operating Systems”, by Andrew Tanenbaum.

* “Artificial Intelligence: a Modern Approach”, by Russel and Norvig.

* “Modern Compiler Implementation (in ML)”, by Andrew Appel.

I would like to also recommend “Concrete Mathematics”, by Graham, Knuth and Patashnik, but I remember to not feel it the most pedagogical book on the subject.

Good luck!

---

[1]: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[cr0sh]

> If I had to say one text that is the fundamental one, I would go with a paper: “On Computable Numbers, with an Application to the Entscheidungsproblem” [1], by Alan Turing

Certainly that one, but I would add a couple of others:

"https://en.wikipedia.org/wiki/The_Laws_of_Thought" (George Boole) - lays out boolean algebra; fundamental to everything in computing

"https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a... (Claude E. Shannon) - basically lays out the equivalence of switching circuits to boolean algebra, fundamental to electronic computing

Note in fact many of Shannon's works and research could be considered "fundamental"...

[jamil7]

I've found this to be a pretty good list (https://teachyourselfcs.com), I can't say I've read every book on the list but I hope to someday.

[agentultra]

The Art of Computer Programming

Structure and Interpretation of Computer Programs

Purely Functional Data Structures

Programming in the 1990s

A Logical Approach to Discrete Math

[purple_ducks]

> The Art of Computer Programming

I'm guessing like most people who bought it, it sits collecting dust on the shelf.

Youthful naivety is the only reason I bought it. Completely impenetrable but look, "I'm a real™ software engineer now"

[robto]

The Elements of Computing Systems: Building a Modern Computer from First Principles[0] and its accompanying class Nand to Tetris[1]. Starting at logic gates and moving up through the levels of abstraction until you can build a programming language and implement a video game is the most fundamental approach that I'm aware of.

[0]https://www.nand2tetris.org/book [1]https://www.nand2tetris.org/

[artimaeis]

A lot of great books have already been recommended. Going to go a different route than others here have and recommend The Elements of Computing Systems.

It's a book that explores hardware from the ground up. It's one of the most insightful books I've found for getting a real intuition for hardware.

[srijanshetty]

The books that really shaped my understanding of CS are:

- Theoretical CS: - Compilers: Principles, Techniques, and Tools (The Dragon Book) - Introduction to the Theory of Computation, Sipser

- Programming: - Java Concurrency In Practice, Brian Goetz - Generics in the Java Programming Language, Gilad Bracha - Professor Frisby's Mostly Adequate Guide to Functional Programming - Unix for Poets - Modern C++

[mrbrowning]

To stick to the more theoretical interpretation of "computer science," and with a focus on theory of computation/programming languages:

- Discrete Mathematics And Its Applications, Kenneth H. Rosen (this is more foundational, but it's definitely targeted at a CS audience and touches on things like automata theory)

- Types and Programming Languages, Benjamin C. Pierce

- Semantics of Programming Languages, Carl Gunter

[faizshah]

One possible answer to this question is the most assigned books on computer science syllabi: https://opensyllabus.org/results-list/titles?size=50&fields=...

[dougb5]

_Concrete Mathematics_ by Knuth et al is a dense but joyful overview of discrete math for CS: https://www.goodreads.com/book/show/112243.Concrete_Mathemat...

[andrelgomes]

Operate on first principles, what do you need to know to be a "successful" programmer in the technical, social, and/or ideological context.

Data Structures and their relationship with each other to be a great technical programmer. These books (just highlight not everything) I would think -> Algorithms Sedgewick, Lisp Programmers Manual, Designing Distributed Systems. .To be a great collaborative programmer (in a work enviornment) -> Pragmattic Programmer, Code Complete, Mythical Man Month, A Philsophy of Software Design by Ousterhout. For philsophy of programming itself -> The Soul of a Machine

Edit: Programming is very broad and operates in many context from the technical, social, to the ideas behind it. I would say it is almost to early to have those definitive fundamental books

[carapace]

1. Knuth. Skim it all then keep as a reference. Dive deep into anything that catches your fancy.

2. "Programming Pearls" by Jon L. Bentley IMO this is the most concise yet accessible gateway to the inner Mysteries of Computer Programming. Read between the lines, the prime thesis is implied not explicit.

3. "Thinking Forth" by Leo Brodie (Available as a PDF here: http://thinking-forth.sourceforge.net/ ) Most software is grossly too large. This book shows how to grok and extract the essence of your problem into minimal code. (Chuck Moore had a 3D wireframe CAD program he used to carry around as a deck of punch cards in his shirt pocket.)