Functional programming, in my opinion, is one of the most important programming paradigms. It relies on the programmers ability to understand types, algorithms, and run-time steps. Also, it happens to use a great deal of mathematics. To start with functional programming, we need a language to use. In this tutorial, we’ll use Standard ML (SML). SML is almost a purely functional language I learned while I was at CMU during my sophomore fall semester.

In this part of the introduction, we’ll go over types, equivalence, and evaluation. If you’re confused along the way, I highly recommend you just try things out and write some code to do so. Also, there is a nice book by Bob Harper online, linked here. This book will help ease you in to the functional world. Now, let’s begin!

Types, Equivalence, and Evaluation

First things first, all computation is functional. That means that all functions map values to values. So if we have the add operator, it takes two numbers and maps those two numbers to another number, which is the sum. This is based off of the mathematical definition of a function: a relation between two sets. So in functional programming, we have expressions, not commands. Expressions are evaluated, and have no side effects. So doing 2 + 3 will have no effect on 2 + 5. Both will come out as values, not states.

Secondly, when writing a functional program, you’re really just explaining your problem. So you’re given a problem statement. Well, you have some invariants, a specific outcome you’re looking for (so a specification), and then some sort of assurance that you’re code is correct (a proof of correctness). So, when writing a functional program, be sure to include invariants, your specification, and have a proof of correctness. If you have all three, they will follow each other. The invariants allow you to create necessary variables. Your specification is the blueprint of your code. Finally, your proof of correctness allows you to ensure the outcome specified in the problem.

Now, in SML, there are types, expressions, and values. Some types are ints, Reals, strings, chars, and bools. An expression can be as simple as 2 + 5. These expressions must have a type. A value is a subset of an expression, as it is the final value when an expression is evaluated. So the expression 2 + 5 has type Int and will have the value of 7 when evaluated. It is important to remember that SML is a well-typed language: so an expression is well-typed if it has at least one type, otherwise it is not well-typed.

Existential Equivalence and Referential Transparency

In SML, expressions can be equivalent (note this is different than equal). This equivalence is called existential equivalence. Two expressions are existentially equivalent if they: (1) reduce to the same value, (2) raise the same error, (3) both loop forever. Functions have equivalence also. Functions are existentially equivalent if they map equivalent arguments to equivalent results. This rule allows us to have safe substitution of equivalent code.

Finally, there exists something called referential transparency for functional programs. That means the value of an expression depends only on the values of its sub-expressions. Furthermore, the type of an expression depends only on the type of its sub-expressions.