For many, programming nowadays means writing some code in an object oriented programming language such as C#, Java or C++ at a lower level. Well, those are the mainstream languages nowadays and the reigning paradigm is the object oriented one.
What is a programming paradigm? It's a philosophical and theoretical framework within which solutions to problems of algorithmic nature are formulated. What a definition! Well, to say it simpler, a paradigm represents a way of thinking, thus a programming paradigm is one way of thinking about programming.
Let's take for example C#, Java, C++, etc. They're all in fact imperative object oriented languages. How do you think about programming when you use an imperative language? You're thinking in state, which is a snapshot of your machine's memory. Can you guess what I was thinking about when John Doe asked me to write a function which adds 5 to a given parameter and I wrote this?
int Add5(int x) { for (int i = 0; i < 5; i++) { x++; } return x; }
This is what I thought: "x comes with a value, stored somewhere. I can add 1 to that value and store it again. So now I have x+1 instead. The next time I add 1, I'll have x+2. If I add 1 five times... bingo!"
Ok, if I did think that "smoothly" it'll take hours to write the simplest program, and I would be fired in a couple of days. I, as any imperative programmer, do it pretty naturally, but that's because we have assumed and internalized the paradigm!
That kind of reasoning ("I have this value stored here, then I transform it in this way, then I transform the result in that way, etc") is exactly what we do when we demonstrate correctness of an imperative program according to a specification.
And that happens in general: the mechanisms to prove correctness of a program in a given paradigm are deeply connected with the way we think when we write programs in that paradigm.
An alternative to the imperative paradigm is functional programming. This one may not be that familiar to all programmers, since it's more rarely used in industry. Those with an academic background will know it for sure.
What are we thinking of when we program with a functional language? We are thinking in composing and applying functions. There's no state here. If we need to repeat some task, we make use of recursion. Programs look a lot more like math equations than in imperative. Functional programming lovers, say a functional program is so much more declarative and self-evident than an imperative one. I agree, but that's true once you got used to think "in functional". At first, if you come from imperative programming, it's not that easy to get it.
Let's see our completely useless "Add5" function written in Haskell, a functional programming language:
add5 :: Int -> Int add5 x = addN 5 x addN :: Int -> Int -> Int addN 0 x = x addN n x = 1 + addN x (n-1)
I had to use an auxiliary function called addN, which let's me recurse over N and repeatedly add 1 five times. That's what I meant when I said repetition is performed through recursion.
Now, have you noticed the arity of addN? Int -> Int -> Int. To simplify things, we could say the 2 first parts of it mean the function expects 2 ints as parameters, and the last one says it returns an int. That would work. However, it would hide the power of functional programming. In functional programming, functions are first class citizens. They can be understood as operations as usual, but they can be used as values also. They can even be data structures. The way to parenthesize Int -> Int -> Int, is Int -> (Int -> Int). What does that mean? addN is a function which takes an Int and returns another function! The arity of the new function is Int -> Int. Knowing this, we could redefine add5 in a simpler way:
add5 = addN 5
See? We don't need to use both parameters of addN at once. If we did, we would obtain an int. Instead, we just give it the first one, and we get a function! So we defined a whole family of functions by defining a single function! We can do this due to another feature of the paradigm: partial application of functions. We are partially applying addN when we just give it the first param.
This is just the top of an iceberg about functional programming. Trust me, it's amazing.
How do we prove correctness in functional programming? Basically through induction. Since the repetition artifact is recursion, and all the statements are given as equations, this mathematical tool is all we need. That's one of the advantages of not having to rely in state to perform our computations. And that gives us the clue of what we think of when we program in the functional paradigm: recursion and equations.
Finally, a third paradigm (there are dozens of paradigms!): the logic paradigm. It has a pretty famous language: Prolog.
What do we think when we program in the logic paradigm? Well, we think in what we don't know and what we do know. The result we want to get is what we don't know. The program consists in stating which are those things we don't know and we want to know (called "goals") and stating which things are true (called "knowledge base"). Let's go back to add5, now in Prolog:
nat(zero). nat(suc(X)): - nat(X). add(zero, X, X). add(suc(X), Y, suc(Z)) :- add(X, Y, Z). add5(X, Y) :- add(X, 5, Y).
I also needed to define a couple of auxiliaries. First of all, in Prolog all our statements are predicates. A program is a set of predicates and a goal. In the first 2 lines, we define the naturals. We assert to things: "zero is a natural" and "if X is a natural, then suc(X) is a natural". Then we define the relation "add". First we say that the result of adding zero to any number is the same number. Then we say, "if I add one to one of the operands, then the result also must be greater by one". As in functional, repetition is expressed through recursion. Then we define add5 in terms of add.
To execute this program, we have to ask Prolog to find what we don't know in terms of this knowledge base. We would do it like this:
? add5(10, X)
And Prolog would answer 15. If there were more than one feasible result, we could ask Prolog to return another answer. The question means: "find any X such that add5(10, X) is true". Prolog then tries to infer X from the given knowledge base.
How do we prove correctness? Well, the answer is... we don't! The one who proves correctness in this case is Prolog. We just state truths, then Prolog proves that the result it found is correct according to those proves.
Knowing more than one programming paradigm helps us think in different ways when it comes to solving a problem. You may not use many of them usually, but it's a great mind exercise to at least try them a couple of times. If you didn't yet, I hope this post encourages you to take a look at them!
Martin