Programming Paradigms

The earliest Turing complete programming paradigm was non-structured.

The non-structured paradigm can be found in both high level and low level languages. The flow of programs in non-structured languages use jumps to labels or addresses. In many of these languages line numbering is important with “goto” statements being the jump that moves to the line number or label. Non-structured programming is therefore hard to read and produces spaghetti code, though it’s proponents, such as Donald Knuth, argue that structured programming can be just as hard to understand.

Structured programming was designed to improve the flow and readability of programs.

It became popular after a letter by Edsger Dijkstra was published titled “Go To Statements Considered Harmful”. The Structured Programming theorem states that a group of flowcharts, or more generically control flow graphs, can compute any computable function by combining subprograms in one of three ways: sequence, selection, or iteration. Sequence combines subprograms in a linear fashion with one performed followed by another. Selection uses a boolean expression to decide which subprogram to perform. Iteration repeatedly runs a subprogram as long as a boolean expression is true.

Structured programming uses control flow constructs like if/else, loops, blocks, and subroutines to guide the flow of a program rather than unstructured jumps to different areas of code. Subroutines are a callable unit of code such as a function or method that allows a sequence of instructions to be referenced by a single statement. Block structured languages have syntax for formally enclosing sets of instructions into blocks of code that are wrapped by some sort of block identifier and closer like {} in C based languages or BEGIN…END in Pascal.

While you won’t see GoTo statements in modern languages, you’ll be hard pressed to find fully structured languages too.

There are several deviations from structured programming that modern languages use to be more efficient. The most often used deviation is the return statement or the early exit from a loop or function. In many cases multiple exits from a function are desirable, even Kent Beck and Martin Fowler suggested having multiple exits in their book on refactoring. The biggest concern is memory leakage because of lack of clean up from leaving too early, but this is handled in most modern managed languages.

A specific type of early exit that violates the single exit principle of structured programming is exception handling. Proponents of error handling in structured programming state that at the time Dijkstra wrote the rules of structured programs that error handling was not in place. A less common deviation is the state machine which will have several states that are not easily converted into structures. State changes tend to be implemented with a jump to the new state. This can be seen in parsers, communication protocols, and the Linux kernel.

Imperative programming changes the state of the program or machine through code written by the programmer.

Imperative programming focuses on how a computer performs operations by expressing commands for the computer to perform. Recipes are a good example of a real world imperative paradigm. Each step in the recipe is an instruction and the real world holds the state. In low level imperative languages statements are instructions that can be translated down to the native machine language. State is then defined by what is in memory. At the lowest level, hardware implementations are all imperative as it is designed to execute imperative machine code to change the state of the machine. Higher level languages use assignment statements to assign values in memory for later use allowing the program to evaluate complex expressions. They also apply the aspects of combining subprograms, blocks, and subroutines of structured programming with selection, iteration, and sequence.

Procedural languages apply the imperative paradigm by grouping sets of instructions into procedures.

Procedural programming is a form of structured programming where the state changes are localized to explicit arguments or procedures. Procedures, sets of instructions, are a series of steps for a computer to follow when executing a program. They may be called at any point in a program, even from other procedures or recursively. Modularity is important in procedural programming as it limits the interaction the procedure has with the execution environment by specifying input arguments and return values. Scoping in languages is a way to keep procedures from accessing variables of other procedures.

Object Oriented languages group sets of instructions based on the parts of the state on which they operate.

Objects in Object-Oriented programming contain both data and the code that acts upon that data. Data is stored as fields, properties, or attributes and code is in the form of methods or procedures. Object oriented programming (OOP) creates objects that interact with one another via side effects to perform the necessary tasks of a program. Side effects alter the state of variables outside of the local method or object. In class-based languages every object is an instance of a class with the classes containing the definition for the data types and any methods working on that object’s data. The objects are then specific instances of those classes. Classes don’t exist in prototype-based languages, objects are the main entity. Each object has a prototype, just one, which itself is an object. The data attributes and methods of a prototype are applied to all objects inheriting from that prototype.

Declarative programming is a way of designing and building programs that declare the desired results without describing the control flow or how the program gets to that result.

One of the main aims with declarative programming is to reduce or even completely remove side effects. This is accomplished by explicitly defining what a program must do in terms of a problem domain instead of defining how the program must do it. Declarative programming has a strong resemblance to mathematical and formal logic. Programs are viewed as theories of formal logic with the variables and some procedures as premises and the computations performed as deductions.

Constraint programming involves declaring a set of constraints on a variable or group of variables. Constraints are not steps in a recipe to get to a solution but properties of the solution to be found. Algorithms are not so much run as computations are solved by applying values to the variable to meet the constraints of the program. Domain-specific languages are languages that are specialized to a particular domain, such as markup languages and regular expressions. HTML only describes what should be on a webpage, not how it is rendered. The advantage of domain specificity is that the language does not have to be Turing complete, meaning it is easier for it to be completely declarative.

Functional languages use expression trees to declare values as a series of function applications.

An expression tree is an abstract data type where a binary tree structure is used to define an expression. Each node will either be terminal or have up to two children. In functional languages functions are treated as first class citizens in that they can be passed as arguments, returned from other functions, and bound by names. Smaller functions are combined modularly to create a composite program of multiple functions. It comes from the use of lambda calculus which is a system of mathematical logic that uses functions to express computations. Lambda calculus was proven to be equivalent to a Turing machine by Alan Turing himself. Purely functional programming treats functions as mathematical in that they cannot be affected by mutable state or side effects from other functions. This means that when an argument is passed into the function it will always return the same result. For example the function f(x) = x^2 always returns 4 when x=2.

Logical languages are based on formal logic, using a system of facts and rules to declare an answer to a question.

Programs in logical languages are sets of sentences that describe rules or facts about a problem. The rules are written as clauses for formal arguments and read declaratively. Facts are rules without a body. Programming in logical languages is basically controlled deductions. Programs are separated into control components and logic components where the logic component determines the output of the program. Stricter logical languages like Datalog are only declarative with their execution completed by a proof procedure not controlled by the programmer, whereas less strict languages like Prolog have a procedural interpretation that can be manipulated by the programmer. A Horn clause is a clause with only atomic formulae or literals. Meaning that the rules and facts are all strictly self contained without any subclauses within them. This is the simplest, most basic form, of a logical program.

In his Turing Award lecture, John Backus described a new philosophy in programming design.

Backus was a computer scientist who invented the first high level programming language (Speedcode) and lead the team that developed FORTRAN. He also invented BNF or Backus-Naur Form for the notations of formal language syntax. His Turing Award lecture which lead to the distinction between value-level languages and function-level languages was titled “Can Programming be Liberated from the von Neumann Style?” While his intent was to promote and gain interest in the FP language he developed as fully function-level the paper had more effect in gaining interest in functional programming. The von Neumann style of languages implements the von Neumann architecture which applies to any computer that stores programs where getting instructions and data manipulation cannot occur at the same time. Most modern languages apply von Neumann architecture.

Value-Level languages describe how to combine certain values with others values until an ultimate result or final value is found.

All von Neumann Style, and therefore most programming languages, are value-level languages. Expressions on the right side of an assignment statement. These build values that can be stored or used to build other values. Value-level programming studies look at the values within value-forming operations and their algebraic properties. Study of data types is a subset of studying values and focuses on the axioms or algebraic laws around the values. Even functional languages based on lambda calculus are value-level languages. The functions return a value, which can be another function, to be stored passed into another function to form yet another value.

Function-Level languages are variable free, instead they apply programs to program-forming operations or programs.

Programs are built from other programs that are given on the outset by combining them via functions or program-forming operations. Instead of creating successive sets of values function-level languages create successive sets of programs. Function-level programming allows for bottom-up semantics by enforcing very strict functions. It also doesn’t lift lower value-level to higher function-level images of an existing value-level. The difference between functional languages and function-level languages is that function-level languages have a hierarchy that goes from atoms to functions that take in one atom and return another to higher-order functions that will take in one or two functions and return another function.