BSD 4_4 release

[unix-history] / usr / src / old / lisp / fp / PSD.doc / manCh1.rno

.\" Copyright (c) 1980 The Regents of the University of California.
.\" All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\" 3. All advertising materials mentioning features or use of this software
.\"    must display the following acknowledgement:
.\"	This product includes software developed by the University of
.\"	California, Berkeley and its contributors.
.\" 4. Neither the name of the University nor the names of its contributors
.\"    may be used to endorse or promote products derived from this software
.\"    without specific prior written permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
.\"	@(#)manCh1.rno	6.2 (Berkeley) 4/17/91
.\"
.sp
.NS 1 "Background"
.sp
.pp
\fBFP\fP stands for a \fIFunctional Programming\fP language.
Functional programs
deal with \fIfunctions\fP instead of \fIvalues\fP.
There is  no explicit  representation of state, there are
no assignment statments, and hence,
no variables.
Owing to the lack of state, FP functions are free from
side-effects;  so we
say the FP is \fIapplicative\fP.
.pp
All functions take one argument and they are evaluated using
the single FP
operation, \fIapplication\fP (the colon ':' is the apply operator).
For example, we read $~+^:^<3~4>~$ as \*(lqapply
the function '+' to its argument <3 4>\*(rq.
.pp
Functional programs express a functional-level combination of
their components
instead of describing state changes using value-oriented
expressions.
For example, we write the function returning the
\fIsin\fP of the \fIcos\fP
of its input, \*(IE $sin(cos(x))$, as:
$sin^@^cos$.  This is a \fIfunctional expression\fP, consisting
of the single \fIcombining form\fP called \fIcompose\fP ('@'
is the compose operator)
and its \fIfunctional arguments\fP \fIsin\fP and \fIcos\fP.
.pp
All combining forms take functions as arguments and return
functions as results; functions may either be applied,
\*(EG
$sin @ cos^:^3$, or used as a functional argument in another functional
expression, \*(EG \fItan @ sin @ cos\fP.
.pp
As we have seen,
FP's combining forms allow us to express
control abstractions without the use of variables.
The \fIapply to all\fP functional form (&)
is another case in point.  The function '& exp'
exponentiates all the elements of its argument:
.sp 4p
.EQ I (1.1)
"&exp : <1.0 2.0>" ~==~ "<2.718 7.389>"
.EN
.sp 4p
In (1.1)
there are
no induction variables, nor a
loop bounds specification.
Moreover, the code is useful for any size argument,
so long as the sub-elements of its argument conform to the domain of the
\fIexp\fP function.
.pp
We must change our view of the programming process
to adapt to the functional
style.
Instead of writing down a set of steps that manipulate and assign values,
we compose functional expressions
using
the higher-level functional forms.
For example, the function  that adds a
scalar to all elements of a vector will be written in two steps.  First,
the function that distributes the scalar amongst each element
of the vector:
.sp 4p
.EQ I (1.2)
"distl : <3 <4 6>>" ~==~ "<<3 4> <3 6>>"
.EN
.sp 4p
Next, the function that adds the pairs of elements that
make up a sequence:
.sp 4p
.EQ I (1.3)
"&+ : <<3 4> <3 6>>" ~==~ "<7 9>"
.EN
.sp 4p
.pp
In a value-oriented programming language the computation
would be expressed as:
.sp 4p
.EQ I (1.4)
"&+ : distl : <3 <4 6>>,"
.EN
.sp 4p
which means to apply 'distl' to the input and then to apply '+'
to every element of the result.
In FP we write (1.4) as:
.sp 4p
.EQ I (1.5)
"&+ @ distl : <3 <4 6>>."
.EN
.sp 4p
The functional expression of (1.5) replaces
the two step value expression of (1.4).
.pp
Often,
functional expressions are built from the inside out,
as in LISP.
In the next example we derive a function that scales then
shifts a vector, \*(IE for scalars $a,~b^$ and a vector $v vec$,
compute $a~+~b v vec$.  This FP function will have three
arguments, namely $a,~b~$ and $~v vec$.  Of course, FP
does not use formal parameter names, so
they will be designated by the function symbols 1, 2, 3.
The first code segment scales $v vec~$ by $b$ (defintions
are delimited with curly braces '{}'):
.sp 4p
.EQ I (1.6)
"{scaleVec &\(** @ distl @ [2,3]}"
.EN
.sp 4p
The code segment in (1.5)
shifts the vector.
The completed function is:
.sp 4p
.EQ I (1.7)
"{changeVec &+ @ distl @ [1 , scaleVec]}"
.EN
.pp
In the derivation of the program we wrote from right to left,
first doing the \fIdistl\fP's and then composing with the
\fIapply-to-all\fP functional form.
Using an imperative language, such as Pascal,
we  would write the program from
the outside in, writing the loop
before inserting the arithmetic operators.
.pp
Although
FP encourages a recursive programming style,
it provides combining forms to avoid explicit recursion.
For example, the
right insert  combining form (!)
can be used to write a function
that adds up a list of numbers:
.sp 4p
.EQ I (1.8)
"!+ : <1 2 3>" ~==~ 6
.EN
.pp
The equivalent, recursive function is much longer:
.sp 4p
.EQ I (1.9)
"{addNumbers (null -> %0 ; + @ [1, addNumbers @ tl])}"
.EN
.pp
The generality of the combining forms encourages hierarchical
program development.  Unlike APL,
which restricts
the use of combining forms to certain builtin functions,
FP allows combining forms to take any functional expression as
an argument.
.bp