Functional ‘while’ loops – no, really

As I’ve explained I invented and implemented a small functional language (PYFL) to test out some ideas. In particular one idea is the (oxymoronic) functional while loop.

A while loop? In a functional language? “Impossible!” you snort.

Well you’re wrong. Let me explain.

Anyone who has tried programming the Fibonacci function has got a big surprise. In PYFL, for example, you can naively write

fib(n) = if n<2 then 1 else fib(n-1)+fib(n-2) fi;

On my Intel Macbook Air evaluating fib(20) eventually produces 10946 but fib(30) hangs up. A little thought explains why:  each call to fib generates two calls to fib … an exponential explosion, because the calls are independent, don’t share results unless you augment the simple program with some memoization scheme.

However in PYFL you have an alternative, namely a while loop:

fib(n) =
while i < n
 i = 1 fby i+1;
 f = 1 fby f+pf;
 pf = 1 fby f;
 result = f;
end;

Now when I evaluate fib(20) I get 10946 immediately and fib(30) produces 1346269, also immediately. Given fib(1000), after a barely detectable pause, I get

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

The secret, of course, is that the while loop uses an iterative algorithm that carries forward both the current value (f) of fib(i) as well as the previous value (pf) of fib(i).

Isn’t this cheating? PYFL is supposed to be functional and use recursion not iteration … We’ll see.

Another example, summing up 22 terms of the series for e**x:

e(x) = 
while i<22
 i = 1 fby i+1;
 term = 1 fby term*x/i;
 sum = 0 fby term+sum;
 result = sum;
end;

evaluating e(1) yields 2.7182818284590455, exact. Of course you can do this recursively but avoiding the calculation of x**i and i! at each stage requires auxiliary functions with extra arguments.

As for the charges of cheating – not guilty. PYFL while loops use plain old respectable tail recursion.

Suppose we want a function that removes duplicates in its list argument while preserving order. We soon realize we need an auxiliary function with an extra parameter that accumulates one copy of everything we’ve seen so far:

nodups(l) = g([],l);
g(m,k) = if k == [] then m else if hd(k) isin m
                                  then g(m,tl(k))
                                  else g(m<>[%hd(k)%],tl(k))
                                fi
         fi;

Now consider how the recursion unfolds when l is [1 3 5 3]. We have

nodups([1 3 5 3]) => g([],[1 3 5 3]) => g([1],[3 5 3]) => g([1 3],[5 3]) =>
                     g([1 3 5],[3])  => g([1 3 5],[])  => [1 3 5]

And now notice that the variables m and k take on sequences of values; for example, m takes on the sequence

[], [1], [1 3], [1 3 5], [1 3 5]

And what are the rules that generate the sequences? For m the rules are that m is initially [], and thereafter is m again if the head of k is in m, otherwise m<>[%hd(k)%] (the result of appending the head of l on the end of k).

The rules for k are simpler: k is initially l, and thereafter tl(k), until k is empty.

This tail recursion corresponds closely to the (conventional imperative) while loop:

m := []
k := l
while k != []
  m := if hd(k) isin m then m else m<>[%hd(k)%] fi
  k := tl(k)
end
return m

Thus tail recursion and recurrence rules are basically different specifications of the same computation. The idea of PYFL’s paradoxical while loops is to let the programmer specify the recurrence rules for the iterative version of the computation then have the PYFL interpreter translate them into (functionally respectable) tail recursions.

Here is nodups as a PYFL while clause

nodups(l) =
while k != []
 k = l fby tl(l);
 m = [] fby if hd(k) isin m then m else m<>[%hd(k)%] fi;
 result = m;
end;

The PYFL while is similar to the imperative one given above except that the statements are recurrence rules, not commands. They are unordered. The word fby is borrowed from Lucid but is just a syntax word, not an operator. It all gets translated into something very close to the tail recursion given above.

Ordinary tail recursions have a particularly simple formulation as while loops. Here is the definition of a function which sums the squares of the elements its list argument

sumsq(l) =
while m != []
 m = l fby tl(m);
 sum = 0 fby sum + hd(m)**2;
 result = sum;
end;

The function sumsq can be defined using map-reduce:

sumsq(l) = reduce(map(lambda (h) h**2 end,l),add,0);
reduce(m,A,b) = if m == [] then b else A(hd(l),reduce(tl(m),A,b) fi;

which is nowhere near as clear.

Slightly more generally, the while loop

while p
 a = fa fby na;
 b = fb fby nb;
 c = fc fby nc;
 result = r;
end

gets translated to

valof
 result = f(fa,fb,fc);
 f(a,b,c) = if p then r else f(na,nb,nc) fi;
end

The rules in the body don’t have to be recurrences; you can define a variable directly as a given expression. For example we could rewrite our PYFL while as

while k != []
 k = l fby tl(k);
 h = hd(k);
 m = [] fby if h isin m then m else m<>[%h%] fi;
 result = m;
end

We need a slightly more sophisticated translation which I won’t go into.

Input and output calls may appear in a while loop, with the expected results.

Here is a simple loop for factoring numbers, which prints the partial results as the factoring proceeds

factors(n) =
 while p*p <=
             outputf('{:>20s}{:10d}{:>6} \n',str(f),m,p)
           && m
  p = 2 fby if divides then p else p+1 fi;
  m = n fby if divides then m  div p else m fi;
  f = [] fby if divides then p :: f else f fi;
  divides = m mod p == 0;
  result = outputf('{:>20s}{:10d} \n',str(m :: f),1) && "";
 end
;

n = input('Number to be factored: ');
r = factors(n);

It works by enumerating possible divisors starting at 2, accumulating  divisors found in the  list f. If, for example, when it asks for an input number, you give it 1968, you get

                  []      1968     2 
                 [2]       984     2 
               [2 2]       492     2 
             [2 2 2]       246     2 
           [2 2 2 2]       123     2 
           [2 2 2 2]       123     3 
         [3 2 2 2 2]        41     3 
         [3 2 2 2 2]        41     4 
         [3 2 2 2 2]        41     5 
         [3 2 2 2 2]        41     6 
         [3 2 2 2 2]        41     7 
      [41 3 2 2 2 2]         1 

There is another while-like construct, called until. It runs until a condition is true, in itself a trivial difference. But until has two conditions and two result expressions, the result returned depending on which condition is true first.

Here is an until clause used to calculate cube (for a change) roots using Newton’s method, exiting if it doesn’t converge in 8 steps.

root(N) =
until A == pA, steps>8
 steps = 1 fby steps+1;
 A = 1 fby (2*A+N/A**2)/3;
 pA = 0 fby A;
 result = A, "noroot";
end;

For example root(27) evaluates to 3.0 but root(100) produces noroot.

So why am I telling you all this? In the hope that you will switch from Haskell to PYFL?

Sorry, but I’m not delusional. PYFL is an experimental toy language but is far from practical for serious projects. I’ll make it available and some of you may find it interesting to write little programs with while loops, VBOs, interactive IO etc. Or experiment with your own ideas.

The real point is that serious functional languages, like Haskell, could benefit from these features – they are trivial to implement. The whole implementation of PYFL is less than 5000 lines of Python. For example, Haskell could have while loops using the source translation given above. The entire translation process, including parsing, required less than 100 lines of code.

Haskell is great but it shouldn’t be the last word in functional programming. There is no last word in functional programming, and the PYFL experiment makes that clear.

Like this:

Like Loading...

Related

from Hacker News https://ift.tt/3jc8PXI