PLC Session 12

Session 12: Functional Programming Languages

A. Introduction to Functional Programming Languages

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutabledata. It is a declarative programming paradigm, which means programming is done with expressions or declarations instead ofstatements. In functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function f twice with the same value for an argument x will produce the same result f(x) each time. Eliminating side effects, i.e. changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.

Functional programming has its roots in lambda calculus, a formal system developed in the 1930s to investigate computability, the Entscheidungs problem, function definition, function application, and recursion. Many functional programming languages can be viewed as elaborations on the lambda calculus. Another well-known declarative programming paradigm, logic programming, is based on relations.

In contrast, imperative programming changes state with commands in the source language, the most simple example being assignment. Imperative programming does have functions—not in the mathematical sense—but in the sense of subroutines. They can have side effects that may change the value of program state. Functions without return values therefore make sense. Because of this, they lack referential transparency, i.e. the same language expression can result in different values at different times depending on the state of the executing program.

Functional languages use a different paradigm than imperative and object oriented languages. They use side effect free functions as a basic building block in the language. This enables lots of things and makes a lot of things more difficult (or in most cases different from what people are used to)

One of the biggest advantages with functional programming is that the order of execution of side effect free functions is not important. For example in erlang this is used to enable concurrency in a very transparent way. And because functions in functional languages behave very similar to mathematical functions it’s easy to translate those into functional languages. In some cases this can make code more readable.

Traditionally one of the big disadvantages of functional programming was also the lack of side effects. It’s very difficult to write useful software without IO, but IO is hard to implement without side-effects in functions. So most people never got more out of functional programming than calculating a single output from a single input. In modern mixed paradigm languages like F# or scala this is easier.

Lots of modern languages have elements from functional programming languages. C# 3.0 has a lot functional programming features and you can do functional programming in python too. I think the reasons for the popularity of functional programming is mostly because of two reasons. Concurrency is getting a real problem in normal programming because we’re getting more and more multiprocessor computers. And the languages are getting more accessible.

In functional programming, functions are treated as objects. But in C++, functions are not treated as an object. To remedy that,function objects or lambdas are just a class with operate method.

As it’s tedious to create a class for each function, C++ provides a shortcut syntax to create function objects.

auto println = [](const char *message){ std::cout << message << std::endl;};

Above code is creating a function object,println, which takes a single parameter and returns nothing. The []brackets are used to specify the environment aka closure for the function. We will see more about closure in later part of the post.

As you can see, we use auto here so that we don’t have to care about how these function objects are encoded inside the C++ types.

B. LISP (Programming Language)

Lisp is the second-oldest high-level programming language after Fortran and has changed a great deal since its early days, and a number of dialects have existed over its history. Today, the most widely known general-purpose Lisp dialects are Common Lisp and Scheme.

Lisp was invented by John McCarthy in 1958 while he was at the Massachusetts Institute of Technology (MIT). Lisp was originally created as a practical mathematical notation for computer programs, influenced by the notation of Alonzo Church‘s lambda calculus. It quickly became the favored programming language for artificial intelligence (AI) research. As one of the earliest programming languages, Lisp pioneered many ideas in computer science, including tree data structures, automatic storage management, dynamic typing, conditionals, higher-order functions, recursion, and the self-hosting compiler.

The name LISP derives from “LISt Processor”. Linked lists are one of Lisp’s major data structures, and Lisp source code is made of lists. Thus, Lisp programs can manipulate source code as a data structure, giving rise to the macro systems that allow programmers to create new syntax or new domain-specific languages embedded in Lisp.

The interchangeability of code and data gives Lisp its instantly recognizable syntax. All program code is written as s-expressions, or parenthesized lists. A function call or syntactic form is written as a list with the function or operator’s name first, and the arguments following; for instance, a function f that takes three arguments would be called as (f arg1 arg2 arg3).

C. Comparison of Functional and Imperative

1) Functional programming treats everything as a function. The key point is it does not have a state associated with it i.e it is immutable.
So, the next best thing in terms of its usage is concurrent programming. As concurrent operations can be performed much easily without having to worry about state changes.
Having to learn functional programming paradigms lets you understand the common semantics and syntax that most of the programming languages use.

2) Imperative programming is procedural programming which is more focussed on how things are done. It has steps associated with it to perform a task, states and immutable objects.

Object oriented programming is a very common imperative style of programming.Here everything revolves around objects which are real life entities. It has the excellent concepts of encapsulation and abstraction which are the building blocks of object oriented programming style.

Nowadays, people are focussing on hybrid languages which use the best of both approaches. One such example is SCALA which is a hybrid language.

Imperative programming involves writing your program as a series of instructions (statements) that can actively modify memory (variables, arrays). Imperative programming focuses on how, in the sense that you express the logic of your program based on how the computer would execute it.

Functional programming involves writing your program in terms of functions and other mathematical structures. A function is just a rule that maps input elements to output—unlike an imperative procedure or subroutine, it can’t rely on outside state or have any side-effects. Functional programming concentrates on the what, trying to let you specify the logic of your program as close to actual logic as possible rather than basing its semantics on how a computer would execute it.

Fundamentally, functional programming is a different basis from imperative programming. It provides a completley new foundation for writing programs and requires a different way of thinking. However, there are some advantages: functional languages tend to be more expressive, so you end up writing less code; they tend to be safer so that more bugs are prevented by the language ahead of time and they have some featuresimpossible in normal languages because side-effects are controlled.