7
$\begingroup$

I was reading Structure and Interpretation of Computer Programs (SICP), MIT. What I have understood is that in pure functional programming language, there is no such thing as a local state. SICP, pg 230 says:

"Programming without any use of assignments, as we did throughout the last two chapters of this book, is accordingly known as functional programming."

I come from a imperative programming background, and I can't seem to comprehend how to design a program that models a real world system (like a simple bank or a library management software) without the idea of state.

If functional programming does not have the idea of a state, how do we do this?

$\endgroup$
7
$\begingroup$

The key with functional programming is not that there is no state, it's that there is explicit state.

What this means is, that your state is passed around as a parameter to your functions. It's an actual value, that you can get your hands on, look at, and pass to other functions.

For example, let's look at the Dynamic Programming method of calculating the Fibonacci numbers. In an imperative language, you'd have something like this:

def fib(n):
  A = {}
  A[0] = 0
  A[1] = 1
  for i in [2 .. n+1]:
      A[i] = A[i-1] + A[i-2]
  return A[n]

To do this without state, you just have to explicitly pass your store around. Using Haskell-ish syntax:

fib n = fibHelper 2 n {(1,1), (0,0)}

fibHelper i end cache = 
  if 
    i > end
  then 
    lookup end cache
  else
    let
      newVal = (lookup (i-1) cache) + (lookup (i-2) cache)
      newCache = insert i newVal cache
    in
      fibHelper (i+1) end newCache

Now, this is a bit contrived, since you don't need the whole array for the Fibonacci numbers, but you can imagine using this for more complicated dynamic programming problems like Knapsack, where you do need the entire set of previously computed values.

The key thing to understand here is that insert is a function which takes a store, and returns a new store, which is equal to the original with a new value added. The original value of cache doesn't get destroyed, so if you had an application where you needed some sort of "undo" operation, you could keep track of your state's history.

You might say "but that looks inefficient! You're creating a whole new store each time!" However, usually in functional languages, these things are implemented cleverly using references, so that there aren't whole new copies of the data lying around.

It's also worth mentioning that this pattern of having a state parameter, passing it around as your computation progresses, and modifying it, is very common. People have invented abstractions, like the State monad, which allow you to write things that look imperative, but which are purely functional "under the hood."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.