Work Plan

Introduction, types of programming languages, pseudo-code
Variables, data types
Pointers and arrays
Simple instructions and tricks
Functions and procedures
Debug
Input / Output
Data structures
Modern C++
Python
Python cont.
Functional / object oriented programming
Software development process, git, agile, tdd
Final Test during last classes: about 30 open/close questions - mostly closed.

Paradigms

There are three widely used programming paradigms: procedural programming, functional programming, and object-oriented programming.

Python supports all three programming paradigms.

Procedural

Procedural programming divides sequences of statements and conditional constructs into separate blocks called procedures that are parameterized over arguments that are (non-functional) values.

Procedural programming focuses on statements. It contains a systematic order of statements, functions and commands to complete a computational task or program.

Object-Oriented

Object-oriented programming (OOP) is a programming paradigm that uses objects and their interactions to design applications and computer programs.

Object have specific responsibilities within the program and make it simpler to design complex systems and operations.

Object oriented programs are class-based, meaning that objects are instances of classes, which typically also determine their type.

Object

Object is an abstract concept. Objects are a representation of the real world objects like cars, dogs, bike, etc. The objects share two main characteristics: data and functionality.

Object is a realization of a class that can be treated as a variable type.

This object can include multiple variables (called attributes/properties) for storing different types of data. It can also have its own set of functions (called methods), to manipulate the object's properties.

Class

A class creates a new type where objects are instances of the class.

An analogy is that you can have variables of type int which translates to saying that variables that store integers are variables which are instances (objects) of the Integer class.

It is a convention to give classes a name that starts with a capital letter.

Class in Python

Everything is a class in Python.

"One of my goals for Python was to make it so that all objects were "first class." By this, I meant that I wanted all objects that could be named in the language (e.g., integers, strings, functions, classes, modules, methods, and so on) to have equal status. That is, they can be assigned to variables, placed in lists, stored in dictionaries, passed as arguments, and so forth." (Blog, The History of Python, February 27, 2009)

Example

>>> x = 42
>>> type(x)
<class 'int'>
>>> y = 4.34
>>> type(x)
<class 'int'>
>>> def f(x):
...     return x + 1
... 
>>> type(f)
<class 'function'>
>>> import math
>>> type(math)
<class 'module'>

Class elements

Objects can store data using ordinary variables that belong to the object.

Variables that belong to an object or class are referred to as fields / attributes / properties.

A class is created using the class keyword. Like its function-based cousin def, it concerns the definition of things. While def is used to define a function, class is used to define a class.

The fields and methods of the class are listed in an indented block.

Example

class Robot:
    pass

A class consists of two parts: the header and the body.: The header usually consists of just one line of code. It begins with the keyword "class" followed by a blank and an arbitrary name for the class. The body of a class consists of an indented block of statements. In our case a single statement, the "pass" statement.

Example

class Person:
    pass  # An empty block

p = Person()
print(p)

Output:

<__main__.Person instance at 0x10171f518>

We created an object/instance of the class using the name of the class followed by a pair of parentheses.

Python can store the object in memory wherever it finds space.

Attributes

Attributes are characteristics of an object.

We can dynamically create arbitrary new attributes for existing instances of a class. We do this by joining an arbitrary name to the instance name, separated by a dot "."

class Robot:    
    pass

x = Robot() 
y = Robot()

x.name = "Marvin"
x.build_year = "1979"

y.name = "Caliban"
y.build_year = "1993"

print(x.name)

print(y.build_year)

Output:

Marvin
1993

Attributes with class

Attributes can be bound to class names as well. In this case, each instance will possess this name as well.

class Robot(object):
    pass

x = Robot()
Robot.brand = "RoboA"    
print(x.brand)

x.brand = "RoboB"
print(x.brand)

y = Robot()
print(y.brand)

Robot.brand = "RoboB"
print(y.brand)
print(x.brand)

Output:

'RoboA'
'RoboB'
'RoboA'    
'RoboB'
'RoboB'

Summary

Class attributes are shared - they can be accessed by all instances of that class. There is only one copy of the class variable and when any one object makes a change to a class variable, that change will be seen by all the other instances.

Object variables are owned by each individual object/instance of the class. In this case, each object has its own copy of the field i.e. they are not shared and are not related in any way to the field by the same name in a different instance.

Methods

Methods are functions defined inside the body of a class.

They are used to perform operations with the attributes of our objects.

Methods in class

Example:

class Robot:
    def hi():
        print("Hi, I am a Robot")


x = Robot()
x.hi()

Output:

Hi, I am Robot

Self

Methods are like functions except that we have an extra self variable added to the beginning of the parameter list.

class Robot:
    def hi(self):
        print("Hi, I am " + self.name)


x = Robot()
x.name = "Marvin"
x.hi()

Output:

Hi, I am Marvin

self points to instance of the class that execute the method.

Methods vs Functions

The proper way of defining methods of a class:: Instead of defining a function outside of a class definition and binding it to a class attribute, we define a method directly inside (indented) of a class definition. A method is "just" a function which is defined inside of a class. The first parameter is used a reference to the calling instance. This parameter is usually called self.

Init

A special method called __init__() is used to initialize an object.

__init__ is a method which is immediately and automatically called after an instance has been created. This name is fixed and it is not possible to chose another name.

The __init__ method is run as soon as an object of a class is instantiated (i.e. created). The method is useful to do any initialization (i.e. passing initial values to your object) you want to do with your object. Notice the double underscores both at the beginning and at the end of the name.

Example

class Robot:

    def __init__(self, name=None):
        self.name = name   

    def say_hi(self):
        if self.name:
            print("Hi, I am " + self.name)
        else:
            print("Hi, I am a robot without a name")


x = Robot()
x.say_hi()
y = Robot("Marvin")
y.say_hi()

Output:

Hi, I am a robot without a name
Hi, I am Marvin

When creating new instance p, of the class Person, we do so by using the class name, followed by the arguments in the parentheses: y = Robot("Marvin").

Static Methods

There is a class of methods, called static methods, that don't have access to self.

Just like class attributes, they are methods that work without requiring an instance to be present.

class Robot(object):

    def make_sound():
        print 'BpBpBp!'

Robot.make_sound()

Output:

BpBpBp

Class Methods

A variant of the static method is the class method. Instead of receiving the instance as the first parameter, it is passed the class.

class Robot():
    model = 'old';

    @classmethod
    def is_NewModel(cls):
        return cls.model == 'new'

x = Robot()
print(x.is_NewModel())
print(Robot.is_NewModel())
Robot.model = 'new'
print(x.is_NewModel())
print(Robot.is_NewModel())

Output:

False
False
True
True

Data abstraction

Part of the object oriented programming is a concept of data abstraction - which means that data should be separated and accessed only if programmer allows it.

Through the process of abstraction, a programmer hides all but the relevant data about an object in order to reduce complexity and increase efficiency.

Element that allows data abstraction through access specifiers.

Access specifiers

Attribute also have access specifying types:: name Public These attributes can be freely used inside or outside of a class definition. _name Protected Protected attributes should not be used outside of the class definition, unless inside of a subclass definition. __name Private This kind of attribute is inaccessible and invisible. It's neither possible to read nor write to those attributes, except inside of the class definition itself.

Example

class A():

def __init__(self):
    self.__priv = "I am private"
    self._prot = "I am protected"
    self.pub = "I am public"

>>> x = A()
>>> x.pub
'I am public'
>>> x.pub = x.pub + " and my value can be changed"
>>> x.pub
'I am public and my value can be changed'
>>> x._prot
'I am protected'
>>> x.__priv
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'A' object has no attribute '__priv'

Built-In Class Attributes

Every Python class keeps following built-in attributes and they can be accessed using dot operator like any other attribute −

__dict__ − Dictionary containing the class's namespace. __doc__ − Class documentation string or none, if undefined. __name__ − Class name. __module__ − Module name in which the class is defined. This attribute is "__main__" in interactive mode. __bases__ − A possibly empty tuple containing the base classes, in the order of their occurrence in the base class list.

Example

class Employee:
    'Common base class for all employees'
    empCount = 0

def __init__(self, name, salary):
    self.name = name
    self.salary = salary
    Employee.empCount += 1

def displayCount(self):
    print "Total Employee %d" % Employee.empCount

def displayEmployee(self):
    print "Name : ", self.name,  ", Salary: ", self.salary

print "Employee.__doc__:", Employee.__doc__
print "Employee.__name__:", Employee.__name__
print "Employee.__module__:", Employee.__module__
print "Employee.__bases__:", Employee.__bases__
print "Employee.__dict__:", Employee.__dict__

Output:

Employee.__doc__: Common base class for all employees
Employee.__name__: Employee
Employee.__module__: __main__
Employee.__bases__: ()
Employee.__dict__: {'__module__': '__main__', 'displayCount':
<function displayCount at 0xb7c84994>, 'empCount': 2, 
'displayEmployee': <function displayEmployee at 0xb7c8441c>, 
'__doc__': 'Common base class for all employees', 
'__init__': <function __init__ at 0xb7c846bc>}

Functional

Functional Paradigm

Functional

Functional Programming is a programming paradigm based on the evaluation of expression, which avoids changing-state and mutable data.

Popular functional languages include Lisp (and family), ML (and family), Haskell, Erlang and Clojure.

A very large percentage of program errors—and the problem that drives programmers to debuggers—occur because variables obtain unexpected values during the course of program execution. Functional programs bypass this particular issue by simply not assigning values to variables at all.

Functional

Functional language features:: Often recursive. Always returns the same output for a given input. Order of evaluation is usually undefined. Must be stateless. i.e. No operation can have side effects. Good fit for parallel execution Tends to emphasize a divide and conquer approach.

Functional elements

In functional programming, functions transform input into output, without an intermediate representation of the current state.

In functional language functions are first class (objects). That is, everything you can do with "data" can be done with functions themselves (such as passing a function to another function).

High-order functions are functions which can take functions as arguments (or return them as results).

Functions will return new data as the outcome of a computation, leaving the original input intact.

Recursion.

Iterators

An iterator is an object representing a stream of data; this object returns the data one element at a time.

The built-in iter() function takes an arbitrary object and tries to return an iterator that will return the object’s contents or elements.

L = [1,2,3]
it = iter(L)
it  

it.__next__()  # same as next(it)
next(it)
next(it)
next(it)

Output:

<...iterator object at ...>
1
2
3
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration

Generators

Generators are a special class of functions that simplify the task of writing iterators. Regular functions compute a value and return it, but generators return an iterator that returns a stream of values.

Example:

def generate_ints(N):
    for i in range(N):
        yield i

yield is a keyword that is used like return, except the function will return a generator.

The generator is considered empty once the function runs but does not hit yield anymore.

Generators do not store all the values in memory, they generate the values on the fly.

Example

>>> gen = generate_ints(3)
>>> gen  
<generator object generate_ints at ...>
>>> next(gen)
0
>>> next(gen)
1
>>> next(gen)
2
>>> next(gen)
Traceback (most recent call last):
File "stdin", line 1, in <module>
File "stdin", line 2, in generate_ints
StopIteration

Example

In-order traversal of a tree using generators recursively.

# A recursive generator that generates Tree leaves in in-order.

def inorder(t):
    if t:
        for x in inorder(t.left):
            yield x

        yield t.label

        for x in inorder(t.right):
            yield x

Eliminating flow control statements

Eliminating flow control statements with the use of functions:

# Normal statement-based flow control
if <cond1>:   func1()
elif <cond2>: func2()
else:         func3()

# Equivalent "short circuit" expression
(<cond1> and func1()) or (<cond2> and func2()) or (func3())

# Example "short circuit" expression
>>> x = 3
>>> def pr(s): return s
>>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other'))
'other'
>>> x = 2
>>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other'))
'two'

Lambdas

lambda operator or lambda function is used for creating small, one-time and anonymous function objects in Python.

Lambda operator can have any number of arguments, but it can have only one expression. It cannot contain any statements and it returns a function object which can be assigned to any variable.

add = lambda x, y : x + y 

print add(2, 3) # Output: 5

In lambda x, y: x + y; x and y are arguments to the function and x + y is the expression which gets executed and its values is returned as output.

Build-in functions

Python functional programming built-in functions:: map() performs the passed function on each corresponding item in the specified list(s), and returns a list of results. reduce() performs the passed function on each subsequent item and an internal accumulator of a final result; for example, reduce(lambda n,m:n*m, range(1,10)) means "factorial of 10" (in other words, multiply each item by the product of previous multiplications). filter() uses the passed function to "evaluate" each item in a list, and return a winnowed list of the items that pass the function test.

By combining these three FP built-in functions, a surprising range of "flow" operations can be performed (all without statements, only expressions).

In Python 3, reduce() is not a core built-infunction anymore and it has been moved to functools (still part of the standard library), i.e. in order to use it you need to import it as follows:

from functools import reduce

Map

Map functions expects a function object and any number of iterables like list, dictionary, etc. It executes the function_object for each element in the sequence and returns a list of the elements modified by the function object.

def multiply2(x):
    return x * 2

map(multiply2, [1, 2, 3, 4]) # Output [2, 4, 6, 8]

map(lambda x : x*2, [1, 2, 3, 4]) #Output [2, 4, 6, 8]

In Python3, map function returns an iterator or map object which gets lazily evaluated.

Filter

Filter function expects two arguments, function_object and an iterable. function_object returns a boolean value. function_object is called for each element of the iterable and filter returns only those element for which the function_object returns true.

a = [1, 2, 3, 4, 5, 6]
filter(lambda x : x % 2 == 0, a) # Output: [2, 4, 6]

Like map function, filter function also returns a list of element. Unlike map function filter function can only have one iterable as input.

Similar to map, filter function in Python3 returns a filter object or the iterator which gets lazily evaluated.

Lazy evaluation

Lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed and which also avoids repeated evaluations.

Iterators returns only element at a time, len function cannot be used with iterators.

We can not access chosen element of the sequence.

Lazy evaluation, allow creating an infinite sequence of numbers in generators.

def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

Replacing loops

for e in lst:  func(e)      # statement-based loop
map(func,lst)           # map()-based loop

Map-based action sequence:

# let's create an execution utility function
do_it = lambda f: f()

# let f1, f2, f3 (etc) be functions that perform actions

map(do_it, [f1,f2,f3])   # map()-based action sequence

Example

Finding intersection of two lists:

a = [1,2,3,5,7,9]
b = [2,3,5,6,7,8]
print filter(lambda x: x in a, b)

Output:

2,3,5,7

Determining the maximum of a list of numerical values by using reduce:

f = lambda a,b: a if (a > b) else b
reduce(f, [47,11,42,102,13])

Output:

Sorting

sorted() is a built-in function that builds a new sorted list from an iterable.

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

sorted() have a key parameter to specify a function to be called on each list element prior to making comparisons.

student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]
sorted(student_tuples, key=lambda student: student[2])   # sort by age

Output:

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Benefits

Functional programming forces you to break apart your problem into small pieces. Programs are more modular as a result. It’s easier to specify and write a small function that does one thing than a large function that performs a complicated transformation.

Testing and debugging a functional-style program is easier.

A theoretical benefit is that it’s easier to construct a mathematical proof that a functional program is correct.

Composability - assemble new programs by arranging existing functions in a new configuration and writing a few functions specialized for the current task.

Foundations of programming

Work Plan

Paradigms

Procedural

Object-Oriented

Object

Class

Class in Python

Example

Class elements

Example

Example

Attributes

Attributes with class

Summary

Methods

Methods in class

Self

Methods vs Functions

Init

Example

Static Methods

Class Methods

Data abstraction

Access specifiers

Example

Built-In Class Attributes

Example

Functional

Functional

Functional

Functional elements

Iterators

Generators

Example

Example

Eliminating flow control statements

Lambdas

Build-in functions

Map

Filter

Lazy evaluation

Replacing loops

Example

Sorting

Benefits

References