21

I have been trying to wrap my head around functional programming for a while now. I have looked up lambda calculus, LISP, OCaml, F# and even combinatorial logic but the main problem I have is this - how do you do things that require side effects like:

  • interacting with a user,
  • communicating with a remote service, or
  • handle simulating using random sampling

without violating the fundamental premise of pure functional programming which is, that for a given input the output is deterministic?

I hope I am making sense; if not I welcome any attempts to help me understand. Thanks in advance.

0

10 Answers 10

24

Most real-world functional programming is not "pure" in most senses, so half of the answer to your question is "you do it by giving up on purity". That said, there are alternatives.

In the "purest" sense of pure, the entire program represents a single function of one or more arguments, returning a value. If you squint your eyes and wave your hands a bit, you can declare that all user input is part of the function's "arguments" and that all output is part of the "return value" and then fudge things a bit so that it only does the actual I/O "on demand".

A similar perspective is to declare that the input to the function is "the entire state of the outside world" and that evaluating the function returns a new, modified "state of the world". In that case, any function in the program that uses the world state is obviously freed from being "deterministic" since no two evaluations of the program will have exactly the same outside world.

If you wanted to write an interactive program in the pure lambda calculus (or something equivalent, such as the esoteric language Lazy K), that's conceptually how you'd do it.

In more practical terms, the problem comes down to making sure that I/O occurs in the correct order when input is being used as an argument to a function. The general structure of the "pure" solution to this problem is function composition. For instance, say you have three functions that do I/O and you want to call them in a certain order. If you do something like RunThreeFunctions(f1, f2, f3) there's nothing to determine the order they'll be evaluated in. On the other hand, if you let each function take another function as an argument, you can chain them like this: f1( f2( f3())), in which case you know that f3 will be evaluated first because the evaluation of f2 depends on its value. [Edit: See also the comment below about lazy vs. eager evaluation. This is important, because lazy evaluation is actually quite common in very pure contexts; e.g., the standard implementation of recursion in the pure lambda calculus is nonterminating under eager evaluation.]

Again, to write an interactive program in the lambda calculus, this is how you'd probably do it. If you wanted something actually usable for programming in, you'd probably want to combine the function composition part with the conceptual structure of functions taking and returning values representing the state of the world, and create some higher-order abstraction to handling pipelining the "world state" values between I/O functions, ideally also keeping the "world state" contained in order to enforce strict linearity--at which point you've all but reinvented Haskell's IO Monad.

Hopefully that didn't just make you even more confused.

8
  • 4
    "On the other hand, if you let each function take another function as an argument, you can chain them like this: f1( f2( f3())), in which case you know that f3 will be evaluated first because the evaluation of f2 depends on its value." - only if f2 and f1 actually use its argument to compute its result, and only if the caller of f1 will also use its result. Otherwise lazy evaluation can legitimately kick in. Commented Dec 16, 2009 at 19:00
  • 5
    You are of course correct, and I glossed over a lot of other details for the sake of not exacerbating the answer's already prodigious verbosity. Commented Dec 16, 2009 at 19:06
  • So is the world state changing as the functions are being evaluated? What rewrites the world state structure is it outside of the application? Do you have to keep calling your application in a loop to deal with the changing worldstate?
    – Jeremy E
    Commented Dec 16, 2009 at 19:45
  • The "world state" is mostly a conceptual abstraction, not an actual data structure in the program. All that matters is that any function with side-effects accept a world state as a parameter and return a new world state when it's done. The progression of unique world state tokens as they pass between functions represents the irrevocable effects the program has on the outside world. As long as world states are never reused, consistent structure will be maintained. Commented Dec 16, 2009 at 20:05
  • 2
    To be pedantic, the world state for a chess game would also include whose turn it is and partial movement history for certain pieces (due to the rules for en passant capture and castling). A Haskell-style, state-based monad encapsulates the details of that state and abstracts the process of passing state data between functions. You could theoretically pass an explicit state structure around for the same effect--the monad is only there to enforce correctness and avoid boilerplate code. Commented Dec 16, 2009 at 21:53
10

Haskell is a pure functional programming language. In Haskell all functions are pure (i.e. they always give the same output for the same inputs). But how do you handle side-effects in Haskell? Well, this problem is beautifully solved through the use of monads.

Taking I/O as an example. In Haskell every function that does I/O returns an IO computation, i.e. a computation in the IO monad. So, for instance, a function that reads an int from the keyboard, instead of returning an int, returns an IO computation that yields an int when it is run:

askForInt :: String -> IO Int

Because it returns an I/O computation instead of an Int, you cannot use this result directly in a sum, for example. In order to access the Int value you need to "unwrap" the computation. The only way to do this is to use the bind function (>>=):

(>>=) :: IO a -> (a -> IO b) -> IO b

Because this also returns an IO computation, you always end up with an I/O computation. This is how Haskell isolates side-effects. The IO monad acts as an abstraction of the state of the real world (in fact under the covers it is usually implemented with a type named RealWorld for the state part).

6
  • But since monads are non-function, Haskell is not a "pure functional programming language". Commented Dec 16, 2009 at 18:49
  • 2
    @RBarryYoung: what do you mean, they are "non-function"? What makes you say that Haskell is not purely functional? Haskell is purely functional.
    – Stephan202
    Commented Dec 16, 2009 at 18:54
  • 2
    Being a pure functional language does not mean everything is a function. It is a functional language and all functions are pure (nevermind unsafePerformIO) Commented Dec 16, 2009 at 18:56
  • 4
    Haskell is pure. Haskell programs do not have side effects - they return a computation (not a value), that, given one state of the "world" (wrapped in an IO monad), produce another state of the "world" (the returned IO monad). Commented Dec 16, 2009 at 19:02
  • This blog post (not by me) makes an interesting/humorous argument that C is purely functional: conal.net/blog/posts/the-c-language-is-purely-functional Commented Dec 16, 2009 at 23:23
7

Interacting with a user and communicating with a remote service do require some sort of non-functional part to your software.

Many "functional languages", (like most Lisps) are not purely functional. They still let you do things with side-effects, though side-effecty things are "discouraged" in most contexts.

Haskell is "purely functional" but still lets you do non-functional things via the IO monad. The basic idea is that your purely functional program emits a lazy data structure which is evaluated by a non-functional program (which you don't write, it's part of the environment). One could argue that this data structure itself is an imperative program. So you're sort of doing imperative meta-programming in a functional language.

Ignoring which approach is "better", the goal in both cases is to create a separation between the functional and non-functional parts of your programs, and to limit the size of the non-functional parts as much as possible. The functional parts tend to be more reusable, testable, and easier to reason about.

0
7

Functional Programming is about limiting & isolating side-effects, not trying to get entirely rid of them... because you can't.

... and yes I find FP useful (certainly with Erlang anyways): I find it is easier to get from "idea" to "program" (or problem to solution ;)... but of course that could just be me.

2
  • I do too, I have always liked the concepts of pipelining and filtering as basic data processing functions which is a fundamental principle of functional programming in general.
    – Jeremy E
    Commented Dec 16, 2009 at 19:53
  • @Jeremy E: agreed: I come from an HW engineering background and very often I think in terms of "data flows", just like Erlang allows me to.
    – jldupont
    Commented Dec 21, 2009 at 1:08
5

The only completely pure functional language I know of is the template system in C++. Haskell takes second place by making the imperative portions of the program explicit.

In Haskell the program has mutable state, but functions (almost always) don't. You keep like 99% percent of program pure, and only the portion that interacts with the outside world is impure. Therefore when you are testing a function, you know there are no side effects. Pure core, with an impure shell.

2
  • 1
    I was starting to come to the same conclusion on my own everyone helping me clear this up.
    – Jeremy E
    Commented Dec 16, 2009 at 20:23
  • Haskell doesn't have mutable state: it "fakes" it using the definition "newtype StateT s m a = StateT {runStateT :: s -> m (a, s)}", and IO has an almost identical definition. Commented Mar 31, 2014 at 10:50
2

You need to know at least another essential concept: Monads. You will need this to do I/O and the other "useful" stuff!

2

The way Haskell does it is by using monads see wikipedia and the explanation by Haskell on their page.

Basically the idea is that you do not get rid of the IO monad. My understanding is that you are able to chain functions that unwrap an IO monad and execute that function. But you are not able to remove the IO monad altogether.

Another example using monads that is not directly tied to IO is the Maybe Monad. This monad is 'unwrappable' in contrary to the IO monad. But it is easier to explain the use of monads using the Maybe monad. Let's assume you have the following function.

wrap :: Maybe x -> (x -> y) -> Maybe y
wrap Nothing  f = Nothing
wrap (Just x) f = Just (f x)

now you can call wrap (Just 4) (5+) which will return Just 9.

The idea of the IO-monad is that you can use functions like (+5) on the internal type. The monad will assure that the functions will be called in serial, because every function is chained with the wrapping IO-monad.

2
  • 1
    That's the idea. There's a bind function/operator (>>=) that "unwraps" an IO computation and passes it to a function that returns another IO computation. Because there's no other way to "unwrap" an IO computation, you can't get rid of it. Commented Dec 16, 2009 at 18:58
  • @Ruben: 'unwrappable' => For future reference, these monads are called open monads, as opposed to IO being a closed monad. Commented Dec 16, 2009 at 19:20
1

Given that most programs have some effects on the outside world (writing to files, modifying data in a database...) programs as whole are rarely side-effect free. Outside of academic exercises, there is no point in even trying.

But programs are assembled out of building blocks (subroutine, function, method, call it what you want), and pure functions make for very well-behaved building blocks.

Most functional programming languages do not require functions to be pure, although good functional programmers will try to make as many of their functions pure as is feasible and practical, in order to reap the benefits of referential transparency.

Haskell goes further. Every part of a Haskell Programm is pure (at least in the absence of sins such as "unsafePerformIO"). All functions that you write in Haskell are pure.

Side-effects are introduced through monads. They can be used to introduce a sort of "shopping-list -- shopper"-separation. Essentially your program writes a shopping list (which is just data and can be manipulated in a pure fashion), while the language runtime interprets the shopping list and does the effectful shopping. All your code is pure and friendly to equational reasoning and such, whereas the impure code is provided by the compiler-writers.

0

Even if you don't use it in your work, learning one or more functional programming languages is a great way to learn to think differently and gives you a toolkit of alternative approaches to problems (it can also frustrate you when you can't do something as neat and clean as a functional approach in other languages).

And it made me a better at writing XSL stylesheets.

5
  • 1
    XSLT: Because Turing-complete XML is just what the world needed. Commented Dec 16, 2009 at 19:01
  • @camccann I hope you're being sarcastic. Commented Dec 16, 2009 at 19:10
  • I find Turing-complete XML to be vastly preferable to Turing-complete type generalization mechanism (c.f. C++ templates etc). That said, for angle brackets haters, there's XQuery. Commented Dec 16, 2009 at 19:14
  • Sarcastic about the world needing Turing-complete XML: Yes. Sarcastic about XSLT being Turing-complete: Sadly, no. (And don't even mention Turing-complete typesetting languages or build systems.) Commented Dec 16, 2009 at 19:18
  • 1
    @Pavel Minaev: On the other hand, back on topic, C++ templates are actually a purely functional language! Commented Dec 16, 2009 at 19:20
0

Are side-effects possible in pure functional programming?

That depends on what is meant by pure...

[...] the main problem I have is how do you do things that require side effects [...] without violating the fundamental premise of pure functional programming which is, that for a given input the output is deterministic?

...that's an interesting description: here's a similar one:

[...] the mathematical foundations of functional programming, which require that the value of a function be uniquely determined by the values of its arguments.

F. Warren Burton.,

...which he then expands upon:

Referential transparency, the property that an expression always has the same value in the same environment, is central to the mathematical foundation for functional programs.

We'll leave the choice of terms like "pure", "referentially transparent" and "side effects" for another question, instead choosing to modify the question posed here to avoid using them:

How would a program written in a functional language (a functional program) carry out practical tasks like:

  • interacting with a user,
  • communicating with a remote service,
  • handle simulating using random sampling,
  • printing out an SVG file (e.g. as a poster),
  • making scheduled backups,

...etc, while making sure that, for a given input, the output is deterministic?

Burton's solution uses what he calls pseudo-data: a supply of abstract single-use values. An initial source is then made available in the form of a suitable structured value - Burton uses a tree:

  • The original tree - passed as an argument to the running program - is divided up into subtrees, to be distributed (also as arguments to the program's functions) throughout the program;

  • From those subtrees, new abstract values are then retrieved for use by primitive functions, in which the intended effects occur.

  • Each abstract value can only be used once, so each primitive call requires another new abstract value as input - if a primitive call is somehow duplicated, the output will be the same.

In addition to providing nondeterminism, Burton briefly describes how his approach can be extended to access other system resources (specifically timestamps and spacestamps). For more information, read his paper - it's only 5 pages long...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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