PyFl – new functional programming language from Bill Wadge

It was developed in a secret lab and released, after which it spread rapidly. COVID? (maybe …). But I’m talking about the new PyFL interpreter. It’s finally available for the general public at

pyflang.com

To make things simple, in the form of a zip file   –  I’ll put it  on GitHub if there’s enough interest.

Just read README.txt and follow the instructions. As it says you need Python 3, 3.10.1 being the latest  stable version. . It all should work straight out of the box.

A quick summary of PyFL

It”s all implemented on top of Basic PyFL, a  stripped down lazy functional language. Basic PyFL has the data  types and infix operators of POP-11, lambda expressions, and valof clauses (basically where clauses), and function application. Function application uses conventional mathematical notation, e.g. f(a,b) instead of (f a b) as in Haskell.

Basic PyFL was implemented from scratch using function closures and similar standard techniques. It is  dynamically typed –  no type declarations and no constraints on application (self application in particular              is  supported).

Once Basic PyFL was implemented I proceeded to add more and more extensions, some quite novel.

Conventional function definitions

Mathematicians don’t normally use lambda expressions to define functions. Instead of writing

sumsq = lambda (x,y) x*x+y*y;

they are more likely to write

sumsq(x,y) = x*x+y*y;

This notation is implemented by simple translation – definitions using conventional notation are replaced by the version using lambda. Naturally this involves a complete ‘tree walk’ of the entire program because conventional definitions may occur in values deeply nested in other expressions.

The next feature added is where clauses. These are stylistically more convenient but cause parsing problems and so are not a basic feature. They, too, are implemented by a simple translation. A where clause with subject (head) s and set body of definitions is rewritten as a valof with the same body except that the definition result=s is  added.

With where and lambda we can write a non recursive factorial  program:

fac(7)
 where
  fac = Y(A);
  A(f) = lambda (n) if n==0 then 1 else n*f(n-1) fi;
  Y(a) = g(g) where g(x) = a(x(x));
 end

Notice that no variable is defined directly or indirectly in terms of itself. This definition of the fixed point combinator Y  clearly depends on self-application, which  Haskell’s  type system won’t allow. I was pretty happy when the PyFL interpreter produced 5040, the  correct answer.

Another feature added was multiple returns, so that you can write e.g.

min, max = bounds(x)

This is implemented with a simple translation but I won’t go in to it.

The next feature added was VBOs – variable binding operators, like the existential quantifier ∃ or the sigma (summation) operator ∑. They work exactly like their math counterparts except the ranges are lists and they are expressed in ASCII  notation. Thus we can compute  the primes less than 100   a

res = [2 3 5 7] <>
those n in rg(2,100):
 forall p in [2 3 5 7] :
  n mod p != 0
 end
end
where  
 rg(l,u) = 
    if l>u then [] 
           else l :: rg(l+1,u)
    fi;
end;

These VBOs are disguised loops, even though PyFL is a  functional language. They are implemented by translating into expressions using map, filter, and reduce.

My next step was to jump right in and add genuine while loops. We can use a while clause to compute the primes less than 100 as follows

res =
while n <100
 n = 3 fby n+2;
 nprime = not exist p in primes: n mod p == 0 end;
 primes = [2] fby if nprime then n :: primes else primes fi;
 result = primes;
end

There are three loop variables, n, primes, and nprime. The first is a counter that enumerates the odd numbers starting at 3, the second is a (reverse) list of the primes we have found so far, and prime is true or false depending on whether or not the current value of n is a prime (not divisible by any prime we’ve found so far).

It looks like Lucid (as intended) but is not Lucid; fby is just a syntax word that separates the initial expression from the next value expression of the recurrence relation. It’s translated into a tail recursion with the loop variables becoming formal parameters of the tail recursively defined function.

Next I took a break from innovating and produced a REPL program – REPL stands for Read, Evaluate, Print, Loop. The REPL is invoked by the command repl and when run it prints a welcome message and a list of real commands. It declares the current input file, if any, then gives a prompt consisting of a % proceeded by the name of the current import, if any. For example you might see

exp%

which means the current input file is exp.

The various commands allow you to manipulate the current import, whose source is stored in the file buffer and whose name is in the file currentimport (don’t touch these files directly). For example, to see the source use the command b or better yet, f, which invokes the pretty printer to format it. If you want to edit the file in the buffer use v, which invokes vi.

The file in the buffer is a set of definitions, not a program, so it doesn’t make sense to ‘run’ it. Instead, you can evaluate a PyFL expression and the evaluator will take the definitions into account if need be. What I usually do, as in the program given above, is equate the variable res to the expression of interest and use the command

primes% e res

The evaluator evaluates the expression following the e and prints the result, followed by some statistics.You can enter any PyFL expression, it doesn’t have to use the definitions in the buffer.

There’s more but you can discover it for yourself. PyFL is well documented by README.txt file, the REPL, and my numerous blog posts (my blog can now be found at billwadge.com)

A few notes. If you pay attention to the statistics, it’s obvious that for some programs the evaluator is ridiculously inefficient – huge numbers of list operations. This will be fixed in a future release. Also, I overlooked some vital opportunities for caching. I discovered, to my disgust, that evaluating res*res takes twice as long as evaluating res or res**2. This will also be fixed.

I put a lot of work into catching and handling errors, but not enough. It’s still easy to crash the software (generate a traceback). This will get harder in future releases.

So please download the zip file and try it out. Write your own PyFL programs, and, if you’re feeling adventurous, modify the source of the interpreter for e.g. better error handling or new features. Let me know of any interesting results and I’ll discuss them in my blog and maybe incorporate them in a future release (with appropriate credit given).

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