Programming is Math Proof: Structured Programming

Keywords:

  • Dijkstra, Edge Wyber (born 1930 Rotterdam)
  • Goto is harmful
  • Structures: sequence, selection, iteration

Three Programming Paradigms:

1. Structured Programming (1968 Dijkstra)

  • Impose discipline on direct transfer of control aka “Goto“.
  • “If/ then /else, do/while” control structures are structured.
  • Language: Pascal, etc

2. Object-Oriented ‘OO’ (1966 Ole Johan Dahl & Kristen Nygaard)

  • Impose discipline on Indirect transfer of control (Polymorphism, Inheritance, Encapsulation:constructor‘ function of class, it’s local variables = instance variables).
  • Language: C++/ C# / Objective-C, Java / JavaScript, Go, Python, etc.

OO = Data + Function
=>
Class = Object + Method

3. Functional Programming ‘FP’ (1958 John McCarthy’s LISP language, based on Math “Lambda Calculus” from Alonzo Church 1936).

In LISP: Data = Function

  • Impose discipline upon assignment (side effect, immutability of data, Referential Transparency *).
  • Category Theory = Program : Monad, etc
  • Language: Pure FP: {Lisp, Clojure, Haskell}, Hybrid OO+FP: {Scala, Kotlin}, etc.

4. Any more ?

All Programs can be constructed from just 3 structures (Böhm and Jacopini, 1966):

Sequence / Selection / Iteration.

Dijkstra’s Math Proofs for:

1. Sequence – by simple enumeration.

  • Math Technique: trace the inputs of the sequence to the outputs of the sequence.

2. Selection – by reapplication of enumeration.

  • Each path thru the selection was enumerated. If both paths eventually produced appropriate Math results, then the proof was solid.

3. Iteration – by induction.

  • Proved the case for 1 by enumeration.
  • Assume if N case was correct.
  • Proved N+1 case correct by enumeration.
  • Also proved the starting and ending criteria of the iteration by enumeration.

Note (*): Referential Transparency means – a function (f) with a given parameter always returns the same result.

Eg. Trigonometric function (f) = sin 30 = 0.5 (always! )

In FP, a program is many layers of composition of functions of function, with each function guaranteed (math proven) always returning the same result for given parameters (aka arguments). This is software safety with no surprising unexpected result due to side effects (like database search / Web search / IO output errors).

Reference:

Clean Architecture – A Craftsman’s Guide to Software Structure and Design (by Robert C. Martin)

[Singapore National Library NLB #004.22]