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.
First of all, let's assume we have access to the following three
functions, and three logic operators: (
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.
The three operations also allow us to define both
even without the need for the
("Odd" "Even" "Odd" "Even" "Odd" "Even")
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.
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
Because we are counting down towards zero, we do no longer need
sub3 helper function.
defun sub2 (x y) (if (is-zero y) x ( (sub2 (pred x) (pred y)))) print (sub2 3 5))(
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))(
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.
By using the
mult function, we just created, we can
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
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.
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 (t) ((is-zero z) nil) ((same x z) t (less2 x (suc z)) ( )))defun less (x y) (if (same x y) nil (- x y)))) (less2 x ( print (if (less 8 5) ("Less" "More or equal"))
More or equal
less we are able to construct a basic
more function. We do not even need a
operator, because we can simply swap the x and y
defun more (x y) ( (less y x)) print (if (more 8 5) ("More" "Less or equal"))
Now that we are able to compare two values properly, we can finally implement the division.
By using the same method, but returning the remainder instead of
the factor q, we can define the
defun rrem (x y) (if (less x y) x ( (rrem (sub x y) y)))print (rrem 7 3))(
Using all of these functions, we build so far, we can calculate the fibonacci numbers:
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 (0) ((is-zero y) ((even y)2))) (mult2 (add x x) (ddiv y t (add x (mult2 x (pred y)))))) (2 3)(mult2
We can also do better than our current
defun pow2 (x y) (cond (1) ((is-zero y) ((even y)2))) (pow (mult2 x x) (ddiv y t (mult2 x (pow x (pred y)))))) ( 2 6)(pow2
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
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.