Paradigms

In this lecture we're taking a look at various programming languages categories and illustrate the resulting characteristics with code samples. We'll learn the difference between imperative and declarative languages, the relevance of a type system, encapsulation, and learn why recursion is a building component of functional programming.

Lecture upshot

Programming languages are usually inspired by a set of paradigms. Not all programming problems match all paradigms equally well. By consequence it is crucial to know about basic paradigms, their possibilities and their limitations to pick the right programming language.

Paradigm definition

A programming paradigm is a relatively high-level way to conceptualize and structure the implementation of a computer program. A programming language can be classified as supporting one or more paradigms.
-- Wikipedia

In this course unit, we'll take a look at two main paradigm categories, and their various sub-categories.

• Imperative: How get somewhere, concrete step-by-step instructions
• Declarative: What is expected, in terms of inputs and outputs

Imperative paradigms

• This is our first umbrella paradigm, i.e. other paradigms are specialized form of this
• In essence, imperative programming means telling the computer how to do something, step by step.
  • How: we provide concrete instructions, indicating how to solve a problem.
  • Step by step: instructions are listed one after the other. We process them sequentially.

Primitive imperative languages

The earliest, simplest programming languages fell into that category, and instructions are often oriented on the underlying hardware.

Assembler

• Assembler sample:

section .data
    hello:     db 'Hello, World!',10    ; 'Hello, World!' plus a linefeed character
    helloLen:  equ $-hello             ; Length of the 'Hello world!' string

section .text
    global _start

_start:
    mov eax,4            ; The system call for write (sys_write)
    mov ebx,1            ; File descriptor 1 - standard output
    mov ecx,hello        ; Put the offset of hello in ecx
    mov edx,helloLen     ; helloLen is a constant, so we don't need to say
                         ;  mov edx,[helloLen] to get it's actual value
    int 80h              ; Call the kernel
    mov eax,1            ; The system call for exit (sys_exit)
    mov ebx,0            ; Exit with return "code" of 0 (no error)
    int 80h;

Quite low level. You literally have to know the eax, ebx, ... abbreviations to call a simple "system" "out" and print something to screen. That's because you are writing the human-readable equivalent of machine bytecode.

Basic

Basic at least gives us a print function, to call. There are other weird concepts though, like jumping around in the source code (GOTO instructions)

10 PRINT "Hello, World!"
20 GOTO 10

You can play around with basic programs on "https://www.quitebasic.com"

Procedural

• An early insight was that long, convoluted programs are hard to write, and even harder to understand.
• Hence, the idea to encapsulate repetitive logic into functions.
  • Code is still executed line by line, but
  • Code execution jumps into and out of functions.

ANSI C

A widespread low-level language supporting functions is the C programming language:

#include <stdio.h>

// Function declaration
int sumToN(int n);

int main() {
    int n = 100;
    int sum = sumToN(n);

    printf("The sum of numbers from 1 to %d is %d\n", n, sum);
    return 0;
}

// Function definition
int sumToN(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

C is a compiled language, so to execute it we have to convert it to machine code:

• Compile with:
  $ gcc sum.c
• This creates a new file a.out. A machine-code binary. We can just call it:
  sum.c

Why is the compiler needed ? Assembler did not need a compiler.

Assembler code is literally the human readable equivalent of machine instructions (bytecode). Running compiler comes down to translating each individial instruction into bytecode.
C however, is not a direct one-to-one version of bytecode. It is easier for us humans, but for the computer to understand, we still need to convert it to bytecode.
There's a few advantages, too: * Performance optimizations. * Catching low level mistakes, e.g. syntax errors or unreferenced variables.

Note: C still has a lot of caveats, e.g. nothing stops you from running out of array boundaries:

#include <stdio.h>

int main() {
    int numbers[] = {1, 2, 3, 4, 5};   // Array of 5 integers
    int sum = 0;
    int size = sizeof(numbers) / sizeof(numbers[0]);  // Compute array length

    // Loop over the array
    for (int i = 0; i < size; i++) {
        sum += numbers[i];   // Access each element
    }

    printf("The sum of the array elements is %d\n", sum);
    return 0;
}

Let's see what happens:

$ gcc array.c
$ ./a.out
The sum of the array elements is 17

What just happened

The c compiler does not check array dimensions are respected. Our loop just walked out the array, and added whatever value happened to be in RAM there.
C does not protect us from making stupid programming mistakes, we just obtain garbage results.

Bash

• Bash is another useful example of a procedural language.
• In contrast to C, it does not require a compiler, only an interpreter.
• You already used the bash interpreter: it is your command line !
• Bash is very handy, because it combines the power of file system access with declarative programming.
• Create directories and files
• Remove, rename directories and files
• Regular expressions
• Arrays
• Functions
• ... and the ability to call any program you installed (get webpages, extract information, send messages to webAPIs, ...)

Here's an example of program that creates 100 folders, each with a same numbered file inside:

for i in {1..100}; do mkdir $i; touch $i/$i; done

Object Oriented

• With C we've already seen how functionality can be encapsulated.
• But often you do not just want to just modularize logic, you can to modularize data.
• Object-oriented languages add the concept of classes and information hiding:
• A class defines

OO macro definition here. Class secrets / encapsulation, orientation on real world objects. Combining state and behaviour.

Strictly typed, strict encapsulation

Ideally, using an OO programming language, we have to obey to the OO rules.

• Classes strictly define what inputs and outputs they accept
• Ideally, a compiler tells us before runtime, if we violate types.
• Objects have a proper mechanism to protect their secrets
• We cannot directly access class secrets, we have to pass over the prepared access mechanisms.
• Ideally, a compiler tells us when we attempt to access something restricted.

Java has mechanisms to enforce encapsulations, but by default these are not activated.

Here's an example of a Java class representing a Car with open access on all variables:

public class Car
{

  public int remainingFuel = 50;
  public int mileage = 200;
  public int horsepower = 80;
  public int speed = 0;

  public void accelerate()
  {
    speed = speed + 10;
    System.out.println("Vroooooom");
  }

  public void slowDown()
  {
    speed = speed - 10;
    System.out.println("Screeeeech");
  }

  public void fuelUp()
  {
    remainingFuel = 100;
    System.out.println("Glug, glug, glug");
  }
}

Not strictly typed, no strict encapsulation

• Python is a good example for a language that handles things with a lot more slack than java.
• Python supports types and classes, so we might take it for a proper OO language.

Consider this example:

• We have a Car class
• The car class has a fuel field (int)
• fuel is private (__ notation)

class Car:

    # Constructor for car, here we initialize fuel with the provided int
    def __init__(self, fuel: int):
        self.__fuel = fuel  # "private" by convention

    # Driving consumes some fuel
    def drive(self, distance: int):
        """Consumes 1 unit of fuel per unit of distance"""
        if self.__fuel >= distance:
            self.__fuel -= distance
            print(f"Drove {distance} units, fuel left: {self.__fuel}")
        else:
            print("Not enough fuel!")

    # Getter to look up remaining fuel
    def get_fuel(self) -> int:
        return self.__fuel

And for a while this seems like a very reasonable programming langage:

• We can create car objects.
• We can use the get_fuel method to look up how much is remaining.
• We can drive, consuming fuel. The method won't let us drive if there's not enough fuel left.

from car import Car

## Here we initialize a Car object with 10 units of fuel.
my_car = Car(10)

print("Fuel (via method):", my_car.get_fuel())

# Normal drive:
my_car.drive(3)

# Let's check how much fuel is remaining:
print("Fuel (via method):", my_car.get_fuel())

However, turns out this language is not safe at all:

• We can bypass the fuel field ourselves, and dump fuel.
• Types are purely decorative, nothing prevents us from writing something else.
• Since there is no compiler, we do not learn about our (most of the time honest) progaming mistakes until it is too late (program execution)

## So far everything was normal, but we can totally abuse the provided code and deviate from string OO programming.
# 1) We can "steal" fuel from the car, without driving:
# (fuel is a private field, but python lets as tamper anyway)
my_car._Car__fuel = 1  # whoops, we just dumped fuel.
print("Fuel after external tampering:", my_car.get_fuel())

# 2) Even worse, although "fuel" is supposed to be an int, we can write a string inside:
my_car._Car__fuel = "infinite"  # no runtime type check
print("Fuel is now:", my_car._Car__fuel)

# This breaks logically but Python won't stop you
# Now fuel is no longer an int but a string, what will happen if we attempt to drive ?
my_car.drive(2)  # would throw a TypeError at runtime => The program will crash AT RUNTIME !

The above code is not secure

A developer can still access the "private" balance field, e.g. using my_car._Car__fuel = "inifinite". There is not even a type check!

Why is that ?

• The double underscore is purely decorative, expressing slim hope that please everyone respects the classes internals.
• The double underscore provides absolutely no language level protection from someone messing with class internals anyway. It is mostly decorative.

My two cents

I hope I'll never be on board of a plane where the manufacturer decided to implement essential components in python.

Declarative paradigms

Declarative languages is another umbrella term, with multiple adherents. In essence, declarative languages are less concerned with how you reach a result, and instead focus on what is desired.

Graphical

Most likely you've already worked with a declarative language: HTML

In HTML you only descibe what you expect to see. You do not care how the browser at a technical level translates your description into a graphical outcome.

<html>
    <body>
    <h1>I want a big fat heading.</h1>
    <h2>And then I want some subheading</h2>
    <p>... and then I want some text.</p><br/>
    <p>and then a cute image:<p>
    <img src="https://upload.wikimedia.org/wikipedia/commons/6/6e/Golde33443.jpg"/>
    </body>
</html>

Any ideas for another graphical language ?

Latex! You only descibe document content, latex handles the rest!

Here's an example of a public latex code in action, rendering a document.

Data

Retrieving data from a database often requires a lot of optimization. As a user you're rarely concerned with how exactly the data is retrieved, as long as it is rocket fast.

Database querying languages like Sequel (SQL) serve for just that: You describe what you want, not how to efficiently get it:

So for example for a database table with professors:

First Name	Last Name	Field
Alan	Turing	Theoretical CS, AI
John	McCarthy	AI, Lisp
Donald	Knuth	Algorithms, TeX
Edsger	Dijkstra	Algorithms, Software Eng
Grace	Hopper	Programming Languages
Tim	Berners-Lee	Web, Networking
Ada	Lovelace	Programming, Computation
Marvin	Minsky	AI, Robotics
Claude	Shannon	Information Theory
Leslie	Lamport	Distributed Systems
John	Backus	Programming Languages, Fortran
Richard	Stallman	Free Software, OS
Ken	Thompson	Operating Systems
Dennis	Ritchie	Programming Languages, C
Barbara	Liskov	Distributed Systems, OOP
Vinton	Cerf	Networking, Internet
Donald	Becker	OS, Networking
Andrew	Tanenbaum	OS, Networking
Bjarne	Stroustrup	Programming Languages, C++
Shafi	Goldwasser	Cryptography

You we could get all profs starring an m in their first name:

SELECT *
FROM professors
WHERE first_name LIKE '%m%';

Why is the SQL statement declarative ?

Because we do not specify HOW the database should be searched. We only describe what we want.

Functional

"[...] a functional approach involves composing the problem as a set of functions to be executed. You define carefully the input to each function, and what each function

returns - MSDN"

• is a declarative approach: The programmer defines what to execute, but not in which order.
• program is not executed line by line, but function call by function call.
  • no loops as control structures.
  • heavy use of recursion.

Recursion (recap)

In pure functional languages, you cannot program declaratively:

• You cannot use basic increments like i = i+1
• Instead you have to use recursion.

Here's a little recap of how loops can be turned into recursions:

Iterative (loop based) and recursive solutions are equally powerful, i.e. every iterative solution can be turned into a recursive solution and the other way round.

Iterative faculty computation:

  private static int facultyLoop(int n) {
    int faculty = 1;
    int i = 1;
    while (i <= n) {
        faculty = faculty * i;
        i++;
    }
    return faculty;
}

Recursive faculty computation:

private static int facultyRecursion(int i) {
    return i <= 1 ? 1 : i * facultyRecursion(i - 1);
}

Is functional programming better than imperative programming ?

Whether a problem is better solved iteratively or recursively fully depends on the problem. Some problems are more elegantly described as a recursive function and overly verbous when coded iteratively. For others it is the other way round. There is no clear winner, it all depends on the nature of the problem you're solving. However, when doing serious functional programing, an OO language like java is not the best choice. Each recursion call adds a function to the heap, other languages like Haskell have better mechanisms for handling recursion side effects.

Haskell

Haskell is considered a pure functional language (no loops).

Here's a short example of how to get a small mathematical task done using the Haskell programming language:

• Every block of two lines first defines a function (input and output types)
• The line below then defines how the result is computed, based on inputs.

-- Function to get all proper divisors of n
divisors :: Int -> [Int]
divisors n = [x | x <- [1 .. n `div` 2], n `mod` x == 0]

-- Function to check if n is perfect
sumDivisors :: Int -> Bool
sumDivisors n = sum (divisors n) == n

-- Result consumes the number as input
isPerfect :: Int -> Bool
isPerfect n = sumDivisors n

To run the program, we need the corresponding interpreter (it is also possible to compile, haskell, but printing results is little tricky then.)

$ ghci perfect.hs
GHCi, version 9.12.2: https://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Main             ( perfect.hs, interpreted )
Ok, one module loaded.

The interpreter has now loaded our haskel file, we can just call functions now.

ghci> result
True

Functional languages are a good fit for, well, functions: Mathematical problems. However, for ordinary real-world problems they tend to cause a low of headache. A program that just prints results (not using the interpreter) already requires advanced programming concepts.

Event-Driven

Event-driven languages follow simple, "if this happens then trigger that action" rules.

Graphical languages, or languages backing user interfaces often have an event driven component, to react to user interactions.

JavaScript is an example (handle mouse clicks, keystrokes etc...)

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Button Alert Example</title>
</head>
<body>

<!-- Event example: Click is an event, the action to invoke is the showAlert function. -->
<button onclick="showAlert()">Click Me</button>

<script>
    function showAlert() {
        alert("Button was clicked!");
    }
</script>

</body>
</html>

Recap

Paradigm	Focus	Common Uses	Languages
Imperative	Step by step instructions	Simple scripts, low level	Assembler, Basic
Procedural	Organizing into functions	Simple apps, teaching	C, Python, Bash
OOP	Modeling real-world entities	Large apps, GUIs	C++, Java
Concurrent	Multiple tasks at once	Real-time systems, parallel tasks	Go, Erlang
Declarative	Describe results, not steps	SQL, configs, UI	SQL, HTML, CSS
Functional	Pure functions, immutability	Math problems	Clojure, Haskell
Event-Driven	Handling events	GUIs, web apps	JavaScript, C# (for UIs)

Imperative-VS-Declarative tree

graph TD
    A[Programming Paradigms]
%% Root categories
    A --> B[Imperative]
    A --> C[Declarative]
%% Imperative descendants
    B --> B1[Procedural]
    B1 --> B1a[Assembly]
    B1 --> B1b[C]
    B --> B2[Object-Oriented]
    B2 --> B2b[Java]
    B2 --> B2c[C++]
    B --> B3[Concurrent/Parallel]
    B3 --> B3a[Go]
    B3 --> B3b[Erlang]
%% Declarative descendants
    C --> C1[Functional]
    C1 --> C1a[Haskell]
    C1 --> C1b[Lisp]
    C --> C2[Graphic]
    C2 --> C2a[HTML]

Multi paradigm languages

Some programming languages showcase significant paradigm overlaps. These are also called "multi paradigm languages".

Paradigm mismatches

We've already seen one strong paradigm mismatch: Coding OO in python.

• Just because something can be implemented in a given language, does not mean it should be, or is good programming style.
• In fact, it is perfectly to force programming constructs into a language it was not build for.
  • In the best case the code is overly complex.
  • In the worst case the code does not at all do what one would expect it to...

Use a hammer for nails, only.

When your code gets overly complicated and you have a constant feeling the language itself is restricting you from what you want to do, chances are high you're encoutering a paradigm mismatch.

OO python

• When used to strict OO principles, switching to a less OO ecosystem can result in paradigm mismatches: The developer tries to enforce a paradigm on language not primarily build for this purpose.
• Happens to most java developers coming from a Java background.
• Java easily allows OO principles like information hiding, private fields etc.
• As previously seen, in python, fields can be declared "pseudo" private, but they do not actually change in behaviour and are still accessible.

Compiled versus interpreted

• Throughout the lecture we've seen various compiled languages and various interpreted languages.
• Note that this distinction does not align with the Declarative / Imperative dichotomy.
• Some languages even support both: Haskell code can be interpreted and compiled.
• Often times compiled languages have a stricter type system, simply because you can enforce type safety at compile time, and rule out a whole category of programming mistakes.

Compiled languages

• A stricter type system
• Pre runtime optimisations
• Bytecode is usually bound to a specific platform

Why usually ?

Because you can have both, a compiler and an interpreter. Java is an example: The code is compiled, but it still needs interpretation by a JVM.

Interpreted

• Often scripts
• Often a simpler syntax
• Often no strict type system (or no types at all)

Esoteric languages

As a closing note, paradigms are not always pragmatic. The programming lanugage community sometimes tends to come up with absurd paradigms, just to demonstrate the concepts and introduce a new language.

Here's a few of my favourite:

Whitespace

• Whitespace has only two characters:
• Space
• Tab
• With that you have representatives of 0es and 1es, so you can write anything you want to write in binary.
• Here's a "Hello, World!" program in whitespace:

Image credit: Wikipedia

Don't see anything ? Me neither, that's the idea :)

An academic loophole

If your professor does not specify in which language you have to do your homework, turn in an empty sheet and state you implemented in whitespace and printed the solution for their convenience.

Ook!

Ook! is another sophisticated language. Technically it is just a variant of the Brainfuck language (a language designed to be as impossible to use as possible).

• Ook! only has a few commands, and they all sound the same, yet anything is possible.
• Here's a Hello, World! program, written in Ook!:

Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook.
Ook! Ook. Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook?
Ook! Ook! Ook? Ook! Ook? Ook. Ook. Ook. Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook! Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook. Ook. Ook? Ook. Ook? Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook. Ook! Ook.
Ook. Ook? Ook. Ook? Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook. Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook.
Ook? Ook. Ook? Ook. Ook? Ook. Ook? Ook. Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook! Ook. Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook.
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook. Ook. Ook? Ook. Ook? Ook. Ook. Ook! Ook.

Piet

Piet combines programming with modern art. The code is a canvas, and program execution corresponds to sending a pointer horizontally or vertically through the canvas. The pointer continues to run in the same direction until it hits a colour change:

Here's a Hello, World! program in Piet:

Literature

Inspiration and further reads for the curious minds:

• Microsoft - functional VS declarative
• Assembler online
• BASIC online compiler
• Haskell programming language
• Ook programming language
• Piet language

Here's the link to proceed to the lab unit: Lab 02