<!--
  - Authors:
  -   Seif Haridi (seif@sics.se)
  -   Nils Franzen (nilsf@sics.se)
  -
  - Copyright:
  -   Seif Haridi, Nils Franzen, 1998
  -
  - Last change:
  -   $Date: 1999-01-21 11:01:50 +0100 (Thu, 21 Jan 1999) $ by $Author: schulte $
  -   $Revision: 10566 $
  -
  - This file is part of Mozart, an implementation
  - of Oz 3
  -    http://www.mozart-oz.org
  -
  - See the file "LICENSE" or
  -    http://www.mozart-oz.org/LICENSE.html
  - for information on usage and redistribution
  - of this file, and for a DISCLAIMER OF ALL
  - WARRANTIES.
  -
  -->

<CHAPTER ID="chapter.functional">
<TITLE>Functions</TITLE>

<SECTION><TITLE/Functional Notation/
<P>Oz provides functional notation as syntactic convenience. We have seen
that a procedure call:

<<<{P X1 ... Xn R}>>>

could be used in a nested expression as a function call:

<<<{P X1 ... Xn}>>>

Oz also allows functional abstractions directly as syntactic notation
for procedures. Therefore, the following function definition:

<<<fun {F X1 ... Xn} ?{S} ?{E} end>>>

where ?{S} is a statement and ?{E} is an expression corresponds to the
following procedure definition:

<<<proc {F X1 ... Xn R} ?{S} R=?{E} end>>>

<P CLASS=WARNING>The exact syntax for functions as well as their
transformation into procedure definitions is defined in the
<ref.extern to="ozdoc:notation"/<EM>The Oz Notation Reference Manual</EM>/.

<P>Here we rely on the reader's intuition. Roughly speaking, the
general rule for syntax formation of functions looks very similar to
how procedures are formed. With the exception that, whenever a thread
of control in a procedure ends in a statement, the corresponding
function ends in an expression.

<P>The program shown in <PTR TO="CheckBinTreeLazy3"> is the functional
equivalent to the program shown in <PTR TO="CheckBinTreeLazy">. Notice
how the function <<AndThen/2>> is unfolded into the procedure
<<AndThen/3>>. Below we show a number of steps that give some
intuition of the transformation process. All the intermediate forms
are legal Oz programs.

<<<
fun {AndThen BP1 BP2}
   if {BP1} then {BP2}
   else false end
end
>>>

<P>Make a procedure by introducing a result variable <<B>>:

<<<
proc {AndThen BP1 BP2 B}
   B = if {BP1} then {BP2}
       else false end
end
>>>

<P>Move the result variable into the outer <EM>if-expression</EM> 
to make it an <EM>if-statement</EM>:

<<<
proc {AndThen BP1 BP2 B}
   if {BP1} then B = {BP2}
   else B = false end
end
>>>


<P><FIGURE ID="CheckBinTreeLazy3" CLASS="Figure">
<CAPTION>Checking a binary tree lazily</CAPTION>
<<<
% Syntax Convenience: functional notation
local
   fun {AndThen BP1 BP2}
      if {BP1} then {BP2}
      else false end
   end
   fun {BinaryTree T}
      case T
      of nil then true
      [] tree(K V T1 T2) then
         {AndThen
          fun {$} {BinaryTree T1} end
          fun {$} {BinaryTree T2} end}
      else false end
   end
end
>>>
</FIGURE>

<P>If you are a functional programmer, you can cheer up! You have your
functions, including higher-order ones, and similar to lazy functional
languages Oz allows certain forms of tail-recursion optimizations that
are not found in certain strict functional languages
<NOTE FOOT>Strict
functional languages evaluate all its argument first before executing
the function</NOTE> 
including Standard ML, Scheme, and the concurrent
functional language Erlang. However, standard function definitions in
Oz are not lazy. Lazy functions are also supported in Oz<NOTE FOOT> We will
discuss them later when talking about <EM>futures</EM> and by need 
synchronization</NOTE>.

<P>Here is an example of the well-known higher order function
<<Map/2>>. It is tail recursive in Oz but not in Standard ML or in
Scheme.

<<<
fun {Map Xs F}
   case Xs
   of nil then nil
   [] X|Xr then {F X}|{Map Xr F}
   end
end
{Browse {Map [1 2 3 4] fun {$ X} X*X end}}
>>>

<SUBSECTION><TITLE/<<andthen>> and <<orelse>>/
<P>After all, we have been doing a lot of work for nothing! Oz already
provides the Boolean lazy (non-strict) versions of the functions
<<And/2>> and <<Or/2>> as the Boolean operators <<andthen>> and
<<orelse>> respectively. The former behaves like the function
<<AndThen/2>>, and the latter evaluates its second argument only if
the first argument evaluates to <<false>>. As usual, these operators are
not primitives, they are defined in Oz. <PTR TO="CheckBinTreeLazy4">
defines the final version of the function <<BinaryTree>>.

<P><FIGURE ID="CheckBinTreeLazy4" CLASS="Figure">
<CAPTION>Checking a binary tree lazily</CAPTION>
<<<
fun {BinaryTree T}
    case T of nil then true 
    [] tree(K V T1 T2) then 
       {BinaryTree T1} andthen {BinaryTree T2} 
    else false end 
end
>>>
</FIGURE>



<SUBSECTION><TITLE/To Function or not to function?/
<P>Since now, in principal, we have some syntactic redundancy by
either using procedures or functions, the question is when to use functional notation, and when not. The
honest answer is that it is up to you! I will tell you my personal
opinion. Here are some rules of thumb:

<LIST>

<ITEM>First, what I do not like. Given that you defined a procedure
<<P >>do not call it as a function, i.e. do not use functional nesting
for procedures. Use instead procedural nesting, with nesting marker,
as in the <<SMerge>> example. Moreover, given that you defined a
function, call it as function. 

<ITEM>I tend to use function definitions when things are really
functional, i.e. there is one output and, possibly many inputs, and
the output is a mathematical function of the input arguments.

<ITEM>I tend to use procedures in most of the other cases,
i.e. multiple outputs or nonfunctional definition due to stateful data
types or nondeterministic definitions<NOTE FOOT>In fact, in those
cases the use of the object-oriented style of Oz is most appropriate</NOTE>.

<ITEM>One may relax the previous rule and use functions when there is
a clear direction of information-flow although the definition is not
strictly functional. After all functions are concise.

</LIST>

</CHAPTER>
