How do functional programming languages work?

Question

I was just reading this excellent post, and got some better understanding of what exactly object oriented programming is, how Java implements it in one extreme manner, and how functional programming languages are a contrast.

What I was thinking is this: if functional programming languages cannot save any state, how do they do some simple stuff like reading input from a user (I mean how do they "store" it), or storing any data for that matter?

For example - how would this simple C thing translate to any functional programming language, for example haskell?

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

Answer 1

Functional programing drives from lambda Calculus. If you truly want to understand Functional programing check out http://worrydream.com/AlligatorEggs/

It is a "fun" way to learn lambda Calculus and bring you into the exciting world of Functional programming!

How knowing Lambda Calculus is helpful in functional programming.

So Lambda Calculus is the foundation for many real-world programming languages such as Lisp, Scheme, ML, Haskell,....

Suppose we want to describe a function that adds three to any input to do so we would write:

plus3 x = succ(succ(succ x)) 

Read “plus3 is a function which, when applied to any number x, yields the successor of the successor of the successor of x”

Note that the function which adds 3 to any number need not be named plus3; the name “plus3” is just a convenient shorthand for naming this function

(plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

Notice we use the lambda symbol for a function (I think it looks kind of like an Alligator I'm guessing thats where the idea for Alligator eggs came from)

The lambda symbol is the Alligator (a function) and the x is its color. You can also think of x as an argument (Lambda Calculus functions are really only suppose to have one argument) the rest you can think of it as the body of the function.

Now consider the abstraction:

g ≡ λ f. (f (f (succ 0)))

The argument f is used in a function position (in a call). We call g a higher-order function because it takes another function as an input. You can think of the other function calls f as "eggs". Now taking the two functions or "Alligators" we have created we can do something like this:

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) 
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

If you notice you can see that our λ f Alligator eats our λ x Alligator and then the λ x Alligator and dies. Then our λ x Alligator is reborn in the λ f's Alligator eggs. Then the process repeats and the λ x Alligator on the left now eats the other λ x Alligator on the right.

Then you can use this simple set of rules of "Alligators" eating "Alligators" to design a grammar and thus Functional programming languages were born!

So you can see if you know Lambda Calculus you will understand how Functional Languages work.

Answer 2

haskell:

main = do no <- readLn
          print (no + 1)

You can of course assign things to variables in functional languages. You just can't change them (so basically all variables are constants in functional languages).

Answer 3

Functional language can save state! They usually just either encourage or force you to be explicit about doing so.

For example, check out Haskell's State Monad.

Answer 4

(Some functional languages permit impure functions.)

For purely functional languages, the real world interaction is usually included as one of the function arguments, like this:

RealWorld pureScanf(RealWorld world, const char* format, ...);

Different languages have different strategies to abstract the world away from the programmer. Haskell, for instance, uses monads to hide the world argument.

---

But the pure part of functional language itself is already Turing complete, meaning anything doable in C is also doable in Haskell. The main difference to imperative language is instead of modifying states in place:

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

You incorporate the modification part into a function call, usually turning loops into recursions:

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}

Answer 5

Plenty of good answers here, but they are long. I'm going to try to give a helpful short answer:

• Functional languages put state in the same places that C does: in named variables and in objects allocated on the heap. The differences are that:

  • In a functional language, a "variable" gets its initial value when it comes into scope (through a function call or let-binding), and that value doesn't change afterward. Similarly, an object allocated on the heap is immediately initialized with the values of all its fields, which don't change thereafter.

  • "Changes of state" handled not by mutating existing variables or objects but by binding new variables or allocating new objects.

• IO works by a trick. A side-effecting computation that produces a string is described by a function that takes a World as argument, and returns a pair containing the string and a new World. The World includes the contents of all disk drives, the history of every network packet ever sent or received, the color of each pixel on the screen, and stuff like that. The key to the trick is that access to the World is carefully restricted so that

  • No program can make a copy of the World (where would you put it?)

  • No program can throw away the World

  Using this trick makes it possible for there to be one, unique World whose state evolves over time. The language run-time system, which is not written in a functional language, implement a side-effecting computation by updating the unique World in place instead of returning a new one.

  This trick is beautifully explained by Simon Peyton Jones and Phil Wadler in their landmark paper "Imperative Functional Programming".

Answer 6

might be useful , Function Programming for the rest of us

Answer 7

The technique for handling state in Haskell is very straightforward. And you don't need to understand monads to get a handle on it.

In a programming language with state, you typically have some value stored somewhere, some code executes, and then you have a new value stored. In imperative languages this state is just somewhere "in the background". In a (pure) functional language you make this explicit, so you explicitly write the function that transforms the state.

So instead of having some state of type X, you write functions that map X to X. That's it! You switch from thinking about state to thinking about what operations you want to perform on the state. You can then chain these functions together and combine them together in various ways to make entire programs. Of course you're not limited to just mapping X to X. You can write functions to take various combinations of data as input and return various combinations at the end.

Monads are one tool, among many, to help organise this. But monads aren't actually the solution to the problem. The solution is to think about state transformations instead of state.

This also works with I/O. In effect what happens is this: instead of getting input from the user with some direct equivalent of scanf, and storing it somewhere, you instead write a function to say what you'd do with the result of scanf if you had it, and then pass that function to the I/O API. That's exactly what >>= does when you use the IO monad in Haskell. So you never need to store the result of any I/O anywhere - you just need to write code that says how you'd like to transform it.

Answer 8

I'm breaking off a comment reply to a new answer, to give more space:

I wrote:

As far as I can tell, this IO story (World -> (a,World)) is a myth when applied to Haskell, as that model explains only purely sequential computation, while Haskell's IO type includes concurrency. By "purely sequential", I mean that not even the world (universe) is allowed to change between the start and end of an imperative computation, other than due to that computation. For instance, while your computer is chugging away, your brain etc cannot. Concurrency can be handled by something more like World -> PowerSet [(a,World)], which allows for nondeterminism and interleaving.

Norman wrote:

@Conal: I think the IO story generalizes pretty nicely to nondeterminism and interleaving; if I remember right, there's a pretty good explanation in the "Awkward Squad" paper. But I don't know of a good paper that explains true parallelism clearly.

@Norman: Generalizes in what sense? I'm suggesting that the denotational model/explanation usually given, World -> (a,World), doesn't match Haskell IO because it doesn't account for nondeterminism and concurrency. There might be a more complex model that does fit, such as World -> PowerSet [(a,World)], but I don't know whether such a model has been worked out and shown adequate & consistent. I personally doubt such a beast can be found, given that IO is populated by thousands of FFI-imported imperative API calls. And as such, IO is fulfilling its purpose:

Open problem: the IO monad has become Haskell’s sin- bin. (Whenever we don’t understand something, we toss it in the IO monad.)

(From Simon PJ's POPL talk Wearing the hair shirt Wearing the hair shirt: a retrospective on Haskell.)

In Section 3.1 of Tackling the Awkward Squad, Simon points what doesn't work about type IO a = World -> (a, World), including "The approach does not scale well when we add concurrency". He then suggests a possible alternative model, and then abandons the attempt at denotational explanations, saying

However we will instead adopt an operational semantics, based on standard approaches to the semantics of process calculi.

This failure to find a precise & useful denotational model is at the root of why I see Haskell IO as a departure from the spirit and the deep benefits of what we call "functional programming", or what Peter Landin more specifically named "denotative programming". See comments here.