## scheme0-pe

### Introduction

The `scheme0-pe` egg is a variant of the `Scheme0` partial evaluator adapted for Chicken. `Scheme0` is a first-order pure subset of Scheme described in the book Partial Evaluation and Automatic Program Generation.

### Notation

The following notation is used in this documentation:

`program`- is a plain
`Scheme0`program `annprogram`- is an annotated (two-level)
`Scheme0`program `sdpattern`- is a tuple of argument binding times
`S`and`D` `division`- is a possibly polyvariant division
`staticinputs`- is a tuple of static argument values

### Procedures

*[procedure]*

`monodiv program sdpattern`

Does a monovariant binding time analysis of the subject program program, given the binding times sdpattern of its goal function. Returns the resulting monovariant division.

*[procedure]*

`polydiv program sdpattern`

Similar to `monodiv`, but does a polyvariant binding time analysis. Returns the resulting polyvariant division.

*[procedure]*

`annotate program division`

Annotates the `Scheme0` program according to the monovariant or polyvariant division. May make several copies of each function for a polyvariant division. Returns the annotated two-level `Scheme0` program or reports that division is not congruent.

*[procedure]*

`monotate program sdpattern`

Does monovariant binding time analysis and an- notation of program given the binding times sdpattern of its goal function. Returns the annotated two-level `Scheme0` program.

*[procedure]*

`polytate program sdpattern`

Similar to `monotate` but performs polyvariant binding time analysis and annotation. Returns the annotated two-level `Scheme0` program.

*[procedure]*

`spec annprogram staticinputs`

Specializes the annotated annprogram with respect to the list `staticinputs` of static argument values. Returns the residual `Scheme0` program.

*[procedure]*

`monope program sdpattern staticinputs`

Does a monovariant binding time analysis and annotation of program, then specializes it with respect to the given static inputs `staticinputs`. Returns the residual `Scheme0` program.

*[procedure]*

`polype program sdpattern staticinputs`

Similar to `monope` but does polyvariant binding time analysis and annotation. Returns the residual `Scheme0` program.

*[procedure]*

`make f program`

Converts program from `Scheme0` to Scheme and defines a Scheme function f to invoke the converted program. Returns the name f. Side effect: Defines function f. This is for executing residual `Scheme0` programs.

*[procedure]*

`scheme program`

Converts program from `Scheme0` to Scheme, possibly renaming functions. Returns a list of Scheme function definitions. This is for studying residual Scheme0 programs.

### Representation of Scheme0 programs

A program must have at least one definition, and function definitions may have zero or more arguments.

program ::= (def ... def) def ::= (define (funcname var ... var) exp)

exp ::= () | number | var | (quote S-expression) | (if exp exp exp) | (call funcname exp ... exp) | (op basefunction exp ... exp)

Variables are Scheme symbols, that is, non-numeric atoms different from (). Function names may also be simple Scheme symbols, but in residual programs, a function name is a pair `(annotatedname . staticvalues)` of an annotated function name and the values of the function's static arguments for this variant. Annotated function names are those found in the annotated subject programs given to the specializer.

### Representation of two-level Scheme0 programs

program ::= (def ... def) def ::= (define (funcname (var ... var) (var ... var)) exp)

exp ::= () | number | var | (quote S-expression) | (ifs exp exp exp) | (ifd exp exp exp) | (calls funcname (exp ... exp) (exp ... exp)) | (calld funcname (exp ... exp) (exp ... exp)) | (ops basefunction exp ... exp) | (opd basefunction exp ... exp) | (lift exp)

A variable is a Scheme symbol as above, but a function name must have the form: `((f . dynvaroccs) . sdpattern)`.

Here `f` is a function name from the `Scheme0` subject program; `dynvaroccs` is a list of the number of occurrences of `f`'s dynamic parameters; and `sdpattern` describes the binding times of the parameters of this variant of `f`. Thus `f` is a Scheme symbol; `dynvaroccs` is a list of 0, 1, or 2, where 2 represents any number greater than 1; and `sdpattern` is a list of `S` and `D`.

The `sdpattern` component is used to distinguish the binding time variants of `f` and is present also in monovariantly annotated programs. The `dynvaroccs` component is used to avoid unfolding static calls to `f` when this may cause duplication of a non-trivial non-variable dynamic argument expression. This component could in principle be computed during specialization, in which case it need not be part of the function name, but this would incur unnecessary recomputation, so we choose to compute it when annotating the program.

### Examples

(use scheme0-pe)

(define ack '( (define (ack m n) (if (op equal? m 0) (op + n 1) (if (op equal? n 0) (call ack (op - m 1) 1) (call ack (op - m 1) (call ack m (op - n 1))))) ))) (pp (scheme ack)) (pp (scheme (monope ack '(S D) '(4))))

### Authors

The Scheme0 partial evaluator is described in Chapter 5 and Appendix A of the book:

N.D. Jones, C.K. Gomard, and P. Sestoft, Partial Evaluation and Automatic Program Generation. Prentice Hall International, June 1993. xii + 415 pages. ISBN 0-13-020249-5.

Available from http://www.itu.dk/people/sestoft/pebook/pebook.html

### Version

- 1.0
- Initial version

### License

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.