scheme0-pe

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

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

monodivprocedure: 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.

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

annotateprocedure: 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.

monotateprocedure: 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.

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

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

monopeprocedure: 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.

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

makeprocedure: 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.

schemeprocedure: 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.

chickadee » scheme0-pe

Identifier search