#+DATE: [2026-04-09 Thu 11:00]
#+TITLE: Functional Programming EZ
#+AUTHOR: Joshua Branson
#+TAGS: functional programming
#+SUMMARY: A conceptual overview of functional programming and why to use it.
#+OPTIONS: toc:nil
#+STARTUP: showall

For quite some time, I have been inspired by the GNU project and Richard Stallman (1).  His writings and talks convinced me to use Emacs and the Scheme programming language.  Scheme is essentially programming language [[https://www.youtube.com/watch?v=iSmkqocn0oQ][nirvana]].  If you have never tried learning any lisp-like language, then give Scheme a try.  It is [[https://www.youtube.com/watch?v=tA1clbGDczI][weird and cool]], and the Scheme family of languages, in particular, encourage you to use [[https://www.youtube.com/watch?v=HlgG395PQWw][functional programming]].  Note that the best way to learn any lisp like language, is to use a good editor like Emacs with paredit or [[https://docs.racket-lang.org/drracket/][Dr. Racket]].

I've been interested in the functional programming paradigm for a while, but I've yet to write any practical code in that style.  GNU Guix's build daemon, Dave Thompson's Haunt, and the GNU Guile compiler is written in the functional style.  I recently wanted to learn /what is/ functional programming.  This is the first blog post that gives a quick and easy overview of functional programming.  If you like this quick introduction, then be sure to read the later more in depth blog posts.

Let's start with giving a quick look at [[https://en.wikipedia.org/wiki/Imperative_programming][imperative programming]] and  [[https://en.wikipedia.org/wiki/Object-oriented_programming][object oriented programming]], which functional programming is not.  Let's examine imperative programming first.

Imperative programming is like talking to a robot.  You tell the robot to first clean the kitchen, then take out the trash, next rob the bank...the usual things.  Imperative programming is giving the computer a list of commands to be completed in sequence.  Here's a simple example of imperative programming to find the [[https://www.geeksforgeeks.org/c/c-program-to-check-prime-number-by-creating-a-function/][prime numbers less than 10]].

#+BEGIN_SRC c
  int is_prime (int n) {
    for (i = 2; i <= (sqrt n); i++) {
      if (n % i == 0) {
        return 0;
      }
    }
    return i;
  }

  for (i = 2; i <= 10; i++) {
    if (is_prime (i))
      printf ("%d ", i);
   }
#+END_SRC

If you choose to write a program in C, then you are usually writing in the imperative style.  There are no objects.  A good programmer developing imperatively will avoid mutable global variables, use good data structures, and have sensibly named /procedures/.  I believe a good portion of the Linux kernel is written this way.

Now let's consider object oriented programming.  Most people are familiar with this style of coding.  The programmer creates multiple objects.  Each object has methods which manipulate data.  It's a really nice abstraction.  Java really popularized object oriented coding.  Here's a object oriented coding style featuring java.

[[https://www.naukri.com/code360/library/print-prime-numbers-from-1-to-n-in-java][link to the java source code:]]
#+BEGIN_SRC java
  import java.util.Scanner;

  public class PrimeNumberExample {
      public static void main(String[] args) {
          Scanner scanner = new Scanner(System.in);
          System.out.print("Enter a number to check: ");
          int num = scanner.nextInt();
          scanner.close();

          if (isPrime(num)) {
              System.out.println(num + " is a prime number.");
          } else {
              System.out.println(num + " is not a prime number.");
          }
      }

      /**
       ,* Checks if a positive integer is a prime number.
       ,* @return true if the number is prime, false otherwise.
       ,*/
      public static boolean isPrime(int number) {
          // Numbers less than or equal to 1 are not prime
          if (number <= 1) {
              return false;
          }

          // Check for factors from 2 up to the square root of the number
          for (int i = 2; i * i <= number; i++) {
              if (number % i == 0) {
                  return false; // Found a divisor, so it's not prime
              }
          }

          return true; // No divisors found, so it's prime
      }
  }
#+END_SRC

Object Oriented coding is typically the norm.  It just makes sense for the average coder to code this way.  If you mutate a variable, you are normally only modifying one isolated object's variable.  Object Oriented programming tries to minimize global variables, by grouping variables to objects.  This way you can mutate state of on object and not mutate global state.

If you are not a programmer, just know that having lots of global variables that you can change at anytime is a recipe for disaster.  *Don't do it!*

Now that we've considered the other styles of coding, let's consider functional programming.  Let's start by defining it.  Functional programming does not have loops (like =while= or =for=) and does not change the value of variables.  All variables are constant or immutable.  You might find writing code without =while= or =for= loops strange at first.  Instead of loops, repetitive code is written via functions calling themselves, which is called recursion. It feels odd the first time you try it, but once you wrap your head around it, recursion is so much easier to use!  Most repetitive processes are easier to write via recursion. Additionally, in the functional programming jargon a /function/ is defined as a subroutine that is written in the functional style. A /procedure/ is any subroutine that is written in any style: functional or not.  With our first bit of jargon out of the way, let's compare loops vs. recursion.

First, let's imperatively sum all the numbers 1 - 10 first.

#+BEGIN_SRC scheme
  (define (Σ-imperatively number)
    "Sum the numbers 1 - n. Σ or sigma is the mathmatical symbol for sum of numbers.  I just wanted to show that scheme procedures can have pretty much any arbitrary utf-8 character in them.  Cool right?"
    (do ((i 0 (1+ i))
         (n 0 (+ n i)))
        ((> i number)
         n)))
  (Σ-imperatively 10)
#+END_SRC

This is a /procedure/, (not a /function/), because it uses a loop, and the value of =i= and =n= change during program execution.  Now let's consider how you might sum the numbers via recursion.  This is the intuitive/easy/lazy/slow way to do it.  It has some short comings that later blog posts will explain.

#+BEGIN_SRC scheme
  (define (naive-sum-function n)
    (let loop ([i 1])
      (if (> i n)
          0
          (+ i (loop (+ 1 i))))))
#+END_SRC

Notice that the recursion version only has one variable instead of two.  :) At first glance, it may look like the value of =i= increases during program execution.  Let me assure you that it does not.  Let's use the /substitution method/ to expand the program to show that there is no variable =i= whose value ever changes.

#+BEGIN_SRC scheme
  (loop i) ; i starts equal to 1
  (loop 1)
  (+ i (loop (+ 1 i)))
  (+ 1 (loop (+ 1 1)))
  (+ 1 (loop 2))  ; (loop 2) creates a new unique i equal to 2
  (+ 1 (+ i (loop (+ 1 i))))
  (+ 1 (+ 2 (loop (+ 1 2))))
  (+ 1 (+ 2 (loop 3))) ; (loop 3) creates a new unique i equal to 3
  (+ 1 (+ 2 (+ i (loop (+ 1 i)))))
  (+ 1 (+ 2 (+ 3 (loop (+ 1 3)))))
  (+ 1 (+ 2 (+ 3 (loop 4))))
  ;; etc.
#+END_SRC

The value of the variable =i= never changed.  Instead each time the procedure =loop= was called, a new variable =i= was created.  This is what =SICP= calls a "linear recursive process", which is smart talk for inefficient.  This above function =(let loop= works, but it create 10 different =i= variables. way to write that loop construct.  It is the easiest.

#+BEGIN_SRC scheme
  (define (efficient-sum-function n)
    (let loop ((i n) (sum 0))
      (if (> i 0)
          (loop (1- i) (+ sum i))
          sum)))
  (efficient-sum-function n)
#+END_SRC

#+BEGIN_SRC scheme
  (loop i sum) ; i = 10 & sum = 0
  (loop (1+ i) (+ sum  i))
  (loop (1+ 10) (+ 10 ))
  (loop 9 10)  ; i = 9 & sum = 10
  (loop (1+ i) (+ sum i))
  (loop (1+ 9) (+ 9 10))
  (loop (8 19)) ; i = 8 & sum = 19
  (loop (1+ i) (+ sum i))
  (loop (2+ 8) (+ 8 19))
  (loop 7 27) i = 7 & sum = 27
  ;; etc.
#+END_SRC

I do wish that emacs's flycheck mode had a scheme linter that you highlight linear recursive process and encourage you to rewrite them to linear iterative process.  One of the [[https://spritely.institute/][brilliant spritely.institute developers]] told me that classifying procedures as linear or iterative via static analysis is only possible for a subset of programs.

At this point, the reader may be wondering, what is the point of functional programming ?  Why should one use it?  You should use functional programming because, it allows you to craft deterministic programs.  For example, junior programmers may write a program that uses lots of mutable global variables, which is an easy way to create a buggy program, especially if you use threads.  This is not possible in a functional program.  A purely functional program can use threads without fear of data races (you will still have logic bugs of course).

Still not convinced? I actually recently read a blog post that really sold functional programming well.  It said that removes all the un-needed features of programming languages.  For example, the =C= programming language has the =goto= keyword.  It allows you to precisely control your program control flow. When I was being taught =C= in college our professor had this to say about the =goto= keyword:

#+BEGIN_EXAMPLE
C has this "goto" keyword.  Never use it.
#+END_EXAMPLE

And then he never talked about it ever again! =goto=  ends up creating more headache for the user.  It is so easily mis-used.  Languages that do not have =goto= are easier to use.  Rust, for example, does not have =goto=.  The same is true for the a =null pointers= and the =return= keyword.  In functional languages, there is usually =return= keyword.  Instead the last expression that is evaluate is what is returned from the function.  This felt weird to me when I first used emacs-lisp.  In C you can return a value and end a procedure whenever you want.  In lisp like languages the last expression that you evaluate is the procedures result.

If you decide to learn the scheme programming language, which you can learn enough to be competent in a half an hour, you can ensure that your code is functional by avoiding any function that ends in =!=.  By convention, scheme functions that end in =!= are not functional.  For example, the function =!set= changes the value of a variable, ergo not functional.

I'll end this blog post by mentioning that functional programming is super cool, but this blog post is more conceptual than practical.  There's not quite enough information here to allow the reader to start making any useful functional programs.  You will have to wait until the next blog post, or perhaps dive into [[https://web.mit.edu/6.001/6.037/sicp.pdf][Structure and Interpretation of Programs]].  However, if you can wrap your head around recursion, then give it a try in whatever programming language you use, it'll REALLY help you simplify your algorithms.  You will need less variables, and it'll just work.  [[https://felleisen.org/matthias/BTLS-index.html][The Little Schemer]] is a great book that teaches you how to use recursion.

1. Some people have complained that Richard Stallman is not the best leader for the GNU project.  While I largely agree that he can be odd (maybe even weird or occasionally a "creepy old man"), I still find myself admiring the man that created the GNU project and wrote much of its early software.  He's an atheist, and I'm a Christian.  He votes Democrat, and I usually vote Republican.  I invite you to make up your own mind: [[https://stallmansupport.org/][In Support of Richard Stallman]] vs.  [[https://stallman-report.org/][The Stallman Report]]