Copyright (c) 1980 The Regents of the University of California.
All rights reserved.

%sccs.include.redist.roff%

@(#)manCh2.rno 6.2 (Berkeley) 04/17/91

.NS 1 "System Description" .NS 2 "Objects" .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 "?"$, bottom. Bottom 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: .(b C

$?$ $1.47$ $3888888888888$

$ab$ "$CD$" $<1,<2,3>>$

$<>$ $T$ $<a,<>>$

.)b 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]. .NS 2 "Application" .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 operator and that $x$ is the operand. The following are examples of applications:

$bold + : <7,8>$ $==$ $15$ $bold tl :<1,2,3>$ $==$ $<2,3>$

1 $: <a,b,c,d>$ $==$ $a$ 2 $: <a,b,c,d>$ $==$ $b$

.nr ii 0.35i .NS 2 "Functions" .pp All functions (F) map objects into objects, moreover, they are strict: sigma^:^? equiv ?,~~ forAll ^sigma^ memberOf F .EN 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} .EN 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$. .NS 3 "Structural" .b "Selector Functions" .(b M F 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}; ~ ?$

.)b .(b

.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}; ~ ?$

.)b .pp The user should note that the function symbols 1,2,3$,...$ are to be distinguished from the atoms $1,2,3,...$. .(b M F .ip "$bold last ~ : ~x~ ==$" $x = <> ~ -> ~ <> ~ ;$ $x = fs ~ andsign ~ k >= 1 ~ -> ~ x sub k ;~?$ .)b .(b M F .ip "$bold first ~ : ~x~ ==$" $x = <> ~ -> ~ <> ~ ;$ $x = fs ~ andsign ~ k >= 1 ~ -> ~ x sub 1 ;~?$ .)b .(b M F .b "Tail Functions" .ip "$bold tl ~:~x ~==$" $x = <x sub 1 > ~ -> ~ <> ~ ;$ $x = fs ~ andsign ~ k >= ~ 2 ~ -> ~<x sub 2 ~,..., ~x sub k > ~ ;~ ?$ .)b .(b M F .ip "$bold tlr ~ : ~ x~==$" $x = <x sub 1 > ~ -> ~ <> ~ ;$ $x = fs ~ andsign ~ k >= ~ 2 ~ -> ~ <x sub 1 ~ ,..., ~x sub {k - 1} > ~ ; ~ ?$ .)b .pp Note: There is also a function front that is equivalent to tlr. .(b M F .b "Distribute from left and right" .ip "$bold distl ~:~x~==$" $x = <y,<>>~->~<>;$ $x = <y, qz >~->~<<y,z sub 1 >,...,<y,z sub k >>;~?$ .)b .(b M F .ip "$bold distr ~:~x~==$" $x = <<>,y>~->~<>;$ $x = < qy , z >~->~<<y sub 1 , z >,...,<y sub k , z >>;~?$ .)b .(b M F .b "Identity" $bold id ~:~x~==~x$ .)b $bold out ~:~x~==~x$ .pp Out is similar to id. Like id it returns its argument as the result, unlike id it prints its result on stdout - It is the only function with a side effect. Out is intended to be used for debugging only. .(b M F .b "Append left and right"

.ip "$bold apndl ~:~x~==$"
$x = <y,<>>~->~<y>;$
$x = <y, qz >~->~<y, z sub 1 ,~ z sub 2 ,...,~ z sub k >;~?$
.)b
.(b M F
.ip "$bold apndr ~:~x~==$"
$x = <<>,z>~->~<z>;$
$x = < qy , z >~->~< y sub 1 ,~ y sub 2 ,...,~ y sub k ,~z >;~?$

.)b .(b M F .b "Transpose"

.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 >,$
$1<=i<=k ~,~ 1<=j<=m.$
.)b

.(b M F .ip "$bold reverse~:~x~==~$" $x =<>~ ->;$ $x = fs ~->~ <x sub k ,..., x sub 1 >;~?$ .)b .(b M F .b "Rotate Left and Right"

.ip "$bold rotl~:~x~==$"
$x = <>~ -> ~ <>;~x = <x sub 1 >~->~<x sub 1 >;$
$x = fs ~ andsign ~k >= 2~ -> ~ <x sub 2 ,..., x sub k , x sub 1 >;~?$
.)b
.(b M F
.ip "$bold rotr~:x~==$"
$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} >;~?$
.)b

.(b M F

.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 >; ?$
.)b
.(b M F
.pp
Concatenate removes all occurrences of the null sequence:
bold concat ~ :~ <<1,3>,<>,<2,4>,<>,<5>> ~==~ <1,3,2,4,5>
.EN
.)b
.(b M F
.ip "$bold pair~:~x~==$"
$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 >
,..., <x sub k >>;~?$
.)b
.(b M F
.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 >>; ?$
.)b
.(b M F
.ip "iota$~:x~==$"
$x = 0 ~->~ <>;$
$x memberOf bold {N sup +} ~ ->~<1,2,...,x>;~?$
.)b
.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 ;~?$
.pp
Also less than ($bold <$), greater than ($bold >$),
greater than or equal (>=),
less than or equal (<=), not equal (~=);
'$bold =$' is a synonym for eq. 
$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; ~ ?$
/$~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ andsign 
~z$\(!= $0 ~ ->~y$\(di$z ;~?$
.b "And, or, not, xor"
$nd~:~<x,y>~==~x = T ~->~ y;~x= F ~->~ F ;~?$
$rr~:~<x,y>~==~x = F ~->~ y;~x= T ~->~ T ;~?$
.(b M F
.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 ;~?$

.)b
$bold not~:~x~==~x= T ~->~F;~x= F~->~T ;~?$
.NS 3 "Library Routines"
$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 ~;~?$
.sx 2
.NS 2 "Functional Forms"
.pp
Functional forms define new functions
by operating on
function and object parameters of the form.
The resultant expressions
can be compared and contrasted to the value-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 composition. 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
.EN
The constant function takes an object parameter:
%x:y~==~y=?~->~?;~x,~~~ forAll ~~x,y~ memberOf OMEGA
.EN
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.
.b "Composition"
$( sigma ~@~ tau ):x~==~sigma : ( tau : x)$
.b "Construction"
$[ 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,?>~=~?
.EN
.(b M F
.b "Condition"
.ip "$( xi~"->" ~sigma ;~tau ):x~==~$"
$( xi : x) = T~->~sigma : x;$
$~ ( xi : x)= F~ ->~tau :x;~?$
.)b
.pp
The reader should be aware of the distinction between
functional expressions, in the variant of McCarthy's conditional
expression,
and the functional form introduced here.
In the former case the result is a value, while in the latter case
the result is a function. Unlike Backus' FP, the conditional form
must be enclosed in parenthesis, \*(EG
roman {"(isNegative -> - @ [%0,id] ; id")}
.EN
.(b M F
.b "Constant"
$%x:y~==~y=?~->~?;~x,~~~~~~ forAll ~x memberOf OMEGA$
.)b
This function returns its object parameter as its result.
.(b M F
.b "Right Insert"
.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$.
.)b
.pp
If $sigma$ has a right identity element $e sub f$,
then $! sigma :<>~=~ e sub f$, \*(EG
!+^:^<> =0 ~roman "and" ~!*^:^<> =1
.EN
Currently,
identity functions are defined for $+   (0),  -   (0),  *   (1),
 /   (1)$,
also for and (T), or (F), xor (F). All other unit functions
default to bottom (?).
.(b M F
.b "Tree Insert"
.ip " | $sigma~:~x~==$"
$x = <>~->~e sub f : x;$
$x=<x sub 1 >~->~x sub 1 ;$
$x= fs ~ andsign ~k>1~->$
$bold sigma ~:~< $|$~ sigma~:~
<x sub 1 ,..., x sub {left ceiling k/2 right ceiling} >~,~
"|" ~ sigma ~:~<x sub {left ceiling k/2 right ceiling + 1}
,..., x sub k >>; ?$
\*(EG
"|" +:<4,5,6,7> ~==~ +:<+:<4,5> , +:<6,7>> ~==~ 15
.EN

.)b
.pp
Tree insert uses the same identity functions as right
insert.
.b "Apply to All"
.ip "&$^sigma :~x~==$"
$x=<>~-><>;$
$x= fs~->~< sigma : x sub 1 ,...,~sigma : x sub k >;~?$
.(b M F
.b "While"
.ip "(while$ ~xi~sigma ):x~==$"
$xi : x= T~->~($while$ ~xi~sigma ):( sigma : x);$
$xi : x= F~->~x;~?$
.)b
.NS 2 "User Defined Functions"
.pp
An FP definition is entered as follows:
"{fn-name fn-form},"
.EN
where fn-name is an ascii string consisting of letters, numbers and the
underline symbol, and fn-form is any valid functional form, including
a single primitive or defined function.
For example the function
"{factorial !* @ iota}"
.EN
.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:
f:x~==~? forAll x memberOf OMEGA ,~f^ notmemberof F
.EN
.sx 1
.bp