8

I read "The Why of Y" from Richard P. Gabriel. It is an easy to read article about the Y combinator, which is quite rare. The article begins with the recursive definition of the factorial function:

(letrec ((f (lambda (n)
              (if (< n 2) 1 (* n (f (- n 1)))))))
  (f 10))

And explains that letrec can be defined with a side effect:

(let ((f #f))
  (set! f (lambda (n)
            (if (< n 2) 1 (* n (f (- n 1))))))
  (f 10))

And the rest of the article describes, that it is also possible to define letrec with the Y combinator:

(define (Y f)
  (let ((g (lambda (h)
             (lambda (x)
               ((f (h h)) x)))))
    (g g)))

(let ((f (Y (lambda (fact)
              (lambda (n)
                (if (< n 2) 1 (* n (fact (- n 1)))))))))
  (f 10))

Obviously this is much more complicated than the version with the side effect. The reason why it is beneficial to prefer the Y combinator over the side effect is given just by the statement:

It is easier to reason about programming languages and programs that have no side effects.

This is not explained any further. I try to find an explanation.

  • That "easier to reason about" line is pure propaganda. It's always given as an article of faith--no evidence is needed nor offered--and when critically analyzed it doesn't even pass the laugh test. As you noted, it's trivially obvious that the Y Combinator version is more than twice as complicated, and thus harder to understand and reason about! – Mason Wheeler Dec 15 '16 at 16:23
  • 5
    @MasonWheeler Passing a mutable object to several methods makes it difficult to tell where it's being used purely as input and where it's being mutated in place. The functional alternative - returning a new copy of the object - makes it clear. I'm not going to say pure is always better, but it's difficult to claim that large graphs of mutable objects are easy to reason about. There's too much invisible context involved. – Doval Dec 15 '16 at 16:40
  • @Doval How is it "made clear" when you now have multiple copies of your objects running around, some of which are obsolete, others canonical, and now you have to keep that straight? That sounds even more confusing! (Or, alternatively, you must ensure that there are no references to any secondary copies, which is a task exactly equivalent to manual memory management, which FP found soooooo confusing and hard to reason about that it invented garbage collection in order to avoid the need to do so!) – Mason Wheeler Dec 15 '16 at 17:55
  • 2
    @MasonWheeler Even when the data is supposed to change, you want to be in control of who's changing it. You want to pass it to a method that's not supposed to mutate it, but someone could screw up and introduce a bug that ends up mutating the data anyways. Then you end up making "defensive copies" (which is actually a recommendation in the Effective Java book!) and doing more work/generating more garbage than using an immutable data structure from the beginning. The fact that the data is going to change never got in the way of anyone using immutable string or numeric types. – Doval Dec 15 '16 at 21:40
  • 2
    @MasonWheeler FP languages do not generate lots of garbage, otherwise they'd be useless. That's not how they work "behind the scenes". The "easier to reason about" usually refers to equational reasoning, which is no laughing matter. Equational reasoning can be done in many paradigms, with varying success, but in FP languages it's usually easier, and that's a huge win (though at the cost of other things; everything is a trade-off in life). – Andres F. Jan 20 '17 at 22:44
13
+50

Obviously, you can find examples of incredibly difficult to read pure functions that perform the same calculations as functions with side effects that are much easier to read. Especially when you use a mechanical transformation like a Y-combinator to arrive at a solution. That's not what is meant by "easier to reason about."

The reason it's easier to reason about functions without side effects is you only have to concern yourself with the inputs and outputs. With side effects, you also have to worry about how many times functions are called, what order they are called in, what data is created within the function, what data is shared, and what data is copied. And all that information for any functions that may be called internal to the function you're calling, and recursively internal to those functions, and so forth.

This effect is a lot easier to see in production code with several layers than in toy example functions. Mostly it means you can rely much more on just a function's type signature. You really notice the burden of side effects if you do pure functional programming for a while then come back to it.

10

An interesting property of languages without side-effects is that introducing parallelism, concurrency, or asynchrony cannot change the meaning of the program. It can make it faster. Or it can make it slower. But it can't make it wrong.

This makes it trivial to automatically parallelize programs. So trivial, in fact, that you usually end up with too much parallelism! The GHC team experimented with automatic parallelization. They found that even simple programs could be decomposed into hundreds, even thousands of threads. The overhead of all those threads will overwhelm any potential speedup by several orders of magnitude.

So, for automatic parallelization of functional programs, the problem becomes "how do you group small atomic operations together into useful sizes of parallel pieces", as opposed to impure programs, where the problem is "how do you break up large monolithic operations into useful sizes of parallel pieces". The nice thing about this is that the former can be done heuristically (remember: if you get it wrong, the worst thing that can happen is that the program runs slightly slower than it could be), whereas the latter is equivalent to solving the Halting Problem (in the general case), and if you get it wrong, your program will simply crash (if you're lucky!) or return subtly wrong results (in the worst case).

  • it could also deadlock or livelock, not that either is any better... – Deduplicator Jan 25 '17 at 18:22
6

Languages with side effects employ aliasing analysis to see if a memory location might possibly need to be reloaded after a function call. How conservative this analysis is depends on the language.

For C, this has to be pretty conservative, as the language isn't type safe.

For Java and C# these don't have to be as conservative because of their increased type safety.

Being overly conservative prevents load optimizations.

Such analysis would be unnecessary (or trivial depending on how you look at it) in a language without side effects.

  • Note that aliasing is only possible with both mutable variables and references. A language with only one or the other does not have this problem – gardenhead Jan 20 '17 at 22:44
4

There's always optimizations to take advantage of whatever assumptions you give. Reordering operations comes to mind.

One amusing example that comes to mind actually shows up in some older assembly languages. In particular MIPS had a rule that the instruction after a conditional jump was executed, regardless of which branch was taken. If you didn't want this, you put a NOP after the jump. This was done due to the way the MIPS pipeline was structured. There was a natural 1 cycle stall built into the conditional jump execution, so you might as well do something useful with that cycle!

Compilers would often look for an operation which needs to be performed on both branches and slide it into that slot, to eek out a little more performance. However, if a compiler can't do that, but can show that there were no side effects to the operation, the compiler could opportunistically stick it into that spot. Thus, on one path, the code would execute one instruction faster. On the other path, no harm done.

1

"letrec can be defined with a side effect ..." I see no side effect in your definition. Yes, it uses set! which is a typical way of producing side-effects in Scheme, but in this case there is no side effect -- because f is purely local, it cannot be referenced by any function other than locally. It is therefore not a side effect as seen from any external scope. What this code does do is hack around a limitation in the scoping of Scheme which by default does not allow a lambda definition refer to itself.

Some other languages have declarations where an expression used to produce the value for a constant can refer to the constant itself. In such a language, the exact equivalent definition can be used, but clearly this does not produce a side effect, as only a constant is used. See, for example, this equivalent Haskell program:

let f = \ n -> if n < 2 
                 then 1 
                 else n*(f (n-1)) 
        in (f 5)

(which evaluates to 120).

This clearly has no side effects (as in order for a function in Haskell to have a side effect, it must return its result wrapped in a Monad, but the type returned here is a plain numeric type), but is structurally identical code to the code you quote.

  • In general it is a side effect, because let could return the local function. – ceving Dec 15 '16 at 16:36
  • 2
    @ceving - even then, it isn't a side effect, because the modification of the storage location is limited in the time it can occur in to a time before any other code is able to read it. In order for a side effect to be real, it must be possible for some external agent to notice that it has happened; in this case, there is no possible way for that to happen. – Periata Breatta Dec 16 '16 at 16:12
0

This is not explained any further. I try to find an explanation.

It's something that's inherent to many of us who have debugged massive codebases but you have to deal with a large enough scale at the overseer level for a long enough time to appreciate it. It's like understanding the importance of being in position in Poker. Initially it doesn't seem like such a useful advantage to go last at the end of every turn until you record a hand history of a million hands and realize that you won so much more money in position than out.

That said, I disagree with the idea that a change to a local variable is a side effect. From my view, a function does not cause side effects if it does not modify anything outside of its scope, that anything it touches and tampers with is not going to affect anything below the call stack or any memory or resource the function did not acquire itself.

In general the hardest thing to reason about in a complex, large-scale codebase that doesn't have the most perfect testing procedure imaginable is persistent state management, like all the changes to granular objects in a video game world as you wade through tens of thousands of functions while trying to narrow down among an endless list of suspects which one actually caused a system-wide invariant to be violated ("this should never happen, who did it?"). If nothing is ever changed outside of a function , then it can't possibly cause a central malfunction.

Of course this isn't possible to do in all cases. Any application that updates a database stored on a different machine is, by nature, designed to cause side effects, as well as any application designed to load and write files. But there's a whole lot more we can be doing without side effects in many functions and many programs if, for example, we had a rich library of immutable data structures and embraced this mindset further.

Funnily enough John Carmack has jumped on the LISP and immutability bandwagon in spite of starting in the days of the most micro-tuned C coding. I have found myself doing a similar thing, though I still use C a lot. Such is the nature of pragmatists, I think, who have spent years of debugging and trying to reason about complex, large-scale systems as a whole from an overseer level. Even ones that are surprisingly robust and devoid to a large extent of bugs can still leave you with an uneasy feeling that something wrong is lurking around the corner if there's a lot of complex persistent state being modified among the most complex interconnected graph of function calls among the millions of lines of code. Even if every single interface is tested with a unit test and all pass, there's also the uneasy feeling of what might happen to the central states with an unanticipated input case with all the countlessl interdependent function calls between interfaces if the application's logic revolves around cascading side effects to the most central and persistent states.

In practice I often find functional programming makes it more difficult to comprehend a function. It still spins my brain into twists and knots, especially with complex recursive logic. But all the intellectual overhead associated with figuring out a couple of functions written in a functional language is dwarfed by that of a complex system with persistent states being changed across tens of thousands of functions, where each function that causes side effects adds up to the total complexity of reasoning about the entire system's correctness as a whole.

Note that you don't need a pure functional language to make functions avoid side effects. Local states changed in a function don't count as a side effect, like a for loop counter variable local to a function doesn't count as a side effect. I even write C code nowadays with the aim of avoiding side effects when possible and have devised myself a library of immutable, thread-safe data structures that can be partially modified while the rest of the data is shallow copied, and it has helped me a great deal to reason about my system's correctness. I strongly disagree with the author in that sense. At least in C and C++ in mission-critical software, a function can be documenting as having no side effects if it doesn't touch anything that could possibly affect the world outside of the function.

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.