Programing Paradigms

Programing Paradigms

Some of the more common paradigms are

• 
  Imperative — Control flow is an explicit sequence of commands.
  
• 
  Declarative — Programs state the result you want, not how to get it.
  
• 
  Structured — Programs have clean, goto-free, nested control structures.
  
• 
  Procedural — Imperative programming with procedure calls.
  
• 
  Functional (Applicative) — Computation proceeds by (nested) function calls that avoid any global state.
  
• 
  Function-Level (Combinator) — Programs have no variables. No kidding.
  
• 
  Object-Oriented — Computation is effected by sending messages to objects; objects have state and behavior.
  
  • 
    Class-based — Objects get their state and behavior based on membership in a class.
    
  • 
    Prototype-based — Objects get their behavior from a prototype object.
    
• 
  Event-Driven — Control flow is determined by asynchronous actions (from humans or sensors).
  
• 
  Flow-Driven — Computation is specified by multiple processes communicating over predefined channels.
  
• 
  Logic (Rule-based) — Programmer specifies a set of facts and rules, and an engine infers the answers to questions.
  
• 
  Constraint — Programmer specifies a set of constraints, and an engine infers the answers to questions.
  
• 
  Aspect-Oriented — Programs have cross-cutting concerns applied transparently.
  
• 
  Reflective — Programs manipulate their own structures.
  
• 
  Array — Operators are extended to arrays, so loops are normally unnecessary.
  

Functional Programming Features

Here's a (non-exhaustive) list of FP features:

1. 
   First-Class Functions
   
2. 
   High-Order Functions
   
3. 
   Pure Functions
   
4. 
   Closures
   
5. 
   Immutable State
   

First-Class Functions: mean that you can store functions into a variable.
High-Order Functions: mean that functions can return functions or receive other functions as params.
Pure Functions: mean that the function doesn't change any value, it just receives data and output data, just like our beloved functions from Mathematics. That also means that if you'd pass 2 for a function f and it returns 10, it'll always return 10. Doesn't it matter the environment, threads, or any evaluation order. They don't cause any side-effects in other parts of the program and it's a powerful concept.
Closures: mean that you can save some data inside a function that's only accessible to a specific returning function, i.e the returning function keeps its execution environment.
Immutable State: means that you can't change any state at all (even though you can get a new state). 

Functional Programming Terms (Slide 4)

Immutable State: means that you can't change any state at all (even though you can get a new state). 

First-Class Functions: mean that you can store functions into a variable.

Recursion: Simply when a function calls itself…

• 
  "The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."
  
• 
  Functional Languages do recursion better than other languages because they have to! The key concept is pure functions with no state or side effects. Results in more efficient implementation by complier.
  

Tail Call Optimization: special form of recursion (Tail-Recursion) where you can avoid having to avoid allocating a new stack frame for a function. (Scheme, Javascript (ES6) force this)

• 
  Traditional Recursion: preform calculations/operations first then execute recursive call, passing result of current step to next step. Don’t get result until you have returned from every recursive call.
  
• 
  Tail Recursion: preform calculations/operations then execute receursvie call, passing result of current step to next step. The return value of any given recursive step is the same as the return value of the next recursive step
  

Map (Higher-Order Function): map(func, list) given a function applies that function to each element in an a list.

Reduce (Fold, Accumulate): reduce(func, list) reduce takes a seed and apply a function co-recursively to a list.

• 
  Co-recursively: CS Term, type of dual recursion…
  

Pipelining: Technique and operation in some languages where you can perform successive operations on the same input set.

Currying: Technique of evaluating a function with multiple arguments as a sequence of functions with a single argument.

Higher Order Functions: Does at least one of the following:

• 
  Takes one or more functions as an argument
  
• 
  Returns a function as its result
  

Lazy Evaluation (Call-by-Need): Evaluation strategy which delays the evaluation of its expression until its value is needed (non-strict evaluation) Benefits Include:

• 
  The ability to define flow control (structures) as abstractions instead of primitives
  
• 
  Defining potentially infinite data structures
  
• 
  Performance improvements by avoiding needless calculations
  
• 
  Memory footprint reduction
  

Monad: Simply defines what it means to chain operations together.

Higher Order Functions Map (Slide 6)

Two of Python’s built-in functions, map() and filter(), are somewhat obsolete; they duplicate the features of list comprehensions but return actual lists instead of iterators.

map(f, iterA, iterB, ...) returns a list containing f(iterA[0], iterB[0]), f(iterA[1], iterB[1]), …
def upper(s):

... return s.upper()
map(upper, ['sentence', 'fragment'])

['SENTENCE', 'FRAGMENT']

[upper(s) for s in ['sentence', 'fragment']]

['SENTENCE', 'FRAGMENT']

Higher Order Functions Filter (Slide 7)

filter(predicate, iter) returns a list that contains all the sequence elements that meet a certain condition, and is similarly duplicated by list comprehensions. A predicate is a function that returns the truth value of some condition;

>>> def is_even(x):

... return (x % 2) == 0

>>> filter(is_even, range(10))

[0, 2, 4, 6, 8]

Using List Compreshension:

>>> [x for x in range(10) if is_even(x)]

[0, 2, 4, 6, 8]

filter() also has a counterpart in the itertools module, itertools.ifilter(), that returns an iterator and can therefore handle infinite sequences just as itertools.imap() can.

Higher Order Functions Reduce (Slide 8)

reduce(func, iter, [initial_value]) doesn’t have a counterpart in the itertools module because it cumulatively performs an operation on all the iterable’s elements and therefore can’t be applied to infinite iterables. func must be a function that takes two elements and returns a single value. reduce() takes the first two elements A and B returned by the iterator and calculates func(A, B). It then requests the third element, C, calculates func(func(A, B), C), combines this result with the fourth element returned, and continues until the iterable is exhausted. If the iterable returns no values at all, a TypeError exception is raised. If the initial value is supplied, it’s used as a starting point and func(initial_value, A) is the first calculation.

>>> import operator

>>> reduce(operator.concat, ['A', 'BB', 'C'])

'ABBC'

>>> reduce(operator.concat, [])

Traceback (most recent call last):

...

TypeError: reduce() of empty sequence with no initial value

>>> reduce(operator.mul, [1,2,3], 1)

6

>>> reduce(operator.mul, [], 1)

1
>>> reduce(operator.add, [1,2,3,4], 0)

10

>>> sum([1,2,3,4])

10

>>> sum([])

0

Partial Functions (Slide 10)

The functools module in Python 2.5 contains some higher-order functions. The most useful tool in this module is the functools.partial() function.

The constructor for partial takes the arguments (function, arg1, arg2, ... kwarg1=value1, kwarg2=value2). The resulting object is callable, so you can just call it to invoke function with the filled-in arguments.

Demo (Slide 12)

In Python 2.7 functional is comparable to iterative solutions but for Python 3.5+ is significantly faster.

Directory: courses
courses -> Algorithms for Register Allocation Andrew Pardoe
courses -> Ieor 4600 Mixed-Integer Rounding Inequalities
courses -> San José State University Social Science/Psychology Psych 175, Management Psychology, Section 1, Spring 2014
courses -> Kennan's Telegram (Excerpt)
courses -> The university of british columbia
courses -> A hurricane track density function and empirical orthogonal function approach to predicting seasonal hurricane activity in the Atlantic Basin Elinor Keith April 17, 2007 Abstract
courses -> Cover page need figure & title by Proposed Table of Contents
courses -> Objectives
courses -> Dr. Jeff Masters' WunderBlog

Download 55.33 Kb.

Share with your friends: