Iterators,Generators,List comprehension and Python

     Last time in my post I discussed about how you can use python in functional programming style. Python offers iterators, generators and list comprehension which serve many useful purposes when writing simple code which require production of sequences, series etc.

So, what is an iterator?

 According to Wikipedia an iterator is similar in behavior to a database cursor. It allows the user to traverse a container which contains the value, without having the liberty to perform any iterations on it.  Though the interface and semantics of a given iterator are fixed, iterators are often implemented in terms of the structures underlying a container implementation and are often tightly coupled to the container to enable the operational semantics of the iterator. 

Iterators act like pointers which reference a value and point to the next value in the list. The basic purpose of an iterator is to allow access to a user to a value without the knowledge of its container. This gives the container to hold the value in any way it wants and the iterator assumes it as a list or sequence. Python has many objects that help implement iterators like lists, dictionary, tuples, files. 

The use of iterators saves a lot of resource. In cases you only wish to get results to a certain limit, iterators save a lot of memory as they do not require to load the complete result set to memory. They help in making a cleaner code, and work fine with infinite sequences.

In the code given below is a simple iterator for a counter.

import itertools

counter = itertools.count(10)

for i in counter:

   print i

   if i == 15:

     break 

 gives - 10,11,12,13,14,15 

 Another simple example using lists.

rand = []
i = 0
for item in range(10):
        i = i + 4
        rand.append(i)
print rand

a = iter(rand)
print a.next()
print a.next()  gives the output -

[4, 8, 12, 16, 20, 24, 28, 32, 36, 40]
4
8
>>> a.next()
12
>>> a.next()
16
>>> a.next()
20

What are generators?

 A generator is nothing but a function which is able to control the iterations, stop at a point save the context and resume from where it stopped last. A generator can generate a sequence of numbers and yields the result one at a time. Since generators return one value at a time they take up less memory and behave similar to an iterator. Generators are usually evoked in a loop. A simple Fibonacci series generator code to explain the idea of generators:-

def fibo():
        a = 0
        yield a
        b = 1
        yield b
        while 1:
                c = a + b
                a, b = b, c
                yield c
d = fibo()

This code continuously produces a element in the Fibonacci series, till any limit.

 Generators can be of many types like recursive generators, generating sequences, zero crossing detectors etc. An example for a range generator is given below:-

for i in range(100000):

        i = i + 1

        print i

What is list comprehension?

    A list comprehension as defined by python.org is a concise way of creating lists. We  are to define operations that are to be applied to each element in the list. It simplifies the code, where we have to use multiple statements to get desired output to a more shorter form. Eg:-

for x in range(10):

          squares.append(x*x)

>>>squares => [1,4,9,16,25,36,49,64,81]

while this could be done in a single statement as:-

>>>squares = [x*x for x in range(10)] 

In python it is also allowed to have nested list comprehensions.

matrix = [ [1,2,3,4],

                  [5,6,7,8],

                  [9,10,11,12]

               ]

[[row[i] for row in matrix] for i in range(4)] 

List allows supports many built-in functions which allows us to use it in place of any data structure like stacks, queues, tree etc. Eg:-

>>>stack = [1,2,3]

>>>stack.append(6) 

>>>stack => [1,2,3,6]

>>>stack.append(5)

>>>stack => [1,2,3,6,5]

>>>stack.pop()

>>> stack => [1,2,3,6]

In the pop() if we do not mention a value in the list by default it removes the last one inserted, giving the idea same as in stack. Lists find most use in functional programming aspect of python. The functions like map, filter and reduce are used with ease with lists. Eg:-

>>>map(cube, range(1,11))

>>>[1,8,27,64,125,216,343,512,729,1000]

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

>>> 10

These are a few easy techniques for generating sequences and iterations using the functions provided by iterators, generators and lists, which help make a cleaner and concise code.

  

Functional Programming in Python

 Every now and then Python amazes me with its features. It is one programming language which captures the nuances of most of the  programming styles of computation. Here we discuss functional programming with python to make your code more compact and use expression evaluation than execute a number of statements.

What is Functional Programming?

     Functional programming is a paradigm in of programming which models the computation of expressions. Programs are  executed as expressions rather than a number of statements, which do not allow state change as in imperative programming. Python does not strictly stick to functional programming but has some flavors of functional programming to it. 

     Functional programming requires functions which are First-class. They are nothing but functions  that are treated like any other values and can be passed as arguments to other functions or be returned as a result of a function. Being first-class also means that it is possible to define and manipulate functions from within other functions. Eg of a code i implemented for map function :-

def f(s):  return s.upper()

def my_map(f,s):  
  result = []
  for r in s:
        temp = f(r)
        result.append(temp)
  return result

 >>>s=['anjali','menon']
>>> my_map(f,s) => ['ANJALI','MENON']

Instead of upper you can define any function for f and any list for s and the function is applied to each element in the given list.

Pure Functions

According to Wikipedia and i quote:-
"In computer programming, a function may be described as pure if both these statements about the function hold:

1. The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change as program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices.
2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices." Eg:-

def  length(s): return len(s)

The length of the string remains the same no matter how many times you call the function length(). It only varies if you vary the input.

Referential  Transparency

Pure functions yield the same value each time they are invoked. This property is referential transparency and makes possible to conduct equation reasoning on the code- 

if y = f x and g = h y y then we should get the same result for g = h fx fx.

What are higher order functions?

Higher order functions are functions that take other functions as their parameters.Higher-order functions are very useful for refactoring code and reduce the amount of repetition. For example, typically most for loops can be expressed using maps. A function is considered as a mechanism for capturing patterns. Eg:-

def add(x,y):

   if x > y: return 0

   else: return x + add(x+1,y)

  

Python allows the use of lambda. It is a keyword used for making anonymous functions. According to Wikipedia an anonymous function (also function constant or function literal) is a function (or a subroutine) defined, and possibly called, without being bound to an identifier. Anonymous functions are convenient to pass as an argument to a higher-order function and are ubiquitous in languages with first-class functions. The lambda function should contain expressions only. Usually use of lambda while writing codes should not be done frequently. The idea is to simply write a code in lambda, think about the basic idea in the function or the best use of the function and replace lambda with def functionname!

Eg:- 

lambda x: x + 10

The are other simple functions which can be used to make your code more compact and less complicated. The use of map we can simply apply the function in map to every element given in the list.Eg:-

def  cube(x): x*x*x

map(cube, [2,4,6,8])=> [8,64,216,512]

The next one is filter, which allows to filter out the values which satisfy the expression given in the function. Also we have filterfalse which returns the opposite of filter.Eg:-

filter(lambda x: x%3 == 0 in range(10))=> [3,6,9]
 

filterfalse(lambda x: x%3 == 0 in range(10))=>[1,2,4,5,7,8]

Another one is reduce which applies the function within the list and returns the result.Eg:-

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

where in a file operator.py add function is defined.

What is closure and currying?

Closures allow functions to be nested within other functions. The value passed to functions are within parenthesis indicating the value is parsed to functions in the order the appear. Eg:-

def mul(a): return lambda (b): a*b

called as mul(3)(4) returns 12.

Currying is a technique by which if a function takes multiple arguments then it can be called as a chain of functions that take single arguments. This means that we can define a function say f(x,y) = x*y and make it as g(y) = f(2,y)= 2*y 

then replace y with 3 we have g(3)= f(2,3) = 2*3

Eg:-

def add_2(a): return add_1(b): a+b

called as add_2(3)(4) results in 7.

Python with functional programming style lessens the number of lines of code, helps in applying the built in function with less hassle and more efficiency.   

   

 

 

Unit Testing With Python

     While browsing through python and discovering new facets of python everyday, I found about unit testing feature in python. As the name suggests "Unit testing" is basically testing of code which are part of a larger module. It is nothing but a sort of white box testing where we are only bothered about whether the code gives a correct output rather than the more complex case that is how it was implemented. The advantages of using unit testing techniques is that we are able to identify the errors more easily, the fixing is simpler and most important it is less complex.

     Now when i talk about python and how it supports unit testing, there are 3 techniques that i came across. I would like to give you a gist of these techniques how you can incorporate the same while working on  python projects.

The 3 techniques are- Unit test, doctest, nose test

Why Unit test?

     Unit test is a module available for all python 2.1 and above. By importing this module in your program. The basic idea is to think of all the positive and negative inputs your program might face while its use. This way you start with all such scenarios even before actual building of code. An example for this I came across while browsing was with roman numerals. Roman numerals are meant only for counting purposes so only real life numbers are interpreted in roman numerals. So all negatives, fractions, zero find no place in roman numerals. Also they are limited to the range of 1--3999. So again anything beyond 3999 is a myth in roman. 

Now when we import unittest module we define the situations which the code will face in its test cases. We define a dictionary for every number till 3999.

•  Test for success- We then decide positive test cases where the program should run successfully and reach the desired outcome. Eg: For any number in the range of 1-3999.
• Test for failure- We then decide negative test cases where the program should throw an error as it doesn't satisfy the critiera. Eg: A number greater than 3999 or a decimal number, 0 etc. 
• Test for sanity- We test if we convert a number to roman numeral then on converting back we should obtain the number itself and not lose it to roundoffs etc. Eg: tonumber(toroman(n)) = n should give n itself.

Why DocTest?

     Doctest is an interactive python to check whether the output given is according to the desired output or not. The ways to use doctest are:-

• To check that a module’s docstrings are up-to-date by verifying that all interactive examples still work as documented.
• To perform regression testing by verifying that interactive examples from a test file or a test object work as expected.
• To write tutorial documentation for a package, liberally illustrated with input-output examples. Depending on whether the examples or the expository text are emphasized, this has the flavor of “literate testing” or “executable documentation”

     To explain it using the following example. We check the cases in which factorial conditions are to be checked. The last statement of the code imports doctest in which testmode() is used. This automatically provides testcases to the code while running it and checks for errors if any. To do so we run it using the command-- python filename.py -v. This returns a log file which shows the test cases given as input and returns ok if correct. It returns an error if it doesn't satisfy the condition.

def factorial(n:) 

  import math
    if not n >= 0:
        raise ValueError("n must be >= 0")
    if math.floor(n) != n:
        raise ValueError("n must be exact integer")
    if n+1 == n:  # catch a value like 1e300
        raise OverflowError("n too large")
    result = 1
    factor = 2
    while factor <= n:
        result *= factor
        factor += 1
    return result


if __name__ == "__main__":
    import doctest
    doctest.testmod()

 

     Now a common error, many of us may get an error that doctest doesn't have the file testmode in it. It is because we created a py file doctest.py which on running creates a file doctest.pyc. Remove the .pyc file, rename your file and try again, your file will run absolutely fine.

     Another feature is testfile(). Here it searches in any given .txt file, if it contains any python code in it and runs test cases for it and returns error message if any errors, or checks if its correct.

syntax- 

import doctest
doctest.testfile("example.txt")

Doctest also provides many options  which you can find in the doctest module like ignoring blankspaces, ellipses(...),dont accept true value flags, normalize whitespaces.

Doctest integrates tester class which has testsuites for integrating different testcases for different modules for it BASIC API. 

The advanced API has a framework as given in the figure.

                            list of:
+------+                   +---------+
|module| --DocTestFinder-> | DocTest | --DocTestRunner-> results
+------+    |        ^     +---------+     |       ^    (printed)
            |        |     | Example |     |       |
            v        |     |   ...   |     v       |
           DocTestParser   | Example |   OutputChecker
                           +---------+

It also provides objects like finder objects, parser objects, runner objects and output checker objects. It also provides debugger options which can be run under the python debugger pdb.

Why nose tool?

For nose tools testing you need to have nose installed in your systems, which can be easily done using apt - get install. Writing testcases is easier as nose collects cases from unittest.TestCase.

     Running testcases is easier as nose automatically collects as long as you follow some simple guidelines for organizing your library and test code. There’s no need to manually collect test cases into test suites. Running tests is responsive, since nose begins running tests as soon as the first test module is loaded. Nose supports fixtures at the package, module, class, and test case level, so expensive initialization can be done as infrequently as possible. It comes with builtin plugins to help in easier output capture, error finding, code coverage etc. 

The code shown below is an example code I tried for a python game. It gives a unit test skeleton for nose tools.

from nose.tools import *
from ex47.game import Room


def test_room():
    gold = Room("GoldRoom", 
                """This room has gold in it you can grab. There's a
                door to the north.""")
    assert_equal(gold.name, "GoldRoom")
    assert_equal(gold.paths, {})

def test_room_paths():
    center = Room("Center", "Test room in the center.")
    north = Room("North", "Test room in the north.")
    south = Room("South", "Test room in the south.")

    center.add_paths({'north': north, 'south': south})
    assert_equal(center.go('north'), north)
    assert_equal(center.go('south'), south)

 

On simply running nosetests on your terminal, you get the following output log:-

~/projects/simplegame $ nosetests
...
----------------------------------------------------------------------
Ran 3 tests in 0.007s

OK

Now that we have more than one way to test our code with little more ease, all we need to do now is start right away thinking of test cases for a code still in pipeline. All I can say for now is HAPPY TESTING to all!!!  

Sierpinski's Fractal

     Sierpinski's triangle is a fractal or an attractive fixed set named after the Polish Mathematician Waclaw Sierpinski. A mathematically generated pattern which can be reproduced to any order.

 How to start?

• start with an equilateral triangle with base parallel to the horizontal axis.
• Shrink the triangle to 1/2 height and 1/2 width, make three copies, and position the three shrunken triangles so that each triangle touches the two other triangles at a corner   
• repeat the earlier step with the smaller triangles.

I created these perfect Sierpinski triangles in two approaches. One way is to find the center coordinates of the screen, then finding equidistant points which form a equilateral. Another way is to by providing any 3 equidistant points. Either way we find the midpoints of the lines joining the 3 points. Then we recursively call the function which requires the parameters - the midpoints and the depth till which you need to create the fractals. The code fragment is as follows:-

def sierp(screen,color,a,b,c,deep):

        if(deep <= 0):
                tri(screen,color,a,b,c)
        else:
                ab = midpoint(a,b)
                ac = midpoint(a,c)
                bc = midpoint(b,c)

                sierp(screen,color,a,ab,ac,deep-1)
                sierp(screen,color,b,ab,bc,deep-1)
                sierp(screen,color,c,ac,bc,deep-1)

The ouput for the fractal for both methods are similar as shown in figures below.

using any 3 equidistant co-ordinates

using center co-ordinates

 The Sierpinski triangles are used in logic sets and gaming logics.
For complete code refer to my git repository - https://github.com/anjalirmenon/sierpinski

 

KOCH'S SNOWFLAKE- A Mathematical Curve

     Koch's snowflake also known as Koch star is a mathematical curve and one of the earliest fractals to be described by Swedish scientist Helge Von Koch.

 How is a Koch- snowflake built?

     The snowflake starts as an equilateral triangle. Recursively each side is altered by-

• divide the line segment into three segments of equal length.
• draw an equilateral triangle that has the middle segment from step 1 as its base and points outward.
• remove the line segment that is the base of the triangle from step 2.

After one iteration of this process, the resulting shape is the outline of a         hexagram as in the figure below.

Lindenmayer System Representation

Lindenmayer system makes use of alphabet-- F, and constants -- +,-.

F draws a length forward, + moves an angle of 60 degrees to the right and - moves 60 degrees to the left.

The production rules are:- F-F++F-F.

Pygame Implementation

I implemented the Koch snowflake model using pygame. It makes use of recursively calling the function till a set number of iterations. A set range is decided where the recursions are placed in a stack and the range decremented each time. After the value of the range becomes zero the function implements once. Again the stack pops the recursion and decrements the value by 1 and this continues till all the recursive calls are popped from the stack.

def koch(screen,range1,angle1):
        if range1 == 0:
                Koch_snowflake(1,angle1)
        else:
                for angle in [60, -120, 60, 0]:
                        koch(screen, range1-1, angle1)
                        right(angle)
The output of the code I  implemented using the above is as follows:

Anti Koch snowflake is also an interesting fractal, which is built similar to Koch snowflake only varying in the direction and angle.

The output looks like the figure below:-

For complete code refer to my Github id- https://github.com/anjalirmenon/koch_snowflake

Conway's Game Of Life.

     Cellular automation devised by the British mathematician John Horton Conway, hence the name Conway's Game of Life.
The game is a zero player game, which has an initial set of cell configuration and based on a set of rules how the cells evolve.
     The game has 4 rules which each cell follows:-
Each individual cell interacts with its 8 neighboring cells.

1. A living cell with 2 or 3 neighboring cells lives to join the next generation.
2. A dead cell with exactly 3 cells in its neighborhood turns alive.
3. A living cell having less than 2 cells as neighbors dies due to depression.(no company no life!)
4. A living cell having more than 3 cells as neighbors dies due to overcrowding.(Phew! it's so stuffed out there.)

My approach to implement this game using pygame was to first get a random set of cells represented by little black rectangles indicating life on a white canvas. After which I checked for the rules according to Conway and accordingly adding and removing cells from the screen. The cells keep on evolving satisfying the conditions laid down in Game of Life.

The screenshot shows a program I implemented using pygame.

 


The code is available at my github id: anjalirmenon@github.com, search for conways game of life.

Pygame Basics

        Pygame is a cross platform set of python modules designed for writing video games. It provides simple libraries, with the intention of allowing real time computer game  development without the low level mechanics of C programming. We can draw simple geometrics figures like rectangle, square,  polygon or circle. A sample syntax to draw a rectangle of length and breadth 50, 100 respectively is: 
                               pygame.draw.rect(screen,(0,0,0),(50, 50, 100, 100))
                               pygame.display.flip().
        Here screen is the surface on which the figure gets displayed or the basic background, (0, 0, 0) stands for the color of the rectangle to be drawn, flip() updates the full display surface to the screen.

The screenshot shows the output of the code I wrote to draw a rectangle.

  PYGAME ESSENTIALS

Pygame program to work the most essential things to be included in the program are:-

1. import pygame module.
2. initialize pygame using pygame.init().
3. you need a display screen to display your figure. Select a background color and also the size of the screen for your figure.
4. RGB color scheme represented by the tuple(0,0,0) which stands for black and (255,255,255) for white. Any combination in the tuple give you different colors.
5. the figure to be drawn. 
6. display the figure using pygame.display.flip().  

Using pygame you can also import images, audio, video files and texts to make your game look more interesting!