[[tags: egg]]
[[toc:]]
== 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
[[http://www.itu.dk/people/sestoft/pebook/pebook.html|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
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.
polydiv program sdpattern
Similar to {{monodiv}}, but does a polyvariant binding time
analysis. Returns the resulting polyvariant division.
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.
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.
polytate program sdpattern
Similar to {{monotate}} but performs polyvariant binding time analysis and
annotation. Returns the annotated two-level {{Scheme0}} program.
spec annprogram staticinputs
Specializes the annotated annprogram with respect to the list
{{staticinputs}} of static argument values. Returns the residual {{Scheme0}}
program.
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.
polype program sdpattern staticinputs
Similar to {{monope}} but does polyvariant binding time analysis and
annotation. Returns the residual {{Scheme0}} program.
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.
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.