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
DFKI-Kolloquium
AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 23 October 95
11:00
60 Minutes
43.1
1.01
Saarbrücken
Abstract
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
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
Contact
Prof. Gert Smolka
0681 302-5310
--email hidden
passcode not visible
logged in users only