************************
 Functional Programming
************************

==========================================
 What is functional programming language?
==========================================

Common features of functional programming languages are as follows:

* A program is a set of functions.
* A function is a first class object.
* There is no such thing as statements or commands.  Evaluating
  expressions is the only way to execute a program.
* There is referential transparency.

.. index::
   single: referential transparency

==========================
 referential transparency
==========================

A language has *referential transparency* if literally same expressions
always result in the same value as long as the environment is the
same.

Variable
--------

Since a single variable is an expression, referential transparency
implies that the value of the variable is always the same.

In other words, a variable name is directly bound to a value
(cf. :ref:`binding`).  Note that the same name may be bound to another
value in another environment.

You may think switching environments is virtually same as assigning
new values.  However, there are differences as follows:

* Environments are usually associated with syntactic structures while
  assignments are non-structured and hard to predict their influence.

* Since creation of a new environment does not affect existing
  environments, there is no side-effect.

Loop
----

With referential transparency, it is impossible to have a loop
structure such as ``while`` because the value of its condition never
changes.

Instead, recursive functions are usually used for iterations in
functional languages.  Each time a function is called, a new
environment is created so that a condition may have another value.

Data structure
--------------

When we have a complex data, referential transparency implies that its
structure never changes.  It is also called *persistent data
structure* or *immutable data structure*.

Although it is called persistent, it may be removed by the garbage
collector.

.. note::

   Whereas the most prominent feature of functional languages is
   referential transparency, not so many languages strictly follow the
   policy.  For example, Lisp has ``setq`` (assignment to variables)
   which breaks referential transparency.  However, many people say
   Lisp is a functional language because it is possible to write a
   program with only features that keep referential transparency.

   When we want to emphasize that every feature of a language keeps
   referential transparency, we say the language is pure functional.

.. index::
   single: lambda calculus

===================
 Theoretical basis
===================

*Lambda calculus* is a formal system used for research of theoretical
computer science.  See `Wikipedia
<https://en.wikipedia.org/wiki/Lambda_calculus>`_ for detail.

Reduction
---------

In mathematics, the right side of :math:`1+2=` may be :math:`4-1` or
:math:`\sqrt{9}`.  However, we expect the value of ``1+2`` is ``3`` in
computer programs.  Reduction is, intuitively speaking, a procedure to
convert an expression into a simpler equivalent expression.

* :math:`\beta`-reduction in lambda calculus corresponds to applying a
  function to its arguments in programming languages.

* Given a lambda expression, we can repeatedly apply
  :math:`\beta`-reduction until it is irreducible any more.  The final
  expression is called the *normal form* of the given expression.

* Normal form may not exist because :math:`\beta`-reduction may be
  applicable infinitely many times.

Reduction strategy
------------------

A lambda expression may have more than one part for which
:math:`\beta`-reduction is applicable.  A *reduction strategy* is a
rule to choose the next reduction step.

applicative order

  Select the innermost part for which :math:`\beta`-reduction is
  applicable.  There is a possibility that reduction continues forever
  even if the expression has a normal form.

normal order

  Select the outermost part for which :math:`\beta`-reduction is
  applicable.  Reduction always reach the normal form if it exists.

Reduction strategies correspond to evaluation strategies in
programming languages (cf. :ref:`evaluationStrategyOfParameters`, :ref:`lazyEvaluation`).

.. list-table::
   :header-rows: 1

   * - applicative order
     - normal order
   * - strict evaluation
     - non-strict evaluation
   * - eager evaluation
     - lazy evaluation
   * - pass by value
     - pass by name

Reduction steps that do not reach the normal form corresponds to an
infinite loop in programming languages.
  
.. admonition:: Strictness and infinite loop

   JavaScript is a strict language.  ``bar(foo("a"))`` goes into
   an infinite loop.

   .. code-block:: javascript

      function foo(x) {
	return foo(x)
      }

      function bar(x) {
	return "b"
      }

      console.log(bar(foo("a")))


   Haskell is a non-strict language.  ``bar(foo("a"))`` returns ``"b"``.

   .. code-block:: haskell

      foo :: String -> String
      foo x = foo x

      bar :: String -> String
      bar x = "b"

      main = putStrLn (bar (foo "a"))

=======
 Monad
=======

There are several cases where referential transparency obstacles
practical use of the language.

* Random number: It is nonsense that the function ``random`` returns
  the same value every time.
* Input/Output: The function ``getLine`` should return strings typed
  by humans.

Haskell, a pure functional language, has introduced *monad* to solve the
problems above.

* Monad is a simple mechanism that generates a new type from an
  existing type by adding auxiliary information.

* IO monad is somewhat special.

  * It encapsulates input/output operation as auxiliary information.

  * For example, ``getLine`` always returns the same value whose type
    is ``IO string``.

  * Actual input/output operations are done by Haskell runtime.

* cf. `You Could Have Invented Monads! (And Maybe You Already Have.) <http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html>`_