Understanding Computation

From Simple Machines to Impossible Programs

Tom Stuart (Autor)

Buch | Softcover

332 Seiten

2013
O'Reilly Media, Inc, USA (Verlag)
978-1-4493-2927-3 (ISBN)

Artikel merken

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

Tom Stuart is chief scientist at Expert Human. He is an experienced, passionate computer scientist and programmer. He work as a freelance consultant, mentor and trainer, helping all kinds of companies to improve the quality and clarity of their approach to creating software products, usually on the web. Sometimes this means spending a month writing code for them; at other times it means encouraging them to rethink their product, re-educate their teams, rewrite their tests, or ruthlessly refactor their code. He has lectured on compilers at the University of Cambridge, helped organize the Ru3y Manor conference, and is a member and speaker of the London Ruby User Group.

Chapter 1 Just Enough Ruby
Interactive Ruby Shell
Values
Control Flow
Objects and Methods
Classes and Modules
Miscellaneous Features
Programs and Machines
Chapter 2 The Meaning of Programs
The Meaning of “Meaning”
Syntax
Operational Semantics
Denotational Semantics
Formal Semantics in Practice
Implementing Parsers
Chapter 3 The Simplest Computers
Deterministic Finite Automata
Nondeterministic Finite Automata
Regular Expressions
Equivalence
Chapter 4 Just Add Power
Deterministic Pushdown Automata
Nondeterministic Pushdown Automata
Parsing with Pushdown Automata
How Much Power?
Chapter 5 The Ultimate Machine
Deterministic Turing Machines
Nondeterministic Turing Machines
Maximum Power
General-Purpose Machines
Computation and Computability
Chapter 6 Programming with Nothing
Impersonating the Lambda Calculus
Implementing the Lambda Calculus
Chapter 7 Universality Is Everywhere
Lambda Calculus
Partial Recursive Functions
SKI Combinator Calculus
Iota
Tag Systems
Cyclic Tag Systems
Conway’s Game of Life
Rule 110
Wolfram’s 2,3 Turing Machine
Chapter 8 Impossible Programs
The Facts of Life
Decidability
The Halting Problem
Other Undecidable Problems
Depressing Implications
Why Does This Happen?
Coping with Uncomputability
Chapter 9 Programming in Toyland
Abstract Interpretation
Static Semantics
Applications
Appendix Afterword
Colophon

Erscheint lt. Verlag	2.7.2013
Verlagsort	Sebastopol
Sprache	englisch
Maße	178 x 233 mm
Gewicht	531 g
Einbandart	kartoniert
Themenwelt	Informatik ► Programmiersprachen / -werkzeuge ► Ruby
	Mathematik / Informatik ► Informatik ► Software Entwicklung
	Informatik ► Theorie / Studium ► Theoretische Informatik
ISBN-10	1-4493-2927-6 / 1449329276
ISBN-13	978-1-4493-2927-3 / 9781449329273
Zustand	Neuware