This is the first part of a series of posts intended to teach functional programming from the ground up. It is assumed that you have programmed in some imperative language like C but no previous exposure to functional programming is assumed.

What’s Functional Programming?

In functional programming, computations are expressed as functions and their applications. This is in contrast to imperative programming where the emphasis is on commands and their execution. In a functional language problems can be expressed using simple and concise syntax, close to mathematical notation.

Functional programs can be written in many popular programming languages like Python and JavaScript. Programming languages that used to emphasize imperative Object Oriented Programming has recently started to add support for functional programming. C++ and Java are examples. This means the functional paradigm will continue to gain more mind share and is here to stay.

Functional Languages

To realize the full potential of the functional style, it is better to program in a language designed for that purpose. Most early functional languages belonged to the Lisp family. Lisps are dynamically typed and focus on functions that work with a few basic data types.

Over the years many statically typed functional languages also appeared. Languages that belong to the ML family are among the most popular. Along with the great ideas of Lisp, ML provides a rich sub-language of types. Problems are modeled by designing new types and functions that operate on them.

Two modern dialects of ML are Ocaml and Standard ML (SML).

This tutorial will use SML for code examples. This is because SML is a simple, rigorously defined language with many high quality implementations.

SML has features that enable it to scale easily to large software engineering projects. This means you can apply the skills you acquire here for solving real-world problems. Also notable is the fact that many modern statically typed functional languages like OCaml, F#, ReasonML and Haskell are strongly influenced by SML. A thorough understanding of SML and its type system, along with the functional concepts explaind in this tutorial series, will make it easy for you to pickup these languages.

Getting Ready

You will need a working installation of SML and a code editor like Emacs or Vi to work through this tutorial. You can choose to install one of the many implementations of SML. SML of New Jersey (SML/NJ) is a popular choice for beginners. PolyML is also a good choice, especially if you decide to stay with SML and use it to program multi-core machines.

On my laptop running Ubuntu, I installed SML/NJ by running:

$ sudo apt install smlnj

Typing sml at the shell will take you to the SML REPL as shown below:

Standard ML of New Jersey v110.79 [built: Tue Aug  8 23:21:20 2017]
-

The minus sign (-) is the prompt displayed by SML/NJ. It indicates that SML is now waiting for us to type something. Let’s enter a simple arithmetic expression:

- 2 + 5;

SML will now respond with:

val it = 7 : int

A few notes about the input and SML’s response:

  • The expression typed at the prompt must be terminated by a semicolon (;). If we type the <enter> key before a full expression is typed, SML/NJ will respond with a = instead of a - indicating that more input is required before a response can be generated.
  • The response tells that the result of evaluating the expression is 7 and it’s type is integer (int). SML has bound the value of the last expression to a variable caller it.

The value of the last expression evaluated by SML can be reused in the next expression by referring to the variable it:

- 2 * it;
(* val it = 14 : int *)

Note: In SML comments are enclosed by the pair of characters (* and *). In this tutorial, the response generated by SML at the REPL will be shown as a single-line comment.

All the basic arithmetic operators that we are familiar with can be applied to integers. The only deviation from tradition is that integer division and remainder are denoted by the div and mod operators respectively.

A negative integer is formed by placing the unary minus operator before the digits. This operator is represented by the ~ (tilde) character and not by the - (minus) sign.

Now you know everything to use the SML system as a simple calculator!

- 45 * 7 + 10;
(* val it = 325 : int *)

- it div 5;
(* val it = 65 : int *)

- it * ~10;
(* val it = ~650 : int *)

Functions vs Commands

At the beginning of this post, I made a claim that functions in functional languages are qualitatively different from their namesake in imperative languages. Let me explain this with a simple example.

Think about how you will express the idea of “squaring” a number in your favorite language. This is how it could be expressed as a function in C:

int square(int x) {
  return x * x;
}

Here is the same function defined in SML:

fun square x = x * x

You might have noticed that the C definition of square contains a few details irrelevant to the problem being solved. The result of the function is made available to the caller by an explicit “command” in the form of the return statement. C also requires the programmer to specify the type of the parameter and the result.

In comparison, the SML definition preserves the simplicity of mathematical notation. The idea of squaring is captured in its purest form. There are no return statements and type annotations. This does not mean SML trades type safety for code brevity. The type of the function is automatically inferred for us by the SML compiler.

If you enter the square function in the REPL, you should see the response:

val square = fn : int -> int

This means SML has correctly inferred the type of square as a function that takes an int as argument and produces an int as result. The types of all expressions are verified by the compiler. There is no dynamic type checking, allowing compiled SML code to run at full speed.

The qualitative difference of functional languages from imperative languages will become more evident as we study deeper examples in future posts.

Conclusion

The objective of this post was to lay the foundation for exploring modern functional programming using SML. In the next post we will introduce some basic features of SML that will enable you to write useful programs.

Before we say goodbye, here is a sneak peek of the topics that will be covered in future installments of this series:

  1. Types and pattern matching.
  2. Higher-order functions.
  3. Efficient implementation of important algorithms.
  4. Techniques for designing immutable data structures - queues, balanced trees.
  5. Idioms for error handling, state management etc.
  6. Working with infinite streams of data.
  7. Functional abstractions for concurrency and parallelism.
  8. Inner workings of functional language interpreters.
  9. … and more!

We will also publish lot of well tested code that you can reuse.


Note that name and e-mail are required for posting comments