Understanding Computation. From Simple Machines to Impossible Programs - Helion

ebook

Autor: Tom Stuart
ISBN: 978-14-493-3010-1
stron: 332, Format: ebook
Data wydania: 2013-05-15
Księgarnia: Helion

Cena książki: 126,65 zł (poprzednio: 147,27 zł)
Oszczędzasz: 14% (-20,62 zł)

Osoby, które kupiły tę książkę, wybierały także »

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

Osoby które kupowały "Understanding Computation. From Simple Machines to Impossible Programs", wybierały także:

Windows Media Center. Domowe centrum rozrywki 66,67 zł, (8,00 zł -88%)
Ruby on Rails. Ćwiczenia 18,75 zł, (3,00 zł -84%)
Przywództwo w świecie VUCA. Jak być skutecznym liderem w niepewnym środowisku 58,64 zł, (12,90 zł -78%)
Scrum. O zwinnym zarządzaniu projektami. Wydanie II rozszerzone 58,64 zł, (12,90 zł -78%)
Od hierarchii do turkusu, czyli jak zarządzać w XXI wieku 58,64 zł, (12,90 zł -78%)

Spis treści

Understanding Computation. From Simple Machines to Impossible Programs eBook -- spis treści

Understanding Computation
Preface
- Who Should Read This Book?
- Conventions Used in This Book
- Using Code Examples
- Safari Books Online
- How to Contact Us
- Acknowledgments
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
I. Programs and Machines
- 2. The Meaning of Programs
  - The Meaning of Meaning
  - Syntax
  - Operational Semantics
    - Small-Step Semantics
      - Expressions
      - Statements
      - Correctness
      - Applications
    - Big-Step Semantics
      - Expressions
      - Statements
      - Applications
  - 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
  - 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
II. Computation and Computability
- 6. Programming with Nothing
  - Impersonating the Lambda Calculus
    - Working with Procs
      - Plumbing
      - Arguments
      - Equality
      - Syntax
    - The Problem
    - Numbers
    - Booleans
    - Predicates
    - Pairs
    - Numeric Operations
    - Lists
    - Strings
    - The Solution
    - Advanced Programming Techniques
      - Infinite streams
      - Avoiding arbitrary recursion
  - Implementing the Lambda Calculus
    - Syntax
    - Semantics
      - Replacing variables
      - Calling functions
      - Reducing expressions
    - Parsing
- 7. Universality Is Everywhere
  - Lambda Calculus
  - Partial Recursive Functions
  - SKI Combinator Calculus
  - Iota
  - Tag Systems
  - Cyclic Tag Systems
  - Conways Game of Life
  - Rule 110
  - Wolframs 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
    - Itll Never Work
      - Too good to be true
      - Fundamentally impossible
  - 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
A. Afterword
Index
About the Author
Colophon
Copyright