Ken has posted 2 posts at DZone. View Full User Profile

An Introduction to Functional Languages

06.25.2009
| 29072 views |
  • submit to reddit

There has been explosion of software development languages in recent years. Chief among these languages or programming approaches is functional programming. This article will go through the details of functional programming; concepts, terms, approaches, and languages. The target audiences for this article are developers that already understand programming but are totally new to functional programming.

What is Functional Programming?

If you have been writing code for a long time with an object-oriented language (such as Java or C#) it may be difficult to imagine a different way to approach programming. Functional programming does just that. At the heart of functional programming is a new way to address a software problem- by focusing on the function decomposition of the algorithm(s). With functional programming, functions are first class citizens. If you come from the Java world, you can already appreciate the difference. In Java, the only way to express a method is as a component of a class.

Although a recent uptick in special purpose languages has gotten all the attention, functional programming is a technique and not necessarily a language. It is possible to write in a functional way with a general purpose or object-oriented language (in a later section we examine a functional example written in C#). Although it is possible, for anything significant, the lack of expressiveness quickly becomes apparent and anti-patterns start to crop up. Imagine trying to write an object-oriented program of any significant size using Java without the keywords extend or implements. These difficulties naturally lead to the need for a new language; a functional language.

Characteristics of Functional languages

One of the core tenets of a functional language is that it is not an imperative language. In an imperative language, the variable defined in a function represents a place in memory with a defined size, which usually has an assigned value that can change through the execution of the method. In a functional language the assignment of a value to a variable is binding, just as it would be in a mathematical function. In a math example, we might say: let x = 2. That is to say for this problem, x is the value of 2. The value of x cannot change as we evaluate this problem it is always 2. As we think in these terms, common programming practices begin to not make sense any more, like the following assignment: let x = x + 1. While this equation makes imperative programming sense, it makes absolutely no mathematical sense. There is no solution to x where x is equivalent to x+1. When you understand this concept, you are on the path to functional development.

As with Math, functional languages are not limited to just numerical value assignments. Methods in a functional language are first class citizen. So a method closure can be assigned to a variable and be passed around or leveraged in other function expressions. Comparing this again to math we can say: let x = f(y). In mathematical terms the value of x is the function f of y. For a value of y we will get a value of x. This is another core concept of functional programming. X will always be the same for a given y; it will never be a different value.

While there are variations in a number of functional programming languages, functional programming usually has the following characteristics:

  • Function Closure Support

  • Higher-order functions

  • Use of recursion as a mechanism for flow control

  • No side-effects

  • A focus on what is to be computed rather then how to compute it

  • Referential transparency

Functional languages

As we look back in the history of computer languages, we see that functional languages have been with us for some time. The most notable “grandfather” languages would include, LISP and FORTRAN. Since the mid-1980s these languages for enterprise and commercial development have taken a back seat to object-oriented languages, while functional languages have remained mostly in the academic scene. The following is a list of notable functional programming languages moving into the commercial scene:

Erlang

A general-purpose concurrent programming language and runtime named after A.K. Erlang. It contains elements of functional constructs, along with an Actor concurrency model, allowing for a simplified concurrency approach.

Haskell

An open source language greater than 20 years old, which was designed to be a purely functional programming language.

OCaml

Objective Caml is an open source implementation of the Caml programming language, which is dialect of the ML programming language, which is a general purpose functional programming language developed in 1970. It is credited as being the base of a number of functional programming languages including F#.

Lisp

LISt Processing language is a functional programming language that was originally specified in 1958. LISP has a number of dialects to its credit.

Scala

Scala is a language designed to integrate functional and object-oriented programming running on the Java Virtual Machine. It is a strongly typed programming language.

Clojure

Clojure is a modern dialect of the Lisp programming language that runs on the Java Virtual Machine, which is designed for concurrency. It is a dynamically typed programming language.

F#

A new language which runs on the .Net CLR, which is an implementation of OCaml and brings together functional programming and imperative object-oriented programming. It is a strongly typed programming language.



It is important to note that functional programming does not require a dynamic language. Functional language choices allow for a dynamic or static typing. The languages listed are just a small subset of all the functional languages, each one as noted fulfilling a unique need. This article isn’t a focus on any one specific functional language, as we will see a number of language examples. The one important question we haven’t answered yet is why? Why has there been should an uptick in demand for functional languages and why now?

Why Functional?

A significant change in the modern computing platform is the addition of multiple cores. Outside of the new netbook computers and PDAs, you can’t find a computer or a laptop that has a single core in it any more. We are moving to multi-core, multi-processor machines and all signs indicate this trend will continue. In addition to multi-core, high processing and complex algorithm environments are moving toward leveraging graphic processing units or GPU for highly parallel processing. The sum of all of this from a developer’s standpoint is concurrency.

Most of our programming languages make concurrency hard. Think of it this way; decades ago error handling in a c program was littered through the code base. It was integrated in with the business logic. C functions would return 0 for success and an error number for a failure code. It was obvious this wasn’t ideal, but the language was limited in expressing error handling in any other way. Along come other languages, C++ or Java, where error handling through exception handling abstracts the business code from the error handling code. Some might argument that it isn’t great, but it is at least a step better. This illustrates the same level of maturity in our industry with concurrency. If you have a need to provide concurrency in a program in an object-oriented language, it has to be well thought out. The simple cases of spinning off a print job thread require little in the way of concurrency control, but in many cases there is a need to share state across threads, resulting in blocking on monitors. As the number of cores increases, resulting in a possible larger number of concurrently running threads, the efficiency of the system degrades. What we need is a new language, one that abstracts us from all this work in taking advantage of concurrency.

Functional languages already aid in the development of constructs that ease concurrent development, through the benefit of functions which do not share memory and which exhibit no side effects. As you dig deeper into functional languages you’ll discover that many of them abstract the developer from the concept of concurrency, in some cases it is darn right far to tell that processing is occurring concurrently. Many of the languages implement a pattern of concurrent development referred to as the actor model, where instead of threads sharing state, messages are passed between threads, thereby removing thread blocking.

Another value add of functional languages is conciseness. In chapter 1 of Stuart Halloway’s book Programming Clojure, Stu shows how 3 lines of clojure code is a factor of 3 smaller than the Jakarta Commons equivalent and is simpler in that it has no branching logic.

An important observation is that functional languages are not a replacement for procedural or object-oriented programming language. Reading through the list of functional languages in the previous section, notice that many of the newer functional languages are multi-paradigm languages that run on virtual machines and bridge other object-oriented and imperative languages. The idea is to use the most appropriate language for the problem at hand. I expect that general practitioners will continue to use a general-purpose language such as Java, Groovy or C# for mainstream needs, but when faced with a highly complex algorithm or a high concurrency need they will switch out to functional programming, integrating these solutions. This is exactly what Neal Ford has been describing for years, referring to it as the “polygot programmer”.

Functional Functions and Functional Terms

There are a number of new terms associated with functional programming, but no term comes up faster than Lambda. As mentioned, there is a close association between functional development and mathematics. Lambda refers to lambda calculus or -calculus. No wait… don’t run away. Lambda calculus is a system designed to investigate function definition, function application and recursion.

Listing 1: A simple lambda expression

There is a lot to lambda calculus we are not going to explore here. In the simplest of expressions as in listing 1, lambda just provides a new syntax. The example listed is a unary function, meaning it only takes one parameter or an arity of 1. We could also pass a function to a function as in listing 2.

Listing 2: A simple lambda function passing

The explanation and details are at the web reference provided on lambda calculus. In listing 2, each row is equivalent. The f function is passed the x function and applies a 3 to it. The x function taking the 3 is 3+2. This a very common practice in functional languages to have one function build upon another function. Consider listing 3.

Listing 3: functions as values

In listing 3, we have 3 functions. The function scale_by_2 is a method that takes the scale function and applies it to 2. It returns the equivalent of λ n. x * 2. Functional development is often layers upon layers of functions in this type of style.

Closure

Another term and aspect of functional programming is closures. Closures are common in variety of programming languages today and the term is commonly interpreted to mean a method reference or anonymous function. Technically closures are dynamically allocated data structures containing a code pointer, pointing to a fixed piece of code computing a function result and an environment of bound variables. A closure is used to associate a function with a set of “private” variables. Anonymous functions are a technique used to accomplish this in some languages, which is where the line gets blurred for those new to the concepts.

Function powerFunctionFactory(int power) {
int powerFunction(int base) {
return pow(base, power);
}
return powerFunction;
}
Function square = powerFunctionFactory (2);
square(3); // returns 9
Function cube = powerFunctionFactory (3);
cube(3); // returns 27

In listing 4, the function factory returns a function that will raise a number to a power. When we invoke the square function, the necessary power variable isn’t in scope… how can this work? The function powerFunctionFactory has returned and the stack is gone. The cube method has the same problem and this is another power to be raised. The language must store the value and it must store it for each created function. This is called closure.

Closures allow for the passing of custom behavior as arguments to functions, which leads us to our next important term “currying”

Currying

Currying is a cool word, which simply refers to the technique of transforming a function that takes multiple arguments in a way that can be called as a chain of functions which each take a single argument. So given a function foo(x,y) which results in the value of z, better expressed foo(x,y) -> z. We need to break the function down into multiple functions, which will require the passing or returning of a function. Do you see how this technique is congruent with lambda calculus?

So what if the function bar(x) -> baz then baz(y) -> z, or stated another way. The method bar will take the parameter x and return a function baz. When the function baz is given the parameter y, the result is z. So foo(x,y) -> z can now be expressed as:

bar(x) -> baz

baz(y) -> z

Lets move away from theory and into practice, with a functional programming example in C#. Yes this is possible in C# 3.5.

 

 

Func<int, Func<int,int>> scale =
x => y => x * y;

var scaleBy2 = scale(2);
scaleBy2 (100);

 

 

Our normal tendency may be to create a method that takes 2 numbers, the value 100 with our scale factor 2. Using functional practices, the function scale(2) returns the function which can be applied to another variable. We name that function scaleBy2, but we could have just as easily “chained” the execution. By naming the reference to the function, we have a function that can be leveraged throughout the entire program. If you are still missing the justification don’t worry yet, we are still discussing the building blocks to functional programming.

Data Structures

Some of the data structures in functional languages include tuples, and monad. Tuples are immutable sequences of objects. Sequences, lists and trees are very common data structures in functional languages. Most languages provide operators and libraries in order to simplify working with them. We will see examples in F# later in this article.

A Monad is an abstract data type used to represent control flows or computations. The purpose of monads is to express input/output operations and changes in state without using language features that introduce side effects.

Pattern Matching

Pattern matching is nothing innovative or even specific to functional programming. It is commonly associated with functional programming because the more common mainstream languages still do not have this language feature. Pattern matching is nothing more than a concise way to match a value or type. If you have ever had a long complex series of if, if/else statements or a complicated switch statement, then suffice it to say you understand the value of pattern matching. Listing 6 shows an example of matching using Mathematica to find a given Fibonacci sequence.

fib[0|1]:=1
fib[n_]:= fib[n-1] + fib[n-2]

Listing 6: Mathematica example of pattern matching

The match of 0 or 1 is 1. The match of any other value causes a recursive call back into fib. It would be a challenge to see a more concise approach to calculate a Fibonacci sequence number. In a later f# example you’ll notice a match on a discriminating union, which is a union of defined specific types. It is a very powerful technique.

 

Part 2 of this article will deal with functional programming using F#

 

 

 

 

Published at DZone with permission of its author, Ken Sipe.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags:

Comments

Gerrit Cap replied on Thu, 2009/06/25 - 4:11am

Excellent !!!!!!!!!!

Ricky Clarkson replied on Thu, 2009/06/25 - 9:19am

"If you have been writing code for a long time with an object-oriented language (such as Java or C#) it may be difficult to imagine a different way to approach programming."

I think you'll find that most C# programmers are at least familiar with delegates, and a good number with anonymous methods.  Lambdas are still quite new to the language, so not as many know them yet.

"In a functional language the assignment of a value to a variable is binding, just as it would be in a mathematical function."

According to this, 4 of your functional languages aren't, namely Scala, Lisp, OCaml and F#.

rebol tutorial replied on Thu, 2009/06/25 - 10:52pm

You should also read Carl Sassenrath's article explaining the concept of referentially transparency (RT) in Functional Programming and why REBOL 1.0 was PFL (pure functional language) but relaxed on later version:

"That fact made REBOL's implementation very complex, but more importantly it made its execution 30 times slower than REBOL 2.0 that followed it. "

http://www.rebol.com/article/0206.html

To learn Rebol (I'm not an employee of Rebol company, just a beginner's fan of this amazing language):

http://reboltutorial.com

 

Otengi Miloskov replied on Fri, 2009/06/26 - 1:16am

Why not the second part of this tutorial with Scala?, We java developers does not care F# because does not run on the jvm but Scala it is.

My favorite is the pure functional language Haskell. If in the future I will do functional development, I want to do it in pure way not just bolted-on, As OOP I liked the almost pure way than the bolted-on as in C++. It was ugly.

josef betancourt replied on Fri, 2009/06/26 - 7:06am

Very informative article.  I wonder if Functional Programming is still valuable in non-pure FP languages.  What are the limitations?

 For example, some techniques can be used in the Groovy language, see here:  http://docs.codehaus.org/display/GROOVY/Functional+Programming+with+Groovy

rebol tutorial replied on Fri, 2009/06/26 - 7:58pm in response to: josef betancourt

Limitation is performance see

Carl Sassenrath's article on referentially transparency (RT) in Functional Programming and why REBOL 1.0 was PFL (pure functional language) but relaxed on later version:

http://www.rebol.com/article/0206.html


 

Ted Neward replied on Tue, 2009/06/30 - 1:53am in response to: Otengi Miloskov

The concepts are the important part; the language shouldn't matter.

 

Having said that, if the demand is high enough, I'll work with Ken to create a set of Scala examples to go along with the F# ones.

Arek Stryjski replied on Thu, 2009/07/02 - 5:55pm

"Outside of the new netbook computers and PDAs, you can’t find a computer or a laptop that has a single core in it any more. We are moving to multi-core, multi-processor machines and all signs indicate this trend will continue."

Well not all.

It is possible what with "Cloud computing" we will return to single thread paradigm (see Google App Engine).
I even thing what "cloud" will be more and more popular, because it will allow 90% of developers to ignore concurrency.

But of course it does not mean what functional programming will not be more important in coming years.

replied on Thu, 2009/07/16 - 12:11pm in response to: Ted Neward

Thank you for including F#. As a .NET programmer I don't write any software for the JVM but it is always informative to do hands on work to reinforce your understanding of concepts. With Scala and F# examples everyone can try some hands on work whether they work with the JVM or CLR to make sure they are correctly internalizing the concepts presented. 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.