Even pure functions have side-effects | Hacker News Reader

Even pure functions have side-effects

johndcook.com

53 pointsColinWright16 comments

Wow. The argument in the original post that is linked to about scalability and functional programming is almost exactly backwards. Resource usage here is a silly red herring.

Keeping code free of side effects means you _can_ scale it. Try scaling out to multiple machines when you have a fundamental bottleneck like serialized state in your code.

All data-parallel programming techniques, dating back from at least 1985 with the connection machine lisp, and whose modern friends include MapReduce, come from unshackling ourselves from too much state.

These benefits come from making software more functional, not less functional.

A (pure) function is a mathematical concept. Saying a pure function can have side effects is like saying a line has a thickness because no one can draw a line with no thickness.

TL:DR; Pure functions still use memory and CPU.

Very insightful. I forgot code ran.

And indeed, FP hackers do mind their pure functions' performance:

- http://haskell.org/haskellwiki/The_Fibonacci_sequence

- http://vimeo.com/20655874 ("Faster persistent data structures through hashing")

Mock him if you like, but he puts his finger on a real problem. When I encounter a library or language that makes a big deal about being "declarative", I now consider that a black mark against it, not a feature, because what that translates to is usually "You still have to tell it how to get the thing you want, but since we thought we could abstract away all such performance issues, we've made it impossible to introspect or fix any performance issues you may encounter, and the language will require bizarre contortions to get acceptable performance."

Example the first and one of the biggest: SQL. Sure, it's a declarative language... after you learn how databases work, after you learn how indexes work, after you profile your biggest hitting queries and work out how to rewrite them into semantically equivalent queries that perform orders of magnitude faster, after you learn how to deal with sharding, after you learn when to denormalize and when not to, after you learn the necessary performance hacks that trick the indexer into doing what you need instead of what it thinks is correct, and after a few more things I could go on about, it's a declarative language where you don't have to worry about performance any more. Yup, totally declarative.

I like Haskell, but only because I can mostly (although not entirely) see through it.

"The major difference between a thing that might go wrong and a thing that cannot possibly go wrong is that when a thing that cannot possibly go wrong goes wrong, it usually turns out to be impossible to get at and repair." - Douglas Adams

Anything that claims to be declarative is lying. All declarations in some given environment entail some process that will be used to obtain your results, you will not be able to get good performance if you don't know that process, and actively obscuring those processes only makes it harder.

You can't afford to ignore the side effects of "pure" functions.

In the same vane, is the classic article [Evolution of a Haskell programmer](http://www.willamette.edu/~fruehr/haskell/evolution.html). Its just the factorial function written in different styles in Haskell, each with very different performance implications.

What does the literature say about a pure function that throws an exception? For example, what of an asynchronous exception like out-of-memory or stack?

I don't think pure functions are supposed to throw exceptions, instead they should return error values.

Yes, but they usually use some form of monad to hold either an exception or a value.

The implementation of >>= (haskell calls it bind, buts it's useful to think of it like an overloaded ";" that takes a continuation as a parameter ) examines the return value and decided wether to run the normal path or the exception path...

It doesn't quite perform the same as exceptions do (it burdens both paths with if checks, whereas imperative exceptions only burden the error path)

But the code you write looks almost identical to exception handling code. It doesn't look like something using if checks.

The Maybe and Either type classes are typically used to model exceptions in Haskell.

There's actually some discussion about how to handle errors in Haskell. See: http://blog.ezyang.com/2011/08/8-ways-to-report-errors-in-ha...

An exception is simply a change in control flow and, if I'm not mistaken, this can be modeled easily in a purely functional system. I imagine a real system like Scheme, Racket, etc. would use call/cc, but I can best explain this with Continuation Passing Style[1].

Suppose you have some function like:

  (define (foo x y)
    (+ (/ x y) 1))

And you call it:

  > (* (foo 4 2) 3)
  9

the previous expression is equivalent to: ((4 / 2) + 1) * 3.

Now, suppose instead you call it with a bogus argument:

  > (* (foo 4 0) 3)
  Error: / expects the second argument to be non-zero!

Obviously, an error must be thrown because there is no reasonable answer to the quotient of 4/0.

Now, let me introduce CPS. To evaluate (+ (/ 4 2) 1) we must first evaluate (/ 4 2), then we can add 1 to the result. Written in a Scheme/Lisp language this looks like:

  (let ((result (/ 4 2)))
    (+ result 1))

The body of this let form is the "continuation" of (/ 4 2), which is a fancy way of saying it's what we should do next. One of the neat things about Scheme/Lisp is that we can write let expressions as function applications, like this:

  ((lambda (result) (+ result 1)) (/ 4 2))

So now we have a function which represents what we should do when we're done with (/ 4 2).

  k := (lambda (result) (+ result 1)) ; continuations are often called k

Now we are ready to add real power. Let us modify our call to foo as follows:

  ((lambda (result) (* result 3)) (foo 4 2))

But, why not let foo decide its own future by passing the continuation as an argument which foo can decide to use, or not!

  (foo 4 2 (lambda (result) (* result 3)))

Now, foo can say "Hey, I'm all done, I'm gonna call my continuation and keep evaluating!", or foo can say "No way man, shit hit the fan, we cannot continue evaluating!" This is how foo can be given that behavior:

  (define (foo x y k)
    (if (zero? y)
        "Uh-oh, you gave me a divisor of zero. I don't know what happens in black holes!"
        (k (+ (/ x y) 1))) ; I'll divide, then add, then give the result to my continuation

Furthermore, primitive operations like /, +, and * can be also be modified to accept continuations so the final program looks like:

  (define (foo x y k)
    (if (zero? y)
        "Uh-oh, you gave me a divisor of zero. I don't know what happens in black holes!"
        (/ x y (lambda (quotient)
                 (+ quotient 1 k)))))

  > (foo 4 2 (lambda (result) (* result 3)))
  9
  > (foo 4 0 (lambda (result) (* result 3)))
  "Uh-oh, you gave me a divisor of zero. I don't know what happens in black holes!"

I encourage you to experiment with turning simple arithmetic programs into CPS-style. It's really enlightening and let's you experiment with highly abnormal control flow (much more than just implementing exceptions). In Scheme, Racket, and languages like them, you can use call/cc and let/cc to have access to continuations without this laborious rewriting process. In fact, continuations are used to model the interactions of a web server written in Racket[2].

TL;DR: Exceptions can be modeled in a completely functional way, and the manner in which you do this opens up a really cool world of control flow mucking.

[1] http://en.wikipedia.org/wiki/Continuation-passing_style

[2] http://pre.racket-lang.org/docs/html/more/index.html#(part._...

edit: added a TL;DR and a reference to Racket's example of applying continuations to web server interactions

edit2: formatting

Synchronous exceptions are debatable. For example, a library function throwing an exception may require its callers to use "finally" clauses (or similar constructs in other languages) in order to maintain Exception Safety.

Also, a common property of "pure" functions is that it doesn't matter what order you call them in. But if you reorder calls to functions which can throw exceptions, you may get different results.

Asynchronous exceptions on the other hand are usually fine. For example, square-root library library functions aren't defined in terms of how much stack space is available on the machine; they're defined in terms of their argument.

Systems which have asynchronous exceptions ideally permit programs to handle them with code at carefully chosen places, rather than code spread around everywhere.

The main thing a statically typed pure functional language tries to do is force you to "mark" the side effect in your code with type annotations. Various effects can be modeled with different types. Many of these types still support some form of composability, which promotes modularity--a major goal of functional programming.

Whether every effect can and should be modeled in this way seems to be an open question that depends on the semantics you wish to apply to your programming language.

Anybody know what presentation software the guy in the PyCon talk was using? That looked pretty slick.

Looks like Prezi http://prezi.com/

Reply on news.ycombinator.com