.\" Copyright (c) 1980 The Regents of the University of California.
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" 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
.\" @(#)manCh2.rno 6.2 (Berkeley) 4/17/91
.NS 1 "System Description"
The set of objects \(*W consists of
the atoms and sequences $fs$ (where the $x sub i memberOf OMEGA$).
(Lisp users should note the similarity to the list structure syntax,
just replace the parenthesis
by angle brackets and commas by blanks. There are no 'quoted' objects,
The atoms uniquely determine the set of valid objects and consist of the
numbers (of the type found in \s-2FRANZ LISP\s+2 [Fod80]), quoted ascii strings
("abcd"), and unquoted alphanumeric strings (abc3).
There are three predefined atoms, $T$ and $F$, that correspond
to the logical values 'true' and 'false', and the undefined atom $bold "?"$,
\fIBottom\fP denotes the value returned as the result of an
undefined operation, \*(EG division by zero.
The empty sequence, $<>$ is also an atom. The following are examples
$?$ $1.47$ $3888888888888$
There is one restriction on object construction: no object may contain
the undefined atom, such an object is itself undefined, \*(EG
$<1,?>~==~?$. This property is the
so-called \*(lqbottom preserving property\*(rq [Ba78].
This is the single FP operation and is designated by the colon (":").
For a function $sigma$ and an object $x$, $sigma : x$ is an application
and its meaning is the object that results from applying $sigma$ to
$x$ (\*(IE evaluating $sigma (x)$).
We say that $sigma$ is the \fIoperator\fP and that $x$ is
The following are examples of applications:
$bold + : <7,8>$ $==$ $15$ $bold tl :<1,2,3>$ $==$ $<2,3>$
\fB1\fP $: <a,b,c,d>$ $==$ $a$ \fB2\fP $: <a,b,c,d>$ $==$ $b$
All functions (\fIF\fP) map objects into objects, moreover, they are
sigma^:^? equiv ?,~~ forAll ^sigma^ memberOf F
To formally characterize the primitive functions,
we use a modification of McCarthy's conditional expressions [Mc60]:
p sub 1~->~ e sub 1~; ... ;~p sub n~->~ e sub n~;~e sub {n + 1}
This statement is interpreted as follows:
return function $e sub 1$ if the predicate '$p sub 1$' is
true $,...,~e sub n$ if '$p sub n$' is true.
If none of the predicates are satisfied then default to $e sub {n + 1}$.
It is assumed that $x ,~x sub i ,~y ,~y sub i ,~z sub i memberOf OMEGA$.
For a nonzero integer $mu$,
.ip "$bold mu~ : ~x~ ==$"
\&$x = fs ~ andsign ~0~<~mu~<=~k ~->~ x sub mu ;$
\&$x = fs ~ andsign ~-k <= mu < 0 ~ -> ~ x sub {k + mu + 1}; ~ ?$
.ip "$bold pick~ : ~<n,x>~ ==$"
\&$x = fs ~ andsign ~0~<~n~<=~k ~->~ x sub n ;$
\&$x = fs ~ andsign ~-k <= n < 0 ~ -> ~ x sub {k + n + 1}; ~ ?$
The user should note that the function
symbols \fB1\fP,\fB2\fP,\fB3\fP$,...$ are
to be distinguished from the atoms $1,2,3,...$.
.ip "$bold last ~ : ~x~ ==$"
\&$x = fs ~ andsign ~ k >= 1 ~ -> ~ x sub k ;~?$
.ip "$bold first ~ : ~x~ ==$"
\&$x = fs ~ andsign ~ k >= 1 ~ -> ~ x sub 1 ;~?$
\&$x = <x sub 1 > ~ -> ~ <> ~ ;$
\&$x = fs ~ andsign ~ k >= ~ 2 ~ -> ~<x sub 2 ~,..., ~x sub k > ~ ;~ ?$
.ip "$bold tlr ~ : ~ x~==$"
\&$x = <x sub 1 > ~ -> ~ <> ~ ;$
\&$x = fs ~ andsign ~ k >= ~ 2 ~ -> ~ <x sub 1 ~ ,..., ~x sub {k - 1} > ~ ; ~ ?$
Note: There is also a function
\fBfront\fP that is equivalent to \fBtlr\fP.
.b "Distribute from left and right"
.ip "$bold distl ~:~x~==$"
\&$x = <y, qz >~->~<<y,z sub 1 >,...,<y,z sub k >>;~?$
.ip "$bold distr ~:~x~==$"
\&$x = < qy , z >~->~<<y sub 1 , z >,...,<y sub k , z >>;~?$
\fBOut\fP is similar to \fPid\fP.
Like \fBid\fP it returns its argument as the result,
result on \fIstdout\fP \(mi
It is the only function with a side effect.
\fPOut\fP is intended to be used for debugging only.
.b "Append left and right"
.ip "$bold apndl ~:~x~==$"
\&$x = <y, qz >~->~<y, z sub 1 ,~ z sub 2 ,...,~ z sub k >;~?$
.ip "$bold apndr ~:~x~==$"
\&$x = < qy , z >~->~< y sub 1 ,~ y sub 2 ,...,~ y sub k ,~z >;~?$
.ip "$bold trans~:~x~==$"
\&$x = <<>,...,<>>~->~<>;$
\&$x = fs ~->~<y sub 1 ,..., y sub m >;~?$
\&where $x sub i ~=~<x sub i1 ,..., x sub im >~andsign
~ y sub j ~=~<x sub 1j ,..., x sub kj >,$
.ip "$bold reverse~:~x~==~$"
\&$x = fs ~->~ <x sub k ,..., x sub 1 >;~?$
.b "Rotate Left and Right"
\&$x = <>~ -> ~ <>;~x = <x sub 1 >~->~<x sub 1 >;$
\&$x = fs ~ andsign ~k >= 2~ -> ~ <x sub 2 ,..., x sub k , x sub 1 >;~?$
\&$x = <>~ -> ~ <>;~x = <x sub 1 >~->~<x sub 1 >;$
\&$x = fs ~ andsign ~k >= 2~ -> ~
<x sub k ,~ x sub 1 ,..., x sub {k - 2},~ x sub {k - 1} >;~?$
.ip "$bold concat~:~x~==$"
\&$x = <<x sub 11 ,..., x sub 1k >,<x sub 21 ,..., x sub 2n >
,...,<x sub m1 ,..., x sub mp >> ~ andsign ~ k, ~m, ~n, ~p ~>~ 0 ~->$
\&$<x sub 11 ,..., x sub 1k , x sub 21 ,..., x sub 2n ,..., x sub m1 ,..., x sub mp >; ?$
Concatenate removes all occurrences of the null sequence:
bold concat ~ :~ <<1,3>,<>,<2,4>,<>,<5>> ~==~ <1,3,2,4,5>
\&$x = fs ~ andsign ~ k >0 ~ andsign ~ k~is~even~->~ <<x sub 1 , x sub 2 >
,..., <x sub k-1 , x sub k >>;$
\&$x = fs ~ andsign ~ k >0 ~ andsign ~ k~is~odd~->~ <<x sub 1 , x sub 2 >
.ip "$bold split~:~x~==$"
\&$x = <x sub 1 > ~->~<<x sub 1 > , <>>;$
\&$x = fs ~ andsign ~ k > 1 ~ ->
~<<x sub 1 ,..., x sub {left ceiling k/2 right ceiling} >,
<x sub {left ceiling k/2 right ceiling + 1} ,..., x sub k >>; ?$
\&$x memberOf bold {N sup +} ~ ->~<1,2,...,x>;~?$
.NS 3 "Predicate (Test) Functions"
$bold atom~:~x~==~x~ memberOf atoms~-> ~ T ; ~ x$\(!=$? -> ~ F ;~ ?$
$bold eq ~:~x~==~x~=<y,z> ~ andsign ~ y=z ~ -> ~ T ;~x= <y,z> ~ andsign ~y$ \(!= $z ~->~ F ;~?$
Also less than ($bold <$), greater than ($bold >$),
greater than or equal (\fB>=\fP),
less than or equal (\fB<=\fP), not equal (\fB~=\fP);
\&'$bold =$' is a synonym for \fBeq\fP.
$bold null ~ : x~==~x = <> ~ -> ~ T ;~x$\(!=$?~ -> ~ F ;~?$
$bold length ~ :~ x~==~x~= ~ fs ~ -> ~ k; ~ x = <> ~ -> ~0; ~ ?$
.NS 3 "Arithmetic/Logical"
$bold +~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ ->~ y+z; ~ ?$
$bold -~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ -> ~y-z; ~ ?$
$bold *~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ -> ~y$\(mu$z; ~ ?$
\fB/\fP$~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ andsign
~z$\(!= $0 ~ ->~y$\(di$z ;~?$
$nd~:~<x,y>~==~x = T ~->~ y;~x= F ~->~ F ;~?$
$rr~:~<x,y>~==~x = F ~->~ y;~x= T ~->~ T ;~?$
.ip "$bold xor~:~<x,y>~==$"
\&$x = T ~ andsign ~ y = T ~->~ F ;~ x = F ~ andsign ~ y = F ~->~ F ;$
\&$x = T ~ andsign ~ y = F ~->~ T ;~ x = F ~ andsign ~ y = T ~->~ T ;~?$
$bold not~:~x~==~x= T ~->~F;~x= F~->~T ;~?$
$bold "sin"~:~x~==~x roman {~is~a~number} ~->~sin(x);~?$
$bold "asin"~:~x~==~x roman {~is~a~number}
~andsign~|x|~<=~1 ~->~sin sup {-1} (x);~?$
$bold "cos"~:~x~==~x roman {~is~a~number} ~->~cos(x);~?$
$bold "acos"~:~x~==~x roman {~is~a~number}
~andsign~|x|~<=~1 ~->~cos sup {-1} (x);~?$
$bold "exp"~:~x~==~x roman {~is~a~number} ~->~ e sup x;~?$
$bold "log"~:~x~==~x roman {~is~a~positive~number} ~->~ ln(x);~?$
$bold "mod"~:~<x,y>~==~ x nd y roman {~are~numbers} ~->~ x ~-~ y times
left floor x over y right floor ~;~?$
Functional forms define new \fIfunctions\fP
function and object \fIparameters\fP of the form.
The resultant expressions
can be compared and contrasted to the \fIvalue\fP-oriented
expressions of traditional programming languages.
The distinction lies in the domain of
the operators; functional forms manipulate functions, while traditional
operators manipulate values.
One functional form is \fIcomposition\fP. For two functions $phi$ and
$psi$ the form $phi ~ @ ~psi$ denotes their composition $phi ~$\*(cm$~ psi$:
( phi ~@~ psi )~:~x~==~phi :( psi :x),~~ forAll ~~x memberOf OMEGA
The \fIconstant\fP function takes an object parameter:
%x:y~==~y=?~->~?;~x,~~~ forAll ~~x,y~ memberOf OMEGA
The function $%?$ always returns ?.
In the following description of the functional forms, we assume that
$xi , ~xi sub i ,~sigma , ~sigma sub i ,~tau ,$ and $tau sub i$
$x,~x sub i ,~ y$ are objects.
$( sigma ~@~ tau ):x~==~sigma : ( tau : x)$
$[ sigma sub 1 ,..., sigma sub n ]:x~==~< sigma sub 1 : x,..., sigma sub n : x>$
Note that construction is also bottom-preserving, \*(EG
[ bold +, bold /]^:^<3,0>~=~<3,?>~=~?
.ip "$( xi~"->" ~sigma ;~tau ):x~==~$"
\&$( xi : x) = T~->~sigma : x;$
\&$~ ( xi : x)= F~ ->~tau :x;~?$
The reader should be aware of the distinction between
\fIfunctional expressions\fP, in the variant of McCarthy's conditional
and the \fIfunctional form\fP introduced here.
In the former case the result is a \fIvalue\fP, while in the latter case
the result is a \fIfunction\fP. Unlike Backus' FP, the conditional form
\fImust\fP be enclosed in parenthesis, \*(EG
roman {"(isNegative -> - @ [%0,id] ; id")}
$%x:y~==~y=?~->~?;~x,~~~~~~ forAll ~x memberOf OMEGA$
This function returns its object parameter as its result.
.ip "$! bold sigma~:x~==$"
\&$x = <>~->~e sub f : x;$
\&$x=<x sub 1 >~->~x sub 1 ;$
\&$x= fs ~ andsign ~k>2~->~ sigma :<x sub 1 ,~! sigma :<x sub 2 ,...,~x sub k >>;~?$
\&\*(EG $!+:<4,5,6> =15$.
If $sigma$ has a right identity element $e sub f$,
then $! sigma :<>~=~ e sub f$, \*(EG
!+^:^<> =0 ~roman "and" ~!*^:^<> =1
identity functions are defined for $+ \ (0),\ - \ (0), \ * \ (1),
also for \fBand\fP (T), \fBor\fP (F), \fBxor\fP (F). All other unit functions
.ip " \fB|\fP $sigma~:~x~==$"
\&$x = <>~->~e sub f : x;$
\&$x=<x sub 1 >~->~x sub 1 ;$
\&$x= fs ~ andsign ~k>1~->$
\&$bold sigma ~:~< $\fB|\fP$~ sigma~:~
<x sub 1 ,..., x sub {left ceiling k/2 right ceiling} >~,~
"\fB|\fP" ~ sigma ~:~<x sub {left ceiling k/2 right ceiling + 1}
"\fB|\fP" +:<4,5,6,7> ~==~ +:<+:<4,5> , +:<6,7>> ~==~ 15
Tree insert uses the same identity functions as right
.ip "\fB&\fP$^sigma :~x~==$"
\&$x= fs~->~< sigma : x sub 1 ,...,~sigma : x sub k >;~?$
.ip "(\fBwhile\fP$ ~xi~sigma ):x~==$"
\&$xi : x= T~->~($\fBwhile\fP$ ~xi~sigma ):( sigma : x);$
.NS 2 "User Defined Functions"
An FP definition is entered as follows:
where \fIfn-name\fP is an ascii string consisting of letters, numbers and the
underline symbol, and \fIfn-form\fP is any valid functional form, including
a single primitive or defined function.
is the non-recursive definition of
the factorial function. Since FP systems are applicative it is permissible
to substitute the actual definition of a function for any reference to it
in a functional form: if $f ~==~ 1 @ 2$ then $f~:~x~==~1@2~:~x,~~~
forAll ~x memberOf OMEGA$.
References to undefined functions bottom out:
f:x~==~? forAll x memberOf OMEGA ,~f^ notmemberof F