### 25` `Deconstructing Loops

#### 25.1` `Setup: Two Functions

```
fun gcd(a, b):
if b == 0:
a
else:
gcd(b, num-modulo(a, b))
end
end
fun pr(n):
fun g(x): num-modulo((x * x) + 1, n) end
fun iter(x, y, d):
new-x = g(x)
new-y = g(g(y))
new-d = gcd(num-abs(new-x - new-y), n)
ask:
| new-d == 1 then:
iter(new-x, new-y, new-d)
| new-d == n then:
none
| otherwise:
some(new-d)
end
end
iter(2, 2, 1)
end
```

`gcd`

by calling itself and
`pr`

with recursion on its inner function. But if you’ve
programmed before, you’ve probably written similar programs with
loops.Exercise

Because we don’t have loops in Pyret, the best we can do is to use a higher-order function; which ones would you use?

But let’s see if we can do something “better”, i.e., get closer to a traditional-looking program.

`gcd`

:
```
check:
gcd(4, 5) is 1
gcd(5, 7) is 1
gcd(21, 21) is 21
gcd(12, 24) is 12
gcd(12, 9) is 3
end
```

#### 25.2` `Abstracting a Loop

```
data LoopStatus:
| done(final-value)
| next-2(new-arg-1, new-arg-2)
end
```

```
fun loop-2(f, arg-1, arg-2):
r = f(arg-1, arg-2)
cases (LoopStatus) r:
| done(v) => v
| next-2(new-arg-1, new-arg-2) => loop-2(f, new-arg-1, new-arg-2)
end
end
```

`gcd`

. (It is generic in the same way that higher-order functions
like `map`

and `filter`

are generic.) It just repeats if
`f`

says to repeat, stops if `f`

says to stop. This is the
essence of a loop.Exercise

Observe also that we could, if we wanted, stage [Staging]

`loop-2`

, because`f`

never changes. Rewrite it that way.

`loop-2`

, we can rewrite `gcd`

:
```
fun gcd(p, q):
loop-2(
{(a, b):
if b == 0:
done(a)
else:
next-2(b, num-modulo(a, b))
end},
p,
q)
end
```

`gcd`

code as a function and there’s this `LoopStatus`

datatype and…everything’s gotten much more complicated.`for`

construct in Pyret
actually rewrites as follows:
`for F(a from a_i, b from b_i, …): BODY end`

`F({(a, b, …): BODY}, a_i, b_i, …)`

`for map(i from range(0, 10)): i + 1 end`

`map({(i): i + 1}, range(0, 10))`

`gcd`

.
Going in reverse, we can rewrite
`F({(a, b, …): BODY}, a_i, b_i, …)`

`for F(a from a_i, b from b_i, …): BODY end`

```
fun gcd(p, q):
for loop-2(a from p, b from q):
if b == 0:
done(a)
else:
next-2(b, num-modulo(a, b))
end
end
end
```

#### 25.3` `Is It Really a Loop?

This whole section should be considered an aside for people with more advanced computing knowledge.

If you know something about language implementation, you may know that
loops have the property that the iteration does not consume extra
space (beyond what the program already needs), and the repetition
takes place very quickly (a “jump instruction”). In principle, our
`loop-2`

function does not have this property: every iteration is
a function call, which is more expensive and builds additional stack
context. However, one or both of these does not actually occur in
practice.

In terms of space, the recursive call to `loop-2`

is the
last thing that a call to `loop-2`

does. Furthermore,
nothing in `loop-2`

consumes and manipulates the return from that
recursive call. This is therefore called a tail call.
Pyret—

#### 25.4` `Re-Examining `for`

The definition of `for`

given above should make you suspicious:
Where’s the loop?!? In fact, Pyret’s `for`

does not do any
looping at all: it’s simply a fancy way of writing `lam`

. Any
“looping” behavior is in the function written after `for`

. To
see that, let’s use for with a non-looping function.

`for F(a from a_i, b from b_i, …): BODY end`

`F({(a, b, …): BODY}, a_i, b_i, …)`

```
delta-x = 0.0001
fun d-dx-at(f, x):
(f(x + delta-x) - f(x)) / delta-x
end
```

`d-dx-at({(n): n * n}, 10)`

`for d-dx-at(n from 10): n * n end`

```
check:
for d-dx-at(n from 10): n * n end
is
d-dx-at({(n): n * n}, 10)
end
```

`d-dx-at`

has no iterative behavior, no iteration
occurs. The looping behavior is given entirely by the function
specified after `for`

, such as `map`

, `filter`

, or
`loop-2`

above.#### 25.5` `Rewriting Pollard-Rho

`loop-2`

we had before: that’s only
a suitable loop when we have two arguments that change on each
iteration (often the iteration variable and an accumulator). It would
be easy to design a 3-argument version of loop, say `loop-3`

, but
we could also have a more general solution, using a tuple:
```
data LoopStatus:
| done(v)
| next–2(new-x, new-y)
| next-n(new-t)
end
fun loop-n(f, t):
r = f(t)
cases (LoopStatus) r:
| done(v) => v
| next-n(new-t) => loop-n(f, new-t)
end
end
```

`t`

is a tuple.`pr`

. Let’s first rename the old `pr`

function as `pr-old`

so we can keep it around for testing. Now we
can define a “loop”-based `pr`

:
```
fun pr(n):
fun g(x): num-modulo((x * x) + 1, n) end
for loop-n({x; y; d} from {2; 2; 1}):
new-x = g(x)
new-y = g(g(y))
new-d = gcd(num-abs(new-x - new-y), n)
ask:
| new-d == 1 then:
next-n({new-x; new-y; new-d})
| new-d == n then:
done(none)
| otherwise:
done(some(new-d))
end
end
end
```

```
check:
ns = range(2, 100)
l1 = map(pr-old, ns)
l2 = map(pr, ns)
l1 is l2
end
```

#### 25.6` `Nested Loops

`lol = [list: [list: 1, 2], [list: 3], [list:], [list: 4, 5, 6]]`

```
for loop-2(ll from lol, sum from 0):
cases (List) ll:
| empty => done(sum)
| link(l, rl) =>
l-sum =
for loop-2(es from l, sub-sum from 0):
cases (List) es:
| empty => done(sub-sum)
| link(e, r) => next-2(r, e + sub-sum)
end
end
next-2(rl, sum + l-sum)
end
end
```

```
fun sum-a-lon(lon :: List<Number>):
for loop-2(es from lon, sum from 0):
cases (List) es:
| empty => done(sum)
| link(e, r) =>
next-2(r, e + sum)
end
end
end
fun sum-a-lolon(lolon :: List<List<Number>>):
for loop-2(l from lolon, sum from 0):
cases (List) l:
| empty => done(sum)
| link(lon, r) =>
next-2(r, sum-a-lon(lon) + sum)
end
end
end
check:
sum-a-lolon(lol) is 21
end
```

```
fun sum-a-list(f, L):
for loop-2(e from L, sum from 0):
cases (List) e:
| empty => done(sum)
| link(elt, r) =>
next-2(r, f(elt) + sum)
end
end
end
```

```
fun sum-a-lon(lon :: List<Number>):
sum-a-list({(e): e}, lon)
end
fun sum-a-lolon(lolon :: List<List<Number>>):
sum-a-list(sum-a-lon, lolon)
end
check:
sum-a-lolon(lol) is 21
end
```

`sum-a-lon`

, each element is a number, so it “contributes
itself” to the overall sum. In `sum-a-lolon`

, each element is a
list of numbers, so it “contributes its `sum-a-lon`

” to the
overall sum.```
fun sum-a-lon(lon :: List<Number>):
for sum-a-list(e :: Number from lon): e end
end
fun sum-a-lolon(lolon :: List<List<Number>>):
for sum-a-list(l :: List<Number> from lolon): sum-a-lon(l) end
end
```

Arguably this makes even clearer what each element contributes. In
`sum-a-lon`

each element is a number, so it contributes just that
number. In `sum-a-lolon`

, each element is a list of numbers, so
it must contribute `sum-a-lon`

of that list.

#### 25.7` `Loops, Values, and Customization

- Every loop produces a value. This is consistent with the rest of the language, where—
as much as possible— computations try to produce answers. We don’t have to produce a value; for instance, the following program, reminiscent of looping programs in many other languages, will work just fine in Pyret: `for each(i from range(0, 10)): print(i) end`

However, this is the unusual case. In general, we want expressions to produce values so that we can compose them together. Many languages have strong opinions on exactly how many looping constructs there should be: two? three? four? In Pyret, there are no built-in looping constructs at all; there’s just a syntax (

`for`

) that serves as a proxy for creating a specific`lam`

. With it, we can reuse existing iterative functions (like`map`

and`filter`

), but also define new ones. Some can be very generic, like`loop-2`

or`loop-n`

, but others can be very specific, like`sum-a-list`

. The language designers don’t prevent you from writing a loop that is useful to your situation, and sometimes the loop can be very expressive, as we see from rewriting`sum-a-lon`

and`sum-a-lolon`

atop`for`

and`sum-a-list`

.