Saturday 27 September 2014

Programming with Invariants


Computation is a process of unfolding the given problem over time.  It is the process of identifying if the problem is solvable or not. In more concrete terms, as we speak to computer science graduates, it the question of “Can you write an algorithm for the given problem?

Algorithms play a central role in both the science and practice of computing. They are sequence of unambiguous instructions for solving a problem. Precisely, algorithm is a logical, arithmetical or computational procedure that if correctly applied ensures the solution of a problem. An algorithm has to be lucid, precise and unambiguous and give the correct solution in all cases. More importantly it has to terminate after a finite numbers of steps aka the finiteness property.

The algorithms we study concentrate on the space and time efficiency. Though we list several desirable properties of an algorithm like simplicity, correctness, unambiguous etc there is no formal method established to verify these properties. Primary concern of every algorithm designer has to be indeed verifying correctness; only then later to establish efficiency parameters. In this regard, programming with invariants is not a new paradigm but definitely the one every programmer needs to adapt.

Procedure:

1. Understand the problem.
2. Write few examples to verify your understanding.
3. Write the state space. State space is basically the domain of the problem. The type of data on which the processing is about to happen.
4. Identify the transition function which describes the various states the process can be in.
5. Write down the traces to authenticate the transition function
6. Identify the invariant. Invariant is property that proves the correctness of the algorithm. It is that one property that does not change in the algorithm.
 
Example:

1. Problem: 
Given a list, find the length of the list. The task is to identify how many elements are present in the list.


2. Examples:


3. State Space:
Input: List of integers
Output: Natural number with is the length of the list
List --> Natural


4. Transition Function:



5. Trace:



6. Invariant:
Observing the transition function and the trace we can conclude that the invariant for the process is:
1 + list-length (n-1)

Reasoning being at any point of iteration, we can use the invariant and find the length of the list! by the way, identifying a invariant is not an easy task. It comes by practice. I have just adapted the process into my coding routines!

Sunday 14 September 2014

Why Suddenly The languages I Studied Look Bad!??




(Image Ref: http://en.wikibooks.org/wiki/Programming_Languages)

The decisive goal of each programming language is to keep it effortless for the user and conceal the complexity in the implementation. The intact notion of theory in computer science verbalizes the abstraction by keeping it easy to the user. The theory puts a demand that every perception needs a formal proof for acceptance. Concept is goal driven to optimize it to the computer architecture. After completion of my degree, when I have the bigger picture of what I have acquired, I still have following questions unanswered.

The Expression Notation
We study about prefix and postfix notations and its greater advantages. Why do not the programming languages we use follow prefix/postfix evaluation of expressions? Why is not my language a set of expressions formally proving my program is right?

The Data Type
Data is information. User should write the data leaving behind the type of storage to the system. But we don’t do that! Instead we are also asked to communicate the type of data and hence defining a data type.  Instead, for the user there should be only one data type. The “data” data-type. May be that’s why I can’t return functions. Language would be so cool, if there was a provision to return the functions as well as a result.

The Definition of Data-Type
The definition of the data-type itself looks a faulty one. It’s not about how the data is stored in memory. In the first case, why should I even worry about how the data fits in the memory layout? It should be all about the operations which are possible on the data. Data type should be more of algebra on the data.

The Address Operation
Why the user is made aware of registers and pointer operations? Was it to cover up the limitations of the language? Instead, should not the language implementation take care of all the efficiency issues and not make it a concern to the user?

The Idea of Programmable
We all speak of domain specific languages today. Why is not my language customizable? It should be as small as possible which can grow as large as possible. User bears in mind very few details and grows the language in his own terms.  Why there is a restriction that execution has to begin with “main”? Why is writing an interpreter for my required domain so complex? Is it that the limitations of a language are covered up by adding more features than providing the abstraction?

The list of questions keeps growing like an ant trail. And that’s when you start falling in love with Functional programming.