rs@uunet.UU.NET (Rich Salz) (07/07/87)
Mod.sources: Volume 10, Number 35
Submitted by: robison@b.cs.uiuc.edu (Arch Robison)
Archive-name: ifp/Part02
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh.
# The following files will be created:
# manual
export PATH; PATH=/bin:$PATH
if test -f 'manual'
then
echo shar: over-writing existing file "'manual'"
fi
cat << \SHAR_EOF > 'manual'
Professional Workstation
Research Group Technical Report #7
Illinois FP User's Manual
Arch D. Robison
Department of Computer Science
University of Illinois at Urbana-Champaign
Urbana, Illinois 61801
February 9, 1987
_T_a_b_l_e _o_f _C_o_n_t_e_n_t_s
1. Overview .......................................... 1
2. Prerequisites ..................................... 2
2.1. Organization .................................... 2
2.2. Environment (UNIX) .............................. 3
2.3. Environment (MSDOS) ............................. 3
3. Using IFP ......................................... 4
3.1. Starting IFP .................................... 4
3.2. Creating and Editing Definitions ................ 4
3.3. Applying Functions .............................. 5
3.4. Executing UNIX Commands ......................... 5
3.5. Executing MSDOS Commands ........................ 6
4. Language .......................................... 6
4.1. Objects ......................................... 6
4.2. Functions ....................................... 7
4.2.1. Primitive Functions ........................... 9
4.2.1.1. Structural Functions (/sys) ................. 11
4.2.1.2. Arithmetic (/math/arith) .................... 12
4.2.1.3. Logic (/math/logic) ......................... 14
4.2.1.4. String Functions (/sys) ..................... 16
4.2.1.5. Miscellaneous Functions (/sys) .............. 16
4.2.2. User Defined Functions ........................ 19
4.2.3. Functional Variables .......................... 20
4.3. Functional Forms ................................ 21
4.3.1. Constant ...................................... 21
4.3.2. Selection ..................................... 22
4.3.3. Composition ................................... 22
4.3.4. Construction .................................. 23
4.3.5. Apply to Each ................................. 23
4.3.6. If-Then-Else .................................. 24
4.3.7. Filter ........................................ 24
4.3.8. Right Insert .................................. 25
4.3.9. While ......................................... 26
4.3.10. Fetch[8] ..................................... 26
4.4. Comments ........................................ 27
4.5. Syntax Summary .................................. 27
5. IFP Graphics (optional)[9] ........................ 27
5.1. Coordinate System ............................... 28
5.2. Display List Structure .......................... 28
5.2.1. Polyline ...................................... 28
5.2.2. Color ......................................... 29
5.2.3. Transform ..................................... 29
5.2.4. Text .......................................... 29
6. Debugging ......................................... 30
7. Differences between IFP and Backus' FP ............ 31
7.1. Domain .......................................... 31
7.2. Functions ....................................... 31
7.3. Functional Forms ................................ 31
7.4. Syntax .......................................... 32
8. Functional Programming Techniques ................. 33
8.1. Functional Programming Identities ............... 33
8.2. Common Subfunctions ............................. 34
8.3. State Machines .................................. 34
8.4. Tail Recursion .................................. 35
9. Installation Notes ................................ 35
9.1. Machine Dependence .............................. 35
9.2. Compiling Options ............................... 36
i
_I_l_l_i_n_o_i_s _F_P _0._5 _U_s_e_r_s _M_a_n_u_a_l[_1]
_1. _O_v_e_r_v_i_e_w
Functional Programming (FP) [Bac78a] is a radically new
form of programming. FP programs have neither the control
flow nor variables of Von-Neumann languages. Instead pro-
grams are directly constructed from smaller programs. As a
result, FP offers a new style of programming with numerous
advantages, including:
Modular Programming
Program Verification
Parallel Processing
Optimization
IFP (Illinois Functional Programming) [Rob87a,Rob87b]
is an interactive functional programming implementation for
UNIX and MSDOS systems. The user may interactively create
and execute functional programs. In addition to Backus' FP,
IFP has the following features:
Hierarchical and Modular Function Organization
Block-Structured Syntax
Error Explanations
Graphics Display List Processor[2]
The interpreter is an order of magnitude more compact and
____________________
[1]Any resemblance to the real product is purely coin-
cidental.
[2]Once upon a time it worked. The code has since then
not been maintained. So it is not implemented in most ver-
sions.
February 9, 1987 IFP 0.5 Users Manual 2
faster than previous FP implementations.
_2. _P_r_e_r_e_q_u_i_s_i_t_e_s
The rest of the manual assumes the reader has read
Backus' original paper on FP. [Bac78a] Other references on
FP [Bad83a,Dar82a] may be of help. Additionally, parts of
the manual assume the reader understands UNIX or MSDOS[3]
file structure and paths.
_2._1. _O_r_g_a_n_i_z_a_t_i_o_n
IFP organizes functions in a tree structure analogous
to UNIX/MSDOS files. In fact each function is a file. For
UNIX systems, each user specifies the root (``IFP root'') of
their function tree. Within IFP, paths specify a path rela-
tive to the IFP root. The IFP root is set by a UNIX
environment variable. For MSDOS systems, the IFP root is
identical to the current drive root. (see ``Environment''
below).
Each node on the tree is either a function definition
(corresponding to a file), or a module (corresponding to a
directory). A function may reference another function via a
path.
To avoid having to write out the entire path for a
function every time, IFP has a function identifier importa-
tion feature. Functions from other modules may be imported
into a module. Once imported, a function may be referenced
February 9, 1987 IFP 0.5 Users Manual 3
as though it were defined in the module.
_2._2. _E_n_v_i_r_o_n_m_e_n_t (_U_N_I_X)
Before invoking IFP, two environment variables should
be set. The ``EDITOR'' variable should be set to the name of
your favorite editor. The ``IFProot'' variable should be
set to the absolute path of your ``IFP root''.[3] The
``IFPprompt'' is optional. If set, it changes the IFP
prompt. The default prompt is ``ifp> ''. Normally these
variables will be set by your .login file. Below is an
example of the commands which would appear in your .login
file.
setenv EDITOR = ``/usr/ucb/vi''
setenv IFProot = ``/mnt/bonzo/fproot''
setenv IFPprompt = ``ifp> ''
_2._3. _E_n_v_i_r_o_n_m_e_n_t (_M_S_D_O_S)
Before invoking IFP, two environment variables should
be set. The ``EDITOR'' and ``IFPDIR'' variables should be
set to the names of your favorite editor and directory lis-
ters respectively. Normally these should be set by your
autoexec.bat file, e.g.:
set EDITOR=C:ED.EXE
set IFPDIR=C:SD2.COM
Unlike the UNIX version, there is no IFProot variable. The
____________________
Use the actual path, not a symbolic link. When IFP
starts up, it assumes that the current directory path is a
prefix of the IFP root path.
February 9, 1987 IFP 0.5 Users Manual 4
root of the IFP file system is the root of the current
drive.
_3. _U_s_i_n_g _I_F_P
_3._1. _S_t_a_r_t_i_n_g _I_F_P
To start an IFP session, change your current working
directory to a directory under your IFP root. Then type
"ifp". Your current working directory becomes your IFP
current working module. When IFP is ready, it will respond
with the prompt ``ifp> ''. To end the IFP session, type
control-D or enter the command ``exit''.
_3._2. _C_r_e_a_t_i_n_g _a_n_d _E_d_i_t_i_n_g _D_e_f_i_n_i_t_i_o_n_s
To edit an IFP definition, type the command:
vi[4] foo
where foo is the name of the function to be edited. The
function may be one local to the current working module, or
one that is imported into the current working module. If
the function name is neither defined locally nor imported,
then it is assumed to be a new local function. To delete an
IFP definition, type the command:
rm[5] foo
____________________
[4]If your editor is not ``vi'' (as specified by the last
element of your EDITOR path), replace ``vi'' with your
editor's name. For MS-DOS, the command is always ``ed'', no
matter what the editor is called.
February 9, 1987 IFP 0.5 Users Manual 5
_3._3. _A_p_p_l_y_i_n_g _F_u_n_c_t_i_o_n_s
To apply an FP function, type the command[6]:
show object : function
The interpreter evaluates the result of applying the
function to the object. The result is then pretty-printed
at the terminal. Below are some example inputs and outputs.
show <a b c> : reverse
<c b a>
show <1 2 3> : sum
6
show <1 2 3> : EACH [id,id]|* END | sum (* sum of squares *)
14
show <1 2 3 4 5> : EACH iota END
<
<1>
<1,2>
<1,2,3>
<1,2,3,4>
<1,2,3,4,5>
>
exit
_3._4. _E_x_e_c_u_t_i_n_g _U_N_I_X _C_o_m_m_a_n_d_s
If a command is not recognized by the IFP interpreter,
then it is passed on to the UNIX shell ``sh''. Commands
such as ``ls'' and ``more'' work as expected. Commands
which change environment do not work properly, as they
____________________
[5]For MS-DOS, the command is ``del''.
[6]Some earlier versions (before 0.4, e.g. the BYTE BIX
release) require a semicolon after the _f_u_n_c_t_i_o_n.
February 9, 1987 IFP 0.5 Users Manual 6
change their environment (within ``sh'') but not your own.
For example, the ``cd'' command does not work.
_3._5. _E_x_e_c_u_t_i_n_g _M_S_D_O_S _C_o_m_m_a_n_d_s
The only two MSDOS command that can be run from within
the interpreter are ``dir'' and ``del''. Some systems seem
to require ``dir/''. I don't know why.
_4. _L_a_n_g_u_a_g_e
IFP semantics are almost identical to Backus' FP,
though the syntax is quite different. The IFP language con-
sists of objects, functions, and functional forms. The sin-
gle operation is _a_p_p_l_y which maps a function and object into
a new object.
_4._1. _O_b_j_e_c_t_s
Objects in FP are either atoms, sequences, or _b_o_t_t_o_m.
The latter is a special object which denotes an undefined
value. Atoms are numbers, strings, or boolean values.
Strings must be quoted when they look like another kind of
atom or contain non-alphanumeric characters. Below is a
table of some typical atoms:
banana string
"The cat in the hat" string (double quotes)
'hello world' string (single quotes)
7 number
3.1415 number
1e6 number (million)
February 9, 1987 IFP 0.5 Users Manual 7
"1.414" string
t boolean true
f boolean false
"t" string
Sequences are lists of zero or more objects surrounded
by angle brackets. Sequences are written as:
<x ,x ,...x >
1 2 n
Below is table of some typical sequences:
<a,b,c>
<1 2 3 4 5 6>
<>
<<1 2 3> <apple banana> t>
Either commas or spaces may be used to separate the elements
of a sequence. The elements of the sequence may be any kind
of object except ``?'', and do not have to be of the same
type.
IFP sequences have the _b_o_t_t_o_m _p_r_e_s_e_r_v_i_n_g [_B_a_c_7_8_a] pro-
perty. Any sequence containing ``?'' is itself equal to
``?''.
_4._2. _F_u_n_c_t_i_o_n_s
Functions in FP always have a single argument and a
single result. FP functions are analogous to UNIX programs
which transform ``standard input'' into ``standard output''
without side effects.
February 9, 1987 IFP 0.5 Users Manual 8
The IFP interpreter distinguishs two kinds of func-
tions: primitive functions and user-defined functions.
Primitive functions are built into the FP interpreter;
user-defined functions are created by the user. The only
distinction between the two kinds of functions is that
user-defined functions have definitions in terms of other
IFP functions. All functions may be used in the same
manner, neither primitive nor user-defined functions are
privileged in any way.
IFP functions are arranged in a tree structure analo-
gous to the way UNIX files are arranged. Each node of the
tree is either a module (directory) or function (file). A
function is referenced by its _p_a_t_h_n_a_m_e, which is a sequence
of node names separated by slashes. Pathnames follow the
UNIX conventions. Absolute pathnames begin with a slash,
which indicates that the path starts at the IFP root direc-
tory (as specified by the IFProot variable in your environ-
ment). Relative pathnames do not begin with a slash, which
indicates that the path starts at the current directory.
Within function definitions, the current directory is the
parent node of the function. Pathnames may contain ``..'',
which indicates moving up to the parent node.
For example, consider the node tree in Figure 1. The
root node is ``r''. Below are some ways the function ``b''
can reference the other nodes. Note that the name of the
root node is never explicitly used.
February 9, 1987 IFP 0.5 Users Manual 9
+-----+
| r |
+-----+
/ \
/ \
/ \
/ \
/ \
/ \
+-----+ +-----+
| tmp | | sys |
+-----+ +-----+
/ | \ / \
/ | \ / \
/ | \ / \
/ | \ / \
+-----+ +-----+ +-----+ +-----+ +-----+
| foo | | a | | b | | id | | sum |
+-----+ +-----+ +-----+ +-----+ +-----+
/ \
/ \
/ \
+-----+ +-----+
| p | | q |
+-----+ +-----+
Figure 1
_________________________
|_p_a_t_h_n_a_m_e________t_y_p_e______|
| /sys/sum absolute|
| /tmp/foo/p absolute|
| foo/p relative|
| ../tmp/foo/p relative|
| ../sys/sum relative|
|_________________________|
_4._2._1. _P_r_i_m_i_t_i_v_e _F_u_n_c_t_i_o_n_s
Primitive functions are built into the IFP interpreter.
They have pathnames like any other function, except that
there is no source code file for the function. The function
descriptions are grouped into sections below. The pathname
for the function's module is in parentheses at the top of
February 9, 1987 IFP 0.5 Users Manual 10
each section.[7]
The following sets (types) are used in the definitions
of functions:
A atoms
B boolean values
O objects
R real numbers
Z integers
S strings
T* sequences with element type T
T+ non-empty sequences with element type T
Tn sequences of length n with element type T
T[n,m] sequences of length m with element type Tn
[T ,T ] pair of types T and T
1 2 1 2
A function returns ``?'' if the argument is not in its
domain. The notation x denotes the nth element of a
n
sequence X.
For example, the domain of the addition function is
[X,Y] in [R,R]. That is addition takes a pair of real
numbers as its argument. We could also write this as [X,Y]
in R2, since a pair is a sequence of length two.
The types may be pictured neatly with the Venn diagram
in Figure 2:
____________________
[7] NOTE: The author does not worship backward compati-
bility. Future versions of IFP may put primitive functions
in different subdirectories.
February 9, 1987 IFP 0.5 Users Manual 11
+----------------------------+
| O |
| +--------------------+ |
| | A | |
| | +-----------+ | |
| | | B | | |
| | +-----------+ | |
| | | R | | |
| | | +---+ | | |
| | | | Z | | | |
| | | +---+ | | |
| | | | | |
| | +-----------+ | |
| | | O* | | |
| | +-----------+ | |
| | | |
| +--------------------+ |
| |
| +-+ |
| |?| |
| +-+ |
| |
+----------------------------+
Figure 2
_4._2._1._1. _S_t_r_u_c_t_u_r_a_l _F_u_n_c_t_i_o_n_s (/_s_y_s)
Structural functions are assemble, reorganize, and
select data. The primitive structural functions are listed
below:
February 9, 1987 IFP 0.5 Users Manual 12
__________________________________________________________________________
_|N_a_m_e_______D_o_m_a_i_n_________________D_e_f_i_n_i_t_i_o_n________________________________|
| |
|apndl [X,Y] in [O,On] <X,y ,y ,...y > |
| 1 2 n |
|apndr [X,Y] in [Om,O] <x x ,...x ,Y> |
| 1, 2 m |
| nm |
|cat X in O catenate subsequences, e.g. |
| <<a b> <x> <3 5>> -> <a b x 3 5> |
| n |
|distl [X,Y] in [O,O ] <<X,y1><X,y2>...<X,yn>> |
| m |
|distr [X,Y] in [O ,O] <<x1,Y><x2,Y>...<xm,Y>> |
| n |
|dropl [X,K] in [O ,0<_Z<_n] <xK+1,xK+2,...xn> |
| n |
|dropr [X,K] in [O ,0<_Z<_n] <x1,x2,...xn-k> |
| |
|iota n in Z>_0 <1,2,...n> |
| n |
|length X in O n |
| n |
|pick [X,K] in [O ,0<Z<_n] xK |
| |
|repeat [X,K] in [O,0<_Z] sequence <X,X...X> of length K |
| n |
|reverse X in O <xn,xn-1,...x1> |
| n |
|takel [X,K] in [O ,0<_Z<_n] <x1,x2,...xK> |
| n |
|taker [X,K] in [O ,0<_Z<_n] <xn-K+1,xn-k+2,...xn> |
| m>0 |
|tl X in O <x2,x3,...xm> |
| m>0 |
|tlr X in O <x1,x2,...xm-1> |
| [n,m] |
|trans X in O transpose matrix, e.g. |
_||________________________________<_<_a__1_>__<_b__2_>__<_c__3_>_>__-_>__<_<_a__b__c_>__<_1__2__3_>_>
_4._2._1._2. _A_r_i_t_h_m_e_t_i_c (/_m_a_t_h/_a_r_i_t_h)
Most IFP arithmetic functions are found here. Below is
a table of the existing functions. Some function's domain
may be further restricted due to range limitations.
February 9, 1987 IFP 0.5 Users Manual 13
_______________________________________________________________
_|N_a_m_e______D_o_m_a_i_n______________D_e_f_i_n_i_t_i_o_n_________________________|
| |
|+ [X,Y] in [R,R] X+Y |
| |
|- ... X-Y |
| |
|* ... XxY |
| |
|% [X,Y] in [R,R=/0] X/Y |
| |
|add1 X in R X+1 |
| |
|arcsin X in R, -1<_X<_1 arcsinX |
| |
|arccos X in R, -1<_X<_1 arccosX |
| |
|arctan X in R arctanX |
| |
|cos X in R cosX |
| |
|div [X,Y] in [R,R=/0] floor(X/Y) |
| |
|exp X in R eX |
| |
|ln X in R>0 log X |
| e |
|max [X,Y] in [R,R] max(X,Y) |
| |
|min [X,Y] in [R,R] min(X,Y) |
| |
|minus X in R -X |
| |
|mod [X,Y] in [R,R] X-Yfloor(X/Y) if Y=/0, 0 otherwise|
| |
|power [X,Y] in [R>_0,R] XY |
| |
|sin X in R sinX |
| _ |
|sqrt X in R>0 \|X |
| |
|sub1 X in R X-1 |
| |
|sum X in R* X +X +...+X |
| 1 2 n |
|tan X in R tanX |
_|______________________________________________________________|
February 9, 1987 IFP 0.5 Users Manual 14
_4._2._1._3. _L_o_g_i_c (/_m_a_t_h/_l_o_g_i_c)
Most IFP primitive functions returning boolean values
are found here. Below is a table of the existing functions:
February 9, 1987 IFP 0.5 Users Manual 15
______________________________________________
|_N_a_m_e_______D_o_m_a_i_n__________________D_e_f_i_n_i_t_i_o_n___|
| |
| = [X,Y] in [O,O] X=Y |
| |
| ~= ... X=/Y |
| |
| < [X,Y] in [R,R]U[S,S] X<Y |
| |
| <= ... X<_Y |
| |
| >= ... X>_Y |
| |
| > ... X>Y |
| |
| ~ X in B ~X |
| |
| and [X,Y] in [B,B] X/\Y |
| |
| all X in B* /\x |
| k k |
| |
| any X in B* \/xk |
| k |
| atom X in O X in A |
| |
| boolean X in O X in B |
| |
| false X in O X=#f |
| |
| imply [X,Y] in [B,B] ~X\/Y |
| |
| longer [X,Y] in [Om,On] m>n |
| |
| member [X,Y] in [O*,O] Y in X |
| |
| numeric X in O X in R |
| |
| null X in O* X=<> |
| |
| odd X in Z X mod 2 = 1|
| |
| or [X,Y] in [B,B] X\/Y |
| |
| pair X in O X in [O,O] |
| |
| shorter [X,Y] in [Om,On] m<n |
| |
| xor [X,Y] in [B,B] X=/Y |
|______________________________________________|
String inequalities are defined from the lexigraphical
February 9, 1987 IFP 0.5 Users Manual 16
(dictionary) ordering.
_4._2._1._4. _S_t_r_i_n_g _F_u_n_c_t_i_o_n_s (/_s_y_s)
The string functions are:
____________________________________________________________
_|N_a_m_e_______D_o_m_a_i_n_____D_e_f_i_n_i_t_i_o_n______________________________|
| |
|explode X in S sequence of characters in X |
| |
|implode X in S* string made by catenating strings in X|
| |
|patom X in A string representation of X, e.g. |
| 123 : patom -> "123" |
_|___________________________________________________________|
_4._2._1._5. _M_i_s_c_e_l_l_a_n_e_o_u_s _F_u_n_c_t_i_o_n_s (/_s_y_s)
The miscellaneous functions are listed below. Each
function description is preceded by a title line of the
form:
____________________________________________________________
function domain definition
____________________________________________________________
apply [X,F] in [O,S*] apply F to X
F is a sequence of strings representing a pathname
to a defined function. The result is the function
referenced by F applied to X. Example:
<<3 4> <math arith "+">> : apply -> 7
F may also be an anonymous function. Anonymous func-
tions are objects that are enclosed by parentheses. For
instance, the previous example could be written as
February 9, 1987 IFP 0.5 Users Manual 17
<<3 4> (+)> : apply -> 7
Functions built from functional forms may also be ob-
jects, for example:
<<<1 2 3> <4 5 6>> (trans|EACH * END|sum) -> 32
Function objects are considered to be atomic. Functions
that act on sequences will not behave properly when ap-
plied to a function object. The ``apply'' function com-
bined with function objects lets us define our own func-
tional forms. For example, we can define a functional
form Twice which applies a function twice as:
DEF Twice AS [apply,2]|apply;
Then we can write:
3 : [id,([id,id]|*)] | Twice -> 81
________________________________________________________
assoc [X,Y] in [(O+)*,O] associative lookup
X is an association sequence, which is a se-
quence of non-empty subsequences. The first
element of each subsequence is the _k_e_y of the
subsequence. The result of assoc is the first
subsequence of X with a key equal to Y. If no
matching key is found, f is returned. The key
may be any type of object. Examples:
<<<a b c> <w x y z> <i j>> w> -> <w x y z>
<<<a b c> <w x y z> <i j>> U> -> f
____________________________________________________
def X in S+ definition
The definition function returns the object
representation of its argument. The
representation of a function is a sequence
of strings denoting its absolute pathname.
The representation of a functional form is a
sequence. The first element of the sequence
is a pathname to the functional form. The
remaining elements of the sequence are
parameters of the functional form. Suppose,
for example, we define the inner product
function:
February 9, 1987 IFP 0.5 Users Manual 18
DEF Inner AS trans | EACH * END | INSERT + END
and ``Inner'' is defined with a module with
pathname ``/math/linear''. Then ``<math linear
Inner> : def'' will result in:
<
<sys compose>
<sys trans>
<<sys each> <math arith *>>
<<sys insertr> <math arith +>>
>
Currently, the representations of functional
forms are:
________________________________________________________
| #c <<sys constant> #c> |
| #? <<sys constant>> |
| n <<sys select> n> |
| nr <<sys select> -n> |
| f1|f2|...fn <<sys compose>, f1,f2,...fn |
| [f1,f2,...fn] <<sys construct>, f1,f2,...fn|
| ^c <<sys fetch> c> |
| EACH f END <<sys each> f> |
| FILTER p END <<sys filter> p> |
| INSERT f END <<sys insertr> f> |
| IF p THEN g ELSE h END <<sys if> p g h> |
||_W_H_I_L_E__p__D_O__f__E_N_D__________<_<_s_y_s__w_h_i_l_e_>__p__f_>______________||
ELSIF clauses are always expanded into
equivalent nested IF-THEN-ELSE constructions.
Note the special case for #?, the representation
<<sys constant> ?> would be useless due to the
bottom-preserving property.
________________________________________________
id X in O identity
The identity function returns its argu-
ment. It is useful as a place holder in
functional forms. For example, the
``square'' function can be written as:
DEF Square AS [id,id] | *;
February 9, 1987 IFP 0.5 Users Manual 19
_4._2._2. _U_s_e_r _D_e_f_i_n_e_d _F_u_n_c_t_i_o_n_s
The user may define functions by creating defini-
tion files (source code). The definition in the file is
of the form:
DEF _f_o_o AS _b_a_r;
where _f_o_o is the name of the function and _b_a_r is the de-
finition. The name of the file must also be _f_o_o. The
definition may be any IFP function. For example, you
can define the square function as:
DEF Square AS [/sys/id,/sys/id] | /math/arith/*;
Writing out the entire pathname of functions is not
necessary. If the function is defined in the same sub-
directory, then just its name is necessary. If the
function is defined in another subdirectory, then you
can ``import'' it. An imported function can be refer-
enced as though it were defined in the directory into
which it is imported. To import functions into a sub-
directory, you create an ``import file'' with the name
%IMPORT with the editor. The form of the %IMPORT file
is:
FROM directory IMPORT f ,f , ... f ;
FROM directory1 IMPORT g1,g2, ... gn;
... 2 1 2 m
The directory is a pathname to a directory. For exam-
ple, typical import file might be:
FROM /sys IMPORT apndr,distl,id,iota,takel;
February 9, 1987 IFP 0.5 Users Manual 20
FROM /math/arith IMPORT +,-,*,%;
Since the function ``id'' is imported, the square function
can be defined as:
DEF Square AS [id,id] | *;
_4._2._3. _F_u_n_c_t_i_o_n_a_l _V_a_r_i_a_b_l_e_s
Functional variables [Bac81a] are locally defined func-
tions with special scope rules. A functional variable defin-
ition is written:
{_l_h_s := _f_u_n_c_t_i_o_n}
where _l_h_s (left hand side) is either a function name or con-
struction of _l_h_s's. All function names in the _l_h_s become
functional variables within their scope. The scope is _b_o_u_n_-
_d_a_r_y _s_t_r_u_c_t_u_r_e_d as opposed to block structured, which means
that the variables may be seen only through certain boun-
daries. The scope rules can be defined by the following
transformations:
{V := h} v -> h | V -1
v
{V := h} [f ,f ,...] -> [{V := h} f , {V := h} f , ...]
1 2 1 2
{V := h} IF p THEN x IF {V := h} p THEN {V := h} x
ELSE y -> ELSE {V := h} y
END END
where -> indicates that the left side may be simplified to
the right side. ``V'' denotes a left-hand side containing
the functional variable ``v''. V -1 is the inversion func-
v
tion of ``V'' for ``v''. For example, if V = [a,b,c], then
V -1 = 3. Variables must be defined before use. Note that
c
the vertical bar of composition cuts off the scope, e.g. in
{[_x,_y] := id} _g | _h
February 9, 1987 IFP 0.5 Users Manual 21
the function _g can ``see'' _x and _y, but _h can not.
An example of a definition with functional variables
appears below:
(*
* InsertSort
*
* This function sorts a sequence of numbers or strings into ascending order
* using insertion sort.
*
* Examples:
*
* <3 1 4 1 5 9 2> : InsertSort == <1 1 2 3 4 5 9>
*
* <all work and no play> : InsertSort == <all and no play work>
*
* The sequence may not mix strings and numbers.
*)
DEF InsertSort AS
IF null THEN id (* Check for trivial case *)
ELSE
[tl,[1]] | apndr |
INSERT
{[Element,Seq] := id}
{[Left,Right] := [Seq, distl | FILTER > END | length] | [takel,dropl]}
[Left,[Element],Right] | cat
END
END;
In this example, _E_l_e_m_e_n_t, _S_e_q, _L_e_f_t, and _R_i_g_h_t are function-
al variables.
_4._3. _F_u_n_c_t_i_o_n_a_l _F_o_r_m_s
Functional forms combine functions and objects to
create new functions.
_4._3._1. _C_o_n_s_t_a_n_t
Constant functions always return the same result when
applied to any value which is not ``?''. Constant functions
February 9, 1987 IFP 0.5 Users Manual 22
are written as:
#_c
where c is the constant value to be returned. A constant
function applied to ``?'' results in ``?''. Note that the
function ``#?'' always returns `?'. Examples:
923 : #<cat in hat> -> <cat in hat>
<a b c d e f> : #427 -> 427
? : #<q w er t y> -> ?
5 : #? -> ?
_4._3._2. _S_e_l_e_c_t_i_o_n
Selector functions return the nth element of a sequence
and are written as n, where n is a positive integer. Note
the distinction between #5, which returns the value 5, and
5, which returns the fifth element of its argument. There
are also a corresponding set of select-from-right functions,
written as nr. These select the nth element of a sequence,
counting from the right. All selectors return ``?'' if the
argument has no nth element or is not a sequence. Below are
some examples of applying selector functions:
<a b c d e> : 1 -> a
<a b c d e> : 2 -> b
<apple banana cherry> : 1r -> cherry
<apple banana cherry> : 4 -> ?
hello : 1 -> ?
_4._3._3. _C_o_m_p_o_s_i_t_i_o_n
The function composition of two functions is written
as:
February 9, 1987 IFP 0.5 Users Manual 23
f | g
Applying the result function is the same as applying f and
then g. E.g.: Function composition is defined by the equal-
ity:
x : (f | g) =_ (x : f) : g
Since function composition is associative, the composition
of more than two functions does not require parentheses.
The composition of f ,f ,...f is written:
1 2 n
f | f | ...f
1 2 n
Composition syntax is identical to UNIX's pipe notation for
a reason: function composition is isomorphic to a pipe
between processes without side effects.
_4._3._4. _C_o_n_s_t_r_u_c_t_i_o_n
The construction of functions is written as bracketed
list of the functions. For example, the construction of
functions f is written:
i
[f ,f ,...f ]
1 2 n
Function construction is defined by the equality:
x : [f ,f ,...f ] =_ <x:f ,x:f ,...x:f >
1 2 n 1 2 n
_4._3._5. _A_p_p_l_y _t_o _E_a_c_h
The EACH functional form applies a function to each
element of a sequence. It is written as
EACH _f END
February 9, 1987 IFP 0.5 Users Manual 24
It is defined by the equality:
<x ,x ,...x > : EACH f END =_ <x :f,x :f,...x :f>
1 2 n 1 2 n
_4._3._6. _I_f-_T_h_e_n-_E_l_s_e
The IF functional form allows conditional function ap-
plication. It is written as
IF _p THEN _g ELSE _h END
and is defined by the equality:
| g(x) if p(x)=t
|
x :IF p THEN g ELSE h END -> | h(x) if p(x)=f
| ? otherwise
|
The level of nesting of conditional forms may be reduced by
using ELSIF clauses:
IF p THEN g
ELSE1 1
IF p THEN g
ELSE2 2
IF p THEN g
ELSE3h 3
END
END
END
_4._3._7. _F_i_l_t_e_r
The FILTER functional form filters through elements of
a sequence satisfying a predicate. It is written as:
FILTER _p END
where p is the predicate. It is defined by the functional
equality:
EACH
IF _p THEN [id] ELSE [] END
END | cat
February 9, 1987 IFP 0.5 Users Manual 25
For example, if you wish to find all numeric elements in a
sequence, you could write:
FILTER numeric END
The FILTER functional form is an IFP extension to Backus'
FP.
_4._3._8. _R_i_g_h_t _I_n_s_e_r_t
The INSERT functional form is defined by the recursion:
INSERT _f END =_ IF tl|null THEN 1 ELSE [1,tl | INSERT _f END] | _f END
Typically it is used for crunching a sequence down. For ex-
ample,
INSERT + END
returns the sum of a sequence.
Unlike Backus' FP, functions formed with INSERT are al-
ways undefined for empty sequences. The reason is that it
is impractical for the interpreter to know the identity ele-
ment of user-defined functions. The number of cases where
the interpreter could know the identity element are so few
that you might as well define special functions for those
cases, e.g:
DEF sum AS IF null THEN #0 ELSE INSERT + END END;
Alternatively, you can append the identity element to the
end of the sequence before inserting, e.g.:
DEF sum AS [id,#0] | apndr | INSERT + END;
Currently there is no ``left insert'' form. The left
insertion of f can be written as:
February 9, 1987 IFP 0.5 Users Manual 26
reverse | INSERT reverse|f END
_4._3._9. _W_h_i_l_e
The WHILE functional form allows indefinite composi-
tion. It is written as:
WHILE _p DO _f END;
and is defined by the recursive functional equality:
WHILE _p DO _f END =_ IF _p THEN
_f | WHILE _p DO _f END
ELSE id
END
That is the _W_H_I_L_E PFO applies the fewest f's such that
_x:_f:_f:_f...:_p is true.
_4._3._1_0. _F_e_t_c_h[_8]
The fetch functional form allows easy access to associ-
ation sequences (see function /sys/assoc in section 4.2.1.5
for a description of association sequences.) A fetch is
written as ^c, where c is an object. The fetch form is de-
fined by the functional equality:
^_c =_= IF EACH pair END | all THEN [id,#_c]|assoc|2
ELSE #?
END;
Note that the input is restricted to a sequence of pairs.
For example,
<<a 1> <b 2> <c 3>> : ^b -> 2
____________________
[8]The fetch functional form is being deimplemented. It
may or may not exist on your IFP interpreter.
February 9, 1987 IFP 0.5 Users Manual 27
_4._4. _C_o_m_m_e_n_t_s
Comments are delimited by matching pairs of ``(*'' and
``*)''. Comments may be inserted anywhere not adjacent to a
token. For example:
DEF foo AS bar; (* This is a comment. DEF foo AS bar is not a comment *)
_4._5. _S_y_n_t_a_x _S_u_m_m_a_r_y
Below is an EBNF grammar for IFP:
________________________________________________________________________________________
|Def -> 'DEF String 'AS' Comp ';' |
|Comp -> Simple { '|' Simple } |
|Simple -> Conditional | Constant | Construction | Each | Filter | |
| Insert | Path | While | Fetch | Debug | FunVar |
|Conditional -> 'IF' Comp 'THEN' Comp { 'ELSIF' Comp 'THEN' Comp } 'ELSE' Comp 'END'|
|While -> 'WHILE' Comp 'DO' Comp 'end' |
|Insert -> 'INSERT' Comp 'END' |
|Each -> 'EACH' Comp 'END' |
|Filter -> 'FILTER' Comp 'END' |
|Fetch -> '^' String |
|Constant -> '#' Object |
|Debug -> '@' Object |
|FunVar -> '{' Lhs ':=' Comp '}' |
|Lhs -> String | '[' [ Lhs { ',' Lhs } ] ']' |
|Construction -> '[' [Comp {',' Comp}] ']' |
|Path -> ['/'] String {'/' String} |
|Object -> Bottom | Atom | '<' [Atom {','Atom}] '>' |
|Bottom -> '?' |
|Atom -> Number | String | Boolean |
_||B_o_o_l_e_a_n__-_>_________'_t_'__|__'_f_'_____________________________________________________________||
Strings may be in single or double quotes. The strings
``t'' and ``f'' must be quoted to distinguish them from
boolean atoms. Strings of digits must also be quoted to
distinguish them from numeric atoms.
_5. _I_F_P _G_r_a_p_h_i_c_s (_o_p_t_i_o_n_a_l)[_9]
____________________
[9]This option is currently not implemented. If this
section inspires you, get the source code and fix it (see
G_*.c).
February 9, 1987 IFP 0.5 Users Manual 28
There are no graphics primitives in IFP itself, rather
IFP is used to calculate a display list. A display-list
processor then draws the picture specified by the display
list. To send an IFP result to the display-list processor
instead of the screen, use the command:
graph object : function
instead of the ``show'' command.
_5._1. _C_o_o_r_d_i_n_a_t_e _S_y_s_t_e_m
Points on the graphics display are referenced by <X,Y>
coordinate pairs. <0,0> is the lower left corner, <1,1> is
the upper left corner. Currently there is no clipping.
Lines outside the display are wrap around in weird and not-
so-wonderful ways.
_5._2. _D_i_s_p_l_a_y _L_i_s_t _S_t_r_u_c_t_u_r_e
Below is an EBNF grammar for the display list.
______________________________________________________________________________
| |
| display-list -> < {display-list} > | polyline | color | transform | text |
| polyline -> <'line' { < x y > } > |
| color -> <'color' color-index display-list > |
| text -> <'text' atom size ['center']> |
| transform -> <'trans' t-matrix display-list > |
| t-matrix -> <<Txx Txy Tx0> <Tyx Tyy Ty0>> |
_||_____________________________________________________________________________||
_5._2._1. _P_o_l_y_l_i_n_e
The polyline structure specifies a sequence of points.
It is of the form:
February 9, 1987 IFP 0.5 Users Manual 29
<line <x ,y > <x ,y > ... <x ,y >>
1 1 2 2 n n
where each <x ,y > is a point coordinate. Adjacent points
i i
in the sequence are connected with line segments. For exam-
ple, the sequence:
<line <0 0> <0 5> <1 5> <1 0> <0 0>>
draws a box 1 unit wide and 5 units high.
_5._2._2. _C_o_l_o_r
The color structure draws the display-list in the color
specified by the color index (0..15). The color applies to
all parts of the subordinate display-list which are not
subordinate to a color structure within. In other words, a
structure is colored by its inner-most bounding ``color''
structure.
_5._2._3. _T_r_a_n_s_f_o_r_m
The transform structure draws the display-list as
transformed by the t-matrix. Transforms may be nested.
Transforming a display-list converts coordinates <x,y> into
coordinates <x',y'> via the formula:
| x' | | Txx Txy Tx0 | | x |
| | = | | | y |
| y' | | Tyx Tyy Ty0 | | |
| | | 1 |
_5._2._4. _T_e_x_t
The text structure draws the atom with the lower-left
corner at (0,0). Each character is drawn in a _s_i_z_e by _s_i_z_e
February 9, 1987 IFP 0.5 Users Manual 30
box (including spacing) The lower-left corner of the text is
at <0 0> by default. Including the _c_e_n_t_e_r option centers
the text on <0 0>.
_6. _D_e_b_u_g_g_i_n_g
Currently, IFP has simple program trace mechanism.[10]
To trace a function, respond to the IFP prompt with:
trace on f ,f ,...f ;
1 2 n
where the f's are functions to be traced. Whenever a traced
function is invoked, its argument and result are shown.
Also, the argument and result of all called functions are
shown. To stop tracing functions, respond to the IFP prompt
with:
trace off f ,f ,...f ;
1 2 n
When tracing, the interpreter ellipses are used to ab-
breviate functions. You can set the depth at which ellipses
occur with the _d_e_p_t_h command:
depth n
where n is a non-negative integer. The default depth is
two.
There is also a functional form for creating trace
functions. Its form is
@_m_e_s_s_a_g_e
____________________
[10]This will be replaced by a much better trace mechan-
ism as soon as the author as time to design one.
February 9, 1987 IFP 0.5 Users Manual 31
The function formed always returns its argument unchanged,
and it prints ``message: '' followed by its argument. For
example,
<1 3 5> : EACH @banana END
will print the messages:
banana: 1
banana: 3
banana: 5
This tracing functional form is for debugging only, since it
creates a side effect (the message!), it is not truly func-
tional.
_7. _D_i_f_f_e_r_e_n_c_e_s _b_e_t_w_e_e_n _I_F_P _a_n_d _B_a_c_k_u_s' _F_P
_7._1. _D_o_m_a_i_n
Backus' FP has two types of atom, the string and empty
sequence. IFP atoms do not include the empty sequence. IFP
include numbers and truth values as atoms distinct from
strings.
_7._2. _F_u_n_c_t_i_o_n_s
There are many new primitives. See the section on
``Primitives'' elsewhere. Of particular interest are the
functions _c_a_t, _d_r_o_p_l, _t_a_k_e_l, _t_a_k_e_r, and _i_o_t_a.
_7._3. _F_u_n_c_t_i_o_n_a_l _F_o_r_m_s
Backus' FP defines the INSERT form for empty sequences
as returning u , the right identity element of f. IFP does
f
February 9, 1987 IFP 0.5 Users Manual 32
not define INSERT for empty sequences. If necessary, use
one of the following functions:
IF null THEN u ELSE INSERT f END END
f
[id,u ] | apndr | INSERT f END
f
IFP has a new functional form, FILTER, which filters a
sequence according to a predicate. It is written as:
FILTER p END
When applied to a sequence X, it returns a sequence of x
i
for which p is true.
_7._4. _S_y_n_t_a_x
The IFP syntax is designed to facilitate indentation
and comments. All functional forms bracket their parame-
ters, so no parentheses are necessary. The differences
between Backus' FP and IFP syntax are shown below.
___________________________________________________
|_B_a_c_k_u_s___________I_F_P________________________________|
| CBA A | B | C |
| [F,G,H] [F,G,H] |
| p->f;g IF p THEN f ELSE g END |
| p->f; q->g; h IF p THEN f ELSIF q THEN g ELSE h|
| Af EACH f END |
| /f INSERT f END |
| (while p f) WHILE p DO f END |
| (_bu f x) [id,#x] | _f |
| f #_f |
| Def f =_ x DEF f AS x; |
| U <> |
| _| ? |
|___________________________________________________|
Also, parentheses are neither necessary nor allowed in IFP
function definitions.
February 9, 1987 IFP 0.5 Users Manual 33
Finally, IFP functions are arranged in a tree structure
and referenced by pathnames. All pathnames are expanded
into absolute pathnames when read by the interpreter, so the
meaning of a pathname is static. This is an important
point, otherwise IFP would have significantly different (and
more complex) semantics than Backus' FP.
_8. _F_u_n_c_t_i_o_n_a_l _P_r_o_g_r_a_m_m_i_n_g _T_e_c_h_n_i_q_u_e_s
_8._1. _F_u_n_c_t_i_o_n_a_l _P_r_o_g_r_a_m_m_i_n_g _I_d_e_n_t_i_t_i_e_s
Functional programs can be improved by algebraic sub-
stitutions. Below is a table of some IFP identities. The
notation ``f=_g'' indicates f and g are equal and have the
same domain. The notation ``f < g'' indicates that g is
equal to f over f's domain, but may have a larger domain
than f.
__________________________________________________________
| EACH f END | EACH g END =_ EACH f | g END |
| [#c,id] | distl =_ EACH [#c,id] END |
| [takel,dropl] | cat < 1 |
| apndl | length < 2 | length | add1 |
| apndr | length < 1 | length | add1 |
| iota | length < id |
| reverse | length =_ length |
| tl | length < length | sub1 |
| tlr | length < length | sub1 |
| apndl | reverse =_ [2 | reverse,1] | apndr |
| apndr | reverse =_ [2,1 | reverse] | apndl |
| reverse | reverse < id |
||_t_r_a_n_s__|__t_r_a_n_s_______________<_____i_d________________________||
February 9, 1987 IFP 0.5 Users Manual 34
_8._2. _C_o_m_m_o_n _S_u_b_f_u_n_c_t_i_o_n_s
The interpreter is not very smart about common subfunc-
tions, it reevaluates a function every time its encountered.
You can always factor out such common subfunctions by creat-
ing extra function constructions. Consider the function:
[f,a,f|g,b]
You can move f to outside the construction by forming the
pair [id,f] and making the transformation:
[f, a, f|g, b] -> [id,f] | [2, 1|a, 2|g, 1|b]
In general, create the pair [id,f]. Then replace all lead-
ing occurrences of f in the construction by the 2 selector
and insert a leading 1 selector elsewhere in the construc-
tion.
_8._3. _S_t_a_t_e _M_a_c_h_i_n_e_s
You can simulate a state machine in IFP by defining the
state transition function D, which maps an input and state
into another state:
[input,state] : _D -> state
You then run the state machine with the function
apndl | reverse | INSERT _D END
which yields the final state when applied to the initial
conditions <initial-state,tape>.
February 9, 1987 IFP 0.5 Users Manual 35
_8._4. _T_a_i_l _R_e_c_u_r_s_i_o_n
Regrettably, the IFP interpreter currently does not
recognize tail recursions as iterations. Thus near-infinite
recursions will cause a stack overflow. If this is a prob-
lem, rewrite the function with the WHILE functional form to
remove the tail recursion.
For example, consider the tail recursive function:
DEF f AS
IF p THEN g
ELSE h | f (* tail recursion *)
END;
We can rewrite is as:
DEF f AS
WHILE p|~ DO h END | g;
_9. _I_n_s_t_a_l_l_a_t_i_o_n _N_o_t_e_s
_9._1. _M_a_c_h_i_n_e _D_e_p_e_n_d_e_n_c_e
The IFP interpreter is machine independent, as long as
your machine has 32-bit two's complement integers and IEEE
floating point. If not, you should take a look at the
struct.h and F_arith.c source files. The struct.h file de-
fines all the principle types and limit definitions (e.g.
MaxInt, MAXFLOAT). The F_arith.c contains the arithmetic
functions. See the comments in the code for details.
February 9, 1987 IFP 0.5 Users Manual 36
_9._2. _C_o_m_p_i_l_i_n_g _O_p_t_i_o_n_s
Look in the Makefile and "struct.h" for possible com-
piling options. Not all options are available in all
releases. Normally, the release version comes ready to com-
pile on UNIX boxes. For MSDOS, you will have to modify the
Makefile and change the OPSYS variable in ``struct.h''. The
graphics interface is extremely machine dependent, though
should not be difficult to modify it for other machines.
February 9, 1987 IFP 0.5 Users Manual 37
____________________
Bac78a.
John Backus, "Can Programming Be Liberated from the von
Neumann Style? A Functional Style and Its Algebra of
Programs," _C_A_C_M Vol. 21,8 pp. 613-641 ACM, (August
1978).
Rob87a.
Arch D. Robison, "A Functional Programming Inter-
preter," _T_H_E_S_I_S, University of Illinois, (January
1987).
Rob87b.
Arch D. Robison, "Illinois Functional Programming: A
Tutorial," _B_Y_T_E Vol. 12,2 pp. 115-125 McGraw-Hill Inc.,
(February 1987).
Bad83a.
Scott Baden, "Berkeley FP User's Manual, Rev. 4.1,"
_U_N_I_X _P_r_o_g_r_a_m_m_e_r_s _M_a_n_u_a_l, (July 27,1983).
Dar82a.
J. Darlington, J.V. Guttag, P. Henderson, J.H. Morris,
J.E.Stoy, G.J. Sussman, P.C. Treleaven, D.A. Turner,
J.H. Williams, and D.S. Wise, _F_u_n_c_t_i_o_n_a_l _P_r_o_g_r_a_m_m_i_n_g
_a_n_d _i_t_s _A_p_p_l_i_c_a_t_i_o_n_s, Cambridge University Press
(1982).
Bac81a.
John Backus, "The Algebra of Functional Programs: Func-
tional Level Reasoning, Linear Equations, and Extended
Definitions," in _F_o_r_m_a_l_i_z_a_t_i_o_n _o_f _P_r_o_g_r_a_m_m_i_n_g _C_o_n_c_e_p_t_s,
Springer Verlag, New York (1981).
SHAR_EOF
# End of shell archive
exit 0
--
Rich $alz "Anger is an energy"
Cronus Project, BBN Labs rsalz@pineapple.bbn.com
Moderator, comp.sources.unix sourcrin2. 2. na>,