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 programmi...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Sebastopol, CA
O'Reilly Media
2013
|
| Subjects: | |
| Online Access: | |
| Collection: | O'Reilly - Collection details see MPG.ReNa |
Table of Contents:
- Regular Expressions
- Syntax
- Semantics
- Parsing
- Equivalence
- 4. Just Add Power
- Deterministic Pushdown Automata
- Storage
- Rules
- Determinism
- Simulation
- Nondeterministic Pushdown Automata
- Simulation
- Nonequivalence
- Parsing with Pushdown Automata
- Lexical Analysis
- Syntactic Analysis
- Practicalities
- How Much Power?
- 5. The Ultimate Machine
- Deterministic Turing Machines
- Storage
- Rules
- Determinism
- Simulation
- Nondeterministic Turing Machines
- Maximum Power
- Internal Storage
- Subroutines
- Multiple Tapes
- Multidimensional Tape
- General-Purpose Machines
- Encoding
- Simulation
- pt. II Computation and Computability
- 6. Programming with Nothing
- Impersonating the Lambda Calculus
- Working with Procs
- The Problem
- Numbers
- Booleans
- Predicates
- Pairs
- Numeric Operations
- Lists
- Strings
- The Solution
- Advanced Programming Techniques
- Implementing the Lambda Calculus
- Syntax
- Semantics
- Machine generated contents note: 1. Just Enough Ruby
- Interactive Ruby Shell
- Values
- Basic Data
- Data Structures
- Procs
- Control Flow
- Objects and Methods
- Classes and Modules
- Miscellaneous Features
- Local Variables and Assignment
- String Interpolation
- Inspecting Objects
- Printing Strings
- Variadic Methods
- Blocks
- Enumerable
- Struct
- Monkey Patching
- Defining Constants
- Removing Constants
- pt. I Programs and Machines
- 2. The Meaning of Programs
- The Meaning of "Meaning"
- Syntax
- Operational Semantics
- Small-Step Semantics
- Big-Step Semantics
- Denotational Semantics
- Expressions
- Statements
- Applications
- Formal Semantics in Practice
- Formality
- Finding Meaning
- Alternatives
- Implementing Parsers
- 3. The Simplest Computers
- Deterministic Finite Automata
- States, Rules, and Input
- Output
- Determinism
- Simulation
- Nondeterministic Finite Automata
- Nondeterminism
- Free Moves
- Parsing
- 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
- 8. Impossible Programs
- The Facts of Life
- Universal Systems Can Perform Algorithms
- Programs Can Stand In for Turing Machines
- Code Is Data
- Universal Systems Can Loop Forever
- Programs Can Refer to Themselves
- Decidability
- The Halting Problem
- Building a Halting Checker
- It'll Never Work
- Other Undecidable Problems
- Depressing Implications
- Why Does This Happen?
- Coping with Uncomputability
- 9. Programming in Toyland
- Abstract Interpretation
- Route Planning
- Abstraction: Multiplying Signs
- Safety and Approximation: Adding Signs
- Static Semantics
- Implementation
- Benefits and Limitations
- Applications