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