Lambda the Ultimate

Interesting blog post. I disagree with you on both points.

In terms of monads being function I think Simon Peyton Jones is absolutely correct.

1) Functional programming happens in the world of pure timeless abstract mathematics where platonic ideal data is fed into stateless functions to produce results that are timeless.

2) The purpose of a computer program is to produce a side effect often dependent on ambient state.

Monads are the means by which the paradigm of (1) expresses itself in the world of (2). Monads are the medium of expression. Without the medium the mathematical expression is empirically unknowable. The expression must take on the the properties of the medium in which the ideal needs to be expressed.

So of course monads aren't purely functional, they are where purely functional code finds expression in the actual world. But that definition doesn't make them not part of a purely functional language. What makes a language purely functional is not that it can't carry out side effects but rather it makes side effects painful so the vast bulk of the code is side effect free.

As for the first point. Of course the universe is not purely functional. Once data is passed out of the purely functional part and into the universe it becomes tainted. Purely functional program reasoning treats all code that exists in the actual physical universe as tainted. So passing data around via. a container makes it immediately obvious that the data is not being preserved between function calls. That's all purely functional programming can do, make it explicit what can't be controlled.

Finally on the example of large quantities of data. There are no limits on the size of the state being weaved through the code via. the State Monad. If you mean a large block of unchanging data, an object with a bunch of methods works fine and just pass the object, and pick off specific details via. the method calls. Haskell allows you to define arbitrarily complex constants so you are only passing one variable and that only to top level functions.

Unless I missed something, neither of your points is addressed in the blog post. I'll address them:

Dynamic scope is functional

What's your definition of "functional"? Mine (and I suspect most people's) includes referential transparency, and dynamic scope precludes referential transparency. Unless your definition of "functional" or "dynamic scope" differs from the common one, this statement is false.

On the topid of definitions, in the previous discussion you mention something about a Candle program's main function being referentially transparent -- this is true of imperative languages so long as they don't to any I/O, so this isn't really saying much. Referential transparency is only useful if it's global.

Monads are not functional

I'm not sure what your definition of a monad is. Mine is a data type M which has defined two functions, return: a -> M a, and bind: M a -> (a -> M a) -> M a (or alternatively, return: a -> M a, join: M (M a) -> M a, and fmap: (a -> b) -> (M a -> M b)). These are just restrictions on the kinds of data types called monads. In an otherwise functional language, you cannot produce non-functional semantics by restricting to the language.

That the IO monad in Haskell performs IO is irrelevant. I can implement a replacement IO module using pure constructs to say, model a world where the standard input stream consists only the text of Fresh Prince. Every program will behave the same as if I ran the program with the actual IO monad and echoed that same text to Fresh Prince. The only difference is that use of the actual IO monad means a program might produce a different result on each run. This is expected and desired behavior in programs performing I/O.

What's way more important to the notion of "functional" is that code is referentially transparent within a given run, not when run with a different world state.

Let me poke the hole even bigger. As I think deeper about I/O monad, I can claim that it is not RT. Here's my prove:

• As I mentioned in my blog, and I think everyone would also agree, for a function to be RT, it's output must not overlap its input. In other words, the output must not change the input during the execution of the function.
• Functions using I/O monad in Haskell are declared as:
  main :: RealWorld1 -> ((), RealWorld2)
  ... etc.

• The question now is: Does the output RealWorld2 overlap the input RealWorld1 in monadic I/O functions?

  I think most functional programmer won't able to answer that, because this RealWorld is just something magic, opaque.

• My own thinking is that output RealWorld2 definitely overlaps, i.e. changes, the input RealWorld1 in some way, thus I declare i/O monad non-RT.

If we bend the rule to allow a pure (i.e. RT) function to mutate its input in someway, then all procedural functions can be called pure function.

Let me know if you think my proving is wrong in any way.

Thanks for all you detailed comments and feedback. I've written a new blog article in response.

In brief, it talks about a new term, I called "Pure Computation", which I hope can better describe my intention.

Here's the definition - a function may be described as pure computation if both these statements about the function hold:

• The function always evaluates to the same result value given the same argument value(s) and the same set of context value(s). The function result value cannot depend on other hidden information.
• Evaluation of the result does not cause any semantically observable side effect or output through the direct interface of the hosting world.

I've highlighted in bold the parts that are in contrast to Wikipedia's definition of pure function.

Adding dependency on context values is to help include contextual features in XQuery and XSLT. The condition that side effect must be observed through the direct interface of the hosting world is added, so that we cannot be fooled by the threading RealWorld. When we talk about side effect, our primary concerns are of course related to the real hosting world instead of a virtual RealWorld that the compiler makes us believe. This condition is to help exclude Haskell kind of monadic I/O implementation.

I think you are slightly confused about the IO monad.

Building a value of type (IO a) is exactly that: you build - in a pure functional language - a value of type IO a.

Exactly as you would build a String or a List of Int.

The use of the value by the runtime will produce side effects.
But the creation of something of type IO a has no side effect.

In a Haskell program, you only create such a value of type IO a. Consequently, the program is built with pure functions.

I am getting a mixed feeling from your blog posts. The first reaction is to say that they are about two misconceptions of yours; clearly your are wrong about some of the things you say.

On the other hand, what you say is not empty; you are trying to make a finer distinction about "contextually referential computations" that, I think (I haven't yet taken the time to understand it well), has value.

I think it could help your point to actually define precisely the program transformation you are talking about. It will probably be a monad. If it is, you can compare it with other monads to see if it can be described as having "less" effects, eg. as the Reader or Writer monads have "less" effects than the full State monad. You would gain a more precise description of the structure of your restricted effects, which is currently very hand-wavy. I realize it must be feel precise to you as you are familiar with the specialized domain, but it is still hand-wavy.

I personally think everyone is confused about transparency. In my view this is a property of concrete syntax.

Consider a compiler with a high level layer of sugar that translates C into Haskell, and a low level layer that translates Haskell into Assembler.

Clearly, C and Assembler aren't transparent, but we'd like to think Haskell is.

What this means is that monads may be functional but if you add syntactic sugar to make the use appear more conventional or imperative, the result is not. The syntax, not the semantics, are what matter.

After all it is well established functional and imperative code can be translated into each other.