From: kelly@ogicse.cse.ogi.edu (Kelly Atkinson)
Newsgroups: or.general,pdx.general,ogi.general
Subject: Computer Science Colloquium
Date: 21 Jul 92 22:42:55 GMT
Article-I.D.: ogicse.40370
Distribution: or
Organization: Oregon Graduate Institute (formerly OGC), Beaverton, OR


                Computer Science & Engineering
                       COLLOQUIUM SERIES

              Parameterized Partial Evaluation --
                    Principle and Practice

                        Siau Cheng Khoo
                        Yale University

Partial evaluation is the process of constructing a  new  program
given some original program and a part of its input that is stat-
ic. Examples of partial evaluation application include  achieving
compilation  using interpreters and eliminating levels of instru-
mentation in interpretation. Essentially, a partial evaluator  is
a  program  specializer and is expected to produce more efficient
programs.

In practice, there are two apparently independent  strategies  of
partial  evaluation:  on-line  and  off-line.  An on-line partial
evaluator processes a program in one  single  phase,  whereas  an
off-line partial evaluator performs some analyses before special-
izing the program.

Specializing programs with respect to static  properties  of  the
input  (such  as signs, ranges, and types) is a natural extension
of  partial  evaluation  and  significantly  contributes  towards
adapting  partial evaluation to a larger variety of applications.
Although work has been done in this direction, there has not been
a  formal  treatment of this idea, and the systems developed thus
far do not provide users with the capability of introducing stat-
ic properties into the partial-evaluation process.

In this talk, I introduce the  notion  of  PARAMETERIZED  PARTIAL
EVALUATION  -- a generic form of partial evaluation parameterized
with respect to user-defined static properties. This  generaliza-
tion  is  accomplished by introducing an algebraic framework that
enables modular definition of static  properties  and  systematic
incorporation  of  these  properties  into the partial-evaluation
process. More specifically, from a concrete algebra, an  abstract
algebra  called a FACET is defined; it is composed of an abstract
domain --- capturing the properties of interest --- and a set  of
abstract primitives that operate on this domain.

Not only does the framework guarantee the safety of the  partial-
evaluation  process  with respect to the static properties intro-
duced, but it also provides a new understanding of  the  relation
between  on-line and off-line partial evaluation. Furthermore, it
enables us to prove the correctness of  partial  evaluation  with
polyvariant  specialization  (in  which any function in a program
can have more than one specialized version), which was not possi-
ble before.

Lastly, to demonstrate the effectiveness of parameterized partial
evaluation,  I  provide  an implementation for first-order strict
functional language with data structures and demonstrate its use-
fulness with some applications.

                Thursday - July 23, 10:30 a.m.
                   Room 102, CSE Bldg., OGI
Xref: sparky or.general:480 pdx.general:957 ogi.general:24