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

Acknowledgements: I created 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.

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)

    int count =  0;
    int maxc  = 10;
    while (count <= maxc) {
        System.out.println(count) ;
        count = count + 1
    }

• State in above Java example

  • values of count and maxc
  • output lines printed
  • next statement to be executed

Imperative Paradigm (3)

    int count =  0;
    int maxc  = 10;
    while (count <= maxc) {
        System.out.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)

    int count =  0;
    int maxc  = 10;
    while (count <= maxc) {
        System.out.println(count) ;
        count = count + 1
    }

• Execution in sequence

  • while causes execution zero or more times
  • depending upon changing values count, maxc

Imperative Paradigm (5)

    int count =  0;
    int maxc  = 10;
    while (count <= maxc) {
        System.out.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 Java code above can be included in main method

    public class Counting {
        public static void main(String[] args) {
            int count =  0;
            int maxc  = 10;
            while (count <= maxc) {
                System.out.println(count) ;
                count = count + 1 
            }
        }
    }

Imperative Paradigm (7)

• 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)

    counter :: Int -> Int -> String 
    counter count maxc 
        | count <= maxc = show count ++ "\n" ++ counter (count+1) maxc 
        | otherwise     = ""

• Above Haskell example similar in meaning to earlier Java example

  • defines function counter
  • takes integer arguments count and maxc
  • returns string with integers count to maxc one per line

Functional Paradigm (3)

    counter :: Int -> Int -> String 
    counter count maxc 
        | count <= maxc = show count ++ "\n" ++ counter (count+1) maxc 
        | otherwise     = ""

• 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)

    counter :: Int -> Int -> String 
    counter count maxc 
        | count <= maxc = show count ++ "\n" ++ counter (count+1) maxc 
        | otherwise     = ""

• 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 Haskell code executes no actions

• Must execute IO program to do input/output

    main = do 
        putStrLn (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)

    def counter(count,maxc):
        def has_more(count,maxc): # new variables
            return count <= maxc 
        def incr():
            nonlocal count     # from counter
            count = count + 1
        while has_more(count,maxc):
            print(f'{count}')  # Py 3.6 string interpolation
            incr()

• Call counter(0,10) similar to Java fragment

• counter procedure called “function” in Python

• counter returns special value None

Procedural Paradigm (3)

    def counter(count,maxc):
        def has_more(count,maxc): # new variables
            return count <= maxc 
        def incr():
            nonlocal count     # from counter
            count = count + 1
        while has_more(count,maxc):
            print(f'{count}')  # Py 3.6+ string interpolation
            incr()

• Has nested function has_more and procedure incr

• Abstracts out loop test and increment action

Procedural Paradigm (4)

    def counter(count,maxc):
        def has_more(count,maxc): # new variables
            return count <= maxc 
        def incr():
            nonlocal count     # from counter
            count = count + 1
        while has_more(count,maxc):
            print(f'{count}')  # Py 3.6 string interpolation
            incr()

• Scope is range of code where name accessible

• Lexical scope begins at definition, ends at end of block

• has_more and incr scopes begin with definitions, end with counter body

Procedural Paradigm (5)

    def counter(count,maxc):
        def has_more(count,maxc): # new variables
            return count <= maxc 
        def incr():
            nonlocal count     # from counter
            count = count + 1
        while has_more(count,maxc):
            print(f'{count}')  # Py 3.6 string interpolation
            incr()

• counter parameters count and maxc accessible within body unless hidden

  • hidden in function has_more by new parameters of same names

  • accessible in procedure incr, but count declared nonlocal to allow assignment

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)

Each Python module is in separate file, creates separate name space

    # Python 3.6 file CountingMod.py
    count = 0                 # Notes 2,3
    maxc  = 10

    def has_more(count,maxc): # Notes 1,4
        return count <= maxc 

    def incr():               # Notes 1,4
        global count          # Note 5
        count = count + 1

    def counter():            # Notes 1,4
        while has_more(count,maxc):
            print(f'{count}')
            incr()

Modular Paradigm (3)

1. Defines 3 module-level functions: has_more, incr, counter

2. Defines 2 module-level global variables: count, maxc

3. Initializes global variables: count, maxc

4. Gives lexical scope in module to global variables & functions

   • globals count, maxc hidden in has_more by parameters with same names

   • globals count, maxc visible in incr, counter

5. Declares count as global in incr for assignment

Modular Paradigm (4)

    from CountingMod import counter
    counter()

• Imports feature counter from module CountingMod.py

• Does not make other features accessible

Modular Paradigm (5)

    import CountingMod

    CountingMod.count = 10
    CountingMod.maxc  = 20
    CountingMod.counter()

• Imports all features of module, but requires qualified names

• Allows modification of imported module’s variables

Modular Paradigm (6)

• Most modern languages support “modules” in some way

• Some languages (e.g. Standard ML) provide advanced support for encapsulation and multiple implementations of interfaces

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 Java program Counting.java

• Functional Haskell program Counting.hs

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

• Procedural Python 3 program CountingProc.py

• Modular Python 3 program CountingMod.py