Functional Light JavaScript, v3
Link to the course exercise files
Introduction
Introduction
This workshop will cover a ‘style’ of functional programming that the instructor, Kyle Simpson, has developed; Functional-Light JS. You can also read Kyle’s book of the same name here. ‘Light’ is not intended to allude to the depth or level of difficulty of this workshop, rather ‘Light’ refers to the workshops’ intention to not weigh you down with terminology or mathematic notation. This workshop will take a ‘bottom-up’ approach to Functional Programming in JavaScript, an approach that does not make the assumption that you have a background in mathematics or knowledge of specific terminology.
Why Functional Programming
One of the biggest reasons to learn functional programming is because it is, in Kyle’s opinion, impossible to write functional programming in isolation. Meaning that if you bring these concepts back to work and write some code in a functional programming style, submit a pull request, that it is then somehow magically going to now be the way that your team writes code. Nope… It is important to learn functional programming so that you can convince others of its importance.
Functional programming is not imperative, it is declarative. An imperative approach is one that is primarily focused on how to do something; i.e. add a bunch of numbers from an array and return the result, would probably lead you to having an accumulator variable and a for loop to loop over the array and add each number in the array to the accumulator variable. But this is an imperative approach because a future reader of your code would have to read all of your code to understand what is happening. This is fine. but the being that benefits most from imperative code is the computer, not the human. A declarative approach focuses on the what, the outcome; which should, by its very nature, make your code inherently more obvious as to what its purpose is and what it does. Functional programming != declarative, but it is more declarative than it is imperative.
Functional Programming Journey
The instructor, and maybe you or myself?, admits to starting off with somewhat readable but imperative (non-functional) code which evolved to less readable but closer to declarative code, finally ending up at highly readable and functional code. He points out that in the middle of that journey is where most people ‘drop-off’ from continuing to pursue functional programming. The ‘pit of despair’ is that point when most people ‘drop-off’ from continuing to pursue functional programming and the instructor admits he hit this point, but stresses the importance of continuing on, of continuing to pursue ones understanding of functional programming. Small wins will turn into bigger wins will turn into something that is greater than no understanding whatsoever of functional programming. The important thing is to keep at it!
No one can remove the fact that functional programming is difficult, but an aim of this course is to make it approachable and more manageable. It will be important for you to find comfort in the unfamiliar and keep the faith when your code becomes less readable on your functional programming journey, when you learn a new concept or approach this is how it will be at first, but it is important to trust the process of learning and know that at some point you will understand what you are doing and your code will become more readable.
Code is Provable
Functional programming is based on mathematical principles. It is likely that we’ve all written code that did not pass a test and then we fumble through trying to figure out how to get whatever we’re working on to pass the test. But what would it be like if when you wrote some code that you were then going to test that you were 100% certain of the outcome? Would that fact make you a more effective programmer? Would you have more confidence? Would you drop your sense of being an imposter?! The set of techniques associated with functional programming are not just a nicely designed API, they are about using mathematical principles, in a mathematically sound way, that just so happens to look like programming and happens to let us solve programming problems. An overarching goal [of functional programming] is to reduce the cognitive overhead, to rely on mathematical principles, to produce code that requires less reading; code that is easier to understand, which frees us up to focus on the important pieces with far less guesswork.
Course Overview
- Functions - because… in functional programming it is important to understand what a function is and what a function is is probably not what you think it is.
- Closure - you do not understand the entirety of functional programming if you do not understand closure. We will understand it.
- Composition - the way that data flows and is mapped through applications.
- Immutability - how we manage the changes to values and state over time. Management of state change is one of the fundamentals of almost all programming.
- Recursion - an incredibly useful too, especially in functional programming.
- Lists / Data Structures - map, filter, reduce… this is what everybody calls functional programming, but with the other sections, these functions are only part of functional programming, not the entirety of what it is.
- Async - the act of applying functional principles over time… aka asynchronous functional programming.
- FP Libraries - a look at some of the libraries available in the wild to use in projects that will help you get the most out of functional programming.
Function Purity
Functions vs Procedures
What is a function? Let’s start with this inflammatory statement: “Functional programming is not all about the function keyword”. Consider the following:
Is addNumbers
a function? What about extraNumbers
? Are either of them functions? If they are not functions, why not?
addNumbers
clearly takes some inputs (x, y, z, w
) and it clearly does something with those inputs, so it is at least kind of like a function, right? Nope. The bar for being a function is a bit higher than that. So… what is it then? The best term that we could use to describe addNumbers
is that it is a ‘procedure’. A procedure is a collection of operations, a collection of things that you need to do in a program. Just because it uses the function keyword does not make it a function. Procedures can take inputs, they can return outputs, they can print to the console, they can be called multiple times. There are a lot of benefits to procedures, but this course is not about procedural programming (yes, its a thing).
Wonderful, but… what is a function? To start, a function not only has to take some input, it also has to return some output. Not just print something to the console, if it does not have the return
keyword, it is most definitely not a function! So any ‘function’ that does not have a return
keyword is a procedure and a function is more than what we’ve covered so far, we will expand on what a function is as we move through this workshop. Oooook, so addNumbers
isn’t a function, it’s a procedure. What about extraNumbers
? extraNumbers
has a return
keyword! extraNumbers
is function? 😞 No.
extraNumbers
is not a function, because; expanding on the definition of what a function is, a function can only call other functions. Functions cannot call procedures (addNumbers
), if they do, they themselves become procedures. Number one in functional programming is that you can’t do functional programming with a thing that is not a function; it has to be a function for you to take advantage of functional principles. So, neither addNumbers
nor extraNumbers
qualify as functions because they both violate what we have so far learned about what a function is. They are procedures.
How about this:
In JavaScript, a tuple is basically two values in an array. The function tuple
has inputs, uses the return
keyword to return outputs, it is a function?
Function Naming Semantics
Long story short, yes, tuple
was a function. But if you took that tuple
function and it required the inputs x
and y
, but instead of returning those as outputs returned the number 40, would it still be a function? Not really. To better understand what makes a function a function, lets look at some maths:
f(x) = 2x2 + 3
The above might look familiar from some math you may have learned in (not college) school and, unless you were using a graphing calculator, you may recall not really understanding that math in any real concrete sense. The reality of the math above is that you are taking an input value, x, putting it into a function x
. The output value will be the y
coordinate, when you combine x
with y
, you will see a ‘u’ shape on a graph! Uh huh… But what is a function? A function is a relationship between the input and the output. If you were to write the above maths as a JavaScript function, it might look something like this:
In functional programming, it matters that there is an obvious relationship between the input and output of a function. Again, a function is the semantic relationship between input and computed output. Here’s another example:
Side Effects
In functional programming there should not be any side effects in functions. But what is meant by side effects? Indirect inputs or outputs. Like this:
The above code has no direct relationship between the input and output values, and therefore is not considered a function. If however, we made some changes and made the code look like this:
Now in the above code, the (direct) relationship between the input and output values has been created and this qualifies as a function? Yes! The important thing to consider when talking about whether or not a function is a function is to look at where was the function called, which needs to avoid creating or using side effects. But w hat really are the side effects that we need to be concerned about?
- I/O (console, files, etc) - Any logs or something dealing with files are considered side effects on the system
- Database Storage
- Network Calls
- Reading from / Writing to the DOM
- Timestamps
- Generating a Random Number
- CPU Heat? - Any program will cause a CPU to compute which in turn will cause it to generate heat which is a side effect
- CPU Time Delay
Not only is it impractical to avoid all side effects, but it is theoretically impossible to avoid all side effects. So really, what is meant when it is suggested to avoid side effects is to minimize them. A program with no side effects would be no different than if the program did not exist at all, you couldn’t even prove it existed! The necessity of side effects is undeniable, but we need to make certain that we are as intentional as possible about them and make them obvious.
Pure Functions & Constants
Continuing to build on our definition of what a function in functional programming is, a ‘pure function’ is one that takes direct inputs and provides direct outputs and has no side effects. Also, as mentioned previously, it is where the function is called that will be the determining factor as to whether or not the function is a function and whether or not it is pure. Consider this code:
Because addAnother
relies on z
, which would be a value that is potentially unknown at the time of the function call, it is considered impure. But what if the code looked like this:
Now, z
is defined as a const
and we could surmise that its value would not change throughout the life of the program, is that valid? Well, it is still consistent with functional principles. But what if you used var
instead of const
? Would that invalidate the above code as being in line with functional programming? No, var
or const
the above code would still be following / consistent with functional principles. The reason being that in the above code block, z
is never being reassigned and is therefore serving the purpose of a constant value in the application. If you are using something as a constant in your program, it is best to make it as obvious as possible that is what you are doing. It is important for the reader of our code, yes even if that person is ourselves, to know that they do not need to worry whether something will change, this improves code readability.
Reducing Surface Area
Now the codes ‘surface area’ has been reduced. There are only 2 possible places where the value of z
could be reassigned (inside of the addAnother function before the return statement, and inside of the addTwo function also before the return statement). This should have the effect on the reader of making them confident that when they pass a value into the addAnother
function it will stay the same as the value they passed in. The constant nature of the z
variable is happening via closure. The above code is both a pure function and a pure function call; they both have predictability which is needed and expected out of pure functions.
Same Input, Same Output
What about this code?
Would you consider getId
to be a pure function in the sense that if passed the same object it would always return the same id? What if there was more to the program and it looked like this:
With the revised code, your confidence level of whether you would get the same id from passing in the same object should have gone to zero. In determining whether or not a function is pure, it is important to see all relevant parts of the program. The more that you can use the techniques outlined in this workshop, to reduce the surface area of where non-functional things can occur, the easier it will be for somebody to read, understand, and ultimately rely upon. We want all readers of our code, again including our future selves, to know from reading our code that they can ‘trust’ it. Pure function calls act in isolation. i.e given the same inputs they should always produce the same output. A pure function is one that whenever it is executed with the same input, it will always give the same output. The goal in functional programming is to design our functions so that as many of the functions as possible will always return the same output when provided the same input, i.e. pure functions.
Level of Confidence
The point of function purity in JavaScript is; how confident are we, the reader, in any given functions behavior? When asked whether or not a function is pure, a binary answer of yes or no will not suffice. The question is not a yes or no question, but one of level of confidence. Something along the lines of “I have a high level of confidence that this function will behave pure” or “I have a low level of confidence that this is a pure function” is more appropriate. The goal being to shift the balance of confidence, as much as possible, to a high degree of confidence in the purity of our functions. And remember that the determining factor, in JavaScript, of whether or not a function behaves pure is at the function call, not the function definition.
Extracting Impurity
If a function is not pure for whatever reason, what are our options? An obvious option would be to leave it as it is; i.e. maybe it must write to a database, this is a side effect and an impurity, but sometimes it has to happen. What you can do is make it obvious that the procedure will have side effects; name it in a way that conveys this, add a comment. The reason for being obvious is to make it easier to maintain the code. Another option would be to look at any given impure function and ask: Is there some way for me to rearrange the way this function works and extract out the impurity, leaving just a pure function in place? This does not mean to remove the impure functionality from your application, but to put the impurity in a place that makes it more obvious. Here is some code to look over:
In the above code block, both the function definition and the function call are impure as the function definition will modify the DOM when called, and the function call… modifies the DOM. An additional side effect above is the id being generated by uniqueID()
. Is it possible to extract the impurities? We could change it to look like this:
The above does not get rid of any side effects, but extracts them to leave a pure function whenever possible.
Containing Impurity
If you cannot extract impurities, another way to handle impurities is to contain them. The goal here is not to have no impurity, but to handle impurity so that it does not have any effect on other parts of the application. If you can reduce the surface area of impurities, this will make your codebase more manageable. Looking at the following code, try to identify impurities and consider how to better contain them:
In the above code, insertSortedDesc
modifies the global numbers
variable. How could that function be modified to contain the impurity? Wrap it in another function!
Now that insertSortedDesc
is wrapped in getSortedNums
, the numbers
variable is restricted to the function scope of getSortedNums
. The side effect of modifying the numbers
array still exists, but it is now contained within a function scope instead of global scope, effectively reducing the impurities surface area. But there is still one additional impurity… SomeAPI.threshold = v;
is modifying the value of threshold
in the SomeAPI
object. How can that be contained? We likely cannot wrap it in another function because this is likely a third-parties API service who’s code we do not have access to modify. Containment of this impurity might look like this:
The above code is a very ‘brute force’ way of dealing with side effects which would get very unmanageable very quickly, especially if we were dealing with a more complex set of state; i.e. the DOM. Capturing the current state of the DOM, modifying it, then resetting it is very hard. Same for a database. Again, all of this is just an attempt to reduce the surface area of side effects, ideally improving code readability and maintainability.
Impurity Exercise: Wrappers & Adapters
Instructions:
This is a two-part exercise to practice two techniques for containing function impurity.
Instructions (Part 1)
In this part of the exercise, you will contain the function impurity of sortStudentsByName(..)
using a wrapper function.
NOTE: Do not modify the contents of sortStudentsByName(..)
for this exercise.
-
Move and modify
getStudentsByName(..)
so that it wraps aroundsortStudentsByName(..)
(and calls it internally). -
getStudentsByName(..)
should receive the current list of students, and return a new sorted list of students. -
Make sure that calling
getStudentsByName(..)
doesn’t have a side-effect of modifying the globalstudents
array. -
The
studentsTest1
andstudentsTest3
tests at the bottom of the exercise should all printtrue
.
Instructions (Part 2)
In this part of the exercise, you will contain the function impurity of sortStudentsByID(..)
using an adapter function.
NOTE: Do not modify the contents of sortStudentsByID(..)
for this exercise.
-
Modify
getStudentsByID(..)
so that it is an adapter that callssortStudentsByID(..)
. -
getStudentByID(..)
should receive the current list of students, and return a new sorted list of students. -
Make sure that calling
getStudentsByID(..)
doesn’t have a side-effect of modifying the globalstudents
array. -
All tests (
studentsTest1
,studentsTest2
, andstudentsTest3
) at the bottom of the exercise should all printtrue
.
Code to work from:
Impurity Solution: Wrappers
Click to view the solution
Impurity Solution: Adapters
Click to view the solution
Argument Adapters
Function Arguments
Shifting from to the arguments that functions receive. Parameter and argument are generally used interchangeably, but they are technically different. The generally accepted definition is that a parameter is the ‘thing’ in the function definition and an argument is the value that gets passed in when you call the function. Put more simply, arguments get assigned to parameters. And to throw some confusion in there, both parameters and arguments can be considered inputs. Here’s some code to look at:
Throughout the remainder of this course, the instructor will be describing the ‘shape’ of functions which will speak to the number and kinds of things that get passed into and returned from functions. In the above code block, the ‘shape’ of the two functions is described in the comment above each of the respective function definitions; unary and binary. The shape of a function is quite critical and functional programmers are obsessed with the shape of functions. For functions that we create, it is important to be cognizant of their shape; what arguments will they receive, what will they return. Functional programmers tend to prefer unary functions; those with a single input and a single output, followed by binary functions; two inputs, single output. The more inputs a function has, the harder it is to make it work with other functions, the harder it is to get the shapes to fit.
Arguments Shape Adapters
We can adapt the shape of functions, have a look at this code:
Let’s talk about higher order functions. A higher order function is a function that either receives, as its inputs, one or more functions, and/or returns one or more functions. In the above code, the variables g
and h
are creating copies of the unary
and binary
functions respectively, with the function definition f
being passed in as an argument. So, when g(1, 2, 3, 4)
is called, it only returns the first number in the supplied arguments, effectively limiting, or adapting, the shape of f
to the definition of unary
; only takes (and returns) a single argument. Adapter and higher order functions are at the core of functional programming.
Flip & Reverse Adapter
Let’s look at a couple of adapter functions; flip and reverse. Starting with flip
:
flip
is a function that…flips the order of some of the supplied arguments; in the above example, flip
flips the first two of the supplied arguments. flip
is a common method that you might find in utility libraries. A somewhat less common example that you may come across is a reverse arguments method. That looks something like this:
This may not be a situation you come across, but the above will reverse the supplied arguments that are passed in. When you find yourself struggling to ‘fit’ together functions that have different shapes, can you refactor the functions to make them better fit one another or do you need to write an adapter function to make them fit? While it is possible to make a variety of utility functions to modify the shape of other functions, it is best practice to try and write your functions as close to a familiar functional programming approach as possible so that it is familiar at a glance without some reader of your code having to trace all of the transformations and shape changes.
Spread Adapter
Another of shape adaptation that commonly occurs in functional programming is having a function that takes numerous individual arguments, but you want to call that function with an array. To do this, we can use the spread operator:
The spread operator is the same as JavaScript’s .apply
method; it ‘spreads’ the array out so that each value becomes it’s own value, separate from the array.
Point Free
Equational Reasoning
What is point-free? Point-free is a way of defining a function without actually writing anything in the function; a way of making a function by making it with other functions. More specifically, point-free is a way of defining a function without needing to define its ‘points’, aka, its inputs. Check out this code:
The above code has a callback passed in onPerson
which passed on the person
input to another function, in the above case; renderPerson
. The input, person
, is the ‘point’. What if you could define the onPerson
function without needing to list the ‘point’ at all? Since onPerson
and renderPerson
have the same ‘shape’, you could just pass renderPerson
as the argument to getPerson
; i.e.
Doing the above is called equational reasoning. Equational reasoning means reason about this thing and say that it is equationally, not equal in the identity sense, but equal in the shape sense with another thing. Equational reasoning is just one aspect of the ‘family’ called point-free, and in the next few sections it might become increasingly difficult to follow, but don’t despair. Try the things and they will become more familiar and easier to understand. Once you do understand how to implement point-free, try not to go overboard, it can have the unintended side-effect of making your code less readable which is not the point of functional programming.
Point Free Refactor
Our goal is to make the shape of our functions similar, let’s look at some code:
In the above code, isEven
is defined in terms of isOdd
, specifically checking whether v % 2 == 1
returns false. This is beneficial for the sake of readability and to create the relationship between the isOdd
and isEven
function definitions. Going further, would it be possible to define isEven
in a point-free way? Before we do that, what even is the point of point-free? Point-free moves us closer to a declarative style of code. The approach we are going to take is to implement another Higher Order Function (HOF) as we had done in a previous section. Like so:
The refactored code makes more obvious the relationship between isEven
and isOdd
which arguably improves readability in the code.
Point Free Exercise
This is an exercise to practice point-free style.
Instructions
-
Refactor the
output(..)
,printIf(..)
, andisLongEnough(..)
functions to use point-free style. -
Hints:
- Some browsers require
console.log(..)
to run against theconsole
context , sof = console.log; f(..)
fails (because of lostthis
binding).
- Some browsers require
Use .bind(..)
to be safe.
printIf(..)
can be expressed in terms of awhen(..)
that looks like:
isLongEnough(..)
is the negation ofisShortEnough(..)
.
Code:
Point Free Solution
Click to view the solution
Advanced Point Free
We’ll cover these advanced point-free techniques later in this workshop, but here is a preview:
The above methods are something that you could find in a functional programming utility library, but we’ll break them down. Both the mod
and eq
functions take two arguments, first y
, then x
. This might seem strange, but it makes them more predictable. In functional programming, the order of parameters is important and should be considered. Adding on to the above code, let’s stub out an isOdd
function that uses both mod
and eq
:
In the above code, specifically in the isOdd
function definition, you may notice that the return value of executing mod2
is immediately passed in to eq1
, this is known as composition. Now let’s make isOdd
into a point-free function:
We’ve added a compose
function which will compose two functions for us, but there is still an additional measure we could take to make our code more implicit and get rid of the var mod2
var eq1
variables:
All of this was achieved using equational reasoning which is the core of being able to do point-free style code. This may feel way too advanced and more confusing that helpful, but the point is exposure and the real understanding and comfort with this paradigm will come from practice and from being able to speak to your code which will reinforce your knowledge and comfort level.
Closure
Closure
We’ve already used/seen closure a few times in this workshop, but let’s get a definition for exactly what closure is. It is virtually impossible to be any good at functional programming without a solid understanding of what closure is.
Closure is when a function “remembers” the variables around it even when that function is executed elsewhere.
Here is an example of closure:
The example above clearly illustrates closure, but when c
is set to makeCounter
than repeatedly called, are the function calls; c()
, pure function calls? Nope. Every time c()
is called, it returns a different value. The takeaway of which is; closure is not necessarily functionally pure. This isn’t to suggest that closure cannot be used in functional theory, it can. Here are some examples of using closure in a way that is consistent with functional style, that produces a pure function.
In the above unary
function, the one
function retains access to the fn
parameter, This is closure and it is considered in functional programming to be pure. Here’s another example we have already seen:
In the above, addTwo
is ‘closed’ over the z
variable, which it is able to use in the final return statement; return x + y + z
. Both the unary
function and the addAnother
function reference variables that are outside of themselves, but it is ‘safe’ from a functional programming perspective because the values of the referenced variables do not change.
Closure Exercise
This is an exercise to practice closure.
Instructions
-
Modify
strBuilder(..)
so that it can take a string and return back a function.Note: For purposes of this exercise, assume that
strBuilder(..)
itself is always called with a string initially. -
For each call to a function here, if a string is passed, a function should be returned.
-
If a non-string is passed (such as passing no argument), a string value should be returned, which is the concatenation of all the passed in strings.
-
Hints:
-
You can use
typeof foo == "string"
to test iffoo
is a string. -
Look at the test cases at the bottom of the exercise file to clarify any questions about expected behavior.
-
Ensure your function(s) are pure. Avoid mutating a closed over variable, which would be a side-effect.
-
Here’s the code to work from:
Closure Solution
Click to view the solution
Lazy vs Eager Execution
As long as the A
variable retains its relationship to the repeater
function with the argument of 10; i.e. it is not reassigned, it will always return AAAAAAAAAA
. The function call is when the ‘work’ of making the string of A’s happens, this is considered to be deferred or lazy. But why would you want to defer the work? You would want to defer the work of a function if you are uncertain the frequency at which that function will be used; i.e. maybe you only need to call a function 10% of the time, it would not make sense to have it always run. The downside of this lazy or deferred approach is having to call the function and do the work every time it is called. The opposite approach to lazy is eager, which would look like this:
Now, the work of the repeater
functions execution has moved to when it is assigned to the variable A
instead of when A()
is called, meaning that the return value of executing the function has already been stored in A
at the time of its declaration. The benefit of the eager approach is that the work is only done once. The downside of the eager approach is that A
may never get called in which case we’ve ‘wasted’ having done the work up-front for storing a value that is never used. In these examples the ‘cost’ of executing vs. not is trivial, but if one were doing more intensive and complex executions, the value of choosing lazy over eager (or vice versa) would become a more important decision. Either approach is possible thanks to closure.
Memoization
What if we want to do the work of the function in the last section, but only want to do the work when it has been asked for and we want to do it only once? Maybe we could have a way to detect whether or not the work had been done, and if it had been done, not do it again? That approach might look like this:
Now, the only time str
will be undefined is at the first call, in which case the work will execute. Once it has executed once, str
will no longer be undefined and it will just return str
instead of doing the work again. The only ‘problem’, from a functional programming perspective, is that the str
variable changes over time from undefined to whatever the eventual string is. The function call itself is pure, but the function definition is not obviously pure. Functional programming is not useful unless it is both readable and pure. In other words, the style of this code produces a low-degree of confidence in the mind of a functional programmer. What if there was a way of achieving the performance benefit of having a lazy function that only executes once when called, but does so in a declarative way? There’s a utility for that! The utility is called memoize
.
memoize
is built into all the functional programming utility libraries. memoize
maintains an internal cache, which if the same input is passed to a function, it will just return the previously cached result. Memoization allows us to write more declaratively, which makes the code more obviously pure. Since memoization maintains an internal cache, is it necessary to wrap all of your functions in it? It depends on whether your function will be called repeatedly with the same or different inputs. If the input will always be the same, this is a good use case for memoization, otherwise, you’d use up a lot of memory for all of the memoization from calling a function with different inputs, in which case this would not be a good use of it. Memoize if you would benefit from the usage pattern of the performance improvement.
Referential Transparency
We’re finally ready to get to the complete definition of what a pure function is! We started with a pure function needs to take some inputs and return an output. We then added to that a pure function actually needs to have a relationship between the inputs and outputs, which is better but still not good enough. We then added that the input and output need to be direct, still incomplete. We then said that the inputs do not have to be direct, but do need to be unchanging. The definition then evolved to focus on the function call which stated that when the function is called with the same inputs we should be able to expect the same output. All of this builds on the previous, but yet incomplete, definition of what a pure function is, but is still incomplete. Here is the canonical definition of what a pure function is. If at the point of a function call you could replace the value with what is returned from the function call and it would not change anything else in the entire program, that is considered a pure function. This is referential transparency.
A function call is pure if it has referential transparency. Referential transparency means that a function call can be replaced with its return value and not affect any of the rest of the program. The real benefit of referential transparency is to the reader of the code. If the reader of your code can realize that a function call will always return the same result, this reduces the cognitive overhead to trace through the entirety of your code every time they see a function call. You cannot have anything else in functional programming unless you understand the value and importance of function (call) purity.
Generalized to Specialized
Moving from generalized functions to ones that are more specialized is a key concept in functional programming. Imagine you have the following code:
There is nothing inherently wrong with the above code, but there may be some details in the function call that are unnecessary. How can we make that cleaner?
We’ve introduced an intermediary function, getCustomer
, which only requires data
and cb
arguments. The getCustomer
function call becomes easier to understand than the ajax
function call. One of the reasons that you make something into a function is so the code is more semantic. The name of a function call describes its purpose, which is the key thing that we want to describe to our codes readers. Considering this, it may be beneficial to push this even further towards specialization adding additional benefit in the way of readability. Here’s that same code further expanded upon:
getCurrentUser(renderCustomer);
is more descriptive than getCustomer({id: 42}, renderCustomer)
is more descriptive than ajax(CUSTOMER_API, {id: 42}, renderCustomer)
. None of the functionality has changed, the stylization of the code has changed to be more semantic. This is great, but we’ve kind of cluttered up our code. Is there a way that we could define these more specialized versions of functions without having to define manually pointed functions? Of course there is! But before we jump into what that looks like, it is important to reiterate that the order of parameters in our function definitions is important! Parameters should be ordered from most general to most specialized and you will see this being the case if you take a look at functional programming utility libraries.
Partial Application & Currying
The first approach we could take to refactoring the code in the last section would be partial application:
partial
is a utility method provided by all the functional libraries which takes a function as its first input, and then it takes as its next input a set of arguments to pass along to that function at some point. Another, more common, way of specialization is currying. When it comes to (function) specialization, partial application and currying are kind of like cousins, related in the sense that they both accomplish the same end goal; specializing a generalized function, but they both go about it in a different way. Let’s look at how we could specialize our functions with currying.
The ajax
function call is actually being called three separate times, with an argument supplied for each ‘level’ of the function; url
, data
, and cb
; this could be considered a manual form of currying. This allows us to get specialization like so:
We can now get the more specialized function calls without having to leverage a utility such as partial
. It would be nice if there were a utility that could further simplify the currying for us! Well there is:
The curry
utility adapts the passed in function into one that only accepts one input at a time. In other words, it creates a wrapper adapted function who’s job it is to keep returning a new function that expects another input, until you have provided the specified number of inputs; in the above code that’d be 3.
Partial Application & Currying Comparison
So we have the same output with currying that we had with partial application. The major difference is that with partial application we had to call the partial
utility function numerous times versus currying where we only had to call the utility function for currying once. Functional programmers prefer currying over partial application because they tend to prefer unary functions; single input, single output; which currying is. Here’s a summary of partial application versus currying:
-
Both are specialization techniques
-
Partial Application presets some arguments now, receives the rest on the next call
-
Currying does not preset any arguments, receives each argument one at a time
If you’re ever asked in an interview what’s the difference between partial application and currying, the answer is; both of them specialize, but they do it differently; partial application takes some input now, the rest later, currying takes no input now, each input one at a time.
Q: Why does Partial Application still exist in functional programming?
A: Because, aside from it being a part of the historic canonical definition of functional programming, there are some cases where it would be more convenient to do Partial Application over Currying. For example, consider you have a function that starts out expecting five inputs, and you want to produce another function that expects three inputs, i.e. you only want to preset two of the inputs. If you were to curry this, you’d have to call it twice, and the function that you get back would not be one that is expecting three inputs, but a curried function of three more chains, which might not be the shape of function that you want to pass around. In this case, it might be that Partial Application produces a more preferable shape.
Changing Function Shape with Curry
Consider the following code:
Why in the above .map
could you not directly pass the add
function instead of how it is implemented above? Because they have different shapes. add
is a binary function while map
is expecting a unary function. In the above code, addOne
is changing the shape by pre-specifying one of the inputs. But it might be even better to have a curried version like so:
While both function the same, using curry
is arguably better for readability, and this is an extremely common pattern in functional programming. You will see this all the time if you are working in a functional programming environment. The curry
function above is something that would be provided by a functional programming utility library and is out of the scope of this workshop to show / describe.
Composition
Composition Illustration
Composition is the idea of one functions output becoming the input to another function. Here’s an example of some code that could benefit from composition:
Although we do not see what basePrice
is, the code is easy enough to follow. Could it be improved? We will expand on this while working through what composition is. In the above code, there are a couple of things happening that we could abstract further; the calculation of the shipping rate and the calculation of the totalCost
. But what is abstraction? The original idea of abstraction was to tease apart two things which were otherwise intertwined together, so that they are separate, and by way of separation, we insert between them a semantic boundary. Abstraction is not about hiding anything, but about separation. The idea behind separation is that we should be able to look at the pieces of our code and understand them as individuals. But how could we abstract(separate) the above code? Well, since you asked… We could do something like this:
Notice how we are now nesting the function calls which allows us to get rid of the tmp
variable. The nested function calls are a form of composition. This works, but the separation(abstraction) is still incomplete; the shipping is being calculated within the totalCost
variable. What if there were a shipping cost function?
The above result is definitely cleaner, because the concerns have been separated. AKA abstraction. The semantic boundary that we’ve inserted is the function name shippingRate
.
Declarative Data Flow
So far, the abstraction and composition of our code has progressed nicely, but what if there were numerous shipping rates to handle? Could we further modify our code to accommodate them? Well, currently, the shippingRate
function is essentially handling the execution of 3 different functions, maybe we could create a utility function that could accommodate this.
Now, with our new utility function, we can refactor our code to look like so:
Using the utility function, shippingRate
can change according to what functions are passed into composeThree
. Composition works from right to left, which is why in the utility function definition we’ve structured the arguments from fn3 to fn1, because they will execute in the ‘reverse’ or right to left order. Composition is critical to functional programming because the entire point of any program is to have data flow; something coming in and something being returned out. The composeThree
utility function that we ‘created’ is actually present in functional programming utility libraries, typically named compose
which has the ability to compose however many functions you need.
Piping vs Composition
To illustrate the importance of function order and the right to left execution of composed functions, take a look at this:
f(4)
will first increment 4 making its value 5, then triple 5 becoming 15, finally minus2 returning the value 13.
p(4)
will first minus2 making the return value 2, then triple 2 becoming 6, finally incrementing by 1 returning the value 7.
Considering composition, this should not come as a surprise. But what if we wanted to have the functions passed in as arguments to something like compose and executed in left to right instead of compose’s right to left? Pipes do that!
Piping & Composition Exercise
This is an exercise to practice composition.
Instructions
-
Define a
compose(..)
that takes any number of functions (as individual arguments) and composes them right-to-left. -
Define a
pipe(..)
that takes any number of functions (as individual arguments) and composes them left-to-right.
Hint: you only need to implement one of the two functions compose
or pipe
. Once you’ve completed one of them, you can simply pass whatever is being passed to the other function but reverse it. i.e. complete pipe
, then in compose
you would just need to return pipe(functions.reverse())
.
Piping & Composition Solution
Click to view the solution
Associativity
Associativity is a mathematical concept, but composition is also associative. Meaning that if you have a list of functions that need to be composed, you can compose them in any grouping and get the same result. Here is some code which illustrates associativity:
Associativity is useful because it means that we are able to do currying and partial application on compositions.
Composition with Currying
With the following code, how could we combine composition and currying?
So far, we’ve seen composition only with unary functions; functions that take and return a single value. Why would it be that we would only compose unary functions? Primarily because of the differing shapes of unary and binary functions. Again, how would it be possible to compose the three functions in the code above? Possibly something like this which basically turns the binary functions into unary functions:
Now that we’ve seen composition and currying together in action, let’s take another look at point free, with this before seen example:
If we wanted to transform the above code for the isOdd
function into one that is point free, we could again use the compose
style of function to do just that:
The above is another example of taking binary functions and composing them into unary functions.
Immutability
Immutability
Immutability implies that something is not going to change, but that does not fully encompass what this section of the workshop will cover. It isn’t only that things do not change, but that they do not change unexpectedly. In programs, there is a lot of state change, which is arguably the point of them, for state to change over time and with state change being the point, you don’t really want to stop that from happening. There’s really no such thing as making an immutable program because that program would not have any point or reason to exist. The point of immutability is that change which needs to occur, needs to do so in an intentional manner. How do we control mutation and change? There are a couple of types of immutability that we will look at, the first being assignment immutability.
Assignment immutability is the idea that when you assign something to a variable or property that it is no longer allowed to be reassigned to another value. Here’s an example to consider:
In the above code, basePrice
and shippingCost
are both variables, rather a symbolic representation in memory, the difference between the two being how they will handle reassignment. With var
or let
, you can reassign them, no problem. But if you try to reassign something that has been declared as a const
, you will get an error saying that it is not allowed. Another caveat about const
is that it cannot be declared without an assignment. You may have heard of the ‘temporal dead zone’ or TDZ which is all about preventing us, the developers, from seeing a const
ever in an in-between state where it is undefined. So… then why should we use const
in our applications? The greatest support for having const
as a variable type in JavaScript comes from the functional programming community.
Let’s look at some more code:
Notice now that we are merely computing values as opposed to reassigning values to existing variables. This is typical of functional programming where most will tell you to try and avoid assignment at all costs. Which is suspicious as to whether or not const
is as useful as it is proclaimed to be.
Rethinking const Immutability
Here’s some more code to look at when considering the proliferation of const
in JavaScript:
There is a lot of baggage that comes with the const
keyword. A lot of the ‘issues’ that people have seem to come from the term const
(ant) and the meaning that it (constant) conveys in the English language as opposed to how const
has been implemented in [insert programming language here]. In English, one would typically associate const
(ant) with something that has not / does not change. When using const
with a primitive value; number, string; it’s no problem. But when using const
with an array or an object (yes, also a function which is an object), these elements are changeable / has mutability. const
implies that an assignment will not change, not the values within. You can certainly learn the mechanics of const
and make these ‘issues’ not a problem for you. Java deprecated the const
keyword and replaced it with final
. final
implies that it is the final state of a variable, rather than one that does not change.
Does const
have provide benefit that it can overcome any potential downsides that it may present? It is the opinion of the instructor that const
doesn’t really carry its own weight. The argument being that if it is going to trip people up so much, then it had better provide enough benefit to justify its inclusion in our programs. Keeping in mind that assigning a value to a variable is linked to the idea that the variable belongs to a particular scope, in the above code, there is a very small ‘window’ of possible code that could reassign any of the variables that exist. A typical argument in defense of const
is that it is signifying intent, that this variable will not change anywhere in the code. But if we are following ‘best practice’, whether that is your own self-imposed definition of what best practice is or otherwise (perhaps you have some rule about how long you will allow any given block of code or function to be), the possibility of a variable changing should be fairly limited.
So how can you signal to the reader of your code that a variable is not going to be reassigned without using const
? Don’t reassign it! And if you are doing functional programming, don’t assign at all! Or as little as possible, do assignments. More important than all of this const
business and whether it is immutable or not, is value immutability.
Value Immutability
After all that const
hate, we’re going to focus on the immutability of values. 99% of the problems we face come from a value being mutated in a way that we did not expect. The instructor shares that in all of the code he has ever written that he has never had a bug that came from reassignment… Here’s some code to consider the idea of value immutability:
In the above code, what is the processOrder
function doing? No idea? Me neither… But if there was something else after the function call to processOrder
, something that relied on the orderDetails
object, we would have to have the suspicion that the object has changed. One of the things functional programmers do is try to pinpoint where the bugs are going to be and avoid them before they occur by using patterns where bugs cannot happen. Value immutability is arguably one of the most under-covered topics in functional programming. Values get passed everywhere, we pass arrays and objects and functions all over the place. And we should be asking ourselves every time we are passing one of these things; how do I know that isn’t going to create a bug somewhere in my program? When you pass a string or number, you do not have to worry, but when you pass an object or an array, you do not have that same level of (immutability) guarantee. So even without looking at the processOrder
function, it should be safe to assume that it is going to do something to the orderDetails
object and something should be done to ensure that does not happen!
Object.freeze
How can we make sure that the orderDetails
object does not change when it is passed to the processOrder
function? Your first guess might be, “we need an immutable data structure”. Nope. We need to say that the value is read-only. i.e. a data structure that can be read but not written to. Thankfully, there is a method built in to JavaScript; Object.freeze
. Here’s that in action:
Object.freeze
is telling the object to change all of its properties to have the read-only attribute on them so that none of them can be changed, it also cannot have properties added or removed. Object.freeze
is only shallow though, so be aware that if you have nested objects of nested objects of arrays, you would have to freeze each level to get that same read-only guarantee that Object.freeze
provides. But in our code above, there is only a simple single-level object, so Object.freeze
will make our object read-only. But maybe it doesn’t really matter if the (entire) object becomes read-only? The real intent of using Object.freeze
here is to communicate to the reader of your code that they do not need to worry about the thing changing. Object.freeze
does in fact do what it is supposed to do, freeze the object to a read-only state, but it does also give the reader of your code the signal that this object will not be changed or mutated.
Don’t Mutate, Copy
Read-Only Data Structures: Data structures that never need to be mutated
The above code is what the processOrder
function that we saw before could look like. Notice that it is in fact trying to modify the object that it received, but the modification does make sense because it is trying to update the order status in a database. But this mutation is, by definition of functional programming, a side-effect; i.e. an impure function. Erring on the safe side, you should always assume that you are not allowed to mutate something; but then what can we do? Make a copy of the object! Like so:
Now that we’ve made a copy of the original object, we can safely mutate it without mutating the original! So now we have two considerations when avoiding mutation; 1. Do your reader a favor and signal that you do not want whatever it is to be changed; i.e. use something like Object.freeze
. 2. When you write a function that receives data structures, treat the incoming data as if it were read-only, no matter what. Make a copy of the data structure and make changes to that local copy. In these ways we are able to deal effectively with value mutability.
Immutable Data Structures
We’ve covered what to do with data structures that don’t need to change, what do we do with data structures that do need to change? You cannot treat all data structures as immutable data structures, some of them are going to have to be mutable. When you have the need for a mutable data structure, one that is not read-only, what you need is an immutable data structure. Wait, what? An immutable data structure is one that allows not no-mutation, but rather structured mutation. Structured, controlled, intentional mutation as opposed to just create an assignment and have side effects somewhere. You should build your objects by first asking if it will ever need to mutate. If so, you don’t need to use read-only, but something immutable. But if it never needs to change, stick with a read-only structure. We will only use an immutable data structure if it need to mutate.
What is an immutable data structure? It is a representation of the data structures that we are used to dealing with; i.e. arrays, where we can access things at indexed positions, and objects, where we can access things at named property positions. It is data structures like those mentioned, but where you don’t have access to the underlying data structure, what you have only is an API to access it. The API creates a layer of control that prevents unexpected changes to the data structure. Specifically, an immutable data structure does not allow you to make any changes to it unless you switch into a special mode that allows changes to be made. You can only create a new data structure with the change having been applied.
This immutability is great, but what are the implications for performance? Remember, we are working in a way that only allows changes to be made to an array or object that is a copy and we’re talking about making thousands of changes per second. At best, we have a bunch of garbage collection, but at worst there is going to be a ton of CPU churn from making thousands of copies of something per second. Fear not! The way that immutable data structures are designed is specifically with optimization in mind. In theory, in functional programming, we don’t make a new thing, you don’t make a change to a thing, you make a new thing with the change applied, which in practice means real cost like garbage collection and CPU churn. Therefore, it is the job of an immutable data structure to mitigate that real practical cost so we get closer back to the theoretical benefit of what an immutable data structure is.
If you use an immutable data structure, what it is actually going to do is not create a whole new copy of the object when you try to change a property, but rather make a new object with the new information in it and internally have a pointer back to the previous object. This is something like a git repo where every time you’ve committed something you are just storing a diff compared to what it was before. Similarly, the new object is effectively a diff on the previous object. This reduces the CPU usage and garbage collection. This is all wonderful, I want immutable data structures, please give?
We do not at the present time have immutable data structures natively in JavaScript 🤬
JavaScript having immutable data structures has been discussed at TC39, but that does not mean that it will ever happen. There would be a huge benefit to the language being able to highly optimize immutable data structures.
Immutable.js Overview
In the interim, of immutable data structures being directly implemented in JavaScript, if it is important for you to manage the mutations on data structures, you are going to need a library that provides an immutable data structure. The most common JavaScript library that provides immutable data structures is, immutable.js, brought to you by Facebook. There is another library called mori, this is preferred by functional programmers that prefer closure. Mori has a different take on the way it works, as opposed to immutable.js, and what the API looks like. Both libraries provide structured mutation for data structures. Here is an example using immutable.js:
While we don’t have any details on what textbook
, supplies
, or calculator
are, that doesn’t really matter. When the updatedItems
variable is created and we push calculator
to items
, that doesn’t actually happen, well it doesn’t get pushed to items
but rather to the updatedItems
variable. items
is immutable whereas updatedItems
is a copy of item
and is not immutable. You can see that reflected in the logs of whether the two objects are equal and when we check their size.
Functional programmers tend to minimize the amount of assignments, but for ones that you do have, you will generally do them in small blocks and the const
keyword will not provide much benefit for you. Therefore, it may be more appropriate to use var
or let
if nothing else than for the benefit of the reader of your code. Another way to signify to readers of our code is to wrap the data being passed at a function call site in Object.freeze
, and if you need to recursively freeze the various levels of your object, make a helper utility function for this. When you receive a data structure, assume it is read-only. If you need to track changes to data structures, you should be doing so with an immutable data structure.
Immutable Data Structures are data structures that need to be mutated.
Immutability Exercise
This is an exercise to practice with assignment and value immutability.
Instructions
-
Define
pickNumber(..)
so that it’s a pure function. It should the list of lottery numbers and a new lottery number (randomly generated usinglotteryNum()
) to add to the list. -
pickNumber(..)
should always keep the list of lottery numbers sorted in ascending order. Also, no duplicates! -
Hint: Array’s
sort()
(with no argument) does not do numeric sorting but alphanumeric sorting. You’ll need to pass a custom comparator function to get true numeric sorting.
Bonus
Instead of a read-only array (via Object.freeze(..)
), use Immutable.js’s List
data structure to manage the additions to luckyLotteryNumbers
.
Work from this code:
Immutability Solution
Click to view the solution
Recursion
Recursion
Ah recursion, the terrifyingly complex concept. But not. The issue might be related to our lack of proper perspective on this topic, it’s actually not so complex. And as a person who aspires to use functional techniques, your toolbox would be incomplete if you left recursion out of it. Let’s look at some code and get more comfortable!
The above code works, but the “problem” with it is that you have to read it to convince yourself of what it does. So… is there a more declarative approach? Of course! There are multiple ways to solve this problem, recursion is not the only way to do so. But a recursive approach is something that we should get more comfortable with because there will be problems that we come across where recursion is the best answer to the problem and in some cases almost the only practical answer to the problem at hand. In other words; some problems can be solved with recursion while other problems must be solved with recursion. That being the case, we should be familiar with it! As a programmer, our first job is to understand the problem that needs to be solved. That being said, we should (when first presented with a problem) think about how to solve that in a recursive way before trying to write any code. How would we solve the vowel check in a recursive fashion? What if we looked at the characters one by one, as we’ve done above, but in a slightly different way? Every recursive function should have a base condition which will define the stopping point for the function:
Recursion gets confusing for people because they try to think about the implementation rather than the outcome, the issue in that being recursion is declarative; which is concerned with the outcome. It is important as a functional programmer to think whether or not you can break problems into easy to understand pieces. There are a few patterns that are repeated over and over in recursion, one of which is solving sub-problems, which is what was used above to determine the number of vowels. Another recursive pattern is called ‘divide and conquer’, which takes a giant problem set and tries to determine if you can eliminate half of the problem, then eliminate half of the remaining, and then eliminate half of the remaining, and so on. If you can get to the point where you can understand common recursive patterns, then you will be able to see a recursive problem and understand exactly how it is being solved.
Base Condition Location
In the code we just looked at in the last section, the function countVowels
runs one final time, even when there is nothing of the string left, executing on what is an empty string. Is there a way to preserve the declarativeness of the countVowels
function and also prevent that final function call when there is an empty string? Of course we can! By moving the base condition within the function definition, we can determine whether or not the function should even be run before running the function. BOOM:
In the slightly refactored code above, we’ve moved the base condition one line down and are checking whether the string is less than or equal to 1, rather than zero, which will cause the function to run again only if there is more string left.
Recursion Exercise
This is an exercise to practice recursion techniques.
Instructions
-
Define a recursive
isPalidrome(..)
function that returnstrue
if the string passed in is a palindrome – same string when written forwards or backwards – orfalse
otherwise. -
An empty string and a single character string are both defined as base-condition palindromes. The strings “aba” and “abba” are also palindromes.
-
All the test cases at the bottom of the exercise file should print
true
. -
Hint: Consider “abcdcba”. A handy recursive definition for a palindrome is that the first and last character of a string (ie, the “a” and “a”) must be the same character, and the substring in between (ie, “bcdcb”) must also be a palindrome.
Recursion Solution
Click to view the solution
Stack Frames & Memory Limits
Recursion typically doesn’t make its way into production applications because of range errors that get thrown when recursion has been running for too long, resulting in a range error
or stack overflow exceeded
error. We can address this problem by first thinking about the implementation. Consider what happens when a function is called, it doesn’t have to be its own function or recursion, but when one function calls to another function, at that moment, everything that was currently happening in the original function needs to get saved somehow so that whatever happens in the new function call doesn’t ruin whatever was happening in the first function. Where is this in-progress function state saved? In something computer scientists call stack frames. Each time a function gets executed, an area of memory is reserved and it is called a stack frame. It is called a stack frame, or memory frame, because when one function calls another and then that one calls another and so on, we actually have a ‘stack’ (of functions) that is growing.
This idea of a stack data structure is used because when the function ‘on-top’ of the stack finishes running, it gets ‘popped’ off of the stack, returning to the function that was underneath it in the stack. But what is in the stack frames? All of the local variables that have been assigned, any memory that is being assigned for those variables, a program counter which tracks what line of code it is on, and any basic low-level things that the computer needs to track what’s happening inside of a function. This doesn’t take up a lot of memory, not megabytes of memory at least, the stack frame is more likely around a few hundred bytes or 1kb or something small like that. When you call some function, it might go 5, 10, or even 15 calls deep, and in turn add that many layers to the stack, but when you start running recursive functions, the stack can grow to thousands of levels, which will start to have an impact on the amount of memory being used.
From a mathematical perspective, recursion works very well, but from the perspective of computer hardware, this is not the case.
Optimization: Tail Calls
The way to address the (potential) computational-heavy effect of recursion is an optimization called tail calls. To understand what a tail call is and how it works, we need to understand that when we make a recursive call, we need to understand why the stack frame that is currently being executed needs to be kept. We can often either reuse the existing stack frame or throw it out in favor of a new one, this is what happens with tail calls. If a function call happens in a position which is referred to as a tail call, meaning it is at the tail of the execution logic, then we don’t need the existing stack frame anymore and we can dispatch to another function call and not take up any extra memory. The idea is that at any given time you should only need one stack frame. This idea only holds up for function calls that have happened in a tail position. This is an optimization in the bigger sense of optimization, not of performance or speed, but one of memory use.
Tail calls are an additional feature that the system, language, compiler, and runtime has to support. So, what about tail calls in JavaScript? Well, the language itself does have a way of checking against how much memory an application is using and a threshold for what a limit is. In Internet Exploder 6, the total stack depth was limited to 13. But what is the right number of function calls that should be allowed? This is a prediction that the JavaScript engine has to make, it doesn’t know if the recursive function is about to finish or not. So the JavaScript engine is looking at what is happening in the application and stack, then making a prediction about whether or not what is happening will in fact run the system out of memory. Modern browsers don’t have this arbitrary number thrown on the limit of depth of the stack, but it is more likely based on the actual available system memory.
The actual (stack) limit will vary depending on environment, device, etc., which are generally not things you can predict or control. This fact makes it all the more important that JavaScript has support for tail calls. This hasn’t happened because the idea of tail calls is antithetical to the way that the JavaScript specification was written. Well, not literally antithetical, but the specification is designed to be as agnostic about implementation details as possible. The JavaScript spec says, this is the final outcome that should happen, and it does also specify algorithms for how things should be accomplished, but if the end goal of any operation is preserved, the JavaScript engines are allowed to decide which corners they are going to cut. As long as they follow the spec, they can implement JavaScript however they like, make optimizations however they see fit.
Proper Tail Calls
Traditionally, there has been a wide range in terms of implementation for JavaScript. If the JavaScript spec steps in and says, “you must absolutely throw away stack frames and allow 0(1) memory usage”, that would encroach upon the freedoms that JavaScript engines have had in how they implement. As of yet, the way engines implement JavaScript does not have this sort of restrictions or such a high-level of specificity when it comes to implementation. There’s even been push back from JavaScript engines on tail calls, arguing that people don’t even really care much about them and that people don’t even use recursion, so why should they (the JavaScript engines) modify their implementations? The problem creates an infinite loop of, “no one uses this (recursion) so we are not going to implement it, it’s (recursion’s) not implemented so we aren’t going to use it, no one uses this (recursion) so we are not going to implement it” ∞. There was a proposal in ES6 that aimed to standardize that JavaScript engines should have to do tail calls, specifically, ‘proper tail calls’ or PTC.
Proper tail calls are the idea that memory gets optimized, that we only use 0(1) memory space. There is a related term, Tail Call Optimizations or TCO, which is a set of optional optimizations on top of PTC that were proposed as well, i.e. garbage collecting old stack frames, or reusing them. The only thing relevant to us (JavaScript developers) though is whether proper tail calls are in the language or nah. So the ES6 PTC proposal was aiming to standardize them. The specific language of the PTC proposal was not worried with any of the TCOs, but with a function in a tail call position to not take up any extra memory. It was actually voted in to the ES6 spec standard. PTC looked like this:
PTC in ES6 requires that ‘strict mode’ is on, which if you are not already using strict mode, you should be. So do it. Next, you have to have your function call in what is called a proper tail position. The function call above inside of decrement
; sub(x, 1)
is in the proper tail position and this is the proper tail position because once that function is run there is nothing else left to do in decrement
except return whatever comes from sub
. Additionally, without the return keyword, it would not be considered to be a proper tail call. Proper tail calls require a return keyword, a single function call, and nothing else in that expression that needs to be computed afterwards. Even if you have a ternary expression and the function call is in one of the positions; i.e. a ? doSomething() : doSomethingElse()
, that is a proper tail call because nothing else is going to happen, even if it doesn’t look like a proper tail call, it is considered to be.
We’ll typically see proper tail calls in the case of recursion, here’s another code example to examine:
The diminish
function above takes a number and keeps dividing it and calling the diminish
function until the condition is met. It is a proper tail call.
Q: What if instead of Math.trunc
there was instead another function call?
A: That call would contribute to the growth of the call stack and likely lead to a range error. You only get the benefits if the function calls are in the tail call position.
Refactoring to PTC Form
Let’s refactor the countVowels
recursive function to use PTC, this is what it looked like when we first saw it:
First, why countVowels
is not already PTC is because of the addition that is happening within the return statement. That’s fine because many forms of recursion can be refactored to take advantage of tail calls. If you are ever going to use recursion, you’re going to have to get comfortable with the idea of thinking about proper tail calls. Great, so how can we get that maths out of the return statement? Where else could we keep track of that if not in the return statement / stack frame? If you guessed next stack frame, AKA arguments being passed to the function, you are correct! If not, that’s fine, I did guess it, but wasn’t 100 on whether or not that is the correct place for it. Here’s what the above code looks like when refactored to use a proper tail call:
The above works fine, but having to pass zero into the function call seems kind of awkward. WHY?! Often, to avoid this kind of very weird thing, functional programmers will create an interface function that has a nice looking signature and then they’ll have the recursive function hidden away that has the ‘non-clean’ signature, which might look more like this:
The above will now work just fine, and may in fact be a bit slower than a for loop, but we won’t end up with a runaway memory situation.
Continuation-Passing Style
Because we know that proper tail calls are not something that we can yet rely upon, we have to consider other strategies for writing what are essentially recursive algorithms without having to rely upon the optimization of tail calls. There are a couple of options that we could use, the first of which, continuation-passing style (CPS), you will probably never use 🤔, nonetheless, it is important to know that it exists. A continuation is essentially a call-back and returning to the countVowels
example from the last section, it would look like this:
Notice how some of our countVowels
function has remained basically the same, but there are some additional additions to talk about. The first is cont = v => v
, this is what is referred to as the ‘identity function’, which in functional programming is a function that returns whatever is passed to it. Identity functions are really useful base conditions for a bunch of things in functional programming. Our instructor doesn’t particularly care for arrow functions (one was used here for the express purpose of saving space on his slides) and mentions that an identity function would likely exist in whatever functional programming library you might be using. The identity function is only used on the initial function call, later it is replaced by the function f
when the return countVowels
is hit. All of this is exceptionally complex, so if the above looks confusing, that’s par for the course. People don’t usually write in the continuation-passing style, it is usually what is converted code; meaning that you write your code in some other way and your code is converted to CPS style.
The fact that the code looks confusing is directly related to the fact that it is normally written by a machine, not a human. CPS is kind of a ‘cheat’, but it is definitely a proper tail call. We won’t experience any range error issues, because the function is wrapped in another function, which results in a progressively bigger and bigger function until that is finally executed, but that doesn’t actually fix any memory problems. While the above code won’t grow our usage of the stack, it will grow our usage of the memory ‘heap’. Theoretically, if you were to run a program using CPS, it would eventually exhaust the entire system of all of its memory and crash the system. JavaScript does not have error to check for the exhaustion of the ‘heap’ memory, only for exhausting the stack. The bottom line is that CPS is not really the solution that we want in JavaScript, it cheats around one error and potentially creates another.
Trampolines
The idea of deferring the work of a function until later is an idea that we want to keep in mind for this last technique, one that is recommended to be used; trampolines. Trampolines are written almost like a regular recursive function, but with an adapter that helps take care of the tail calling. Oddly enough, a trampoline is a way of indicating that we want something to ‘bounce’ back and forth. But what is being bounced back and forth? Instead of having a function call a function call a function, a trampoline will go something like; function call function, then call that function and return another function, then call that one and return another function, then call that one and return another function. This gets around the stack build-up, in the case of a trampoline, the stack depth never goes beyond 1. Instead of an actual recursive call, we are returning a function that makes the next call.
Here’s a utility that demonstrates what a trampoline looks like:
The above code block is an example of a utility function that would be provided by a functional library. But how it works can be seen in the while
loop, where it is checking whether or not what is being passed is a function; if yes, run again, if not, return result. And in this way, a trampoline will not cause the stack to overflow or the heap memory to exhaust, because it is only returning and calling one function at a time. Here’s what it looks like to actually use the trampoline utility:
The above code looks quite familiar to the countVowels
function that we saw earlier, the only major difference(s) being that it is wrapped in trampoline
and the return countVowels...
line is now also wrapped in a function. The way that the added function f
works is that it has closure over the things that it needs. So that’s how trampolining works, and why you should use it over other tail call formats is that at some point if tail calls are implemented in JavaScript, compilers will likely be able to convert trampolines into proper tail calls. Also, if you are doing anything iteratively in your code, try to find opportunities to use recursion, or better yet some implementation of tail calls, better yet, trampolines. In this way you will find that these things will start to make better sense to your understanding of how they work and are implemented.
CPS & Trampolines Q&A
Q: So CPS is some sort of memorization where we’re trying to call cont v
?
A: In CPS, the ‘trick’ to what we are doing is, instead of actually making the recursive call, or doing the work up front, the work is being deferred by wrapping it in a function and passing the function forward. cont
becomes a bigger and bigger function, all of which are in tail call form, with a bunch of returns.
Q: Why do we have tools to transpile code to CPS if there are issues with memory [use]?
A: Because it does fix the stack issue. The heap allocation issue is actually specific to JavaScript, in C, they do have techniques for dealing with the memory allocation problem.
Q: What are good trampoline libraries?
A: Ramda, Lo Dash, basically any functional utility library will have a trampoline function. They will have slightly different implementations of trampoline, so read the documentation!
Q: Can you summarize the difference between a trampoline and regular recursion?
A: In regular recursion, we stack up the work, which grows the memory usage. In a trampoline, the work is never stacked up in this way, work is done, then returned back to the helper function (trampoline), if it is a function, the work will continue and so on until the returned value is not a function.
Let’s take one more look at the code difference between a regular recursive function and one that is ‘trampoline-able’:
Between the two countVowels
above, the only real difference is the return countVowels...
is wrapped in another function in the trampoline-able version, all else it would need is to be wrapped in the trampoline
utility function.
List Operations
Map: Transformation
When talking about lists, we’re not only going to only be talking about arrays, even though these things are usually illustrated with arrays; we’ll be focussed on data structures. map
and filter
, etc. are actually generalized operations that should be able to be performed across any data structure. It just happens to be that, especially in JavaScript, that it’s convenient to illustrate these concepts in the context of arrays. So far, we’ve learned how to use operations on single (discrete) values, and now we will adapt those operations so that they work across a collection of values. A functional programming term that we should know is functor. A functor is a value, even a collection of values, over which those values in it can be mapped. In the case of an array, we (probably) know that we can call .map
on an array, the array is a functor. The only purpose of bringing up the word functor is to let you understand that a functor is essentially a value that can be mapped.
Moving on… What is map? It is fundamentally a transformation operation. Meaning that we will take the values in some collection and perform a conversion on each of them. Keep in mind that a data structure does not imply multiple values. A single value in a single data structure can be a functor, and can be mapped over. This is valid. Map transformations are not happening in place, for it to be the functor, to behave according to these (functional programming) principles, it has to be a pure function, it cannot have mutation, it has to produce a new data structure. A map always results in the same kind of data structure as it started with. i.e. you start with an array, map will give you another array. So how can we implement a map-like function?
Technically, the makeRecord
function in the code above is not a pure function in functional programming standards, but technically it is, because the name
value is not being mutated and the returned object is also not a mutation. The above functionality is typically used with arrays and there is in fact a map method for arrays built in to JavaScript:
Any sort of source value with any sort of transformation can be mapped. The idea of map, and the other methods we will look at, is that we are using the same transformations across all of the values in the data structure. While it would be possible to include some if
statements within a mapper function, this is a polymorphic way of thinking about the purpose of a mapper function and is advised against. Map functions should do only one sort of transformation.
Filter: Inclusion
Filter is often referred to or thought of as an exclusionary activity, i.e. filtering something out; when cooking spaghetti noodles, we filter the water out when pouring the contents of the pot into a strainer. But in development, filter is actually an inclusion; you return true if you want to keep something, false if you do not want to keep something. The main issue with the word filter is that in English, it usually implies that something is being filtered out. Because of this (potential ambiguity or implied meaning), the instructor names his filter operations as filterIn
and filterOut
to be more explicit as to what the implications of using these operations will achieve. Here is an example of how a filterIn
function would look:
In the above filterIn
function, the predicate
argument is used when a function returns a boolean. Using the filterIn
function and passing in the isLoggedIn
function with an array, we will end up ‘filtering in’ the user objects to the newList
array that have a session associated with them. This is exactly the same as JavaScript’s built-in filter
method. That would look like this:
Using the filter
method, none of the values get changed, that’s what map
does. With filter
, we are just selecting values based on a predicate check.
Reduce: Combination
map
does transformation, filter
does inclusion or exclusion, reduce
combines values. Reduce works with multiple values, making its decision based on the current running accumulator, as well as the next value. When working with a collection of values and a reduce function, it is important to select the appropriate initial value for your reduction; i.e. something numeric for math based reduction, an empty string for string concatenation, a resolved promise for promise chaining, etc… There are some implementations of reduce that if you do not provide an initial value, reduce will select the first item in the collection as the initial value, starting the reduction with the next value in the collection.
Reduce, whatever the current accumulator is, whether an initial value or we’re somewhere into the reduction, takes the current accumulated value, adds in the next value in the collection, and they get ‘combined’ (or reduced). In other words, the reducer takes two inputs; the existing accumulator and the next value in the collection, and decides how to combine them (whether by your provided initial value or the initial value of the collection). the idea of reduction is a very general concept, reducing a collection does not have to be combining values, you could have a reducer that picks a value. Reduction is whatever you define it to be, but it is often used for values to ‘end up’ together in some way. However it is reduced, the result is a single value.
Reduce can be thought of a the swiss army knife of functional programming because you don’t have to produce a single value, you can produce an entire data structure with reduce. You could start with a list of numbers and ‘reduce’ that list to an object with properties holding those numbers. Reduce is so general in fact that you could implement it to function as map
or filter
. Here is how to implement a reduce function:
The above implementation of reduce will take an array of tuples (an array with two values) and reduce them into an object where the first element of the tuple becomes the key and the second element of the array becomes the value. Notice the spread operator being used in the addToRecord
function? Why would you want to effectively make a copy of the object every time instead of just adding the new key: value pair to the object? Because, in functional programming, we want to avoid mutation as much as possible. Here’s the same code from above, but using JavaScript’s built-in reduce
method:
Composition with Reduce
Let’s talk about composition. In the last section, we looked at a reduce function. There is a companion to reduce, which is called reduceRight
. reduce
goes from left to right in an array, and reduceRight
goes from right to left. Earlier, there was another thing we looked at which also goes from right to left, which was foreshadowing for this discussion, and that was composeTwo
(in associativity of the composition section). If you look at the shape of the composeTwo
function, you might notice that the shape of it matches that of the reducer that we just covered, in fact, composeTwo
is a reducer! Here’s another look at the composeTwo
function:
And here’s an implementation of compose with reduceRight
:
List Operations Exercise
This is an exercise to practice list operations (map/reduce/filter). We also revisit a variety of previous FP concepts (closure, recursion, etc).
Instructions
-
Write two functions, each which return a fixed number (different from each other) when called.
-
Write an
add(..)
function that takes two numbers and adds them and returns the result. Calladd(..)
with the results of your two functions from (1) and print the result to the console. -
Write an
add2(..)
that takes two functions instead of two numbers, and it calls those two functions and then sends those values toadd(..)
, just like you did in (2) above. -
Replace your two functions from (1) with a single function that takes a value and returns a function back, where the returned function will return the value when it’s called.
-
Write an
addn(..)
that can take an array of 2 or more functions, and using onlyadd2(..)
, adds them together. Try it with a loop. Try it without a loop (recursion). Try it with built-in array functional helpers (hint: reduce). -
Start with an array of odd and even numbers (with some duplicates), and trim it down to only have unique values.
-
Filter your array to only have even numbers in it.
-
Map your values to functions, using (4), and pass the new list of functions to the
addn(..)
from (5).
Bonus
Write tests for your functions.