Functional programming: Examples, Methods and Concepts
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast with the imperative programming style that emphasizes changes in state.
The lambda calculus provides the model for functional programming. Modern functional languages can be viewed as embellishments to the lambda calculus.
While not fully functional, both the original Lisp and APL were important in the development of functional programming. Later versions of Lisp such as Scheme and variants of APL did provide full functional support. Other important functional languages include Erlang, Haskell, and ML.
Functional programming languages, especially purely functional ones, have largely been emphasized in academia rather than in commercial software development. However, notable functional programming languages used in industry and commercial applications include Erlang, OCaml, Haskell, Scheme (since 1986) and domain-specific programming languages like R (statistics), Mathematica (symbolic math), J and K (financial analysis), and XSLT (XML).
What is a purely functional language
Functional programming languages are informally classified into pure and impure languages. The precise meaning of this distinction has been a matter of controversy. We therefore investigate a formal definition of purity. We begin by showing that some proposed definitions that rely on confluence, soundness of the beta axiom, preservation of pure observational equivalences, and independence of the order of evaluation, do not withstand close scrutiny. We propose instead a definition based on parameter-passing independence. Intuitively, the definition implies that functions are pure mappings from arguments to results; the operational decision of how to pass the arguments is irrelevant. In the context of Haskell, our definition is consistent with the fact that the traditional call-by-name denotational semantics coincides with the traditional call-by-need implementation. Furthermore, our definition is compatible with the stream-based, continuationbased, and monad-based integration of computational effects in Haskell. Finally, we observe that call-by-name reasoning principles are unsound in compilers for monadic Haskell.
Functional programming in non-functional languages
It is possible to employ a functional style of programming in languages that are not traditionally considered functional languages. Some non-functional languages have borrowed features such as higher-order functions, and list comprehensions from functional programming languages. This makes it easier to adopt a functional style when using these languages. Functional constructs such as higher-order functions and lazy lists can be obtained in C++ via libraries. In C one can use function pointers to get some of the effects of higher-order functions, for example one can implement the common function map using function pointers. Widespread declarative domain specific languages like SQL and Lex/Yacc, while not always Turing-complete, use some elements of functional programming, especially in eschewing mutable values.
Imperative programs tend to emphasize the series of steps taken by a program in carrying out an action, while functional programs tend to emphasize the composition and arrangement of functions, often without specifying explicit steps. A simple example of two solutions to the same programming goal (using the same multi-paradigm language Python) illustrates this.
# imperative style target =  # create empty list for item in source_list: # iterate over each thing in source trans1 = G(item) # transform the item with the G() function trans2 = F(trans1) # second transform with the F() function target.append(trans2) # add transformed item to target
A functional version has a different feel to it:
# functional style # FP-oriented languages often have standard compose() compose2 = lambda F, G: lambda x: F(G(x)) target = map(compose2(F, G), source_list)
In contrast to the imperative style that describes the steps involved in building
target, the functional style describes the mathematical relationship between
List of functional programming topics
- Programming paradigm
- Declarative programming
- Programs as mathematical objects
- Function-level programming
- Purely functional
- Lambda programming
- Static scoping
- Higher-order function
- Referential transparency
- Sequent, sequent calculus
- Natural deduction
- Intuitionistic type theory
- BHK interpretation
- Linear logic
- Game semantics
- Typed lambda calculus
- Typed and untyped languages
- Type signature
- Type inference
- Algebraic data type
- Type variable
- First-class value
- Calculus of constructions
- Graph reduction
- Non-strict programming language
- Lazy evaluation, eager evaluation
- Speculative evaluation
- Continuation passing style
- Operational semantics
- State transition system
- Simulation preorder
- Monads in functional programming
- Exception handling
- Garbage collection (computer science)
- Clean programming language
- Erlang programming language
- FP programming language
- F# programming language,
- Haskell programming language
- Kent Recursive Calculator
- Kogut programming language
- Mercury programming language
- Miranda programming language
- ML programming language
Curry: A Truly Integrated Functional Logic Language
Curry is a universal programming language aiming to amalgamate the most important declarative programming paradigms, namely functional programming and logic programming. Moreover, it also covers the most important operational principles developed in the area of integrated functional logic languages: “residuation” and “narrowing” (there is an older survey and a newer survey on functional logic programming).
Curry combines in a seamless way features from functional programming (nested expressions, higher-order functions, lazy evaluation), logic programming (logical variables, partial data structures, built-in search), and concurrent programming (concurrent evaluation of expressions with synchronization on logical variables). Moreover, Curry provides additional features in comparison to the pure languages (compared to functional programming: search, computing with partial information; compared to logic programming: more efficient evaluation due to the deterministic and demand-driven evaluation of functions).
The development of Curry is an international initiative intended to provide a common platform for the research, teaching and application of integrated functional logic languages. The design of Curry is mainly discussed in the Curry mailing list. A detailed report describing the language is available here. To get an idea of Curry, you may have a look into the short list of Curry’s features or a tutorial on Curry. (more)
Microsoft moves on F# functional language
F# (pronounced F Sharp) is a multi-paradigm programming language, targeting the .NET Framework, that encompasses functional programming as well as imperative object-oriented programming disciplines. It is a variant of ML and is largely compatible with the OCaml implementation. F# was initially developed by Don Syme at Microsoft Research but is now being developed at Microsoft Developer Division and will be distributed as a fully supported language in the .NET Framework and Visual Studio ecosystem.
F# is a programming language that provides the much sought-after combination of type safety, performance and scripting, with all the advantages of running on a high-quality, well-supported modern runtime system. F# gives you a combination of (more)
Haskell is an advanced purely functional programming language. The product of more than twenty years of cutting edge research, it allows rapid development of robust, concise, correct software. With strong support for integration with other languages, built-in concurrency and parallelism, debuggers, profilers, rich libraries and an active community, Haskell makes it easier to produce flexible, maintainable high-quality software. (more)
Simon Peyton Jones on Functional Programming and Haskell on http://www.se-radio.net
We start our discussion with a brief look at what Haskell is and how a pure functional language is different from non-pure languages. We then look at the basic building blocks and the philosophy of the language, discussing concepts such as the lambda calculus, closures, currying, immutability, lazy evaluation, memoization, and the role of data types in functional languages. A significant part of the discussion is then spent on the management of side effects in a pure language – in other words, the importance of monads. We conclude the episode with a look at Haskell’s importance and community today.
Objective Caml (OCaml) is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. OCaml is an open source project managed and principally maintained by INRIA.
OCaml extends the core Caml language with object-oriented constructs.
OCaml’s toolset includes an interactive toplevel interpreter, a bytecode compiler, and an optimizing native code compiler. It has a large standard library that makes it useful for many of the same applications as Python or Perl, as well as robust modular and object-oriented programming constructs that make it applicable for large-scale software engineering.
OCaml is the successor to Caml Light. The acronym CAML originally stood for Categorical Abstract Machine Language, although OCaml abandons this abstract machine. (more)
As it turns out Coq is really a dependently typed functional programming language masquerading as a proof assistant! I’ve spent quite a lot of time over the past few weeks writing total functional programs in Coq and proving properties about them. I’ve done a bunch of simple things so far, including a proof of correctness for various properties of insertion sort. I started with merge sort, but stalled when it got too complicated. I’m starting to get a feel for using Coq however and large proofs are getting much easier. (more)
Functional Programming with Python (RuPy 2008)
Python is a general-purpose, high-level programming language. Its design philosophy emphasizes programmer productivity and code readability. Python’s core syntax and semantics are minimalist, while the standard library is large and comprehensive. It is unusual among popular programming languages in using whitespace as block delimiters.
Python supports multiple programming paradigms (primarily object oriented, imperative, and functional) and features a fully dynamic type system and automatic memory management; similar to Perl, Ruby, Scheme, and Tcl.
Python was first released by Guido van Rossum in 1991. The language has an open, community-based development model managed by the non-profit Python Software Foundation. While various parts of the language have formal specifications and standards, the language as a whole is not formally specified. The de facto standard for the language is the CPython.