A data model for HLL

[Marnix Klooster]

Hello all,

Having read the WWW-pages and some archived mail about the HLL, I
think the first priority in designing a high-level language is to
design a high-level data model.  Will data be active (coming into
action when changes in the environment take place) or passive (coming
out only when called upon)?  Are there going to be objects?  Message-
passing?  And so on...

The WWW-pages on the HLL talk about objects, functions, attributes,
contexts, classes, connecting objects, proofs, specifications, and
more.  It's too complex, if you ask me.  A useful HLL must be based
on a simple, yet powerful data model.  To get a discussion started,
let me put forward such a data model.  I call it...


Function-Based Computing
------------------------

Everything is a function, in the mathematical sense.  That is, a
function can be viewed as a (finite or infinite) collection of
input-output pairs, where for every input value there is at most one
output value.  (Note that these input and output values are also
functions.)  Two functions are considered 'the same' iff they give
the same results on all input values.

Functions simply exist; they cannot be created, changed or deleted.

The only way to use a function is to apply it to a value (i.e. a
function), and look at the result.  Applying a function to an input value
can:
(i)   result in the output value associated with the input value in
      the function;
(ii)  result in a special value (say BOTTOM) when the function gives
      no output value for the given input value;
(iii) generate no result at all, because the result should be kept
      secret, or because the computing machine is not capable of
      producing one.

                           *   *   *

Let's, for an example, look at the way a list datatype might be
implemented using functions.  [7,8,9] denotes the list containing
three elements (counting from zero).  It is a function that returns
an integer for input values 0, 1 and 2.

(i) When we apply this function to 0, the result is the first element
of the list:

  [7,8,9].0 --> 7                // the first element of [7,8,9] is 7

Here, "." stands for 'applied to', and "-->" stands for 'results in'.
To find out the length of a list, just apply it to the symbol
'length:

  [7,8,9].'length --> 3                     // [7,8,9] has 3 elements

(As is LISP, a symbol is just an identifier preceded by a single
quote.  The defining property of symbols is that they are different
of all other values.)

(ii) When we try to get the fourth element of this list, we hit BOTTOM:

  [7,8,9].4 --> BOTTOM           // 4 is not in the domain of [7,8,9]

because it has no fourth element.

(iii) What happens when we apply [7,8,9] to some strange symbol,
e.g. 'xyzzy?  The implementor of the datatype probably didn't give an
output value for this case, so we would expect

  [7,8,9].'xyzzy --> BOTTOM

But what if the implementor, for some reason, used 'xyzzy to return
the square of the length of the list?  The we would get

  [7,8,9].'xyzzy --> 9

In this case, the user of the list doesn't need to know what the
result is of applying [7,8,9] to 'xyzzy.  Therefore, the list
datatype is implemented in such a way that

  [7,8,9].'xyzzy --> ??                // no result can be computed

                           *     *     *

This data model is a simple one.  I think it is also powerful,
because functions can be used to model just about any data structure:
- a number is a function that has a number of 'methods',
  corresponding to operations on numbers; e.g.

    5.'neg --> -5
    1.'plus --> ...the function that adds 1 to any number...

- a list is a function whose domain contains a subset of the natural
  numbers.
- a state (environment, context) is a function from identifiers
  (symbols) to arbitrary values.
- a statement is a function from states to states.

                             *     *     *

The above data model is intended as a starting point for discussion.
Could it be used to build a working system on?

Let's hear _your_ opinion on this.

Keep up the good work,

 <><
Marnix
--
Marnix Klooster
klooster@dutiba.twi.tudelft.nl