Understanding Computation (34 page)

Using code to
represent data has some interesting advantages. Our proc-based lists don’t
have to be static: a list is just code that does the right thing when we pass it to
FIRST
and
REST
, so
we can easily implement lists that calculate their contents on the fly, also
known as
streams
. In fact, there’s no reason why
streams even need to be finite, because the calculation only has to generate the list
contents as they’re consumed, so it can keep producing new values indefinitely.

For example, here’s how to implement an infinite stream of
zeros:

ZEROS
=
Z
[->
f
{
UNSHIFT
[
f
][
ZERO
]
}
]

On the console, we can see that
ZEROS
behaves just
like a list, albeit one with no end in sight:

>>
to_integer
(
FIRST
[
ZEROS
]
)
=> 0
>>
to_integer
(
FIRST
[
REST
[
ZEROS
]]
)
=> 0
>>
to_integer
(
FIRST
[
REST
[
REST
[
REST
[
REST
[
REST
[
ZEROS
]]]]]]
)
=> 0

A helper method to turn this stream into a Ruby array would be
convenient, but
to_array
will run
forever unless we explicitly stop the conversion process. An optional
“maximum size” argument does the trick:

def
to_array
(
l
,
count
=
nil
)
array
=
[]
until
to_boolean
(
IS_EMPTY
[
l
]
)
||
count
==
0
array
.
push
(
FIRST
[
l
]
)
l
=
REST
[
l
]
count
=
count
-
1
unless
count
.
nil?
end
array
end

This lets us retrieve any number of elements from the stream and
turn them into an array:

>>
to_array
(
ZEROS
,
5
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [0, 0, 0, 0, 0]
>>
to_array
(
ZEROS
,
10
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>
to_array
(
ZEROS
,
20
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

ZEROS
doesn’t calculate a new element each time,
but that’s easy enough to do. Here’s a stream that counts upward from a given
number:

>>
UPWARDS_OF
=
Z
[->
f
{
->
n
{
UNSHIFT
[->
x
{
f
[
INCREMENT
[
n
]][
x
]
}
][
n
]
}
}
]
=> #
>>
to_array
(
UPWARDS_OF
[
ZERO
]
,
5
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [0, 1, 2, 3, 4]
>>
to_array
(
UPWARDS_OF
[
FIFTEEN
]
,
20
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34]

A more elaborate stream contains all the multiples of a given
number:

>>
MULTIPLES_OF
=
->
m
{
Z
[->
f
{
->
n
{
UNSHIFT
[->
x
{
f
[
ADD
[
m
][
n
]][
x
]
}
][
n
]
}
}
][
m
]
}
=> #
>>
to_array
(
MULTIPLES_OF
[
TWO
]
,
10
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
>>
to_array
(
MULTIPLES_OF
[
FIVE
]
,
20
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]

Remarkably, we can manipulate these infinite streams like any
other list. For example, we can make a new stream by mapping a proc
over an existing one:

>>
to_array
(
MULTIPLES_OF
[
THREE
]
,
10
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [3, 6, 9, 12, 15, 18, 21, 24, 27, 30]
>>
to_array
(
MAP
[
MULTIPLES_OF
[
THREE
]][
INCREMENT
]
,
10
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [4, 7, 10, 13, 16, 19, 22, 25, 28, 31]
>>
to_array
(
MAP
[
MULTIPLES_OF
[
THREE
]][
MULTIPLY
[
TWO
]]
,
10
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [6, 12, 18, 24, 30, 36, 42, 48, 54, 60]

We can even write procs that combine two streams to make a
third:

>>
MULTIPLY_STREAMS
=
Z
[->
f
{
->
k
{
->
l
{
UNSHIFT
[->
x
{
f
[
REST
[
k
]][
REST
[
l
]][
x
]
}
][
MULTIPLY
[
FIRST
[
k
]][
FIRST
[
l
]]]
}
}
}
]
=> #
>>
to_array
(
MULTIPLY_STREAMS
[
UPWARDS_OF
[
ONE
]][
MULTIPLES_OF
[
THREE
]]
,
10
)
.
map
{
|
p
|
to_integer
(
p
)
}
=> [3, 12, 27, 48, 75, 108, 147, 192, 243, 300]

Since the contents of a stream can be generated by any
computation, there’s nothing to stop us creating an infinite list of
the Fibonacci series, or the prime numbers, or all possible strings in
alphabetical order, or anything else computable. This abstraction is a
powerful one and doesn’t require any clever features on top of what we
already
have.

def
multiples_of
(
n
)
Enumerator
.
new
do
|
yielder
|
value
=
n
loop
do
yielder
.
yield
(
value
)
value
=
value
+
n
end
end
end

>>
multiples_of_three
=
multiples_of
(
3
)
=> #:each>
>>
multiples_of_three
.
next
=> 3
>>
multiples_of_three
.
next
=> 6
>>
multiples_of_three
.
next
=> 9

>>
multiples_of
(
3
)
.
first
=> 3
>>
multiples_of
(
3
)
.
take
(
10
)
=> [3, 6, 9, 12, 15, 18, 21, 24, 27, 30]
>>
multiples_of
(
3
)
.
detect
{
|
x
|
x
>
100
}
=> 102

>>
multiples_of
(
3
)
.
lazy
.
map
{
|
x
|
x
*
2
}
.
take
(
10
)
.
force
=> [6, 12, 18, 24, 30, 36, 42, 48, 54, 60]
>>
multiples_of
(
3
)
.
lazy
.
map
{
|
x
|
x
*
2
}
.
select
{
|
x
|
x
>
100
}
.
take
(
10
)
.
force
=> [102, 108, 114, 120, 126, 132, 138, 144, 150, 156]
>>
multiples_of
(
3
)
.
lazy
.
zip
(
multiples_of
(
4
))
.
map
{
|
a
,
b
|
a
*
b
}
.
take
(
10
)
.
force
=> [12, 48, 108, 192, 300, 432, 588, 768, 972, 1200]