Haskell has been both a blessing and a curse for Functional Programming (FP.)

A blessing because it has allowed many thousands to experience FP firsthand – by writing functional programs. They’ve discovered that it’s not that hard, that you can do useful projects in FP, and (thanks to the cleverness stuffed into Glasgow Haskell) the performance is comparable if not superior to that of conventional languages like Java,

So what is the curse? The curse is that Haskell dominates FP like Tyrannosaurus Rex dominated the dinosaurs (and like LISP used to dominate FP). Any discussion of FP becomes a discussion of Haskell, any proposed feature becomes a proposal for extending Haskell, and any problems with Haskell seem inherent in FP. The FP ecosystem seriously lacks diversity

I’m going to fix that with PyFL (PYthon based Functional Language), designed and implemented from scratch, as you watch

Take currying. In school we learned that addition, denoted by “+”, was a friendly little operator that takes two numeric values and returns their sum. Studying Haskell, we learn that it is actually a complex object that takes a number and returns a function that takes another number and returns the result of adding the first number to it.

Higher order functions that return other functions? Pretty complex stuff just to understand why 2+2 = 4.

Then there’s the monads. I’m more in favor of monads since I discovered that Lucid can be explained in terms of a simple stream monad. But I’m baffled by the IO monad. What causes the side effects? And are we really required to write imperative-looking code to read and write? Here is “Hello World” in Haskell according to online sources:

main :: IO ()
main = putStrLn "Hello, World!"

Yes, “putStrLn’, which, is clearly a command. The same source also offers

main = do {
   putStrLn "Hello, World!" ;
   return ()
   }

which to me looks like C. Apparently the “do” is shorthand for invoking monads … who knows.

Enough is enough

I don’t believe functional programming should look like C and I’m going to put my money where my mouth is. I’m going to increase the diversity of the FP ecosystem by inventing a new FP language – starting now. As the title says, I aim to put the fun into – and take the C out of – functional programming. Perhaps I can overcome some of Haskell’s limitations and draw backs.

The new language is called PyFL : Python based Functional Language. It’s based on Python in the sense that Python is the implementation language.

Succeeding posts will take you through the development. You can think of it as live blogging except that I’ve already done much of the work.

I’m cutting only two corners. First, PyFL is dynamically typed. A static type system is too much work. And they can be constraining and cumbersome, so I think I can do without one for the time being.

The other corner is performance. PyFL is relatively slow given two levels interpretation. It would take a whole team to match the amazing work done on the GHC. But modern computers are powerful and PYFL performance is good enough that the language is usable on small projects.

The basic principles

The first principle is that PyFL is math. Out is any feature (like putStrLn) that can’t be explained as math. (And not just through math because any precisely defined notion can be described using math).

The second principle is that as far as possible PyFL uses conventional mathematical notation. This means prefix and infix operators, parentheses, and operator precedence. But most importantly, conventional mathematical notation adapted to linear format using the ASCII alphabet.

Thus a function to compute the root of the sum of the squares of its arguments can be defined by the equation

sumsq(x,y) = sqrt(x**2+y**2)

The function sumsq is a simple, humble first order function of two arguments (it has arity 2), not a disguised second order unary function. It is invoked like in your calculus text, e.g.

sumsq(3,4)

Of course we can define higher order functions as required, using function formal parameters or (linear ascii) lambda notation. Thus

simpson(f,a,b) = (b-a)*(f(a)+4*f((a+b)/2)+f(b))/6

Here simpson(f,a,b) is the simple Simpson’s rule approximation to the integral of function f from a to b. Thus

simpson(lambda (x) 1/x end,1,2)

gives an approximation to log 2.

Valof clauses

The only remaing feature of basic PyFL is a construct for auxiliary definitions. Haskell adopted Landin’s where clause, so that the definition of simpson could be written

simpson(f,a,b) = l*avgf
where l = b-a; m = (a+b)/2; avgf = (f(a)+4*f(m)+f(b)/6; end;

However where clauses cause problems with top-down parsing so instead we adapt BCPL’s valof construct, and write

simpson(f,a,b) =
   valof
      result = l*avgf;
      l = b-a;
      m = (a+b)/2;
      avgf = (f(a)+4*f(m)+f(b)/6;
   end

The valof clause is equivalent to the where clause except for the definition of the special variable result, which is equated to the expression at the head of the corresponding where clause.

The equations in the body of a valof are unordered. There must be a definition of result, and every variable defined must have a unique definition. Definitions inside the body override definitions of the same variable outside the body. This is all standard. Thus

valof factorial(n) = if n<1 then 1 else n*factorial(n-1) fi; result = factorial(5); end

has value 120.

VBOs

PYFL fully implements Variable Binding Operators (VBOs), as described in a previous post. For example you can compute the set of all subsets of s as

unionfor x in s all
 valof
   r = s – {% x %};
   sr = subsets(r);
   wix = collectfor u in sr all // subsets with x
               {% x %} ++ u
            end ;
   wox = sr; // subsets without
   result = {%s%} + wix ++ wox + {{}};
 end
end

A current list of VBOs is: sumfor, prodfor, consfor, appendfor, concatfor, unionfor, intersectfor, collectfor, those, exist, forall.

Notice PyFL has sets, implemented properly, with higher order primitives instead of a random member operator.

The fixed point operator

One intriguing property of basic PYFL (which is really just applied lambda calculus) is that in principal recursion is not necessary. The following valof also has value 120

valof
   alpha(f) = lambda (n) if n<1 then 1 else n*f(n-1) fi end;
   Y(gamma) =
       valof
          result = h(h);
          h(k) = gamma(k(k));
        end;
   factorial = Y(alpha);
   result = factorial(5)
end

Examine the code carefully; you can verify that no variable is defined directly or indirectly in terms of itself.

Notice the simple (untypable) definition of the fixed point operator Y; there are advantages to skipping static type checking.

To see how Y works, look at the definition of h:

h(k) = gamma(k(k))

Now substitute h for k, giving

h(h) = gamma(h(h))

In other words, h(h) is a fixed point of gamma!

The PyFL interpreter handles this correctly; the valof above evaluates to 120. In fact all these examples have been tested by my PyFL interpreter.

There’s a lot more to PyFL but that’s for next time.