HTML5 Paint

line width
fill

nil

line

nil

Scala : How functions are treated as objects

Hi friends,
        happy to share some interesting things studied from the on-line course Functional Programming Principles in Scala taken by the creator of Scala himself. Here I am trying to explain how functions are treated as primitive objects in Scala.

Consider Assignment of function

scala> def f(x:Int)=x*x  
f: (Int)Int

scala> var t:(Int)=>Int=f
t: (Int) => Int = <function>

We can also perform such an assignment as follows

scala> var t:Function[Int, Int]=f
t: (Int) => Int = <function>

similerly,

val y:Function2[Int,Int,Int]=(i:Int,j:Int)=>i+j
y: (Int, Int) => Int = <function> 

This gives insight to how functions are actually treated like objects in Scala.

In Scala, Traits Function1, Function2, ...Function22 are defined like follows

package scala
Trait Function1[T,F]
{
    def apply(x:T):F
} 

A function object of type (T) => F is an instance of subclass of Function1[T,F]
We can now define a function of type (Int)=>Int in this very basic way as follows.

class FunClass extends Function[Int,Int] {            
     def apply(x:Int):Int=x*x
}
defined class f

scala> val newFun=new FunClass()
newFun: FunClass = <function>

scala> newFun.apply(9)
res1: Int = 81

This is same as

scala> newFun(9)      
res2: Int = 81 

Now let us create an anonymous function

scala> val f= new Function[Int,Int] {
     | def apply(x:Int)=x*x
     | }

scala> f(9)
res2: Int = 81 

Now look at the apply() function.What happens if The apply itself a function object which with an apply() function as its member? It will lead to an infinite expansion when we create any function objects.

scala> def f(x:Int)=x*x                  
f: (Int)Int

scala> f.apply(9)
<console>:6: error: missing arguments for method f in object $iw;
follow this method with `_' if you want to treat it as a partially applied function
       f.apply(9)
       ^

Why we could not call apply() of object f? No its not. f is not a function object here. Now look back to our first try

scala> var t:Function[Int, Int]=f
t: (Int) => Int = <function>

Here a function object corresponds to f is generated which is an "anonymous function object" and is assigned to variable t while executing these kind of assignment statements. Here it is a simple definition for "eta expansion".

Scala:Type parameterization

Polymorphism in Scala can be achieved through type parameterization. Let us define class g with attributes x,y as integers as

scala> class g(val x:Int, val y:Int)
defined class g

We can use Type parameter like follows

scala> class g[T](val x:T, val y:T)
defined class g

scala> val obj=new g[Char]('a','b')
obj: g[Char] = g@a53564

scala> obj.x
res11: Char = a

scala> obj.y
res12: Char = b

We need not specify the type parameter explicitly like that, the Scala compiler  can infer the Type from function parameters

scala> val obj=new g('a','b')
obj: g[Char] = g@a53564

scala> obj.x
res3: Char = a
scala> val obj1=new g(1,2)
obj1: g[Int] = g@a53564

scala> obj1.y
res3: Char = 2

Now we can play a bit

scala> val obj=new g(1,true)          
obj: g[AnyVal] = g@11d95

scala> obj.x
res1: AnyVal = 1

scala> obj.y
res2: AnyVal = true

Notice that  val obj=new g(1,true) doesn't cause a type mismatch error even Value 1 is of type Int and true is of Boolean while both parameters are expected to be of same type. The reason is that, Boolean, Char, Int etc. are Subtypes of AnyValue.Here The compiler inferred the type as AnyValue looking at the parameters passed.

We can also have multiple Type parameters as follows

scala> class g[T,H](val x:T, val y:H)
defined class g

scala> val obj=new g('A',9)
obj: g[Char,Int] = g@14f7121

scala> obj.x
res10: Char = A

scala> obj.y
res11: Int = 9

We can define functions of parameterized type like follows

scala> def f[T](x:T):Unit=print(x)
f: [T](T)Unit

scala> f[Int](6)                  
6

scala> f(6)                  
6

scala> f("ssss")                  
ssss

Python Decorators

Python Decorator is a strategic use of functional programing facilities. Decoration stands for some kind of modifications. Let us consider one example. Consider , we have some function takes one integer and maps to some other integer, take a squaring function for now.

>>> def square(x):
...     return x*x

and we have to make a generalized function which accepts functions of the above kind as arguments and produce new function which do some further maping. take a doubling method for now.

>>> def double(x):
...     return x*2

Now let us make a function mofifier function

>>> def modify(f):
...     def g(x):
...             return double(f(x))
...     return g

now we can have a new function which performs the two mappings squaring and doubling together

command

>>> newFun=modify(square)
>>> newFun(2)
8

we can generalize the use of such function modifying functions with concept of decorators as

>>> @modify
... def square(x):
...     return x*x

 now we have a modified version of function square(x)

>>> square
<function g at 0x93dc64c>
>>> square(2)
8

Just after defining the function square, it is passed to modify() and the result returned is used instead of square().

>>> def decGenerate(mapping):
...     def modify(f):
...             def g(x):
...                     return mapping(f(x))
...             return g
...     return modify
... 
>>> @decGenerate(double)
... def square(x):
...     return x*x
... 
>>> square(2)
8

Here function decGenerator(mappingFunction) returns a function makung functio modify(f) which can be used as decorator

some magic with python

Here I am trying to discuss about some special method attributes in python.

we define a class like

>>> class myClass:
...     def __init__(self,value):
...             self.value=value
...             print 'object initialized'

And an object instantiation is done by

>>> a=myClass(10)
object initialized
>>> b=myClass(20)
object initialized

This seems usual but the magic is in evaluating the function myClass(value). an expression in the formmyClass(args) causes a call to __init__(self,args) defined inside class myClass.

let us make a new object c with its value attribute as sum of those of objects a and b.

>>> c=myClass(a.value+b.value)
object initialized
>>> c.value
30

It will be awesome if we can perform

>>> c=a+b
object initialized
>>> c.value
30

 We can make this possible by including a magic function __add__ to the class definition of myClass.

>>> class myClass:
...     def __init__(self,value):
...             self.value=value
...             print 'object initialized'
...     def __add__(self,obj):
...             c=myClass(self.value+obj.value)
...             return c

 Here c=a+b is evaluated as c=a.__add__(b)
There are more such methods enables operator overloading for arithmetic operators

Operator	Special method
-	__sub__(self, other)
//	__floordiv__(self, other)
/	__div__(self, other)
%	__mod_(self, other)
**	__pow__
<<	__lshift__(self, other)
&	__and__(self, other)
|	__or__(self, other)
^	__xor__(self, other)

There are corresponding reflected arithmetic operators too. If we use __radd__ instead of __add__ in above example, c=a+b will be evaluated as c=b.__radd__(a). We can define custom behavior for a lot of operations other than these arithmetic operators, like attribute assignments, comparisons, unary arithmetic operations like '+', '-' etc

Now let us look on some awesome special methods which enables creation of sequence types.

We have a class mySequence

>>> class mysequance:
...     def __init__(self,list):
...             self.value=list
...     def __iter__(self):
...             return iter(self.value)
...     def __getitem__(self,index):
...             return self.value[index]
...     def __len__(self):
...             return len(self.value)
... 
>>> s=mysequance([1,2,3,4,5,6])
 

Now we can perform some  list operations as follows

>>> len(s)
6
>>> s[1]
2
>>> it=iter(s)
>>> for i in it:
...     print i
... 
1
2
3
4
5
6

Python iterators, generators and list comprehension

Iterators

Iterators are objects which enables traversal of python sequence data structures like strings, tuples and lists which are so called iterable.

>>> list=[1,2,3,4]
>>> lit=iter(list)
>>> lit
<listiterator object at 0x96abd2c>

 we can use this iterator object to extract elements on the list one by one

>>> lit.next()
1
>>> lit.next()
2
>>> lit.next()
3
>>> lit.next()
4
>>> lit.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Function next() raise Stopiteration exception when there is no more element in list to traverse.

 we can use iterator object instead of corresponding sequence variables in construct.

>>> tit=iter((1,2,3,4))
>>> tit
<tupleiterator object at 0x96abfcc>
>>> 3 in tit
True 

generators

>>> def listgen(n):
...     for i in range(n):
...             yield i
... 

Python interpret functions like above containing a yield statement in a special way unlike to other functions. When we call the function listgen(n)

>>> g=listgen(5)
>>> g
<generator object listgen at 0xb786af7c>

Instead of executing the function and returning the result, a generator object  corresponding to listgen() is returned. The use of generator object is similar to iterator object.

>>> g=listgen(3)
>>> g.next()
0
>>> g.next()
1
>>> g.next()
2
>>> g.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration 

List comprehension

squares=[i*i for i in range(10)  if i%2==1]
>>> squares
[1, 9, 25, 49, 81]

A list comprehension consists of brackets containing an expression followed by a for clause, then zero or more if clauses. This special construct returns a list. The above list comprehension statement gives same result as

>>> squares=[]
>>> for i in range(10):
...     if i%2==1:
...             squares.append(i*i)
... 

 or

>>>squares=map((lambda x: x*x),filter((lambda x:x%2==1), range(10)))

We can perform nested list comprehension like follows,

>>> matrix=[[1,2,3],[4,5,6],[7,8,9]]
>>> transpose=[[matrix[i][j] for i in range(len(matrix))] for j in range(len(matrix[0]))]
>>> transpose
[[1, 4, 7], [2, 5, 8], [3, 6, 9]] 

 

Functional programming with python

Even we cant depend completely on functional programming, we should employ this approach whenever possible. In that sense, Python is a good platform for mixing up different programming approaches in a most convenient way

Python functional programming facilities

We shall discuss python functional programming capabilities based on following examples

With Python object oriented programming, we can notate an arithmetic progression as

>>> class term:
 def __init__(self,a,d):
  self.value=a
  self.d=d
 def next(self): 
  self.value+=self.d
  return self 

>>> x=term(1,2)

Here x is capable of generating terms in an arithmetic progression with a=0 and common difference d=2, as follows.

>>> x.next() 
>>> x.value
3
>>> x.next() 
>>> x.value
5
>>> x.next()
>>> x.value
7 

We can perform such an abstraction with functional programming facilities as follows.

>>> def term(a,d):
...     return(lambda f: f(a,d))
... 
>>> def next(s):
...     return s(lambda a,d: term(a+d,d))
... 
>>> def value(s):
...     return s(lambda a,b:a)
... 

>>> x=term(1,2)
>>> value(x)
1
>>> x=next(x) 
>>> value(x)
3
>>> value(next(next(next(next(term(1,2))))))
9

Inside term(a,b) a nameless function is defined using lambda expression. The definition of this lambda function contain use of local variables of function term(). The closure property of functional languages facilitate this kind of definition of functions inside a function. Again, this lambda function accepts a function f of the form

f(a,b):
     return expression_on(a,b)

as its argument and apply f on local variables a and b of function term(a,b) then return the result. So this lambda function is a higher order function, that is a function accepts functions as arguments. What is returned by term function is a higher order function which has access on local variables of term(). This ability to use function as return value is called currying.

What's the benefit?

Functional programs contain no side-effects. that is, A function call can have no effect other than to compute its result.


Function term(a,b) returns a higher order function x with a,b as tis local variables. With special functions value(s) and next(s) we can have read access to the local variables. In the second case x is a function object with constant state. In other words state is strictly conserved. in first case, in this style of programming, state change for x occurs  as a side effect for each call to member function next().

Advantage of Eliminating side effects is "Referential transparency"

In first case

>>>x.next().value==x.next().value
False 

in second case

>>>value(next(x))==value(next(x))
True 

Here value(next(x)) returns same value at every time applied on x. That means we can replace this expression with a value whenever it occurs. This property is called referential transparency. No one feel any confusion because it is "Mathematically provable". In first case we can maintain referential transparency by adding some extra object replications instead of just returning a self. But in functional programming approach, it is an inherent characteristic.

Simple Chess using Recursive Minimax

Here it is just a try to make a chess playing program. The program runs on a very basic recursive minimax algorithm. So it now plays like a novice chess player, and also subjected to usual problems of recursive minimax. The maximum achievable depth for the minimax tree is 10 here. so at most 5 opponent movements can be foretasted. Also a depth of 4 or 5 is practical considering the time taken for each decision. I am trying to implement it by means of non-recursive minimax algorithm and more constraints on cost benefit analysis of each move to upgrade it to a moderate level chess playing program

Here is the source code

Applicative Order Evaluation in Scheme

Arguments to functions can be expressions which are to be evaluated inorder to pass values to function. There are two models of evaluation of arguments to functions. Applicative order and normal order evaluation. In normal order evaluation, not all the arguments are to be evaluated. the evaluation of each argument is delayed until it is necessary. Its a lazy evaluation technique. But in the case of applicative order evaluation all arguments are evaluated regardless of the need.
for example consider function "checkrange" which accepts two parameters x and y, then returns true if x coming under the range 0 to y.

(define (checkrange x y)
    (if (< x 0)
        false
        (if (> x y)
            false
            true)))

Here we have two conditions ,where the second is checked only if the first condition fails. Also the value y is used only then.

If we call this function this way 

(checkrange -15 (/ 100 0))

Since x value less then 0 first check satisfies and function should return a #f (boolean false value) and second argument is not evaluated in case of normal order evaluation. But in scheme this would cause error since it perform application order evaluation and so evaluating (/ 100 0) raise division by zero error.
   
We use "if" construct as any other function by passing predicates and expressions as arguments to function. But in Scheme (or lisp) the "if" function is a specially made one since applicative order evaluation makes problems. This scenario will be more clear with the example: Square Roots by Newton's Method.

(define (absolute x)
    (cond ((< x 0) (- x))
        (else x)))
      
(define (good guess x)
    (< (absolute (- (* guess guess) x)) 0.001))


(define (improvguess guess x)
    (/ (+ guess (/ x guess)) 2))
  
(define (sqroot guess x)
    (if (good guess x)
        guess
        (sqroot (improvguess guess x) x)))
Function (sqroot guess x) is recursively called here. The termination of recursion occurs when function (good guess x) returns a boolean true value.
   
In the example let us replace "if" by a user defined function "new-if" which obeys applicative order evaluation, as follows.



(define (new-if x y z)
    (cond (x y)(else z)))

(define (sqroot guess x)
    (if (good guess x)
        guess
        (sqroot (improvguess guess x) x)))
define (p) (p))
       
Function (sqroot (improvguess guess x) x))) will be evaluated whenever the "new-if" function is called, yielding infinite recursive calls.
       
   

Simulator for a Mythical Machine in JAVA

Mythical machine is an imaginary decimal based computer simulated over real machines. Mythical machine performs very basic computations and has small instruction set and instructions are treated as decimals for simplicity. here is a java version of the simulation.We can type assumbly code and simply run it on the simulated mythical processor which has a register file of 10 registers r0-r9 and having a load store architecture. Contents in memory locations and registers are displayed as output.
You can look at the source code here.

pyUnit A unit testing framework

Pythons unittest module provides organized tests for our modules. Here i am testing my numTOword conversion module which convert large numbers to corresponding natural language representations.  a 111 will be converted to one hundred eleven consisting all lower-case letters. We use string of digits to represent numbers since we have to convert really huge numbers.  The module converts numbers in a range 1 to 10^100, deliberately missing zero.

The use of unit test module is as follows

 #test.py

import unittest
import convert
class testnumberTOword(unittest.TestCase):
 
 
 numwordmapping={
   '1':'one',
   '11':'eleven',
   '111':'one hundred eleven',
   '1111':'one thousand one hundred eleven',
   '11111':'eleven thousand one hundred eleven',
   '111111':'one lakh eleven thousand one hundred eleven',
   '1111111':'eleven lakh eleven thousand one hundred eleven',
   '11111111':'one crore eleven lakh eleven thousand one hundred eleven',
   '2':'two',
   '22':'twenty two',
   '222':'two hundred twenty two',
   '2222':'two thousand two hundred twenty two',
   '22222':'twenty two thousand two hundred twenty two',
   '222222':'two lakh twenty two thousand two hundred twenty two',
   '2222222':'twenty two lakh twenty two thousand two hundred twenty two',
   '22222222':'two crore twenty two lakh twenty two thousand two hundred twenty two',
   '3':'three',
   '33':'thirty three',
   '333':'three hundred thirty three',
   '3333':'three thousand three hundred thirty three',
   '33333':'thirty three thousand three hundred thirty three',
   '333333':'three lakh thirty three thousand three hundred thirty three',
   '3333333':'thirty three lakh thirty three thousand three hundred thirty three',
   '33333333':'three crore thirty three lakh thirty three thousand three hundred thirty three',
   '4':'four',
   '44':'fourty four',
   '444':'four hundred fourty four',
   '4444':'four thousand four hundred fourty four',
   '44444':'fourty four thousand four hundred fourty four',
   '444444':'four lakh fourty four thousand four hundred fourty four',
   '4444444':'fourty four lakh fourty four thousand four hundred fourty four',
   '44444444':'four crore fourty four lakh fourty four thousand four hundred fourty four',
   '5':'five',
   '55':'fifty five',
   '555':'five hundred fifty five',
   '5555':'five thousand five hundred fifty five',
   '55555':'fifty five thousand five hundred fifty five',
   '555555':'five lakh fifty five thousand five hundred fifty five',
   '5555555':'fifty five lakh fifty five thousand five hundred fifty five',
   '55555555':'five crore fifty five lakh fifty five thousand five hundred fifty five',
   '6':'six',
   '66':'sixty six',
   '666':'six hundred sixty six',
   '6666':'six thousand six hundred sixty six',
   '66666':'sixty six thousand six hundred sixty six',
   '666666':'six lakh sixty six thousand six hundred sixty six',
   '6666666':'sixty six lakh sixty six thousand six hundred sixty six',
   '66666666':'six crore sixty six lakh sixty six thousand six hundred sixty six',
   '7':'seven',
   '77':'seventy seven',
   '777':'seven hundred seventy seven',
   '7777':'seven thousand seven hundred seventy seven',
   '77777':'seventy seven thousand seven hundred seventy seven',
   '777777':'seven lakh seventy seven thousand seven hundred seventy seven',
   '7777777':'seventy seven lakh seventy seven thousand seven hundred seventy seven',
   '77777777':'seven crore seventy seven lakh seventy seven thousand seven hundred seventy seven',
   '8':'eight',
   '88':'eighty eight',
   '888':'eight hundred eighty eight',
   '8888':'eight thousand eight hundred eighty eight',
   '88888':'eighty eight thousand eight hundred eighty eight',
   '888888':'eight lakh eighty eight thousand eight hundred eighty eight',
   '8888888':'eighty eight lakh eighty eight thousand eight hundred eighty eight',
   '88888888':'eight crore eighty eight lakh eighty eight thousand eight hundred eighty eight'
   }
 def testnumtowordmapping(self):
  p=convert.numbertoword()
  for number in self.numwordmapping.keys():
   print 'tested' , number 
   self.assertEqual(p.spel(number),self.numwordmapping[number])
 
 def runTest(self):
  self.checknumtowordmapping()
   

unittest.main()

On running the script we see


----------------------------------------------------------------------
Ran 1 test in 0.004s

OK

To perform unittest, we have to make a subclass for unittest.TestCase. An instance for this class will carry tests.
The num_word_mapping is the dictionary containing few known mappings between numbers and their word representations. We have to test the convert module giving each number and comparing obtained outputs with expected values.

the function testnumtowordmapping() checks convert.numbertoword.spell(number)
by applying each test cases in num_word_mapping.

The function assertEqual(ExpectedResult,ObtainedResult)  will introduce exception when the Obtained_Result differs from Expected_Result and the checknumtowordmapping()
skips with reporting the unittest module an exception

The result of test with taking expected value for 777777777 on convwesion as 'seven crore seventy WRONG VALUE seven lakh seventy seven thousand seven hundred seventy seven' is as follows

AssertionError: 'seven crore seventy seven lakh seventy seven
thousand seven hundred seventy seven' != 'seven crore seventy WRONG
VALUE seven lakh seventy seven thousand seven hundred seventy seven'


 The completion of testnumtowordmapping() means that there are no bugs found in the scope of this test case

Say BIG numbers in words

Hello friends ,
here is my python app to convert big numbers into words. for example  13333333333333 will be "thirteen trillion three hundred thirty three billion thirty three crore thirty three lakh thirty three thousand three hundred thirty three". Numbers upto googol(10^100) can be converted this way. Conversion is puerly lexical and so complexity depends only on number of digits.

you can find source code Here 

 

GitPython :Python Git API

    Scripting Git tasks is made simpler using GitPython. We can use it to create local Git applications. Here is a simple example script to perform initial Git setup for our project directory /home/user/myproject. We have already created a new repository in GitHub with url https://github.com/user/test.git. Run the script as follows

python initwithGit /home/user/myproject https://github.com/dileepnandanam/test.git

# initWithGit.py
import git
import commands
import sys
import os
projectdir=sys.argv[1]
remote=sys.argv[2]
modules=os.listdir(projectdir)
g=git.cmd.Git(projectdir)
g.init()
for module in modules:
    g.add(module)
message='first commit'
(stats,op)=commands.getstatusoutput("git commit -m '"+message+"'"+projectdir)
g.push(remote)

Class git makes bindings with git binaries  possible

The statement g=git.cmd.Git(projectdir)

enables us to manage the local repository using object g. We can issue git commands as

• g.init()
• g.commit()
• g.branch(branchname)
• g.checkout(branchname)
• g.push(remoteRepo)

We can monitor current repository status through git.Repo
eg.

repo= git.Repo(projectdir)
for branch in repo.heads:
    print branch.name
    print branch.commit

This will display all branches and details of commits corresponding to repository   

TutFind :Fun with python

I dont like googling for tutorials. Thats why I made TutFind- a download utility just for web learners. TutFind makes use of Google to find possible pages where we will get free stuff and download it. This multi threaded application simultaneously search hundreds of pages by traversing the web in a limited depth. Python's powerful urllib and  regular-expression form the core of this application.

Screenshot:TutFind

Here I am searching for PDFs of python tutorial. I gave the search keywords "python tutorial" and specified that I want PDF documents by entering ".pdf" as file extension. Also the target folder ids set to "dest". We will get a collection of PDF tutorials at /home/dest (sorry about the poor GUI facilities provided). On search, we got a list of available PDF(Here they are only four since the depth and breadth of search is set very small).

Screenshot:TutFind

Now lets see what we have now in dest

 Here is the source code

Quadrapassel Using Pygame

Hi friends, Here is my version of Quadrapassel the legendary tile matching puzzle video game of 1984.Quadrapassel  is the first video game i ever played and this my first pygame too, using very basics of python and pygame library. Quadrapassel is one of my favorite games. The goal is to fill a complete row of bricks and clear it. I imagine those incoming bricks  as "opportunities" and accumulated ones as circumstances in life. Use them wisely or we will lose.

Screenshot: Pygame display

Here’s the source code.

An English Malayalam Translitrator

Here is an English to Malayalam transliterator  perform conversion of English script to phoneticly equivalent Malayalam script using a Decision tree based algorithm.

The decision tree outline

The converter parse the input English string character by character, and maps each character to a Malayalam Unicode character, based on surrounding context. This context is determined three or more characters at right side or right three or more characters  left or both. These checks for determining surrounding context is done by decision tree. At each node of the decision tree, when we traverse it, an elementary check about surrounding context is carried out. The result decides the next check to be carried out or the final mapping to Malayalam Unicode character or string.

Here is my git hub rep

A virtual mouse with IR sensor array

This is an attempt to make an extreme low cost virtual mouse. The user can perform mouse actions by hand gestures. The work is done as part of my B.Tech projects. Here we followed the common way of tracking motion with multiple simple proximity sensors and the ideas from the existing gestural pointing device for gesture recognition.

The device has a sensor array composed of Infrared LEDs (IR133-A) and Photo-transistors (PT333-3C) interfaced with an Arduino board. When each LEDs are illuminated, the reflected infrared radiations are measured using these photo-transistors which gives voltage levels indicating spatial orientation of finger tips. These voltage levels are used for finding approximate distance from a sensor to finger tip in front of it. So an array of distances is calculated each time. We have a USB Driver running on PC that queries the device, 50 times in a second, fetching these informations. A simple  pattern recognition algorithm detects current mouse gestures. The movement of hand is estimated analyzing consecutively fetched distance arrays.

Two consecutively fetched distance arrays indicating a hand movement