P.F.Meredith and P.J.H King

{P.F.Meredith@btinternet.com, pjhk@dcs.bbk.ac.uk}

An inherent conflict arises with functional languages in the database context between change of state on update and the concept of referential transparency. Passing the database itself as a parameter resolves the issue conceptually but is not a practical approach. Update by side-effect is efficient but necessarily implies loss of referential transparency. Additionally side-effects are often incompatible with lazy evaluation since the occurrence and sequence of updates can become non-intuitive. Our approach is to accept that a change of database state will result in loss of global referential transparency but that referential transparency can be scoped so that areas of a program can be identified which retain the property. Equational reasoning and consequent optimisation can then be applied within these scopes.

We describe a variant of the functional database language FDL [Pou88, PK90], called Relief, which is lazy and which has been extended with functions to facilitate updates and reading of files. These functions work by means of side-effects which are explicitly sequenced with an eager let expression and a derivative sequencing construct. There is no change in the overall laziness of the graph reduction which we illustrate with an example update program which employs the lazy stream model. To redress the loss of global referential transparency an effects checker identifies referentially transparent regions or scopes.

The development of Relief is a contribution to the work of the Tristarp Group, initiated in 1984 to investigate the feasibility of a database management system which supports the binary relational model both at the storage and conceptual levels. A summary of the early work is given by King et al. [KDPS90]. More recently research has focused on supporting the entity-function model, a hybrid of the binary relational and functional data models [Shi81, AK94]. The relationships between entities are binary and are represented by (possibly) multivalued single argument functions. Entity types are classified into lexical and non-lexical as with the analysis methodology NIAM [VV82]. Members of lexical types have direct representation (for example the types string and integer) whereas those of non-lexical types are real or abstract objects without direct representation eg. persons, invoices, courses etc.

Fig. 1. The Computer Literature Database (CLDB)

Figure 1 is a subschema of the Computer Literature Database (CLDB), a body of data used experimentally by the Tristarp Group, and illustrates the entity-function model. Non-lexical types are shown as circles with functions represented by arcs. A single-headed arrow represents a single-valued function and a double-headed one denotes a multivalued function. Thus a Paper has a single Abstract but is by (possibly) several Authors. In this example, the lexical type "string" is used extensively in the ranges of the functions.

Relief is an experimental variant of FDL [Pou88, PK90], the first language to integrate the entity-function model with the functional computation model over a binary relational storage structure. FDL has the usual features of a modern functional programming language such as polymorphic types, lazy evaluation and pattern-matching and we refer the reader to Field and Harrison [FH88] for an explanation of these. We describe here only the features of Relief which illustrate the scoping of referential transparency. A full syntax and description of the language and its implementation is given by Meredith [Mer98]. The persistent functions and entities which constitute a database in Relief are held in a triple store, a development of the grid file [NHS84, Der89] which has recently been adapted to hold long strings and to support interval queries.

CLDB contains the non-lexical types paper and author amongst others. This part of the schema is implemented in Relief with the following type declarations:

paper :: nonlex;

author :: nonlex;

by : paper -> [author];

title : paper -> string;

surname : author -> string:

initials : author -> string;

In order to facilitate easy navigation of the schema Relief automatically maintains a converse function for all functions whose domain is a non-lexical type, referred to by the prefix rev. For example the converses of the functions surname and by are:

rev_surname : string -> [author];

rev_by : author -> [ paper ];

As an example of their use consider the following list comprehension query which retrieves the papers by authors with the surname "Meredith".

[ title p | for a in rev_surname "Meredith";

for p in rev_by a] ;

It is interesting to note here the syntactic similarity between Relief and the "FOR EACH" statement in DAPLEX [Shi81].

The extent of a database is defined and can be redefined by means of the functions create, destroy, define and delete. The function create takes a non-lexical type as an argument and returns a new entity of the specified type. For instance:

create author;

The function destroy destroys an entity of the specified non-lexical type. Thus to destroy the first element in the list of all authors:

destroy author (head (All author));

In the functional model it is necessary for every expression to have a value and thus destroy returns the value Done which is the only value in the type update. Functions are incrementally defined using the function def which adds an equation to the database and returns the value Done. To illustrate this, we give an expression which creates an author entity, binds it to a scoped static variable "a" and then defines an equation for their initials. The binding is done with an eager form of the let expression which is further explained in the next section. Thus:

e_let a = create author in (def initials a => "PF");

The left hand side of a function equation consists of the name of the function followed by one or more arguments, and the right hand side is an expression which is stored unevaluated. The arguments at definition time can either be patterns or a bound variable such as "a", in which case the value of the variable is used in the definition of the equation. The value of a function’s application defaults to the constant "@" (denoting "undefined") if there is no equation which matches the function’s arguments. The pattern-matching in Relief uses the left-to-right best-fit algorithm developed by Poulovasillis [Pou92].

The delete function del deletes an equation from the database and returns the value Done. The arguments of del identify the left hand side of the function equation for deletion, for example:

e_let a = head(rev_surname "King") in (del initials a);

deletes the equation defining the initials of an author with the surname "King".

All four update functions are statically type checked, see Meredith [Mer98] for details, and work at the object level. Thus their invocation needs to be sequenced and we discuss this next.

A new construct, the eager let (e_let), is introduced to sequence updates by employing call-by-value parameter substitution but within a general scheme of lazy evaluation. We illustrate the eager let expression with the following example which evaluates an expression before using it as the value of the right hand side in an equation definition. The example assumes that people have a unique name and the types of the functions name and salary are:

name : person -> string;

salary : person -> integer;

The expression below defines the salary of Bill to be 5000 more than Fred’s current salary.

e_let bill = head(rev_name "Bill") in

e_let fred = head(rev_name "Fred") in

(def salary bill => bills_salary );

Thus the value of Bill’s salary is stored as an integer and not a formula and so a subsequent change to Fred’s salary will not result in a change to Bill’s salary. The next example produces a sequence of updates to create an author entity and define surname and initials before returning the new entity. Two dummy variables, dum1 and dum2, are used to bind with the values returned by calls to the define function.

e_let a = create author in

e_let dum1 = (def surname a => "Meredith") in

e_let dum2 = (def initials a => "PF")in a;

The overall evaluation scheme is still normal order reduction, the outermost let being reduced before the innermost let and the body of each eager let being evaluated lazily. The syntax of the eager let is not ideal because of the need to specify binding patterns which are of no further interest. Hence we have provided an explicit sequencing construct in Relief which, although formally only syntactic sugar for the eager let, is much more succinct and convenient for programming. This construct is written as a list of expressions separated by semicolons, enclosed in curly brackets, and is optionally terminated by the keyword puis and a following expression which gives a functional value for the entire sequence. The expressions between the brackets are evaluated in their order, from left to right. For example, the expression above can be written as the sequence:

{ a = create author; (def surname a=>"Meredith");

(def initials a => "PF") } puis a;

We refer to the keyword puis and its following expression as the continuation. If it is omitted then a default value of Done is inferred for the sequence.

We describe here a Relief program which processes a list of data constructors representing the records in a file "Tristarp_papers" and updates that part of the CLDB concerning authors and papers. Relief contains a read_file function which can lazily convert a file of records into such a list but space precludes a full description here. The elements of the list are members of the paper_record sum type which is defined by the two constructors TITLE_REC and AUTHOR_REC. TITLE_REC has a single string component, whereas AUTHOR_REC has two components: one for the surname of the author and one for the initials:

paper_record :: sum;

TITLE_REC : string -> paper_record;

AUTHOR_REC : string string -> paper_record;

Our example will assume the following list of records as input:

The program to process the list consists of two functions: cldbup which creates the paper entities, and add_authors, which creates the author entities and links them to the papers. Both functions operate recursively and process records at the head of an input list before returning the remainder of the list. For a list with a title record at its head, cldbup creates a paper, defines its title and calls add_authors as specified by the first equation below. If the head of the list is not a title record then the list is returned unaltered as given by the second equation. This is an appropriate action when an unexpected or unrecognised record is encountered. The third equation specifies that cldbup returns the empty list when given the empty list. Thus cldbup will return the empty list if all of the records in the file can be processed, otherwise it returns some remainder of the input list.

cldbup : [paper_record] -> [paper_record];

def cldbup ((TITLE_REC t) : xs) => {

p = create paper;

(def title p => t)

} puis cldbup (add_authors p xs);

def cldbup (h : t) => (h : t);

def cldbup [ ] => [ ];

The function add_authors recursively processes all the author records at the front of the list before returning the remainder of the list. The logic for processing a single author record is:

• construct a list of authors with the specified surname and initials
• if the list is empty create a new author, define their surname and initials, and bind them to the pattern "a" else bind the pattern to the head of the list of authors
• if the list of authors for the specified paper is currently undefined, then define a list with the author "a" as its single member. Otherwise add the author "a" to the existing list.

add_authors : paper [paper_record] -> [paper_record];

def add_authors p ((AUTHOR_REC s i) : xs) => {

auth_list = [ a1 | for a1 in rev_surname s;

a = if auth_list == [ ] then

{a2 = create author;(def surname a2 => s);

(def initials a2 => i) } puis a2

else head auth_list fi;

e_let authors = by p in

if authors == @ then (def by p => [a])

else e_let new_authors = append authors [a]

in (def by p => new_authors)

fi

} puis add_authors p xs;

def add_authors p (h : t) => (h : t);

def add_authors p [ ] =>[ ];

The file of papers is then processed lazily by evaluating the following expression:

cldbup (read_file paper_record "Tristarp_papers");

A defining property of languages which are purely functional is said to be referential transparency [Hud89]. It is this property which allows functional languages to be declarative rather than imperative in nature. Put simply, referential transparency means that every instance of a particular variable has the same value within its scope of definition. This is the interpretation of variables in algebra and logic which allows the use of equational reasoning.

Although Relief is not a pure functional language it is possible to identify regions of referential transparency where the techniques used in functional programming, and by functional compilers, can still be applied. This follows from the fact that the concept of referential transparency is scoped by definition. In a purely functional language the scope is the environment or script in which an expression is evaluated. Referential transparency in Relief is scoped by the update operations which destroy reference. These regions of referential transparency can be statically identified by means of an effects checker which classifies the effect of an expression. Furthermore an effects checker is of use in concurrent systems since it identifies potential interference between expressions.

Effects checking was first described by Gifford and Lucassen [GL86] in connection with their research into the integration of imperative and functional languages. Gifford and Lucassen identify the following three kinds of effects of expressions:

• A – allocation and initialisation of mutable storage, for example the declaration of a variable or collection.
• R – reading a value from mutable storage.
• W – writing to mutable storage, that is assignment.

There are eight possible combinations of these three effects which form a lattice under the subset relation. These eight different combinations can be grouped into effect classes depending on the language requirement. Gifford and Lucassen were interested in identifying those parts of a program which could be memoised and were amenable to concurrent evaluation. Hence they produced an effect checking system which classified expressions into one of the following four effect classes:

There is a total ordering of these effect classes in the sense that they form a hierarchy of effect properties. The effect properties of the four classes can be summarised as:

• PROCEDURE – expressions of this sublanguage can define variables, read mutable storage and write mutable values.
• OBSERVER – expressions of this sublanguage can define variables and read variables. They cannot perform assignments and cannot make use of expressions with the effect class PROCEDURE.
• FUNCTION – expressions of this sublanguage can define variables but they cannot read variables or change their value. FUNCTION expressions cannot make use of PROCEDURE or OBSERVER expressions.
• PURE – a pure function has no effects and cannot be affected by the evaluation of other expressions. It can neither define variables, nor read, nor write them. A PURE expression cannot make use of PROCEDURE, OBSERVER or FUNCTION expressions.

The only expressions which can interfere with concurrency are those in the effect class PROCEDURE and these can only interfere with other expressions in the PROCEDURE and OBSERVER effect classes. Thus the ability to identify expressions of these classes would be important in order to maximise concurrency in a multi-user system. In contrast PURE, FUNCTION and OBSERVER expressions do not interfere with each other and can be run concurrently. PURE expressions can be memoised and OBSERVER expressions can be memoised between updates. We now look at how effects checking is applied in Relief.

We begin by classifying the effect properties of constructs in Relief. Relief has no updateable variables in the usual sense but it does have extensible and updateable types, namely user-defined functions and non-lexical entities. Thus the Gifford and Lucassen concept of the allocation of mutable storage is equivalent to the declaration of such types. With regard to the initialisation of storage, a function declared in Relief has a default definition so that initially its application gives only the undefined value. The extent of a non-lexical type, accessed by the All metafunction, is initially the empty set. Type declarations however are commands and are not referentially transparent because they alter the database schema. Since they contain no subexpressions and cannot appear as subexpressions they are omitted from the effects checking.

With regard to updates, user-defined functions are updated by the def and del functions which define and delete equations in the definition of a function. The extents of non-lexical types are altered by the create and destroy functions. An expression which directly or indirectly calls any of these four functions has the (W) property. An expression which directly or indirectly applies a user-defined function or examines the extent of a non-lexical type has a value which is dependent on the state of the system. Such an expression has the (R) property. Since no expressions in Relief can have the (A) property it is sufficient to classify them as belonging to one of the following three effect classes:

Because Relief is a single-user sequential system we can say that an expression is referentially transparent if it makes no change to mutable storage under any condition. Thus an expression with the effect class OBSERVER or PURE is referentially transparent and has a value which is independent of the evaluation order of its subexpressions. The operational semantics of Relief allows the static scoping of referential transparency. Thus we arrive at the definition for the scope of referential transparency for an expression in Relief:

"The scope of an expression’s referential transparency in Relief is the maximal enclosing expression which has no (W) effects."

In a multi-user system, PURE and OBSERVER expressions can still be treated as referentially transparent if there is a locking mechanism to prevent expressions with effect class PROCEDURE from changing the function and entity types on which they depend.

Our approach differs from that of Gifford and Lucassen in that we regard the effect class of an expression as a property orthogonal to its type. We regard their approach of annotating each function type with its effect class as unnecessarily complex and giving no practical benefit. In our implementation an expression’s effect class is inferred from its subexpressions in tandem with its type. Thus whilst performed in parallel effects checking and type checking are conceptually independent.

In Relief the programmer declares the effect class of a function from the outset and the compiler ensures that the declaration is not violated. The effect class of a user-defined function must be either PROCEDURE or OBSERVER since it is an observer of its own mutable definition and hence possesses the (R) property. A user-defined function defaults to the effect class of OBSERVER, whereas an effect class of PROCEDURE is specified by preceding the function name with "proc". The following examples illustrate this. Firstly declaring a PROCEDURE whose application conditionally creates an author and defines their surname and initials:

proc create_author : string string -> update;

then { a = create author; (def surname a => sur);

(def initials a => init) }

Secondly declaring an OBSERVER function which is dependent on other functions. This example defines a person’s salary as the sum of their basic pay and their bonus.

salary : person -> integer;

def salary x => basic x + bonus x;

Finally declaring an OBSERVER function which is only dependent on its own definition. This example extracts the second component of a tuple.

sec_comp : (alpha1 ** alpha2) -> alpha2;

def sec_comp (x,y) => y;

The effects checker ensures that the declarations are not violated by checking that the effect class of each defining equation is less than or equal to the declared effect class of the function. The inference rules used in the effects checker are given by the pseudocode below. The effect class of a pattern is PURE and since this is the least value it can be ignored where some other expression is present.

The fundamental inference rule is the one for application. The effect class of an application is the maximum of the effect class of the function and the effect class of its argument. This means that effect inference is pessimistic since it assumes that if an expression contains a side-effect then that side-effect will take place. This is of course not necessarily true with lazy evaluation. We now give the algorithm for the function effect_chk which infers the effect class of an expression. The declared effect class of a user-defined function is retrieved by calling the function dec_effect. Thus the value of "dec_effect(create_author)" is PROCEDURE assuming the declaration of create_author above.

effect_chk(E) // effects checker

{

switch(E)

case (E₁ E₂) // application

case ( e_let p = E₂ in E₁ ) //eager let expression

case ( l_let p = E₂ in E₁ ) //lazy let expression

case (\p. E) // lambda abstraction

case Qual //Qualifier in a list comprehension

case VAR v // a bound formal parameter, not

case NONLEX n // a nonlexical entity

case CONFUN c // a data constructor

case ETYPE // a type as a parameter

case constant c // eg integer or string

case FUN f // a persistent function

case INFUN f // a built-in function

switch(f)

case create t

case destroy t

return(PROCEDURE)

OTHERWISE

return(PURE)

This algorithm can be modified to prohibit subexpressions with the effect class PROCEDURE from parts of the language. We suggest that this restriction might be applied to list comprehension qualifiers so that optimisations such as those published by Trinder [Tri91] can be automatically performed.

Ghelli et al. [GOPT92] have proposed an extension to list comprehension notation which provides update facilities for an object-oriented database language. The extension is achieved by adding a do qualifier which can perform actions on objects identified by earlier bindings in the list comprehension. They show that known optimisation techniques can be modified to operate in the presence of do qualifiers. Their technique however relies on the programmer restricting the use of side-effecting expressions to do qualifiers, there being no compile-time checking.

We briefly discuss three other approaches which promise efficient, functionally pure database update: linear types, monads and mutable abstract data types (MADTs). They are all efficient since they can guarantee a single-threaded store so that updates can be done in-place.

A linear object is an unshared unaliased singly-referenced object and thus linear objects have the property that there is only one access path to them at any given time. A linear variable is a 'use-once' variable which can only be bound to a linear object and must be dynamically referenced exactly once within its scope. Linear type checking systems have been designed which can statically check that linear variables are neither duplicated nor discarded. These systems have a theoretical foundation in linear logic whence they derive their name.

The motivation for having linear types in functional languages is to capture the notion of a resource that cannot or should not be shared, hence the linear variable. A linear type system does however allow for the explicit creation, copying and destruction of linear objects. Whenever a program creates a linear object it must also be responsible for its destruction. One advantage of this is that there is no need for garbage collection in a purely linear language. For functional programmers linear types offer a way, amongst other things, of guaranteeing safe in-place updates since a linear object can have only a single reference.

Purely linear languages however are very restrictive since functions must always pass-on their linear arguments, explicitly destroy them or return them even when they are not changed. The programs in these languages tend to be somewhat difficult to read due to their heavy use of multiple returned values. Another problem with languages which support linear types is that they must also deal with nonlinear, i.e. shared, objects. This requires them to have a dual type checking system whereby most of the type inference rules have linear and nonlinear counterparts. The programmer must be aware of the distinction between linear and nonlinear values.

In the database context we want to treat database objects as linear when updating them but also to treat the same objects as shared when querying. However an object cannot be both linear and nonlinear at the same time. An interesting application of linear types to functional databases has been implemented by Sutton and Small [SS95] in their further development of PFL, a functional database language which uses a form of relation, called a selector, as its bulk data type. In the first version of PFL the incremental update of relations was achieved by means of the side-effecting functions include and exclude. A linear type checking system was introduced into PFL later on by changing these functions so that they took a linear relation name as an argument and returned the same relation name as a result. The type checking system worked by preventing the duplication or discarding of these relation names. Sutton and Small give examples of strict updating functions which show that the language is still update-complete within the constraints of this type checking. In order to reduce the number of parameters returned when querying they also allow a relation to be referred to by a nonlinear name. However a relation’s linear name and nonlinear name cannot both appear within the same expression.

In-place update can also be guaranteed by wrapping up the state in a higher-order type which is accessed only by functions with the single-threaded property. The functions must support the creation, access and updating of the state within the type. Wadler has shown how monads can be used for this purpose [Wad95]. Monads, a category-theoretic notion, are defined by a triple: the type constructor M, and the operations unit and bind. Monadic programming is an implicit environment based approach to programming actions such as updating state and input/output. Actions on the environment have a special type which indicates what happens when the action is performed. The programmer composes actions with the two combinators unit and bind.

The monadic approach to handling state has both advantages and disadvantages when compared with the use of linear types. Its chief advantage is that it does not require a special type system beyond the usual Hindley-Milner one. Also because monads handle state implicitly it is argued that this can make an underlying algorithm more apparent since there is less parameter passing. Their main disadvantage is that they require a centralised definition of state. Although this restriction might initially appear to fit nicely with the use of a single conceptual data model in databases, in practice however this lack of granularity would have performance and concurrency implications. A treatment of multiple stores with different types, such as relations in a relational database, requires the definition of many monads and monad morphisms in order to support operations involving the different types. It may also be that for databases a two state monad is more appropriate in order to represent the current state and the state at the start of the transaction. This could then support the rollback operation. We consider these to be areas for further research.

Monads can also be defined in terms of unit, map and join operations which are a generalisation of the same operations which give the semantics of list comprehensions. Wadler has shown how the list comprehension notation can also be used to manipulate state monads [Wad90], each qualifier becoming an action on the state. The resulting programs however look very procedural.

Monads in themselves do not enforce linearity on the encapsulated state, their operations must be carefully designed in order to ensure this. The use of abstract data types which encapsulate state and linear access to it has been investigated by Hudak [CH97]. A mutable abstract datatype or MADT is any ADT whose rewrite semantics permit "destructive re-use" of one or more of its arguments while still retaining confluence in a general rewrite system. A MADT is an ADT whose axiomatisation possesses certain linearity properties. Hudak shows how a number of MADTs can be automatically derived from such an ADT. Using an array as an example Hudak gives three ways of defining an appropriate MADT. These correspond to direct-style semantics, continuation passing style (CPS) and monadic semantics. A MADT is defined in terms of functions which generate, mutate and select state of a simple type.

Not only is the state hidden in a MADT but the linearity is too and so there is no need for the programs using MADTs to have a linear type system. It has been noted that programming in MADTs tends towards a continuation passing style no matter which form of MADT is used. MADTs are excellent at handling simple state but further research is required into handling bulk data types efficiently and into combining MADTs. Unlike monads there is no rigorous way of reasoning with a number of MADTs.

Whilst there is much promising research into handling state within functional languages the update problem in functional databases such as FDL remains problemmatical because the database is comprised of function definitions which must be both simple to apply and simple to update. The design of an uncomplicated integrated language to handle both queries and updates in an efficient purely functional manner is difficult. Whilst linear types could have been used it is our view that the result would have been less satisfactory and less programmer-friendly than the approach we have taken. The introduction of the four update functions described in section 4, whilst not functionally pure, has kept the language strongly data-model oriented. Also none of the approaches outlined in the section on related work have been used to address transaction handling which is a fundamental distinction between database programming and persistent programming. In contrast Relief does have a programmable transaction handling mechanism although this is not described here. (See [Mer98] for details of this).

Relief demonstrates that a functional interpreter based on graph reduction can be used to perform updates and that effects checking can scope referential transparency so that the usual functional optimisations can be used for queries and read-only subexpressions. The approach taken has allowed the benefits of lazy evaluation and static type checking to be retained. Updates are performed efficiently and the programmer does not have to learn a new type system. Whilst the eager let helps to make the sequencing of updates more explicit it is still necessary to understand the operational semantics of the pattern matcher when function arguments contain side-effects. Applicative order reduction would simplify these semantics but the lazy stream model used for file reading and the other advantages of lazy evaluation would be lost. Update by side-effect and effects checking are applicable to database systems supporting other data models.

Further work will centre on integrating Relief with the data model of Hydra [AK94] which distinguishes between navigable functions and non-navigable functions in a functional database. This may require the definition of further effect classes.

Acknowledgements: We would like to thank the referees and Alex Poulovassilis for their comments during the preparation of this paper. The first author was supported by the EPSRC and IBM UK Labs Hursley during this work.