Functional Programming and Quicksort

Just stumbled upon the Haskell page.

Looks like Functional Programming really has some points :

• In functional programs, most of the times, the specification is THE code . Take for eg, the quicksort example in Haskell :
  

         qsort []     = []
       qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                      where
                         elts_lt_x   = [y | y <- xs, y < x]            
                         elts_greq_x = [y | y <- xs, y >= x]

• You specify what you want and not how you want it to be done. In the above example, you are just specifying the property ( invariant ) that is to be obeyed at every step of the algorithm. In case of imperative programming languages, you have to "mentally execute the programs to be able to write programs".

• The most important feature of a functional programming language is that functions are treated as first class objects, in the sense you can define functions at runtime, compose functions just like you would assign values to variables , use them to construct expressions in imperative functions.

• One more thing to be noted is the polymorphic nature of the above program. The quicksort program above can be used to sort chars, ints, list of chars, list of list of chars and so on. In case of C, you would need separate programs for 1-D, 2-D and 3-D arrays.

• Other features of FPs include automatic garbage collection, lazy evaluation and so on.
  

• Pitfalls : The quicksort program is from the view of the specifier ( mathematician ? ). It has no references whatsoever to any code for memory management, so the Haskell system ends up using a lot of space behind the scenes, whereas in C, Hoare's method sorts the array in place.

• Functional Programming languages are more suited in those environments where users are willing to take a dip in performance while trading it with ease-of-program writing, fewer bugs and more often that not using programs which have been proven to be working correct !
  

Turing Complete Languages

• A programming language is said to be Turing complete if it has computational power equivalent to a Universal Turing machine (UTM) -

  "It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine"

• Physically any such programming language is impossible to achieve since it requires unlimited storage ( Why ? ) . So , the term Turing complete languages applies to all those programming languages that would emulate a UTM if provided with unlimited storage.

• All general purpose programming languages are Turing complete ( C, Java, LISP, Haskell, Prolog etc ) . The non-Turing complete PLs are rare to find, for eg, machines that always halt, those languages in which it would be impossible to form loops. Also, not all programs solved by Turing complete languages can't be solved by programming languages with finite looping capabilities.

[Reference]

On Searches

• Find whether an user-given element exists in a cyclically sorted array [ For eg, say find whether 108 exists in a cyclically sorted array 67,89,109,4,26,33,45,55 with indices from 1 to 8 ] .

• Suppose you have an infinite sequence of integers ( lets say some kind of streaming data ) all of which arrive in sorted order in a buffer area ( in the form of an array ) . How do you find a particular element ? Note that you can't use a binary search since the size of the array is not known
  

• Suppose you know beforehand that an array has sorted integers in such a way that they are almost uniformly distributed. How do you find the existence of a particular element ?

Answers(?)

• Two binary searches , one to find the smallest element and hence start of the sorted array and another to find the required element

• Use the doubling search . Search elements at positions 2,4,8,16,32, etc .Once the range is found, binary search within the range . O(log i) + O(log j) where 'i' is the index at which you stop doubling search and 'j' is the number of elements within the range
  

• Use the interpolation search . Rather than dividing the interval by half everytime, try to guess the neighbourhood of the element of interest by finding out the interval of separation between successive elements ( works well with uniformly distributed elements ). [Reference].Supposed be of O(loglogn) on an average ( Proof ? )
  

Programmer Defined Overloading : Syntatic Heroin ?

An ACM Queue article : http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=315

Author's Arguments :

Things with different meanings are made to look the same, hampers readability, complicates compiler writing ( resolution of the function call to the right function definition), any inadvertant mistakes by the programmer in making a function call coupled with conversion rules lands us in soup.

Note that all these arguments are being made for programmer defined overloading and the author sees no problems with built-overloading ( for eg, of operators )

Can the same arguments be made for generics/templates ? Tradeoffs between developer( code writer) friendliness, maintainer ( debugger ) friendliness and compiler writer friendliness ? Are the lack of proper typing rules really to blame rather than overloading ?

Interestingly this article has a reference to the JLS :-) . Overloading & Java ?

Why SSA is good for Java compilation

"The strong typing in Java simplifies much of the compiler analysis. In particular, Java semantics ensure that a local variable can only be modified by explicit
assignment to the variable. In contrast, the creation of a pointer to a local variable in C allows a local variable to be modified at any time by any routine. Similarly, a field of a Java object can never be modified by an assignment to a different field. Because of these properties that make most data
dependences explicit in Java programs, we believe that static
single assignment (SSA) form is highly appropriate as an intermediate
representation for Java. SSA graphs make most or all of the dependences in a method explicit, but provide great freedom in optimizing and scheduling the resulting code."
- The Swift Java Compiler: Design and Implementation