Notes on functional programming
Some years ago I did a couple of courses, Paradigms of Computer Programming and Introduction to Functional Programming, and I took notes while doing them. Here you have a selection of the notes about functional programming I took from these courses.
Paradigms of Computer Programming
This is a course by Peter Van Roy, using the Oz language, offered at edX:
https://www.edx.org/course/paradigms-of-computer-programming-fundamentals
https://www.edx.org/course/paradigms-of-computer-programming-abstraction-and
(I completed it in May 2014. I believe it was the first offering, and then it was split in two.)
Oz is a multi-paradigm language. The course starts with the functional paradigm, which serves as a basis for object-oriented programming and concurrent programming.
The course has different chapters, so I've divided the 'quotes' based on the course's chapters.
Introduction
Functional programming has one key property: a function never changes its behavior.
The property that functions never change is both the strength and weakness of functional programming. The strength because it means that working programs cannot be broken. The weakness because it means that programs cannot change to meet changing demands. The only way to change a program is to create a new program.
Functional programs do not have any internal memory, they are stateless.
(About single assignment.) It's not possible to change the value of a variable. We say that variables are single assignment. Each variable can be assigned to only one value. Why are variables single assignment? It is because of the functional paradigm. A mathematical function is a fixed thing; it does not change once defined. Since variables are used to define functions, they have the same property.
A functional program that is correct today will still be correct tomorrow.
The functional paradigm makes it easier to write correct programs.
Higher-order programming
Higher-order programming is the ability to use functions and procedures, of course, as first-class entities in the language. So we can use them as inputs and outputs of other functions. We can have functions that are parametrized by other functions and that return functions that have new behavior. It's at the foundation of data abstraction. All the sophisticated ideas of data abstraction and object-oriented programming, classes, object, metaclasses, inheritance, and so on can be defined in terms of higher-order programming.
Procedures have two important properties: they are values, and they have a contextual environment. The combination of these two properties leads to very powerful programming techniques. In fact, we can say that the whole layered construction of data abstractions that gives today's programming systems so much power is based on procedures with these two properties! So the procedure concept, as defined here, is one of the most important concepts in all computer programming. It makes possible building large systems based on data abstraction, in layers, encapsulation. Many of the good properties are based on this key idea of higher-order programming, which is based on procedure values with a contextual environment.
Functions can hide values inside them. This is the foundation of encapsulation.
If you have higher-order programming, you can create your own sophisticated control structures (if, while, for) by defining a statement and passing it to a function which decides whether or not to execute it.
Data abstraction is built on top of higher-order programming.
Explicit state and data abstraction
In the functional paradigm, there is no notion of time
In the functional paradigm, what works now will work in the future.
In the imperative paradigm, a function can be updated without changing the interface.
Paradigms redux
This chapter is a summary of the course.
Functional programming is a basis or foundation for the other paradigms. And the technique of higher order programming, in particular, pervades all the other paradigms and gives them a lot of power. So functional programming is very important. And it's mostly because of higher order programming.
We then extended this functional programming paradigm (...) by adding multiple assignment, which we called explicit state, with a concept called cells. And this led us to object-oriented programming, data abstraction.
Bonus: on object-oriented programming and distributed systems
Peter Van Roy also talks about the limitations of OOP in the cloud era:
Object oriented programming is very good for applications that have a lot of knowledge.
So a language like Java, which is almost completely just object oriented, this is in fact too limited in practice. And in many cases, Java people spend their time inventing other concepts, and putting them in libraries, and encoding them, and so on. Lots of new things built on top. And so, Java programs are unnecessarily complex.
Object oriented programming is the wrong paradigm for internet programming. The concepts of object oriented programming are solving other things. They might be good for business applications, but they're not good for internet. So for internet applications, you need other concepts. Such as isolation, concurrency, asynchronous messages, high order programming for factoring what's relatively unimportant for the internet aspects of the language, so the distribution, fault tolerance. Inheritance, classes, methods, UML diagrams, monitors... these are not solving the problem.
People sometimes tend to think object-oriented programming is kind of a panacea, and if a language is not object-oriented, then it's not good. It's not modern. It's not advanced. But that's not true.
For example, there is a language called Erlang which is, in fact, much better for building fault-tolerant systems, systems that are able to survive both software and hardware failures, systems that can be distributed, that have high availability, which means that the chance the system is working at any instant is very high, is close to 100%.
Object-oriented programming is traditionally focused on sequential, centralized programs, programs that run on one machine and programs that have very few threads, very little concurrency. Concurrency support is very bad. Distribution support is very bad. Nowadays, we need this concurrency support. We are really seeing a strong push towards long-lived distributed systems called Services, implemented in many different ways, including on Clouds, but also peer to peer. This requires new concurrency abstractions, not just transactions, and certainly not monitors. This requires support for fault tolerance, also security. This will require language support.
OOP doesn't perform very well in distributed systems. Through large-scale distributed programming, we can observe the current limits of data abstraction languages.
In the next two decades, a lot will probably change in data abstraction languages, but principles like inheritance and polymorphism will not.
Some of these appear in an "end of lesson" video, which I recommend you to watch: https://www.youtube.com/watch?v=rKXQFZRhd3Q
Wrap
Here I only put stuff related to functional programming (and a bit of OOP), but the course has plenty of superb content about concurrency and other topics.
Let's wrap this with a fundamental statement from Van Roy:
A big program almost always needs several paradigms.
Introduction to Functional Programming
This is a course by Erik Meijer, the creator of Reactive Extensions, also offered in edX:
https://www.edx.org/course/introduction-to-functional-programming
Basics
Functional programming is programming using expressions.
Functional programming is a programming style in which expressions are more important than statements. We want to compose programs using expressions.
Expressions deliver a value. So we take 2 expressions that deliver a value and we compose them in a bigger expression.
Statements have side effects. When you compose statements the statements have an implicit side-effect on the global state and they communicate values via that global state.
On the other hand, in an expression based programming style expressions return values and we compose these values directly.
A functional programming language is a language that supports and encourages writing code using expressions.
Functional programming does not imply not using side-effects. Functional programming does not mean using pattern-matching. Functional programming means using higher-order functions (whether they are pure or not) and focusing on expressions instead of statements.
Random stuff
Haskell algebraic data types is a streamlined way to write a class hierarchy in object-oriented languages. Pattern matching is a streamlined way to do 'is' checks/tests. If you have an inheritance hierarchy in an object-oriented language you can often model it as an algebraic data type in Haskell.
Haskell, I think, is a language that is closest to the lambda calculus because it's based on pure functions, whereas in other languages lambda expressions are I think a better way would be to call them closures. Because they can close over variables in the outer scope. But these lambda expressions can have side effects.
Tail call elimination: do not create a new stack for each function call. In imperative languages you usually don't have tail call elimination. Therefore you have specialized control structures.
On side effects and purity
It is up to you as a developer to decide how much side effects to use. But it is never a good answer to say “I'm never going to use side effects” or it is also never good, the other extreme, to say “I don't care about purity”. That is exactly what shows mastery of programming that you can decide where to use side effects and where to avoid them. But if I hear you say we have to program without any side effects, you have not understood the essence of this course.
We have a sea of imperative code that interacts with the outside world with islands of pure code where you use pure functions. You have to decide how big the sea is and how big the islands are. But the answer is never that there is only sea or only islands. A good programmer knows the right balance.
Summary
Functional programming is not about avoiding mutable state but that there are many more effects, but all about composition. If you have a fellow programmer that does fall into the immutability trap, point him/her to https://queue.acm.org/detail.cfm?id=2611829. And if you want to teach your fellow programmers about the beauty of composition and higher-order APIs, point them to this classic paper https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf.
Bonus — Solving Problems the Clojure Way
If you are interested in functional programming, I strongly recommend this superb talk: