Elisa: Programming by Definitions  News

 Data Structures 1. Multi-value Functions 2. Lists and Streams 3. Descriptors 4. Trees

A Fundamental approach to Multi-value Functions

Tutorial 1: Functions with Multiple results

Jan Klunder

Summary

 Contents   1.  Introduction   2.  Multi-value Functions   3.  Multi-value Expressions          3.1  Serial Expressions        3.2  Range Expressions        3.3  Compound Expressions        3.4  Empty Streams   4.  Multi-value Definitions  5. Example: Parental Relations

# Introduction

To illustrate the impact of multiple value expressions we will use Elisa. Elisa is an experimental language. It started as an effort to combine the paradigms of procedural programming, functional programming, object-oriented programming and logic programming into one coherent linguistic framework. During this integration process it turned out that a complete integration of different paradigms is not possible. Mainly because of conflicting requirements. For example, assignment statements are essential in procedural and object-oriented paradigms, but are forbidden in the functional paradigm. As a consequence we dropped the requirement of complete integration and decided to design a new language based on the best and well-established features of different paradigms. The result is a language not hindered by compatibility requirements but a language that uses the best available concepts. One of the offsprings of this effort is the use of multi-value functions.

In this paper we will discuss how multi-value functions can simplify programs in various ways as is illustrated by a number of example programs. All example programs have been verified by the Elisa development system.

# Multi-value Functions

In the following, we will describe how the programming language Elisa handles multiple answers and what the consequences are for the language design. We start with a simple function. We know how a normal function is written. For example, the function:

f(x) = 2 * x;

has one input value and one output value. In this example, the value of the output value is two times the input value. Or in other words: one question to the f function delivers one answer.

The next step is to define functions that may generate multiple answers, like

f(x) = (x + 7, 2 * -x, x ** 3);

In this case, one question such as f ( 5) ? will return 3 answers: 12, -10, 125. In addition, the system requires extra information in order to  select the proper computer instructions. This information is included in a so-called signature and must precede the function definition. For our example it means:

f(integer) -> multi(integer);

The signature tells the system that the input of the function will be an integer value and that the output consists of multiple integer values. Based on this information a dialogue with the system has the following elements:

f(integer) -> multi(integer);         << signature >>

f(x) = ( x + 7, 2 * -x, x ** 3);      << function  >>

f(5)?                                 << question >>

This is an example of one question with three answers.

The text between << and >> is comment. The ? question mark requests the system to evaluate the preceding expression. To present results in this paper we will often use a different notation and combine the question and the answers on one line:

f(5)?     ==> ( 12, -10, 125)

The ==> notation is not part of the language. It points to a stream of resulting values representing the output of the expression.

# Multi-value Expressions

However, defining multi-value functions is one part of the job. The other part is to explain how multi-value functions are used and what its consequences are. For example, what may we expect if we use the following multi-value expression        3 * f(5)?  Or, more complicated,  f(5) * f(7)?.  We need to define the meanings of the combinations of single-value and multi-value expressions. The introduction of multi-value functions not only has it consequences for functions but also has it impact on other language elements. Therefore we will describe a number of single- and multi-value expressions.

To keep it simple we will not use a formal treatment but use examples to clarify several constructs. We start with a description of two basic constructs that are introduced in Elisa to be used in multi-value expressions. They are called serial expressions and range expressions.

## Serial Expressions

The first basic construct consists of a series of expressions, separated by comma’s and enclosed in parentheses:

( expr1, expr2, expr3 ... )

Here are some examples:

( 5, 12 * 3 - 11, 13)?               ==>  (5, 25, 13)

( 3.5, 2.7 + 3.5, - 5.6)?            ==>  (3.5, 6.2, - 5.6)

( "John", "Mary")?                   ==>  ("John, "Mary")

All elements of a serial-expression must be of the same type. The execution of a serial-expression results in a corresponding stream of data items. A serial-expression may also contain other serial-expressions. For example:

is equivalent to:

( 2, 9, 7, 4, 5, 6, 3, 8)

## Range Expressions

The second basic construct is the range-expression. A range-expression is only defined for integer values and represents a stream of successive integer values. For example 3 .. 7 is a multi-value expression for (3, 4, 5, 6, 7). In general,  m  ..  n represents the multi-value expression:

( m,  m + 1,  m + 2, ... n)

With this construct the number of integer values may be variable depending on the actual values of m and n. Three interesting situations can be distinguished depending on these values:

if  m < n  the expression represents n - m + 1 values

if  m = n  the expression represents only one value

if  m > n  the expression represents no value

The two basic constructs may be combined. For example:

(2 .. 5, 5 .. 3, 2 * (1..3))?    ==>   ( 2, 3, 4, 5, 2, 4. 6)

## Compound Expressions

In general, operations on expressions representing multiple data items are straightforward extensions of operations on single data items. Here are some examples:

2 - ( 3, 4, 5)?    ==>    (-1, -2, -3)

( 3, 4, 5) – 2?    ==>    ( 1, 2, 3)

These examples are showing the effect of an infix operation with one operand that represents a single data item and the other operand representing a number of data items.

Let us now give some examples where both operands of an infix operation are streams of data items.

( 2, 3) + ( 4, 5, 6)?   ==>   ( 6, 7, 8, 7, 8, 9)

( 2, 3) * ( 4, 5, 6)?   ==>   ( 8, 10, 12, 12, 15, 18)

( 2, 3) - ( 4, 5, 6)?   ==>   ( -2, -3, -4, -1, -2, -3)

From these examples it will be clear what the general rules are for the evaluation of infix-operations on streams: Take from the left operand the first data item and apply the operation with that data item to all the data items of the right operand; take then the second data item of the left operand and apply the operation with that second data item to all the data items of the right operand again, and so on. We make that explicit in the following example:

( 2, 3, 4) * ( 4, 5, 6, 7)?  will be evaluated as:

( 2 * ( 4, 5, 6, 7),  3 * ( 4, 5, 6, 7),  4 * ( 4, 5, 6, 7) ) that is:

( ( 8, 10 ,12, 14), ( 12, 15, 18, 21), ( 16, 20, 24, 28) ) that is:

( 8, 10, 12, 14, 12, 15, 18, 21, 16, 20, 24, 28)

This example demonstrates another property: If an expression consists of an infix-operator and its two operands, then the number of resulting data items is equal to the product of the numbers of data items of each operand.  In our example 3 * 4 = 12.

Let us now use some examples of prefix operations:

- ( 2, 3, 4)?                 ==> ( -2, -3, -4)

+ ( 2.3, 3.4, 4.5)?           ==> ( +2.3, +3.4, +4.5)

~ ( true, false, true)?       ==> ( false, true, false)

Streams as arguments of functions are also allowed as shown in the following examples:

Let us compute the absolute values of a stream:

Convert a stream of real values to the corresponding integer values:

integer( ( .3, -5.7, 4.* 7.5) )?      ==>  (3, -5, 30 )

The abs and integer function are standard Elisa functions.

The rules for the evaluation of function calls are similar to the rules discussed before:

f( ( 2, 3, 4) )?         ==>   ( f(2), f(3), f(4) )

g( (2,3), (4,5) )?       ==>   ( g(2,4), g(2,5), g(3,4), g(3,5) )

The order of evaluation of infix operations, prefix operations and function calls are the same as the rules defined for the well-known single values. The evaluation of stream expressions in general, consists of the evaluation of its constituent operations according to the normal evaluation rules. For example,

( 2, 3, 4) - ( 5, 6) * ( 7, 8)?

is evaluated in the normal precedence order: first the multiplication operation and then the subtraction operation. We may also use range expressions as part of stream expressions as illustrated by the following examples:

Notice that the range operator .. has a higher precedence level than the * operator.

Another example of a different data type: Suppose we want to build a list of the lengths of the names in a list:

The size function is a standard Elisa function. It gives the length of an array. In Elisa text is the same as a character array.

Before proceeding to our next topic three remarks may be worthwhile: First, although we are using in many of our examples for the sake of simplicity integer numbers, the principles are equally applicable to other types of data items. The second remark is that single value expressions are special cases of the more general multiple value expressions. And the third remark is: a stream is not an object. It is a sequence of unconnected data items.

## Empty Streams

If we are searching for entities with specific properties such as all blue cars in the street or all employees speaking Chinese we may expect a number of items satisfying the criteria. However, it is also possible that there are no items with the required properties. How do we cope with these kinds of situations? To answer such questions, let us examine in more detail the range expression. A range expression represents a stream of integer values. To recall

m .. n represents the stream ( m, m + 1, m + 2, ..., n)

We distinguish three situations depending on the actual values of m and n:

if m < n the stream consists of n - m + 1 values

if m = n the stream consists of  only one value

if m > n the stream is empty: there are no values

The important question is: How are the above-mentioned operations defined for empty streams? The answer is very simple: any operation or function call where an operand represents an empty stream it will also produce an empty stream. In the following, we will represent an empty stream by two adjacent parentheses ( ), although this is not a legal language construct. Here are some examples of operations on empty streams:

2 * ( )?              ==> ( )

( ) + ( 4, 5, 6)?     ==> ( )

f(( ))?               ==> ( )

g((2,3),( ))?         ==> ( )

So, in general, if one of the operands in an expression represents an empty stream the whole expression represents an empty stream. Also, if one of the arguments of a function call represents an empty stream, the result of the function is an empty stream.

However, there are two exceptions to this rule. If an expression represents an empty stream and it is part of a serial-expression or is part of a list between curly brackets then the result is not necessarily the empty stream. The empty stream element will be skipped and the next stream element will be processed, as is shown by the following examples:

( 2, ( ), 5)?         ==>  ( 2, 5)

{ 3, ( ), 7}?         ==>  { 3, 7}

However, if all the elements of a serial expression, or of a list are empty then the whole list is empty.

# Multi-value Definitions

With the preceding constructs we are now able to define definitions that are representing multiple data items. Let us start with a simple example:

This definition is based on the range operation. It represents a number of multiple values. For example, the evaluation of f (3, 6) will result in the values (3, 4, 5, 6); but the evaluation of f (7, 2) will result in no value.

As explained earlier, the fact that our definition may produce more than one data item is reflected in its signature. A signature is the first rule of a definition. It specifies the name, the number and types of the parameters and the result specification. As part of the result specification a so-called quantifier may be used. A quantifier specifies how many data items may be returned. There are four quantifiers defined in the language with the following meaning:

 multi specifies that zero, one, or more data items of the given type may be returned single specifies that one and only one data item of the given type will be returned optional specifies that zero or one data item of the given type may be returned nothing specifies that no data item will be returned

If the quantifier multi is used in a specification then an evaluation of the definition produces as many data items as can be produced by the definition depending on the values of the arguments. Take as an example:

g (integer, integer) -> multi (integer);

g (p, q) = ( p - q, p + q, p .. q );

Execution of this definition will produce a stream of at least two data items but may be more, depending on the values of p and q. For example, the evaluation of g (7, 2) will result in only two data items: (5, 9); but the evaluation of g (3, 5) will result in the stream (-2, 8, 3, 4, 5).

The quantifier single is used if the definition produces one data item. If in a result specification no quantifier has been given, as default the quantifier single is assumed. This means, for example, that the definition:

F (integer, integer) -> integer;

F (x, y) = x + y;

is equivalent with:

F (integer, integer) -> single(integer);

F (x, y) = x + y;

If the quantifier optional is used in a specification then an evaluation of the definition produces zero, or maximally one data item, even if more data items can be produced by the definition. For example, if you need only one prime number, you may use the optional quantifier. The multi quantifier would give you all the prime numbers). The optional quantifier (as well as the multi quantifier) also takes care of the situation that there are no data items with the required characteristics.

The quantifier nothing is used if no data items are produced by the definition. The quantifier nothing can be interpreted as the name of a special, built-in type that has no values. Because there are no values, there are also no operations defined on nothing. Function-definitions specified with the nothing quantifier are comparable to what in some other programming languages are called procedures. Let us see how the nothing quantifier may be used in a definition:

G (integer, integer) -> nothing;

G (p, q) = print(p + q);

In this example, the definition calls another definition print (not defined here) that also returns nothing.

## Example: Parental Relations

To give you an impression of the power of definitions based on multi-values we introduce some definitions for parental relations. As said earlier, expressions are not restricted to integer values. Any type may be used in the signature of a definition. In our example it makes use of a symbolic enumeration type. The program describes parental relations that can be used to answer questions about ancestors. These relations are defined as follows:

type Person = (Mary, George, John, Liz, Albert, Alice, Jane, Harry, Unknown);

mother (Person) -> Person;

mother (=Mary)   = Liz;

mother (=George) = Liz;

mother (=John)   = Alice;

mother (=Liz)    = Jane;

mother (others)  = Unknown;

father (Person) -> Person;

father (=Mary)   = John;

father (=George) = John;

father (=John)   = Albert;

father (=Liz)    = Harry;

father (others)  = Unknown;

parents(Person) -> multi (Person);

parents(P) = (father(P),mother(P));

grandmothers(Person) -> multi(Person);

grandmothers(P) = (mother(father(P)), mother(mother(P)));

grandfathers(Person) -> multi(Person);

grandfathers(P) = (father(father(P)),father(mother(P)));

grandparents(Person) -> multi(Person);

grandparents(P) = parents(parents(P));

The first line in this example introduces the type Person and enumerates the names of the relevant persons, including Unknown persons. The following lines are introducing the mothers and the fathers of the different persons. And then some parental relations are given. Each parental relation defines that for a given person multiple persons may be returned. For example, a person has always two parents and four grandparents. So, the parent definition produces for one person two persons and a grandparent definition produces two times two persons. The parental relations are multi-value functions and are implemented by means of serial expressions.

In an interactive session we may question the system about the ancestors of a person. We show some questions with their answers:

mother(Mary)?                ==>     (Liz)

father(mother(George))?      ==>     (Harry)

parents(Mary)?               ==>     (John, Liz)

parents(Harry)?              ==>     (Unknown, Unknown)

grandfathers(Mary)?          ==>     (Albert, Harry)

grandparents(George)?        ==>     (Albert, Alice, Harry, Jane)

These examples illustrate that a single question may generate multiple answers.

The Parental Example has a number of characteristics:

• It is written in a functional style.

• It has no control statements such as  if, then, else, or for loops.

• It is declarative instead of imperative in nature.

• It is easily extendable with new definitions such as great-grandmother, great-grandparents, etc

• The definitions reflect the concepts of the problem space

To understand the implications of this approach you are invited to write a corresponding program in your favorite programming language.

My next tutorial will contain many more examples of multi-value expressions. It will also describe the use of the optional quantifier and the marriage of multi-value expressions with lists.