[2008.06.27] Functional Programming Terms

Functional Programming is new to me and I have recently started learning F#. While it is not a 'pure' functional language, I feel that it is the middle ground between Functional and Imperative languages. Plus, since it is built to run on the CLR, you also have access to the rich collection classes the .NET framework has to offer.

As with everything else, functional programming has its own share of techno-babble. So as a start, I have decided to note the terms I have come across and the definitions/descriptions that go along with them.

Static Typing

Type checking done at compile time which will allow you to catch many errors before the program is ever fun. Languages that support this include C, C++, C#, Java, F#, Haskell.

Dynamic Typing

Type checking is done during runtime. This is also known as late binding and languages that support this include Perl, Python, PHP.

Type Inference

The ability of the compiler to determine the type of the variable based on what was used to initialize it. For example, C# 3.0 uses the var keyword for this, therefore in var x = 10;, the type of x is inferred to be an Int32.

Function

In mathematics, it illustrates a dependency relationship between two quantities and the function will return the same result each time the same argument is used.

In programming, a function or method is a block of code that performs a specific task and can have side effects, such as changing the state of an object.

Imperative Programming

Is a programming style which embrace state and effect. Some imperative programming languages are C, C++, C# and Java.

Object Oriented Programming (OOP)

In its simplest, it is the style of programming using mathematical functions which means that the functions are honest and show side effects in their type. Just like the definition of a function, in FP, passing the same argument to a function will produce the same result.

Honest Type

Is a type that tells you exactly what is going on, in that, exactly what happened in order to return the value to you.

Dishonest Type

The type doesn't tell you what's going on or how it returned the value to you. So if you look at a function and it promises to return an Int32, it may not do that actually.

For example, the function: Int32 MyFunction(Int32 x) takes an integer and indicates that it returns an integer as well. However, it may throw an exception or do some side effects that you are not aware of it but there is no indication in the function definition of these additional effects.

Side Effect

A side effect in programming has the effect of altering the state of the object. Side effects are things like return values, exceptions, IO, updating variables, etc. Basically, I think of it as all the useful things you can get out of a program.

First Class Function

The idea is that functions can be treated as values, that is, functions are values. As such can be used as return values, new functions/values can be created in the middle of executing the program and functions can be passed as arguments to other functions.

Higher Order Function:

Is a function which can take functions as arguments and return functions as output. Higher Order Functions are commonly known in the realm of functional programming as operators. For example, List.filter in F# is an operator that takes a function and a list and filters the input list based on the function passed to it. Operators are also an integral part of function composition.

Function Composition

Function Composition is the combination of first class functions and higher order functions as it allows simple functions to be chained together to create more complex functions. You can do this by passing in one function as an argument to another.

For example, in F#: let f g x = . . . is the same as saying, pass x to the function, f, and then take the result as pass it to g. Therefore, f g x is the same as g(f(x)).

Lazy Evaluation

The idea is to compute what is needed on demand, that is, compute what you want only when you need it. In F#, Lists and Arrays will produce a full result set, whereas Sequences uses lazy evaluation to return the first 4 values until more is needed.

Monoid

The simplest way to think of a monoid is that it is a collection of items with way of putting the items together, independent of what the items are. You can see that function composition basically uses the idea of monoids to chain simple functions together. Monoids must satisfy mathematical Associativity and Identity.

Monad

Follows the same rules as a monoid, but in addition, it allows for side effects. Monads basically encapsulate state in a succinct manner.

Lambda Expression

A lambda expression is a compact representation of a delegate, and a delegate is a class – therefore, a lambda expression is nothing more than a specialized class. The main point here is that LE gives you closure and anonymous expressions. Closure and anonymous expressions allow you to define new types inline and have access to the variables in the outer scope of the anonymous type.