2 Misconcepts About Functional Programming (relating to context and monad)

It's interesting that almost every old and new language that claims to have some functional support has to go through the trial of its purity, like Perl, Scala, Erlang, Ruby, JavaScript and Python. Candle is no exception. Candle's last release announcement to LtU triggered some interesting discussion about whether the functional features in Candle are pure. I finally have sometime to share more about my thoughts on this issue. I'd like to talk about 2 misconcepts about functional programming. The first misconcept is that dynamic scope variables are not functional. The second misconcept is that monads are functional. I know the following writing is going to kick up the dust, but it is better than we settle without thorough thinking.

Of course, to continue the discussion, we must first define the judging criteria(s) to tell whether a programming feature is functional or not. I think everyone would agree the single most important criteria is referential transparency. Other salient features, like function composition, lazy evaluation and anonymous functions, are more prominent in functional programming, but they are not exclusive to just functional programming; imperative programming can sometimes exhibit or exploit these features as well.

1st Misconcept: Dynamic Scoped Variables are not Functional

 

This question arise due to the discussion whether the put statement in Candle is functional or not. Yes, by strict definition, dynamic scoped variables are not referentially transparent. But I'd argue it is still functional. I'd like to introduce a new concept here, so as to extend the scope of functional programming, a concept called contextually functional.

In other words, features in a functional programming language can be divided into two categories: purely or strictly functional and contextually functional. Strictly functional features are those obey the referential transparency rule. And a contextually functional feature is a feature that follows these rules:

• Some API function or language construct is defined to allow user to retrieve information about the context at certain place in a program.
• Some corresponding API function or language construct is defined to allow user to push value unto the context, which can be retrieved later by the previous API function or language construct. The pushed value must be hold constant when it is in scope. When the pushed value goes out of scope, they are popped out of the stack automatically.
• The pushed value can shadow or occlude previous values of same identity. This is very important. Certain features like global variables, current date and time function (like in XQuery), data input functions are contextual information, but as they cannot be occluded, they can still be classified as strictly functional.

Some contextual functional features that I can think of are:

• Dynamical scoped variable, as in Common Lisp, Candle and XSLT (which is named as tunneled parameters);
• The context item in XPath/XQuery and current item in XSLT. Most people take for granted that XSLT and XQuery are purely functional. They are not.
• Closure.
• 'this' and 'super' accessors in functional OOP.

I won't argue that contextual functional features are RT (referentially transparent). As pointed out in the LtU discussion, the Wikipedia article is wrong or inaccurate in classifying dynamic scoped variable as RT. But I'd argue that they are still functional. The justification I can put forward is that a program containing contextual functional features can be transformed into a program containing just pure RT functions. The brute force way of transformation is to pass all context information as parameters to all functions in the program.

As can be seen from the LtU discussion, some people might not accept that as valid proof. They would argue that even procedural program can be transformed into functional program. But that's a misconception, which I'll elaborate later. The truth is that a procedural program with external side effects cannot be transformed into pure functional program. By this proof, I believe, Candle's put statement, even in its earlier version put expr = value { ... } is still functional. In the latest release, I change the put statement to put qname = value { ... }, not because I think the earlier version would render Candle impure, but because I think that the later version is more friendly to static analysis.

But I do acknowledge the concern that contextual functional features, if misused, can make a program look less functional. For example, say if a language goes to the extreme to allow any addressable data to be occluded, then a programmer can essentially program in a procedural style by occluding any data when he wants an assignment and passing on the continuation.

But when contextual functional features are carefully defined, we can come up with idiomatic usages, and our programs will not look any less functional then pure RT programs. Just look at XQuery and XSLT. We accept them as 'pure' functional programming languages without second thoughts.

Programming is both science and engineering. When used in science, which often deals with complicated problems, it is often enough to just use RT functions. But when used in engineering and real life programming, which often deals with complex problems, there is often a lot of context information. In such application system, it is often cumbersome to pass all necessary contextual information to a function. Contextual functional features are very important in making these large and complex application systems more modular and maintainable. The price that we have to pay is that contextual functions are harder to analyze and process than pure functions, for example, in caching the output of a function.

As programming evolves, I'm sure we'll see more contextual functional features. CSS (cascading style sheet) and SVG drawing context are good examples of functional contextual dependency in complex application modeling. And we can come up with new idiomatic usages when we selectively allow some context information to be shadowed. For example, if we allow the current date-time to be shadowed, then we can emulate a past or future time, which can be very useful in automatic testing. If we allow the OS specific information to be shadowed, then we may emulate a UNIX environment on a Windows platform.

If we restrict functional programming to just mean RT programming, then we lose all those rich contextual programming features.

2nd Misconcept: Monads are Functional

 

Monad is probably one of the mostly misunderstood programming feature. I myself have attempted very hard to understand it by carefully studying different tutorials for over 10 times at least, and I think I still just have elementary understanding of it.

Most people think monad is a 'functional' programming feature. But this really depends on how we define functional. If it is defined to be RT, as above, then I claim that monads are not functional when they are used to allow functional programming languages to carry out side effects.

Monad itself is just a way of computation. It transform a program into another program. Monad itself does not introduce additional side-effects. But if the result program is procedural, I cannot accept that monad used in such way can be called functional.

Monad doesn't have the magic power of transforming a procedural program into a purely functional program, as some might have mis-believed. This misconcept might be related to the misconcepts that "all programs (whether functional or procedural) are essentially the same" based on the Church-Turing thesis (for example in this LtU post). But this is wrong interpretation of the thesis. I don't think the thesis is actually of any relevance in judging functional programming, because the effective method in the thesis can be functional or non-functional (although the descriptions sound like functional computation). So we can put the thesis aside.

Here, I'll put it very clearly that pure functional program is distinctively different from procedural program. The fundamental assumption of pure functional program is that the inputs to a function must not change during the evaluation of that function. If the inputs might change, then it loses RT and all other fancy functional features. One obvious derivation of the assumption is that the output of a pure function must not overlap its input. Thus a pure function can never to used to directly perform the external side-effects.

A pure function can be used to compute the desired side-effects, but that is just a pending list. The actual side-effects have to be carried out by a procedural program. One good example to understand this is the XQuery Update Facility. This extension to XQuery only generates pending update lists. And the lists can be further processed (merged, validated) in a functional manner. The final 'blast' is left to the underlying engine. So XQuery Update can be considered purely functional, but the final 'blast' is not.

If a pure functional program can never carried out effective side effects, then a true procedural program (which performs side effects) can never be transformed into a pure functional program. Of course, there are many procedural programs out there that can be completely replaced by pure functional program, for example those programs that perform static analysis, report generation and program compilation. But it doesn't mean all procedural programs can be replaced by pure functional programs.

This misconcept is also probably due to the way monad is advocated in Haskell. People advocate Haskell as a pure functional language even when monads are used to perform side effects, which I don't accept. I think the classification of functional languages into pure and impure (e.g. in this wiki article) is simply wrong. You can say XQuery or XSLT are purely functional, but if you say Haskell is still purely functional when it is used to perform side effects, that is simply cheating. When you start mixing black with white, you get all shades of gray; you can't classify a gray color as white, no matter how light it is.

Furthermore, I don't think Haskell's monads when used to perform side effects are in any way superior than other ways of mixing functional and procedural programming. The model to carry out side-effects by monads is different from XQuery Update. XQuery Update only produces pending update lists, and the update commands in these PULs are unordered, and the PULs are mergable. But the side-effects performed by monads are threaded just like procedural program. They can't be reordered or merged. When you use monads to perform side effects, you are just writing a so called 'functional' program to generate a traditional procedural program. If that can be called 'pure' functional programming, then any C program can be called pure functional as well.

I don't doubt monads usefulness. I think it is a powerful meta-programming mechanism. But when monads are use to mimic every ways of procedural programming, like I/O monad, state monad, async monad, concurrent monad, I don't see any extra values that they bring into programming than the procedural counterparts. They are more like the Emperor's New Clothes, sophisticated enough that whoever don't praise them looks like a fool.

In the next blog article, I'll talk about the procedural design in Candle. The mechanisms in Candle to allow procedural programming to be cleanly mixed with functional programming.

(Update: I've posted a new blog article in response to the comments and feedback.)