Click here to Skip to main content
15,867,834 members
Articles / Programming Languages / F#

Introduction to Functional Programming using F# - Part 2

Rate me:
Please Sign up or sign in to vote.
3.10/5 (6 votes)
3 Feb 2009CC (ASA 2.5)5 min read 29.5K   23   2
This article explains the fundamentals of functional programming and lambda calculus

Background

In part 1 of this article, I explained the fundamentals of functional programming using F#. In this section, I explain the advantages of functional programming and a comparison between procedural and functional. Finally, I explain why F# and other most popular functional languages are not pure functional.

Advantages of Functional Programming

More Corresponds to Mathematics

If you are coming from a mathematics background, most of the computer theories are strongly based on Mathematics. Though we are now living in the trend of rapid application development in which core and repetitive tasks are abstracted, we find solutions to the real world problems on top of these abstractions. Anyhow, problem-solving is based on mathematics. The level of complexity and the appliance of mathematics help to find more effective solutions. Functional programming correspond more to mathematics. With a set of denotational semantics (you can see some simple examples in part 1 of this article), functional languages enable you to resolve a problem in a much simpler and effective manner than procedural languages. This denotational semantics saves us from non-terminated loop statements, goto and break statements.

No Side-effect on Expression Evaluation

Functional languages are created in such a way as to mimic the Mathematical concepts, hence sub-expressions in an expression can be evaluated at any order. This characteristic enables functional languages as the choice for parallel programming.

Parameterized Types and Functions

In part 1 code 4, you can see that the function square requires a function as an argument with the following denotational semantic:

F#
let square (f : int -> int) n = f(n) * f(n);;

Like this, all types and functions are clearly parameterized what needs to be given and what will be returned. This characteristic makes the code more general meaning that you can apply a functionality to different related types.

Short Order of Magnitude O(n)

As we know, that order of magnitude is used to compare the performance between different algorithms for solving a particular problems, smaller the value higher in the performance. In comparing with typical procedural, theoretically there is no assignments in functional programming. (See the examples in part 1). Procedural programs contains 90 percent of assignment statements. This is the major reason for them having higher O(n) than functional.

Real Modular Programming

OO programming allows to do modular programming, however, with the compliment of parameterized type and non-sequential properties allows to write real modular programming using functional languages. You can see code 4 of part 1 where a function is consumed in a modular manner.

Where Functional Overtakes Procedural?

It is surprising that most of the procedural languages have some of the functional behaviour. Where do functional languages overtake procedural? Let us see.

  • Procedural languages such as C, C++ have function pointers, there we can treat them as high order and curried functions. However, those function pointers are very limited and in these languages, you cannot create functions dynamically without any name.
  • Those procedural languages too support recursive. But, these are again handled by sequential statements like a human approaches the computer.

Lambda Calculus - Origin of Functional Programming

Since it corresponds more to mathematics, functional programming concept is based on the mathematics Lambda Calculus. It is a system to express any type of algorithm in a much more effective and simpler way. Generally, in maths and procedural languages, functions are to be defined and referred by an arbitrary name, for example:
f(x) = { 0 if x = 0
x2 sin(1/x2) if x ? 0 But in high order functions, insistence on naming is rather inconsistent.

For example:
Define x and y by x = 2 and y = 4, then we can say xx = y, in this there is no need to give any name to this function.

A function can be defined anonymously in lambda calculus which expresses the function's action on its argument. Lambda calculus provides a notation ? to define a function. For example, f(x) = x + 1 can be defined as ?x.x+1. Here, the name of the function and parameters are immaterial and this application of this function f(2) would be (?x.x+1) 2. In this example, ? is function, x is an argument and x+1 is the function body.

Definition of Lambda Calculus

If t is a lambda calculus, if

  • t = x where x ? variables
  • t = ?x.M where x ? variables and M is lambda expression
  • t = MN where M and N are lambda expression

Function application is left associative, for example f x y = (f(x))(y). Simple, a lambda calculus takes only one argument and applies it and returns one result. All the functional language behaviours (recursive, any order evolution, stateless) are actually the basic behaviours of lambda calculus.

There are two types of variables that exist in lambda:

  • Bound Variable: This falls within the function (or lambda) scope.
  • Free Variable: This takes the value from the expression in the function body.

For example, in ?x.xy, x is bound variable and y is free variable. In programming languages, we call these as argument or parameter and local variable respectively.

Why F# & Other Popular Functional Languages are NOT Pure Functional

The two immediate reasons are:

  • Immutability: As we learned, immutable data structure causes performance. However, for collection type, immutability is much better than the mutability. F# stands at this point.
  • Inapplicable Places: Functional programming concepts are not suitable for some scenarios, for example I/O operation and GUI. In these areas, imperative style is recommended.

Summary

In this part, we learned the advantages and fundamental concepts behind functional languages. Also, view my two part screen cast about Functional Programming with C# 3.0 at http://www.screencast.com/t/a0lgbHiF7cF and http://www.screencast.com/t/dndqkp4r, or, download both from http://cid-1ea86c1fb1c134b8.skydrive.live.com/browse.aspx/ScreenCast.

History

  • 3rd February, 2009: Initial post

License

This article, along with any associated source code and files, is licensed under The Creative Commons Attribution-ShareAlike 2.5 License


Written By
Architect Aditi
India India
Working as Architect for Aditi, Chennai, India.

My Website: www.udooz.net

My Blog: www.udooz.net/blog

Comments and Discussions

 
GeneralMy vote of 3 Pin
Björn Friedrich11-Jan-11 10:39
Björn Friedrich11-Jan-11 10:39 
GeneralMy vote of 2 Pin
cebess16-Feb-09 1:12
cebess16-Feb-09 1:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.