Read Understanding Computation Online

Authors: Tom Stuart

Tags: #COMPUTERS / Programming / General

Understanding Computation

BOOK: Understanding Computation
5.97Mb size Format: txt, pdf, ePub
ads
Understanding Computation
Tom Stuart

Beijing • Cambridge • Farnham • Köln • Sebastopol • Tokyo

Special Upgrade Offer

If you purchased this ebook directly from
oreilly.com
, you have the following benefits:

  • 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

If you purchased this ebook from another retailer, you can upgrade your ebook to take advantage of all these benefits for just $4.99.
Click here
to access your ebook upgrade.

Please note that upgrade offers are not available from sample content.

Preface
Who Should Read This Book?

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.

Conventions Used in This Book

The following typographical conventions are used in this
book:

Italic

Indicates new terms, URLs, email addresses, filenames, and
file extensions.

Constant width

Used for program listings, as well as within paragraphs to
refer to program elements such as variable or function names,
databases, data types, environment variables, statements, and
keywords.

Constant width bold

Shows commands or other text that should be typed literally by
the user.

Constant width italic

Shows text that should be replaced with user-supplied values
or by values determined by context.

Tip

This icon signifies a tip, suggestion, or general note.

Caution

This icon indicates a warning or caution.

Using Code Examples

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]
.

Safari® Books Online
Note

Safari Books Online (
www.safaribooksonline.com
)
is an on-demand digital library that delivers expert
content
in both
book and video form from the world’s leading authors in technology and
business.

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
.

How to Contact Us

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

O’Reilly Media, Inc.
1005 Gravenstein Highway North
Sebastopol, CA 95472
800-998-9938 (in the United States or Canada)
707-829-0515 (international or local)
707-829-0104 (fax)

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

Acknowledgments

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.

Chapter 1. Just Enough Ruby

The code in this book is written in Ruby, a programming language that was designed to be
simple, friendly, and fun. I’ve chosen it because of its clarity and flexibility, but nothing in
the book relies on special features of Ruby, so you should be able to translate the code
examples into whatever language you prefer—especially another dynamic language like Python or
JavaScript—if that helps to make the ideas clearer.

All of the example code is compatible with both Ruby 2.0 and Ruby 1.9. You can find out more
about Ruby, and download an official implementation, at the
official Ruby website
.

Let’s take a quick tour of Ruby’s features. We’ll concentrate on the
parts of the language that are used in this book; if you want to learn more,
O’Reilly’s
The Ruby Programming
Language
is a good place to start.

Note

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

Interactive Ruby Shell

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
Values

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.

Basic Data

As we’d expect, Ruby
supports Booleans, numbers, and strings, all of which come with the usual
operations:

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

A Ruby
symbol
is a
lightweight, immutable value representing a name. Symbols
are widely used in Ruby as simpler and less memory-intensive
alternatives to strings, most often as keys in hashes (see
Data Structures
). Symbol literals are written with a colon
at the beginning:

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

The special value
nil
is used
to indicate the absence of any useful value:

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

Ruby array
literals are written as a
comma-separated list of values surrounded by
square brackets:

>>
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"]

A
range
represents a
collection of values between a minimum and a maximum. Ranges are written by
putting a pair of
dots between two values:

>>
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

A
hash
is a
collection in which every value is associated with a key;
some programming languages call this data structure a “map,”
“dictionary,” or “associative array.” A hash literal is written as a
comma-separated list of
key
=>
value
pairs inside curly
brackets:

>>
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"}

Hashes often have symbols as keys, so Ruby
provides an alternative
key
:
value
syntax for writing key-value pairs where the
key is a
symbol. This is more compact than the
key
=>
value
syntax
and looks a lot like the popular JSON format for JavaScript objects:

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

A
proc
is an
unevaluated chunk of Ruby code that can be passed around
and evaluated on demand; other languages call this an “anonymous
function” or “lambda.” There are several ways of writing a proc literal,
the most compact of which is the
->
arguments
{
body
}
syntax:

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

As well as the
.call
syntax,
procs can be called by using
square
brackets:

>>
multiply
[
3
,
4
]
=> 12
Control Flow

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
Objects and Methods

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
=> #
>>
def
o
.
add
(
x
,
y
)
x
+
y
end
=> nil
>>
o
.
add
(
2
,
3
)
=> 5

Here we’re making a new object by sending the
new
message to a special built-in object
called
Object
; once the
new object’s been created, we define an
#add
method on it. The
#add
method adds its two arguments together and
returns the result—an explicit
return
isn’t necessary, because the value of the last expression to be executed
in a method is automatically returned. When we send that object the
add
message with
2
and
3
as
arguments, its
#add
method is executed
and we get back the answer we wanted.

We’ll usually send a message to an object by writing the receiving object and the
message name separated by a dot (e.g.,
o.add
),
but Ruby always keeps track of
the
current object
(called
self
) and will allow us to send a message to that object by writing a message
name on its own, leaving the receiver implicit. For example, inside a method definition the
current object is always the object that received the message that caused the method to
execute, so within a particular object’s method, we can send other messages to the same object
without referring to it explicitly:

>>
def
o
.
add_twice
(
x
,
y
)
add
(
x
,
y
)
+
add
(
x
,
y
)
end
=> nil
>>
o
.
add_twice
(
2
,
3
)
=> 10

Notice that we can send the
add
message to
o
from within the
#add_twice
method by writing
add(x, y)
instead of
o.add(x, y)
, because
o
is the object that the
add_twice
message was sent to.

Outside of any method definition, the current object is a special
top-level
object called
main
, and
any messages that don’t specify a receiver are sent to it; similarly, any
method definitions that don’t specify an object will be made available
through
main
:

>>
def
multiply
(
a
,
b
)
a
*
b
end
=> nil
>>
multiply
(
2
,
3
)
=> 6
BOOK: Understanding Computation
5.97Mb size Format: txt, pdf, ePub
ads

Other books

Trust by Serruya, Cristiane
Tap Out by Eric Devine
Pranked by Katy Grant
Finally by Miranda P. Charles
The Owl Keeper by Christine Brodien-Jones
Wishing in the Wings by Klasky, Mindy

© 100 Vampire Novels China Edition 2015 - 2022    Contact for me [email protected]