[TriLUG] What about this is functional programming, and what about it isn't

[Michael Alan Dorman]

Steve Litt <slitt at troubleshooters.com> writes:

> Being a firm believer in data-centered programming, functional
> programming doesn't come easy to me, but I have to include it.

I have to say, as a haskell hobbiest, this strikes me as a weird
statement, as I can't imagine something being more data-centered than
functional programming.

I say this because one perhaps-not-horrible way to think about
functional programming would be that it is focussed on running
transformations on data to produce new data.

This has been pretty much true since the earliest days of LISP, which
got so much of its power, which gets so much of its power from the fact
that its code is also data.

> * The main logic isn't iteration, it's let_human_move() and
>   machine_moves_now() repeatedly call each other recursively, so at
>   the top level there's no state but the function args and returns.

Well, kinda?

Please note: I am still only a journeyman at writing stuff in an FP
style---and, of course, there are dozens of FP styles to choose
from---but one of the secondary tenets of a certain style of FP might be
expressed as "figure out the shape of your algorithm, encode that shape
in a function that then takes other functions to do the actual work".

This separates the process of stepping your transformations over
successively updated bits of data from the process of actually
transforming the data.  It has the nice quality of making it easier to
get both parts correct, because you're clear about where the boundaries
are.

The map function, for instance, is a perfect example of this---the
process of iterating over your list of items is separated from the
process of transforming an individual item.

So, to talk about your particular example, there is this pattern of
having a seed value to which you successively apply transformations,
which is then passed in as the next seed value, to to achieve some end
state---which is what you're doing in broad strokes---called an
'unfold', or to be all math-y like Haskell people tend to, an
'anamorphism'.

All of which is to say: while your code is good from a referential
transparency/purity standpoint, the fact that you have intermixed the
bits that effectively handle flow control with the bits that munge the
data means that in many ways, this isn't a very FP program at all.

> * With the exception of a few prints and a couple input accepts, no
>   function has side effects: Each function's effect is only on the
>   return value.
> * Every function's return value is affected only by the function's
>   inputs.

These are kind of redundant, but yes transforming inputs to outputs
without side-effects---that is referential transparency/purity---is very
functional.  And a lot of the code is doing that, but both the biggest,
most important pieces, and the smallest, least significant pieces,
aren't.

> * I'm passing around, as an argument and as a return, a huge piece of
>   state called "board".

That isn't a disqualification at all. Functional programs intended to do
something can't eschew state if they intend to do anything useful.

In fact, some of the most confusing bits about Haskell for beginners
(the dreaded Monads) are actually just structures that allow programmer
to *implicitly* pass around state-y bits while being very clear about
data dependencies, etc.

> * The internals (implementation) of many of the functions are extremely
>   state rich and contain lots of state-depending loops.

I agree, this isn't very functional.

> I'm sure some of you know a lot more about functional programming than
> I do, so it would help me a lot if you could tell me what is, and what
> is not, functional programming within this tic-tac-toe program.

On the micro level, you do a lot of munging of 'board' using for loops
and array dereferences.  Some of these things are entirely appropriate,
some of them could probably be expressed in a more functional way.  For
instance in best_guess():

       for i in range(1,10):
            if slot_available(board, i):
                return i

would be more functionally expressed as (in Perl, since I don't really
know python):

     return first_idx {slot_available ($board, $_)} [1..10]

Here first_idx() is a function that encapsulates the idea of "search a
list for a value for which this predicate returns true, and then give me
its index".  You just fit in in whatever predicate you like, the
structure of the algorithm is kept separate from the code that
determines if it "matches".

On the medium level, it does well.  Most functions transform inputs into
outputs, however they handle things under the covers.

On the top level, those two functions locked into a recursive embrace
should probably be divested of their flow-control properties, and turned
into more transformation-y functions that are then slotted into
something that expresses the algorithm separate from its steps.

Hope this helps.

Mike.