| Description |
1 online resource (1 volume) : illustrations |
| Contents |
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 -- 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 -- 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 |
| Summary |
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 languagesDiscover how programs use dynamic semantics to communicate ideas to machinesExplore what a computer can do when reduced to its bare essentialsLearn how universal Turing machines led to today's general-purpose computersPerform complex calculations, using simple languages and cellular automataDetermine which programming language features are essential for computationExamine how halting and self-referencing make some computing problems unsolvableAnalyze programs by using abstract interpretation and type systems |
| Notes |
Print version record |
| Subject |
Mathematics -- Data processing.
|
|
Computer science.
|
|
Computational complexity.
|
|
Electronic Data Processing
|
|
Programming languages (Electronic computers)
|
|
Computational complexity
|
|
Computer science
|
|
Mathematics -- Data processing
|
| Form |
Electronic book
|
| ISBN |
1449329276 |
|
9781449329273 |
|
9781449330101 |
|
144933010X |
|
9781449330118 |
|
1449330118 |
|
