##
David S. Warren

###
Applications of a General Evaluation Strategy for Recursive Definitions

Abstract:
In this talk I present a general evaluation strategy for recursive
definitions of relations based on caching of computed results,
a.k.a. tabling. The claim is that a programming language that includes
tabled evaluation can make the programming of certain kinds of
algorithms very easy and straightforward. Just as the addition of
recursive evaluation to Fortran or Cobol 40 years ago made some
algorithms (e.g. quicksort) trivial to express, so adding tabulation
to a programming language can make other algorithms (e.g. abstract
interpretation) very easy.

The talk is in two parts: 1) A review of general evaluation methods
for recursive definitions of functions and the presentation of tabled
evaluation and multi-valued functions, 2) Application of tabled
evaluation of multi-valued functions to problems of grammar processing
and abstract interpretation.

Brief Bio:

David Scott Warren is currently Professor of Computer Science at the
University at Stony Brook. He was recently elected a Fellow of the
ACM. He was chairman of the Stony Brook CS Department from
1996-1999. For the past eighteen years his research has centered
around a variety of topics in the area of logic programming. For
approximately ten years his focus has been the development of the XSB
tabled logic programming system. He is a Past President of the
Association for Logic Programming.

Host: Frank Pfenning

Appointments: Maury Burgwin

Principles
of Programming Seminars

POP Seminar

January 30, 2002

3:30 p.m.

Wean Hall 8220