Daniel Jomphe's Library tagged language →  View Popular

template <typename T>
void qsort (T *result, T *list, int n)
{
    if (n == 0) return;
    T *smallerList, *largerList;
    smallerList = new T[n];
    largerList = new T[n];      
    T pivot = list[0];
    int numSmaller=0, numLarger=0;      
    for (int i = 1; i < n; i++)
        if (list[i] < pivot)
            smallerList[numSmaller++] = list[i];
        else 
            largerList[numLarger++] = list[i];
    
    qsort(smallerList,smallerList,numSmaller); 
    qsort(largerList,largerList,numLarger);
        
    int pos = 0;        
    for ( int i = 0; i < numSmaller; i++)
        result[pos++] = smallerList[i];
        
    result[pos++] = pivot;
                
    for ( int i = 0; i < numLarger; i++)
        result[pos++] = largerList[i];
        
    delete [] smallerList;
    delete [] largerList;
        
    return;
};

qsort []     = []
qsort (x:xs) = qsort less ++ [x] ++ qsort more
     where less = filter (<x)  xs
           more = filter (>=x) xs

An ideal situation is updating relevant parts of the code without stopping any part of the system at all. In an imperative
world this isn't possible. Consider unloading a Java class at runtime and reloading a new definition. If we were to do
that every instance of a class would become unusable because the state it holds would be lost. We would need to resort to
writing tricky version control code. We'd need to serialize all running instances of the class, destroy them, create
instances of the new class, try to load serialized data into them hoping the loading code properly migrates the data to work
with the new instance. On top of that, every time we change something we'd have to write our migration code manually.
And our migration code would have to take special care not to break relationships between objects.
Nice in theory, but would never work well in practice.

In a functional program all state is stored on the stack in the arguments passed to functions. This makes hot deployment
significantly easier! In fact, all we'd really have to do is run a diff between the code in production and the new version,
and deploy the new code. The rest could be done by language tools automatically! If you think this is science fiction, think
again. Erlang engineers have been upgrading
live systems without stopping them for years.

An interesting property of functional languages is that they can be reasoned about mathematically. Since
a functional language is simply an implementation of a formal system, all mathematical operations that could be done on
paper still apply to the programs written in that language. The compiler could, for example, convert pieces of code into
equivalent but more efficient pieces with a mathematical proof that two pieces of code are equivalent⁷.
Relational databases have been performing these optimizations for years. There is no reason the same techniques can't apply
to regular software.

Additionally, you can use these techniques to prove that parts of your program are correct. It is even possible to create tools
that analyze code and generate edge cases for unit tests automatically! This functionality is invaluable for rock solid systems.
If you are designing pace makers and air traffic control systems such tools are almost always a requirement. If you are writing
an application outside of truly mission critical industries, these tools can give you a tremendous edge over your competitors.

Let's extend our Java compiler to support this notation. When we
type something like this our compiler will convert it to the following Java code (don't forget, everything is final):

class add_function_t {
    int add(int i, int j) {
        return i + j;
    }
}

add_function_t add = new add_function_t();

The symbol add isn't really a function. It is a small class with one function as its member. We can now pass
add around in our code as an argument to other functions. We can assign it to another symbol. We can create instances
of add_function_t at runtime and they will be garbage collected when we no longer need them. This makes functions
first class objects no different from integers or strings. Functions that operate on other functions (accept them
as arguments) are called higher order functions. Don't let this term intimidate you, it's no different from Java
classes that operate on each other (we can pass class instances to other classes). We can call them "higher order classes" but nobody
cares to because there is no strong academic community behind Java.

dapter pattern is best known when applied to the "default" abstraction unit in Java - a class. In functional languages the
pattern is applied to functions. The pattern takes an interface and transforms it to another interface someone else expects.
Here's an example of an adapter pattern:

int pow(int i, int j);
int square(int i)
{
    return pow(i, 2);
}

The code above adapts an interface of a function that raises an integer to an integer power to an interface of a function
that squares an integer. In academic circles this trivial technique is called currying (after a logician Haskell Curry who
performed mathematical acrobatics necessary to formalize it). Because in FP functions (as opposed to classes) are passed around
as arguments, currying is used very often to adapt functions to an interface that someone else expects. Since the interface to
functions is its arguments, currying is used to reduce the number of arguments (like in the example above).

For example consider implementing the following control structure:

unless(stock.isEuropean()) {
    sendToSEC(stock);
}

We want sendToSEC executed unless the stock is European. How can we implement unless? Without lazy evaluation
we'd need some form of a macro system, but in a language like Haskell that's unnecessary. We can implement unless as a function!

void unless(boolean condition, List code) {
    if(!condition)
        code;
}

• In Scala, fields must be declared val (immutable) or var (changeable). Scala style encourages you to use val where possible.
• Scala's Set is immutable.

In Clojure, immutability is the default. In fact, everything is immutable, with only two exceptions:




• calling down into Java APIs (the Clojure version of assembly language)
• a few data structures which are specifically designed to support Software Transactional Memory

I’m of the belief that compiler checks don’t eliminate or even reduce programmer stupidity. They just make it go deeper by creating complexity. Have I written my fair share of stupid python code? Sure. But it’s rare that I ever find myself saying “WTF is this code doing?”

But you obviously view things differently and that’s a good thing.