Understanding Computation (59 page)

Read Understanding Computation Online

Authors: Tom Stuart

Tags: #COMPUTERS / Programming / General

BOOK: Understanding Computation

12.54Mb size Format: txt, pdf, ePub

Read Book Download Book

Game of Life, Conway’s Game of Life – Conway’s Game of Life

GCC compiler, Coping with Uncomputability

general-purpose machines

about, General-Purpose Machines – General-Purpose Machines
encoding, Encoding
simulation, Simulation
universality of, Universal Systems Can Loop Forever

generalized nondeterministic finite automaton (GNFA), Just Add Power

Ghory, Imran, The Problem

GNFA (generalized nondeterministic finite automaton), Just Add Power

Gödel’s first incompleteness theorem, Why Does This Happen?

Goldbach conjecture, Too good to be true

Goldbach, Christian, Too good to be true

greatest common divisor, Universal Systems Can Perform Algorithms

guillemets, Expressions

halting problem, The Halting Problem – Fundamentally impossible

Hash class

about, Enumerable
#merge method, Statements

hashes, Data Structures

Hofstadter, Douglas, Programs Can Refer to Themselves

if expression, Control Flow , Statements

inference rules

formal semantics in practice, Formality
Simple example, Small-Step Semantics

infinite loops, Simulation , Numeric Operations , Universal Systems Can Loop Forever – Universal Systems Can Loop Forever

infinite streams, Infinite streams – Infinite streams

inheritance, Classes and Modules

input

deterministic finite automata, States, Rules, and Input
nondeterministic finite automata, Nondeterminism

inspecting objects, Inspecting Objects

instances

classes and, Classes and Modules , Expressions
methods and, Classes and Modules
virtual machines, Expressions

Integer#gcd method, Universal Systems Can Perform Algorithms

Interactive Ruby Shell (IRB), Interactive Ruby Shell

interpreters, operational semantics and, Applications , Finding Meaning

IRB (Interactive Ruby Shell), Interactive Ruby Shell

ISO/IEC 30170 standard, The Meaning of “Meaning”

Kernel module

#eval method, Expressions
#puts method, Code Is Data

key-value pairs, Data Structures

lambda calculus

about, Programming with Nothing
avoiding arbitrary recursion, Avoiding arbitrary recursion – Avoiding arbitrary recursion
constants and, Impersonating the Lambda Calculus
FizzBuzz problem, The Problem
FizzBuzz solution, The Solution – The Solution
impersonating, Impersonating the Lambda Calculus
implementing, Implementing the Lambda Calculus – Parsing
implementing Booleans, Booleans – Booleans
implementing lists, Lists – Lists
implementing numbers, Numbers – Numbers
implementing numeric operations, Numeric Operations – Numeric Operations
implementing pairs, Pairs
implementing predicates, Predicates
implementing strings, Strings
infinite streams, Infinite streams – Infinite streams
parsing, Parsing – Parsing
procs and, Working with Procs – Syntax
semantics, Semantics – Reducing expressions
SKI combinator calculus and, SKI Combinator Calculus – Iota
syntax, Syntax – Syntax
Turing machines and, Lambda Calculus – Lambda Calculus

Lee, Bruce, The Meaning of Programs

lexical analysis

about, Parsing with Pushdown Automata
parsing with PDA, Lexical Analysis – Lexical Analysis

Lisp programming languages, Code Is Data

lists

in FizzBuzz example, Lists – Lists
infinite streams, Infinite streams – Infinite streams

local variables, Local Variables and Assignment

lookahead technique, Practicalities

looping constructs

big-step semantics, Statements , Statements
denotational semantics, Statements , Statements
infinite loops, Simulation , Numeric Operations , Universal Systems Can Loop Forever – Universal Systems Can Loop Forever
small-step semantics, Statements , Statements

Lovecraft, H. P., Impossible Programs

machines (see computing machines)

main object, Objects and Methods

mathematical semantics (see denotational semantics)

Matz’s Ruby Interpreter (MRI), The Meaning of “Meaning” , Statements

meaning

finding, Finding Meaning
meaning of, The Meaning of “Meaning”

&:message shorthand, Enumerable

messages

arguments and, Objects and Methods
components of, Objects and Methods
methods and, Objects and Methods
objects and, Objects and Methods
Ruby shorthand, Enumerable

metalanguage, Small-Step Semantics , Expressions

methods

classes and, Classes and Modules , Classes and Modules , Monkey Patching
defining, Objects and Methods
inheritance and, Classes and Modules
instances and, Classes and Modules
messages and, Objects and Methods
modules and, Classes and Modules , Monkey Patching
objects and, Objects and Methods
passing arguments to, Expressions
private, Removing Constants
return constraints, Statements
variadic, Variadic Methods

ML programming language, Applications

modules

constants and, Defining Constants , Defining Constants
methods and, Classes and Modules , Monkey Patching

modulo operator, Numeric Operations

monkey patching, Monkey Patching

MRI (Matz’s Ruby Interpreter), The Meaning of “Meaning” , Statements

mruby project, The Meaning of “Meaning”

natural semantics (see big-step semantics)

nested strings, Just Add Power

nesting levels in balanced brackets example, Just Add Power – Just Add Power

NFA (nondeterministic finite automata)

about, Nondeterministic Finite Automata
balanced bracket example, Just Add Power – Just Add Power
converting to DFA, Equivalence – Equivalence
converting to regular expressions, Just Add Power
free moves feature, Free Moves – Free Moves
input, Nondeterminism
nondeterminism, Nondeterminism – Nondeterminism
regular expressions and, Semantics – Semantics
rules, Nondeterminism
simulation, Nondeterminism
states, Nondeterminism , Semantics
storage, Nondeterminism

nondeterminism, Nondeterminism – Nondeterminism

nondeterministic finite automata (see NFA)

nondeterministic pushdown automaton (see NPDA)

nondeterministic Turing machines, Nondeterministic Turing Machines

nonequivalence, NPDA and, Nonequivalence

NPDA (nondeterministic pushdown automaton)

about, Nondeterministic Pushdown Automata – Nondeterministic Pushdown Automata
nonequivalence, Nonequivalence
palindrome recognition example, Nondeterministic Pushdown Automata – Nondeterministic Pushdown Automata
simulation, Simulation – Simulation

numbers

absolute values, Abstraction: Multiplying Signs
in FizzBuzz example, Numbers – Numbers

numeric operations in FizzBuzz example, Numeric Operations – Numeric Operations

Object object

#inspect method, Inspecting Objects
new method, Objects and Methods
send method, Removing Constants
#to_s method, String Interpolation

objects

current object, Objects and Methods
inspecting, Inspecting Objects
messages and, Objects and Methods
methods and, Objects and Methods
string interpolation, String Interpolation
values and, Objects and Methods

OCaml programming language, Applications , Applications

operational semantics

about, Operational Semantics
big-step semantics, Big-Step Semantics – Applications , Statements
interpreters and, Applications , Finding Meaning
Simple programming language example, Expressions
small-step semantics, Small-Step Semantics – Applications , Statements

operator precedence, Expressions

output, deterministic finite automata, Output – Output

pairs in FizzBuzz example, Pairs

palindrome recognition example, Nondeterministic Pushdown Automata – Nondeterministic Pushdown Automata

parallel assignment, Local Variables and Assignment , Variadic Methods

parsers and parsing process

about, Syntax , Parsing with Pushdown Automata
implementing, Implementing Parsers – Implementing Parsers
lambda calculus, Parsing – Parsing
lexical analysis, Lexical Analysis – Lexical Analysis
lookahead technique, Practicalities
regular expressions, Parsing – Parsing
syntactic analysis, Syntactic Analysis – Syntactic Analysis
syntax and, Syntax

parsing expression grammar (PEG), Implementing Parsers

partial programming languages, Universal Systems Can Loop Forever

partial recursive functions, Partial Recursive Functions – Partial Recursive Functions

PDA (pushdown automaton)

about, Storage
deterministic, Deterministic Pushdown Automata – Simulation
nondeterministic, Nondeterministic Pushdown Automata – Nonequivalence
parsing with, Parsing with Pushdown Automata – Practicalities

PEG (parsing expression grammar), Implementing Parsers

PLT Redex programming language, Applications

power (computing)

about, Just Add Power – Just Add Power , How Much Power?
deterministic pushdown automata, Deterministic Pushdown Automata – Simulation
nondeterministic pushdown automata, Nondeterministic Pushdown Automata – Nonequivalence
parsing with PDA, Parsing with Pushdown Automata – Practicalities
Turing machines, Maximum Power – Multidimensional Tape

predicates in FizzBuzz example, Predicates

primitive recursive functions, Partial Recursive Functions

printing

procs and, The Problem
strings, Printing Strings

private methods, Removing Constants

procs, Working with Procs

(see also FizzBuzz program)
about, Procs , Working with Procs
arguments and, Arguments
calling, Procs
extensional equality, Equality
implementing numbers, Numbers – Numbers
lambda calculus and, Working with Procs
printing and, The Problem
reducing, Applications
syntax for, Syntax

programming languages

about, The Meaning of Programs
abstract machines and, Operational Semantics
denotational semantics, Denotational Semantics – Applications
dynamic semantics, Correctness , Static Semantics
essentials for specifying, The Meaning of “Meaning”
formal semantics, Formal Semantics in Practice – Alternatives
meaning of, The Meaning of “Meaning”
metalanguage and, Expressions
operational semantics, Operational Semantics – Applications
parsing with PDA, Parsing with Pushdown Automata
partial, Universal Systems Can Loop Forever
semantics of, The Meaning of “Meaning”
syntax of, The Meaning of “Meaning” , Syntax
total, Universal Systems Can Loop Forever , Depressing Implications

programs

about, The Meaning of Programs , Syntax
abstract machines and, Operational Semantics
denotational semantics, Denotational Semantics – Applications
formal semantics, Formal Semantics in Practice – Alternatives
meaning of, The Meaning of “Meaning”
operational semantics, Operational Semantics – Applications
parser, Syntax , Implementing Parsers – Implementing Parsers
predicting behavior of, Coping with Uncomputability , Programming in Toyland
self-referential, Programs Can Refer to Themselves – Programs Can Refer to Themselves , Why Does This Happen?
standing in for Turing machines, Programs Can Stand In for Turing Machines
sufficiently powerful, Programming in Toyland
syntax and, Syntax
unreachable code, Coping with Uncomputability

pushdown automaton (see PDA)

#puts method, Printing Strings

Other books

The Pretend Marriage: A Werewolf Romance by Steele, Dawn

Beyond (Afterlife book 1) by Willow Rose

The Chronology of Water by Lidia Yuknavitch

Day of the Oprichnik by Vladimir Sorokin

Rock the Heart by Michelle A. Valentine

In the Market for Love by Blake, Nina

Pet From Hell (Infected Series Book 1) by Gowland, Justin

Nan's Journey by Elaine Littau

Remember the Dreams by Christine Flynn

Liz Ireland by A Cowboy's Heart