Name: Understanding Computation
ISBN: 9781449329273

Understanding Computation

Finally, you can learn computation theory and programming language design in an engaging, practical way. Understanding Computation explains theoretical computer science in a context you’ll recognize, helping you appreciate why these ideas matter and how they can inform your day-to-day programming. Rather than use mathematical notation or an unfamiliar academic programming language like Haskell or Lisp, this book uses Ruby in a reductionist manner to present formal semantics, automata theory, and functional programming with the lambda calculus. It’s ideal for programmers versed in modern languages, with little or no formal training in computer science. Understand fundamental computing concepts, such as Turing completeness in languages Discover how programs use dynamic semantics to communicate ideas to machines Explore what a computer can do when reduced to its bare essentials Learn how universal Turing machines led to today’s general-purpose computers Perform complex calculations, using simple languages and cellular automata Determine which programming language features are essential for computation Examine how halting and self-referencing make some computing problems unsolvable Analyze programs by using abstract interpretation and type systems

What Hacker News says

rramadassMay 2026

This is quite unique and interesting; thanks for posting.

Seems like there might be some overlap with Tom Stuart's excellent Understanding Computation book - https://computationbook.com/

thread

rramadassFeb 2025

Another excellent book is Tom Stuart's Understanding Computation : From Simple Machines to Impossible Programs - https://computationbook.com/

thread

rramadassMar 2024

Nice!

If folks would like to learn these ideas by hand via programming, i highly recommend Tom Stuart's Understanding Computation From Simple Machines to Impossible Programs - https://computationbook.com/

thread

cbenMar 2023

There are 2 components here. One is the "type metaprogramming" - (mis)use of the type system to implement to do compile-time computation, mainly by using parametrized types as kinda-functions + type inference for kinda-pattern-matching.

The other is building up basic "data types" by pretty standard lambda calculus > LISP route. "Understanding Computation" book has a great chapter 6 on that, which is available in blog & video forms on https://computationbook.com/extras - Here, Church numerals were used to represent numbers. - booleans & conditionals here didn't resort to the lambda representation you'll see in the book, but relied on type conditionals builtin to TypeScript. - The names "Cons" & "nil" are a ringer for LISP-like building of lists, and recursive processing of lists, from a "pair" data type.

thread

jgrodziskiDec 2022

Understanding Computation by Tom Stuart is very good.

[https://computationbook.com]

thread

cbenJun 2022

"Understanding Computation: From Simple Machines to Impossible Programs". I knew many of topics and enjoyed it nonetheless. Highlights:

+ Very insightful chapter on different flavours of language semantics, and specs vs implementation.

+ The standard CS automata/ grammars stuff, but with working code.

+ Fun chapter on FizzBuzz in lambda calculus (it's also the free sample+video). Whats vool there is not just showing you _can_ compute everything (of vourse you can) but that you can build high-level constructs so the resulting code is todally clear.

+ A bit of the standard CS computability stuff, but then gets into esoterically minimalistic yet turning-complete stuff like 1D cellular automata.

+ Type checking as a form of partial evaluation, and some other "symbolic" stuff you can do with partially-evaluting interpreter. Some overlap with dependent types - but a more pragmatic less type-theoretic angle.

Author uses a carefully selected subset of ruby, introduced in a short intro - big props for being thoughtful about that.

P.S. +1 to Mazes book too (which is not as conscious about its ruby use, fun anyway)

thread