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.
The following notation is used in this documentation:
- is a plain Scheme0 program
- is an annotated (two-level) Scheme0 program
- is a tuple of argument binding times S and D
- is a possibly polyvariant division
- 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.
(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))))
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
- Initial version
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.