Functional Programming and first class functions

Is every language a functional programming language?

No, every programming language does not support functional programming.

There’s a lot of evolution of functions in functional programming.

In functional programming, Functions are called as first class because :

1.functions can be passed as arguments

2.functions can be returned as value from other function

3.functions can be assigned to a variable

4.functions can be stored in data structures

5.nested functions

6.anonymous functions(function with no name)

What is the problem with first class functions?

Name-binding/Scoping !

Local variables — the variables defined inside a function.

The compiler/lexer has no problem identifying them, as there are visible inside the function.

Nonlocal or Free variables: Free variables- the variables defined outside of a function. Or not visible inside a function.

Problem: How does the compiler identifies non-local variables and which non-local variables can the function access?

Earlier languages like C, although allowing to pass functions as arguments, but did not support nested functions, hence did not ran into problem of name binding.
All the situations stated above need some mechanism with which the name-binding for non-local variables or free variables can be solved.

Solution: The solution depends on scoping rules of language (lexical or dynamic).The mechanism in lexically scoped languages is called as CLOSURES.

Before we get into details of closures, we need to understand lexical and dynamic scopes.

In computer programming, the scope of a name binding — an association of a name to an entity, such as a variable — is the region of a computer programwhere the binding is valid: where the name can be used to refer to the entity. Such a region is referred to as a scope block. In other parts of the program the name may refer to a different entity (it may have a different binding), or to nothing at all (it may be unbound).

In computer science, the funarg problem refers to the difficulty in implementing first-class functions (functions as first-class objects) in programming language implementations so as to use stack-based memory allocation of the functions.

There are two subtly different versions of the funarg problem. The upwards funarg problem arises from returning (or otherwise transmitting “upwards”) a function from a function call. The downwards funarg problem arises from passing a function as a parameter to another function call.

There are certain implementation difficulties in passing functions as arguments or returning them as results, especially in the presence of non-local variables introduced in nested and anonymous functions. Historically, these were termed the funarg problems, the name coming from “function argument”. In early imperative languages these problems were avoided by either not supporting functions as result types (e.g. ALGOL 60, Pascal) or omitting nested functions and thus non-local variables (e.g. C). The early functional language Lisp took the approach of dynamic scoping, where non-local variables refer to the closest definition of that variable at the point where the function is executed, instead of where it was defined. Proper support for lexically scoped first-class functions was introduced in Scheme and requires handling references to functions as closures instead of bare function pointers, which in turn makes garbage collection a necessity.

In lexical scope, the name resolution depends on the location in the source code and the lexical context(outer reference), which is defined by where the named variable or function is defined. This is a property of the program text and is made independent of the runtime call stack by the language implementation. Because this matching only requires analysis of the static program text, this type of scoping is also called static scoping. Lexical scoping is standard in all ALGOL-based languages such as Pascal, Modula2 and Ada as well as in modern functional languages such as ML and Haskell.

In contrast,

In dynamic scope, the name resolution depends upon the program state when the name is encountered which is determined by the execution context or calling context/call stack.

In lexical scoping, the outer reference/scope of a function depends on where it is written or defined and not where it is being called from as in dynamic scope.

e.g.:

$ x=1

$ function g () { echo $x ; x=2 ; }

$ function f () { local x=3 ; g ; }

$ f

$ echo $x

Lexical scope output->1,2

dynamic scope output-> 3,1.

In programming languages, closures (also lexical closures or function closures) are techniques for implementing lexically scoped name binding in languages with first-class functions.

JavaScript as a programming language provides support for first class functions and hence has lexical scope and uses closures.

More on Closures in detail in this post.