Programming with Streams

declare
PositiveIntgers = 1 | {AddStreams Ones PositiveIntegers}

This produces a stream of positive integers. To see how this works, we seek recurrences to produce such a stream. A recurrence which produces an infinite stream of positive integers is:

PositiveIntegers[1] = 1
PositiveIntegers[n] = 1 + PositiveIntegers[n-1], for n >= 2.

The AddStreams call ensures that the number in the nth position is the sum of the numbers in the (n-1)st positions in Ones and PositiveIntegers, which is a correct implementation of the recursion.

It is also clear that the lazy function AddStreams can compute the nth value, since the first n-1 terms of PositiveIntegers will be available by then. That is, just enough elements of PositiveIntegers are available to enable the computation of the next element of PositiveIntegers.

                     Time 1       Time 2            Time 3              Time 4
                     ------       ------            ------              ------
PositiveIntegers =   1 | _        1|_               1 | 2 | _           1 | 2 | 3 | _
                                    ^                       ^                       ^
                                    .                       .                       .
                                    .                       .                       .
PositiveIntegers =   1 | _          1 | _               1 | 2 | _           1 | 2 | 3 | _
                                    +                       +                       +
Ones             =                  1 | 1 | ...         1 | 1 | ...         1 | 1 | 1 | ...

declare
Fibs = 0 | 1 | {AddStreams Fibs Fibs.2}

This works as follows.

            Time 2             Time 3                     Time 4                         Time 3
            ------             ------                     ------                         ------
Fibs    =   0 | 1 | _          0 | 1 | 1 | _              0 | 1 | 1 | 2 | _              0 | 1 | 1 | 2 | 3 | _
                    ^                      ^                              ^                                  ^
                    .                      .                              .                                  .
                    .                      .                              .                                  .
                    .                      .                              .                                  .

Fibs    =           0 | 1 |_           0 | 1 | 1 | _              0 | 1 | 1 | 2 | _              0 | 1 | 1 | 2 | 3 | _
                    +                      +                              +                                  +
Fibs|2  =           1 | _              1 | 1 | _                  1 | 1 | 2 | _                  1 | 1 | 2 | 3 | _

Thus it implements the famous recurrence of the Fibonacci sequence

Fib[1] = 0
Fib[2] = 1
Fib[n] = Fib[n-1]+Fib[n-2], for n >= 3

Here the (n-2)nd term comes from the Fib argument, and the (n-1)st from the Fib.2 argument.

declare
PowersOfTwo = 1 | {ScaleStream 2 PowersOfTwo}

implementing the recurrence

PowersOfTwo[1] = 1
PowersOfTwo[n] = 2 * PowersOfTwo[n-1], for n >= 2.

Alternatively, it can be also written as

declare
PowersOfTwo = 1 | {AddStream PowersOfTwo PowersOfTwo}

implementing the recurrence

PowersOfTwo[1] = 1
PowersOfTwo[n] = PowersOfTwo[n-1] + PowersOfTwo[n-1], for n>=2.

declare Primes = 2 | {FilterStream IsPrime {IntsFrom 3}}

This does not seem to be an implicit definition. However, we will define IsPrime in a way that depends on the Primes list itself. We know that a number \(N\) is prime if and only if no number less than or equal to \(\sqrt{N}\) divides it. It is not difficult to see it is sufficient to check that if no prime below \(\sqrt{N}\) divides \(N\), then \(N\) is prime. We now write a function to realise this test.

declare
fun {IsPrime N}
    local Aux in
        fun {Aux Ps}
            if {Square Ps.1} > N
            then true
            else
                if {Divisible N Ps.1}
                then false
                else {Aux Ps.2}
            end
        end
        {Aux Primes} % implicit reference to Primes
     end
end

The test works because the primes less than or equal to \(\sqrt{N}\) will have been generated by the time we consider the primality of \(N\).

In the bisection method to find the square root of a non-negative real number \(x\), we start with an initial guess \(g\), and iteratively refine it until we find an acceptable approximation to \(\sqrt{x}\).

Either \(g \le \sqrt{x}\) in which case \(g \le \sqrt{x} \le x/g\), or \(g \ge \sqrt{x}\), in which case \(x/g \le \sqrt{x} \le g\). Thus, we can refine the guess \(g\) by taking the average of \(g\) and \(x/g\) as the next guess. In practical scenarios, this refinement is continued until \(g\) and \(x/g\) are fairly close to each other, at which point \(g\) is a fairly good approximation of \(\sqrt{x}\).

This is a nice example of an iterative procedure, where \(g\) is the variable whose value changes every iteration. We will now code this in the stream mode. The stream will be the sequence of guesses.

declare SqrtImprove SqrtEstimateStream
fun {SqrtImprove Guess X}
    (Guess + (X/Guess))/2
end

fun {SqrtEstimateStream X}
    local Guesses in 
        Guesses = 1.0 | {MapStream   fun {$ A} {SqrtImprove A X} end
                                     Guesses}
    end
end

{Browse {SqrtEstimateStream 2}}

In stream-based iteration, we have the entire history of the iterated variable with us. Can we put this to good use? Here's a nice example.

We know that \(\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} \dots\).

declare PiSummands PiStream EulerTransform MakeStreamOfStreams

fun lazy {PiSummands N}
  (1/N) | {MapStream  fun {$ A} A*~1 end    % negative, for the alternating series
                      {PiSummands N+1}}
end

%--------------------------
% implement the recurrence
%    {PartialSummands Xs}[1] = Xs[1]
%    {PartialSummands Xs}[n] = Xs[n] + {PartialSummands Xs}[n-1]
%-------------------------
fun lazy {PartialSummands Xs}
    local Summands in 
        Summands = Xs.1 | {AddStream Xs.2 Summands}
    end
end

PiStream = {ScaleStream {PartialSums {PiSummands 1}} 4}

In an alternating series, we can "accelerate" the series to produce another series that converges to the same sum, via a procedure called the Euler transform. It transforms the series with \(n^\text{th}\) term \(S_n\) into another series where the \(n^\text{th}\) term is $$S_{n+1} - \frac{(S_{n+1} - S_n)^2}{S_{n-1} - 2S_n + S_{n+1}}.$$ We can define a function to accelerate the series as follows.

fun {EulerTransform S}
    local S0 S1 S2 in
        S0 = {Nth S 0}         % S[n-1]
        S1 = {Nth S 1}         % S[n]
        S2 = {Nth S 2}         % S[n+1]

        S2 - {Square (S1-S0)}/(S0 - 2*S1 + S2) | {EulerTransform S.2}
    end
end

Thus, we take the initial stream of the summands of pi, and refine it to produce an accelerated stream of the summands of pi. We can now iterate this procedure to produce a stream of streams, where each stream is the Euler transform of the previous.

fun {MakeStreamOfStreams Xs}
    local StreamOfStreams in
        StreamOfStreams = Xs | {MapStream EulerTransform StreamOfStreams}
    end
end

---