6.2.1. Infinite Sequences¶

Implementing call-by-name

Macro-expansion may be implemented with a double textual substitution (as in the C++ pre-processor) or with a single substitution and dynamic scoping. The result is the evaluation of the entire function body in the caller’s environment. But how to implement call-by-name? How to evaluate the arguments in the caller’s environment but the rest of the body in the callee’s environment?

Instead of simply passing a textual representation of the argument, we pass in a parameterless anonymous function that returns the argument. Such an anonymous function is called a thunk.

Understanding the difference between passing an argument that is evaluated before calling the function and passing a thunk is to understand the difference between

and

The former, when passed as an argument, is already evaluated. The function can use that value without having to do anything else to it. However, the latter, when passed as an argument, requires that the thunk be invoked to “unwrap” the value that the function should be using in its computation.

Instead of evaluating the argument before calling the function and using that value in the function, every time a parameter is referenced in the function body, the thunk is evaluated to obtain the argument’s value. The evaluation process is often referred to as thawing the thunk.

If the thunk contains a reference to a free variable, such as the x in the following example:

then the callee (that is passed the thunk as an argument) will be able to access the free variable that was defined in the caller’s environment. This is because the thunk is a function, in other words a closure that includes the environment that existed at the time the thunk was created (i.e., the caller’s environment that contains the definition of x).

Call-by-name lists

To illustrate the use of thunks, we will implement call-by-name lists, which are similar to the way lists are used by default in Haskell or as a programmer-chosen option in Python and Scala. Call-by-name lists essentially give you lazy lists, and we will see that they can also be thought of as “infinite sequences”. This perspective offers a very different approach to the way in which one works with such lists.

Below is documentation for some of the functions that we will provide in a JavaScript module for infinite sequences called the is module.

The constructor for sequences (i.e., the cons function) takes two arguments, namely the element we want at the head of the sequence and a thunk that will return the tail of the sequence if we ever need to go beyond the first element. For simplicity, we will only manipulate infinite sequences of integers.

// Construct a new sequence comprised of the given integer and thunk
var cons = function (n,thunk) { ... };

// Get the first integer in the  sequence
var hd = function (seq) { ... };

// Get the infinite sequence following the first element.  This
// will itself be in the form of an integer followed by a thunk
var tl = function (seq) { ... };

// Return the (finite, non-lazy) list containing the first n
// integers in the given sequence
var take = function (seq,n) { ... };

The following slide show illustrates how we could use these operations to construct and then expose various parts of an infinite sequence of 1s.

1 / 4 Settings

<<<>>>

With documentation for the operation highlighted in blue (lines 1 and 2) and actual code highlighted in red (lines 3-6), the is.cons operation is used to construct an infinite sequence of ones. Note that the thunk that comprises the second argument to the is.cons operation buries a recursive reference to ones inside a parameterless function. This technique will often be used in constructing infinite sequences.

1. // Construct a new sequence comprised of the given integer and thunk
2. var cons = function (n,thunk) { ... } // code in the is module
3. // Example of constructing a sequence using the is module, in this
4. // example, the sequence consisting of all 1s
5. var ones = is.cons(1,
6. function () { return ones; } );
7. // Get the first integer in the sequence
8. var hd = function (seq) { ... } // code in the is module
9. // Example of using the is.hs operation
10. is.hd(ones);
11. // Get the the infinite sequence following the first element. This
12. // will itself be in the form of an integer followed by a thunk
13. var tl = function (seq) { ... } // code in the is module
14. // Example of using the is.tl operation
15. var more_ones = is.tl(ones);
16. // Return the (finite, non-lazy) list containing the first n
17. // integers in the given sequence
18. var take = function (seq,n) { ... } // code in the is module
19. // Example of using the is.take operation
20. is.take(ones,5);

1. 1
2. Thunk to expose 1s that follow

ones

1. 1

is.hd(ones)

1. 1
2. Another thunk to expose 1s

more_ones

1. 1
2. 1
3. 1
4. 1
5. 1

is.take(ones,5)

Saving...
Server Error
Resubmit

Let’s now turn our attention to how these four basic functions in the is module, i.e., cons, hd, tl, and take, are implemented. The underlying representation of a lazy list is a two-element array seq. seq[0] stores the head of the list, which is already evaluated, and seq[1] stores the thunk that must be evaluated to expose the remainder of the list.

// Construct a new sequence comprised of the given integer and thunk
var cons = function (x, thunk) {
  return [x, thunk];
};

// Get the first integer in the  sequence
var hd = function (seq) {
  return seq[0];
};

// Get the infinite sequence following the first element.  This
// will itself be in the form of an integer followed by a thunk
var tl = function (seq) {
  return thaw(seq[1]);
};

// thaw is a helper function for tl. It returns the result
// of evaluating the function given as argument
var thaw = function (thunk) { return thunk(); };

// Return the (finite, non-lazy) list containing the first n
// integers in the given sequence
var take = function (seq, n) {
  if (n === 0)
    return [];
  else {
    // Get a copy of the result of recursive call with n - 1
    var result = take(tl(seq), n - 1).slice(0); // slice(0) gives a copy of the array
    // And use Javascript's unshift to put the hd at the beginning of result
    result.unshift(hd(seq));
    return result;
  }
};

So far the only sequence that we have been able to create has been a boring sequence consisting of all ones. To make it easier to construct more interesting sequences, in addition to cons, hd, tl, and take, the is module has some utility functions that are “infinite analogues” to their counterparts in finite lists (our fp module). All of these utility functions (i.e., from, map, filter, iterates, and drop) are discussed and illustrated below.

• The from operation:

1 / 8 Settings

<<<>>>

The is.from function returns a (lazy) list of integers starting at n. In a few slides we will consider how to fill in the question marks below. But first consider the usage of the is.from function to produce the sequence intsFrom1 below. Although you can think of this sequence as the infinite sequence 1, 2, 3, 4, ..., remember that it actually is implemented as the two-element array with 1 and a thunk that must be thawed to get to the rest of the integers that follow 1.

1. // return the sequence of successive integers starting at n
2. var from = function (n) {
3. return cons(n, function () { ?????? });
4. return cons(n, function () { return n + 1; });
5. return cons(n, function () { return from(n + 1); });
6. };
8. // Example of using from
9. var intsFrom1 = is.from(1);
10. var h = is.hd(intsFrom1);
11. var s1 = is.tl(intsFrom1);
12. var s2 = is.tl(is.tl(intsFrom1));
13. var s3 = is.take(s2, 6);

1. 1
2. Thunk to expose integers after 1

intsFrom1

1. 1

h

1. 2
2. Thunk to expose integers after 2

s1

1. 3
2. Thunk to expose integers after 3

s2

1. 3
2. 4
3. 5
4. 6
5. 7
6. 8

s3

Saving...
Server Error
Resubmit

• The map operation

1 / 5 Settings

<<<>>>

The is.map function applies an operation, in the form of a function, to an entire sequence returning a new sequence. In the example highlighted below, the function that doubles its argument is applied to the sequence of integers starting with 1. Taking the first five members of the returned sequence results in the sequence s1.

• // Analogue to what the map operation did for finite lists in the fp
• // module, that is, return a new sequence obtained by applying the
• // given function f to each member of the given sequence seq
• var map = function (f,seq) {
• return cons(<??? 1st arg to cons ???>,
• return cons(f(hd(seq)),
• <??? 2nd arg to cons ???> );
• function () {
• return map(f, tl(seq));
• }
• );
• };
• // Examples of using map
• var intsFrom1 = is.from(1);
• var s1 = is.take(is.map( function (n) { return 2 * n; },
• intsFrom1),
• 5);
• var s2 = is.take(is.map( function (n) { return n * n; },
• intsFrom1),
• 5);

1. 1
2. Thunk to expose integers after 1

intsFrom1

1. 2
2. 4
3. 6
4. 8
5. 10

s1

1. 1
2. 4
3. 9
4. 16
5. 25

s2

Saving...
Server Error
Resubmit

• The filter operation

1 / 5 Settings

<<<>>>

The is.filter function takes a predicate (i.e., a function that returns a Boolean), and a sequence. It returns the sequence of all items in the input sequence that satisfy the predicate. In the example highlighted below, JavaScript's mod operator is used with filter to create the sequence of all even integers, of which the first 5 are then taken.

• // Filters the given sequence with the given predicate
• var filter = function (pred,seq) {
• if (pred(hd(seq))) {
• return cons( ?????? );
• return cons(hd(seq),
• function () {
• return filter(pred, tl(seq));
• });
• } else {
• return ??????;
• return filter(pred, tl(seq));
• }
• };
• var intsFrom1 = is.from(1);
• var evens = is.take(
• is.filter(
• function (n) { return n % 2 == 0; },
• intsFrom1
• ),
• 10);

1. 1
2. Thunk to expose integers after 1

intsFrom1

1. 2
2. 4
3. 6
4. 8
5. 10

evens

Saving...
Server Error
Resubmit

• The drop operation:

1 / 5 Settings

<<<>>>

The is.drop function takes an infinite sequence and returns a new sequence with the first n elements removed. Note that what is returned is still an infinite sequence since we have only removed a finite number. This is illustrated by the call to is.drop below, which returns a sequence of the even integers starting with 12. is.drop returns an infinite sequence, which is always an integer followed by a thunk. Contrast that with is.take, which returns a finite list, as illustrated by first6.

• // Return a sequence formed by removing the first n items
• // from seq
• var drop = function (seq, n) {
• if (n === 0)
• return ????;
• return seq;
• else {
• return ????;
• return drop(tl(seq), n - 1);
• }
• };
• var intsFrom1 = is.from(1);
• var evens12 = is.drop(
• is.filter(
• function (n) { return n % 2 == 0; },
• intsFrom1
• ),
• 5);
• var first6 = is.take(evens12,6);

1. 1
2. Thunk to expose integers after 1

intsFrom1

1. 12
2. Thunk to expose integers after 12

evens12

1. 12
2. 14
3. 16
4. 18
5. 20
6. 22

first6

Saving...
Server Error
Resubmit

• The iterates operation:

1 / 5 Settings

<<<>>>

The is.iterates function takes two parameters f and n. It returns a new sequence starting with n and having its subsequent elements computed by repeatedly applying f to the previous term of the sequence. That is, it returns the sequence n, f(n), f(f(n)), f(f(f(n))), etc. The example highlighted below shows how we could use the is.iterates operation to compute the sequence comprised of the powers of 2.

• // Return a new sequence obtained by repeatedly applying the given
• // function to the previous term of the sequence (starting with the
• // given integer n). That is, return the sequence n, f(n), f(f(n)),
• // f(f(f(n))), ...
• var iterates = function (f, n) {
• return cons(
• ??????
• n,
• ??????
• function () { return iterates(f, f(n)); }
• );
• };
• is.take(is.iterates(function (x) { return 2 * x; }, 1), 6);
• is.take(is.iterates(function (x) { return ?????? ; }, ??????), 6);
• is.take(is.iterates(function (x) { return 3 + x; }, 3), 6);

1. 1
2. 2
3. 4
4. 8
5. 16
6. 32

First 6 elements using iterates

with the 2 * x function

1. 3
2. 6
3. 9
4. 12
5. 15
6. 18

First 6 members of the

multiples-of-3 sequence

Saving...
Server Error
Resubmit

The Sieve of Erastosthenes: an example that takes advantage of lazy lists

The need to compute various prime numbers occurs in a variety of applications, for example, public-key encryption. A long known technique to compute all of the prime numbers up to a limit n with reasonable efficiency is the Sieve of Erastosthenes. The slide slow below describes the sieve algorithm in a language with eager (as opposed to lazy) evaluation.

1 / 13 Settings

<<<>>>

Suppose n = 30. Trace through the pseudocode below.

1. Create a boolean array indexed from 0 to n
2. Set indices 0 and 1 to false. All others to true
3. Initially, let p equal 2, the smallest prime number
4. "Sift" multiples of p, starting at 2*p, by setting them to false
5. Find the first index > p and <= square-root(n) that is true
6. If there is no such index, stop
7. Otherwise, let p = this index and repeat from step 4
8. Upon termination, the indexes that remain true are all the primes <= n

1. 0
2. 1
3. 2
4. 3
5. 4
6. 5
7. 6
8. 7
9. 8
10. 9
11. 10
12. 11
13. 12
14. 13
15. 14
16. 15
17. 16
18. 17
19. 18
20. 19
21. 20
22. 21
23. 22
24. 23
25. 24
26. 25
27. 26
28. 27
29. 28
30. 29
31. 30

p = 2

Saving...
Server Error
Resubmit

There is a problem with this algorithm, however, from the perspective of its utility. Think about how well it can respond to the requests regarding primes that we might want to ask of it. While it can handle a request like “Find all primes less than or equal to n”, it comes up short on requests like “Find the first 1000 prime numbers” or “Find the first prime number larger that 1 billion”. The reason for this is that the underlying eager evaluation of the algorithm is limited by the finite nature of the value n that it is given. On the other hand, with lazy evaluation of lists, we need not be bound by a finite n. Instead we can construct the infinite sequence of primes, relying on repeated applications of a thunk to take us to any point in the sequence that we need to reach. The following slide show demonstrates how the Sieve of Erastosthenes would be implemented using lazy lists.

1 / 4 Settings

<<<>>>

Our sieve function is given all the integers starting at 2.

• var sieve = function (seq) {
• var sift = function (p) { return p % is.hd(seq) !== 0; };
• return is.cons(is.hd(seq),
• function () {
• return ??????;
• return is.filter( sift, is.tl(seq));
• return is.filter( sift, sieve(is.tl(seq)));
• });
• };
• var primes = sieve(is.from(2));
• is.take(primes, 10);

1. 2
2. thunk to expose ints after 2

Initially sieve is given

1. 2
2. thunk to sift multiples of ...

Cons 2 onto the rest of the primes

1. 2
2. 3
3. 5
4. 7
5. 9
6. 11
7. 13
8. 15
9. 17
10. 19

Initial attempt produces ...

1. 2
2. 3
3. 5
4. 7
5. 11
6. 13
7. 17
8. 19
9. 23
10. 29

The correct version produces ...

Saving...
Server Error
Resubmit

Call-by-need

What’s the difference between our call-by-name implementation of infinite sequences and the way it is done in Haskell? In Haskell, the analogue of the is.tl and is.take functions are done with call-by-need instead of call-by-name. In call-by-need, the value returned by a thunk is stored (that is, cached) after it is thawed for the first time. This is much more efficient since it never results in a thunk being thawed more than once.

Now it’s your chance to get some practice with infinite sequences in the following problems.

The following problem will help you better understand code that creates call-by-name infinite sequences.

6.2.2. Practice With Infinite Sequences¶

The following problem will help you write recursive code to process infinite sequences. To earn credit for it, you must complete this randomized problem correctly three times in a row.

6.2.3. Practice With Infinite Sequences (2)¶

The following problem reviews recursive definitions of sequences. To earn credit for it, you must complete this randomized problem correctly three times in a row.

6.2.4. Practice With Infinite Sequences (3)¶

The following problem deals with one more example of a recursive definition of a sequence.