Abstractions

[Laurent Martelli]

I'am currently working on IO services for OIL, and there's something
that bothers me. Until now, the body of services that I created with
lambda could be considered the specification of the service, since it
defines what the service does. For instance, I have defined append whose
body is 

   (if (= nil arg0) context 
        '(list arg1) 
        '(cons (car arg0) ((self) (cdr arg0) arg1)))

It may not be the user friendliest definition of append, but it is
one that is equivalent to 

        for all i in [0,len(L)], get(L,i) = get(append(L,X),i)
        get(append(L,X),len(L)+1) = X
        len(append(L,X)) = len(L+1)

which is more formal.

Now, I want to definea new service select(L), which returns an object
of L selected interactively by the user. I may implement this with
"low-level" IO services such putc and getc, maintaining a map which
associates a string to each object (the user would have to type the
string associated to the object that he wants to select). 

The issue is that the body of such a service will not represent its
specification, since the spec of the service (let's call it `select')
is rather "returns an object from the first argument (which must be a
list) selected interactively by the user". This "abstract" spec is
opened so that it can be implemented in multiple ways, depending on
the IO devices available.

That's important because if I want to communicate with other systems
which implement the service differently, the two systems need to know
that the two services, although implemented differently, represents
the same abstraction. So that if I send the body of service that use
`select', the other system will use its own `select', not mine.

So it looks in the end, that the system should allow to create new
abstractions, because the ones that are needed to express computations
(if, car, cdr, cons, eval, invoke, ...) are not suitable to express
user interaction with the system. And there are probably other things
that cannot be expressed with those services. 

So the real question is in fact : can we enumerate a finite list of
service/abstractions that are enough to express anything ?

We could start with these :

    - computation :
        cons
        car
        cdr
        consp
        if
        equal
        raise

    - programming/memory
        newvar
        getvar(VAR) : retrieve the value of VAR
        setvar(VAR,VAL) : set the value of VAR to VAL
        lambda
        lambdap
        invoke
        eval
        
    - user interaction/communication
        
    - real time                

    ... (you're welcome to complete the list)


The "user interaction" section seems to specially hard to describe
once for all since IO devices change with time. We could describe
services to intercat with keyboard and mice, but what if some creates
a devices that communicates directly with our minds ? However, as I am
writing this, his section could probably be best entitled
"communication". And I think that it could be handled with basic
services that send and receive bits.

What are your reactions ?

-- 
Laurent Martelli
martelli@iie.cnam.fr