"Mathematical state" with functional languages?

Question

I've read some of the discussions here, as well as followed links to other explanations, but I'm still not able to understand the mathematical connection between "changing state" and "not changing state" as it pertains to our functional programming versus non-FP debate. As I understand, the basic argument goes back to the pure math definition of a function, whereby a function maps a domain member to only one range member. This is then compared to when a computer code function is given certain input, it will always produce the same output, i.e., not vary from use to use, i.e.i.e., the function's state, as in its domain to range mapping behavior, will not change.

Then it get foggy in my mind. Here's an example. Let's say I want to display closed block-like polygons on an x-y field. In GIS software I understand everything is stored as directed, closed graphs, i.e. a square is four vectors, their heads and ends connected. The raw data representation is just the individual Cartesian start and end points of each vector. And of course, there might be a function in the software that "processed" all these coordinate sets. Good. But what about representing each polygon in a mathematical way, e.g., a rectangle in the positive x, negative y quadrant might be:

Z = {(x,y) | 3 <= x <= 5, -2 <= y <= -1}

So we'd have many Z-like functions, each one expressing an individual polygon -- and not being a whiz with my matrix math, maybe these "functions" could then be represented as matrices . . . but I digress.

So with the usual raw vector-data method, I've got one function in my code that "changes state" as it processes each set of coordinates and then draws each polygon (and then deals with polygons changing), while the one-and-only-one-Z-like-function-per-polygon method would seem to hold to the "don't change state" rule exactly. Right? Or am I way off here? It seems like the old-fashioned, one-function-processing-raw-coordinate-data is not mutating the domain-range purity law either. I'm confused....

Part of my inspiration came from reading about a new idea of image processing where instead of slamming racks of pixels, each "frame" would be represented by one big function capable of "gnu-plotting" the whole image, edges, colors, gradients, etc. Is this germane? I guess I'm trying to fathom why I would want to represent, say, a street map of polygons (e.g. city blocks) one way or the other. I keep hearing functional language advocates dance around the idea that a mathematical function is pure and safe and good and ultimately Utopian, while the non-FP software function is some sort of sloppy kludge holding us back from Borg-like bliss.

But even more confusing is memory management vis-a-vis FP versus non-FP. What I keep hearing (e.g. parallel programming) is that FP isn't changing a "memory state" as much as, say, a C/C++ program does. Is this like the Google File System where literally everything is just sitting out there in a virtual memory pool, rather than being data moved in and out of databases and memory locations? Somehow all these things are related. Therefore, it seems like the perfect FP program is just one single function (possibly made up of many sub-functions) doing one single task -- although a quick glance at any elisp code seems to be a study of programming schizophrenia on this count.

Answer 1

Referential transparency in programming (and mathematics, logic, etc.) is the principle that the meaning or value of an expression can be determined without needing any non-local context, and that the value of an expression doesn't change. Code like

int x = 0;

int nextX() {
  return x++;
}

violates referential transparency in that nextX() will at one moment return 32, and at the next invocation return 33, and there is no way, based only on local analysis, what nextX() will return in any given location. It is easy in many cases to turn a non-referentially transparent procedure into a referentially transparent function by adding an argument to the procedure. For instance, in the example just given, the addition of a parameter currentX, makes nextX referentially transparent:

int nextX( int currentX ) {
  return currentX+1;
}

This does require, of course, that every time nextX is called, the previous value is available.

For procedures whose entire purpose is to modify state (e.g., the state of the screen), this doesn't make as much sense. For instance, while we could write a method print which is referentially transparent in one sense:

int print( int x ) {
  printf( "%d", x );
  return x;
}

there's still a sort of problem in that the state of the system is modified. Methods that ask about the state of the screen will have different results before and after a call to print, for instance. To make these kinds of procedures referentially transparent, they can be augmented with an argument representing the state of the system. For instance:

// print x to screen, and return the new screen that results
Screen print( int x, Screen screen ) {
  ...
}

// return the contents of screen
ScreenContents returnContentsOfScreen( Screen screen ) {
  ...
}

Now we have referential transparency, though at the expense of having to pass Screen objects around. For instance:

Screen screen0 = getInitialScreen();
Screen screen1 = print( 2, screen0 );
Screen screen2 = print( 3, screen1 );
...

This probably feels like overkill for working with IO, since the intent is, after all, to modify some state (namely, the screen, or filesystem, or …). Most programming languages, as a result, don't make IO methods referentially transparent. Some, like Haskell, however, do. Since doing it as just shown is rather cumbersome, these language will typically have some syntax to make things a bit more clean. In Haskell, this is accomplished by Monads and do notation (which is really out of scope for this answer). If you're interested in how the Monad concept is used to achieve this, you might be interested in this article, You Could Have Invented Monads! (And Maybe You Already Have.)