Evolving Algebras (was Re: Lambda-Calculus)

[Francois-Rene Rideau]

>>: Fare Rideau
>: Billy Tanksley

>> Perhaps there are simpler concepts that subsume
>> lambda-calculus and give better insight into programming languages;
>> if there are, I'll be glad to learn about them. I haven't seen them yet,
>> and lambda-calculus is so simple that I'd be surprised if/when I meet them.

> New things are always suprising. Almost always;
> sometimes their unsuprisingness is the thing that suprises me.

> Take a look at Abstract State Machines (Evolving Algebras)
> for an example right in your department (proof of correctness,
> translation from concept to code).  I for one
> consider them to be more useful than the lambda calculus,
> in that they adjust to how the machine works
> as well as how the algorithm works (and that adjustment
> can be tuned by the evaluator).

EAs don't fight in the same field as lambda-calculus.
lambda-calculus is a minimal structure to capture the essence
of functional abstraction; various different kinds of semantics
are associated to it (sometimes as a benchmark for semantic frameworks).
EAs try to capture the notion of operational semantics
as a framework applicable to any structure.

Now, even then, I'm not sure what EAs bring to operational semantics:
step semantics and rewrite logic are already long well-known techniques
for that, and EAs only look like a particular case of using them,
with a wired-in idiosyncratic representation of structures.

I for one think that rewrite logic (evolving elements of static algebras)
is much more basic than EAs, and is cleaner and clearer at separating
issues of rewrite from issues of structural interpretation.
EAs force the use of a given arbitrary meta-algebra with rewrite logic,
which complicates things without bringing much insight.
Well, I for one would certainly not deny the interest of being able
to use meta-structures. But this interest rests precisely
in making the meta-ization an explicit, separate, entity, worth in itself.
Which EAs just don't provide.

Now, if EAs can help spread the understanding of operational semantics,
then so be it. I know no web page for operational semantics with simple
tutorials as for EA. Maybe because operational semantics is so old and
well-known that enthusiastic discoverers didn't have the web at that time,
and researchers, being paid for writing new stuff, don't have time to
write nice tutorials in a central web page [If someone does have a
look, and finds nice such tutorials, maybe it's time to make a page, tho].

EAs look like to me they're going the ugly C++ way: building
a swiss-army-knife of a language, with all blades soldered in open position.
I prefer the clean CAML way: having a well-set toolbox,
orthogonally providing one well-defined tool for each independent concern.

Just my 0.02 Euro, anyway.

## Faré | VN: Уng-Vû Bân   | Join the TUNES project!  http://www.tunes.org/ ##
## FR: François-René Rideau |    TUNES is a Useful, Not Expedient System     ##
## Reflection&Cybernethics  | Project for a Free Reflective Computing System ##
        It is a profoundly erroneous truism, repeated by all copy-books and
by eminent people when they are making speeches, that we should cultivate
the habit of thinking about what we are doing.  The precise opposite is the
case.  Civilization advances by extending the numbers of important operations
which we can perform without thinking about them.  Operations of thought are
like cavalry charges in battle -- they are strictly limited in number, they
require fresh horses, and must only be made at decisive moments.
                -- Alfred North Whitehead