Campus Event Calendar

Event Entry

What and Who

A New Foundation for Computation and Approximation

Prof. Hassan Aït-Kaci
Simon Fraser University, Burnaby, Canada
AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, RG1, SWS  
AG Audience

Date, Time and Location

Monday, 23 October 95
60 Minutes


Lately, many disjoint computer formalisms seem to have come to very similar
stuctures. We have studied a few of them, among which (non-exhaustively):

- - monads and continuation-passing style in functional programming;
- - Definite Clause Grammars (DCG's) and accumulators in logic programming;
- - Montague grammars and Lambek Calculus (and extensions);
- - incremental constraint solving and entailment;
- - linear logic and resource-bound computation;
- - etc. . .

We expose a very simple algebraic structure that - precisely because
it is so simple - universally spans a large set of these and other
varied programming stuctures as distinct incarnations of essentially
the same idea. We motivate our idea with specific, actual, and very
practical examples. We then formalize it rigorously, study its
essential algebraic and order-theoretic characteristics, and then
propose a universal efficient implementation architecture for the
realization of a generic monoidal engine. We use the latter with
several instances to show the power of the principle of our discovery
for programming. We also discuss some extensions and future works.

Starting from the algebraic structure of a monoid, we characterize a
simple variant structure that models a wealth of hitherto
independent, and apparently unrelated, manifestations of the same
principle, both within programming language formalisms and without.
Among the manifestations in the domain of programming languages let
us cite: functional continuation structures (e.g., SCHEME'S or ML's
call/cc), or more generally the notion of monad; the logic
programming definite-clause grammar (DCG) formalism, or more
generally LIFE's calculus of accumulators; BinProlog's CPS-based
implementation; "Ask/Tell" coroutining in the cc family of
Concurrent Constraint (logic) programming languages or LIFE's
residuation; Dataflow architecture's I- and M-Structures or
Mulitilisp's futures; so-called (extendible) record, and record type,
calculi; and many, many other instances. Outside the programming
language area, instances range from formal linguistics (Lambek's
calculus), symbolic computation (Solving Linear [In/Dis] Equations),
operations research (Solving Linear [In/Dis] Equations), and Database
systems (wether logical, algebraic, or Constraint-based, etc. . . ).

Keywords Monoids, Monads, Accumulators, Algebraic programming,
Functional programming, Logic programming, Abstract Interpretation,
Regular Languages, Unification, Residuation, Lambek Calculus,
Categorial Grammars


Prof. Gert Smolka
0681 302-5310
--email hidden
passcode not visible
logged in users only