home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / or / general / 473 < prev    next >
Encoding:
Internet Message Format  |  1992-07-21  |  3.3 KB
  1. Xref: sparky or.general:473 pdx.general:938 ogi.general:23
  2. Path: sparky!uunet!ogicse!ogicse.cse.ogi.edu!kelly
  3. From: kelly@ogicse.cse.ogi.edu (Kelly Atkinson)
  4. Newsgroups: or.general,pdx.general,ogi.general
  5. Subject: Computer Science Colloquium
  6. Message-ID: <40370@ogicse.ogi.edu>
  7. Date: 21 Jul 92 22:42:55 GMT
  8. Article-I.D.: ogicse.40370
  9. Sender: kelly@ogicse.ogi.edu
  10. Distribution: or
  11. Organization: Oregon Graduate Institute (formerly OGC), Beaverton, OR
  12. Lines: 60
  13.  
  14.  
  15.                 Computer Science & Engineering
  16.                        COLLOQUIUM SERIES
  17.  
  18.               Parameterized Partial Evaluation --
  19.                     Principle and Practice
  20.  
  21.                         Siau Cheng Khoo
  22.                         Yale University
  23.  
  24. Partial evaluation is the process of constructing a  new  program
  25. given some original program and a part of its input that is stat-
  26. ic. Examples of partial evaluation application include  achieving
  27. compilation  using interpreters and eliminating levels of instru-
  28. mentation in interpretation. Essentially, a partial evaluator  is
  29. a  program  specializer and is expected to produce more efficient
  30. programs.
  31.  
  32. In practice, there are two apparently independent  strategies  of
  33. partial  evaluation:  on-line  and  off-line.  An on-line partial
  34. evaluator processes a program in one  single  phase,  whereas  an
  35. off-line partial evaluator performs some analyses before special-
  36. izing the program.
  37.  
  38. Specializing programs with respect to static  properties  of  the
  39. input  (such  as signs, ranges, and types) is a natural extension
  40. of  partial  evaluation  and  significantly  contributes  towards
  41. adapting  partial evaluation to a larger variety of applications.
  42. Although work has been done in this direction, there has not been
  43. a  formal  treatment of this idea, and the systems developed thus
  44. far do not provide users with the capability of introducing stat-
  45. ic properties into the partial-evaluation process.
  46.  
  47. In this talk, I introduce the  notion  of  PARAMETERIZED  PARTIAL
  48. EVALUATION  -- a generic form of partial evaluation parameterized
  49. with respect to user-defined static properties. This  generaliza-
  50. tion  is  accomplished by introducing an algebraic framework that
  51. enables modular definition of static  properties  and  systematic
  52. incorporation  of  these  properties  into the partial-evaluation
  53. process. More specifically, from a concrete algebra, an  abstract
  54. algebra  called a FACET is defined; it is composed of an abstract
  55. domain --- capturing the properties of interest --- and a set  of
  56. abstract primitives that operate on this domain.
  57.  
  58. Not only does the framework guarantee the safety of the  partial-
  59. evaluation  process  with respect to the static properties intro-
  60. duced, but it also provides a new understanding of  the  relation
  61. between  on-line and off-line partial evaluation. Furthermore, it
  62. enables us to prove the correctness of  partial  evaluation  with
  63. polyvariant  specialization  (in  which any function in a program
  64. can have more than one specialized version), which was not possi-
  65. ble before.
  66.  
  67. Lastly, to demonstrate the effectiveness of parameterized partial
  68. evaluation,  I  provide  an implementation for first-order strict
  69. functional language with data structures and demonstrate its use-
  70. fulness with some applications.
  71.  
  72.                 Thursday - July 23, 10:30 a.m.
  73.                    Room 102, CSE Bldg., OGI
  74.