<p>The Semantics of Programming Languages is an important and very mathematical subject. Great strides have been made in the past 20 or so years. One book that stands out is <a href="http://rads.stackoverflow.com/amzn/click/0387947752" rel="nofollow noreferrer">A Theory of Objects</a> by <a href="https://en.wikipedia.org/wiki/Luca_Cardelli" rel="nofollow noreferrer">Luca Cardelli</a> and <a href="https://en.wikipedia.org/wiki/Mart%C3%ADn_Abadi" rel="nofollow noreferrer">Martín Abadi</a></p>

<p>Luca, especially, is an expert in operational semantics. He presents a generalized operational calculus for analyzing all aspects of object-oriented languages. The book is deep, but essential for those wanting a deep understanding of the underlying principles of OO languages and, perhaps, wanting to design future languages. </p>

<p>Language is more than syntax. It is the semantics that lets the student form proper hypotheses about programs and programming.  </p>

<p>Most compilers are still "syntax directed" but <a href="https://www.microsoft.com/en-us/research/people/petelee/" rel="nofollow noreferrer">Peter Lee</a>, in his doctoral dissertation (U of Michigan). shows how a compiler can be built from the semantics instead. </p>

CC BY-SA 3.0
2017-07-29T13:58:20.770Z
2017-07-29T14:29:25.830Z
2017-07-29T14:29:25.830Z
Buffy
<p>Another classic is <a href="http://rads.stackoverflow.com/amzn/click/0716710455" rel="nofollow noreferrer"><em>Computers and Intractability: A Guide to the Theory of NP-Completeness</em></a> by Garey and Johnson. As you may know, <a href="https://en.wikipedia.org/wiki/NP_(complexity)" rel="nofollow noreferrer">NP</a> (which stands for "nondeterministic polynomial time") refers to a set of problems that are computationally very difficult but whose answers can be checked in polynomial time relative to the size of their input. Whether all such problems can be solved in polynomial time (<a href="https://en.wikipedia.org/wiki/P_versus_NP_problem" rel="nofollow noreferrer">P=NP</a>?) is one of the greatest unsolved questions in computer science. </p>

<p>Garey and Johnson (as the book is referred to) is about <a href="https://en.wikipedia.org/wiki/P_versus_NP_problem" rel="nofollow noreferrer">NP-Complete</a> problems, members of NP to which all other members of NP could be reduced. The book catalogs problems known to be NP-complete, including proofs that they are members, usually reductions from other NP-complete problems.</p>

<p>Published in 1979, the book is somewhat outdated but is still regarded as a classic<a href="https://en.wikipedia.org/wiki/Computers_and_Intractability" rel="nofollow noreferrer"> [3]</a>. (<a href="https://scholar.google.com/scholar?cites=56570571081301115&amp;as_sdt=2005&amp;sciodt=0,5&amp;hl=en" rel="nofollow noreferrer">Google Scholar</a> lists about 60,000 citations.) The introduction (available <a href="https://pdfs.semanticscholar.org/fa33/c3a89a423f0eb00134fd291894949bf9d54e.pdf" rel="nofollow noreferrer">online</a>), in which an employee explains to their boss why they can't provide a simple solution to a problem, is also classic.</p>

<p>Disclaimer: I am not a theoretical computer scientist. I welcome comments from any.</p>

CC BY-SA 3.0
2017-07-30T23:10:39.997Z
2017-07-30T23:20:34.947Z
2017-07-30T23:20:34.947Z
Ellen Spertus
<p><a href="http://rads.stackoverflow.com/amzn/click/0321751043" rel="nofollow noreferrer">The Art of Computer Programming</a> in four volumes by Knuth is an obvious choice. </p>

<p>The first chapter of the first volume is a pretty solid course in discrete mathematics all by itself. If you can do all of the problems in that chapter you can earn a PhD in CS. (Some of the problems remain unsolved, I think - at least they were when the book was first published.)</p>

<p>Knuth is a Mathematician turned Computer Scientist and gives the mathematician's view of the field about as well as anyone can. You can depend on the accuracy of the book as the author has induced the community to drive out all inaccuracies using bounties. </p>

CC BY-SA 3.0
2017-07-29T17:52:34.190Z
ob xkcd: https://xkcd.com/163/
Ellen Spertus
CC BY-SA 3.0
2017-07-29T17:52:59.723Z
Someone without your mathematical background might start with Knuth's *Concrete Mathematics*.
Ellen Spertus
CC BY-SA 3.0
2017-08-04T08:15:45.563Z
While those are excellent books, they are nigh impossible to read cover-to-cover, even for seasoned academics, yet alone students. If using this, be sure you pick small, self-contained sections and make sure beforehand that the students have all the preliminary knowledge required for understanding the chapters. Knuth is excellent if you want to go really deep, but the amount of time you need to spend on each single page to properly understand it is *very* high.
ComicSansMS
CC BY-SA 3.0
2017-09-10T11:31:33.707Z
@Ellen Spertus: "Someone without your mathematical background" The OP is a mathematician.
beroal
CC BY-SA 3.0
2017-09-10T14:40:05.200Z
@beroal I know. I was saying that the OP could skip Concrete Mathematics but others might find it useful background.
Ellen Spertus
CC BY-SA 3.0
2017-09-10T14:41:50.587Z
@EllenSpertus Thanks for the vote of confidence, but I'd probably find it an interesting read.
Buffy
CC BY-SA 3.0
2017-09-10T14:43:07.977Z
You're not the OP.
Ellen Spertus
CC BY-SA 3.0
2017-09-10T14:44:20.103Z
@EllenSpertus, thought you meant for the answer. Oh well. Back to our regularly scheduled programming.
Buffy
CC BY-SA 3.0
2017-07-29T13:07:18.963Z
2017-07-29T17:36:25.687Z
2017-07-29T17:36:25.687Z
Buffy
<p>In addition to Knuth, I would recommend the classic <a href="https://mitpress.mit.edu/sicp/" rel="nofollow noreferrer">Structure and Interpretation of Computer Programming</a> by Abelson and Sussman. It covers such topics as:</p>

<ul>
<li>Writing simple programs that do powerful things,</li>
<li>Blurring the lines between data and code, including functions as first-class objects,</li>
<li>Creating little languages to solve problems,</li>
<li>Writing an interpreter,</li>
</ul>

<p>and much more.</p>

<p>It is one of the most loved and respected CS books. See also:</p>

<ul>
<li><a href="https://people.eecs.berkeley.edu/~bh/sicp.html" rel="nofollow noreferrer">Why <em>Structure and Interpretation of Computer Programs</em> matters</a>, by Brian Harvey</li>
<li><a href="https://www.quora.com/Is-Structure-and-Interpretation-of-Computer-Programs-SICP-worth-reading" rel="nofollow noreferrer">Is "Structure and Interpretation of Computer Programs" (SICP) worth reading?</a> (Quora)</li>
</ul>

<p>Note that the text, in various formats (<a href="https://mitpress.mit.edu/sicp/full-text/book/book.html" rel="nofollow noreferrer">original HTML</a>, <a href="http://sarabander.github.io/sicp/" rel="nofollow noreferrer">HTML5</a>, <a href="https://github.com/sarabander/sicp-pdf/raw/master/sicp.pdf" rel="nofollow noreferrer">PDF</a>), is available for free online, as are <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/" rel="nofollow noreferrer">video lectures by the authors</a>.</p>

CC BY-SA 3.0
2017-09-10T11:42:56.157Z
IMHO, this book is not rigorous enough for a mathematician. There are no theorems, no proofs.
beroal
CC BY-SA 3.0
2017-09-10T14:49:20.950Z
@beroal it depends what the OP wants to learn. Not all of computer science is theorems and proofs. SICP is considered the deepest introduction to programming, which is part of computer science.
Ellen Spertus
CC BY-SA 3.0
2017-07-29T17:52:07.933Z
2017-07-30T23:37:37.060Z
2017-07-30T23:37:37.060Z
Ellen Spertus
<p>I am a mathematician but I would like to learn basics of computer science. I have seen many books that are fine but has some mistakes. For example, <code>Introduction to algorithms</code> even says that one should use $f(n)\in O(g(n))$ but still uses the notation $f(n)= O(g(n))$.</p>

<p>Is there university level computer science books that are suitable for person who wants to study computer science on very rigorous books, or that are aimed to mathematician?</p>

CC BY-SA 3.0
2017-07-29T09:31:01.360Z
welcome to [cseducators.se]! A very nice question. I advise you use the [tag:resource-request] tag.
ItamarG3
CC BY-SA 3.0
2017-07-29T12:50:06.720Z
Those answering are encouraged to do more than name a book. Say why you believe the book is a good fit, and describe it to some extent. One book per answer is likely better than a single long list.
Buffy
CC BY-SA 3.0
2017-07-29T21:29:59.977Z
I already gave one answer (SICP), but, if I could give a second, I might suggest *Computers and Intractability*. https://en.wikipedia.org/wiki/Computers_and_Intractability
Ellen Spertus
CC BY-SA 3.0
2017-07-30T01:12:49.553Z
@EllenSpertus As I understand it, in situations like this, the limit is one "resource" per answer, with appropriate supporting text to clarify why it's recommended and how it fits the question. I don't recall anything limiting it to one answer per user, however. Even on non-list questions a second answer is acceptable, as long as it is distinct from the first one, as they must be, by definition, in this case. Write up the answer supporting _Computers and Intractability_.
Gypsy Spellweaver
CC BY-SA 3.0
2017-07-30T22:53:59.547Z
@GypsySpellweaver I had not realized I could give multiple answers. I'll do so.
Ellen Spertus
CC BY-SA 3.0
2017-09-10T11:42:14.510Z
I am afraid that your requirements "basics" and "rigor" are incompatible. Introductory books are intended for programmers, and programmers on average have weaker mathematical background and demands. Hence I recommend to pick a book for each topic in Computer Science. As you can see, some answers ("A Theory of Objects", "Computers and Intractability: A Guide to the Theory of NP-Completeness") are already narrow.
beroal
<self-learning><resource-request>
Book recommendations for rigorous CS books
# Book recommendations for rigorous CS books

(Asked by: username_0 on 2017-07-29)

I am a mathematician but I would like to learn basics of computer science. I have seen many books that are fine but has some mistakes. For example, `Introduction to algorithms` even says that one should use $f(n)\in O(g(n))$ but still uses the notation $f(n)= O(g(n))$.

Is there university level computer science books that are suitable for person who wants to study computer science on very rigorous books, or that are aimed to mathematician?

**Tags:** self-learning, resource-request

> **Comments:**
> **username_1**: welcome to [cseducators.se]! A very nice question. I advise you use the [tag:resource-request] tag.  
> **username_2**: Those answering are encouraged to do more than name a book. Say why you believe the book is a good fit, and describe it to some extent. One book per answer is likely better than a single long list.  
> **username_3**: I already gave one answer (SICP), but, if I could give a second, I might suggest *Computers and Intractability*. https://en.wikipedia.org/wiki/Computers_and_Intractability  
> **username_4**: @EllenSpertus As I understand it, in situations like this, the limit is one "resource" per answer, with appropriate supporting text to clarify why it's recommended and how it fits the question. I don't recall anything limiting it to one answer per user, however. Even on non-list questions a second answer is acceptable, as long as it is distinct from the first one, as they must be, by definition, in this case. Write up the answer supporting _Computers and Intractability_.  
> **username_3**: @GypsySpellweaver I had not realized I could give multiple answers. I'll do so.  
> **username_5**: I am afraid that your requirements "basics" and "rigor" are incompatible. Introductory books are intended for programmers, and programmers on average have weaker mathematical background and demands. Hence I recommend to pick a book for each topic in Computer Science. As you can see, some answers ("A Theory of Objects", "Computers and Intractability: A Guide to the Theory of NP-Completeness") are already narrow.  

---

## 4 answers

### Answer by username_2 on 2017-07-29. Score: 7

[The Art of Computer Programming](http://rads.stackoverflow.com/amzn/click/0321751043) in four volumes by Knuth is an obvious choice.

The first chapter of the first volume is a pretty solid course in discrete mathematics all by itself. If you can do all of the problems in that chapter you can earn a PhD in CS. (Some of the problems remain unsolved, I think - at least they were when the book was first published.)

Knuth is a Mathematician turned Computer Scientist and gives the mathematician's view of the field about as well as anyone can. You can depend on the accuracy of the book as the author has induced the community to drive out all inaccuracies using bounties.

> **Comments:**
> **username_3**: ob xkcd: https://xkcd.com/163/  
> **username_3**: Someone without your mathematical background might start with Knuth's *Concrete Mathematics*.  
> **username_6**: While those are excellent books, they are nigh impossible to read cover-to-cover, even for seasoned academics, yet alone students. If using this, be sure you pick small, self-contained sections and make sure beforehand that the students have all the preliminary knowledge required for understanding the chapters. Knuth is excellent if you want to go really deep, but the amount of time you need to spend on each single page to properly understand it is *very* high.  
> **username_5**: @username_3: "Someone without your mathematical background" The OP is a mathematician.  
> **username_3**: @username_5 I know. I was saying that the OP could skip Concrete Mathematics but others might find it useful background.  
> **username_2**: @EllenSpertus Thanks for the vote of confidence, but I'd probably find it an interesting read.  
> **username_3**: You're not the OP.  
> **username_2**: @EllenSpertus, thought you meant for the answer. Oh well. Back to our regularly scheduled programming.  

---

### Answer by username_3 on 2017-07-29. Score: 4

In addition to Knuth, I would recommend the classic [Structure and Interpretation of Computer Programming](https://mitpress.mit.edu/sicp/) by Abelson and Sussman. It covers such topics as:

* Writing simple programs that do powerful things,
* Blurring the lines between data and code, including functions as first-class objects,
* Creating little languages to solve problems,
* Writing an interpreter,

and much more.

It is one of the most loved and respected CS books. See also:

* [Why *Structure and Interpretation of Computer Programs* matters](https://people.eecs.berkeley.edu/~bh/sicp.html), by Brian Harvey
* [Is "Structure and Interpretation of Computer Programs" (SICP) worth reading?](https://www.quora.com/Is-Structure-and-Interpretation-of-Computer-Programs-SICP-worth-reading) (Quora)

Note that the text, in various formats ([original HTML](https://mitpress.mit.edu/sicp/full-text/book/book.html), [HTML5](http://sarabander.github.io/sicp/), [PDF](https://github.com/sarabander/sicp-pdf/raw/master/sicp.pdf)), is available for free online, as are [video lectures by the authors](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/).

> **Comments:**
> **username_5**: IMHO, this book is not rigorous enough for a mathematician. There are no theorems, no proofs.  
> **username_3**: @username_5 it depends what the OP wants to learn. Not all of computer science is theorems and proofs. SICP is considered the deepest introduction to programming, which is part of computer science.  

---

### Answer by username_2 on 2017-07-29. Score: 2

The Semantics of Programming Languages is an important and very mathematical subject. Great strides have been made in the past 20 or so years. One book that stands out is [A Theory of Objects](http://rads.stackoverflow.com/amzn/click/0387947752) by [Luca Cardelli](https://en.wikipedia.org/wiki/Luca_Cardelli) and [Martín Abadi](https://en.wikipedia.org/wiki/Mart%C3%ADn_Abadi)

Luca, especially, is an expert in operational semantics. He presents a generalized operational calculus for analyzing all aspects of object-oriented languages. The book is deep, but essential for those wanting a deep understanding of the underlying principles of OO languages and, perhaps, wanting to design future languages.

Language is more than syntax. It is the semantics that lets the student form proper hypotheses about programs and programming.

Most compilers are still "syntax directed" but [Peter Lee](https://www.microsoft.com/en-us/research/people/petelee/), in his doctoral dissertation (U of Michigan). shows how a compiler can be built from the semantics instead.


---

### Answer by username_3 on 2017-07-30. Score: 0

Another classic is [*Computers and Intractability: A Guide to the Theory of NP-Completeness*](http://rads.stackoverflow.com/amzn/click/0716710455) by Garey and Johnson. As you may know, [NP](https://en.wikipedia.org/wiki/NP_(complexity)) (which stands for "nondeterministic polynomial time") refers to a set of problems that are computationally very difficult but whose answers can be checked in polynomial time relative to the size of their input. Whether all such problems can be solved in polynomial time ([P=NP](https://en.wikipedia.org/wiki/P_versus_NP_problem)?) is one of the greatest unsolved questions in computer science.

Garey and Johnson (as the book is referred to) is about [NP-Complete](https://en.wikipedia.org/wiki/P_versus_NP_problem) problems, members of NP to which all other members of NP could be reduced. The book catalogs problems known to be NP-complete, including proofs that they are members, usually reductions from other NP-complete problems.

Published in 1979, the book is somewhat outdated but is still regarded as a classic [[3]](https://en.wikipedia.org/wiki/Computers_and_Intractability). ([Google Scholar](https://scholar.google.com/scholar?cites=56570571081301115&as_sdt=2005&sciodt=0,5&hl=en) lists about 60,000 citations.) The introduction (available [online](https://pdfs.semanticscholar.org/fa33/c3a89a423f0eb00134fd291894949bf9d54e.pdf)), in which an employee explains to their boss why they can't provide a simple solution to a problem, is also classic.

Disclaimer: I am not a theoretical computer scientist. I welcome comments from any.


---

