What is functional programming

According to Wikipedia, functional programming is defined as

It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program.

This essentially means, that there are no variables with a state, rather, you pass through values as function arguments and changing them can only be accomplished by running a function, and using its return value.

Lisp in itself has a lot of functional components, which is why we'll be using it in the following chapters, in which we'll try to build a basic math library.

Rules

First of all, let's assume we have access to the following three functions, and three logic operators: (not, and, or)

(defun suc (x) (+ x 1))
(defun pred (x) (- x 1))
(defun is-zero (x) (= x 0))

These three operations allow us to implement most of the basic algebra operations. Before we take a look at them, though, let's write a function that allows us to compare to numbers.

Basic logic functions

(defun same (x y)
  (if (is-zero x) (is-zero y)
    (same (pred x) (pred y))))

The three operations also allow us to define both odd and even without the need for the modulo operator.

(defun odd (x)
  (if (is-zero x) nil
    (even (pred x))))
(defun even (x)
  (if (is-zero x) t
    (odd (pred x))))

(mapcar '(lambda (x)
           (if (even x)
               "Even"
             "Odd"))
        '(1 2 3 4 5 6))

("Odd" "Even" "Odd" "Even" "Odd" "Even")

Basic Arithmetic

We are able to define an add function, which is able to add two natural numbers. Notice how we are using the same function which we defined earlier.

(defun suc (x) (+ x 1))
(defun add3 (x y z)
  (if (same y z) x
    (add3 (suc x) y (suc z))))
(defun add (x y)
  (add3 x y 0))

(print (add 3 5))

8

Similarly to how we defined addition, we can define subtraction. But instead of using the z variable to count up, we use it to count down. That way we do not need the same function.

(defun sub3 (x y z)
  (if (is-zero z) x
    (sub3 (pred x) y (pred z))))
(defun sub (x y)
  (sub3 x y y))

(print (sub 3 5))

-2

Because we are counting down towards zero, we do no longer need the sub3 helper function.

(defun sub2 (x y)
  (if (is-zero y) x
    (sub2 (pred x) (pred y))))

(print (sub2 3 5))

-2

The same principle applies to the Addition as well

(defun add2 (x y)
  (if (is-zero y) x
    (add2 (suc x) (pred y))))
(print (add2 3 5))

8

As you probably know, multiplying two numbers (x * y) is the same as adding x, to itself y times. We can do the same thing with recursion.

(defun mult (x y)
  (if (is-zero y) 0
  (add2 x (mult x (pred y)))))

(print (mult 2 5))

10

By using the mult function, we just created, we can now define pow.

(defun pow (x y)
  (if (is-zero y) 1
    (mult x (pow x (pred y)))))

(pow 2 3)

8

Division

That's the easy functions done. Division is a little bit harder, because we do not want to use floating point numbers. Luckily, we can define our division to be of the format:

x = q * y + r

Where q is the factor (sometimes known as //) and r is the remainder (also known as mod or %).

Unfortunately, this requires us to have access to a less-than or greater-than comparator. By definition, we aren't allowed to use them, though, which means that we have to build them ourselves.

Advanced Comparators

We can achieve this by subtracting y from x and increasing the value until we reach x. That way we know if it less, by checking if we go past 0 whilst incrementing.

(defun less2 (x z)
  (cond
   ((is-zero z) t)
   ((same x z) nil)
   (t (less2 x (suc z))
      )))
(defun less (x y)
  (if (same x y) nil
    (less2 x (- x y))))

(print (if (less 8 5)
           "Less"
         "More or equal"))

More or equal

Using less we are able to construct a basic more function. We do not even need a not operator, because we can simply swap the x and y values.

(defun more (x y)
  (less y x))

(print (if (more 8 5)
           "More"
         "Less or equal"))

More

Divide it!

Now that we are able to compare two values properly, we can finally implement the division.

(defun ddiv (x y)
  (if (less x y) 0
    (suc (ddiv (sub x y) y))))
(print (ddiv 7 3))

2

By using the same method, but returning the remainder instead of the factor q, we can define the mod function

(defun rrem (x y)
  (if (less x y) x
    (rrem (sub x y) y)))
(print (rrem 7 3))

1

Using all of these functions, we build so far, we can calculate the fibonacci numbers:

(defun fib (n)
  (cond
   ((same n 0) 1)
   ((same n 1) 1)
   (t (add (fib (pred n)) (fib (pred (pred n)))))))

(print (fib 4))

5

Now that we are able to divide two natural numbers, we can do some more advanced calculations. This also allows us to speed up two of the functions, we wrote previously.

Let's begin with the multiplication

(defun mult2 (x y)
  (cond
   ((is-zero y) 0)
   ((even y)
    (mult2 (add x x) (ddiv y 2)))
   (t (add x (mult2 x (pred y))))))
(mult2 2 3)

6

We can also do better than our current pow function.

(defun pow2 (x y)
  (cond
   ((is-zero y) 1)
   ((even y)
    (pow (mult2 x x) (ddiv y 2)))
   (t (mult2 x (pow x (pred y))))))

(pow2 2 6)

64

Closing thoughts

That's as far as I'm willing to take this for now.

Keep in mind that this only works with natural numbers, so no negative numbers allowed.

You might be wondering: Why functional programming, and that is a reasonable question, as there doesn't appear to be a use beyond basic mathematics.

I've heard a lot of people say, that using functional programming languages, expands your way of thinking about problems and thus improves problem-solving skills. I guess it is your task to judge that.

Actually, functionally programming languages, like elixir or Haskell are still being used nowadays, for example, a fairly popular ActivityPub server called pleroma is written in elixir.