Acknowledgements: I created the original version of these slides in Fall 2017 and revised them in Summer 2018 to accompany what is now Chapter 2, Programming Paradigms, of the book Exploring Languages with Interpreters and Functional Programming. In Spring 2019, I created this Scala version.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of January 2019 is a recent version of Firefox from Mozilla.

Programming Paradigms

Lecture Goals

Introduce concepts of abstraction: procedural and data
Describe what is meant by term “programming paradigm”
Examine natures of the two primary programming paradigms: imperative and declarative (functional and logic)
Examine natures of other important programming paradigms: procedural, modular, etc.

Abstraction

Maxim:: Simplicity is good; complexity is bad.
Abstraction:: concentrating on the essentials and ignoring the details; remembering the “what” and ignoring the “how”

Make large complex problems understandable by decomposing into subproblems

Kinds of Abstraction

Procedural abstraction: separate properties of action from implementation details

Break complex actions into subprograms; develop program as sequence of calls
Data abstraction: separate properties of data from representation details

Identify key data representations; develop program around these and associated operations

Kinds of Subprograms

Procedure (pure) takes zero or more arguments but does not return value; executed for effects
Function (pure) takes zero or more arguments and returns a value; does not have effects
Method is procedure or function associated with object in object-oriented program; object may be implicit parameter

Good practice to maintain distinction between procedure and function even if language does not

Programming Paradigm

Timothy A. Budd. Multiparadigm Programming in Leda, Addison-Wesley, 1995, page 3:

“a way of conceptualizing what it means to perform computation, of structuring and organizing how tasks are to be carried out on a computer.”

Primary Paradigms

Historical programming language paradigms
1. imperative
2. declarative
Recent programming languages blur distinctions
But concept of programming paradigm meaningful

Imperative Paradigm (1)

Imperative program
- has implicit state (variable values, program counters, etc.)
- modified (i.e., side-effected or mutated)
- by constructs (i.e., commands)
Imperative language
- uses sequencing to precisely control state changes
Imperative program
- expresses how something computed

Imperative Paradigm (2)

    var count : Int =  0
    var maxc : Int  = 10
    while (count <= maxc) {
        println(count)
        count = count + 1
    }

State in above Scala example
- integer values of count and maxc
- output lines printed
- next statement to be executed

Imperative Paradigm (3)

    var count : Int =  0
    var maxc : Int  = 10
    while (count <= maxc) {
        println(count)
        count = count + 1
    }

State changes (side effects)
- assignment changes count value
- println adds line to output
- stepping from one statement to next

Imperative Paradigm (4)

    var count : Int =  0
    var maxc : Int  = 10
    while (count <= maxc) {
        println(count)
        count = count + 1
    }

Execution in sequence
- while causes execution zero or more times
- depending upon changing values count, maxc

Imperative Paradigm (5)

    var count : Int =  0
    var maxc : Int  = 10
    while (count <= maxc) {
        println(count)
        count = count + 1
    }

State implicit because state assumed from context
Variable count mutable because value can change—yield different values at different times
Variable maxc also mutable, but does not change here

Imperative Paradigm (6)

To allow execution, the Scala code above can be included in main method

    object CountingImp {
        def main(args: Array[String]) {
            var count : Int =  0
            var maxc : Int  = 10
            while (count <= maxc) {
                println(count)
                count = count + 1
            }
        }
    }

Imperative Paradigm (7)

An implementation using val and type inference

    object CountingImp2 {
        def main(args: Array[String]) {
            var count =  0  // use type inference 
            val maxc  = 10  // make val nor var
            while (count <= maxc) {
                println(count) 
                count = count + 1 
            }
        }
    }

Imperative Paradigm (8)

Imperative languages well suited for traditional computer architectures
Examples: Fortran, C, C++, Java, C#, Python, JavaScript, Lua
Object-oriented languages?
- different dimension of categorization
- most are imperative

Declarative Paradigm (1)

Declarative program
- has no implicit state
- any state must be explicit
Declarative program
- consists of expressions (or terms)
- that are evaluated
- not commands that are executed

Declarative Paradigm (2)

Declarative language
- repetition by recursion
- not by sequencing commands
Declarative program
- expresses what computed
- rather than how computed

Declarative Paradigm (3)

Declarative paradigm subdivided into
- functional (or applicative)
- relational (or logic)

Functional Paradigm (1)

Underlying computational model is mathematical function
- applied to zero or more arguments to compute one result
- result deterministic (or predictable).

Functional Paradigm (2)

    def counter(count: Int, maxc: Int): String =
        if (count <= maxc)
            count.toString ++ "\n" ++ counter(count+1,maxc)
        else
            ""

Above Scala example similar in meaning to earlier example
- defines function method counter
- takes integer arguments count and maxc
- returns string with integers count to maxc one per line

Functional Paradigm (3)

    def counter(count: Int, maxc: Int): String =
        if (count <= maxc)
            count.toString ++ "\n" ++ counter(count+1,maxc)
        else
            ""

Function “call” (application) of counter
- references values of explicit parameters count and maxc
- cannot change variable values within call
- can change arguments for recursive call

Functional Paradigm (4)

    def counter(count: Int, maxc: Int): String =
        if (count <= maxc)
            count.toString ++ "\n" ++ counter(count+1,maxc)
        else
            ""

Repetition of counter by recursive call
State of counter explicit because passed in arguments
Values of arguments immutable within body
Names like count and maxc (in pure functional language)
- are referentially transparent
- always have same value in same context

Functional Paradigm (5)

Previous Scala code executes no actions (i.e. no state change)
Execute main program to do input/output

    object CountingFun {
        def counter(count: Int, maxc: Int): String =
            if (count <= maxc)
                count.toString ++ "\n" ++ counter(count+1,maxc)
            else
                ""
        def main(args: Array[String]) {
            println(counter(0,10))
        }
    }

Functional Paradigm (6)

Referential transparency very important! It allows:
- subexpression evaluation in any order, even parallel
- substitution of value for variable, vice versa
In functional languages, functions often are:
- first class values, can be passed or stored
- higher-order, can take or return functions
Higher-order functions very important
- allow regular and powerful abstractions

Functional Paradigm (7)

Pure examples: Haskell, Idris, Elm, Miranda, Hope, Backus’s FP
Hybrid examples: Scala, F#, OCaml, SML, Erlang, Elixir, Lisp, Clojure, Scheme
Mainstream imperative language with functional subsets: Java 8+, C#, Python, Ruby, Groovy, Rust, Swift

Relational Paradigm (1)

Underlying computational model is mathematical relation (or predicate)
- (nondeterministic) association of group of values
- with backtracking to resolve additional values

Relational Paradigm (2)

    counter(X,Y,S) :- count(X,Y,R), atomics_to_string(R,'\n',S).

    count(X,X,[X]). 
    count(X,Y,[])     :- X  > Y. 
    count(X,Y,[X|Rs]) :- X < Y, NX is X+1, count(NX,Y,Rs).

Above SWI-Prolog example similar in meaning to earlier Java and Haskell examples
- generates string with integers from X to Y, one per line

Relational Paradigm (3)

    counter(X,Y,S) :- count(X,Y,R), atomics_to_string(R,'\n',S).

    count(X,X,[X]). 
    count(X,Y,[])     :- X  > Y. 
    count(X,Y,[X|Rs]) :- X < Y, NX is X+1, count(NX,Y,Rs).

Above defines database consisting of clauses

count(X,X,[X]). defines fact

for any variable X, list [X] with single value X, count(X,X,[X]) asserted true

count(X,Y,[]) :- X > Y. defines rule

left side of :- true if right side also true
count(X,Y,[]) true when X > Y

Relational Paradigm (4)

    counter(X,Y,S) :- count(X,Y,R), atomics_to_string(R,'\n',S).

    count(X,X,[X]). 
    count(X,Y,[])     :- X  > Y. 
    count(X,Y,[X|Rs]) :- X < Y, NX is X+1, count(NX,Y,Rs).

Can query database for missing components
- count(1,1,Z). yields value Z = [1]
- count(X,1,[1]). yields value X = 1.
- generates all components in some nondeterministic order

Relational Paradigm (5)

Can execute query counter(0,10,S), print value of S with following rule

    main :- counter(0,10,S), write(S).

Relational Paradigm (6)

Imperative and functional languages run computation in one direction yielding one answer
Prolog can run computation in multiple directions yielding multiple answers
Example relational languages: Prolog, Parlog, miniKanren
Most Prolog implementations not pure, have imperative features (cut, assert and retract clauses)

Procedural Paradigm (1)

Subcategory of imperative paradigm
- organizes programs primarily using procedural abstractions
- may limit variable/subprogram scope by nesting

Procedural Paradigm (2)

    object CountingProc {
        def counter(count: Int, maxc: Int) {
            var kount = count  // cannot change parameter value
            def has_more(count: Int, maxc: Int) = // Boolean
                count <= maxc 
            def incr {
                kount = kount + 1
            }
            while (has_more(kount: Int, maxc: Int)) {
                println(kount.toString)
                incr
            }
        }
        def main(args: Array[String]) {
            counter(0,10)
        }
    }

Call counter(0,10) similar to functional code
counter is procedure method, returns special value () of type Unit

Procedural Paradigm (3)

        def counter(count: Int, maxc: Int) {
            var kount = count  // cannot change parameter value
            def has_more(count: Int, maxc: Int) = // Boolean
                count <= maxc 
            def incr {
                kount = kount + 1
            }
            while (has_more(kount: Int, maxc: Int)) {
                println(kount.toString)
                incr
            }
        }

Has nested function has_more and procedure incr
Abstracts out loop test and increment action

Procedural Paradigm (4)

    def counter(count: Int, maxc: Int) {
        var kount = count  // cannot change parameter value
        def has_more(count: Int, maxc: Int) = // Boolean
            count <= maxc 
        def incr {
            kount = kount + 1
        }
        while (has_more(kount: Int, maxc: Int)) {
            println(kount.toString)
            incr
        }
    }

Scope is range of code where name accessible
local methods has_more and incr and local variable kount scopes within counter from declaration to end of block

Procedural Paradigm (5)

    def counter(count: Int, maxc: Int) {
        var kount = count  // cannot change parameter value
        def has_more(count: Int, maxc: Int) = // Boolean
            count <= maxc 
        def incr {
            kount = kount + 1
        }
        while (has_more(kount: Int, maxc: Int)) {
            println(kount.toString)
            incr
        }
    }

counter parameters count and maxc accessible within body unless hidden, are immutable
- hidden in function has_more by new parameters of same names
- accessible in procedure incr

Procedural Paradigm (6)

Primarily procedural languages:: Python, C, Fortran, Pascal, Lua, etc.

Modular Paradigm (1)

Refers more to design method than to language
Decomposes program into units (i.e. modules) that can be developed separately
Encapsulates key design and implementation details inside module (i.e. exhibits information hiding)
- expose public features through module interface
- hide private features inside module
- keep coupling among modules to minimum

Modular Paradigm (2)

Use Scala object for module here

    object CountingMod {
        var count =  0   // public, using type inference 
        var maxc  = 10   // declaration & setter/getter better practices 
        private def has_more(count: Int, maxc: Int): Boolean = 
            count <= maxc 
        private def incr {
            count = count + 1
        } 
        def counter {
            while (has_more(count,maxc)) {
                println(count.toString)
                incr
            }
        }
    }

Modular Paradigm (3)

Defines 3 module-level methods: has_more, incr, counter, first 2 private
Defines 2 module-level (object) variables: count, maxc — both part of public interface here
Initializes variables: count, maxc
Gives lexical scope in module to variables & functions
- object variables count, maxc hidden in has_more by parameters with same names
- count, maxc visible in incr, counter

Modular Paradigm (4)

    object CountingModTest {
        def main(args: Array[String]) {
            CountingMod.counter
            println("[1..20]") 
            CountingMod.count =  1
            CountingMod.maxc  = 20
            CountingMod.counter
        }
    }

Accesses public method counter, public variables count and maxc, uses qualified names

Modular Paradigm (5)

    // Alternative module defining public interface with trait
    trait CountingIF { 
        def setStart(start: Int) // setters/getters
        def getStart: Int        // Should use better Scala syntax
        def setStop(stop: Int)
        def getStop: Int
        def has_more(count: Int,maxc: Int): Boolean
        def incr 
        def counter
    }

Modular Paradigm (6)

    object CountingMod2 extends CountingIF { // Impl. 1
        private var count =  0 
        private var maxc  = 10
        def setStart(start: Int) { count = start }
        def getStart: Int = count
        def setStop(stop: Int) { maxc = stop }
        def getStop: Int = maxc
        def has_more(c: Int, m: Int) = c <= m
        def incr { count = count + 1 }
        def counter {
            while (has_more(count,maxc)) {
                println(count.toString)
                incr
            }
        }
    }

Modular Paradigm (7)

    object CountingMod2a extends CountingIF { // Impl. 2
        private var count =  0
        private var maxc  = 10
        def setStart(start: Int) {
            count = start
        }
        def getStart: Int = count
        def setStop(stop: Int) { maxc = stop }
        def getStop: Int = maxc
        def has_more(c: Int, m: Int) = 
            c != 0 && Math.abs(c) <= Math.abs(m)
        def incr { count = count * 2 }
        def counter {
            while (has_more(count,maxc)) {
                println(count.toString)
                incr
            }
        }
    }

Modular Paradigm (8)

    object CountingModTest2 { // Main module
        def main(args: Array[String]) {
            CountingMod2.counter
            println("[1..20]")
            CountingMod2a.setStart(1)
            CountingMod2a.setStop(20)
            CountingMod2a.counter
        }
    }

Modular Paradigm (9)

Most modern languages support “modules” in some way
Some languages (e.g. Standard ML) provide advanced support for encapsulation and multiple implementations of interfaces
Scala’s object-oriented features offers several possibilities (traits, objects, classes, packages, access controls)

Other Programming Paradigms

Object-based paradigms (object-based, class-bassed, object-oriented, prototype-based) – Chapter 3
Concurrent paradigms – future
etc.

Key Ideas

Procedural and data abstraction
Imperative paradigm expresses how something computed
- implicit state modified by constructs to control sequencing of assignment commands
Declarative paradigm expresses what is computed
- no implicit state for expressions that are evaluated using recursion for repetition

Source Code

Imperative Scala programs: CountingImp.scala CountingImp2.scala
Functional Scala program: CountingFun.scala
Relational (logic) SWI-Prolog program: Counting.pl
Procedural Scala program: CountingProc.scala
Modular Scala programs: CountingMod.scala CountingMod2.scala

Exploring Languages with Interpreters and Functional Programming Chapter 2 Programming Paradigms Scala Version