***********
Subprograms
***********

.. index::
   single: subprogram

=====================
What is a subprogram?
=====================

A *subprogram* is a chunk of code that is independent from other parts
to some extent.  In most languages, subprograms have the following
properties.

- There is a single entry point.  (But Fortran provides multiple entry
  points.)
- When a subprogram *A* calls another subprogram *B*, *A* will pause
  until *B* terminates.  Namely, there is only one subprogram that is
  executed at a time.  (This is not the case for concurrent
  languages.)

.. index::
   single: function
   single: procedure
   single: subroutine
   single: method

In some languages, a subprogram that returns a value is called 
a *function* and one that does not is called a *procedure* or 
a *subroutine*, but both types of subprograms are called *functions* in
other languages such as C.  In addition, object-oriented languages
usually use the term *methods* for them.

.. index::
   single: parameter
   pair: actual; parameter
   pair: formal; parameter
   pair: positional; parameter
   pair: keyword; parameter
   
===========
 Parameter
===========

A *parameter* is used in order to apply a single subprogram to various
data.

  Actual parameters ::
    Data specified when a subprogram is called.
  Formal parameters ::
    Variable names used in a subprogram to store actual parameters.

* In many languages, acutal parameters are associated to formal
  parameters by their positions (*positional parameters*).  It is
  error-prone when a subprogram has many parameters.  In some
  languages, it is possible to specify a formal parameter for each
  actual parameter when calling (*keyword parameters*).

* In many lanuages, the number of actual parameters and formal
  parameters must be the same.  In some languages, it is possible to
  declare default values for formal parameters so that we can omit
  some actual parameters.

* In script lanuages such as Ruby, more than one actual parameters can
  be combined into an array to be stored in a single formal parameter,
  and vice versa.

.. admonition:: Parameters in Ada

   Suppose we have the following declaration in Ada.

   .. code-block:: ada

      procedure Draw_Rect( X , Y : Integer;
			   Width : Integer := 10;
			   Height : Integer := 10;
			   Color : Integer := 0 )

   We may write any of the following procedure calls.

   .. code-block:: ada
		   
      Draw_Rect( 100, 50, 20, 10, 1 )
      Draw_Rect( Width => 20, X => 100, Y => 50, Color => 1 )
      Draw_Rect( 100, 50, Width => 20, Color => 1 )

.. admonition:: Parameters in Ruby

   When a formal parameter has an asterisk, any number of actual
   parameters are combined into an array.

   .. code-block:: ruby

      def foo(*a)
        puts a  # output [1, 2, 3]
      end

      foo(1, 2, 3)

   When an actual parameter is an array and formal parameters are
   enclosed by a parenthes, elements of the array will be stored in
   the formal parameters one by one.  Surplus elements are ignored.

   .. code-block:: ruby

      def bar((a,b))
        puts a  # output 1
	puts b  # output 2
      end

      bar([1,2,3])

================================
 Direction of parameter passing
================================

  Input
    Data are passed from actual parameters to formal parameters
    when a subprogram is called.
  Output
    Data are passed from formal parameters to actual parameters
    when a subprograum finishes its execution.

In case of output, the actual parameter must be assignable, i.e. an
expression that has a left value (:numref:`left-value`), which is
typically a variable.

.. admonition:: Passing parameters in Ada

   .. code-block:: ada

      procedure Foo(A : in Integer;
		    B : in out Integer;
		    C : out Integer) is
      begin
	B := B + 1;
	C := A + B;
      end Foo;

.. _evaluationStrategyOfParameters:

===================================
 Evaluation strategy of parameters
===================================

.. index::
   single: pass by value
   
Pass by value (call by value)
-----------------------------

First, all the actual parameters are evaluated.  Then, the values are
copied to formal parameters.

* It is usually used for input direction.  In case it is used for both
  input and output, we specifically call it *pass-by-copy-restore*.

.. index::
   single: pass by reference

Pass by reference (call by reference)
-------------------------------------

Formal parameters are bound to entities referred by associated actual
parameters.  In other words, formal parameters become aliases
(:numref:`alias`) of actual parameters.

* Its direction is inherently both input and output.

.. admonition:: Passing parameters in Pascal

   In Pascal, a foraml parameter declared with ``var`` is
   pass-by-reference, otherwise pass-by-value (input only).

   For example, the following procedure does nothing at all.
   
   .. code-block:: pascal

      procedure swap(a, b : integer)
	temp : integer;
	begin
	  temp := a;
	  a := b;
	  b := temp
	end;

   If we change the first line as follows, it will swap values of two
   parameters.

   .. code-block:: pascal

      procedure swap(var a, b : integer)

.. index::
   single: pass by name

Pass by name (call by name)
---------------------------

Actual parameters are not evaluated when a subprogram is called.  They
are evaluated each time associated formal parameters are used in the
body of subprograms.  The environment used for evaluation is the one
at the place where the subprogram is called.

* In Algol, an assignment to a formal parameter implies an assignment
  to the associated actual parameter (provided it is assignable),
  which means the direction is input and output.  In Scala, an
  assignment to a formal parameter is prohibited, so the direction is
  input only.

* Precisely speaking, there are two methods to implement pass-by-name.

  * Actual parameters are evaluated each time formal parameters are used.

  * Actual parameters are evaluated at the first time formal
    parameters are used, and the values are memoized.  After that, the
    memoized values are used, and actual parameters are not evaluated.
    This method is also called *pass-by-need* to distinguish it from
    the previous method.

  Results of the two methods are the same as long as there is no
  side-effect, but they may be different if actual parameters or
  subprograms have side-effect.

.. admonition:: Passing parameters in Scala

   .. code-block:: scala

      var x = 0
      def f(a: => Int) = {
	  print(a)  // output 1
	  x = 2
	  print(a)  // output 3
      }
      f(x+1)

.. admonition:: Exercise 16
   :class: exercise

   Suppose we have the following C-like program.

   .. code-block:: c

      void main() {
	int x = 2, list[5] = {1, 3, 5, 7, 9};
	swap(x, list[0]);
	swap(list[0], list[1]);
	swap(x, list[x]);
      }

      void swap(int a, int b) {
	int temp;
	temp = a;
	a = b;
	b = temp;
      }

   Answer the values of variables ``x`` and ``list`` after execution
   when we use the following evaluation strategy of parameters,
   respectively.

   1. pass-by-value (input only)
   2. pass-by-reference
   3. pass-by-name (input and output, evaluate each time)

   **NOTE:** When using pass-by-name, assume that an assignment to a
   formal parameter implies an assignment to the associated actual
   parameter, thus the direction is input and output.

   :ref:`[Answer] <ex16-answer>`

.. index::
   single: closure
   
=========
 Closure
=========

In languages such as Lisp, Ruby, JavaScript, etc., a function is a
first-class object (i.e. it can be assigned into a variable, passed as
a parameter, etc.).

Suppose we put a function into a variable and call it later.

In case the language has static scope (:numref:`scope`), variables in
the function should be evaluated in the environment at the place the
function is defined (not the place the function is called).

In order to do that, we need to prolong extent (:numref:`extent`) of
variables of outer blocks so that the stored function can use those
variables.  This feature is called a *closure*.

.. admonition:: closure in JavaScript

   .. code-block:: javascript

      function get_increment_function() {
          var x = 1;
          return function() { return x += 1; };
      }

      var inc1 = get_increment_function();
      console.log(inc1());  // 2
      console.log(inc1());  // 3

      var inc2 = get_increment_function();
      console.log(inc2());  // 2

      console.log(inc1());  // 4

.. admonition:: Exercise 17
   :class: exercise

   Suppose we want to create 10 buttons in a web page, each of which
   will show its id number when clicked.  But the following JavaScript
   code does not work properly.  Explain why.

   .. code-block:: javascript

      var b = document.getElementsByTagName("input");
              // Returns an array of 10 button objects.
      let i;      
      for (i = 1; i <= 10; i++) {
	  b[i-1].onclick = function(){ alert(i); };
      }

   :ref:`[Answer] <ex17-answer>`