<p>There are several ways to learn about type theory. For a working programmer, 
   <a href="https://www.cis.upenn.edu/~bcpierce/tapl/">Types and Programming Languages</a> by B. Pierce is a good start.
<a href="https://www.cs.cmu.edu/~rwh/plbook/2nded.pdf">Practical Foundations for Programming Languages</a> by R. Harper might also be good. If you want a bit of easy to read background on operational semantics, 
I recommend G. Winskel's, <a href="https://mitpress.mit.edu/books/formal-semantics-programming-languages">The Formal Semantics of Programming Languages: An Introduction</a>. With T. Nipkow, G. Klein, <a href="http://www.concrete-semantics.org/">Concrete Semantics</a>, a variant of Winskel's book has been formalised for the Isabelle/HOL interactive proof assistant. I suspect it's really difficult to get to grips with a prover just from this (or any) book, you'd want an expert nearby to ask questions.
If you want a more mathematical approach to type-theory, you could look at
J. R. Hindley, J. P. Seldin, <a href="http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511809835">Lambda-Calculus and Combinators: An Introduction</a>, or
H. Barendregt's, <a href="http://ttic.uchicago.edu/~dreyer/course/papers/barendregt.pdf">Lambda Calculi with Types</a>. Although I wouldn't recommend starting from Barendregt.</p>

<p>If you want a single recommendation, I'd say read all of Pierce except Part VI (Higher-Order Systems), and implement the toy languages the book discusses. You'll end up with a strong grounding in type theory, and probably a better programmer too.</p>

CC BY-SA 3.0
2015-11-28T14:38:57.227Z
2015-11-28T14:50:41.980Z
2015-11-28T14:50:41.980Z
Martin Berger
<p>I recommend <em>Computability, Complexity, and Languages</em> by Martin Davis, Ron Sigal and Elaine Weyuker.</p>

CC BY-SA 3.0
2015-12-23T18:49:52.700Z
That's a beautiful book for old-skool TCS. Except for the part of domain theoretic semantics, which can be skipped.
Martin Berger
CC BY-SA 3.0
2015-12-23T14:13:59.407Z
2015-12-23T14:13:59.407Z
valepert
<p>I am big fan of Theory and Algorithms. I had once an opportunity to visit Theoretical Computer Science at Indian Institute of Technology, Madras (IIT-M), India. I have got a know about a lot theoreticians there at IIT-M. When I went there I didn't have any idea about what Theory was, but today I am total love with it.</p>

<p>Thanks to @Kate F for the pointer, yes Hopcroft and Ullman is an excellent place to start.</p>

<p>However here is how I have started,</p>

<ol>
<li><p>Read the Introduction to Algorithms by Cormen.&lt;\br>
This is an excellent place to start. When you study try to understand each proof in as much length as possible. If you understand the proof well, try to code the same logic in any language of your choice. (It takes a bit longer but its worth a try)</p></li>
<li><p>Follow the top conferences in Theory like <br/>FOCS <br/>SODA <br/>STOC <br/>
EC (Electronic Commerce) -- Algorithmic Game Theory <br/>
COLT (Conference on Learning Theory) -- Learning Theory <br/>
CRYPTO -- Cryptography <br/>
SOCG (Symposium on Computational Geometry) -- Computational Geometry <br/>
CCC (Conference on Computational Complexity) -- Complexity Theory <br/></p></li>
</ol>

<p>Even if you don't understand much try to read and <strong>THINK</strong> as much as possible.
You have to do as much proofs as possible..</p>

<ol start="3">
<li>This is a wonder place to look at if you are thinking of Computational complexity in particular (<a href="http://plato.stanford.edu/entries/computational-complexity/" rel="nofollow">This is from Stanford</a>). </li>
<li>Follow Prof. Sanjeev Arora, Boaz Barak, Jelani Nelson, Madhu Sudan </li>
<li>Here is a set of synthesized information in the field of <a href="http://www.cs.berkeley.edu/~luca/notes/complexitynotes02.pdf" rel="nofollow">Computational Complexity</a></li>
</ol>

CC BY-SA 3.0
2015-11-29T18:22:49.400Z
2015-11-29T18:34:14.450Z
2015-11-29T18:34:14.450Z
Jaugust
<p>It's a wide field with a few quite different areas.</p>

<p>I'd start with some of the most fundamental ideas about what computers are: Hopcroft and Ullman, "Introduction to Automata Theory, Languages and Computation."</p>

<p>The reason I'd recommend that in particular, is their emphasis on proofs. They guide you through a rigorous way of thinking. That's the difference between writing programs and being scientific.</p>

CC BY-SA 3.0
2015-11-27T21:18:24.273Z
Thanks! I don't know if this changes anything, but I do actually have some background in proof-based mathematics (I probably should have mentioned that in the question). I've done proof-based real analysis, point-set topology, and abstract algebra.
Henry H.
CC BY-SA 3.0
2015-11-27T21:21:05.480Z
Then you'll be able to work through it very quickly :)
Kate F
CC BY-SA 3.0
2015-11-29T01:09:46.903Z
its _a_ difference but not _the_ difference. CS entails many other principles etc
vzn
CC BY-SA 3.0
2015-11-30T08:51:08.470Z
I don't think that the need for rigor is really a difference between programming and math. Programming and proving theorems are imho very related tasks (cf. Curry-Howard Isomorphism), and hardly any non-mathematical task requires more rigor than programming. Compilers are much less forgiving about errors than humans who read proofs.
Jan Johannsen
CC BY-SA 3.0
2015-11-30T14:40:13.970Z
@JanJohannsen I'd quite disagree - for example, see Undefined Behaviour for C.
Kate F
CC BY-SA 3.0
2015-11-27T20:57:00.440Z
2015-11-27T20:57:00.440Z
Kate F
<p>I am a pretty proficient software engineer, but 
I don't know much theory.
I want to learn more theory.
Particular topics that I am interested in are:
computational complexity, formal languages, and type theory.
But I am at a loss as for how to begin learning about these fields.</p>

<blockquote>
  <p>What resources would you recommend to someone 
  who wants to learn more theory through self-study?
  Are there any theoretical computer science self-study guides 
  for software engineers?</p>
</blockquote>

CC BY-SA 3.0
2015-11-27T18:52:52.987Z
It depends what you want to learn about. [Arora-Barak](http://theory.cs.princeton.edu/complexity/) gives a thorough introduction to computational complexity theory (and is freely available online). So that is a good place to start.
Thomas Steinke
CC BY-SA 3.0
2015-11-27T22:38:05.743Z
Have you taken theory courses at college/university like data structures, algorithms, etc.? If you haven't taken typically required undergraduate theory courses then textbooks for those courses would be a good starting point. After that you can have a look at wikipedia articles, our [list of books](http://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read) and [list of videos](http://cstheory.stackexchange.com/questions/1198/what-videos-should-everybody-watch), online courses at Coursera/Udacity/EdX/... Coursera has pretty nice theory courses.
Kaveh
CC BY-SA 3.0
2015-11-28T07:09:43.797Z
What did you study in the college?
Omar Shehab
CC BY-SA 3.0
2015-11-29T07:03:06.313Z
What sort of languages do you program in? Much of theoretical CS can be learned in tandem with something concrete. For instance if you want to learn more about formal languages, regular languages/expressions (i.e. regexp's) are a good place to start as is learning about for compilers. For type theory, you might want to play with a statically typed language like haskell, F# or ML.
Baby Dragon
CC BY-SA 3.0
2015-12-02T23:46:25.803Z
try [New Turing Omnibus](http://www.amazon.com/The-New-Turing-Omnibus-Excursions/dp/0805071660) by Dewdney as a broad/ accessible intro ref/ survey/ cross section. see also [pop science books that inspire TCS](http://cstheory.stackexchange.com/questions/18968/what-are-the-popular-science-books-that-inspire-tcs)
vzn
<soft-question><teaching><books>
Theoretical computer science self-study resources for programmers
Henry H.
# Theoretical computer science self-study resources for programmers

(Asked by: username_0 on 2015-11-27)

I am a pretty proficient software engineer, but
I don't know much theory.
I want to learn more theory.
Particular topics that I am interested in are:
computational complexity, formal languages, and type theory.
But I am at a loss as for how to begin learning about these fields.

> What resources would you recommend to someone
> who wants to learn more theory through self-study?
> Are there any theoretical computer science self-study guides
> for software engineers?

**Tags:** soft-question, teaching, books

> **Comments:**
> **username_1**: It depends what you want to learn about. [Arora-Barak](http://theory.cs.princeton.edu/complexity/) gives a thorough introduction to computational complexity theory (and is freely available online). So that is a good place to start.  
> **username_2**: Have you taken theory courses at college/university like data structures, algorithms, etc.? If you haven't taken typically required undergraduate theory courses then textbooks for those courses would be a good starting point. After that you can have a look at wikipedia articles, our [list of books](http://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read) and [list of videos](http://cstheory.stackexchange.com/questions/1198/what-videos-should-everybody-watch), online courses at Coursera/Udacity/EdX/... Coursera has pretty nice theory courses.  
> **username_3**: What did you study in the college?  
> **username_4**: What sort of languages do you program in? Much of theoretical CS can be learned in tandem with something concrete. For instance if you want to learn more about formal languages, regular languages/expressions (i.e. regexp's) are a good place to start as is learning about for compilers. For type theory, you might want to play with a statically typed language like haskell, F# or ML.  
> **username_5**: try [New Turing Omnibus](http://www.amazon.com/The-New-Turing-Omnibus-Excursions/dp/0805071660) by Dewdney as a broad/ accessible intro ref/ survey/ cross section. see also [pop science books that inspire TCS](http://cstheory.stackexchange.com/questions/18968/what-are-the-popular-science-books-that-inspire-tcs)  

---

## 4 answers

### Answer by username_9 on 2015-11-27. Score: 8 | Accepted answer

It's a wide field with a few quite different areas.

I'd start with some of the most fundamental ideas about what computers are: Hopcroft and Ullman, "Introduction to Automata Theory, Languages and Computation."

The reason I'd recommend that in particular, is their emphasis on proofs. They guide you through a rigorous way of thinking. That's the difference between writing programs and being scientific.

> **Comments:**
> **username_0**: Thanks! I don't know if this changes anything, but I do actually have some background in proof-based mathematics (I probably should have mentioned that in the question). I've done proof-based real analysis, point-set topology, and abstract algebra.  
> **username_9**: Then you'll be able to work through it very quickly :)  
> **username_5**: its _a_ difference but not _the_ difference. CS entails many other principles etc  
> **username_10**: I don't think that the need for rigor is really a difference between programming and math. Programming and proving theorems are imho very related tasks (cf. Curry-Howard Isomorphism), and hardly any non-mathematical task requires more rigor than programming. Compilers are much less forgiving about errors than humans who read proofs.  
> **username_9**: @JanJohannsen I'd quite disagree - for example, see Undefined Behaviour for C.  

---

### Answer by username_6 on 2015-11-28. Score: 9

There are several ways to learn about type theory. For a working programmer,
[Types and Programming Languages](https://www.cis.upenn.edu/~bcpierce/tapl/) by B. Pierce is a good start.
[Practical Foundations for Programming Languages](https://www.cs.cmu.edu/~rwh/plbook/2nded.pdf) by R. Harper might also be good. If you want a bit of easy to read background on operational semantics,
I recommend G. Winskel's, [The Formal Semantics of Programming Languages: An Introduction](https://mitpress.mit.edu/books/formal-semantics-programming-languages). With T. Nipkow, G. Klein, [Concrete Semantics](http://www.concrete-semantics.org/), a variant of Winskel's book has been formalised for the Isabelle/HOL interactive proof assistant. I suspect it's really difficult to get to grips with a prover just from this (or any) book, you'd want an expert nearby to ask questions.
If you want a more mathematical approach to type-theory, you could look at
J. R. Hindley, J. P. Seldin, [Lambda-Calculus and Combinators: An Introduction](http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511809835), or
H. Barendregt's, [Lambda Calculi with Types](http://ttic.uchicago.edu/~dreyer/course/papers/barendregt.pdf). Although I wouldn't recommend starting from Barendregt.

If you want a single recommendation, I'd say read all of Pierce except Part VI (Higher-Order Systems), and implement the toy languages the book discusses. You'll end up with a strong grounding in type theory, and probably a better programmer too.


---

### Answer by username_7 on 2015-12-23. Score: 2

I recommend *Computability, Complexity, and Languages* by Martin Davis, Ron Sigal and Elaine Weyuker.

> **Comments:**
> **username_6**: That's a beautiful book for old-skool TCS. Except for the part of domain theoretic semantics, which can be skipped.  

---

### Answer by username_8 on 2015-11-29. Score: 1

I am big fan of Theory and Algorithms. I had once an opportunity to visit Theoretical Computer Science at Indian Institute of Technology, Madras (IIT-M), India. I have got a know about a lot theoreticians there at IIT-M. When I went there I didn't have any idea about what Theory was, but today I am total love with it.

Thanks to @username_9 for the pointer, yes Hopcroft and Ullman is an excellent place to start.

However here is how I have started,

1. Read the Introduction to Algorithms by Cormen.<\br>
   This is an excellent place to start. When you study try to understand each proof in as much length as possible. If you understand the proof well, try to code the same logic in any language of your choice. (It takes a bit longer but its worth a try)
2. Follow the top conferences in Theory like   
   FOCS   
   SODA   
   STOC   
   EC (Electronic Commerce) -- Algorithmic Game Theory   
   COLT (Conference on Learning Theory) -- Learning Theory   
   CRYPTO -- Cryptography   
   SOCG (Symposium on Computational Geometry) -- Computational Geometry   
   CCC (Conference on Computational Complexity) -- Complexity Theory

Even if you don't understand much try to read and **THINK** as much as possible.
You have to do as much proofs as possible..

3. This is a wonder place to look at if you are thinking of Computational complexity in particular ([This is from Stanford](http://plato.stanford.edu/entries/computational-complexity/)).
4. Follow Prof. Sanjeev Arora, Boaz Barak, Jelani Nelson, Madhu Sudan
5. Here is a set of synthesized information in the field of [Computational Complexity](http://www.cs.berkeley.edu/~luca/notes/complexitynotes02.pdf)


---

