[This is another excerpt from the paper we were going to submit to ICFP 2025. Unfortunately it was immediately rejected because we included our names, contrary to the instructions that it is anonymous. Sigh]

PyFL is a pure and lazy functional language and yet has a limited, declarative form of iteration – a while loop construct (sounds impossible, but true). The while clause not only makes the coding easier, the iterative versions are often much more efficient.

PyFL was implemented using the usual techniques (e.g. closures) and then we added a while clause with very little effort. A while clause consists of the word while followed by a condition, then a body of definitions terminated by end. The definitions can be interpreted iteratively, with the iterations terminating when the condition at the head of the clause first fails.

Here is a PyFL clause to compute the tenth Fibonacci number.

           while count<10
              count = 1 fby count+1;
              fib = 1 fby fib+prefib;
              prefib = 0 fby fib;
              result = fib;
            end

The equation

          count = 1 fby count+1;

is actually two declarations; the first says that the initial value of count is 1, and that thereafter the next value is the current value plus 1. Similarly, the next statement specifies that the initial value of the fib ‘variable’ is 1, and that thereafter the next value is the current value plus the current value of the variable prefib. Finally, the prefib statement declares that its initial value is 0 but the next value is the current value of fib. In other words prefib is initally 0 but thereafter the previous value of fib.

The last statement, the definition of result, specifies that on termination, the value returned for the clause is that of the current value of fib. By “termination” we mean the first time the condition at the head of the clause fails.

The equations in a while clause don’t have to be recurrences using fby. They can be direct, like xcubed = x*x*x;

Nor do they have to involve ground value objects only. The following is perfectly acceptable:

        g = lambda (x) x end fby 
                lambda (x) f(g(x)) end;

and defines g to be the sequence of ‘powers’ of f.

The recurrence equations look like Lucid statements, by intent. In Lucid fby is an infix operator that operates on infinite sequences (streams). In extended PyFL, however, fby is only a syntax word that separates the two expressions in a recurrence declaration. In extended PyFL you can’t write a = b fby c fby d as you can in Lucid.

It may seem inappropriate to think of variables in a pure functional language as having initial values and as being updated. We will argue that it’s semantically correct and can be used as a programming heuristic. Nevertheless the statements are declarations, not assignments; for example, the order in which they appear within the clause is immaterial. We must think of all the updates being performed simultaneously, not one after another.

Here is a program that computes the sum of the usual series for e, until the terms are small enough (or until a count of the terms exhausted).

          while term > 0.0000001 and count < 20
             count = 1 fby count+1;
             term = 1 fby term/count;
             termsum = 0 fby termsum+term;
             result = termsum;
           end

PyFL, including while clauses, has been implemented in about 8000 lines of Python (PyFL has a lot of other features). We ran the programs above and got 89 and 2.718282 as answers.

PyFL programs can be arbitrary value-denoting expressions, and while clauses can be used like any other expressions, e.g. they can be added and subtracted. In particular, they can be used in function definitions. Here is another program to compute the tenth Fibonacci number:

          fibonacci(10)
            where
               fibonacci(n) =
                  if n < 2 then 1 else
                   fibonacci(n-1)+fibonacci(n-2)
                  fi
             end;

The only problem is that the recursive program is very inefficient. We eventually get 89, but only after a long wait. Without some form of memoing, the computation explodes exponentially as each call is recomputed over and over.

Python where clauses have no special memoing in the evaluator. Instead it is enough that expression closures, once evaluated, are changed in place to their results. This procedure is standard in lazy interpreters and was in effect in the PyFL interpreter before while clauses were added to the language. The while clause advantage is not just notational, it has important computational implications.

The PyFL interpreter implements while clauses by translating them to tail recursion, but doesn’t employ any special techniques to handle tail recursion. The clause for the e series, for example, is transformed into something like (simplifying)

            whilefun(1,1,0)
              where
                whilefun(count,term,termsum) =
                  if term > 0.0000001 and count <20 
                     then 
                      whilefun(count+1, term/count,
                               term+termsum)
                     else termsum
                   fi;
                  end;

Evaluating this will cause repeated evaluations of whilefun with a sequence of values of the parameters that accord with the sequences generated by the heuristics. 

The code for the translation to tail recursion was only a couple of dozen lines of Python. Add similar amounts for parsing and formatting, and it’s still a trivial programming project. One could use these ideas on any functional language, pure or not. If the language already converts tail recursion to imperative code, so much the better. For example, it should be easy to extend Haskell with while clauses.