.EQ
delim $$
gfont C
.EN

.de Ds
.nr PS 9
.nr VS 11
.LP
.RS
.LD
..

.de De
.nr PS 10
.nr VS 12
.DE
.RE
..

.TL
User Manual for the Persistent Functional Language (PFL)
.br
Release 0.1
.AU
.AB
.LP
PFL is a lazy functional database language with a polymorphic type inference
system which enforces strong type checking.  All functions persist in a
database, and are specified by the insertion and deletion of equations.  New
data types and values of these types can be added at any time.  A class of
functions called selectors support the storage and associative retrieval of
bulk data.  Selectors play a role similar to the facts of a logic database,
and functions can be defined over selectors which are analogous to the rules
of a logic database.  In addition to supporting database querying, functions
can also be defined to update the database.
.sp 2
.SH
Contents
.LP
1.	An overview of PFL
.RS
.LP
1.1.	Using PFL
.LP
1.2.	About this manual
.LP
1.3.	Summary of the PFL interpreter
.RE
.LP
2.	Expressions
.RS
.LP
2.1.	Simple expressions
.LP
2.2.	Operator expressions
.LP
2.3.	Function applications
.LP
2.4.	Patterns
.RE
.LP
3.	The type system
.RS
.LP
3.1.	Structure of the type system
.LP
3.2.	User defined types
.LP
3.3.	User defined values
.LP
3.4.	User defined functions
.LP
3.5.	System defined functions
.RE
.LP
4.	Equations
.LP
5.	Selectors
.RS
.LP
5.1.	Declaration, update and associative retrieval
.LP
5.2.	Defining rules over selectors
.RE
.LP
6.	Evaluation of expressions
.LP
7.	The command processor
.LP
Appendices and References
.AE
.bp
.SH
1.	An Overview of the PFL System
.SH
1.1.	Using the PFL System
.LP
Synopsis:
.Ds
\fCpfl -dname -hsize -p -X\fR
.De
.LP
Description:  All command line arguments are optional.  If no name is
specified (-d) then a database called "demo" is assumed; if the specified
database does not exist then it is automatically created.  A number of
library functions have been defined for PFL which are to be found in
/bbkcs/lib/pfl/environ/std.env.  These are automatically loaded into the
database when it is created.  Example functions which illustrate various
features of PFL can be found in "/bbkcs/lib/pfl/environ/example.env".  PFL
is exited by entering Control and D simultaneously.  All changes made during
the session are saved in the database before exiting.
.LP
The command line options are :
.IP "-dname" 8
Open the database "name".  If this option is omitted then the database
"demo" (in the current working directory) is assumed.  The database is
stored as a collection of files in a directory of the stated name; thus a
database can be removed when no longer required by entering "rm -r name".
.IP "-hsize" 8
Specifies the size of the heap used by PFL for intermediate computations.
By default this is 50000 cells, but this can be varied depending upon the
amount of memory available on your machine.
.IP "-p" 8
Switches on a primitive profiler.  Following the evaluation of an expression
the name of each function called is displayed together with a count of the
total number of calls.
.IP "-X" 8
Opens up a graphics window and permits use of PFL's graphics routines.
.SH
1.2.	About this manual
.LP
It is beyond the scope of this manual to provide a tutorial on functional
programming, and consequently the reader is assumed to have had prior
exposure to lazy functional programming languages such as Miranda\**
.FS
Miranda is a trademark of Research Software Ltd.
.FE
[Tur85].  A good introductory textbook for functional programming is that of
Bird and Wadler [Bir88]; for those in a hurry, the paper by Hughes [Hug89]
may be sufficient.  This implementation of PFL is based upon the ideas
developed in [Sma91, Pou91, Sma92], although the syntax has changed
somewhat.  In future releases we plan to incorporate both sets and integrity
constraints into the language, based upon the work described in [Pou93,
Red93].  You are recommended to try out the demonstrator (Appendix 2) at an
early opportunity.
.LP
The structure of this manual is as follows.  The remainder of Section 1
provides a summary of the operations supported by the PFL command
interpreter, which are explained in more detail throughout the remainder of
the manual.  Section 2 describes the syntax of expressions.  PFL is a
strongly typed language, and the structure of the type system is explained
in Section 3.  This section also describes the system defined functions
provided by PFL and how new user defined functions can be declared.  The
definition of user defined functions is described in Section 4, whilst
Section 5 describes a special class of functions called selectors which are
used for the storage and associative retrieval of bulk data.  Section 6
describes how expressions are evaluated, and finally Section 7 describes the
definition of functions which modify the database state and access
externally stored files.
.SH
1.3.	Summary of the PFL Interpreter
.LP
The PFL command interpreter accepts and executes commands of the following
forms:
.LP
e\fC;\fR
.RS
causes the expression e to be evaluated and the result to be displayed 
(see Section 6).
.RE
\fC_typeof e;\fR
.RS
causes the type of the expression e to be displayed.
.RE
\fC_type c  ==  m;\fR
.RS
states that c is a constructor of the meta-type m (see Section 3.2).
.RE
\fC_value c  ==  o;\fR
.RS
states that c is a constructor of the object-type o (see Section 3.3).
.RE
\fC_function f  ==  o;\fR
.RS
states that f is a function of object-type o (see Section 3.4).  If
equations already exist for f these are deleted from the database.  The type
of f is determined both from the declared type, o, and the types inferred
for the equations of f as they are incrementally specified.
.RE
\fC_define f p1 ... pn  ==  e;\fR
.RS
adds an equation for the user-defined function f (see Section 4).  We may
informally read this equation as stating that the function f, when applied
to expressions e1 to en which match the patterns p1 to pn, returns the
expression e.
.RE
\fC_display f;\fR
.RS
displays the equations for the user-defined function f.
.RE
\fC_extsel s  ==  o;\fR
.RS
states that s is a selector of type \fCo->[o]\fR (see Section 5).  If s has
already been declared as a selector then the existing extent is deleted.
.RE
\fC_include s  e;\fR
.RS
adds the value e to the extent of the selector s (see Section 5).
.RE
\fC_exclude s  e;\fR
.RS
removes from the extent of the selector s any values which match e (see
Section 5).
.RE
\fC_commit;\fR
.RS
commits the current database state.
.RE
\fC_restore;\fR
.RS
restores the last committed database state.
.RE
\fC_command c;\fR
.RS
causes the command c to be evaluated and the result displayed (see Section 7).
.RE
\fC_load "f";\fR
.RS
directs PFL to read operations from the file with unix path name f.
.RE
.LP
\fC_system "c";\fR
.RS
causes the unix shell command "c" to be executed.
.RE
.SH
2.	Expressions
.LP
An expression is either a simple expression, an operator expression or a
function application.
.LP
.SH
2.1.	Simple Expressions
.LP
A \fIsimple expression\fR is one of :
.IP (i)
a \fIvariable\fR, which is a sequence of characters, numbers and
underscores, and which starts with a lower case character (eg. succ, x,
fun_aux1);
.IP (ii)
a \fIconstructor\fR, which is either :
.RS
.IP *
a number (eg. 123, -123, 123.456, -123.456);
.IP *
a character enclosed in single quotes (eg. '1');
.IP *
a sequence of characters enclosed in double quotes (eg. "the string 1");
.IP *
a sequence of characters, numbers and underscores, and which starts with an
upper case character (eg. True, Person1, Sales_and_Accounts);
.RE
.IP (iii)
a \fIselector\fR, which is a sequence of characters, numbers and
underscores, starting with a vertical bar (eg. |candidates);
.IP (iv)
a \fItuple\fR (see Section 2.1.1);
.IP (v)
a \fIlist\fR (see Section 2.1.2); or
.IP (vi)
a \fIbracketed expression\fR, ie. an expression enclosed in round brackets.
.LP
.SH
2.1.1.  Tuples
.LP
A \fItuple\fR is a structured expression whose components may be of differing
types.  A tuple takes the form :
.Ds
\fC(e1, e2, ..., en)\fR
.De
where e1 to en are expressions.  That is, a tuple comprises at least two
expressions separated by commas and enclosed in round brackets.  Examples of
tuples include :
.Ds
\fC// a 3-tuple of type (Num,Chr,Str)
	(1,'a',"a string")	
// a 2-tuple of type ((Num,Str),(Num,Str))
	((1,"Justinian"),(2,"Theodora"))\fR
.De
.SH
2.1.2.  Lists
.LP
A \fIlist\fR is a structured expression of whose components are all of the
same type.  A list is one of :
.IP (i)
the \fIempty\fR list, \fC[]\fR;
.IP (ii)
a \fIconstructed\fR list, which is built using the `:' operator, such as
\fC1:(2:(3:[]))\fR;
.IP (iii)
an \fIenumerated\fR list, which takes the form \fC[e1,...,en]\fR;
.IP (iv)
a \fIdot-dot\fR list which takes one of the following forms :
.RS
.IP "\fC[a..b]\fR" 8
where a and b are numbers, and which denotes the list
\fC[a,a+1,...,b-1,b]\fR;
.IP "\fC[a..]\fR" 8
where a is an number, and which denotes the infinite list
\fC[a,a+1,a+2,...]\fR;
.RE
.IP (v)
a \fIlist abstraction\fR which takes the form :
.Ds
\fC[\fRe\fC | \fRq1\fC; ...; \fRqn\fC]\fR
.De
.IP
where e is an expression and the qi's are qualifiers.  A \fIqualifier\fR is
either a \fIfilter\fR (a boolean valued expression) or a \fIgenerator\fR of
the form \fCp <- lve\fR where p is a pattern and lve is a list-valued
expression.  A generator is understood to state that p is matched with each
value in e in turn.  A list abstraction is read as "the list of e's such
that q1 and ... and qn".  
.LP
Examples of list abstractions include :
.Ds
\fC--> [x * x | x <- [2..]];
[4,9,16,25,...]
--> [(x,y) | x <- [1..3]; y <- [False,True]];
[(1,False),(1,True),(2,False),(2,True),(3,False),(3,True)]
--> [x | x <- [0..]; x % 2 = 0];
[0,2,4,6,...]
--> [z | (2,z) <- [(x,y) | x <- [1..3]; y <- [False,True]]];
[False,True]
--> [x | x <- [1..]; [y | y <- [2..(x-1)]; x % y = 0] = []];
[1,2,3,5,7,11,13,17,19,23,29,...]\fR
.De
.SH
2.2.	Operator Expressions
.LP
Table 1 below lists the operators in increasing order of precedence.
Further details regarding these operators can be found in std.env.  Note
that there is a system defined ordering over all non-function types.  For
the numbers, characters and strings the ordering is that which you would
expect.  For booleans, False precedes True.  For lists, tuples and other
constructed data types the ordering is non-obvious but reproducible.
.KF
.TS
box expand tab(;);
c | l | l.
\fC\s-2Operator;Type;Description
_
_
:;type0->[type0]->[type0];non-empty list constructor
++;[type0]->[type0]->[type0];list append operator
_
&;Bool->Bool->Bool;logical and
#;Bool->Bool->Bool;logical or
_
\(eq;type0->type0->Bool;equal to
>;type0->type0->Bool;greater than
<;type0->type0->Bool;less than
!=;type0->type0->Bool;not equal to
<=;type0->type0->Bool;less than or equal to
>=;type0->type0->Bool;greater than or equal to
?=;type0->type0->Bool;matches
_
+;Num->Num->Num;addition
-;Num->Num->Num;subtraction
_
-;Num->Num;unary minus
*;Num->Num->Num;multiplication
/;Num->Num->Num;division
div;Num->Num->Num;division with truncation
%;Num->Num->Num;remainder
_
!;[type0]->Num->type0;list subscript\s+2\fR
_
.TE
.DS C
Table 1 :  Operators and their precedences
.DE
.KE
.LP
.SH
2.3.	Function Applications
.LP
Function application is shown by juxtaposition.  A \fIfunction
application\fR is an expression of the form :
.RS
f  e1  ...  en
.RE
where f is a variable which is bound to a function and e1 to en are
expressions.  Function application is left-associative, and thus the
expressions "foo a b c" and "((foo a) b) c" are identical, whilst the
expression "succ succ 0" is ill-typed (assuming that succ is the successor
function of type Num->Num).  Function application has higher precedence than
any operator; hence the expressions "succ 1 + 2" and "(succ 1) + 2" are
equivalent.  An infix operator can be used prefix (and hence can be used as
a function) by enclosing it in round brackets.  Thus, for example, the
expressions "5 * 10" and "(*) 5 10" are equivalent.
.LP
.SH
2.4.	Patterns
.LP 
A pattern is an expression which does not contain an operator or a function
application.  Thus, a pattern is either (i) a variable, (ii) an n-ary
constructor followed by m (m \(<= n) patterns, or (iii) a pattern enclosed in
brackets.  
.SH
3.	The Type System
.SH
3.1.	Structure of the Type System
.LP
PFL's type system comprises three layers :
.IP (i)
A single meta-level type, \fCType\fR, which is the set of all types;
.IP (ii)
The object-level types, which are also regarded as metalevel values of type
\fCType\fR.
.IP (iii)
The values of each object level type.
.LP
There are initially four system defined object-level types - Bool, Str, Num
and Char - and consequently four sets of system-defined values - the
booleans, strings, numbers and characters - which populate these types.  In
addition to these types and values, there is also the distinguished value
Any which is a value of every type.  New user-defined object-level types and
values can be introduced at any time, the only proviso being that the type
or value constructor being introduced is not currently already in use.
.SH
3.2.	User Defined Types
.LP
New (object-level) type constructors can be introduced using the "_type"
command :
.Ds
\fC_type \fRc\fC == \fRt\fC;\fR
.De
which we read as stating that c constructs a type.  For example, the
following declarations state that Employee and Department are types, that
for all types a, (List a) is a type, and that for all types a and b,
(Product2 a b) is a type :
.Ds
\fC_type Employee	==	Type;
_type Department	==	Type;
_type List		==	type0->Type;
_type Product2	==	type0->type1->Type;\fR
.De
Note that there are infinitely many type variables - type0, type1, type2 etc
- and that type constructors must start with an upper case letter.  A type
constructor may be redeclared at any time during the lifetime of a database
as long as no value constructors (see Section 3.3) are declared for that
type.
.SH
3.3.	User Defined Values
.LP
New value constructors can be introduced using the "_value" command :
.Ds
\fC_value \fRc\fC == \fRt\fC;\fR
.De
which we read as stating that c constructs a value of type t.  For example,
the following declarations state that John and Sales are values of type
Employee and Department respectively; that for all types t, [ ] is a value of
type List t; that for all types t, whenever a is a value of type t and b is a
value of type List t then ((:) a b) is also a value of type List t; and that
whenever a is a value of type t1 and b is a value of type t2 then (Tuple2 a
b) is a value of type Product2 t1 t2 :
.Ds
\fC_value John		==	Employee;
_value Sales		==	Department;
_value []		==	List type0;
_value (:)		==	type0->(List type0)->(List type0);
_value Tuple2	==	type0->type1->(Product2 type0 type1);\fR
.De
Constructors which take no arguments - such as John and Sales above - are
sometimes referred to as constants.  A value constructor may be redeclared at
any time during the lifetime of a database as long as it does not appear in
an equation (see Section 4) or selector (see Section 5).
.sp 1
.B1
Note.  The declarations for list and product types are automatically loaded
from std.env into a database at creation time.  Since these types are used
frequently the following abbreviations are available :
.Ds
\fCList t						\(==		[t]
Productn t1 ... tn			\(==		(t1,...,tn)
Tuplen v1 ... vn				\(==		(v1,...,vn)
(v1:(v2:(...(vn:[])...)))	\(==		[v1,...,vn]\fR
.De
Thus the declarations for (:), [] and Tuple2 can equivalently be written :
.Ds
\fC_value []		==	[type0];
_value (:)		==	type0->[type0]->[type0];
_value Tuple2	==	type0->type1->(type0,type1);\fR
.De
.B2
.LP
.SH 
3.4.	User defined functions
.LP
Functions are defined through one or more equations and the type of a
function is automatically inferred as its equations are specified (see
Section 4).  The user may, however, optionally declare the type of the
function using the "_function" command :
.RS
\fC_function \fRf\fC == \fRt\fC;\fR
.RE
where f is a variable and t is its type.  Following such a declaration, any
existing equations for f are deleted and the type of f becomes t.  If the
user cannot determine the ultimately intended type of f but wishes to remove
any existing equations for f, then the type may be specified as type0.
.SH
3.5.	System defined functions
.LP
A number of sytem defined (or "built in") functions are provided by the base
PFL software.  These include:
.IP \(bu
the arithmetic functions ((+), (-), (*), (/) (real division), (div) (integer
division), and (%) (modulus); 
.IP \(bu
the "cast" functions which map values of one primitive type to another (such
as decode and encode, which map numbers to characters and vice versa); 
.IP \(bu
the "error" function which shows a message and aborts computation;
.IP \(bu
the "strict" function which reduces an argument to normal form;
.IP \(bu
the "matches" function, (?=);
.IP \(bu
the graphics functions, to draw arcs, lines, points, etc on a graphics
window; and
.IP \(bu
the functions into which list abstractions are compiled ("flatmap", "foldr"
and "when").
.LP
A system defined ordering is supported over the constructors of each type,
which in turn induces an ordering over all constructed non-function types.
For numbers, characters and strings the ordering is the one you would
expect.  For lists, tuples and other constructed data types the ordering may
not be obvious:  all that is guaranteed is that any two values of a type can
be ordered with respect to one another, and that the ordering is
reproducible.  Thus, the system defined functions (=), (>), (<), (!=), (>=)
and (<=) are the relational functions over non-function types corresponding
to equality, greater than, less than, inequality, not greater than and not
less than respectively.  
.LP
New system defined functions can be added to the PFL interpreter.  For
example, the base PFL software does not provide system defined functions for
log, sin, etc.  To add a new system defined function to PFL the following
modifications must be made to the file "user/user.c":
.IP (i)
add the name of the function (fp, say) \fIas it should be parsed by PFL\fR
as the penultimate entry in the array "fun_names";
.IP (ii)
add an external declaration for the name of the C++ function (fc, say) which
implements fp;
.IP (iii)
add fc as the penultimate entry in the array "functions";
.IP (iv)
if fp takes n arguments, add the number n+1 as the penultimate entry in the
array "arguments";
.IP (v)
if the code for fc is stored in the file "fc.c" add an include statement of the form:
.RS
# include	"fc.c"
.RE
.IP
.SH 
4.	Equations
.LP
New equations for a function can be introduced using the "_define" command :
.RS
\fC_define \fRf\fC \fRp1\fC ... \fRpn\fC == \fRe\fC;\fR
.RE
where f is a variable, p1 to pn are patterns and e is an expression.  The
type of the function is inferred incrementally using the type declared by
the user (if any) together with the equations defining the function as they
are specified.  For example, the function "when" takes three arguments, and
returns the second (respectively, the third) if the first is the value True
(respectively, False) :
.Ds
\fC_function when == type0;
_define when True x y == x;
// the type of `when' is now `Bool->type0->type1->type0'
_define when False x y == y;
// the type of `when' is now `Bool->type0->type0->type0'\fR
.De
As a further example, the function "length" determines the length of a list :
.Ds
\fC_function length == type0;
_define length [] == 0;
// the type of `length' is now `[type0]->Num'
_define length (h:t) == 1 + (length t);\fR
.De
.LP
Higher order functions may be defined, viz. a function may take a function
as an argument or return a function as a result.  For example, the "fold"
function, which is defined as follows:
.Ds
\fC_define fold op end []		==	end;
_define fold op end (h:t)	==	op h (fold end t);
//	the type of `fold' is now `(type0->type1->type1)->type1->[type0]->type1'\fR
.De
has the property that fold f e [v1,...,vn] yields f v1 (f v2 (...(f vn
e)...)).  Thus fold abstracts out a particular recursion patterns over
lists, and can be used in the definition of other functions which use this
recursion pattern.  For example, fold can be used to find the sum or product
of a list; to form the logical "and" or logical "or" of a list of booleans;
to find the maximal element of a list; and so on:
.Ds
\fC_define sum			==	fold (+) 0;
_define product		==	fold (*) 1;
_define and			==	fold (&) True;
_define or			==	fold (#) False;
_define max (h:t)	==	fold greater h t;\fR
.De
.LP
Equations may also use list abstractions to enhance their clarity.  For
example, the following functions return (i) the factors of a given number;
and (ii) an infinite list of prime numbers:
.Ds
\fC_define factors n	==	[v | v <- [1..n]; n % v = 0];
_define primes		==	[n | n <- [1..]; factors n = [1,n]];\fR
.De
.sp 1
.B1
.LP
Note.  A list valued function, allT, is automatically defined for each
monomorphic first-order type T.  The list comprises all the 0-ary
constructors of type T in some (system-defined) order.  For example,
following the declarations of Sections 3.2 and 3.3 the functions
\fCallEmployee\fR and \fCallDepartment\fR yield the lists \fC[John]\fR and
\fC[Sales]\fR respectively.
.LP
.DE
.RE
.B2
.SH
5.	Selectors
.SH
5.1.	Declaration, update and associative retrieval
.LP
In Section 3.1 we noted that the value Any is a value of every type t.  The
purpose of Any is to allow partial matching of values, using the operator
(?=) (pronounced "matches").  When given values \fCp\fP and \fCv\fP, the
expression (\fCp\fP ?= \fCv\fP) yields either \fCTrue\fP or \fCFalse\fP
depending upon whether \fCp\fP is identical to \fCv\fP except for any
occurrences of \fCAny\fR in \fCv\fR.  More precisely, the semantics of (?=)
are as follows, where there is one equation of the form :
.Ds
\fC(?=) (C $x sub 1$ ... $x sub n$) (C $y sub 1$ ... $y sub n$)  ==  True & ($x sub 1$ ?= $y sub 1$) & ... & ($x sub n$ ?= $y sub n$);\fR
.De
for each n-ary constructor \fCC\fP, together with the "default" equation :
.Ds
\fC(?=) x y  ==  x = Any;\fR
.De
Thus, for example, \fC[1,Any,3] ?= [1,2,3]\fR and \fC[Any,2,Any] ?=
[1,2,3]\fR both yield \fCTrue\fR whilst \fC[1,2,3] ?= [1,Any,3]\fP yields
\fCFalse\fP.  A \fIselector\fR is a function which has the same semantics as
a pair of functions of the form
.Ds
\fC_define sel p  ==  [t | t \(<- $sel sub r$; p ?= t];
_define $sel sub r$  ==  [ ... ];\fR
.De
except that values can be added to and removed from the list $sel sub r$
(which we refer to as the relation of the selector) using the commands
"_include" and "_exclude" respectively.  A selector is declared by a
statement of the form :
.Ds
\fC_extsel |s == t;\fR
.De
where \fC|s\fP is a selector and \fCt\fP is a monomorphic first order type;
the type of \fC|s\fR is \fCt->[t]\fR.  Following its declaration the
selector is equivalent to the pair of equations :
.Ds
\fC_define sel p  ==  [t | t \(<- $sel sub r$; p ?= t];
_define $sel sub r$  ==  [];\fR
.De
The "_include" command takes a selector and a value \fCw\fR.
\fCw\fR is evaluated to normal form, say \fCw\(fm\fR.  If \fCw\(fm\fR is
already present in the relation of the selector then the relation remains
unaffected; otherwise the relation is modified by side-effect to include
\fCw\(fm\fR at some system-defined location.  Similarly, "_exclude" takes a
selector and value \fCp\fR; \fCp\fR is evaluated to normal form, say
\fCp\(fm\fR, and every value \fCv\fR of the relation of the selector such
that \fCp ?= v\fR is removed.
.LP
For example, an employee selector can be defined, updated and queried as
follows :
.Ds
\fC// declare an employee selector
--> _extsel |employee  ==  (Emp,Univ,(Num,Num,Num));
// the type of `|employee' is now 
//	`(Emp,Univ,(Num,Num,Num))->[(Emp,Univ,(Num,Num,Num))]'
// add new employees
--> _include |employee (Mir,Birkbeck,(01,10,1987));
	...
// Retrieve Birkbeck employees
--> |employee (Any,Birkbeck,Any);	
[ ..., (Mir,Birkbeck,(01,10,1987)), ... ]
// Mir has resigned
--> _exclude |employee (Mir,Birkbeck,(01,10,1987));
// Fire UCL employees
--> exclude |employee (Any,UCL,Any);\fR
.De
.SH
5.2.	Defining rules over selectors
.LP
Selectors provide PFL with an analogue to the facts of a logic database.  In
addition, functions can be defined over selectors which are the analogue of
the rules of a logic database.  For example, assume we have a selector
relating parents with their children:
.Ds
\fC_extsel |parent ==	(Str,Str);
_include |parent ("Elizabeth","Charles");
_include |parent ("Charles","Harry");
	...\fR
.De
Then functions can be defined over this selector to provide views of
functions relating grandparents with grandchildren and ancestors with their
descendants:
.Ds
\fC_define grandparent (x,z)	==
	[(x,z) |	(x,y) <- parent (x,Any); 
			(y,z) <- parent (y,z)];
_define ancestor (x,z)	==
	parent (x,z) ++ 
	[(x,z) |	(x,y) <- parent (x,Any);
			(y,z) <- ancestor (y,z)];\fR
.De
Note that these functions, like the selector over which they are defined,
are invertible in the sense that we can evaluate any of the following
queries:
.Ds
\fCancestor ("Elizabeth","Charles");	// is Elizabeth an ancestor of charles ?
ancestor ("Elizabeth",Any);		// who is Elizabeth an ancestor of ?
ancestor (Any,"Charles");		// who is an ancestor of charles ?
ancestor (Any,Any);				// who is an ancestor of whom ?\fR
.De
Note also that PFL can also simulate the negative literals of logic
languages.  Assume, for example, that "|mother" is a selector relating
mothers with their children; then we can define fathers to be parents who
are not mothers:
.Ds
\fC_define father (x,y)	== [(x,y) |	(x,y) <- |parent (x,y); |mother (x,y) = []];\fR
.De
.SH 
6.	Evaluation of Expressions
.LP
In contrast to functional programming languages, which compile functions
into executable code PFL stores equations in a repository.  When evaluating
an application of a function to its arguments, the application is replaced
by the right hand side of an equation selected from the equations in the
repository, after replacing any variables in the equation by the
corresponding arguments.  
.LP
In more detail, a query is an expression which is submitted for evaluation.
Queries are first passed to the typechecker for verification.  If a query is
type-incorrect it is rejected with type information detailing the reason for
its rejection; otherwise it is passed to the evaluator.  The evaluator
re-writes the expression using pre-defined and user-defined functions until
it is in weak-head normal form (WHNF) [Fie88].  An expression is in WHNF if
it is of the form ($fc sub n$ $e sub 1$ ... $e sub m$), where $fc sub n$ is
either a constructor and n \(>= m, or is a function and n > m.  If $fc sub
n$ is a constructor and n = m, then the constructor is printed and its
arguments are recursively evaluated; otherwise the expression is
higher-order, and an appropriate error message is printed.  The process of
reducing an expression to WHNF involves the repeated selection and
simplification of redexes (reducible expressions), where a redex is an
expression of the form ($f sub n$ $a sub 1$ ... $a sub n$), $f sub n$ being
an n-ary function.  A normal-order reduction strategy [Fie88] is used :
when there is a choice of redex, the left-most outer-most is selected.  When
reducing an redex one of three cases applies :
.LP
.UL "Case 1 :"
$f sub n$ is a pre-defined function.  The code for $f sub n$ is executed and
the redex is replaced by the result.  (Some of the $a sub i$'s may need
themselves to be reduced to WHNF before the code is executed).
.LP
.UL "Case 2 :"
$f sub n$ is a user-defined function.  The redex is replaced by the right
hand side of an equation, after replacing any variables in the equation by
the corresponding arguments.  The equations defining $f sub n$ are compared
with the arguments $a sub i$ from left to right in turn, and at each $a sub
i$ only those equations which match the argument are considered for $a sub
i+1$ (to determine whether an argument matches the corresponding pattern of
an equation may require the argument to be reduced to WFNF).  If no equation
matches the function application, evaluation of the query aborts with an
appropriate error message.  If several equations match the function
application the left-most most specific equation is selected.
.LP
.UL "Case 3 :"
$f sub n$ is a selector.  In this case the redex is of the form $f sub 1$ $a
sub 1$.  $a sub 1$ is evaluated to its normal form, say $a\(fm sub 1$, and
the redex is replaced with a list is formed of all elements \fCe\fP of the
relation of $f sub 1$ such that $a\(fm sub 1$ ?= \fCe\fR.
.LP
As a simple example of query evaluation, the function \fCnumbers\fP :
.Ds
\fC_define numbers n	==	n : (numbers (n-1));
// `numbers' now has type `Num\(->[Num]'
_define numbers 0	==	[];\fR
.De
.LP
takes a positive integer, \fCn\fP, and returns the list of numbers
\fC[n,n-1,n-2,...,1,n]\fR.  \fCnumbers 2\fR is evaluated as follows (where
the symbol "\(rh" denotes an intermediate step in a computation) :
.Ds
\fCnumbers 2
// only the first equation matches, and so it is selected
\(rh  2:(numbers (2-1))
// (2-1) is evaluated to allow selection of the appropriate equation
\(rh  2:(numbers 1)
// only the first equation matches, and so it is selected
\(rh  2:(1:(numbers (1-0)))
// (1-0) is evaluated to allow selection of the appropriate equation
\(rh  2:(1:(numbers 0)
// both equations match, but the second equation is most specific
\(rh  2:(1:[])\fR
.De
.SH
7.	The Command Processor
.LP
The evaluation of an expression (see Section 5) cannot result in a
modification of the database state, nor can it cause any interaction with
the operating system.  Nevertheless, there is clearly a requirement to be
able to write programs which transform the database state, and which read
from and write to files.  These requirements can be met in PFL by executing
a command of the form :
.Ds
\fC_command op;\fR
.De
where op is an expression of type Oper (operation).  The constructors of
type operation are shown in Table 2.
.KF
.TS
box expand tab(;);
l | l | l.
\fC\s-2Constructor;Type;Use;
_
_
OpenR;Str->(Num->Oper)->Oper;Input;
Get;((Num,Chr)->Oper)->Oper;Input;
Peek;((Num,Chr)->Oper)->Oper;Input;
CloseR;(Num->Oper)->Oper;Input;
_
OpenW;Str->(Num->Oper)->Oper;Output;
Put;Chr->(Num->Oper)->Oper;Output
CloseW;(Num->Oper)->Oper;Output;
_
Include;type0->type1->(Num->Oper)->Oper;Update;
Exclude;type0->type1->(Num->Oper)->Oper;Update;
Define;type0->type1->(Num->Oper)->Oper;Update;
Print;type0->(Num->Oper)->Oper;Display;
_
Commit;(Num->Oper)->Oper;Housekeeping;
Restore;(Num->Oper)->Oper;Housekeeping;
_
Done;Oper;General;\s+2\fR
_
.TE
.DS C
Table 2 :  Constructors of type Operation
.DE
.KE
.LP
A brief description of each operation follows.  Each operation (other than
Done) operates either upon the database or upon the operating system by
side-effect.  For each constructor other than Get and Peek, the argument con
is a continuation function of type (Num->Oper).  If the operation is
successful, the value of the operation is given by (con 1); otherwise it is
given by (con 0).
.LP
\fCOpenR f con;\fR
.RS
where f is a string giving the Unix path name of a file to be opened for
input.  An attempt is made to open f for input.
.RE
.LP
\fCGet con;\fR
.RS
Here con is a continuation function of type (Num,Chr)->Oper.  An attempt is
made to read a character from the current input file.  If the attempt is
successful the value of the operation is given by (con (1,c)), where c is the
character read; otherwise it is given by (con (0,'*')).
.RE
.LP
\fCPeek con;\fR
.RS
Here con is a continuation function of type (Num,Chr)->Oper.  The effect of
this operation is the same as for the Get operation, except that the
character is left on the input stream.
.RE
.LP
\fCCloseR con;\fR
.RS
An attempt is made to close the current input file.
.RE
.LP
\fCOpenW f con;\fR
.RS
Here f is a string giving the Unix path name of a file to be opened for
output.  An attempt is made to open f for output.
.RE
.LP
\fCPut ch con;\fR
.RS
Here ch is a character.  An attempt is made to write ch to the current
output file.
.RE
.LP
\fCCloseW con;\fR
.RS
An attempt is made to close the current output file.
.RE
.LP
\fCInclude sel val con\fR
.RS
where sel is a selector, val is a value to be included into the relation
associated with sel.  An attempt is made to add val to the relation of sel.
.RE
.LP
\fCExclude sel patt con\fR
.RS
where sel is a selector, val is a value to be included into the relation
associated with sel.  An attempt is made to remove every value v from the
relation of sel which matches patt.
.RE
.LP
\fCCommit con\fR
.RS
An attempt is made to commit the database state.
.RE
.LP
\fCRestore con\fR
.RS
An attempt is made to restore the database to its last committed state.  
.RE
.LP
\fCDone\fR
.RS
This operation has no effect upon the database state; it is simply used to
terminate the command.  
.RE
.LP
\fCPrint val con\fR
.RS
where val is a value of any type.  An attempt is made to evaluate and print val.
.RE
.LP
\fCDefine lhs rhs con\fR
.RS
An attempt is made to add the equation lhs = rhs to the database.
.RE
.sp 1
.LP
.UL "Examples."
First we define a function ("ok") which allows the result of a successful
operation to be ignored, but which will terminate immediately following an
unsuccessful operation :
.RS
.Ds
\fC_define ok c 1 ==	c;
_define ok c n ==	Done;\fR
.De
.RE
Examples which use this function follow :
.Ds
\fC--> _command Print (3/3) (ok (Print (3/1) (ok (Print (3/(-1)) (ok Done)))));
1
3
-3
--> _command Print (3/3) (ok (Print (3/0) (ok (Print (3/(-3)) (ok Done)))));
1
<< division by zero >>
--> \fR
.De
We can also define a function which executes an entire list of operations
(other than Get's and Peek's) regardless of whether those operations succeed
or fail :
.Ds
\fCupdate [] c 	==	c;
update (x:y) c 	==	x (ok (update y c));\fR
.De
As an example of the use of "update", assume that |employee is of type
(Emp,Dept)->[(Emp,Dept)], and that |salesman (of type Emp->[Emp]) is to be
set to contain only those employees working in the Sales department :
.Ds
\fC--> _command update	([Exclude |sales Any] ++
					 [Include |sales p | (p,Sales) <- |employee Any])
			Done;\fR
.De
.bp
.SH
Appendix 1.	Syntax of PFL
.LD
\s-1\fC<comm> ::=	<appl> ";"
|			"_typeof" <appl> ";"
|			"_command"  <appl> ";"
|			"_load" <token> ";"
|			"_system" <token> ";"
|			"_commit" ";"
|			"_restore" ";"
|			"_extsel" <token> "==" <type> ";"
|			"_exclude" <token> <appl> ";"
|			"_include" <token> <appl> ";"
|			"_function" <token> "==" <type> ";"
|			"_type" <token> "==" <type> ";"
|			"_value" <expr> "==" <type> ";"
|			"_define" <appl> "==" <appl> ";"
|			"_display" <token> ";"
|			";"

<appl> ::=	<expr>
|			<appl> <op> <appl>
|			"-" <appl>
|			<appl> <expr>

<expr> ::=	<token>
|			"(" <appl> ")"			//	bracketed expression
|			"(" <seq> ")"				//	n-tuple
|			"[" <seq> "]"				//	enumerated list
|			"[" "]"					//	empty list
|			"[" <appl> "]"			//	singleton list
|			"[" <appl> ".." "]"		//	dot-dot list
|			"[" <appl> ".." <appl> "]"	//	dot-dot list
|			"[" <appl> "|" <quals> "]"	//	list abstraction

<seq> ::=		<seq> "," <appl>  |  <appl>

<quals> ::=	<qual> ";" <quals>  |  <qual>

<qual> ::=	<appl>  |  <appl> "<-" <appl>

<type> ::=	<texp>  |  <type> "->" <type>

<texp> ::=	<token>  |  "(" <type> ")"

<token> ::=	<constructor>  |  <variable>

<op> ::=	"+"  |  "-"  |  "*"  |  "/"  |  "%"  |  ":"  |  "mod"\s+1\fR
.DE
.bp
.SH
Appendix 2.	The demonstrator
.LD
\fC\s-1
//	PFL Demonstration Script
//	------------------------
//
//
//	Introduction of new types
//	-------------------------
//
//	Witness is a type; and for all types t, Tree t is a type:
//
_type	Witness		==	Type;
_type	Tree			==	type0->Type;
//
//
//	Introduction of new values
//	--------------------------
//
//	JohnDoe and RichardRoe are values of type witness; Leaf is of type Tree t 
//	for all types t; and Node a v b is of type Tree t whenever v is of type t 
//	and both a and b are of type Tree t:
//
_value	JohnDoe		==	Witness;
_value	RichardRoe	==	Witness;
_value	Leaf			==	Tree type0;
_value	Node			==	(Tree type0)->type0->(Tree type0)->(Tree type0);
//
//	For every monomorphic, first-order type T the function allT returns all of
//	the 0-ary constructors of type T:
//
allWitness;
//
//	The type of any expression can be determined:
//
_typeof JohnDoe;				//	The type of a value constructor
_typeof Node Leaf 50 Leaf;		//	The type of a structured value
_typeof Witness;				//	The type of a type constructor
_typeof allWitness;			//	The type of a function

//
//	Introduction of new selectors
//	-----------------------------
//
//	A selector is a function which embodies a relation.  The relation expands
//	and contracts following the inclusion of exclusion of tuples.  The selector
//	is declared and populated using the "_extsel" and "_include" commands:
//
_extsel  |employee == (Str,Num,Str);		// (Name,Age,Boss)
_include |employee ("John",25,"Mary");
_include |employee ("Jill",25,"Mary");
_include |employee ("Jack",52,"Mary");
_include |employee ("Toby",40,"Fred");
_include |employee ("Roger",41,"Fred");
_include |employee ("Bill",42,"Fred");
_include |employee ("Mary",37,"Brian");
_include |employee ("Fred",39,"Brian");
_include |employee ("Tony",21,"Brian");
_include |employee ("Brian",19,"Angela");
_include |employee ("Mark",22,"Angela");
_include |employee ("Jane",22,"Angela");
//
//	A selector is a function which takes a pattern as an argument and returns all
//	tuples of the relation which match the pattern.  Selectors are "invertible"
//	in that they can be queried with any subset of the arguments known, and
//	correspond to the facts or EDB of a logic database:
//
|employee (Any,Any,"Brian");
|employee (Any,25,"Mary");
//
//	Tuples are removed from the relation using the "_exclude" command (if you
//	delete these facts, put them back in again since we need them later in the
//	demonstration):
//
_exclude |employee (Any,Any,"Angela");
_exclude |employee (Any,25,Any);
//
//
//	Introduction of new functions
//	-----------------------------
//
//	The types of functions are automatically inferred as the equations are entered:
//
_define	freezing_point	==	32;
_define factorial 0		==	1;
_define factorial x		==	x * factorial (x-1);
//
freezing_point;
factorial 5;
//
//	Functions can be defined over selectors which are equivalent to the rules or IDB
//	of a logic database:
//
_define	hierarchy (emp,boss)	==
	[(emp,boss) |	(emp,age,boss) <- |employee (emp,Any,boss)] ++
	[(emp,boss) |	(emp,age,int)  <- |employee (emp,Any,Any);
				(int,boss) <- hierarchy (int,boss)];
//
hierarchy ("John",Any);
hierarchy (Any,"Angela");
hierarchy (Any,Any);
//
//	The list type is defined in "common.env", and hence we can also define functions
//	over lists (note that there are much better ways of determining the length, sum 
//	and average of a list (see "common.env")):
//
_define len_list []	==	0;
_define len_list (h:t)	==	1 + (len_list t);
_define sum_list []	==	0;
_define sum_list (h:t)	==	h + (sum_list t);
_define avg_list x		==	(sum_list x) / (len_list x);
//
//	Lazy evaluation allows manipulation of infinite data structures.
//	You will need to interrupt (Control & C) the evaluation of nats 0:
//
_define nats n		==	n:(nats (n+1));
//
//	DotDot notation is a shorthand way of denoting lists of numbers.  Try out:
//	
[0..100];
[0..];
//
//	ZF expressions (or list abstractions) are a powerful querying mechanism:
//	
[x | x <- [0..]; x % 2 = 0];
[x | x <- [1..]; [y | y <- [2..x div 2]; x % y = 0] = []];
//
//	Strong, static type checking allows early detection of erroneous queries and 
//	function definitions.  Try out:
//
nats '0';
//
//	Higher order functions allow recursion patterns to be abstracted out.  For 
//	example the function fold (given below) thas the property that
//		fold op end [v1,...vn]" => op v1 (op v2 ( ... (op vn end) ...) )
//	and hence it can be used to avoid explicit use of recursion in other functions
//	such as sum, product, max, min, etc.  (The suffix "2" is added to the name of 
//	each function since these are already defined in "common.env").
//
//
_define	fold op end []	==	end;
_define fold op end (h:t)	==	op h (fold op end t);
_define sum2 (h:t)			==	fold (+) h t;
_define prod2 (h:t)		==	fold (*) h t;
_define max2 (h:t)			==	fold greater2 h t;
_define min2 (h:t)			==	fold lesser2 h t;
_define greater2 x y		==	when (x > y) x y;
_define lesser2 x y		==	when (x < y) x y;\fR\s+1
.DE
.bp
.SH
References
.LP
[Bir88] R. Bird and P. Wadler, Introduction to Functional Programming,
\fIPrentice-Hall International\fR, 1988.
.LP
[Hug89] J. Hughes, Why functional programming matters, \fIThe Computer
Journal\fR, 32(2), 1989.
.LP
[Pou91] A. Poulovassilis and C. Small, A functional programming approach to
deductive databases, \fIProceedings of the 17th International Conference on
Very Large Databases\fR, 1991.
.LP
[Pou93] A. Poulovassilis and C. Small, A domain-theoretic approach to
extending a functional database language with sets, \fIProceedings of the
19th International Conference on Very Large Databases\fR, 1993.
.LP
[Red93] S. Reddi, Integrity constraint enforcement in the functional
database language PFL, \fI11th British National Conference on Datbases\fR,
1993.
.LP
[Sma91] C. Small and A. Poulovassilis, An overview of PFL, \fI3rd
International Workshop on Database Programming Languages\fR, 1991.
.LP
[Sma92] C. Small, A functional approach to database updates, submitted for
publication.
.LP
[Tur85] D.A. Turner, Miranda: A non-strict functional language with
polymorphic types, \fIFunctional Programming Languages and Computer
Architecture\fR, Springer-Verlag LNCS 201, 1985.
