Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function. The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.
Scheme is one of the few programming languages that guarantee in the spec that any implementation must provide this optimization, so here are two examples of the factorial function in Scheme:
(define (fact x)
(if (= x 0) 1
(* x (fact (- x 1)))))
(define (fact x)
(define (fact-tail x accum)
(if (= x 0) accum
(fact-tail (- x 1) (* x accum))))
(fact-tail x 1))
The first function is not tail recursive because when the recursive call is made, the function needs to keep track of the multiplication it needs to do with the result after the call returns. As such, the stack looks as follows:
(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
In contrast, the stack trace for the tail recursive factorial looks as follows:
(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6
As you can see, we only need to keep track of the same amount of data for every call to fact-tail because we are simply returning the value we get right through to the top. This means that even if I were to call (fact 1000000), I need only the same amount of space as (fact 3). This is not the case with the non-tail-recursive fact, and as such large values may cause a stack overflow.
The blog post you quoted overstates its claim a bit. FP doesn't eliminate the need for design patterns. The term "design patterns" just isn't widely used to describe the same thing in FP languages. But they exist. Functional languages have plenty of best practice rules of the form "when you encounter problem X, use code that looks like Y", which is basically what a design pattern is.
However, it's correct that most OOP-specific design patterns are pretty much irrelevant in functional languages.
I don't think it should be particularly controversial to say that design patterns in general only exist to patch up shortcomings in the language.
And if another language can solve the same problem trivially, that other language won't have need of a design pattern for it. Users of that language may not even be aware that the problem exists, because, well, it's not a problem in that language.
Here is what the Gang of Four has to say about this issue:
The choice of programming language is important because it influences one's point of view. Our patterns assume Smalltalk/C++-level language features, and that choice determines what can and cannot be implemented easily. If we assumed procedural languages, we might have included design patterns called "Inheritance", "Encapsulation," and "Polymorphism". Similarly, some of our patterns are supported directly by the less common object-oriented languages. CLOS has multi-methods, for example, which lessen the need for a pattern such as Visitor. In fact, there are enough differences between Smalltalk and C++ to mean that some patterns can be expressed more easily in one language than the other. (See Iterator for example.)
(The above is a quote from the Introduction to the Design Patterns book, page 4, paragraph 3)
The main features of functional
programming include functions as
first-class values, currying,
immutable values, etc. It doesn't seem
obvious to me that OO design patterns
are approximating any of those
features.
What is the command pattern, if not an approximation of first-class functions? :)
In an FP language, you'd simply pass a function as the argument to another function.
In an OOP language, you have to wrap up the function in a class, which you can instantiate and then pass that object to the other function. The effect is the same, but in OOP it's called a design pattern, and it takes a whole lot more code.
And what is the abstract factory pattern, if not currying? Pass parameters to a function a bit at a time, to configure what kind of value it spits out when you finally call it.
So yes, several GoF design patterns are rendered redundant in FP languages, because more powerful and easier to use alternatives exist.
But of course there are still design patterns which are not solved by FP languages. What is the FP equivalent of a singleton? (Disregarding for a moment that singletons are generally a terrible pattern to use.)
And it works both ways too. As I said, FP has its design patterns too; people just don't usually think of them as such.
But you may have run across monads. What are they, if not a design pattern for "dealing with global state"? That's a problem that's so simple in OOP languages that no equivalent design pattern exists there.
We don't need a design pattern for "increment a static variable", or "read from that socket", because it's just what you do.
Saying a monad is a design pattern is as absurd as saying the Integers with their usual operations and zero element is a design pattern. No, a monad is a mathematical pattern, not a design pattern.
In (pure) functional languages, side effects and mutable state are impossible, unless you work around it with the monad "design pattern", or any of the other methods for allowing the same thing.
Additionally, in functional languages
which support OOP (such as F# and
OCaml), it seems obvious to me that
programmers using these languages
would use the same design patterns
found available to every other OOP
language. In fact, right now I use F#
and OCaml everyday, and there are no
striking differences between the
patterns I use in these languages vs
the patterns I use when I write in
Java.
Perhaps because you're still thinking imperatively? A lot of people, after dealing with imperative languages all their lives, have a hard time giving up on that habit when they try a functional language. (I've seen some pretty funny attempts at F#, where literally every function was just a string of 'let' statements, basically as if you'd taken a C program, and replaced all semicolons with 'let'. :))
But another possibility might be that you just haven't realized that you're solving problems trivially which would require design patterns in an OOP language.
When you use currying, or pass a function as an argument to another, stop and think about how you'd do that in an OOP language.
Is there any truth to the claim that
functional programming eliminates the
need for OOP design patterns?
Yep. :)
When you work in a FP language, you no longer need the OOP-specific design patterns. But you still need some general design patterns, like MVC or other non-OOP specific stuff, and you need a couple of new FP-specific "design patterns" instead. All languages have their shortcomings, and design patterns are usually how we work around them.
Anyway, you may find it interesting to try your hand at "cleaner" FP languages, like ML (my personal favorite, at least for learning purposes), or Haskell, where you don't have the OOP crutch to fall back on when you're faced with something new.
As expected, a few people objected to my definition of design patterns as "patching up shortcomings in a language", so here's my justification:
As already said, most design patterns are specific to one programming paradigm, or sometimes even one specific language. Often, they solve problems that only exist in that paradigm (see monads for FP, or abstract factories for OOP).
Why doesn't the abstract factory pattern exist in FP? Because the problem it tries to solve does not exist there.
So, if a problem exists in OOP languages, which does not exist in FP languages, then clearly that is a shortcoming of OOP languages. The problem can be solved, but your language does not do so, but requires a bunch of boilerplate code from you to work around it. Ideally, we'd like our programming language to magically make all problems go away. Any problem that is still there is in principle a shortcoming of the language. ;)
Best Answer
An example in JavaScript
Here's an example using JavaScript. Currently, most browsers do not support tail call optimisation and therefore the following snippet will fail
Trampolines
We can work around this limitation by changing the way we write repeat, but only slightly. Instead of returning a value directly or immediately recurring, we will return one of our two trampoline types,
Bounce
orDone
. Then we will use ourtrampoline
function to handle the loop.Currying slows things down a little bit too, but we can remedy that using an auxiliary function for the recursion. This is nice too because it hides the trampoline implementation detail and does not expect the caller to bounce the return value. This runs about twice as fast as the above
repeat
Clojure-style
loop
/recur
Trampolines are nice and all but it's kind of annoying to have to have to worry about calling
trampoline
on your function's return value. We saw the alternative was to use an auxiliary helper, but c'mon that's kind of annoying, too. I'm sure some of you aren't too keen about theBounce
andDone
wrappers, too.Clojure creates a specialised trampoline interface that uses a pair of functions,
loop
andrecur
– this tandem pair lends itself to a remarkably elegant expression of a programOh and it's really fast, too
Initially this style will feel foreign, but over time I am finding it to be the most consistent while producing durable programs. Comments below help ease you into the expression-rich syntax -
The continuation monad
This is one of my favourite topics tho, so we're gonna see what this looks like with the continuation monad. Reusing
loop
andrecur
, we implement a stack-safecont
that can sequence operations usingchain
and run operation sequences usingrunCont
. Forrepeat
, this is senseless (and slow), but it's cool to see the mechanics ofcont
at work in this simple example -Y
combinatorThe Y combinator is my spirit combinator; this answer would be incomplete without giving it some place amongst the other techniques. Most implementations of the Y combinator however, are not stack-safe and will overflow if the user-supplied function recurs too many times. Since this answer is all about preserving stack-safe behaviour, of course we'll implement
Y
in a safe way – again, relying on our trusty trampoline.Y
demonstrates the ability to extend easy-to-use, stack-safe, synchronous infinite recursion without cluttering up your function.Practicality with
while
loopBut let's be honest: that's a lot of ceremony when we're overlooking one of the more obvious potential solutions: use a
for
orwhile
loop, but hide it behind a functional interfaceFor all intents and purposes, this
repeat
function works identically to the ones provided above – except this one is about one or two gadzillion times faster (with exception to theloop
/recur
solution). Heck, it's arguably a lot easier to read too.Granted, this function is perhaps a contrived example – not all recursive functions can be converted to a
for
orwhile
loop so easily, but in such a scenario where it's possible, it's probably best to just do it like this. Save the trampolines and continuations for heavy lifting when a simple loop won't do.setTimeout
is NOT a solution to the stack overflow problemOK, so it does work, but only paradoxically. If your dataset is small, you don't need
setTimeout
because there will be no stack overflow. If your dataset is large and you usesetTimeout
as a safe recursion mechanism, not only do you make it impossible to synchronously return a value from your function, it will be so F slow you won't even want to use your functionSome people have found an interview Q&A prep site that encourages this dreadful strategy
What our
repeat
would look like usingsetTimeout
– notice it's also defined in continuation passing style – ie, we must callrepeat
with a callback (k
) to get the final valueI can't stress enough how bad this is. Even
1e5
takes so long to run that I gave up trying to measure it. I'm not including this in the benchmarks below because it's just too slow to even be considered a viable approach.Promises
Promises have the ability to chain computations and are stack safe. However, achieving a stack-safe
repeat
using Promises means we'll have to give up our synchronous return value, the same way we did usingsetTimeout
. I'm providing this as a "solution" because it does solve the problem, unlikesetTimeout
, but in a way that's very simple compared to the trampoline or continuation monad. As you might imagine though, the performance is somewhat bad, but nowhere near as bad as thesetTimeout
example aboveWorth noting in this solution, the Promise implementation detail is completely hidden from the caller. A single continuation is provided as a 4th argument and its called when the computation is complete.
Benchmarks
Seriously, the
while
loop is a lot faster - like almost 100x faster (when comparing best to worst – but not including async answers:setTimeout
andPromise
)Stone Age JavaScript
The above techniques are demonstrated using newer ES6 syntaxes, but you could implement a trampoline in the earliest possible version of JavaScript – it only requires
while
and first class functionsBelow, we use stone age javascript to demonstrate infinite recursion is possible and performant without necessarily sacrificing a synchronous return value – 100,000,000 recursions in under 6 seconds - this is a dramatic difference compared to
setTimeout
which can only 1,000 recursions in the same amount of time.Non-blocking infinite recursion using stone age JavaScript
If, for some reason, you want non-blocking (asynchronous) infinite recursion, we can rely on
setTimeout
to defer a single frame at the start of the computation. This program also uses stone age javascript and computes 100,000,000 recursions in under 8 seconds, but this time in a non-blocking way.This demonstrates that there's nothing special about having a non-blocking requirement. A
while
loop and first-class functions are still the only fundamental requirement to achieve stack-safe recursion without sacrificing performanceIn a modern program, given Promises, we would substitute the
setTimeout
call for a single Promise.