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.

As I’ve already explained I’ve invented and implemented an experimental functional language – PyFL (Python based Functional Language) – to try out some ideas.

For example, PyFL has a full set of Variable Binding Operators (VBOs) that use a linear ASCII form to represent the constructs like sigma notation of conventional mathematics. For example the following adds up the first 20 squares

sumfor i in range(1,20) all i*i end

and the following tests if N is prime

forall d in range(2,sqrt(N)): N mod d != 0 end

In the previous post I described the PyFL approach to input, which is (arguably) purely functional, drastically simpler, and trivial to implement, as compared to Haskell’s cumbersome IO monad. (Btw I have nothing against monads or Haskell in general, I’m just not impressed by the Haskell IO monad).

This time I’ll talk about PyFL’s output scheme. It ticks two of the three boxes just mentioned – it’s simple and easily implemented. Here’s some output (yep, Pascal’s triangle). I’ll show the program at the end of this post.

As I already explained, I’ve invented and implemented a simple functional language (PYFL) with a few interesting twists. Including a promising but simple approach to input.

The basic language itself is pretty standard, except that it uses infix operators and conventional mathematical notation for function calling; e.g. f(h,a+2*y). It also has a wide range of variable binding operators; as in the program given at the end of this post

VBOs are great but the real elephant in the FP room is I/O. I have a few ideas.

Monads schmonads

Haskell uses the seriously complex machinery of monads to do I/O, supposedly without side effects (I don’t accept this). And you end up writing stuff like

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

which to me looks like C. There must be a more functional approach.

I started from the PyLucid approach, that the output of a program is its value (as an expression) and its input is the value of a special variable input. Simple enough.

The problem with adopting this is that pyLucid has streams and PYFL doesn’t. Infinite lists could serve as a substitute but PyFL has only finite lists (to avoid the complications of list closures)

But there is no harm in having an input variable and this gives us a simple arrangement: the input becomes the value of input, and the corresponding value of the program is the corresponding output. Thus the expression

input*input

is a program to compute the square of its input (note that both occurrences of input denote the same value – no side effects, this program is equivalent to input**2).

What if we do want two inputs, and output their product? If one input variable is kosher, we can have two, input and input2. Our program is input*input2.

Generalizing, we could have inputn for every number n. Even better, a function input(n) of one number argument. When the computation (which is demand driven) needs the value of, say, input(3), it could prompt for it. In this simplest form the scheme is impractical because in general there is no guarantee that these inputs will be demanded in numerical order; the computation may need input(4) before input(3).

The solution (following Lucid) is to demand the inputs in order and cache them, so they will be available when the computation needs them.

Input prompting

PyFL goes one better. It has an input function whose argument can be an arbitrary string (not necessarily a numeral). This string is used as a prompt. Thus a program to compute the roots of a quadratic equation could be (and in PyFL is)

valof a = input(‘coefficient of x squared’); b = input(‘coefficient of x’); c = input(‘constant coefficient’) rdisc = sqrt(b*b-4*a*c); root1 = (-b + rdisc)/(2*a); root2 = (-b – rdisc)/(2*a); result = [% root1, root2 %]; end

As it happens the computation will need the value of b before that of a. If this is a problem, we can write the definition of root1 as

root1 = (1/(2*a))*(-b + rdisc);

(later I’ll explain a more systematic approach). Then the demand for root generates a demand for root1 which generates a demand for 1/(2*a) and finally a demand for a. Demands for b and c follow shortly, in that order.

Input values are cached in a dictionary using the prompt itself as a key. Thus the implementation won’t ask you again for the coefficient of x squared.

This works well if there is a small finite set of inputs but what if, say, we wanted to sum the values of twenty inputs?

The answer is to generate prompts and embed the a call to the input function in a VBO that runs over the required range. For example

sumfor i in range(1,20) all input(‘a number please(‘+str(i)+’)’) end

where str converts numbers to strings.

What if the input is being produced by another program? Why would we print the prompts? Because the program can read them digitally, and produce output as required. In other words the producer program is feeding our consumer program by producing its output on demand. It receives a prompt and computes or looks up the corresponding output.

We can save a lot of trouble if the producer knows ahead of time the order in which the input items will be required. Then we can eliminate the prompting dialogue.

The input scheme is not only conceptually simple (none of those pesky monads) but is trivial to implement – about a dozen lines of Python.

Now for output. The idea is … wait, take a look at the word count … this is already too long, the output story will have to wait till next time. Prompt me.

Here’s the promised program

valof subsets(s,i) = // the set of all i-element subsets of set s if i==0 then {{}} i==1 then collectfor x in s all {% x %} end else unionfor x in s all valof sminusx = s – {% x %}; // {% x %} is singleton x withoutx = subsets(sminusx,i); // subsets without x withx = collectfor u in subsets(sminusx,i-1) all //those with x {% x %} ++ u end; result = withx ++ withoutx; // disjoint union end end fi; result = subsets({tom dick harry chris pat},3); end

which computes all the three element subsets of the set {tom,dick,harry,chris,pat} (PyFL has proper sets).

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

[This reports on research carried out in collaboration with my PhD student Monem Shennat and former student Omar Alaqeeli]

Dimensionality is a big issue with multidimensional Lucid – it means figuring out which dimensions are relevant to calculating the values of a variable.

It’s a simple idea but surprisingly subtle. In this post I’ll deal with the simplest case, time sensistivity in ‘classical’ time-only Lucid. Calculating which variables need to know the value of the time parameter t.

The most pervasive fallacy of philosophic thinking goes back to neglect of context.

Jon Dewey

What exactly is “intensional programming?” The easy answer is, programming in a language based on intensional logic. But that raises another, more important question, namely what is intensional logic? Logicians have been working on the answer for more than 2500 years.

The short answer is, logic in which the truth-value and more generally the meaning of an expression depends on an implicit context. Let me attempt to give you the full answer.

[This is the infamous section of the book Lucid the Dataflow Programming Language where I make fun of everyone working on imperative languages. It was very popular but many people hated it even though no individual is named. In a companion post I cite it as an example of a Career Limiting Move. It didn’t quite kill my career though it didn’t help. I’m sure there were a number of meetings I wasn’t invited to and program committees I was left out of because of it. Hmmm … was that really a bad thing?]

A lot of people have to write as part of their jobs – grant proposals, progress reports, specifications. And there are endless verbal communications – defending code, disputes over features, justifying organization changes, technology explanations, and so on forever.

I’m fortunate enough to have a mathematical concept named after me. And not just Wadge degrees. There’s also the Wadge hierarchy, Wadge reducibility, and the Wadge game. In fact I’ve seen people say they’re interested in “Wadge theory”. A whole theory!

I’ve posted about this before but that was mainly technical and for most readers not all that accessible. It left out the human element, the passion, the drama, the thrill of victory etc. So here’s the real story.

I’ve already written about the origins of Lucid but that was a dry, technical, and incomplete post. Here is the real story, with all the drama and passion, the thrill of victory, the agony of defeat.