Introduction

←

↑

→

Introduction

Functional programming languages have been around since the early days of Lisp. Based on Church's λ-calculus, they have a few common characteristics.

All computation is performed by using pure functions. A function takes a parameter and produces a result. There is no notion of a side effect. There are no variables or anything that can change while a program is computing. Data structures cannot be modified.
Programs are declarative. They consist of a collection of facts.
Functions are considered values, just like other values. You can pass a function to another function, return a function as the result of a function, etc.

Functional programming

To somebody who has only used imperative programming languages, functional languages initially seem very strange, to the point of being impossible to use.

How can you compute if you cannot change anything?
How can you manage without variables?
How do you do anything without commands?

And yet, functional languages, such as Haskell, are growing in popularity.

The reason is that they tend to yield short, simple programs for some problems that would be more difficult to solve in other styles.

Function definitions written in a functional style also tend to be reliable. Programmers often find that their programs work the first time they are tried, or with only a tiny amount of fixing, far more often than even the programmers feel they have a right to expect.

Some of the ideas of functional programming are not as foreign as you might imagine.

In Java, integers have the characteristic that you cannot change them.

In Java, you can build a string, but there is no operation to modify a string. You can only compute new strings.

But Java programmers seem to get by just fine without operations that change integers or strings. (They do resort to StringBuilder objects, but they would do fine without them.)

Functional programming languages

Examples of functional programming languages are Lisp, Standard ML and Haskell. There are many others.

Not all functional languages offer only functional programming. Standard ML, for example, also offers imperative features. Here, we are interested a simple, pure language, though.

This document describes a bar-bones functional programming language called SFL, for Small Functional Language.