.\" Copyright (c) 1980 Regents of the University of California.
.\" All rights reserved.  The Berkeley software License Agreement
.\" specifies the terms and conditions for redistribution.
.\"
.\"	@(#)manCh2.rno	6.1 (Berkeley) 4/29/86
.\"
.NS 1 "System Description"
.sp
.NS 2 "Objects"
.sp
.pp
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,
\*(IE 'abc).
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.
\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
of valid FP objects:
.sp 2
.(b C
.TS
center;
l l l.
$?$	$1.47$	$3888888888888$	
$ab$	"$CD$"	$<1,<2,3>>$
$<>$	$T$	$<a,<>>$
.TE
.)b
.sp 2
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].
.sp
.NS 2 "Application"
.sp
.pp
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 \fIoperand\fP.
The following are examples of applications:
.sp 2
.TS
center;
l c l l c l.
$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$
.TE
.sp 2
.nr ii 0.35i
.NS 2 "Functions"
.sp
.pp
All functions (\fIF\fP) map objects into objects, moreover, they are 
\fIstrict\fP:
.sp 6p
.EQ I (2.1)
sigma^:^? equiv ?,~~ forAll ^sigma^ memberOf F
.EN
.sp 6p
To formally characterize the primitive functions,
we use a modification of McCarthy's conditional expressions [Mc60]:
.sp 6p
.EQ I (2.2)
p sub 1~->~ e sub 1~; ... ;~p sub n~->~ e sub n~;~e sub {n + 1}
.EN
.sp 6p
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$.
.sp
.NS 3 "Structural"
.sp
.b "Selector Functions"
.(b M F
.sp
For a nonzero integer $mu$,
.sp
.nf
.ip "$bold mu~ : ~x~ ==$"
.sp 4p
\&$x = fs ~ andsign ~0~<~mu~<=~k ~->~ x sub mu ;$
.sp 4p
\&$x = fs ~ andsign ~-k <= mu  < 0 ~ ->  ~ x sub {k + mu + 1}; ~ ?$
.fi
.)b
.sp
.(b
.nf
.ip "$bold pick~ : ~<n,x>~ ==$"
.sp 4p
\&$x = fs ~ andsign ~0~<~n~<=~k ~->~ x sub n ;$
.sp 4p
\&$x = fs ~ andsign ~-k <= n  < 0 ~ ->  ~ x sub {k + n + 1}; ~ ?$
.fi
.)b
.sp 2
.pp
The user should note that the function 
symbols \fB1\fP,\fB2\fP,\fB3\fP$,...$ are
to be distinguished from the atoms $1,2,3,...$.
.(b M F
.sp
.ip "$bold last ~ : ~x~ ==$"
.sp 4p
\&$x = <> ~ ->  ~ <> ~ ;$
.sp 4p
\&$x = fs ~ andsign ~ k >= 1 ~ -> ~ x sub k ;~?$
.)b
.(b M F
.sp
.ip "$bold first ~ : ~x~ ==$"
.sp 4p
\&$x = <> ~ ->  ~ <> ~ ;$
.sp 4p
\&$x = fs ~ andsign ~ k >= 1 ~ -> ~ x sub 1 ;~?$
.)b
.sp
.(b M F
.b "Tail Functions"
.sp
.ip "$bold tl ~:~x ~==$"
.sp 4p
\&$x = <x sub 1 > ~ ->  ~ <> ~ ;$
.sp 4p
\&$x = fs ~ andsign  ~ k >= ~ 2 ~ -> ~<x sub 2 ~,..., ~x sub k > ~ ;~  ?$
.)b
.sp 6p
.(b M F
.ip "$bold tlr  ~ : ~  x~==$"
.sp 4p
\&$x = <x sub 1 >  ~ ->  ~ <> ~ ;$
.sp 4p
\&$x = fs  ~ andsign ~ k >= ~ 2 ~ -> ~ <x sub 1 ~ ,..., ~x sub {k - 1} > ~ ; ~ ?$
.)b
.sp
.pp
Note: There is also a function
\fBfront\fP that is equivalent to \fBtlr\fP.
.sp
.(b M F
.b "Distribute from left and right"
.sp
.ip "$bold distl ~:~x~==$"
.sp 4p
\&$x = <y,<>>~->~<>;$
.sp 4p
\&$x = <y, qz >~->~<<y,z sub 1 >,...,<y,z sub k >>;~?$
.)b
.sp 6p
.(b M F
.ip "$bold distr ~:~x~==$"
.sp 4p
\&$x = <<>,y>~->~<>;$
.sp 4p
\&$x = < qy , z >~->~<<y sub 1 , z >,...,<y sub k , z >>;~?$
.)b
.sp 6p
.(b M F
.b "Identity"
.sp 6p
$bold id ~:~x~==~x$
.)b
.sp 6p
$bold out ~:~x~==~x$
.pp
\fBOut\fP is similar to \fPid\fP.
Like \fBid\fP it returns its argument as the result,
unlike \fPid\fP
it prints its
result on \fIstdout\fP \(mi
It is the only function with a side effect.
\fPOut\fP is intended to be used for debugging only.
.sp
.(b M F
.b "Append left and right"
.sp
.nf
.ip "$bold apndl ~:~x~==$"
.sp 4p
\&$x = <y,<>>~->~<y>;$
.sp 4p
\&$x = <y, qz >~->~<y, z sub 1 ,~ z sub 2 ,...,~ z sub k  >;~?$
.)b
.sp 6p
.(b M F
.ip "$bold apndr ~:~x~==$"
.sp 4p
\&$x = <<>,z>~->~<z>;$
.sp 4p
\&$x = < qy , z >~->~< y sub 1 ,~ y sub 2 ,...,~ y sub k ,~z >;~?$
.fi
.)b
.sp
.(b M F
.b "Transpose"
.sp
.nf
.ip "$bold trans~:~x~==$"
.sp 4p
\&$x = <<>,...,<>>~->~<>;$
.sp 4p
\&$x = fs ~->~<y sub 1 ,..., y sub m >;~?$
.sp 8p
\&where $x sub i ~=~<x sub i1 ,..., x sub im >~andsign
~ y sub j ~=~<x sub 1j ,..., x sub kj >,$
.sp 4p
\&$1<=i<=k ~,~ 1<=j<=m.$
.)b
.sp
.fi
.(b M F
.ip "$bold reverse~:~x~==~$"
.sp 4p
\&$x =<>~ ->;$
.sp 4p
\&$x = fs ~->~ <x sub k ,..., x sub 1 >;~?$
.)b
.sp
.(b M F
.b "Rotate Left and Right"
.sp
.nf
.ip "$bold rotl~:~x~==$"
.sp 4p
\&$x = <>~ -> ~ <>;~x = <x sub 1 >~->~<x sub 1 >;$
.sp 4p
\&$x = fs ~ andsign ~k >= 2~ -> ~ <x sub 2 ,..., x sub k , x sub 1 >;~?$
.)b
.sp
.(b M F
.ip "$bold rotr~:x~==$"
.sp 4p
\&$x = <>~ -> ~ <>;~x = <x sub 1 >~->~<x sub 1 >;$
.sp 4p
\&$x = fs ~ andsign ~k >= 2~ -> ~
<x sub k  ,~ x sub 1 ,..., x sub {k - 2},~ x sub {k - 1} >;~?$
.)b
.fi
.sp 2
.(b M F
.nf
.ip "$bold concat~:~x~==$"
.sp 4p
\&$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 >; ?$
.)b
.sp
.(b M F
.pp
Concatenate removes all occurrences of the null sequence:
.sp
.EQ I (2.3)
bold concat ~ :~ <<1,3>,<>,<2,4>,<>,<5>>  ~==~ <1,3,2,4,5>
.EN
.)b
.sp
.(b M F
.ip "$bold pair~:~x~==$"
.sp 4p
\&$x = fs ~ andsign ~ k >0 ~ andsign ~ k~is~even~->~ <<x sub 1 , x sub 2 >
,..., <x sub k-1 , x sub k >>;$
.sp 4p
\&$x = fs ~ andsign ~ k >0 ~ andsign ~ k~is~odd~->~ <<x sub 1 , x sub 2 >
,..., <x sub k >>;~?$
.)b
.sp
.(b M F
.ip "$bold split~:~x~==$"
.sp 4p
\&$x = <x sub 1 > ~->~<<x sub 1 > , <>>;$
.sp 4p
\&$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 >>; ?$
.)b
.sp
.(b M F
.ip "\fBiota\fP$~:x~==$"
.sp 4p
\&$x = 0 ~->~ <>;$
.sp 4p
\&$x memberOf bold {N sup +} ~ ->~<1,2,...,x>;~?$
.)b
.sp
.NS 3 "Predicate (Test) Functions"
.sp
$bold atom~:~x~==~x~ memberOf atoms~-> ~ T ; ~ x$\(!=$? -> ~ F ;~ ?$
.sp
$bold eq ~:~x~==~x~=<y,z> ~ andsign ~ y=z ~ -> ~ T ;~x= <y,z> ~ andsign ~y$ \(!= $z ~->~ F ;~?$
.sp
.pp
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. 
.sp
$bold null ~ : x~==~x = <> ~ -> ~ T ;~x$\(!=$?~ -> ~ F ;~?$
.sp 6p
$bold length ~ :~ x~==~x~= ~ fs ~ -> ~ k; ~ x = <> ~ -> ~0; ~ ?$
.sp
.NS 3 "Arithmetic/Logical"
.sp
$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 ;~?$
.sp
.b "And, or, not, xor"
.sp
$nd~:~<x,y>~==~x = T ~->~ y;~x= F ~->~ F ;~?$
.sp 8p
$rr~:~<x,y>~==~x = F ~->~ y;~x= T ~->~ T ;~?$
.sp 8p
.(b M F
.nf
.ip "$bold xor~:~<x,y>~==$"
.sp 4p
\&$x = T ~ andsign ~ y = T ~->~ F ;~ x = F ~ andsign ~ y = F ~->~ F ;$
.sp 4p
\&$x = T ~ andsign ~ y = F ~->~ T ;~ x = F ~ andsign ~ y = T ~->~ T ;~?$
.fi
.)b
.sp 6p
$bold not~:~x~==~x= T ~->~F;~x= F~->~T ;~?$
.NS 3 "Library Routines"
.sp
$bold "sin"~:~x~==~x roman {~is~a~number} ~->~sin(x);~?$
.sp 8p
$bold "asin"~:~x~==~x roman {~is~a~number}
~andsign~|x|~<=~1 ~->~sin sup {-1} (x);~?$
.sp 8p
$bold "cos"~:~x~==~x roman {~is~a~number} ~->~cos(x);~?$
.sp 8p
$bold "acos"~:~x~==~x roman {~is~a~number}
~andsign~|x|~<=~1 ~->~cos sup {-1} (x);~?$
.sp 8p
$bold "exp"~:~x~==~x roman {~is~a~number} ~->~ e sup x;~?$
.sp 8p
$bold "log"~:~x~==~x roman {~is~a~positive~number} ~->~ ln(x);~?$
.sp 8p
$bold "mod"~:~<x,y>~==~ x nd y roman {~are~numbers} ~->~ x ~-~ y times
left floor x over y right floor ~;~?$
.sx 2
.sp
.NS 2 "Functional Forms"
.pp
Functional forms define new \fIfunctions\fP
by operating on
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.
.pp
One functional form is \fIcomposition\fP.  For two functions $phi$ and
$psi$ the form $phi ~ @ ~psi$ denotes their composition $phi ~$\*(cm$~ psi$:
.sp 4p
.EQ I (2.4)
( phi ~@~ psi )~:~x~==~phi :( psi :x),~~ forAll ~~x memberOf OMEGA
.EN
.sp
The \fIconstant\fP function takes an object parameter:
.sp
.EQ I (2.5)
%x:y~==~y=?~->~?;~x,~~~ forAll ~~x,y~ memberOf OMEGA
.EN
.sp
The function $%?$ always returns ?.
.pp
In the following description of the functional forms, we assume that
$xi , ~xi sub i ,~sigma ,  ~sigma sub i ,~tau ,$ and $tau sub i$
are functions and that
$x,~x sub i ,~ y$ are objects.
.sp 2
.b "Composition"
.sp
$( sigma ~@~ tau ):x~==~sigma : ( tau : x)$
.sp 2
.b "Construction"
.sp
$[ sigma sub 1 ,..., sigma sub n ]:x~==~< sigma sub 1 : x,..., sigma sub n : x>$
.sp
Note that construction is also bottom-preserving, \*(EG
.sp 6p
.EQ I (2.6)
[ bold +, bold /]^:^<3,0>~=~<3,?>~=~?
.EN
.sp 2
.(b M F
.b "Condition"
.sp
.ip "$( xi~"->" ~sigma ;~tau ):x~==~$"
.sp 4p
\&$( xi : x) = T~->~sigma : x;$
.sp 4p
\&$~ ( xi : x)= F~ ->~tau :x;~?$
.)b
.sp 8p
.pp
The reader should be aware of the distinction between
\fIfunctional expressions\fP, in the variant of McCarthy's conditional
expression,
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
.sp 6p
.EQ I (2.7)
roman {"(isNegative ->  - @ [%0,id] ; id")}
.EN
.sp 
.(b M F
.b "Constant"
.sp
$%x:y~==~y=?~->~?;~x,~~~~~~ forAll ~x memberOf OMEGA$
.sp
.)b
This function returns its object parameter as its result.
.sp
.(b M F
.b "Right Insert"
.sp 6p
.nf
.ip "$! bold sigma~:x~==$"
.sp 4p
\&$x = <>~->~e sub f : x;$
.sp 4p
\&$x=<x sub 1 >~->~x sub 1 ;$
.sp 4p
\&$x= fs ~ andsign ~k>2~->~ sigma :<x sub 1 ,~! sigma :<x sub 2 ,...,~x sub k >>;~?$
.sp 10p
\&\*(EG  $!+:<4,5,6> =15$.
.)b
.pp
If  $sigma$ has a right identity element $e sub f$,
then $! sigma :<>~=~ e sub f$, \*(EG
.sp 6p
.EQ I (2.8)
!+^:^<> =0 ~roman "and" ~!*^:^<> =1
.EN
.sp
Currently,
identity functions are defined for $+ \  (0),\  -  \  (0), \ *  \  (1),
\ /  \  (1)$,
also for \fBand\fP (T), \fBor\fP (F), \fBxor\fP (F).  All other unit functions
default to bottom (?).
.sp
.(b M F
.b "Tree Insert"
.sp 6p
.ip " \fB|\fP $sigma~:~x~==$"
.sp 4p
\&$x = <>~->~e sub f : x;$
.sp 4p
\&$x=<x sub 1 >~->~x sub 1 ;$
.sp 4p
.nf
\&$x= fs ~ andsign ~k>1~->$
.sp 4p
\&$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}
,..., x sub k >>; ?$
.sp 10p
\&\*(EG
.EQ I (2.9)
"\fB|\fP" +:<4,5,6,7> ~==~  +:<+:<4,5> , +:<6,7>> ~==~ 15
.EN
.sp
.fi
.)b
.sp
.pp
Tree insert uses  the same identity functions as right
insert.
.sp
.b "Apply to All"
.sp
.ip "\fB&\fP$^sigma :~x~==$"
.sp 4p
\&$x=<>~-><>;$
.sp 4p
\&$x= fs~->~< sigma : x sub 1 ,...,~sigma : x sub k >;~?$
.sp
.(b M F
.b "While"
.sp
.ip "(\fBwhile\fP$ ~xi~sigma ):x~==$"
\&$xi : x= T~->~($\fBwhile\fP$ ~xi~sigma ):( sigma : x);$
.sp 4p
\&$xi : x= F~->~x;~?$
.)b
.sp
.NS 2 "User Defined Functions"
.pp
An FP definition is entered as follows:
.sp 6p
.EQ I (2.10)
"{fn-name fn-form},"
.EN
.sp
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.
For example the function
.sp
.EQ I (2.11)
"{factorial !* @ iota}"
.EN
.sp
.pp
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$.
.pp
References to undefined functions bottom out:
.sp
.EQ I (2.12)
f:x~==~? forAll x memberOf OMEGA ,~f^ notmemberof F
.EN
.sx 1
.bp