Summary
It
started as a simple thought experiment and it
ended with surprising results. The question was: what happens if we
extend single-value functions into multi-value functions. This tutorial
tries to answer that question. Its purpose is to serve as a contribution to the
discussions about future programming languages. It describes how
functions in programming languages can be extended with multi-value
facilities and how that influence program structures. We introduce
functions that can generate multiple results. In other words, this paper
is about single questions that expect multiple answers. Suppose, we have
a single function, not a program, that can answers questions like: "What are
the prime numbers below 10000?", we expect not one answer but several
answers. However, most programming languages provide only functions that
can deliver one answer at a time and procedures that deliver no value
at all. Clever programmers have discovered
ways to move around these restrictions. They put the multiple results in
an array or any other data structure and return that to the user.
However, this approach has a number of disadvantages. The called
function has to pack a number of answers and
the caller has the task of unpacking them. However, if the number of
answers is unknown as is the case of our prime number example, this
will not work. While at the input side of a
function multiple inputs are not much trouble, multiple outputs are
often being a nuisance.
The purpose of this tutorial is to demonstrate that extending the
concept of single-value functions to multi-value functions will offer
new possibilities of solving these kinds of problems.
|
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:
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 >>
12
<< answer >>
-10
<< answer >>
125
<< answer >>
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:
Compound Expressions
In general,
operations on expressions representing multiple data items are
straightforward extensions of operations on single data items. Here are
some examples:
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:
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:
2 * 1 .. 5?
==> ( 2, 4, 6, 8, 10)
1 .. 3 - 1 ..
3?
==> ( 0, -1, -2, 1, 0, -1, 2, 1,
0)
( 21, 2 * 13 .. 15, 33)? ==> ( 21, 26, 28,
30, 33)
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:
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.