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.

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)

    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)

Defines 3 module-level functions: has_more, incr, counter
Defines 2 module-level global variables: count, maxc
Initializes global variables: count, maxc
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
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

Exploring Languages with Interpreters and Functional Programming Chapter 2 Programming Paradigms