Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.
The "game" is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.
The Game of Life is not a game in the conventional sense. There are no players, and no winning or losing. Once the "pieces" are placed in the starting position, the rules determine everything that happens later. Nevertheless, Life is full of surprises! In most cases, it is impossible to look at a starting position (or pattern) and see what will happen in the future. The only way to find out is to follow the rules of the game.
 

Rules

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
   

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. The rules continue to be applied repeatedly to create further generations.
Here is the code of Game of Life I'd done in JavaScript

Lisp Interpreter

    An interpreter is also a program that translates a high-level language into a low-level one, but it does it at the moment the program is run. You write the program using a text editor or something similar, and then instruct the interpreter to run the program. It takes the program, one line at a time, and translates each line before running it: It translates the first line and runs it, then translates the second line and runs it etc.

A language interpreter has two parts:

1. Parsing: The parsing component takes an input program in the form of a sequence of characters, verifies it according to the syntactic rules of the language, and translates the program into an internal representation. In a simple interpreter the internal representation is a tree structure that closely mirrors the nested structure of statements or expressions in the program.
2. Execution: The internal representation is then processed according to the semantic rules of the language, thereby carrying out the computation.
    

Here is a picture of the interpretation process and an interactive session showing how parsing and execution operate on a short program: 

 

Parsing:

Parsing is traditionally separated into two parts: lexical analysis, in which the input character string is broken up into a sequence of tokens, and syntactic analysis, in which the tokens are assembled into an internal representation.

Execution:

The translated programme is processed according to the semantic rules of the language. Considering an example, its output after evaluation step will be as follows.

>>> program = "(begin (define r 3) (* 3.141592653 (* r r)))"

After parsing the program we get,

['begin', ['define', 'r', 3], ['*', 3.141592653, ['*', 'r', 'r']]]

After Executing this, we will get,

28.274333

Here is the code of Lisp Interpreter in Javascript. Now lets go through the code.

Function Env():

This function defines the environment for a variable used in execution. The function find(variable) will find the correct environment of execution for the variable. If the variable is defined in the existing environment, the current environment is considered, else the function is called recursively to the outer environments untill the correct environment is found, property known as lexical scoping.

Function addGlobal():

This functions defines the global environment. Basic math functions such as '+', '*' etc are defined in the global environment. Other than these 21 basic functions, some other math functions such as sin,cos,log etc are also included in the global environment as shown below.

         var functions = ['abs', 'acos', 'asin', 'atan', 'atan2', 'ceil', 'cos', 'exp', 'floor', 'log',
                                               'max', 'min', 'pow', 'random', 'round', 'sin', 'sqrt', 'tan'];

             for (var i = 0; i < functions.length; i += 1) {

                 env[functions[i]] = Math[functions[i]];

             }

Function eval():

Evaluation function defines the steps of evaluation processes for all types of lines of codes. It represents the execution part of the interpreter. 9 cases are defined in the function. 

Functions for parsing:

Parsing is the first stage of the interpreter. It converts the input code into a set of tokens and reads according to the semantic meanings of the language. We use a number of functions for these actions which are listed below. 

• parser() : Returnes the output of readFrom function. 
• tokenize() : Converts the input code into a set of tokens. A set of built in functions are used here. s.replace() is used to replace the parenthesis with a space before and after it. s.trim() removes the spaces at the beginning and end of the expression. s.split() is applied to split the code after every space into a set of tokens. 
• readFrom() : The functions takes the output of tokenize() function as input and forms a list avoiding all parenthesis and resembles the internal ordering of the expression. 
• atom() : Converts integers in string format to numbers. 

Function repl():

repl() represents the read evaluation print loop. The function is used to form an interactive Lisp interpreter.

Huffman Coding Overvew.

    Huffman coding is a statistical technique which attempts to reduce the    amount of bits required to represent a string of symbols. The algorithm accomplishes its goals by allowing symbols to vary in length. Shorter codes are assigned to the most frequently used symbols, and longer codes to the symbols which appear less frequently in the string.
So, when we’ll translate the input we want to encode the most frequent symbols will take less space than they used to and the least frequent symbols will take more space but because they’re less frequent.

Building a Huffman Tree

    The Huffman code for an alphabet (set of symbols) may be generated by constructing a binary tree with nodes containing the symbols to be encoded and their probabilities of occurrence. The tree may be constructed as follows:

Step 1. Create a parentless node for each symbol. Each node should include the symbol and its probability.
Step 2. Select the two parentless nodes with the lowest probabilities.
Step 3. Create a new node which is the parent of the two lowest probability nodes.
Step 4. Assign the new node a probability equal to the sum of its children's probabilities.
Step 5. Repeat from Step 2 until there is only one parentless node left.

Huffman Code: Example

    The following example bases on a data source using a set of five different symbols. The symbol's frequencies are:

Symbol  Frequency
   A       24
   B       12
   C       10
   D        8
   E        8
          ----> total 186 bit
         (with 3 bit per code word)

    The two rarest symbols 'E' and 'D' are connected first, followed by 'C' and 'D'. The new parent nodes have the frequency 16 and 22 respectively and are brought together in the next step. The resulting node and the remaining symbol 'A' are subordinated to the root node that is created in a final step.

Code Tree According To Huffman.

Symbol Frequency  Code  Code   total
                       Length  Length
   A      24      0      1      24
   B      12      100    3      36
   C      10      101    3      30
   D       8      110    3      24
   E       8      111    3      24
---------------------------------------
    ges. 186 bit          tot. 138 bit
    (3 bit code)

    To decode a string of bits we just need to traverse the tree for each bit, if the bit is 0 we take a left step and if the bit is 1 we take a right step until we hit a leaf (which is the symbol we are looking for). For example, if we have the string “100 111 110 ″ and our tree, decoding it we’ll get the string “bed”.
    It’s very important to observe that not one code is a prefix of another code for another symbol. In our example, if 0 is the code for ‘a’, 00 cannot be a code for any other symbol because there’s going to be a conflict. We’ll never reach that symbol because after taking steps for the first two bits we’ll get ‘a’, we’re never going the find the symbol for 00.

Here is the python code for Huffman coding.

Functional programming in Scala

Main programming paradigms

Imperative programming

Functional programming

Logical programming

Functional programming

·         

           Wider sense: Programming with focusing on functions.

·        Restricted sense: Programming without using mutable variables, assignments,loops and other imperative control statements.

Some functional programming languages:

In the wider sense :

·        Lisp,Scheme,Racket,Clojure

·        SML,Ocaml,F#

·        Haskell (full language)

·        Scala

·        Smalltalk,Ruby(!)

In the restricted sense:

·        Pure Lisp,XSLT,XPath,XQuery,FP

·        Haskell(without I/O Monad or UnsafePerformIO)

REPL(Read-Eval-Print)

An interactive shell or REPL allows one to write expressions and responds with their value. Scala REPL can be started by typing

          >scala

          For Example:

                 

                    >scala 34+65

                    res0: Int = 99

                    >scala def radius = 10

                    radius: Int

                    scala>def pi = 3.14159

                    scala>radius * pi

                    res1: Double = 31.4159

Order of evaluation of arithmetic operation:

                  

                    (2 * pi) * radius

                    (2 * 3.14159) * radius

                    6.28318 * 10

                    62.8318

Definitions can have parameters:

scala> def square(x: Double) =  x * x

square: (Double)Double

scala> def sumOfSquares(x: Double, y: Double) = square(x) + square(y)

sumOfSquares: (Double,Double)Double

Expression evaluation strategies Call-by-name and Call-by-value:

Both strategies reduce to the same final values as long as

·        The reduced expression consist of pure functions and

·        Both evaluations terminate

Consider an example:
 

sumOfSquares(2, 3+4)               sumOfSquare(2, 3+4)
sumOfSquare(2,7)                      square(2) + square(3+4)
square(2) + square(7)                2 * 2 + square(3+4)
2 * 2 + square(7)                       4 + square(3+4)
4 + square(7)                             4 + (3+4) * (3+4)
4 + 7*7                                      4 + 7 * (3+4)
4+ 49                                         4 + 7 * 7
53                                               4 + 49
                                                   53

Scala normally uses call-by-value. But if the type of function starts with => it uses call-by-name.

Conditional Expressions

Scala has a conditional expression if-else. It looks likes a if-else in Java, but is used for expressions not statements.

          Example:

                   def abs(x: Int) = if (x >= 0) x else -x

Boolean Expressions

           

         Boolean expressions b can be composed of

                   true false               // Constants

                   !b                          // Negation

                   b && b                 // Conjunction

                   b || b                     // Disjunction

          and of the usual comparison operations:

                   e <= e, e >= e, e < e, e > e, e == e, e != e

Blocks in Scala

It is a good discipline in functional programming to arrange the code into separate blocks so that it avoids the name space pollution and becomes more readable. Every block of code will have a start and end braces. Consider the below given example;

val x = 3
val y = 1
def sum(x: Int , y: Int) = x + y
val res = {
  val y =sum(x,1)
  y * y
}

• ·         The last element of a block is an expression that defines its value.

• ·         Blocks are themselves expressions; a block may appear everywhere an expression can.

• ·         The definitions inside a block are only visible from within the block.

• ·         The definitions inside a block shadow definitions of the same names outside the block.

Semicolons

          

          In Scala, semicolons at the end of lines are in most cases optional

          You could write

                   val x = 1; but not necessary.

On the other hand, if there are more  than one statements on a line, they need to be separated by semicolons:

          val y = x + 1; y * y

More references

• ·         Structure and Interpretation of Computer Programs. Harold Abelson and Gerald J. Sussman. 2nd edition. MIT Press 1996 Download

• ·         Programming in Scala. Martin Odersky, Lex Spoon, and Bill Venners. 2nd edition. Artima 2010.

• ·         Scala for the Impatient. Cay Horstmann Download

Linear Recursion & Iteration

Recursion and Iteration are two types of evaluation methods in scheme language.
Lets explain this with the help of some examples. First of all consider the case of finding factorial of a number defined by:

                   n! = n(n-1)(n-2).......3.2.1

Now lets consider the two ways to compute the result. The first one is to consider that n! is equal to n times (n - 1)! for any positive integer n:
                   
                   n! = n[(n-1)(n-2).......3.2.1] = n.(n-1)!

Thus, we can compute n! by computing (n - 1)! and multiplying the result by n. If we add the stipulation that 1! is equal to 1,we can define the procedure as folows:
                    (define (factorial n)
            (if (= n 1)
                1
                (* n (factorial (- n 1)))))

Using the above defined procedure, the evaluation process for computing 3! can be picturised as follows:
         (factorial 3)
         (* 3 (factorial 2))
         (* 3 (* 2 (factorial 1)))
         (* 3 (* 2 1))
         (* 3 2)
         6

Now let's take a different perspective on computing factorials. We could describe a rule for computing n! by specifying that we first multiply 1 by 2, then multiply the result by 3, then by 4, and so on until we reach n. More formally, we maintain a running product, together with a counter that counts from 1 up to n. We can describe the computation by saying that the counter and the product simultaneously change from one step to the next according to the rule
product counter · product
counter counter + 1
and stipulating that n! is the value of the product when the counter exceeds n.

So using this above described method, we can compute the factorial of n using the following procedure:
         (define (factorial n)
           (fact-iter 1 1 n))          (define (fact-iter product counter max-count)
           (if (> counter max-count)
                product
               (fact-iter (* counter product)
                          (+ counter 1)
                          max-count)))

We can use the substitution model to visualize the process of computing 3!, as shown in figure given below:
                  (factorial 3)
         (factorial 1 1 3)
                  (factorial 1 2 3)
         (factorial 2 3 3)
         (factorial 6 4 3)
         6 

Considering the two methods, the shapes of the evaluation process figure is different for recursion and iterative process. The first figure reveals a shape of expansion followed by contraction. The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications). The contraction occurs as the operations are actually performed. This type of process, characterized by a chain of deferred operations, is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on. 

By contrast, the second process does not grow and shrink. At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count. We call this an iterative process. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate. 

These are some of the main differences between linear recursive and iterative evaluation. Please refer here to read more about the topic with more examples.

UNIT TESTING

• In computer programming, unit testing is a method by which individual units of source code, sets of one or more computer program modules together with associated control data, usage procedures, and operating procedures, are tested to determine if they are fit for use.
• The goal of unit testing is to isolate each part of the program and show that the individual parts are correct.

Advantages 

  Find problems early

• Unit tests find problems early in the development cycle. Unit tests are created before the code itself is written. When the tests pass, that code is considered complete.
• The unit tests alert the development team of the problem before handing the code off to testers or clients, it is still early in the development process.

   Facilitates change

• Unit testing allows the programmer to write test cases for all functions and methods so that whenever a change causes a fault, it can be quickly identified and fixed.
• Readily available unit tests make it easy for the programmer to check whether a piece of code is still working properly.

   Simplifies integration

• By testing the parts of a program first and then testing the sum of its parts, integration testing becomes much easier.

   Documentation

• Unit testing provides a sort of living documentation of the system.
• Unit tests provides a basic understanding of what functionality is provided by a unit and how to use it.

   Design

• The basic building blocks of unit testing are 'test cases' -- single scenarios that must be set up and checked for correctness.
• The testing code of a Test Case instance should be entirely self contained, such that it can be run either in isolation or in arbitrary combination with any number of other test cases.
• An example of unit testing :
  

       import unittest

        class SimpleWidgetTestCase(unittest.TestCase):
            def setUp(self):
                self.widget = Widget("The widget")

        class DefaultWidgetSizeTestCase(SimpleWidgetTestCase):
            def runTest(self):
                assert self.widget.size() == (50,50), 

                            'incorrect default size'

        class WidgetResizeTestCase(SimpleWidgetTestCase):
            def runTest(self):
                self.widget.resize(100,150)
                assert self.widget.size() == (100,150), \
                       'wrong size after resize'
    

• In this, if the 'setUp' method raises an exception while the test is running, the framework will consider the test to have suffered an error, and the 'runTest' method will not be executed.
• The TestCase class of the unittest compares its arguments and if not same, will raise an exception and the test will immediately be considered failed.
• Place the following code at the bottom of your test module:
  

        if __name__ == "__main__":
            unittest.main()
    

Then we could run the code in the command line.
Eg: % python unittest.py widgettests.WidgetTestSuite
• The design document (the unit-test itself) can be used to verify that the implementation adheres to the design.
• With the unit-test design method, the tests will never pass if the developer does not implement the solution according to the design.
• A detailed example of unit testing is given here

Limitations 

• Testing cannot be expected to catch every error in the program: it is impossible to evaluate every execution path in all but the most trivial programs. 
• Unit testing by definition only tests the functionality of the units themselves. Therefore, it will not catch integration errors or broader system-level errors.
• Like all forms of software testing, unit tests can only show the presence of errors; they cannot show the absence of errors.
• Another challenge related to writing the unit tests is the difficulty of setting up realistic and useful tests.
•  If these initial conditions are not set correctly, the test will not be exercising the code in a realistic context, which diminishes the value and accuracy of unit test results. 
• Use of a version control system is essential in unit testing.
• It is also essential to implement a sustainable process for ensuring that test case failures are reviewed daily and addressed immediately.

 

• These are some basic ideas regarding unit testing. You could refer here for more details.

GUIDELINES TO WRITE A PROGRAM IN PYTHON

GUIDELINES TO WRITE A PROGRAM IN PYTHON.

• The guidelines provided here are intended to improve the readability of code and make it consistent across the wide spectrum of Python code.
• The guidelines is about consistency. Consistency with this style guide is important. Consistency within a project is more important.
• Break the rules, if it hinders the readability of the code.

     CODE LAY OUT

     Indentation:

• Use 4 spaces per indentation level.
• Continuation lines should align wrapped elements either vertically or using a hanging indent.
• Eg:
       def long_function_name(
                   var_one, var_two, var_three
                   var_four):
          print( var_one )

     Tabs or Spaces?:

• Never mix tabs and spaces.
• Either follow indenting Python with spaces only or tabs only.

     Maximum Line Length:

• Limit all lines to a maximum of 79 characters.
• Wrapping long lines is done by using Python's implied line continuation inside parentheses, brackets and braces.
• The preferred place to break around a binary operator is after the operator, not before it.
• Eg:

   class Rectangle(Blob):

       def __init__ (self, width, height,

                     color='black', emphasis=None highlight=0):

           if (width == 0 and height == 0 and

               color == 'red' and emphasis == 'strong' or

               highlight > 100);

               raise ValueError("sorry you lose")

           if width == 0 and height == 0 and (color == 'red' or

                                              emphasis is None):

               raise ValueError("I don't think so -- values are %s,

                                %s" (width,height))

           Blob.__init__(self, width, height,

                         color, emphasis,highlight)

     Blank Lines:

• Separate top-level function and class definitions with two blank lines.
• Method definitions inside a class are separated by a single blank line.
• Extra blank lines may be used to separate groups of related functions.
• Use blank lines in functions, sparingly, to indicate logical sections.

     Encodings:

• Code in the core Python distribution should always use the ASCII or Latin-1 encoding.
• For Python 3.0 and beyond, UTF-8 is preferred over Latin-1.
• Files using ASCII should not have a coding cookie.
• Latin-1 (or UTF-8) should only be used when a comment or docstring needs to mention an author name that requires Latin-1; otherwise, using \x, \u or \U escapes is the preferred way to include non-ASCII data in string literals.
• All identifiers in the Python standard library MUST use ASCII-only identifiers, and SHOULD use English words wherever feasible.
• The only exceptions are
  (a) test cases testing the non-ASCII features, and
  (b) names of authors.

      Imports:

• Imports should usually be on separate lines.
• Eg:
            import os
       import sys.

• Imports are always put at the top of the file, just after any module comments and docstrings, and before module globals and constants.
• Imports should be grouped in the following order:
  

1. standard library imports
2. related third party imports
3. local application/library specific imports .

You should put a blank line between each group of imports.
Put any relevant __all__ specification after the imports.
• Relative imports for intra-package imports are highly discouraged. Always use the absolute package path for all imports.
• When importing a class from a class-containing module, it's usually okay to spell this:

                      from myclass import MyClass

                      from foo.bar.yourclass import YourClass.

      Whitespace in Expressions and Statements:

• Avoid extraneous whitespace in the following situations:
• Immediately inside parentheses, brackets or braces.
• Immediately before a comma, semicolon, or colon.
• Immediately before the open parenthesis that starts the argument list of a function call.
• Immediately before the open parenthesis that starts an indexing or slicing.
• More than one space around an assignment (or other) operator to align it with another.

      Other Recommendations:

• Always surround these binary operators with a single space on either side: assignment (=), augmented assignment (+=, -= etc.), comparisons (==, <, >, !=, <>, <=, >=, in, not in, is, is not), Booleans (and, or, not).
• If operators with different priorities are used, consider adding whitespace around the operators with the lowest priority(ies). Never use more than one space, and always have the same amount of whitespace on both sides of a binary operator.
• Eg:
  

  i = i + 1

  submitted += 1

  x = x * 2 - 1

  hypot2 = x * x + y *y

• Don't use spaces around the = sign when used to indicate a keyword argument or a default parameter value.
• Eg:
  def complex(real, imag=0.0):
       return magic(r=real, i=imag).

• Compound statements (multiple statements on the same line) are generally discouraged.

     Comments:

• Comments should not be contradict. Always make a priority of keeping the comments up-to-date when the code changes!
• Comments should be complete sentences. If a comment is a phrase or sentence, its first word should be capitalized, unless it is an identifier that begins with a lower case letter .
• If a comment is short, the period at the end can be omitted. Block comments generally consist of one or more paragraphs built out of complete sentences, and each sentence should end in a period.
• You should use two spaces after a sentence-ending period.
• When writing English, Strunk and White apply.

     Block Comments:

• Block comments generally apply to code that follows them, and are indented to the same level as that code.
• Each line of a block comment starts with a # and a single space.
• Paragraphs inside a block comment are separated by a line containing a single #.

      Inline Comments:

• Use inline comments sparingly.
• Inline comments should be separated by at least two spaces from the statement.
• They should start with a # and a single space.

     Documentation Strings:

• Docstrings explain how to use code, and are for the users of your code.
• Explain the purpose of the function, help full to someone else later on.
• Describe the parameters expected, the return values, and any exceptions raised.
• Docstrings are useful in interactive use (help()) and for auto-documentation systems.

     Naming Conventions:

• joined_lower for functions, methods, attributes.
• joined_lower or ALL_CAPS for constants.
• StudlyCaps for classes.
• camelCase only to conform to pre-existing conventions.

     Prescriptive: Naming Conventions:

     Names to Avoid:

• Never use the characters 'l' , 'O' , or 'I' as single character variable names.

     Package and Module Names:

• Modules should have short, all-lowercase names.
• Underscores can be used in the module name if it improves readability.]
• Python packages should also have short, all-lowercase names, although the use of underscores is discouraged.
• It is important that module names be chosen to be fairly short .

     Class Names:

• Almost without exception, class names use the CapWords convention.
• Classes for internal use have a leading underscore in addition.

     Exception Names:

• Because exceptions should be classes, the class naming convention applies here. You should use the suffix "Error" on your exception names.

     Functional Names:

• Function names should be lowercase, with words separated by underscores as necessary to improve readability.

     Method Names and Instance Varibles:

• Use the function naming rules: lowercase with words separated by underscores as necessary to improve readability.
• Use one leading underscore only for non-public methods and instance variables.
• To avoid name clashes with subclasses, use two leading underscores to invoke Python's name mangling rules.

     Constants:

• Constants are usually defined on a module level and written in all capital letters with underscores separating words.

      Designing for Inheritance:

• Always decide whether a class's methods and instance variables should be public or non-public.
• Public attributes are those that you expect unrelated clients of your class to use, with your commitment to avoid backward incompatible changes.
• Non-public attributes are those that are not intended to be used by third parties.
• Another category of attributes are those that are part of the "subclass API"