Copyright (C) 2017, 2018, 2019, H. Conrad Cunningham

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.

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

1. Procedural abstraction: separate properties of action from implementation details

   Break complex actions into subprograms; develop program as sequence of calls

2. Data abstraction: separate properties of data from representation details

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

Kinds of Subprograms

1. Procedure (pure) takes zero or more arguments but does not return value; executed for effects

2. Function (pure) takes zero or more arguments and returns a value; does not have effects

3. 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)

1. Defines 3 module-level methods: has_more, incr, counter, first 2 private

2. Defines 2 module-level (object) variables: count, maxc — both part of public interface here

3. Initializes variables: count, maxc

4. 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.hs

• Relational (logic) SWI-Prolog programL Counting.pl

• Procedural Scala program: CountingProc.scala

• Modular Scala programs: CountingMod.scala CountingMod2.scala