Thursday, December 8, 2011

What is Pure Computation

In this post, I'll respond to the comments and feedback to my recent blog on 2 misconcepts about functional programming.

I write the original blog because I found it funny that languages like XQuery and XSLT, which I feel so 'functional', is not actually referentially transparent. Yet monadic I/O as implemented in Haskell, which I feel so 'procedural' is referentially transparent. So my intension in the blog was to come up with something that can better depict the computation model of XQuery and XSLT. My approach was to keep the concept of RT, but stretch the concept of functional programming. From the feedback, I can see that people think that's not acceptable.

I admit that it might not be a good idea to stretch some existing well established term. That's fine. I can go plan B.

A new term can be coined instead. For the time being, I call it 'pure computation'. 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 red 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.

By this definition, I want to make sure 'pure computation' cannot carried out side effects through some back door. If I'm the gatekeeper of the real hosting world, I can sleep soundly at night when I grant someone the right to run pure computational program in the hosting world.

Below are two diagrams comparing the two ways of viewing the programming world:


Which one better represents you perception of the programming world, I left it to you to decide.

2 comments:

  1. It seems you've stated the fact that a pure function can contain local mutation. Or is there something different going on?

    ReplyDelete
  2. There are no "RT functions with monadic I/O" in Haskell (barring the use of unsafePerformIO, which can be used to thwart this, but then you can no longer claim that your code is pure if you do). There are "RT functions on monadic I/O", which have no side effects. IO is a more akin to a datatype that can be acted on by functions, like an integer or string. One value of IO is bound to main and that piece of IO is what is actually run. This is magical, "main" is a special name and "main = ..." is an entry point. All other IO does nothing, it has to somehow be bound to main. Usually this is done by composing a bunch of IO into a single program and then binding the result to main. The composition functions themselves (>>= and return) have no side effects.

    That said, Haskell does support referentially transparent procedural programming with local mutable variables, but via a different mechanism from IO.

    ReplyDelete