Understanding Computation

• DRM-free ebooks—use your ebooks across devices without restrictions or limitations
  

• Multiple formats—use on your laptop, tablet, or phone
  

• Lifetime access, with free updates
  

• Dropbox syncing—your files, anywhere
  

This book is for programmers who are curious about programming languages and the theory of computation, especially those who don’t have a formal background in mathematics or computer science.

If you’re interested in the mind-expanding parts of computer science that deal with
programs, languages, and machines, but are discouraged by the mathematical language that’s
often used to explain them, this book is for you. Instead of complex notation we’ll use
working code to illustrate theoretical ideas and turn them into interactive experiments that
you can explore at your own pace.

This book assumes that you know at least one modern programming language like Ruby, Python, JavaScript, Java, or C#. All of the code examples are in Ruby, but if you know another language you should still be able to follow along. However, this book
isn’t
a guide to best practices in Ruby or object-oriented design. The code is intended to be clear and concise, but not necessarily to be easy to maintain; the goal is always to use Ruby to illustrate the computer science, not vice versa. It’s also not a textbook or an encyclopedia, so instead of presenting formal arguments or watertight proofs, this book tries to break the ice on some interesting ideas and inspire you to learn about them in more depth.

The following typographical conventions are used in this
book:

This book is here to help you get your job done. In general, if this
book includes code examples, you may use the code in your programs and
documentation. You do not need to contact us for permission unless you’re
reproducing a significant portion of the code. For example, writing a
program that uses several chunks of code from this book does not require
permission. Selling or distributing a CD-ROM of examples from O’Reilly
books does require permission. Answering a question by citing this book
and quoting example code does not require permission. Incorporating a
significant amount of example code from this book into your product’s
documentation does require permission.

We appreciate, but do not require, attribution. An attribution
usually includes the title, author, publisher, and ISBN. For example:
“
Understanding Computation
by Tom Stuart (O’Reilly). Copyright 2013
Tom Stuart, 978-1-4493-2927-3.”

If you feel your use of code examples falls outside fair use or the
permission given above, feel free to contact us at
[email protected]
.

Technology professionals, software developers, web designers, and
business and creative professionals use Safari Books Online as their
primary resource for research, problem solving, learning, and
certification training.

Safari Books Online offers a range of
product mixes
and pricing programs for
organizations
,
government
agencies
, and
individuals
.
Subscribers have access to thousands of books, training videos, and
prepublication manuscripts in one fully searchable database from
publishers like O’Reilly Media, Prentice Hall Professional, Addison-Wesley
Professional, Microsoft Press, Sams, Que, Peachpit Press, Focal Press,
Cisco Press, John Wiley & Sons, Syngress, Morgan Kaufmann, IBM
Redbooks, Packt, Adobe Press, FT Press, Apress, Manning, New Riders,
McGraw-Hill, Jones & Bartlett, Course Technology, and dozens
more
. For more
information about Safari Books Online, please visit us
online
.

Please address comments and questions concerning this book to the
publisher:

We have a web page for this book, where we list errata, examples,
and any additional information. You can access this page at
http://oreil.ly/understanding-computation
.

To comment or ask technical questions about this book, send email to
[email protected]
.

For more information about our books, courses, conferences, and
news, see our website at
http://www.oreilly.com
.

Find us on Facebook:
http://facebook.com/oreilly

Follow us on Twitter:
http://twitter.com/oreillymedia

Watch us on YouTube:
http://www.youtube.com/oreillymedia

I’m grateful for the hospitality of
Go Free
Range
, who provided me with office space, friendly conversation, and tea throughout
the writing of this book. Without their generous support, I’d definitely have gone a bit Jack
Torrance.

Thank you to James Adam, Paul Battley, James Coglan, Peter Fletcher, Chris Lowis, and
Murray Steele for their feedback on early drafts, and to Gabriel Kerneis and Alex Stangl for
their technical reviews. This book has been immeasurably improved by their thoughtful
contributions. I’d also like to thank Alan Mycroft from the University of Cambridge for all
the knowledge and encouragement he supplied.

Many people from O’Reilly helped shepherd this project to completion, but I’m especially
grateful to Mike Loukides and Simon St.Laurent for their early enthusiasm and faith in the
idea, to Nathan Jepson for his advice on how to turn the idea into an actual book, and to
Sanders Kleinfeld for humoring my relentless quest for perfect syntax highlighting.

Thank you to my parents for giving an annoying child the means, motive, and opportunity to
spend all his time mucking about with computers; and to Leila, for patiently reminding me,
every time I forgot how the job should be done, to keep putting one damn word after another. I
got there in the end.

If you already know Ruby, you can safely skip to
Chapter 2
without missing anything.

One of Ruby’s friendliest features
is its interactive console,
IRB
, which lets us enter pieces
of Ruby code and immediately see the results. In this book, we’ll use IRB extensively to
interact with the code we’re writing and explore how it works.

You can run IRB on your development machine by typing
irb
at the
command line. IRB shows a
>>
prompt
when it expects you to provide a Ruby expression. After you type an expression and
hit Enter, the code gets evaluated, and the result is shown at a
=>
prompt:

$
irb --simple-prompt
>>
1
+
2
=> 3
>>
'hello world'
.
length
=> 11

Whenever we see these
>>
and
=>
prompts in the book, we’re interacting with IRB. To make
longer code listings easier to read, they’ll be shown without the prompts, but we’ll still
assume that the code in these listings has been typed or pasted into IRB. So once the book has
shown some Ruby code like this…

x
=
2
y
=
3
z
=
x
+
y

…then we’ll be able to play with its results in IRB:

>>
x
*
y
*
z
=> 30

Ruby is
an
expression-oriented
language:
every valid piece of code produces a value when it’s executed. Here’s a
quick overview of the different kinds of Ruby value.

>>
(
true
&&
false
)
||
true
=> true
>>
(
3
+
3
)
*
(
14
/
2
)
=> 42
>>
'hello'
+
' world'
=> "hello world"
>>
'hello world'
.
slice
(
6
)
=> "w"

>>
:my_symbol
=> :my_symbol
>>
:my_symbol
==
:my_symbol
=> true
>>
:my_symbol
==
:another_symbol
=> false

>>
'hello world'
.
slice
(
11
)
=> nil

>>
numbers
=
[
'zero'
,
'one'
,
'two'
]
=> ["zero", "one", "two"]
>>
numbers
[
1
]
=> "one"
>>
numbers
.
push
(
'three'
,
'four'
)
=> ["zero", "one", "two", "three", "four"]
>>
numbers
=> ["zero", "one", "two", "three", "four"]
>>
numbers
.
drop
(
2
)
=> ["two", "three", "four"]

>>
ages
=
18
.
.
30
=> 18..30
>>
ages
.
entries
=> [18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
>>
ages
.
include?
(
25
)
=> true
>>
ages
.
include?
(
33
)
=> false

>>
fruit
=
{
'a'
=>
'apple'
,
'b'
=>
'banana'
,
'c'
=>
'coconut'
}
=> {"a"=>"apple", "b"=>"banana", "c"=>"coconut"}
>>
fruit
[
'b'
]
=> "banana"
>>
fruit
[
'd'
]
=
'date'
=> "date"
>>
fruit
=> {"a"=>"apple", "b"=>"banana", "c"=>"coconut", "d"=>"date"}

>>
dimensions
=
{
width
:
1000
,
height
:
2250
,
depth
:
250
}
=> {:width=>1000, :height=>2250, :depth=>250}
>>
dimensions
[
:depth
]
=> 250

>>
multiply
=
->
x
,
y
{
x
*
y
}
=> #
>>
multiply
.
call
(
6
,
9
)
=> 54
>>
multiply
.
call
(
2
,
3
)
=> 6

>>
multiply
[
3
,
4
]
=> 12

Ruby
has
if
,
case
, and
while
expressions, which work in the usual
way:

>>
if
2
<
3
'less'
else
'more'
end
=> "less"
>>
quantify
=
->
number
{
case
number
when
1
'one'
when
2
'a couple'
else
'many'
end
}
=> #
>>
quantify
.
call
(
2
)
=> "a couple"
>>
quantify
.
call
(
10
)
=> "many"
>>
x
=
1
=> 1
>>
while
x
<
1000
x
=
x
*
2
end
=> nil
>>
x
=> 1024

Ruby looks like
other dynamic programming languages but it’s unusual in an
important way: every value is
an
object
, and objects
communicate by
sending
messages
to each
other.
^[
1
]
Each object has its own
collection of
methods
that determine
how it responds to particular messages.

A message has a
name and, optionally, some
arguments. When an object receives a message, its
corresponding method is
executed with the arguments from the message. This is how
all work gets done in Ruby; even
1 + 2
means “send the object
1
a message
called
+
with the argument
2
,” and the object
1
has a
#+
method for handling that message.

We can define our own
methods with the
def
keyword:

>>
o
=
Object
.
new
=> #