On Looping and Recursion

This post was prompted by a discussion about various programming languages on the Scientific Linux Forum. The discussion is in the member’s sub-forum, so I can’t link it here very effectively.

wearetheborg wrote:

I don’t understand the statement “…develop a sense time being slices along the t-axis (similar to thinking transactionally) instead of dealing in terms of state.” Can you elaborate on this? I have been envisioning state as the state of the various variables and objects.

That is the way most people think of state. This is normal in procedural and structured programming languages (everything from assembler to Fortran to C to Java). It doesn’t have to always work that way, though.

Consider a web request. HTTP is stateless by design. We’ve backhacked the bejeezus out of it to try making it have state (cookies, AJAX, etc) but in the end we’re always fighting against that protocol instead of just accepting that documents aren’t application interfaces. But remember the original Perl CGI stuff? That was all based on the way databases treat time — as transaction points along the t-axis. This is very different than inventing the notion of ongoing state. So a user fills out a form, and when he submits it there is a database transaction that completely succeeds or completely fails. Each request for a page view generates a new page via a function whose input is the request URL (and whatever detailed data lies within the GET string), which then calls another function whose input is a complete response from the database containing a snapshot of data from a point in time, and whose output is the web page requested.

There is no necessity for state here. The input to the function is the request URL string. The function breaks that down and returns a complete output (which could be an error message). But there is nothing ambiguous about this and executing the same functions with the same inputs would always return the exact same output, every time. There are no objects carrying state between requests. There are no variables that live beyond the request -> response lifetime.

“But timestamps and things might change and if someone updates a page then a request before and after would be different!” you might say. And this is true (and indeed the whole point of such CGI scripts) but all that is external to the functions themselves. The content of the pages, including the timestamps, page templates and record data, are input to the functions, not persistent state variables that are evolving with time. The functions don’t care what the inputs are, they only need to do their job — the data is a completely separate concern (remembering this will minimize fights with your DBA, by the way… if you know an asshole of a DBA, consider that he’s probably not trying to be an asshole, but rather trying to help you simplify your life despite yourself).

All this functions-that-don’t-carry-state business means is that we don’t need variables, we need symbolic assignment. Further, its OK if that symbolic assignment is immutable, or even if that assignment never happens and is merely functions passing their results (or themselves) along to one another.

This is the foundation for transactional thinking and it treats time as slices or points along the t-axis instead of a stateful concept that is ongoing. Its also the foundation of quite a bit of functional programming. There are no variables internal to the functions themselves that have any influence on the output of the program. Every case of a given input results in an exactly defined output, every time. This simplifies programming in general and debugging in particular.

Its not the best for everything, of course. In simulations and games you need a concept of state to cover the spans between transactions or time-slicing periods. For example, in a game you are fighting a mob. The fight isn’t instant, it is a process of its own and the immediate gameplay is based on the state carried in the various objects that make up your character, the mob, equipped items, world objects, etc. But it doesn’t really matter in a grander sense whether or not each strike or point of time in the fight is actually transacted to the data persistence layer — if the server crashed just then you’d probably prefer to not log in back to the middle of a boss fight while your screen is still loading, or half your party isn’t logging in at the same time with them, etc.

So the fight is its own discreet subsystem which is intimately concerned with state and OOP design principles and is therefore completely expendable — it matters not if you won or lost that particular fight if the server crashes in the middle of it. The overall world, however, is designed based on transactional concepts of time slices — it does matter what the last non-combat status and position snapshot of your character was, and you probably care quite a bit about certain potentially monumental events like when your character binds himself to some epic loot, level up or apply a new skill point (that better go in the database, right?).

The vast majority of user applications aren’t games or simulations, though. Almost everything on the web is text string manipulation and basic arithmetic. Almost everything in business applications development amounts to the same. So we don’t need stateful functions and objects, in fact we get confused by them (the exception here being the interface itself — objects make awesome widgets and windows). If I make an object to represent, say, a customer invoice, and I’m doing calculations on that invoice or within it using methods, to really bug test that object I have to test every method under every possible condition, which means every permutation of state possible. If that object is a subclass of anther object, or interacts with another object in the system, like say a customer record object or a discount coupon object, I have to test both against each other in every combination of possible states. That’s impossible in the lifetime of this universe, so nobody does it. The closest we come is testing a tiny subset of the most likely cases out of a tiny subset of what’s possible, and then we are constantly surprised at lingering bugs users report in modules later because they passed all the tests (or even dumber, we aren’t surprised at all, which says something about how blindly we stick to methodology in the face of contrary evidence).

But we don’t need a stateful concept for, say, a customer invoice. We need a snapshot of what it looked like before, and what we want it to look like next. This “next” result (which is just the output of a function), once confirmed (transacted in the database) becomes the next snapshot and you discard the intermediate concept of “state” entirely. Line item calculations and changes should be functions that operate per line on input data from that line. Invoice sums, averages, discounts, etc. should be functions concerned only with relevant input data as well, namely the aggregate result of each line item.

None of this involves a stateful requirement and shouldn’t involve stateful objects because that state is an unnecessary complication to the system. It also causes problematic architectural questions (is an invoice an object? is a line item an object? are they both objects? what do they inherit from? do they have a common ancestor? how do we make relational data sorta fit with our object model?) What are all these class declarations and the attendant statefulness actually doing for you? Nothing but permitting you to write yourself into a hole with mistaken side-effects (oops, that method wasn’t checking to clear the “discount” boolean in this object before it does self.foo()).

Even more interesting, sticking with the web example above and moving it forward to 2012 where everyone is mad for Django and Rails, these ORM-based frameworks almost never maintain persistent state objects between calls. When they do it often causes a peculiar type of unique-per-thread bug. So what is all this business about class/model declarations in the first place, since objects are first and foremost data structures with behaviors? These class declarations are trying very hard to be CREATE TABLE and ALTER TABLE SQL commands but without the benefit of actually being SQL commands — in other words, they are a weak form of data dictionary that sacrifice both the clean presentation of S-expressions or YAML trees and the full power of your favorite database’s native language.

Dealing with the database on its own terms and letting your functions be stateless makes it enormously easier to test your system because each function has a knowable output for each knowable input. It does mean that you must have a small constellation of functions to do the job, but you were going to write at least as many methods against your objects anyway (and often duplicate, or very nearly duplicate methods across non-sibling objects that do very nearly the same thing — or even worse, inherit several layers deep in a ripped fishing net pattern, which makes future changes to parent classes a horror). If you are dealing with data from a database trying to force your relational data into objects is poor thinking in most cases anyway, not least because none of that object architecture gets you one iota closer to accomplishing your task, despite all the beautiful design work that has to go into making relational data work with OOP. Unless you’re writing a simulation (as in, a MUD, an MMORPG or a flight simulator) there is no benefit here.

The easiest way to envision slices of time for people who got into programming later than 1994 or so is usually to recall the way that database-to-webpage functions worked in the CGI days as referenced above. They don’t maintain state, and if they do it is just as static variables which exist long enough to dump content into a webpage substitution template before being deallocated (and if written differently this wouldn’t always be necessary, either — the following are not the same: return (x + 1);, return x++;, x = x + 1; return x;). The only thing that matters to such functions is the input, not any pre-existing state. You can, of course, include cookies and SSL tokens and Kerberos tickets and whatnot in the mix — they merely constitute further input, not stateful persistence as far as the function itself is concerned.

There are some consequences to this for functional programs. For one thing, most loops wind up working best as recursively defined functions. In a imperative OOP language like Java this is horrible because each iteration requires instantiating a new object with its own state and therefore becomes a wild resource hog and executes really slow. In a functional language, however, tail-recursive functions often perform better than the alternative loop would. The reason for this is that (most) functional languages are optimized for tail-recursion — this means that a recursive function that calls itself as the last step in its evaluation doesn’t need to return state to its previous iterations; it is dependent only on its input. The machine can load the function one time and jump to its start on each iteration with a new value (whatever the arguments are) in the register without even needing to hit the cache, mess with iterator variables, check, evaluate or reform state, etc. (Note that this is possible in languages like C as well, but usually requires use of the “evil” goto statement. In higher level languages, however, this sort of thing is usually completely off limits.)

Let’s look at a stateful countdown program of the type you’d probably write on the first day of class (small caveat here: I’ve never had the privilege to attend a class, but I’m assuming this is the sort of thing that must go on the first day):

#include <stdio.h>

int main()
{
    int x = 10;

    while (x > 0)
    {
        printf("%d\n", x);
        x--;
    }

    printf("Blastoff!\n");
    return 0;
}

Of course, this could be done in a for() loop or whatever, but the principle is the same. Looping is king in C, and for a good reason. Here is an equivalent program in Guile (a Scheme interpreter that’s just one “yum install guile” away if you want to play with it):

(define (countdown x)
  (begin
    (display x)
    (newline)
    (if (> x 1)
      (countdown (1- x))
      (display "Blastoff!\n"))))

(countdown 10)

In this program there is no loop, there is a call to itself with an argument equal to the initial argument decremented by 1, but we are not actually dealing with variables at all here.

In fact, the expression (1- x) does not change the value of x at all, because it is merely an expression which returns “the result of ‘decrement x by 1′” (an equivalent would be (- x 1), which may or may not be equal in efficiency depending on the lisp environment) and not an assignment statement. (There are assignment statements in most functional languages, and they are primarily (ab)used by folks coming to functional languages from non-functional ones. Not saying you never want variables, but more often than not its more sensible to deal with expressions that say what you mean exactly once than stateful variables).

Being a toy example I’m using a “begin” statement to guarantee execution order in the interest of formatting text output. This sort of thing isn’t present in most functions, since whatever is required for the return value will be executed. Here we are generating an output side effect. We could eliminate the “begin” in the interest of being “more functional” while still emitting something to stdout as a side effect, but might be harder to read for someone coming from an imperative background:

(define (countdown x)
  (display (string-append (number->string x) "\n"))
  (if (> x 1)
    (countdown (1- x))
    (display "Blastoff!\n")))

If displaying an integer argument with a newline appended (or more generally, any argument value with a newline appended) was a common requirement (like for log files) the line beginning with display would become its own function, like display\n or something and be called more naturally as (display\n x).

This is a very simple example of how stateless recursion works in place of loops. You can implement loops in functional languages, which is usually a bad idea, or you can implement tail-recursive functions in most imperative languages, which is also usually a bad idea (especially when it involved objects, unless you start inlining assembler in your C with the appropriate jumps/gotos… which isn’t worth the trouble compared to a loop). Having demonstrated the equivalence of loops and recursion for most purposes, it bears mentioning that within the lisp community (and probably others) using tail-recursive functions in place of while()/for() loops is so common that very often when someone says “loop” what they mean is a recursive loop, not an iterative loop.

I say this to illustrate that when comparing languages its not about whether you can do something in language X or not, but whether a certain style of thinking matches the way the compiler or execution environment work. Step outside of the pocket that the language or runtime has built for you and you wind up very quickly in a nasty, panicky, twisty place where unmaintainable hacked up speed optimizations start feeling necessary. The futility of such speed optimizations is usually evidence that you’ve existed the pocket of your language, and is why old timers often are heard saying things like “if you need all those speed hacks, you need to reconsider your design overall” — its not because there is a speedier way to make that one method or function work, per se, but more typically what they are getting at is that you are thinking against the paradigms or assumptions that your language or environment was designed around.

In cases not involving simulation I find that carrying lots of state in variables, structs and the like complicates even simple things unnecessarily and makes testing confusing by comparison to stateless functions. OOP is even worse in this regard because you’ve got functionality intertwined with your state vehicles, and inheritance makes that situation even more convoluted. When dealing with lots of state stack traces can’t give you a clear picture of what happens every time with any given input, only what happened this time, because understanding what happened when you’re dealing with state is not as simple as looking at the arguments, you have to consider the state of the environment and objects within it at the moment of execution. This gets to the heart of why I recommend thinking of time as slices or points or snapshots instead of as continuous state, and is a very important idea to understand if you want to grok functional programming.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>