Many PyFL users are disappointed to find that PyFL lists are finite. Like those of the original LISP, rather than (possibly) infinite, like those of Haskell.

This has been remedied. PyFL now has lists that are in a sense infinite in one direction – what Landin originally called streams.

The basic idea (which goes back to Friedman and Wise) is that the cons function (:: in PyFL) should not evaluate its arguments unless necessary – until hd or tl is applied, and then only to extract these values. Since evaluation is deferred indefinitely, it can be deferred forever.

However we don’t want to fiddle with hd, tl, and :: themselves, because in PyFL traditional finite lists are used to implement expressions. Instead we introduce three new analogous primitives which will be implemented lazily. After some thought I settled on first, Rest and Join.

The idea is that Join‘s second argument is not evaluated until necessary. The first argument of Join, on the other hand, is evaluated eagerly, unlike Haskell.

What this means is that the recursive definition

Ones = 1 Join Ones;

makes sense. If we add

result = first Ones;

and evaluate result, we get 1. I’m following the convention that streams have names that begin with upper case letters. (The analogous equations in ordinary PyFL,

result = hd Ones;
Ones = 1 :: Ones;

fail to terminate when result is evaluated.)

All this justifies taking the lazily defined Ones to be the infinite stream

⟨1, 1, 1, 1, 1, 1, 1, … ⟩

of 1’s (I’m using ⟨ and ⟩ for streams).

Similarly, the equations

result = first Rest Rest N123;
N123 = 1 Join 2 Join 3 Join N123;

define N123 to be the infinite stream ⟨1, 2, 3, 1, 2, 3, 1, 2, 3, …⟩ and yield 3 when result is evaluated.

Initial Segments

We can write result = N123 but we won’t get any output because you can’t print an infinite stream. However, we can see the start of it using the start function defined as follows

start(S,n) =  if n==0 then []
               else first S :: start(Rest S,n-1)
              fi;

Then start(S,n) is the list of the first n elements of S. So, for example, start(N123,5) is
[1 2 3 1 2].

Functions and Streams

If we use functions we can get more elaborate streams. The definitions

result = start(Nats,5);
Nums(i) = i Join Nums(i+1);
Nats = Nums(0);

define Nums(i) to be ⟨i, i+1, i+2 ,..⟩, Nats to be ⟨0, 1, 2, 3 …⟩ and result to be [0 1 2 3 4].

The following

Sum(L,M) = first L + first M Join Sum(Rest L, Rest M);

defines Sum to be pointwise addition operation on streams. Then

Odds = Sum(Ones,Sum(Nats,Nats));

defines Odds to be ⟨1, 3, 5, 7,…⟩.

The next step is to define a function which returns the running sum of its stream argument. So that if S is ⟨1, 6, 2, 4, …⟩, Rsum(s) is ⟨1, 7, 9, 13, …⟩. We need an auxiliary function with an extra numeric parameter :

Rsum(L) = Rsumd(L,0) 
           where 
            Rsumd(L,d) = d + first L Join Rsumd(Rest L, d + first L);
           end;

Then Rsum(odds) is ⟨1, 4, 9, 16, 25, …⟩, the stream of all squares, and start(Rsum(odds),5) is
[1 4 9 16 25].

How it Works

Everything up to this point has been implemented in the current PyFL. When I finally figured it I was amazed at how simple it turned out to be – less than a dozen lines of code. At least for the evaluator. Another dozen or so were required to extend the parser and the formatter.

Here is the code to evaluate first, Rest, and Join expressions:

def first(a,env):                  # a is the list of operands    
    s = Eval(a[0],env)             # evaluate the first operand yielding a
                                   # closure
    h,C,env1 = StreamClosureD(s)   # take apart the closure
    return h                       # return the finite part

def Rest(a,env):
    s = Eval(a[0],env)             # as above
    h,C,env1 = StreamClosureD(s)   # get the parts of the closure
    return Eval(C,env1)            # evaluate the expression and return value 

def Join(a,env):                       
    f = Eval(a[0],env)                # evaluate first (and finite) operand
    return StreamClosureC(f,a[1],env) # return a closure with second operand

To be honest, this code was partially guesswork. But it’s been extensively tested and seems to work. My main reservation is that there is no caching. However it’s not clear how, or if, to add it.

Streams and VBOs

One of PyFL’s strong points is its collection of ‘variable binding operators’ (vbos), patterned after the ∑/∏ and set builder notations of mathematics (not unlike set comprehension in Haskell).

For example, to sum the squares of the positive elements of a list anums we can say

sum a*a for a in anums: a>0 end

or to get the name of the manager in the list of employees

first e in employees: rank(e) == manager end

Although I haven’t implemented anything yet I’ve thought it out: can we use streams instead of lists in vbos? At first sight yes, because even though a stream N of numbers is infinite, it still makes sense to demand first n in N: prime(n) end, the first prime in N. Similarly, Those n in N: n>0 end is the possibly infinite stream of positive elements of N.

On the other hand if I is a stream of positive integers, sum i*i for i in I end doesn’t make sense. Nor does union f(s) for s in S end. Let’s look at these first.

Bounding Streams

What we need for operators like sum and union is a way to bound the stream to a finite list. We could use start except we often don’t know ahead of time how many elements we need. A function more useful than start is startp:

startp(S,p) = if p(first S) then []
               else first S :: startp(rest S,p)
              fi;

which returns the list of elements up to but not including the first for which p is true.

The usual example is testing if n is prime, where we can stop testing divisors once their square is greater than n. This gives us

divisors = startp(Nums(2),lambda (d) d*d > n end);
nisprime = forall d in divisors: n mod d != 0 end;

My great idea is to shorten this by adding the keyword till (meaning until) to the vbo syntax so we can write

nisprime = forall d in Nums(2) till d*d > n : n mod d != 0 end;

Or if you want to sum the squares of elements of N up to the first negative element

sum n*n for n in N till n < 0 end;

Unbounded Streams

On the other hand there are expressions using the stream comprehension primitive Those where it makes sense to accept and/or return streams. For example, if we have an integer stream N and want the stream of squares of all its positive elements, we could write

Those i*i in N: i>0 end

Similarly, if we have a stream S of sets and want the stream of all the sets in S intersected with
{tom, dick, harry} we can write

Those s^{tom dick harry} for s in S end

And if we want the first negative element of N:

first Those n in N: n<0 end

(This will fail to terminate if there are no negative elements of N.)

Stay Tuned

Are streams a good idea? Yes and no. As they exist now, in PyFL, no. Programming with them is too cumbersome. But streams themselves are a good idea, if the language is adapted to them. I’m talking about (Py)Lucid, in which, for example, A+B is the pointwise sum of A and B. No need to define a sum function.

More about PyLucid next.