Re: RFC Walters' "Categories and Computer Science" : Functional Specification

[Sebastiano Vigna <vigna@gongolo.usr.dsi.unimi.it>]

On Mon, 7 Feb 2000, Bill Halchin wrote:

> 1) The method of specification defined in this section seems to be
> essentially a rewrite system, i.e. we do a series of rewrites or
> reductions on "data" (actually a certain kind of path in a Data graph)
> until we possibly terminate. Hence the finite set of Equation that
> Walters' describes is basically a set of rewrite rules, i.e.  one-way
> rules in Rewriting Systems parlance.

Yes. Indeed as part of my Ph.D. dissertation I wrote a complete specification
of the interpreter in ASF+SDF, a rewrite rule-based system for algebraic
specifications used at the University of Amsterdam. It can execute programs
of that kind. I can send it to you if you want so. The interpreter is
partially described also in the following papers:

Sebastiano Vigna. Specifying IMP(G) using ASF+SDF: A case study. In Proc. of
the ASF+SDF95 workshop on generating tools from algebraic specifications.
Technical Report P9504 of the University of Amsterdam, 1995.

Sebastiano Vigna. Towards an efficient implementation of distributive
programs. In Proc. of the 2nd International Workshop on the Theory and
Practice of Algebraic Specifications ASF+SDF, Workshops in Comput.
Springer-Verlag, 1998.


> 3) On pg. 118, there is a "Note" about work that Robie Gates did to show
> that we can achieve Turing completeness with this method of function
> specfication.i.e. we can compute all parial recursive functions from N to
> N. Hence the computation may not be terminating!!!! Otherwise, we would
> not have Turing completeness and could solve Halting problem.

Of course (the book is a bit confusing about this issue). Turing completeness
is proved in

Nicoletta Sabadini, Sebastiano Vigna, and Robert F.C. Walters. A note on
recursive functions. Math. Struct. Comp. Sci., 6:127-139, 1996.

and BSS (real numbers computability) completeness is proved in 

Sebastiano Vigna. On the relations between distributive computability and the
BSS model. Theoret. Comput. Sci., 162:5-21, 1996.

> 5) Finally and important to me, has work been continued by anyone else in
> this area?? I don't see any papers in Walters' groups archive!! This

Not to my knowledge, but you should ask Bob Walters directly.

Greetings,

					Sebastiano Vigna